Симплексный метод решения задачи линейного программирования

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

Для вывода основных соотношений симплексного метода запишем систему уравнений (1.3) в векторной форме

, где и В – векторы.

, , .

Предположим, что известно какое-нибудь базисное решение системы, в котором m значений отличны от нуля

, .

, .

Ненулевые значения удовлетворяют векторному уравнению

. (1.4)

Векторы могут быть приняты в качестве базиса m-мерного пространства, поэтому любой небазисный вектор можно разложить по векторам базиса

. (1.5)

Умножим уравнение (1.5) на произвольную положительную константу и вычтем это уравнение из (1.4).

.

или

. (1.6)

Величина – произвольная, поэтому ее выберем настолько малой, что независимо от знака выражение в скобках будет всегда положительно

, т.к. , ; .

Обозначим , .

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

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

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

.

Допустим, что минимальное значение получается при , т.е.

.

Тогда при данном значение переменной , другие .

Поэтому вместо исходного базисного решения получим новое

(1.7)

На основе нового базисного решения (1.7) уравнение (1.6) будет записано в виде

. (1.8)

Сравнивая полученное уравнение (1.8) с (1.6), получим, что вектор заменен на вектор и новое базисное решение (1.7) удовлетворяет уравнению (1.8).

Таким образом, изложенная процедура позволяет находить при известном базисном решении другое базисное решение, отличающееся от исходного одним базисным вектором.

Как же меняется значение критерия оптимальности при переходе от одного базисного решения к другому? Подставим исходное базисное решение в выражение критерия

.

Число членов под знаком суммы сократилось за счет того, что в исходном базисном решении n членов равно нулю.

Для первого базисного решения значение критерия равно

.

Найдем приращение критерия

.

Величина , если выполняется условие

. (1.9)

Если же , то значение критерия уменьшается при переходе к новому базисному решению.

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