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

Доказано, что оптимальное решение задачи линейного программи­рования связано с угловыми точками многогранника решений, поэтому возникает мысль о следующем пути решения задачи линейного програм­мирования с любым числом переменных. Найти каким-нибудь способом все угловые точки многогранника планов (а их = , если каждый план определяется системой m-линейно независимых векторов, содержащихся в данной системе из n векторов Ā₁, Ā₂ ,..., Ā_n) и сравнить в них значения целевой функции. Но найти оптимальный план, перебирая все опорные планы задачи трудно, поэтому необходимо иметь схему, по­зволяющую переходить к не худшему опорному плану и иметь признак того, что лучших крайних точек, чем данная крайняя точка нет. В этом и состоит идея наиболее широко применяемого в настоящее время сим­плексного метода (метода последовательного улучшения плана).

Итак, симплексный метод предполагает: умение находить начальный опорный план, наличие признака оптимальности (неоптимальности) опорного плана, умение переходить к нехудшему опорному плану.

3.1. Построение начального опорного плана

1. Пусть задача линейного программирования представлена целевой функцией Z=c₁х₁ +с₂х₂ +...+с_nх_n = с_jх_j и системой ограничений, заданной в каноническом виде

Говорят, что ограничение задачи линейного программирования имеет предпочтительный вид, если в _i ³ 0 и левая часть этого ограничения содержит переменную с коэффициентом 1, а в остальные ограничения – равенства она входит с коэффициентом равным 0.

Пример 7.

Первое и второе ограничения имеют предпочтительный вид, а третье – нет.

Если каждое ограничение – равенство задачи линейного программи­рования имеет предпочтительный вид, то и система ограничений пред­ставлена в предпочтительном виде. В этом случае легко найти ее опорное решение: все свободные переменные приравниваются к нулю, тогда ба­зисные переменные равны свободным членам.

Пример 8.

а) предпочтительными, т. е. базисными переменными являются х₂, х₃, х₄, а свободными – х₁ и х₅ х₁ = 0, х₅ = 0, а х₂ = 10, х₃ = 0, х₄ = 2. Тогда начальный опорный план =(0; 10; 80; 32; 0) – угловая точка (согласно теореме 1).

б) пусть система ограничений имеет вид  в _i; в _i ³ 0    (i = ) в задаче линейного программирования на max (задача об использовании сырья). Сведем задачу к каноническому виду, для этого добавим к левым частям неравенств дополнительные переменные х_{n + i} ³ 0 (i = ), тогда получим систему равенств  в _i; в _i ³ 0 (i = ), которая будет иметь предпочтительный вид и, следовательно, начальный опорный план будет = (0,...0, в₁, в₂,…, в_m) (так как в этой системе все дополнительные переменные будут базисными, а в целевую функцию дополнительные переменные входят с коэффициентом равным 0), то Z = c₁x₁ + c₂x₂ + … c_nx_n + 0×x_n+1 + …0×x_n+m.

в) в задачах линейного программирования на min (задача о составлении ра­циона) система ограничений имеет вид  в _i; в _i ³ 0, (i = ). Если мы сведем эту задачу к каноническому виду, то надо из каждого неравенства (из левой части) вычесть дополнительные переменные х_{n+ i} ³ 0 (i = ). Получим систему  в _i; в _i ³ 0, (i = ), однако теперь система ограничений не имеет предпочтительного вида, так как дополнительные переменные х_{n + i} входят в левую часть с коэффициентами (– 1). В этом случае вводится так называемый искусственный базис: к левым частям ограничений равенств, не имеющих предпочтительного вида, добавляют искусственные переменные w _i.

В целевую функцию переменные w _i вводят с коэффициентом М в случае решения задачи на min и с коэффициентом (– M) для задачи на max, где М – большое положительное число. Полученная задача называ­ется М-задачей, которая соответствует исходной. Она всегда имеет пред­почтительный вид.

Пусть исходная задача линейного программирования имеет вид:

max(min) Z = ,  

причем ни одно из ограничений не имеет предпочтительной переменной. Тогда М-задача запишется так:

                            max (min) = – (+) ,

                   в _i,(i = ),

                     х_j ³ 0, (j = ), w _i ³ 0, (i = ).

