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