Реферат: Симлекс-метод

Тогда уравнение

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 определяется соотношением

xr max = , (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 это практически невозможно. Поэтому для перехода от текущего решения к новому допустимому базисному решению, которому отвечает большее значение целевой функции, используют соответствующий критерий (симплекс-разность).