Методы оптимизации

 

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

 

Список тем

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

 

Преподаватели: доцент, кандидат ф.-м. наук Ефимова Галина Алексеевна,

ст. преподаватель, кандидат ф.-м. наук Страхов Евгений Михайлович

 

Учебные материалы

1. Методические указания: "Методы минимизации функций" (в формате DJVU)

2. Методические указания: "Целочисленное программирование" (в формате PDF)

 

 

 

ЛАБОРАТОРНЫЕ РАБОТЫ

Задания	Описание	Срок сдачи
РГР № 1 "Численные методы безусловной минимизации функций"
Задание № 1	Методы одномерного поиска
Задание № 2	Методы многомерной минимизации нулевого порядка
Задание № 3	Методы многомерной минимизации первого порядка
Задание № 4	Методы многомерной минимизации второго порядка
РГР № 2 "Численные методы условной оптимизации"
Задание № 1	Методы условной оптимизации