Е.В. Буйная Симплексный метод решения оптимизационных задач

11

2 этап. Приведение задачи к каноническому виду

В соответствии с требованиями, которые были описаны выше, нам необходимо представить ограничения (4.1)-(4.3) в виде равенств. Для этого введем ослабляющие переменные со знаком (+), так как в ограничениях знак (≤ ), и для простоты последующей работы приведем подобные члены в целевой функции. Тогда задача примет вид:

Максимизировать

L ( x ) = 4 ,6 X 1 + 2 X 2 − 2 X 3 + 5 X 4

при ограничениях
0,5X1 + 0,1X 2 +	0,2X3	+	X5	=	10
0,2X1		+ 0,5X 4	+	X 6 =	30
0,3X 2 +	0,2X3 +	0,2X 4		+ X 7 =	20
X1, X 2 , X3, X 4 , X5 , X6 , X 7 ≥ 0

Таким образом, получена задача с 7 неизвестными и 10 ограничениями, допускающая решение стандартным симплекс-методом.

3 этап. Выбор начального опорного плана

Для простоты выбора базисных векторов и начального плана представим нашу исходную задачу в матричной форме.

С = {4,6, 2, -2, 5, 0, 0, 0} – вектор коэффициентов при переменных задачи в целевой функции.

В = {10, 30, 20} - вектор значений правых частей ограничений за-

дачи.

А =	0,5	0,1	0,2	0	1	0	0
	0,2	0	0	0,5
					0	1	0
	0	0,3	0,2	0,2
					0	0	1

- матрица коэффициентов при переменных в ограничениях задачи.

Как мы видим, в матрице А присутствует единичная подматрица, которая соответствует векторам А5, А6, А7, следовательно, начальный опорный план будет выглядеть так: Х0 ={0, 0, 0, 0, 10, 30, 20}.

12

4 этап. Решение задачи симплекс-методом

Строим начальную симплексную таблицу и проверяем начальный опорный план Х0 на оптимальность. Начальный базис Б0=(А5, А6, А7)

C	Базис	План	4,6	2	-2	5	0	0	0
баз	плана	X0	A1	A2	А3	A4	A5	А6	A7
0	A5	10	1/2	1/10	1/5	0	1	0	0
0	A6	30	1/5	0	0	1/2	0	1	0
0	A7	20	0	3/10	1/5	1/5	0	0	1
	Z k	0	0	0	0	0	0	0	0
	∆ k		-4,6	-2	2	-5	0	0	0

Из таблицы видно, что начальный опорный план не оптимален (для нашей задачи на максимум обнаруживаются отрицательные ∆ k и к тому же имеются значения Zjk >0). Следовательно, можно найти более хороший план. Для этого определяем вектор, вводимый в базис, и вектор, выводимый из базиса.

Так как при переходе к новому опорному плану значение целевой функции изменится и будет равно L { X(Θ ) } = L(X0 ) -Θ ∆ k , то очевидно желание вводить в базис вектор, для которого ∆ k<0 и величина Θ ∆ k наибольшая (последнее необязательно, но часто ускоряет достижение поставленной цели). Напомним, что

Θ = m i n	X 0j
		.
Z jk > 0	Z jk

В нашем случае возможны три выбора:

∆ 1=-4,6.

=

10

30

; −

=

20 .

Θ

min

1 / 2

;

1 / 5

∆ 2=-2.

=

10

20

= 200

Θ

min

; - ;

1 / 10

3 / 10

3 .

∆ 4=-5.

=

30

20

=

60 .

Θ

min

- ;

1 / 2

;

1 / 5

θ ∆ 1=-92.

θ ∆ 2~-133.

θ ∆ 3=-300.

Разумно ввести в базис A4 вместо A6 (выражаем X4 из второго уравнения и исключаем из остальных).

13

Новая симплексная таблица для Б1=(А5, А4, А7) будет выглядеть следующим образом:

C	Базис	План	4,6	2	-2	5	0	0	0
баз	плана	X1	A1	A2	А3	A4	A5	А6	A7
0	A5	10	1/2	1/10	1/5	0	1	0	0
5	A4	60	2/5	0	0	1	0	2	0
0	A7	8	-2/25	3/10	1/5	0	0	-2/5	1
	Z k	300	2	0	0	5	0	10	0
	∆ k		-2,6	-2	2	0	0	10	0

Полученный опорный план не оптимален, следовательно, необхо-

димо его улучшить. Снова рассчитываем θ

и θ ∆

k.

∆ 1=-2,6.

=

10

60

; −

=

20 .

θ ∆

1=-52.

Θ

min

1

/ 2

;

2 / 5

θ ∆

∆ 2=-2.

=

10

