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

Приведено описание симплекс-метода

Симплекс-метод, известный также в нашей литературе под названием метода последовательного улучшения плана, впервые разработал Г.Данциг в 1947 г. Этот метод позволяет переходить от одного допустимого базисного решения к другому, причем так, что значения целевой функции непрерывно возрастают. В результате оптимальное решение находят за конечное число шагов. Алгоритмы симплекса-метода позволяют также установить, является ли задача ЛП разрешимой.

Запишем ограничения задачи ЛП в таком виде:

A1x1 + A2x2 + ... + Anxn +An+1xn+1 +...+ An+mxn+m = A0.

Пусть A1,...,Am – множество линейно независимых векторов. Тогда уравнение

A1x1*+ A2x2* +...+ Anxn* +An+1xn+1* +...+ An+mxn+m* = A0,              (2.2.1)

определяет базисное решение x1*, x2*,.,xm*.

Предположим, что это решение допустимо, то есть x1*³0, x2*³0,...,xm*³0. Базис {A1,.,Am} образует m-мерное пространство, а потому каждый из векторов Am+1,...,Am+n единственным образом выражается через этот базис. Если Ar не входит в базис, то

A1x1r + A2x2r +...+ Amxmr = Ar,              (2...2.2)

где xir – соответствующие коэффициенты (i = 1, 2,...,m). Предположим, что хотя бы одна из величин xir больше нуля. Решение уравнения

A1x1 + A2x2 + . + Amxm + Arxr = A0                (2...2.3)

обозначим как   .

Тогда, очевидно:              (2.2.4)

Умножив уравнение (2.2.2) на xr и вычтя полученное уравнение из уравнения (2.2.1), получим

A1(x1*-xrx1r) + A2(x2*-xrx2r) +...+Am(xm*-xrxmr)=A0 - xrAr.           (2.2.5)

Сравнив уравнения (2.2.5) и (2.2.4), находим связь нового решения 1,...,m, xr со старым базисным решением x*1,...,x*m:

1=x1* - xrx1r,     2=x2* - xrx2r,...,    m=xm* - xrxmr , xr.                              (2.2.6)

Решение (2.2.6), во-первых, не будет базисным, так как содержит m + 1 переменную, а во-вторых, будет допустимым не для всех значений xr. Чтобы новое решение оставалось допустимым, нужно выбрать значение xr таким, чтобы ни одна из величин i = xi* - xrxir (i=1, 2, ...,m) не стала меньше нуля. Следовательно, максимальное значение переменной xr определяется соотношением

xrmax=min { x*i / {x*ir }.              (2.2.7)

где xir > 0.

Чтобы сделать новое допустимое решение базисным, нужно одну переменную xi вывести из базисного решения, а соответствующий вектор из базиса. В этом случае новый базис будет содержать также m векторов. Для этого выбираем значения в соответствии с (2.2.7). Тогда новое базисное решение имеет вид

x1* - xr maxx1r; x2* - xr maxx2r; xj (опущен) xr max, а новый базис - (A1, A2, ., Aj-1, Aj+1,..., Am, Ar).

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

Новому ДБР { x1* - xrx1r, x2* - xrx2r,..., xm* - xrxmr, xr} соответствует следующее значение целевой функции

z1 = с1(x1*-xrx1r) + с2(x2*-xrx2r) +...+сrxr = (с1x1*+с2x2*+...+сmxm*) + xr(сr-с1x1r -...- сmxmr) = z0 + xr(сr-с1x1r -...- сmxmr).       (2.2.8)

где z0 - значение целевой функции для начального ДБР; 

сr-с1x1r - с2x2r -...- сmxmr - симплекс-разность для переменной хr.

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

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

1) находят начальный базис и связанное с ним допустимое базисное решение; 

2) вычисляют симплекс-разность для каждой переменной, не входящей в базисное решение; 

3) вводят в базис наиболее 'выгодную' переменную с максимальной положительной симплексом-разностью; ее значение xrmax определяют из соотношения

для всех xir > 0,

4) выводят из базисного решения переменную xj, соответствующую

а из базиса - вектор Aj;

5) переходят к этапу 2 новой итерации.

Этапы 2) - 4) повторяют до тех пор, пока симплекс-разности для всех переменных, не входящих в базис, не станут отрицательными. Это и есть признак оптимальности текущего базисного решения.

В начало