2.2. Симплекс-метод

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

Алгоритмы симплекса-метода позволяют также установить, является ли задача ЛП разрешимой.

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

A₁x₁ + A₂x₂ + … + A_nx_n +A_n+1x_n+1 +…+ A_n+mx_n+m = A₀.

Пусть A₁,…,A_m–множество линейно независимых векторов.

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

A₁x₁^*+ A₂x₂^* + … + A_nx_n^* +A_n+1x_n+1^* +…+ A_n+mx_n+m^* = A₀,       (2...2.1)

определяет базисное решение   x₁^*, x₂^*,…,x_m^*,

Предположим, что это решение допустимо, то есть x₁^*0, x₂^*0,…,x_m^*0. Базис {A₁,…,A_m}образует m–мерное пространство, а потому каждый из векторов A_m+1,…,A_m+n  единственным образом выражается через этот базис. Если A_r не входит в базис, то

A₁x_1r + A₂x_2r + … + A_mx_mr = A_r,                      (2...2.2)

где x_ir– соответствующие коэффициенты (i = 1, 2, ..., m).

Предположим, что хотя бы одна из величин x_ir больше нуля.

Решение уравнения

A₁x₁ + A₂x₂ + … + A_mx_m + A_rx_r = A₀                (2...2.3)

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

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

 .              (2.2.4)

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

A₁(x₁^*–x_rx_1r) + A₂(x₂^*–x_rx_2r) +…+A_m(x_m^*–x_rx_mr)=A₀–x_rA_r.   (2.2.5)

Сравнив уравнения (2.2.5) и (2.2.4), находим связь нового решения ₁,…, _m , x_r со старым базисным решением x^*₁,…,x^*_m:

₁=x₁^*–x_rx_1r, ₂=x₂^*–x_rx_2r,…, _m=x_m^*–x_rx_mr   , x_r.                  (2.2.6)

Решение (2.2.6), во-первых, не будет базисным, так как содержит

m + 1 переменную, а во-вторых,  будет допустимым не для всех значений x_r.

Чтобы новое решение оставалось допустимым, нужно выбрать значение x_r таким, чтобы ни одна из величин _i = x_i^* – x_rx_ir (i=1, 2, ..., m) не стала меньше нуля. Следовательно, максимальное значение переменной x_r определяется соотношением

x_{r max} =  ,                              (2.2.7)

где x_ir > 0.

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

Для этого выбираем значения в соответствии с (2.2.7). Тогда новое базисное решение имеет вид

x₁^* – x_{r max}x_1r;

x₂^* – x_{r max}x_2r;

x_j (опущен)

x_{r max},

а новый базис – (A₁, A₂, …, A_j-1, A_j+1, …, A_m, A_r).

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

Новому ДБР       { x₁^* – x_rx_1r, x₂^* – x_rx_2r, …, x_m^* – x_rx_mr, x_r}

соответствует следующее значение целевой функции

z₁ = с₁(x₁^*–x_rx_1r) + с₂(x₂^*–x_rx_2r) +…+с_rx_r =

= (с₁x₁^*+с₂x₂^*+…+с_mx_m^*)+x_r(с_r–с₁x_1r–…–с_mx_mr)=

=z₀+x_r(с_r–с₁x_1r–…–с_mx_mr),                                           (2.2.8)

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

с_r–с₁x_1r –с₂x_2r – … – с_mx_mr – симплекс-разность для переменной х_r.

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

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

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

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

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

для всех x_ir > 0,

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

а из базиса – вектор A _j;

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

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

Это и есть признак оптимальности текущего базисного решения.

Пример 2.2. Решить симплексом-методом такую задачу:

                                              максимизировать (2x₁+5x₂)

при ограничениях

x₁400, x₂300, x₁+x₂500 .

Расширенная форма задачи имеет вид

Ограничения задачи запишем в виде табл. 2.1.

Первая итерация. 1. Выбрав в качестве начального базиса векторы { A₃, A_4, A₅}, находим первое допустимое базисное решение:

A₃x₃^*+A₄x₄^*+A₅x₅^*=A₀,

откуда x₃^*=400, x₄^*=300, x₅^*=500,

2. Записываем каждый из небазисных векторов A₁, A₂ в виде линейной комбинации базисных {A₃, A₄, A₅}

A₃x₃₁+A₄x₄₁+A₅x₅₁=A₁;

A₃x₃₂+A₄x₄₂+A₅x₅₂=A₂.

Таблица 2.1

А1	A2	A3	А4	А5	а0
1	0	1	0	0	400
0	1	0	1	0	300
1	1	0	0	1	500

Решая эти уравнения, получим

х₃₁=1; x₄₁=0; х₅₁=1; x₃₂=0; х₄₂=1; х₅₂=1.

3. Находим симплекс-разности для небазисных переменных x₁ и x₂:

с₁-с₃х₃₁-с₄х₄₁- с ₅х₅₁= с ₁=2;

с ₂- с ₃х₃₂- с ₄х₄₂- с ₅х₅₂= с ₂=5.

Поскольку с ₂> с ₁, вводим в базис вектор x₂.

4. Определяем, какая переменная выводится из базиса. Для этого находим

х₃= х₃^* - х₂х₃₂=х₃^*;

х₄= х₄^* - х₂х₄₂=300-1х₂;

х₅= х₅^* - х₂х₅₂=500-1х₂;

Итак переменная х₂ вводится в базис со значением x₂^*= 300, переменная x₄ выводится из базисного решения, а вектор A₄— из базиса.

Вторая итерация. 1. Раскладываем каждый из небазисных векторов через базисные {A₂,A₃,A₅}. Базисное решение

x₂^*=300, х₃^*=400, х₅^*=500-300*1=200

Представим каждый из векторов A_1, A₄ ,не вошедших в базис, в виде линейной комбинации A₂,A₃,A₅ .Так как вектор A₄ был выведен из базиса, рассмотрим только вектор A₁.

Уравнение будет иметь вид

A₂х₂₁+A₃х₃₁+A₅х₅₁=A₁,

откуда х₂₁=0; х₃₁=1; х₅₁=1.