ПРОГРАММА КУРСА «МЕТОДЫ  ОПТИМИЗАЦИИ»
ФИТ  НГУ, 3 курс, 1 семестр

1. Введение. Задачи математического программирования. Выпуклые множества и функции, примеры. Выпуклая комбинация точек и выпуклая оболочка множества. Лемма Каратеодори.

2. Задачи линейного программирования. Базисные решения и крайние точки линейного многогранного множества. Существование оптимального базисного решения. Необходимые и достаточные условия разрешимости задачи линейного программирования. Симплексная таблица.  Элементарные преобразования базиса и симплексной таблицы. Алгоритм симплекс-метода с использованием симплексных  таблиц. Поиск начального базисного  допустимого  решения. Конечность симплекс-метода и вырожденность задачи линейного программирования. Лексикографический вариант симплекс-метода и доказательство его конечности. Двойственные задачи линейного  программирования; правила построения и простейшие свойства. Первая теорема двойственности. Вторая теорема двойственности (условия дополняющей нежесткости). Двойственный симплекс-метод.

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

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

5. Задачи целочисленного линейного программирования. Общая идея методов отсечения.  Лексикографический двойственный симплекс-метод (LD–метод). Способ построения дополнительных ограничений (отсечений). Первый (циклический) алгоритм Гомори и доказательство его конечности.

 ЛИТЕРАТУРА

1. Глебов Н.И., Кочетов Ю.А., Плясунов А.В. Методы оптимизации. Учебное пособие, НГУ, 2000.
2. Васильев Ф.П. Численные методы решения экстремальных задач. М.: Наука, 1980.
3. Карманов В.Г. Математическое программирование. М.: Наука, 1986.
4. Моисеев Н.Н., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. М.: Наука, 1978.
5. Ху Т. Целочисленное программирование и потоки в сетях. М.: Мир, 1974.