08. Симплекс-метод решения ЗЛП

Особенностью задач ЛП является то, что целевая функция достигает экстремума на границе области допустимых решений (ОДР).

Допустимый план, принадлежащий границе ОДР, называется Опорным планом.

Алгоритм симплекс-метода

1 Находим какой-либо начальный опорный план .

2 Проверяем его на оптимальность. Если план оптимален, то задача решена, иначе переходим к пункту 3.

3 По правилам преобразования таблицы Жордана переходим к нехудшему опорному плану. Переходим к пункту 2.

С геометрической точки зрения, перебор опорных планов можно толковать как переход по ребрам из одной вершины многогранника планов (области допустимых решений) в другую, по направлению к вершине , в которой целевая функция достигает экстремального значения.

Геометрическая интерпретация в случае двух переменных

< Предыдущая		Следующая >