8

=

80

2~-53.

Θ

min

; - ;

1

/ 10

3 / 10

3 .

В результате в базис войдут векторы: Б2=(А5, А4, А2). Строим новую симплексную таблицу.

C		Базис	План	4,6	2	-2	5	0	0	0
баз		плана	X2	A1	A2	А3	A4	A5	А6	A7
0		A5	22/3	79/150	0	2/15	0	1	2/15	-1/3
5		A4	60	2/5	0	0	1	0	2	0
2		A2	80/3	-4/15	1	2/3	0	0	-4/3	10/3
	Z k		1060/3	22/15	2	4/3	5	0	22/3	20/3
	∆ k			-47/15	0	10/3	0	0	22/3	20/3

Очевидно, что найденный опорный план не оптимален, следовательно, необходимо его улучшить за счет ввода в базис вектора A1.

	Здесь Θ	=		22 / 3		;	60		=	1100	и из базиса выводится A5. Строим
			min
				79 / 150			2 / 5			79

новую симплексную таблицу.

14

C		Базис	План	4,6	2	-2	5	0	0	0
баз		плана	X3	A1	A2	А3	A4	A5	А6	A7
4,6		A1	1100/79	1	0	20/79	0	150/79	20/79	-50/79
5		A4	4300/79	0	0	-8/79	1	-60/79	150/79	20/79
2		A2	2400/79	0	1	58/79	0	40/79	-100/79	250/79
	Z	k	31360/79	4,6	2	168/79	5	470/79	642/79	370/79
	∆ k			0	0	326/79	0	470/79	642/79	370/79

Из полученной таблицы видно, что найденный опорный план оптимален для данной задачи (все ∆ k ≥ 0), т.е.

Хопт=(1100/79; 2400/79; 0; 4300/79) и Lmax = 31360/79.

Ответ для нашей задачи будет выглядеть следующим образом: для того, чтобы прибыль от производства и реализации продукции трех видов была максимально возможной при данных условиях, необходимо закупить сырье 1-го вида в объеме - ~ 13,92 единицы; сырье 2-го вида - ~ 30,38 единицы; сырье 3-го вида не закупать вовсе; сырье 4-го вида - ~ 54,43 единицы. В результате подобной политики мы получим прибыль в размере ~396,96 у.е.

Замечание. Как мы уже говорили неоднократно, при переходе к новому опорному плану значение целевой функции изменяется на величину Θ ∆ k . Следовательно, получив оптимальный план и обнаружив

существование ∆ k=0, не соответствующего базисным векторам, можно сделать вывод, что найденный оптимальный план не единст-

венный (можно перейти к другому плану с тем же значением целевой функции).

Пример 2.

Рассмотрим следующую ситуацию, с которой вы сталкиваетесь каждый день. Предположим, что вы собрались в магазин канцелярских товаров. Ваша задача сделать как можно больше покупок при условии, что вы покупаете только 3 разновидности товара, а именно ручки, карандаши и блокноты (если рассматривать весь ассортимент товара, размерность задачи значительно увеличится, при наличии достаточного количества свободного времени можете попытаться ее решить). В кармане у вас 50 у.е. и, кроме всего прочего, вам необходимо купить хотя

15

бы 3 ручки и 2 блокнота. Вполне закономерно, что вам известна цена товаров: 10 - ручка, 5 – карандаш и 20 у.е. – блокнот.

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

Решение:

Если обозначить за Х1 – количество приобретаемых в магазине ручек, за Х2 – карандашей, а за Х3 – блокнотов, то исходную задачу можно представить в следующем виде:

Максимизировать

L(X)=X1+X2+X3

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

10 X1+5 X2+20 X3≤ 50,

X1≥ 3,

X3≥ 2,

X1, X2, X3≥ 0.

После приведения к каноническому виду задача примет вид:

максимизировать

L(X)=X1+X2+X3

при ограничениях
10 X1 + 5X2 + 20 X3 + X4		= 50
X1	− X5	=	3
X3	−	X6 =	2

X1,X2 ,X3 ,X4 ,X5 ,X6 ≥ 0

При определении начального опорного плана сталкиваемся с отсутствием единичной подматрицы и, следовательно, вводим искусст-

венные переменные и переходим к М-задаче (M→

):

16

максимизировать

L(X)=X1+X2+X3-M X7-M X8

при ограничениях
10 X1 + 5X 2 + 20 X 3 + X 4			= 50
X1	− X 5	+ X7	=	3
X 3	−	X6	+ X 8 =	2

X1 , X 2 , X 3 , X 4 , X 5 , X6 , X7 , X 8 ≥ 0

Отыскав таким образом единичный начальный базис Б0=(А4, А7, А8), переходим к построению симплексных таблиц.

C		Базис	План	1	1	1	0	0	0	-М	-М
баз		плана	X0	A1	A2	А3	A4	A5	А6	А7	A8
0		A4	50	10	5	20	1	0	0	0	0
-М		A7	3	1	0	0	0	-1	0	1	0
-М		A8	2	0	0	1	0	0	-1	0	1
	Z k		-5М	-М 0		-М	0	М М -М -М
	∆ k			-М-1 -1 -М-1 0				М М 0			0

Если принять во внимание, что М – это большое положительное число, то из данной таблицы видно, что опорный план не оптимален (не все ∆ k>0 и хотя бы одно из значений Zjk >0).

Рассчитываем

∆ 1=-M-1.

=

50

;

3

;

−

=

3 .

θ ∆

1=-3M-3.

Θ

min

10

1

θ ∆

∆ 2=-1.

=

50

=

10 .

2~-10.

Θ

min

5

; - ; -

θ ∆

∆ 3=-M-1.

=

50

;− ;

2

=

2 .

3=-2M-2.

Θ

min

20

1

Вводя в базис А1 вместо А7, получаем новую симплексную табли-

цу.

										17
		C	Базис			План			1	1	1		0	0	0		-М	-М
		баз	плана				X1
									A1	A2		А3	A4 A5		А6		А7	A8
	0			A4			20		0	5		20	1	10	0		-10	0
	1			A1			3		1	0		0	0	-1	0		1	0
		-М		A8			2		0	0	1		0	0	-1		0	1
			Z k			-2М+3			1	0		-М 0 -1			М 1			-М
									0	-1 -М-1 0 -1 М 1+М 0
			∆ k
		Очевидно, что ввод в базис вектора А3 предпочтительнее.
C		Ба-		План		1		1		1	0			0		0		-М	-М
баз		зис		X1		A1		A2		А3		A4		A5		А6		А7	A8
1		A3		1		0		1/4		1	1/20			1/2		0		-1/2	0
1		A1		3		1		0		0	0			-1		0		1	0
-М		A8		1		0		-1/4		0	-1/20			-1/2		-1		1/2	1
	Z	k		-М+4		1	1/4М+1/4			1	1/20М+1/20 1/2М+1/2					М	-1/2М-1/2		-М
	∆ k					0	1/4М-3/4			0	1/20М+1/20			1/2М+1/2		М	1/2М-1/2		0

Из таблицы видно, что данный опорный план оптимален. Однако

в базисе находится искусственная переменная и она не равна нулю, от-

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

занном количестве денег в кармане вам необходимо «умерить свой аппетит».

18

5. Варианты заданий для самостоятельной работы

Решить задачу классическим симплекс-методом. Объяснить полу-

ченные результаты.
1. Минимизировать	2. Максимизировать
F(x)=-2x1+3x2-6x3-x4	F(x)=4x1-3x2+x3
при условиях	при условиях
2x1+ x2-2x3+ x4=24	x1+3x2+2x3 ≤ 5
x1+2x2+4x3 ≤ 22	5x1-x3≥ 10
x1- x2+2x3≥ 10	-5≤ x1≤ 2
x1, x2, x3, x4≥ 0	x2, x3≥ 0
3. Минимизировать	4. Максимизировать
F(x)=2x1-x2-x4	F(x)=4x1-3x2+x3
при условиях	при условиях
x1-2x2+x3=10	x1+3x2+2x3≤ 5
-2x1-x2-2x3≥ 18	5x1-x3≥ 10
3x1+2x2+x4≥ 36	-5≤ x1≤ 2
x1, x2, x3, x4≥ 0	x2, x3≥ 0
5. Максимизировать	6. Максимизировать
F(x)=x1+x2-4(x3+x4)	F(x)=3x1-(x2+x3)+2x4
при условиях	при условиях
5≤ x1+x2≤ 20	x1+x2+x4≤ 12
2x1-3x2+4x4≤ 10	2(x2+x4) ≥ 0
x3≥ 3	3x2-5x3+x4≥ 2
x3, x2, x4≥ 0	x3≤ 5
7. Минимизировать	x2, x4≥ 0
	8. Максимизировать
F(x)=10x1+2x2-6x3	F(x)=3x1+5x2+3x3
при условиях	при условиях
x1+x2+x3≤ 30	x1+2x2+2x3≤ 16
4x2-2x3≥ 2	2x1+x2+x3≤ 21
5x1+x3≤ 0	3x1+2x2+x3≤ 15
x3≤ 0	x1, x2, x3≥ 0
x1, x2≥ 0

	19
9. Максимизировать		10. Минимизировать
F(x)=-x1+3x2+3x3		F(x)=2x1+3x2-x3
при условиях		при условиях
x1 - x2 + x3 ≥ 1		x1 + 2x2 – 10 ≥ 0
x1 - x2 ≤ -2		2x1 + x2 + x3 - 10 ≥ 0
x1, x2, x3≥ 0		x2 + x3 - 4 ≤ 0
11. Максимизировать		x1, x2 ≥ 0
		12. Минимизировать
F(x)=9x1+10x2+16x3		F(x)=x1+x2-4x3-4x4
при условиях		при условиях
18x1+15x2+12x3+ x4=360		5≤ x1+x2≤ 20
6x1+4x2+8x3+x5=192		2x1-3x2+4x4≤ 10
5x1+3x2+3x3≤ 180		x3≥ 3
x1, x2, x3, x4, x5≥ 0		x3, x2, x4≥ 0
13. Минимизировать		14. Максимизировать
F(x)=-4x1 + 4x2 + 12x3		F(x)=2x1 - 3x2+6x3 - x4
при условиях		при условиях
X1 - x2 + x3 + 1 ≤ 0		2x1+ x2 - 2x3≤ 24
2x1 + x2 - 2x3 + 1 ≤ 0		x1+2x2 + 4x3≤ 22
x1, x2, x3 ≥ 0		x1 - x2+2x3 - x4=10
15. Максимизировать		x1, x2, x3, x4 ≥ 0
		16. Минимизировать
F(x)=5x1 + 3x2+2x3 - 5x4 -10 x5		F(x)=5x1 + x2 + 5x3
при условиях		при условиях
3x4+ 10x5 ≥	50	4x1 - 10x2 + 4x3 ≥ 100
x1 + x2 + x3≤	100	3x2 + 2x3 = 10
x1 – x5 ≤ 20		x2 ≥ 0
x1, x2, x3, x4, x5 ≥ 0		18. Минимизировать
17. Максимизировать
F(x)=2x1+3x2-x3		F(x)=2x1 - 3x2 –3x4
при условиях		при условиях
x1 + 2x2 – 10 ≥ 0		2x1 - x2 - x3 – x4 ≥ 3
2x1 + x2 + x3 - 10 ≥ 0		x1 - x2 + x3 ≤ 2
x2 + x3 – 4 ≥ 0		x1, x2, x3 ≥ 0
x1, x2 ≥ 0

	20
19. Минимизировать	20. Минимизировать
F(x)=2x1 - 3x2 +6 x3 + x4	F(x)= - x1+3x2+3x3
при условиях	при условиях
x1 + 2x2 – 4x3 ≤ 20	x1 - x2 + x3 ≥ 1
x1 - x2 + 2x3 ≥ 10	x1 - x2 ≤ -2
2x1 + x2 - 2x3 + x4 =24	x1, x2, x3≥ 0
x1, x2, x3 ≥ 0 ,
x4 ≤ 0

21. Максимизировать

F(x)=3x1+2x3 - 6x6

при условиях

2x1 + x2 – 3x3 +6x6 =18 -3x1 + 2x3 + x4 - 2 x6 =24 x1 + 3x3+ x5 - 4x6 =36

x1, x2, x3, x4, x5, x6 ≥ 0

23. Максимизировать

F(x)=x1+3x2 – 5x4

при условиях

2x1 + 4x2 + x3 + 2x4 =28 -3x1 + 5x2 - 3x4 ≤ 30 4x1 - 2x2+ 8x4 ≤ 32

x1, x2, x3, x4 ≥ 0

25. Максимизировать

F(x)=2x1+5x2 – x3 – x4

при условиях

3(x1 + x2 - x3) ≤ 20

2x2 + 2x3 +x4 ≥ 10 x2 - x4 =2

3≤ x1 ≤ 6 , x3 ≤ 50 x3, x4 ≥ 0

22. Минимизировать

F(x)=2x1 + 3x2 - x4

при условиях

2x1 - x2 – 2x4 ≤ 16 3x1 + 2x2 + x3 –3x4 =18

-x1 + 3x2 + 4x4 ≤ 24 x2, x3, x4 ≥ 0

24. Максимизировать

F(x)=x1+2x2 – x3

при условиях

-x1 + 4x2 - 2x3 ≤ 6

x1 + x2 + 2x3 ≥ 6 2x1 - x2+ 2x3 =4

x1, x2, x3 ≥ 0

26. Максимизировать

F(x)=8x2+7x4 + x6

при условиях

x1 - 2x2 – 3x4 - 2x6 =12 4x2 + x3 - 4x4 - 3x6 =12 5x2 + 5x4+ x5 + x6 =25

x2, x3, x4, x5, x6 ≥ 0