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

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

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

,

, , (5.15)

.

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

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

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

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

Рис. 5.7

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

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

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