Вопрос 11:Симплексные таблицы. Последовательное улучшение плана. Связь оценок свободных неизвестных с приращением целевой функции.

симплекс-таблица представляет собой расширенную матрицу системы ограничений с некоторыми дополнительными столбцами и строками. Рассмотрим пример симплекс таблицы для следующей задачи: Найти значения переменных x₁...x₅, при которых функция:

Q =

5

x1

+

7

x2

+

2

принимает максимальное значение, при условии следующих ограничений :

2

x1

+

4

x2

+

x3

=

64

(1)

x1

+

2

x2

+

x4

=

70

(2)

-

x2

+

x5

=

18

(3)

x₁, x₂, x₃, x₄, x₅ ≥ 0 Симплекс таблица имеет следующий вид:

БП

x₁

x₂

x₃

x₄

x₅

Решение

Отношение

x₃

2

4

1

0

0

64

64

/

4

=

16

x₄

1

2

0

1

0

70

70

/

2

=

36

x₅

0

-1

0

0

1

18

--

Q

5

7

0

0

0

-2

--

Самая верхняя строка - чисто информационная, в ней указывается назначение столбцов. Столбец "БП" также информационный, каждая клетка этого столбца содержит имя переменной, являющейся базисной в соответствующем уравнении системы ограничений. В нашем примере, в первом уравнении, базисной переменной является переменная X₃, во втором X₄, в третьем X₅. Столбцы X1...X₅ содержат коэффициенты при соответствующих переменных в уравнениях системы ограничений (каждому уравнению соответствует отдельная строка). В столбец "Решение" изначально записываются свободные члены соответствующих уравнений. Они же показывают значения базисных переменных для текущегого решения, отображаемого симплекс-таблицей, на некотором шаге (итерации) решения задачи. Коэффициенты целевой функции отражаются в симплекс-таблице в строке "Q", свободный член, как и в случае с уравнениями системы ограничений, изначально записывается в столбец "Решение". Он же одновременно является значением целевой функции, но записанный с противоположным знаком (это удобно для симплекс-метода). В нашем примере показанная симплекс-таблица соответствует некоторому решению при котором переменные X₃, X₄, X₅ равны соответственно 64, 70, 18 (см. столбец "Решение"), а остальные перемнные равны нулю. Значение целевой функции "Q" при этом равно двум (что несложно проверить подставив значения переменных в выражение для целевой функции). В нашем примере свободный член равен -2 (минус два) т.к. в записи целевой функции он записан вместе с переменными по одну сторону от знака равенства, а свободные члены в уравнениях системы ограничений по другую. Поэтому перед записью в таблицу его необходимо перенести вправо от знака равенства. Строка "Q" в данном примере выделена желтым цветом, это значит, что по ней будет приниматься решение относительно выбора разрешающего столбца (иногда его называют направляющим). Разрешающий столбец соответствует переменной, которая будет введена в базис (в список базисных переменных) на следующей итерации решения задачи. Цель подобной замены базиса - улучшение значения целевой функции. Критерием выбора разрешающего столбца является максимальный положительный коэффициент в строке "Q", при решении задачи на максимум, или минимальный отрицательный, при решении задачи на минимум. Если после очередной итерации в строке не окажется положительных (при максимизации), или отрицательных (при минимизации) коэффициентов, то оптимальное решение достигнуто. В нашем примере разрешающий столбец выбран по коэффициенту 7 (максимальный положительный т.к. задача на максимум), он соответствует переменной X₂, именно она будет введена в базис на следующей итерации. Числа стоящие в направляющем столбце окрашиваются красным цветом. Красным цветом также окрашивается и разрешающая (направляющая) строка, она соответствует переменной которая будет выведена из базиса (списка базисных переменных) на следующей итерации. Для ее определения рассчитывается и заполняется столбец "Отношение". Его элементы представляют собой отношения элементов столбца "Решение" к соответсвующим элементам направляющего столбца (кроме строки "Q"). Выбор разрешающей строки производится по минимальному значению из всех отношений. Важно то, что данные отношения рассчитываются только для положительных элементов направляющего столбца. Если на некоторой итерации в направляющем столбце положительных коэффициентов не окажется, то целевая функция исходной задачи неограничена, задача не имеет решения. В нашем примере направляющая строка выбрана по минимальному отношению 16, она соответствует базисной переменной X₃, именно она будет выведена из базиса на следующей итерации (ее место займет X₂)

Вторая часть вопроса:

Описываемый здесь метод основан на симплексном переходе от одного базиса к другому. Метод разработан для решения задач линейного программирования, записанной в форме (1.1) -(1.3). Для записи ограничений (1.2) используем формулу (1.4).

Считается, что найден базис P₁,P₂,…,P_m, обозначаемый

