Симплекс-метод. Вырожденные задачи, проблема зацикливания симплекс-метода. Различные способы выбора опорных индексов. Скелет политопа и его диаметр, связь с числом шагов симплекс-метода. Гипотеза Гирша. Двойственная линейная программа для задачи в стандартной форме. Слабая двойственность и ее следствия. Лемма Фаркаша. Сильная двойственность для задачи в стандартной форме. Построение двойственной программы для задачи в общей форме. Двойственность для задачи о максимальном двудольном паросочетании, вершинные покрытия.