Новосибирский государственный университет
Кафедра дискретного анализа и исследования операций

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

3 курс, ФИТ, НГУ, 1 семестр,  2009 г.  

 Вопросы коллоквиума-1  

1.     Понятие экстремальной задачи. Элементы алгоритмической теории экстремальных задач. Классификация задач математического программирования (Лекция 1). 

2.  Элементы Лагранжевой теории двойственности нелинейного программирования: функция Лагранжа, определение седловой точки, определение двойственной задачи. Леммы 1 и 2 (Лекция 2). 

3.  Теорема 1 (теорема о седловой точке). Следствия 1 и 2 (Лекция 2). 

4.  Задача двойственная к канонической задаче ЛП. Теорема 2. Общая схема формирования двойственных задач линейного программирования. (Лекция 2) 

5.  Задачи линейного программирования. Базисные решения (два определения) и крайние точки линейного многогранного множества. Вырожденнные и невырожденные б.д.р. Примеры (Лекция 3). 

6.  Эквивалентность базисных решения и крайних точек линейного многогранного множества (Лекция 3 (Теорема 3)

7.  Необходимые и достаточные условия разрешимости задачи линейного программирования. Существование оптимального базисного решения (Лекция  № 3 (Теорема 4, Следствия 3 и 4)). 

8.  Симплексная таблица.  Элементарные преобразования базисного допустимого решения (б.д.р.), базиса и симплексной таблицы (Лекция 4). 

9.  Геометрическая интерпретация элементарного преобразования б.д.р. Геометрический смысл столбца коэффициентов замещения с.-т.  (Лекция 4 (Включая лемма 4, 5, 6)). 

10. Конечность симплекс-метода для невырожденной задачи линейного программирования. Эффект зацикливания. Лексикографический вариант симплекс-метода и доказательство его конечности (Лекция 5) 

11. Двухфазный симплекс-метод или метод искусственного базиса (Лекция 6). 

12. Теорема Фаркаша – Минковского, её эквивалентная переформулировка (Лекция 6). 

13. Теорема Гордана (Лекция 6). 

14. Первая и вторая теоремы двойственности (Лекция 6).

Лектор к.ф.м.н., доцент А.В. Плясунов

Редакция 28.10.2009