(P₁,P₂,…,P_m ) = В (3.1) такой, что в разложении

P₀ = ξ₁₀P₁ + ξ₂₀P₂ +…+ ξ_m0P_m (3.2)

Коэффициенты ξ_i0 ≥ 0 ,i=1,…,m.

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

Согласно определению 2 n-мерный вектор

х₀ = (ξ₁₀, ξ₂₀,…,ξ_m0,0,…,0)^t

является опорным планом, соответствующим базису (3.1).

Конечной целью решения задачи линейного программирования является нахождение минимума линейной формы. Поэтому симплексный переход от базиса В к новому базису В’ целесообразно осуществлять так, чтобы для опорного плана x' , соответствующего базису B’ , выполнялось неравенство С^tx₀ ≥ С^tx’. В этом случае говорят, что план x' лучше плана x₀. Улучшать план можно с помощью различных алгоритмов. Один из них и описывается в настоящем параграфе.

Пусть

P_k =ξ_1kP_k+ξ_2kP₂+...+ξ_mkP_m , k=0,1,...,m (3.3)

При k=0 равенство (3.3) совпадает с (3.2). Обозначим

Z_k=ξ_1kC₁+ξ_2kC₂+...+ξ_mkC_m , k=0,1,...,n (3.4)

Заметим, что z₀=C^tx₀ , т.е. z₀, является значением линейной формы C^tx на опорном плане x₀.

Все исходные данные сведем в таблицу, называемую симплексной (см.табл.3.1). В симплексной таблице первые два столбца

Таблица 3.1

Базис В	Сбаз	С0=0	С1	C2...	Cs...	Cm...	Cj...	Ck...	Cn
		B^-1P0	B^-1P1	B^-1P2...	B^-1Ps...	B^-1Pm...	B^-1Pj...	B^-1Pk...	B^-1Pn
P1	C1	ξ10	1	0...	0...	0...	ξ1j...	ξ1k...	ξ1n
P2	C2	ξ20	0	1...	0...	0...	ξ2j...	ξ2k...	ξ2n
...	...	...	...	...	...	...	...	...	...
Ps	Cs	ξs0	0	0...	1...	0...	ξsj...	ξsk...	ξsn
...	...	...	...	...	...	...	...	...	...
Pm	Cm	ξm0	0	0...	0...	1...	ξmj...	ξmk...	ξmn
∆k = zk-ck		z0	0	0...	0...	0...	zj-cj...	zk-ck...	zn-cn

и первые две строки назовем окаймляющими. Остальные элементы составляют основную таблицу. Строкам таблицы приписываются номера от 1 до m+1, столбцам от 1 до n. В столбец окаймления “базис” записываются векторы базиса или их номеры. В столбец С_баз записываются коэффициенты C_i линейной формы C^tx с номерами, соответствующими номерам базисных векторов. В первой окаймляющей строке выписываются все коэффициенты линейной формы, для единообразия дальнейших вычислений в нулевом столбце можно записать C₀=0. В к-ом (к=0,...,n) столбце стоят коэффициенты разложения вектора Р_к по базису В, точнее ξ_sk – коэффициент при векторе Р_к по базису В. Числа ∆_k = z_k-c_k , стоящие в m+1-ой строке, называются оценками, при этом ∆₀=z₀=C_баз B^-1P₀= C^tx₀. Заметим, что z_k по определению (3.4) является скалярным произведением столбца С_баз на столбец B^-1P_к. В связи с этим

∆_k=С^t_баз B^-1P_к-С_к , k=0,1,...,n. (3.5)

Заметим, что если уравнение (1.4) умножить слева на B^-1, то получим уравнение

B^-1P₀ = ξ₁ B^-1P₁ + ξ₂ B^-1P₂ + ξ_n B^-1P_n , равносильное уравнению (1.4). Таким образом, в симплексной таблице 3.1 записана в преображенном виде расширенная матрица системы (1.2).

Теорема 1. Пусть для базиса (3.1) выполняются неравенства ξ_i0 ≥ 0, i=1,...,m и z_k - c_k ≤ 0,k=1,...,n. Тогда опорный план х₀ , соответствующий базису (3.1) оптимален.

Доказательство. Пусть y=(η₁,η₂,...,η_n)^t произвольный план задачи (1.1)-(1.3). Тогда η_к ≥ 0, к=1,...,n и ∑η_кР_к = Р₀ (сумма от к=1 до n). Отсюда Р₀ = ∑∑η_кξ_jkP_k (сумма от j=1 до m, сумма от к=1 до n)в силу (3.3). Сравнивая это равенство с (3.2), в силу единственности разложения вектора Р₀ по базису В находим