Эта система ограничений имеет предпочтительный вид, ее начальный опорный план  = (0,...0, в₁, в₂, …, в_m). Если некоторые из уравнений исходной системы ограничений имеют предпочтительный вид, то в них не следует вводить искусственные переменные. Итак, если в оптимальном плане  = (х₁, x₂,.., x_n, w₁, w₂,.., w_m) М-задачи все искусственные переменные w_I = 0 (i = ), то план = (х₁, x₂,.., х_n) является оптимальным планом исходной задачи. Можно сказать, что если в результате применения симплексного метода к М-задаче получен оптимальный план, в котором все искусственные переменные w_I = 0, то его первые n-компоненты дают оптимальный план исходной задачи. Если же в оптимальном плане М-задачи хотя бы одна из w_i ¹ 0, то исходная задача не имеет допустимых планов, т. е. ее условия не совместны.

Симплексные таблицы.

Признак оптимальности опорного плана

Итак, любую задачу линейного программирования можно предста­вить в предпочтительном виде: max(min) Z = ,

                       x_i + , B_i ³ 0, (i = ),

                      х_j ³ 0, (j = ).

Рассмотрим эту задачу для n = 4, m = 2 (и распространим ее для общего случая): Z = c₁x₁ + c₂x₂ + c₃x₃ + c₄x₄.

  

  

 

Выразим базисные переменные (БП) х₁, х₂ через свободные х₃ и х₄

  x₁ = ,

  x₂ =     и подставим их в целевую функцию

Введем обозначения в общем виде:

,

где = (с₁; с₂; …; с_m) – вектор коэффициентов целевой функции при базисных переменных,  = (B₁; B₂;..; B_m) – вектор свободных членов; =  – вектор коэффициентов при переменных х _j.

С учетом этих равенств целевая функция примет вид:

max(min)Z=  где ; .

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

Таблица 17

БП	СБ	В	х1   х2 … xi … xm xm+1   …    xj … xn
			c1   c2 … ci … cm  cm+1   …    cj … cn
x1 x2 . . . xm	c1 c2 . . . cm	B1 B2 . . . Bm	1     0   …   0 … 0 1, m+1   … 1, j … 1n 0     1  …   0 … 0 2, m+1   … 2, j … 2,n ……………………………………………………………..   0     0 … 0 …  1 m, m+1  … m, j … mn
Z j – c j		ΔO	0 …  0 … 0 … 0  Δm+1          Δ j            Δn

Последнюю строку называют индексной строкой, число  – значение целевой функции для начального опорного плана , т. е. Δ_O = Z() = , числа  – называются оценками свободных переменных.

Теорема.

Пусть исходная задача решается на max. Если для некоторого опорного плана все оценки Δ_j (j = ) не отрицательны (больше или равны 0), то такой план оптимален.

Доказательство: Так как Z = Δ_O и Δ_j ³ 0, то Z достигает max, когда = 0, а это возможно, если х_m+1 = 0, х_m+2 = 0,..., хn = 0, т. е. опорный план (В₁, В₂, …, В_m, 0, …, 0) – оптимален.

Теорема.

Если исходная задача решается на min и для некоторого опорного плана все оценки Δ_j (j = ) не положительны (меньше или равны 0), то такой план оптимален.

Пример 9. Решить задачу линейного программирования.

=>

Система ограничений задачи имеет предпочтительный вид: базисом являются переменные х₂,х₄,х₁. Заносим условие задачи в симплексную таблицу (табл. 18):

Таблица 18

БП	СБ	В	x1	x2	x3	x4	x5
			2	– 1	3	– 2	1
x2	– 1	1,5	0	1	0,5	0	0,5
x4	– 2	2	0	0	1	1	0
x1	2	0,5	1	0	– 0,5	0	0,5
Zj – cj		– 4,5	0	0	– 6,5	0	– 0,5

Заполним индексную строку (Z _j – с _j): ,

Δ_O = – 1 × 1,5 – 2 × 2 + 2 × 0,5 = – 4,5,

Δ₁ = – 1× 0 – 2 × 0 + 2 × 1 – 2 = 0,

Δ₂ = – 1× 1 – 2×0 + 2×0 – (–1) = 0,

Δ₃ = – 1× 0,5 – 2 + 2 × (– 0,5) – 3= – 6,5,

Δ₄ = – 1× 0 – 2×1 + 2×0 – (– 2) = 0,

Δ₅ = – 1× 0,5 – 2 × 0 + 2 × 0,5 – 1 = – 0,5.

Начальный опорный план  = (0,5; 1,5; 0;2; 0), Z () = – 4,5. Так как все оценки индексной строки Δ _j не положительны, а задача на min, то план  – оптимален х* = (0.5: 1.5: 0: 2: 0); Z (х*) = – 4,5.

 

