ЛИНЕЙНОЕ  И  НЕЛИНЕЙНОЕ
ПРОГРАММИРОВАНИЕ

   Линейное  программирование

1. ВВЕДЕНИЕ
1. Истоки системного анализа. Краткий исторический очерк.
2. Системный анализ и моделирование
3. Основные этапы принятия решений
4. Принципы построения математических моделей
5. Типы математических моделей
6. Классический пример задачи ЛП
2. ГРАФИЧЕСКОЕ РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ (ЛП)
1. Постановка задачи ЛП. Основные понятия
2. Каноническая задача ЛП
3. Теорема эквивалентности 1. 
4. Теорема эквивалентности 2. 
5. Пример:  Привести к канонической форме задачу
6. Геометрическая интерпретация задачи ЛП.
7. Общие рекомендации к графическому решению задач ЛП
8. Пример: Решить графически задачу ЛП, заданную в канонической форме
9. Идея методов решения задачи ЛП.  Теорема о достижимости оптимума задачи ЛП в крайней точке.
3. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ЛП
1. Базисные допустимые решения.
2. Пример
3. Базисные решения и крайние точки.  Теорема о базисных решениях и крайних точках.
4. Специальная задача ЛП
5. Правила преобразования симплексных таблиц
6. Пример
7. Теоретические основы симплекс-метода. Критерий оптимальности.
8. Критерий неограниченности целевой функции.
9. Теорема о ключевом отношении
10. Теорема об улучшении базисного решения
11. Алгоритм симплекс-метода.
12. Пример. Решить задачу ЛП, записанную в виде (17)
4. CИМПЛЕКС-МЕТОД  ДЛЯ  ЗАДАЧИ  ЛП  НА  МАКСИМУМ
1. Каноническая  задача  ЛП  на  максимум
2. Вспомогательная задача ЛП.
3. Критерий существования планов канонической задачи ЛП
4. Теорема о преобразовании КЗЛП в эквивалентную СЗЛП
5. Алгоритм метода искусственного базиса
6. Пример
7. План решения задачи ЛП
5. КОНЕЧНОСТЬ СИМПЛЕКС-МЕТОДА В НЕВЫРОЖДЕННОМ  СЛУЧАЕ
1. Теорема о конечности симплекс-метода для невырожденнной задачи ЛП.
2. Вырожденность и зацикливание
3. Теорема об однозначном определении индексной строки базисом
4. Лексикографический симплекс-метод
5. Алгоритм лексикографического симплекс-метода
6. Теоретическое обоснование лексикографического симплекс-метода.
7. Теорема о конечности лексикографического симплекс-метода 
8. Двойственный симплекс-метод
6. ДВОЙСТВЕННОСТЬ   В  ЛП
1. Правила построения пары двойственных задач
2. Пример построения пары двойственных задач
3. Основное неравенство двойственности
4. Следствие (достаточное условие оптимальности)
5. Леммы Фаркаша
6. Основная лемма
7. Первая теорема двойственности
8. Вторая теорема двойственности
9. Лемма о супремуме целевой функции
10. Критерий разрешимости задачи ЛП
11. Классификация пар двойственных задач ЛП
12. Примеры
7. ЭКОНОМИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ДВОЙСТВЕННОСТИ
1. Классическая содержательная постановка ЛП
2. Экономическая интерпретация двойственной задачи
3. Экономическая интерпретация ограничений двойственной задачи.
4. Экономическая интерпретация теорем двойственности
5. Исследование моделей задач ЛП на чувствительность.
8. ИГРОВОЙ   ПОДХОД  К  ДВОЙСТВЕННОСТИ
1. Основные понятия теории игр.
2. Игра ”Производство-Рынок”
3. Двойственная задача ЛП как задача построения равновесных цен рынка.
9. ТРАНСПОРТНАЯ   ЗАДАЧА
1. Постановка задачи
2. Основные свойство транспортной задачи
3. Двойственная задача
4. Теоремы двойственности
5. Построение опорного плана транспортной задачи
6. Метод   севево-западного угла
7. Пример
8. Метод потенциалов
9. Вычислительная схема метода потенциалов

1. Экономическая и геометрическая интерпретации задач НП
2. Метод множителей Лагранжа
3. Задачи выпуклого программирования
4. Градиентные методы
1. Метод Франка-Вулфа
2. Метод штрафных функций
3. Метод Эрроу-Гурвица