Методы оптимизации, ВИ и ТУ (механика)

 

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

Рассматриваются численные методы решения нелинейных задач условной и безусловной оптимизации различных типов, студенты учатся выбирать наилучший метод для решения при определенных условиях, анализировать полученное решение.

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

Излагаются основы теории оптимального управления в линейных и нелинейных системах и ее центральный результат – принцип максимума Понтрягина. Рассматривается ряд примеров применения принципа максимума для построения оптимальных решений, а также численные методы решения задач управления. Внимание уделяется выявлению связи вариационного исчисления и теории оптимального управления.

 

Список тем

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

 

Преподаватели: ст. преподаватель, Огуленко Алексей Павлович

 

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

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

2. Материалы для подготовки к контрольным работам: задача условного экстремума.

 

Баллы

 

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

Задания	Описание	Срок сдачи
РГР № 1 "Численные методы безусловной минимизации функций"
Задание		25.05.2016
РГР № 2 "Численные методы оптимального управления"
Задание	Метод стрельбы Метод Эйлера численного решения ОДУ	15.06.2016