ξ_j0 = ∑ η_kξ_jk (сумма от к=1 до n) используя это равенство, а также неравенства z_k ≤ c_k , k=1,...,n и равенство (3.4), находим С^ty = ∑ c_kη_k ≥ ∑z_kη_k (сумма от к=1 до n)= = ∑∑ξ_jkη_kc_j (сумма от j=1 до m, сумма от к=1 до n) = ∑c_jξ_j0 (сумма от j=1 до m) =С^tx₀.

Но это неравенство, в силу произвольности плана y, и означает, что опорный план х₀ оптимален. Теорема доказана.

Итак, если все оценки неположительные, то задача (1.1)-(1.3) решена. Пусть далее базис В таков, что ему соответствует опорный план х₀ и среди оценок ∆_k, k=1,...,n есть положительные. В этом случае могут возникнуть две существенно различные ситуации. Первая из них характеризуется следующей теоремой.

Теорема 2. Пусть для базиса (3.1) выполняется неравенства ξ_i0 ≥ 0 , i=1,…,m. Если для какого-либо j выполняется неравенство Δ_j > 0, но ξ_ij ≤ 0 для всех i=1,…,m, то линейная форма С^tх неограничена снизу.

Доказательство. Вычитая из равенства (3.2) равенство (3.3) при k = j, умноженное на произвольное положительное число θ, получим P₀ = ∑(ξ_i0 - θξ_ij)Pi + θP_j (сумма от i=1 до m). Это равенство показывает, что n – мерный вектор х’ = (ξ₁₀ – θξ_1j,…, ξ_m0- θξ_mj, 0,…, 0, θ,…,0)^t, где θ является j- ой координатой, удовлетворяет условию (1.4). Так как ξ_i0 ≥ 0, ξ_ij ≤ 0, для любого i, то х’ ≥ 0 и, следовательно, х’ является планом задачи (1.1)-(1.3). Тогда из равенства С^tx’= ∑C_i(ξ_i0 - θξ_ij) + θC_j = С^tx₀ - θΔ_j (сумма от i=1 до m), справедливого для любого θ > 0, следует неограниченность линейной формы С^tx снизу. Теорема доказана.

Итак, в ситуации, описанной в теореме 2, решение задачи линейного программирования заканчивается, так как минимум линейной формы С^tx становится известным, он равен -∞.

Пусть таблица 3 такова, что для тех j, для которых Δ_j > 0, выполняется неравенство ξ_ij > 0, хотя бы для одного i. В этом случае делается симплексный переход к новому базису. При этом ставится цель – для опорного плана, соответствующего новому базису, значение линейной формы не должно быть больше, чем при старом плане. Будет показано, что через конечное число таких переходов возникнет одна из ситуаций, описанных теоремами 1или 2.

Итак, опишем процедуру симплексного перехода к новому базису с уменьшением линейной формы С^tx. Пусть исходным является базис (3.1) и пусть новый базис образуют векторы

(P₁,…,P_s-1,P_j,P_s+1,…,P_m) = B’ , j > m. (3.6). Согласно лемме 2 ξ_ij (см. формулу (3.3) при k = j) отличен от нуля. В силу леммы 3 разложение любого вектора P_k по базису (3.6) имеет вид

P_k = ∑(ξ_ik – (ξ_sk/ξ_sj)ξ_ij)P_i + (ξ_sk/ξ_sj)P_j (сумма от i≠s до m), k=0,1,…,n. (3.7)

Эту формулу, впрочем, можно получить непосредственно, если записать равенство (3.3) при k = j, найти из него P_s и найденное для P_s выражение подставить в (3.3).

Тогда новое значение z’_k, являющееся скалярным произведением столбцов С_баз и к-го новой симплексной таблицы, определится равенством

z’_k = ∑(ξ_ik – (ξ_sk/ξ_sj)ξ_ij)C_i + (ξ_sk/ξ_sj)C_j (сумма от i≠s до m), k = 0,1,…,n. (3.8)

Вычитая, наконец, С_к из обеих частей равенства (3.8) и считая С₀=0, получим формулы пересчета для оценок ∆’_k= ∆_k – (ξ_sk/ξ_sj) ∆_j , k=0,1,…,n (3.9)

Формулы (3.9) показывают, что оценки ∆_к пересчитываются по тем же правилам исключения (2.10), по каким пересчитываются и координаты векторов Р_к.

Проведем теперь анализ, который позволит установить правило выбора вводящегося в базис вектора P_j и выводящегося из базиса (3.1) вектора P_s. Для этого обратимся к равенствам (3.7) и (3.9) при k = 0. Обозначим θ_j = ξ_s0/ξ_sj в силу формулы (3.9) при k = 0, новое значение ∆₀ линейной формы С^tх может быть меньше старого значения ∆₀, если θ_j∆_j ≥ 0 (3.10).

