- •1. Цель и задачи курса «Методы оптимальных решений».
- •2. Классификация и специфика задач математического программирования (мп).
- •3. Основные этапы процесса моделирования задач мп.
- •4. Некоторые стандартные примеры математических моделей в мп (задача о рационе,
- •5. Основные понятия и факты, являющиеся базисными в теории оптимизации.
- •6. Теорема Каратеодори о выпуклой оболочке конечномерного пространства
- •7.Понятия целевая функция и ограничения задачи оптимизации
- •9. Математическая постановка задачи оптимизации.
- •10. Понятие компактности множества. Точная нижняя грань и точная верхняя грань.
- •11. Линейное программирование (лп). Специфика задач лп
- •13. Фундаментальное понятие базиса. Базисное, базисное допустимое и оптимальное базисное решение задачи лп.
- •14. Теорема, устанавливающая необходимое и достаточное условие существования базисного решения системы ограничений, безотносительно к способу их получения.
- •15. Геометрический смысл понятия базисного допустимого решения.
- •16. Критерий разрешимости задачи лп (с обоснованием).
- •17. Достаточное условие существования оптимального базисного решения (с обоснованием).
- •18. Неоднозначность терминологии лп: понятия матрица и вектор условий задачи лп, опорный план и оптимальный план задачи лп.
- •19. Идеи и принципиальные соображения, лежащие в основе конечных методов решения задач лп.
- •20. Элементарное преобразование базиса.
- •21. «Симплекс-таблица» и алгоритм ее построения.
- •22.Прямо и двойственно допустимые «симплекс-таблицы». Правило преобразование «симплекс-таблицы».
- •23. Достаточное условие оптимальности базисного решения задачи лп, основанное на характеристике «симплекс-таблицы».
- •24. Прямой «симплекс-метод» для решения задач лп и его обоснования.
- •25. Выбор столбца для ввода (вывода) в базис (из базиса) и неоднозначность данного выбора. Обоснования этих выборов.
- •26. Уточняющие правила, устраняющие возникающую неоднозначность при выборе ведущего столбца и/или ведущей строки: частичное или полное уточняющие правила Данцинга и Блэнда.
- •27. Рекуррентные соотношения алгоритма прямого «симплекс-метода» (связь между параметрами последовательных итераций).
- •28. Вопрос конечности алгоритма «симплекс-метода».
- •29. Проблема зацикливания алгоритма прямого «симплекс-метода».
- •30. Вырожденное базисное допустимое решение и вырожденная задача лп.
- •31. Возврат к пройденной угловой точке множества допустимых решений при преобразовании «симплекс-таблицы». Пути выхода из зацикливания в случае вырожденности задачи лп.
3. Основные этапы процесса моделирования задач мп.
Под принятием решений в исследовании операций понимают сложный процесс, в котором можно выделить следующие основные этапы:
1-й этап. Построение качественной модели рассматриваемой проблемы, т. е. выделение факторов, которые представляются наиболее важными, и установление закономерностей, которым они подчиняются. Обычно этот этап выходит за пределы математики.
2-й этап. Построение математической модели рассматриваемой проблемы, т. е. запись в математических терминах качественной модели. Таким образом, математическая модель – это записанная в математических символах абстракция реального явления, так конструируемая, чтобы анализ ее давал возможность проникнуть в сущность явления. Математическая модель устанавливает соотношения между совокупностью переменных – параметрами управления явлением. Этот этап включает также построение целевой функции переменных, т. е. такой числовой характеристики, большему (или меньшему) значению которой соответствует лучшая ситуация с точки зрения принимающего решения.
Итак, в результате этих двух этапов формируется соответствующая математическая задача. Причем, второй этап уже требует привлечения математических знаний.
3-й этап. Исследование влияния переменных на значение целевой функции. Этот этап предусматривает владение математическим аппаратом для решения математических, задач, возникающих на втором этапе процесса принятия, решения.
Широкий класс задач управления составляют такие экстремальные задачи, в математических моделях которых условия на переменные задаются равенствами и неравенствами. Теория и методы решения этих задач как раз и составляют содержание математического программирования. На третьем этапе, пользуясь математическим аппаратом, находят решение соответствующих экстремальных задач. Обратим внимание на то, что задачи математического программирования, связанные с решением практических вопросов, как правило, имеют большое число переменных и ограничений. Объем вычислительных работ для нахождения соответствующих решений столь велик, что весь процесс не мыслится без применения современных электронных вычислительных машин (ЭВМ), а значит, требует либо создания программ для ЭВМ, реализующих те или иные алгоритмы, либо использования уже имеющихся стандартных программ.
4-й этап. Сопоставление результатов вычислений, полученных на 3-м этапе, с моделируемым объектом, т. е. экспертная проверка результатов (критерий практики). Таким образом, на этом этапе устанавливается степень адекватности модели и моделируемого объекта в пределах точности исходной информации. Здесь возможны два случая: 1-й случай. Если результаты сопоставления неудовлетворительны (обычная ситуация на начальной стадии процесса моделирования), то переходят ко второму циклу процесса. При этом уточняется входная информация о моделируемом объекте и в случае необходимости уточняется постановка задачи (1-й этап), уточняется или строится заново математическая модель (2-й этап), решается соответствующая математическая задача (3-й этап) и, наконец, снова проводится сопоставление (4-й этап). 2-й случай. Если результаты сопоставления удовлетворительны, то модель принимается. Когда речь идет о неоднократном использовании на практике результатов вычислений, возникает задача подготовки модели к эксплуатации. Предположим, например, что целью моделирования является создание календарных планов производственной деятельности предприятия. Тогда эксплуатация модели включает в себя сбор и обработку информации, ввод обработанной информации в ЭВМ, расчеты на основе разработанных программ календарных планов и, наконец, выдачу результатов вычислений (в удобном для пользователей виде) для их использования в сфере производственной деятельности.