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

 

В общем виде схема решения задач линейного программирования (ЛП) заключается в последовательном переборе всех допустимых решений и выборе «наилучшего», т.е. оптимального решения с точки зрения целевой функции. Однако, если число допустимых решений велико, то такая задача становится труднореализуемой. Суть симплекс-метода заключается в целенаправленном переборе допустимых решений, при котором целевая функция «улучшается», или, по крайней мере, «не ухудшается» на каждом последующем шаге решения (итерации).

Рассмотрим следующую ЗЛП в канонической форме:

,

, , (5.15)

.

Любые m переменных системы ограничений ЗЛП (5.15), состоящей из m линейно независимых уравнений с n переменными (m<n), называются основными (или базисными), если определитель матрицы коэффициентов при них отличен от нуля. Тогда остальные n–m переменных называются неосновными (или свободными).

Базисным называют решение ЗЛП, при котором все свободные переменные равны нулю. Допустимым базисным решением (опорным планом) называют базисное решение, удовлетворяющее условию неотрицательности, т.е. .

Опорный план называют невырожденным, если он содержит ровно m положительных компонент, в противном случае, он является вырожденным.

Алгоритм симплекс-метода можно представить в виде следующей схемы:

 

Рис. 5.7

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

Таким образом, алгоритм симплекс-метода можно представить в виде следующих этапов: