Metody_optimizatsii_Shatina_A_V

71

что b ³ 0 (если $bj < 0 , то умножим обе части j -го уравнения на (-1)).

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

~

(

xn+1,..., xn+m

)

и единичную матрицу I :

ные переменные x =

m

~

= b,

x ³ 0,

~

³ 0

- å xn+i ® max; Ax + Ix

x

( з¢)

i

=

.

1

Точка

(0,...,0,b ,...,b

) Î Rn+m

является начальной крайней

1

m

точкой для вспомогательной задачи ( з¢) . Решение задачи( з¢) име-

ет вид: xˆ = ( x,0,...,0) . Тогда точка x Î Rn является начальной крайней точкой исходной задачи (зк).

Пример 3. Решить задачу линейного программирования симплекс-методом, находя начальную крайнюю точку методом искусственного базиса.

f ( x) = 3x1 - 2x2 + 2x3 - 2x4 + x5 ® max ; x1 + x2 - x3 = 1,

- x2 + x3 + x4 = 1,

x2 + x3 + x5 = 2 xi ³ 0, i = 1, ... ,5.

Решение: Составим вспомогательную задачу:

-x6 - x7 - x8 ® max ; x1 + x2 - x3 + x6 = 1,

-x2 + x3 + x4 + x7 = 1,

x2 + x3 + x5 + x8 = 2 xi ³ 0, i = 1, ... ,8.

Начальной крайней точкой вспомогательной задачи является точка x0 = (0,0,0,0,0,1,1,2) . Заметим, что базисная матрица вспомогательной задачи есть единичная матрица. Поэтому

x j = a j , j =1, ... ,5. Построим симплексную таблицу:

					72
	c		0	0	0	0	0	-1	-1	-1	t
базис		b( xb )	a1	a2	a3	a4	a5	a6	a7	a8
a6	-1	1	1	1	-1	0	0	1	0	0
a7	-1	1	0	-1	1	1	0	0	1	0
a8	-1	2	0	1	1	0	1	0	0	1
z		-4	-1	-1	-1	-1	-1	-1	-1	-1
			-1	-1	-1	-1	-1	0	0	0

В последней строке содержится 5 одинаковых отрицательных чисел. Для определенности в качестве разрешающего столб-

ца возьмем столбец a1. Так как в соответствующем столбце содержится только один положительный элемент, то соответствую-

щая строка a6 будет разрешающей. Исключаем из базиса вектор a6 и заменяем его на a1. Строим новую симплексную таблицу:

	c		0	0	0	0	0	-1	-1	-1	t
базис		b( xb )	a1	a2	a3	a4	a5	a6	a7	a8
a1	0	1	1	1	-1	0	0	1	0	0
a7	-1	1	0	-1	1	1	0	0	1	0	1
a8	-1	2	0	1	1	0	1	0	0	1	2
z		-3	0	0	-2	-1	-1	0	-1	-1
			0	0	-2	-1	-1	1	0	0

Минимальным отрицательным элементом в последней стро-

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

строка a7 является разрешающей.

Выводим из базиса вектор a7 и строим таблицу для нового базиса a1,a3 ,a8:

c

0

0

0

0

0

-1

-1

-1

t

					73
базис		b( xb )	a1	a2	a3	a4	a5	a6	a7	a8
a1	0	2	1	0	0	1	0	1	1	0
a3	0	1	0	-1	1	1	0	0	1	0
a8	-1	1	0	2	0	-1	1	0	-1	1
z		-1	0	-2	0	1	-1	0	1	-1
D			0	-2	0	1	-1	1	2	0

Минимальным отрицательным элементом в последней стро-

ке является элемент -2, соответствующий вектору a2 . Столбец a2 будет разрешающим. В этом столбце имеется одно положитель-

ное число, поэтому строка a8 является разрешающей. Строим та- блицу для базиса a1,a3,a2 :

	c		0	0	0	0		0	-1	-1	-1	t
базис		b( xb )	a1	a2	a3	a4		a5	a6	a7	a8
a1	0	2	1	0	0	1		0	1	1	0
a3	0	3 2	0	0	1	1 2		1 2	0	1 2	1 2
a2	0	1 2	0	1	0	− 1 2	1 2		0	− 1 2	1 2
z		0	0	0	0	0		0	0	0	0
D			0	0	0	0		0	1	1	1
Так как D ³ 0 , то точка (2;1 2;3 2;0;0;0;0;0)										является реше-
нием вспомогательной задачи, а точка								(2;1 2;3 2;0;0 )			является

начальной крайней точкой исходной задачи. Используя получен-

ные разложения векторов по базису a1,a3,a2 , строим симплексную таблицу исходной задачи:

	c		3	-2	2	-2	1	t
базис		b( xb )	a1	a2	a3	a4	a5
a1	3	2	1	0	0	1	0
a3	2	3 2	0	0	1	1 2	1 2	3
a2	-2	1 2	0	1	0	− 1 2	1 2	1
z		8	3	-2	2	5	0

74

D

0

0

0

7

-1

Последняя строка содержит один отрицательный элемент, соответствующий вектору a5 . Вычисляем элементы последнего столбца и выбираем наименьший положительный, соответствующий разрешающей строке a2 . Для нового базиса a1,a3,a5 строим таблицу:

	c		3	-2	2	-2	1	t
базис		b( xb )	a1	a2	a3	a4	a5
a1	3	2	1	0	0	1	0
a3	2	1	0	-1	1	1	0
a5	1	1	0	2	0	-1	1
z		9	3	0	2	4	1
D			0	2	0	6	0

Так как D ³ 0		ˆ	= (	)
		, то x		3;0;2;0;1 является решением задачи,
Smax = 9 .

Замечание. В данной задаче можно было ограничиться вве-

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

матрицы. Тогда число шагов значительно бы уменьшилось.	●
Пример 4. Решить задачу линейного программирования:
f ( x) = -2x1 + x2 - x3 + x5 ® min ;	(з)
2x2 - x4 - x5 = 3,
x3 - 2x4 = 2,
x1 + 3x2 - x4 £ 5,
x1 + x2 ³ -3, x j ³ 0, j = 1,...,5.

На первом шаге приведем данную задачу к канонической

форме, введя дополнительные переменные x6 , x7 . Получим следующую задачу:

- f ( x) = 2x1 - x2 + x3 - x5 ® max ;

(з1)

ственные переменные

						75
		x1 + 3x2 - x4 + x6 = 5,
			- x1 - x2 + x7 = 3,
			2x2 - x4 - x5 = 3,
x	3	- 2x	4	= 2	,	x j ³ 0, j = 1, ... ,7	.

Полученную задачу линейного программирования (з1) в канонической форме будем решать методом искусственного базиса. Для этого рассмотрим вспомогательную задачу, добавляя искус-

x8, x9 :

				- x8 - x9 ® max ;						(з2)
			x1 + 3x2 - x4 + x6 = 5,
				- x1 - x2 + x7 = 3,
			2x2 - x4 - x5 + x8 = 3,
x	3	- 2x	4	+ x	9	= 2	,	x j ³ 0, j = 1, ... ,9		.
Начальная крайняя точка задачи (з2)									x0 = (0,0,0,0,0,5,3,3,2) .

Базисные векторы

a6 = (1,0,0,0), a7 = (0,1,0,0), a8 = (0,0,1,0), a9 = (0,0,0,1) . Составим симплексную таблицу для задачи (з2):

	c		0	0	0	0	0	0	0	-1	-1	t
базис		b( xb )	a1	a2	a3	a4	a5	a6	a7	a8	a9
a6	0	5	1	3	0	-1	0	1	0	0	0	5 3
a7	0	3	-1	-1	0	0	0	0	1	0	0
a8	-1	3	0	2	0	-1	-1	0	0	1	0	3 2
a9	-1	2	0	0	1	-2	0	0	0	0	1
z		-5	0	-2	-1	3	1	0	0	-1	-1
			0	-2	-1	3	1	0	0	0	0

Из таблицы видно, что разрешающим столбцом является

76

столбец a2 , а разрешающей строкой a8 . Заменяем в базисе вектор a8 на вектор a2 и строим новую симплексную таблицу:

	c		0	0	0	0	0	0	0	-1	-1	t
базис		b( xb )	a1	a2	a3	a4	a5	a6	a7	a8	a9
a6	0	1 2	1	0	0	1 2	3 2	1	0	− 3 2	0
a7	0	9 2	-1	0	0	− 1 2	− 1 2	0	1	1 2	0
a2	0	3 2	0	1	0	− 1 2	− 1 2	0	0	1 2	0
a9	-1	2	0	0	1	-2	0	0	0	0	1
z		-2	0	0	-1	2	0	0	0	0	-1
D			0	0	-1	2	0	0	0	1	0

Заменяем в базисе вектор a9 на вектор a3 и строим новую симплексную таблицу:

	c		0	0	0	0	0	0	0	-1		-1	t
базис		b( xb )	a1	a2	a3	a4	a5	a6	a7	a8		a9
a6	0	1 2	1	0	0	1 2	3 2	1	0	− 3 2		0
a7	0	9 2	-1	0	0	− 1 2	− 1 2	0	1	1 2	0
a2	0	3 2	0	1	0	− 1 2	− 1 2	0	0	1 2		0
a3	0	2	0	0	1	-2	0	0	0	0		1
z		0	0	0	0	0	0	0	0	0		0
D			0	0	0	0	0	0	0	1		1
Вектор D ³ 0 ,				поэтому		точка	~
							x = (0;3 2;2;0;0;1 2;9 2;0;0)
является		решением		вспомогательной задачи					(з2). Тогда			точка
~					является начальной крайней точкой за-
x0 = (0;3 2;2;0;0;1 2;9 2)

дачи линейного программирования в канонической форме (з1). Приступим к решению задачи (з1). Составим первую сим-

плексную таблицу для начальной крайней точки

77

~x0 = (0;32;2;0;0;12;92) . Разложения векторов b,a1,a4 ,a5 возьмем из последней симплексной таблицы:

	c		0	0	0	0	0	0	0	t
базис		b( xb )	a1	a2	a3	a4	a5	a6	a7
a6	0	1 2	1	0	0	1 2	3 2	1	0
a7	0	9 2	-1	0	0	− 1 2	− 1 2	0	1
a2	-1	3 2	0	1	0	− 1 2	− 1 2	0	0
a3	1	2	0	0	1	-2	0	0	0
z		1 2	0	-1	1	− 3 2	1 2	0	0
			-2	0	0	− 3 2	3 2	0	0

Из таблицы видно, что разрешающим столбцом является столбец a1, а разрешающей строкой a6 . Заменяем в базисе вектор a6 на вектор a1 и строим новую симплексную таблицу:

	c		0	0		0	0		0		0		0		t
базис		b( xb )	a1	a2		a3	a4		a5		a6		a7
a1	2	1 2	1	0		0	1 2		3 2		1		0
a7	0	5	0	0		0	0		1		1		1
a2	-1	3 2	0	1		0	− 1 2		− 1 2		0		0
a3	1	2	0	0		1	-2		0		0		0
z		3 2	2	-1		1	− 1 2		7 2		2		0
			0	0		0	− 1 2		9 2		2		0
Далее заменяем в базисе вектор a1 на вектор a4 и строим
новую симплексную таблицу:
	c		0	0		0	0		0		0		0		t
базис		b( xb )	a1	a2		a3	a4		a5		a6		a7

											78
a4		0	1			2			0		0		1		3	2	0
a7		0	5			0			0		0		0		1	1	1
a2		-1	2			1			1		0		0		1	1	0
a3		1	4			4			0		1		0		3 2	4	0
z			2			3		-1			1		0		1 2	3	0
D						1			0		0		0		3 2	3	0
	Так как D ³ 0 , то точка (0;2;4;1;0;0;5) является решением за-
						ˆ		= (		0;2;4;1;0		)	является решением исходной
дачи (з1). Тогда точка x
задачи (з).
			ˆ	(	0;2;4;1;0				)	Î abs min з,				Smin = -2 .					●
	Ответ: x =

Задачи для самостоятельного решения.

Решить симплекс-методом задачи линейного программирования в канонической форме с заданной начальной крайней точкой:

6.1.f ( x) = 2x1 + x2 + 3x3 + x4 ® max ;

x1 + 2x2 + 5x3 - x4 = 4 , x1 - x2 - x3 + 2x4 = 1,

xi ³ 0, i = 1, ... ,4, x0 = (0;0;1;1)

6.2.f ( x) = 6x1 + x2 + 4x3 - 5x4 ® max ;

3x1 + x2 - x3 + x4 = 4, 5x1 + x2 + x3 - x4 = 4 ,

xi ³ 0, i = 1, ... ,4, x0 = (1;0;0;1)

79

6.3.f ( x) = x1 + x2 + x3 + x4 + x5 ® max ;

2x1 + 3x2 + 5x3 + 7x4 + 9x5 = 19, x1 - x2 + x4 + 2x5 = 2,

xi ³ 0, i = 1, ... ,5, x0 = (0;0;1;2;0)

6.4.f ( x) = x1 + 2x2 + 2x3 + x4 + 6x5 ® max ;

x1 + 3x2 + 3x3 + x4 + 9x5 = 18, x1 + 5x2 + 2x4 + 8x5 = 13,

x3 + x5 = 3

xi ³ 0, i = 1, ... ,5, x0 = (0;1;2;0;1)

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

6.5. x1 + 4x2 + x3 ® max ; x1 - x2 + x3 = 3,

2x1 - 5x2 - x3 = 0, xi ³ 0, i = 1, ... ,3.

6.6.f ( x) = -6x1 - 8x2 + x3 + 3x4 ® min ;

	2x1 + 5x2 + x3 + 2x4 = 20,
	12x1 + 6x2 + 2x3 + x4 = 72 ,
	xi ³ 0, i = 1, ... ,4
Указание: привести предварительно задачу к канонической
форме.
6.7.	f ( x) = x1 + 4x4 ® max ;
	- x1 - 2x2 + 2x3 + x4 + 5x5 = 13,
	- 2x1 + 2x2 + 4x4 + x5 = 5,
	x1 - x2 + x3 - x4 + 2x5 = 5

80

xi ³ 0, i = 1, ... ,5.

Найти решение задач линейного программирования:

6.8. f ( x) = x1 - x2 + x3 ® min ; x1 - 3x2 + 5x3 ³ 1,

x1 + x2 + x3 ³ 3,

2x1 + x2 - 4x3 ³ 0 xi ³ 0, i = 1,2,3.

6.9.f ( x) = 2x1 + x2 + 3x3 + 5x4 ® max;

2x1 + 3x2 + x3 + 2x4 £ 30, 4x1 + 2x2 + x3 + 2x4 £ 40, x1 + 2x2 + 3x3 + x4 £ 25, xi ³ 0, i = 1, ... ,4

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

f ( x) = -2x1 + x2 - x3 + x5 ® min ; 2x2 - x4 - x5 = 3,

x3 - 2x4 = 2, x1 + 3x2 - x4 £ 5,

x1 + x2 ³ -3, x j ³ 0, j = 1,...,5.

Занятие 7. Транспортная задача.

Транспортная задача является важным частным случаем задачи линейного программирования. Она представляет собой математическую модель задач по оптимизации перевозок.

Постановка задачи. Имеется m станций отправления A1, A2,..., Am , на которых сосредоточено соответственно a1, a2,..., am единиц некоторого однородного груза. Этот груз сле-