3.3. Переход к нехудшему опорному плану

Пусть решается задача линейного программирования с системой ограничений в предпочтительном виде

 (i = ),                    (5)

ее начальный опорный план  = (В₁, В₂, …, В_m, 0, …, 0). Значение целевой функции Z() =  = Δ_O.

Рассмотрим задачу на mах: если все Δ _j ³ 0, то опорный план опти­мален. Пусть существует j_O, для которого Δj_O < 0. Вектор столбец , для которого Δj_O < 0, называется разрешающим, а соответствующая пе­ременная x_jo – перспективной. Попытаемся, не изменяя нулевых значений свободных переменных х_m+1, х_m+2, …, х_n, кроме x_jo увеличить значение целевой функции Z за счет увеличения переменной x_jo > 0. Однако увеличивать x_jo надо осторожно, так как выбор  влияет на значения х₁,..., х_m, которые должны быть ³ 0. Имеем: х₁ ³ 0, х₂ ³ 0,..., х_m ³ 0, х_m+1 = 0,..., x_jo-1 = 0, x_jo > 0, x_jo+1 = 0,..., x_n = 0 и из (5) имеем

 x _i = B _I –   – (i = ).                                (6)

При значительном увеличении  может случиться, что для некоторого i соответствующее B _I < , значит получим х_i < 0, что недопустимо. В случае, если  (i = ), такого нарушения не произойдет.

Итак, x_jo можно увеличивать до тех пор, пока B _i – x_jo ³ 0, не на­рушая общности, можно считать > 0, тогда  £ . Найдем среди отношений  наименьшее. Пусть оно называется наименьшим симплексным отношением и обозначается Q.

x_jo = min  =  = Q,

(если это условие выполняется при нескольких i, то в качестве i _O можно выбрать любое) Cтроку  называют разрешающей, элемент  – разрешающим. Переменная , присутствующая в базисе, является неперспективной и ее выводят из базиса:

x_m+1 = 0, …, = 0, = Q,

 = 0, …, x_n = 0, а из равенства (6) находим: x₁ = B₁ – Q, …,

= – Q,  = 0, = – Q, …,

x_m = Q.

Новый базис будет состоять из переменных х₁, , , ,..., x_m, а соответствующий ему опорный план примет вид, X₁ = (B₁ – Q; B₂ – Q; …; – Q; 0; – Q; …; Q; 0; …; Q; 0; …; 0).

В результате преобразований получен новый опорный план , в котором переменная  заменена на , причем Z(X₁) = Δ₀ – Δ_j0Q = Z(X₀) – Δ_j0Q, но Δ_j0 < 0, поэтому Z(X₁) ³ Z(X₀), то есть новый план  не хуже начального .

Практика показывает, что в случае решения задачи на max число шагов уменьшается, если разрешающий столбец выбрать по правилу max (Δ_j £ 0), т. е. в базис вводить переменную, которой соответствует max по абсолютной величине оценки.

В случае задачи на min разрешающий столбец нужно выбирать по правилу mах Δ_j (Δ_j > 0).

Далее процесс повторяется. Проверяем, является ли план  оптимальным, если да, то задача решена. Если нет, то перехо­дим к нехудшему опорному плану  и т. д.

Шаг симплексного метода, позволяющий перейти от одного опорного плана к другому нехудшему, называется итерацией.

Симплексные преобразования нового базиса выполняются по правилу:

1. Элементы строки i _O новой таблицы равны соответствующим элементам разрешающей строки старой таблицы, деленным на разре­шающий элемент: , , (j = ).

2. Элементы разрешающего столбца j₀ новой таблицы равны 0, за исключением = 1.

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

4. По 3 пункту вычисляются и элементы индексной строки.

Для контроля вычислений они могут быть рассчитаны по формулам ,

Пример 10. Найти max Z = 14х₁ – 5х₂ + 2х₃ – х₄ + 8х₅, если

Решение.

Так как задача имеет предпочтительный вид, то занесем ее условия в симплексную табл. 19 (итерация 0).

Таблица 19

N итерации	БП	СБ	В	x1	x2	x3	x4	x5	Симплексные отношения
				14	– 5	2	– 1	8
0	x2	– 5	5	[1]	1	0	0	– 1
	х3	2	41	5	0	1	0	3
	х4	– 1	15	– 5	0	0	1	4
	zj – cj		42	[– 4]	0	0	0	– 1
