МЕТОДЫ ОПТИМИЗАЦИИ

Лектор: профессор Н. И. Глебов

6 семестр

Математическое программирование

1. Задачи линейного программирования. Базисные решения и крайние точки линейного многогранного множества. Необходимые и достаточные условия разрешимости задачи ЛП. Существование оптимального базисного решения. Элементарные преобразования базиса и симплексной таблицы.

Алгоритм симплекс–метода с использованием симплексных таблиц. Поиск начального базисного допустимого решения. Конечность симплекс–метода. Вырожденность. Лексикографический вариант симплекс–метода.

Двойственные задачи линейного программирования и теоремы двойственности. Двойственный и модифицированный симплекс–методы.

2. Задачи нелинейного программирования. Теоремы отделимости выпуклых множеств. Выпуклые конусы. Сопряженные конусы и их свойства. Теорема Дубовицкого – Милютина. Конусы внутренних и предельных направлений и основное необходимое условие оптимальности. Обобщенное правило множителей Лагранжа. Необходимое условие Куна – Таккера.

Задачи выпуклого программирования. Субградиенты выпуклых функций. Седловые точки функции Лагранжа и теорема Куна – Таккера.

3. Численные методы нелинейного программирования. Градиентные методы и метод Ньютона для задач без ограничений; теоремы о сходимости. Метод возможных направлений и методы штрафных функций для задач с ограничениями.

Оптимизация в функциональных пространствах

1. Задачи вариационного исчисления. Сильный и слабый экстремумы. Необходимые условия экстремума для простейших задач вариационного исчисления.

2. Задачи оптимального управления. Постановка задач. Допустимые управления. Принцип максимума Понтрягина.

Линейная задача оптимального быстродействия. Свойства сфер достижимости. Условие общности положения. Необходимость и достаточность принципа максимума. Свойства траекторий, удовлетворяющих принципу максимума. Теоремы о числе переключений.

Литература

  1. Алексеев В. М., Тихомиров В. М., Фомин С. В. Оптимальное управление. М.: Наука, 1979.
  2. Болтянский В. Г. Математические методы оптимального управления. М.: Наука, 1969.
  3. Васильев Ф. П. Численные методы решения экстремальных задач. М.: Наука, 1989.
  4. Глебов Н. И., Кочетов Ю. А., Плясунов А. В. Методы оптимизации /Учебное пособие /Новосиб. гос. ун-т. Новосибирск, 2000.
  5. Карманов В. Г. Математическое программирование. М.: Наука, 1986.
  6. Мину М. Математическое программирование. Теория и алгоритмы. М.: Наука, 1990.
  7. Моисеев Н. Н., Иванилов Ю. П., Столярова Е. М. Методы оптимизации. М.: Наука, 1978.
  8. Сухарев А. Г., Тимохов А. В., Федоров В. В. Курс методов оптимизации. М.: Наука, 1986.
  9. Алексеев В. М., Галеев Э. М., Тихомиров В. М. Сборник задач по оптимизации. М.: Наука, 1984.
  10. Заславский Ю. Л. Сборник задач по линейному программированию. М.: Наука, 1969.