Новосибирский государственный университет
Кафедра теоретической кибернетики

Thin_Red_and_BlueA205.gif (1558 bytes)

А. В. Плясунов 
Методы оптимизации

ММФ, 3 курс, весенний семестр

Вопросы теоретического минимума

1. Задачи линейного программирования.  Базисные решения и крайние точки линейного многогранного множества (Доказательство эквивалентности (Лемма 1.3)).  Необходимые и достаточные условия разрешимости задачи ЛП (Теорема 2.1 с доказательством). Существование  оптимального  базисного  решения (Лемма 2.1 с доказательством).  Элементарные преобразования базиса и симплексной таблицы (Лекция № 2). Симплекс-метод (Лекция № 3). Конечность симплекс-метода: 1. Невырожденность (Лекция № 3). 2. Вырожденность: лексикографический вариант симплекс-метода (Лекция № 3). Поиск начального базисного  допустимого  решения (Конец лекции № 3 – начало лекция № 4).

Двойственные задачи линейного  программирования  и  теоремы двойственности (Лекция № 4 с доказательством). Двойственный симплекс-метод (Лекция № 5).

2. Задачи нелинейного программирования. Теоремы отделимости выпуклых множеств (Теоремы 5.1-5.3 из Лекции № 5, Теорема 6.1 из Лекции № 6 с доказательством). Выпуклые конусы (Лекция № 6). Сопряженные конусы и их свойства (Лекция № 6, леммы 6.1-6.4 с доказательствами, леммы 6.5-6.6-формулировки). Теорема Дубовицкого-Милютина (с доказательством, Лекция № 6). Конусы  внутренних и предельных  направлений и  основное  необходимое условие оптимальности (с доказательством, Лекция № 6). Обобщенное правило множителей Лагранжа (Лекция № 7 - формулировка). Необходимое условие Куна-Таккера (Лекция № 7 - формулировка).

Задачи выпуклого программирования.  Субградиенты  выпуклых функций. Седловые точки функции Лагранжа и  теорема  Куна-Таккера (Лекция № 8 - уметь доказывать). Фрагмент общей теории двойственности на основе функции Лагранжа (начало Лекции № 9 - уметь доказывать теорему (без номера)).

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

4. Задачи вариационного исчисления и оптимального управления. Постановка задач. Сильный  и  слабый экстремумы. Необходимые условия экстремума для  простейших  задач вариационного исчисления (В виду тривиальности идеи и простоты реализации – знать вывод и по Лагранжу, и по Дюбуа – Раймону).

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

 

Список основной и дополнительной литературы.

 

 1. Алексеев В.М., Тихомиров В.М.,  Фомин  С.В.  Оптимальное управление. - М.: Наука, 1979. 

 2. Болтянский В.Г. Математические методы  оптимального  управления. - М.: Наука, 1969. 

 3. Васильев Ф.П. Численные методы решения экстремальных задач. - М.: Наука, 1989.  

4. Глебов Н.И., Кочетов Ю.А., Плясунов А.В. Методы оптимизации. Учеб. пособие - Новосиб. ун-т. Новосибирск, 2000. 

 5. Карманов В.Г. Математическое программирование. -  М.: Наука, 1986.  

6. Мину М. Математическое программирование. Теория и алгоритмы. - М.: Наука, 1990.  

7. Моисеев Н.Н., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. - М.: Наука, 1978.  

8. Алексеев В.М., Галеев Э.М., Тихомиров В.М. Сборник задач по оптимизации. - М.: Наука, 1984. 

9. Заславский Ю.Л. Сборник задач по линейному программированию. - М.: Наука, 1969.  

10. Ларин Р.М., Плясунов А.В., Пяткин А.В. Методы оптимизации. Примеры и задачи. Учебное пособие. Изд. НГУ, Новосибирск, 2003.