1	х1	14	5	1	1	0	0	– 1
	х3	2	16	0	– 5	1	0	[8]
	х4	– 1	40	0	5	0	1	– 1
	zj – cj		62	0	4	0	0	[– 5]
2	х1	14	7	1	3/8	1/8	0	0
	Х5	8	2	0	– 5/8	1/8	0	1
	х4	– 1	42	0	35/8	1/8	1	0
	zj – cj		72	0	7/8	5/8	0	0

0 итерация: исходная задача на max, поэтому начальный опорный план . Он неоптимальный, так как Δ₁ < 0, Δ₅ < 0.

                           

1 итерация:

1) выбираем разрешающий элемент из условия: max {|Δ₁|, |Δ₅|} = m a x (4; 1) = 4 – это соответствует 1 столбцу, поэтому его выбираем за разрешающий то есть X₁ будем вводить в базис. Для определения разрешающей строки находим минимальное симплексное отношение:

= =

итак, 1 – строка разрешающая =>элемент а₁₁ = 1 – разрешающий;

2) переменную х₂ выведем из базиса, а х₁ введем в базис;

3) разрешающую строку делим на разрешающий элемент;

4) элементы разрешающего столбца заполняем нулями;

5) остальные элементы пересчитываем по правилу прямоугольника и делим на разрешающий элемент.

Делаем контрольные проверки:

14 – 5 + 2×16 – 1× 40 = 62; 14 – 10 – 5 + 5 = 4;

14 + 0 + 0 – 14 = 0;      0 + 2 + 0 – 2 = 0;

0 + 0 – 1 + 1 = 0;      – 14 + 16 + 1 – 8 = – 5 < 0.

Так как существует отрицательная оценка ∆₅ = – 5, план  = (5; 0; 16; 40; 0) не оптимальный, Z(x₁) = 62 > Z () = 42.

2 итерация:

1) разрешающий столбец 5, переменную. х₅,будем вводить в базис.

2) определяем разрешающую строку: min симплексное отношение  =  = 2 соответствует 2-ой строке, значит переменную х₃ выводим из базиса. Разрешающий элемент а₂₅ = 8;

3) разрешающую строку делим на 8;

4) в разрешающем столбце проставляем нули;

5) остальные элементы пересчитываем;

6) делаем контрольные проверки, так же как и в итерации 1, так как все D_j ³ 0, опорный план  – оптимален

Ответ:  = (7; 0; 0; 42; 2), Z() = 72.

Пример 11. Решить М-задачу линейного программирования:

Найти: min Z = 3x₁ + 2х₂ + 3х₃, если

Решение:

Сведем задачу к каноническому виду и введем искусственные переменные  и :

Занесем условие М-задачи в симплексную таблицу (индексную строку записываем в две строки: в первой – слагаемые без М, во второй – слагаемые с М) (табл. 20).

Таблица 20

№		БП	СБ		В	х1	х2	х3	х4	х5	х6	w1	w2	Q
						3	2	3	0	0	0	M	M
0		х4 w1 w2	0 М М		2 8 1	2 3 0	1 [8] 0	1 2 1	1 0 0	0 – 1 0	0 0 – 1	0 1 0	0 0 1	2/1 = 2 8/8 = [1]
					0	– 3	– 2	– 3	0	0	0	0	0
					9M	3M	[8M]	3M	0	– M	– M	0	0
1	х4 х2 w2			0 2 М	1 1 1	13/8 3/8 0	0 1 0	3/4 1/4 [1]	1 0 0	1/8 – 1/8 0	0 0 – 1	– – –	0 0 1	1/ 1/ 1/1=[1]
					2	– 9/4	0	– 7/2	0	– 1/4	0	–	0
					М	0	0	[M]	0	0	-М	–	0

Окончание табл. 20

2	х4 х2 х3	0 2 3	1/4 3/4 1	13/8 3/8 0	0 1 0	0 0 1	1 0 0	1/8 – 1/8 0	3/4 1/4 – 1	– – –	– – –
			9/2	– 9/4	0	0	0	– 1/4	– 5/2

Примечание: по мере вывода из базиса искусственных переменных соответствующие им столбцы можно опускать.

 

Так как все D_j ≤ 0, то план оптимален,

Ответ:  = (0; 3/4; 1; 1/4; 0; 0), Z() = 9/2.

Замечания:

