В общем виде схема решения задач линейного программирования (ЛП) заключается в последовательном переборе всех допустимых решений и выборе «наилучшего», т.е. оптимального решения с точки зрения целевой функции. Однако, если число допустимых решений велико, то такая задача становится труднореализуемой. Суть симплекс-метода заключается в целенаправленном переборе допустимых решений, при котором целевая функция «улучшается», или, по крайней мере, «не ухудшается» на каждом последующем шаге решения (итерации).
Рассмотрим следующую ЗЛП в канонической форме:
,
, , (5.15)
.
Любые m переменных системы ограничений ЗЛП (5.15), состоящей из m линейно независимых уравнений с n переменными (m < n), называются основными (или базисными), если определитель матрицы коэффициентов при них отличен от нуля. Тогда остальные n – m переменных называются неосновными (или свободными).
Базисным называют решение ЗЛП, при котором все свободные переменные равны нулю. Допустимым базисным решением (опорным планом) называют базисное решение, удовлетворяющее условию неотрицательности, т.е. .
|
|
Опорный план называют невырожденным, если он содержит ровно m положительных компонент, в противном случае, он является вырожденным.
Алгоритм симплекс-метода можно представить в виде следующей схемы:
Рис. 5.7
. Алгоритм симплекс-метода
Таким образом, алгоритм симплекс-метода можно представить в виде следующих этапов: