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

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

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

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

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

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

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

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

Дата добавления: 2014-01-11