1. Если в индексной строке последней симплексной таблицы, содержащей оптимальный план, имеется хотя бы одна нулевая оценка, соответствующая свободной переменной, то задача линейного программирования имеет бесконечное множество оптимальных планов.

2. Если в индексной строке симплексной таблицы задачи линейного программирования на max содержится отрицательная оценка D_j < 0, а в соответствующем столбце переменной х_j. нет ни одного положительного элемента, то целевая функция на множестве допустимых планов задачи не ограничена сверху.

Если же задача линейного программирования на min и в индексной строке содержится положительная оценка D_j > 0, а в столбце переменной х_j нет ни одного положительного элемента, то на множестве допустимых планов целевая функция не ограничена снизу.

С экономической точки зрения неограниченность целевой функции задачи линейного програм­мирования говорит только об одном; разработанная модель недоста­точно точна (бессмысленно говорить о бесконечной прибыли). Типичными ошибками, приводящими к построению моделей такого рода, являются:

а) неполный учет ограничений, которые являются существенными в данной задаче;

б) небрежные оценки параметров, которые участвуют в ограничениях.

 

Задания для самостоятельной работы

Задание 1. Для изготовления двух видов продукции P₁ и P₂ используют три вида сырья (S₁, S₂, S₃).

На изготовление единицы продукции P₁ используют сырье      S₁ – a₁ (ед.), S₂ – a₂ (ед.), S₃ - a₃ (ед.). На изготовление единицы продукции P₂ используют сырье S₁ – b₁ (ед.), S₂ – b₂ (ед.), S₃ – b₃ (ед.). Запасы сырья S₁ составляют не более чем k₁, сырья S₂ – не более чем k₂, сырья S₃ – не более чем k₃.

Прибыль от единицы продукции P₁ составляет a руб., от P₂ составляет b руб.

Необходимо составить такой план выпуска продукции, чтобы при ее реализации получить максимальную прибыль.

Данные для выполнения задания соответствующего варианта представлены в табл. 21.

Таблица 21

Вар.	A1	a2	a3	b1	b2	b3	k1	k2	k3	a	b
1	2	3	4	2	3	3	305	676	400	5	6
2	9	7	4	5	8	16	143	122	132	3	2
3	2	7	5	3	3	6	576	344	570	4	7
4	6	7	2	3	5	4	421	567	321	5	7
5	2	6	3	10	3	5	900	540	700	4	5
6	2	4	9	4	6	2	720	300	422	3	2
7	4	5	6	2	7	9	279	756	674	6	2
8	3	7	9	2	9	3	279	392	549	4	7
9	2	4	5	6	7	8	320	440	550	3	4
10	5	4	9	2	1	4	422	516	312	5	7
11	3	4	12	9	8	2	550	600	472	2	8
12	2	3	6	7	4	8	330	410	520	3	2
13	5	4	9	2	3	4	212	512	400	4	5
14	6	4	2	6	7	2	715	472	128	7	8
15	7	2	3	2	4	5	572	244	560	2	3
16	2	3	4	2	4	5	672	567	322	3	4
17	2	4	7	2	3	3	572	322	496	3	7
18	2	3	7	5	6	8	219	300	420	5	6
19	4	2	1	8	7	2	500	617	650	4	4
20	3	4	6	2	3	5	200	215	400	6	2
21	2	3	2	3	6	8	428	672	672	3	8
22	4	3	3	3	4	5	440	393	450	6	5
23	4	3	2	4	3	4	480	144	546	2	4
24	2	4	2	2	5	6	520	670	720	5	4

Окончание табл. 21

25	3	4	2	4	5	4	672	344	520	3	2
26	2	3	2	4	6	5	505	212	470	4	3
27	4	5	4	3	4	3	320	318	415	4	5
28	3	3	4	2	2	6	550	312	202	4	3
29	8	6	3	2	3	2	340	680	300	3	4
30	6	4	3	2	3	4	600	520	700	4	7

Заданеи 2. Задана каноническая модель задачи линейного программирования.

Z = CX, AX = A₀, X ³ 0, A = (a_ij)_{3 х 5}.

Требуется найти max Z М- методом.

1.

 

2.

 

3.

 

4.

 

5.

 

6.

 

7.

 

8.

 

9.

 

10.

 

11.

 

  12.

 

13.

 

14.

 

15.

 

16.

 

17.

 

18.

 

19.

 

20.

 

21.

 

22.  

23.

 

24.

 

25.

 

26.

 

27.

 

28.  

 

29.

 

30.