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

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

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

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

A ₁ x ₁ + A ₂ x ₂ + … + A _nx_n + A _n ₊₁ x_n ₊₁+…+ A _n _{+ m} x_n _{+ m} = A ₀.

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

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

A ₁ x ₁^*+ A ₂ x ₂^* + … + A _nx_n ^* + A _n ₊₁ x_n ₊₁^* +…+ A _n _{+ m} x_n _{+ m}^* = A ₀, (2...2.1)

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

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

A ₁ x _{1 r} + A ₂ x _{2 r} + … + 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 _{1 r}) + A ₂(x ₂^*– x_rx _2r) +…+ A _m (x_m ^*– x_rx_mr)= A ₀– x_r A _r. (2.2.5)

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

₁= x ₁^*– x_rx _{1 r}, ₂= x ₂^*– x_rx _{2 r},…,_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 _{1 r};

x ₂^* – x_r _max x _{2 r};

x_j (опущен)

x_r _max,

а новый базис – (A ₁, A ₂, …, A _j _-1, A _j ₊₁, …, A _m, A _r).

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

Новому ДБР { x ₁^* – x_rx _{1 r}, x ₂^* – x_rx _{2 r}, …, x_m ^* – x_rx_mr, x_r }

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

z ₁ = с ₁(x ₁^*– x_rx _{1 r}) + с ₂(x ₂^*– x_rx _2r) +…+ с_rx_r =

= (с ₁ x ₁^*+ с ₂ x ₂^*+…+ с_mx_m ^*)+ x_r (с_r – с ₁ x _{1 r}–…– с_mx_mr)=

= z ₀+ x_r (с_r – с ₁ x _{1 r}–…– с_mx_mr), (2.2.8)

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

с_r – с ₁ x _{1 r}– с ₂ x _{2 r}– … – с_mx_mr – симплекс-разность для переменной х_r.

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

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

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

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

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

для всех x_ir > 0,

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

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

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

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

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

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

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

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

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

А₁	A₂	A₃	А₄	А₅	а₀

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

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

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

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

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

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

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

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

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

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

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

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

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

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