В силу формулы (3.7) при k = 0 вектор x’ = (ξ’₁₀, ξ’₂₀,…, ξ’_n0), где

ξ_i0 - θ_jξ_ij , i=1,…,s-1,s+1,…m,

ξ’_io = θ_j , i = j (3.11)

0 в остальных случаях,

удовлетворяет ограничениям (1.4). Чтобы вектор х’ был планом, необходимо, чтобы выполнялись неравенства ξ’_i0 ≥ 0, i=1,…,n.

В частности, чтобы обеспечить неравенство ξ’_i0 = θ_i ≥ 0 в любых задачах, необходимо выбирать ведущий элемент ξ_sj > 0. По тем же причинам из (3.10) следует, что j надо выбирать так, чтобы было Δ_j > 0.

Найдем, наконец, условия, при которых будут неотрицательными ξ’_i0 при i ≠ s. Так как ξ_i0 ≥ 0, θ_j ≥ 0 то неравенства ξ_i0 – θ_jξ_ij ≥ 0 выполняются для тех i, для которых ξ_ij ≤ 0. Пусть I ={i| ξ_ij > 0}. Чтобы выполнялись неравенства ξ_i0 - θ_jξ_ij ≥ 0 для всех i I, должны выполняться неравенства θ_j ≤ ξ_i0/ξ_ij для любого i I. Так как s I и θ_j = ξ_s0/ξ_sj ,то θ_j = min ξ_i0/ξ_ij. Это равенство и определяет правило выбора выводящегося из базиса вектора. Именно в качестве индекса s нужно выбирать тот, для которого достигается минимум отношений ξ_i0/ξ_ij при i I.

В результате такого выбора индексов j и s план x’ с координатами (3.11) будет опорным, так как ненулевым координатам плана x’ соответствует линейно-независимые векторы (3.6).

Полученный результат сформулируем в виде теоремы.

Теорема 3. Пусть для базиса (3.1), которому соответствует опорный план x₀, выполняются неравенства Δ_j > 0 для некоторого j и ξ_ij > 0 хотя бы для одного i. Тогда базису (3.6), где s oопределяется равенством θ_j = ξ_s0/ξ_sj = min ξ_i0/ξ_ij, (i| ξ_ij > 0), (3.13) соответствует опорный план x’, для которого C^tx’ ≤ C^tx₀, при этом С^tx’ < C^tx₀, если ξ_{s0 } 0.

Теоремой 3 завершается формулировка принципов построения нового опорного плана x’ такого, что С^tx’ ≤ C^tx₀. Эти принципы можно реализовать с помощью различных алгоритмов. Следующий алгоритм называется симплексным методом или методом последовательного улучшения плана.

Симплексный метод. Пусть выполнены следующие два условия:

А) выбран базис (3.1) такой, что в разложении (3.2) все ξ_i0 ≥ 0,

Б ) построена соответствующая этому базису симплексная таблица 3.1.

1. Если Δ_j ≤ 0 для всех j=1,…,n, то задача решена и опорный план х₀, соответствующий базису (3.1), является оптимальным. В противном случае переходим к пункту 2.

2. Просматриваются столбцы B^-1P_j для тех j, для которых

Δ_j = z_j – c_j > 0. Если хотя бы в одном из таких столбцов ξ_ij ≤ 0 для всех i=1,…,m, то решение задачи прекращается - линейная форма не ограничена снизу. В противном случае выбирается любое j, для которого Δ_j > 0. Вектор Р_j будет вводиться в базис.

3. Выбирается минимальное из отношений ξ_i0/ξ_ij для тех i, для которых ξ_ij > 0. Пусть этот минимум достигается при i = s. Тогда вектор P_s выводится из базиса. Обозначим ξ_s0/ξ_sj = θ_j.

4. В окаймляющих столбцах "базис" и С_баз таблицы 3.1 вектор P_s и число С_s заменяются, соответственно, на P_j и C_j.

5. Элемент ξ_sj выбирается за ведущий и в таблице 3.1 производится процесс исключения элементов j-го столбца, в том числе и элемента Δ_j, по одному из алгоритмов 1-3 исключений из §2 (см. табл. 2.1 и 2.2). Для вновь полученной симплексной таблицы процесс повторяется с пункта 1.

Замечание. Легко понять, что при решении задачи максимизации С^tх при ограничениях (1.2), (1.3) можно использовать этот же алгоритм с той разницей, что в базис нужно вводить вектор P_j, для которого Δ_j < 0 и останавливать счет, если Δ_j ≥ 0 для всех j=1,…,n. При этом линейная форма окажется неограниченной сверху, если хотя бы для одного j выполняются одновременно неравенства Δ_j < 0, ξ_ij ≤ 0, i=1,…,m.