Методы оптимизации
В данном курсе студенты (специальность - "Математика") знакомятся с принципами построения математических моделей экономических задач, с симплекс-методом решения задач линейного программирования и с методами решения транспортных задач. Рассматриваются численные методы решения нелинейных задач условной и безусловной оптимизации различных типов, студенты учатся выбирать наилучший метод для решения при определенных условиях, анализировать полученное решение.
Список тем
- Классификация задач оптимизации.
- Типы задач линейного программирования (ЗЛП). Понятия плана, опорного плана, базиса опорного плана, вырожденного и невырожденного опорного плана. Свойства планов ЗЛП.
- Теория двойственности. Двойственная задача к ЗЛП. Экономический смысл двойственных переменных для задачи линейного программирования в стандартной форме.
- Теоремы двойственности. Условия дополняющей нежесткости. ЗЛП в базисной форме. Условия допустимости и оптимальности. Симплекс-метод.
- Двухэтапный симплекс-метод. М-метод решения ЗЛП. Двойственный симплекс-метод. Обоснование двойственного симплекс-метода.
- Параметрическое программирование. Анализ на чувствительность.
- Задачи транспортного типа (ТЗ). Вид матрицы основных ограничений. Особенности ТЗ. Линейная зависимость и циклы. Опорный план ТЗ.
- Методы построения начального плана. Двойственная задача к ТЗ. Проверка плана на оптимальность. Построение нового опорного плана. Метод потенциалов. Неединственность решения ТЗ.
- Запрещенные и обязательные перевозки. ТЗ с ограничениями на пропускную способность. Доставка груза в кратчайший срок. ТЗ с промежуточными пунктами.
- Целочисленное программирование (ЗЦП). Метод ветвей и границ решения ЗЦП. Метод отсечения решения ЗЦП.
- Классификация численных методов нахождения минимума функции.
- Методы одномерной оптимизации:
- дихотомический поиск,
- метод деления отрезка пополам,
- метод «золотого сечения»,
- метод Фибоначчи,
- методы полиномиальной аппроксимации.
- Необходимые и достаточные условия оптимальности для решения задач безусловной оптимизации.
- Численные методы многомерной оптимизации:
- градиентные методы,
- метод Ньютона и его модификации,
- методы переменной метрики.
- Задачи на условный экстремум. Метод множителей Лагранжа. Необходимые и достаточное условия экстремума для задачи с ограничениями-равенствами и ограничениями –неравенствами.
- Численные методы решения задач условной оптимизации метод:
- линеаризации,
- методы штрафных функций,
- метод модифицированной функции Лагранжа.
- Выпуклое программирование. Седловая точка функции Лагранжа. Теорема о седловой точке. Теорема об отделимости выпуклых множеств. Теорема о строгой отделимости. Основная теорема выпуклого программирования.
- Теория двойственности для задач нелинейного программирования.
- Численные методы решения задач выпуклого программирования:
- метод проекции градиента,
- метод условного градиента,
- методы возможных направлений,
- метод приведенного градиента.
Учебные материалы