1. Задачи линейного программирования.
Лемма Каратеодори (Леммы 1 и
2). Базисные решения и крайние точки линейного многогранного множества
(Доказательство эквивалентности (Лемма 4)). Вырожденные и невырожденные
б.д.р. (Лемма 3 (с доказательством), примеры). Необходимые и достаточные
условия разрешимости задачи ЛП (Теорема 1 с доказательством).
Элементарное преобразование б.д.р., базиса и симплексной таблицы (Лекция
№ 3). Геометрический смысл элементарного преобразования б.д.р, как
движения по конечному или бесконечному ребру. Симплекс-метод (Лекция №
3). Конечность симплекс-метода: 1. Невырожденный случай (Лекция № 3). 2.
Вырожденный случай: лексикографический вариант симплекс-метода (Лекция №
4). Поиск начального базисного допустимого решения (Лекция № 4).
Двойственные задачи линейного программирования (Лекция № 4, включая
леммы 5 и 6) и теоремы двойственности (Лекция № 5 с доказательством).
Двойственный симплекс-метод (Лекция № 5).
2. Задачи нелинейного программирования.
Теоремы отделимости выпуклых множеств (формулировки Теорем 5-8 из Лекции
№ 6, знать доказательство Теоремы 5). Выпуклые конусы (Лекция № 6).
Сопряженные конусы и их свойства (Лекция № 6, леммы 7-9 с
доказательствами, леммы 10-11-формулировки). Теорема
Дубовицкого-Милютина (с доказательством, Лекция № 7). Конусы внутренних
и предельных направлений и основное необходимое условие оптимальности
(с доказательством, Лекция № 7). Конусы внутренних и предельных
направлений для задачи нелинейного программирования. Сопряженные конуса
(с доказательством). Обобщенное правило множителей Лагранжа (Лекция № 7
- формулировка). Необходимое условие Куна-Таккера (Лекция № 8 -
формулировка).
Задачи выпуклого программирования.
Субградиенты выпуклых функций. Седловые точки функции Лагранжа и
теорема Куна-Таккера (Лекция № 9 - уметь доказывать). Фрагмент общей
теории двойственности на основе функции Лагранжа (начало Лекции № 9 -
уметь доказывать теорему (без номера)).
3. Численные методы нелинейного
программирования. Градиентные
методы и метод Ньютона для задач без ограничений (описание методов);
теоремы о сходимости (формулировки). Методы штрафных функций для задач с
ограничениями (Лекции № 12 и 13 – описание методов, плюсы, минусы, уметь
доказывать одну из двух теорем сходимости (на выбор)). Метод
покоординатного спуска и метод Келли (Лекции № 13 и 14 – описание,
доказательство сходимости).
