Моделирование задач с использованием математического программирования

[1]; [4] Т. 1, c. 25-132

В процессе принятия решения важную роль играет задача, связанная с выбором наилучшего из всех возможных способов действий, т.е. оптимального. Таковой является задача математического программирования. Определяется предмет и область применения данной задачи, указывается, что не для всех этих задач разработаны методики решения. Одной из наиболее решаемых задач является задача линейного программирования.

Определяется общий вид задачи линейного программирования, указываются, варианты для которых разработаны точные и однозначные методики ее решения. Приводится каноническая форма задачи линейного программирования и дается методика ее получения.

Для отдельного класса задач – при наличии только двух неизвестных – разработана методика определения оптимального решения на геометрической плоскости. Геометрическая интерпретация задачи линейного программирования, области допустимых планов. Теорема об оптимальности в области допустимых планов. Методика построения произвольного допустимого плана и определения оптимального плана.

Достаточно часто используется на практике один из частных классов задачи линейного программирования – транспортная задача линейного программирования. Постановка транспортной задачи линейного программирования и разработка математической модели транспортной задачи. Методика решения транспортной задачи: приведение транспортной задачи к канонической форме, определение начального допустимого плана и методика его улучшения. Оптимальность полученного решения транспортной задачи линейного программирования. Возможная неоднозначность полученного решения.

Зачастую исследуются технические процессы, которые развиваются во времени, и, при этом допускают огромное множество возможных решений. Для решения задач такого типа используется метод динамического программирования. Определяется предмет и область применения динамического программирования. Формулируется теорема Беллмана, позволяющая определить общую методологию получения оптимального решения. Методика получения оптимального по произвольному критерию решения задачи: метод «Киевского веника».

После изучения темы студент должен иметь представление об основных методах линейного программирования; знать формулировку основных теорем задач математического программирования; уметь формулировать и ставить задачи линейного программирования, транспортную задачу линейного программирования и сводить эти задачи к канонической форме; иметь понятие о постановке задачи динамического программирования; уметь решать задачу линейного программирования на плоскости для двух неизвестных.

ВОПРОСЫ ДЛЯ САМОПРОВЕРКИ

1. Пояснить разницу между понятиями оптимальное и рациональное решение.

2. Общая постановка задачи математического программирования, возможность ее однозначного решения.

3. Постановка задачи линейного программирования: целевая функция и ограничения.

4. Методика приведения задачи линейного программирования к каноническому виду.

5. Геометрическая интерпретация задачи линейного программирования.

6. Область допустимых планов, методика ее получения.

7. Теорема об оптимальности решения задачи линейного программирования.

8. Постановка транспортной задачи линейного программирования.

9. Математическая модель транспортной задачи линейного программирования.

10. Сведение транспортной задачи линейного программирования к канонической форме.

11. Постановка задачи динамического программирования. Класс задач, решаемых с использованием метода динамического программирования.

12. Теорема Беллмана и ее применение для решения задач данного класса.

Поиск по сайту: