А.В.Шатина МО 2012 версия 20.09.2013

61

			x
					1 j
где	x	j	...
				x
					mj

по базису a1,

   

...

– столбец коэффициентов разложения вектора

, a	m	. Тогда x	j	1	a	j	,	j 1,..., m, m 1,..., n .
				Ab

a	j

Для i 1, ... , m разложения векторов ai тривиальны: ai ai ,

следовательно, вектор-столбец xi

представляет собой единичный

вектор. При

i m 1, ... , n

неизвестные вектор-столбцы x

i

отыс-

киваются с помощью обратной матрицы.

в) В предпоследней строке z

под вектором b xb выписыва-

ется z0

cb , xb

–

значение целевой функции в крайней точке.

Под векторами a

j

j 1, ... , n в предпоследнюю строку записы-

ваются

значения

z j

cb , x

j

.

Очевидно,

что

при

j 1, ... , m

z j

c j

.

г) В последнюю строку, начиная с 4-го столбца, заносится разность между элементами предпоследней строки и элементами первой строки:

z c	i	z	c	,
		i	i

i

1,

...

,

n

.

c

c

…

cm

c

m1

…

c

j0

…

cn

t

1

базис

b xb

1

…

a

m

a

m1

…

a

j

0

…

a

n

a

1

c

x

1

…

0

x

…

x

…

x

t

a

1

1

1,m1

1, j

0

1,n

1

…

…

…

…

…

…

…

…

…

…

…

…

a

i

0

ci

xi

0

…

0

xi

,m 1

…

xi

, j

…

xi ,n

ti

0

0

0

0

0

0

0

…

…

…

…

…

…

…

…

…

…

…

…

a

m

cm

xm

0

…

1

xm,m 1

…

x

m,

j0

…

xm,n

tm

z

cb , xb

c1

…

cm

cb , xm 1

…

cb , x j0

…

cb , xn

0

…

0

m 1

…

j0

…

n

62

4) Исследовать симплексную таблицу.

чи,

S

а) Если
max	c
	b

,xb

0.

, то крайняя точка

x

является решением зада-

б) Если для некоторого

j

имеют место неравенства

j

0

и x

j

0 , то Smax .

в) Пусть в строке

имеются отрицательные числа, а соот-

ветствующие

столбцы

содержат положительные числа

и

min

j

j

0

. Тогда столбец с индексом j0 является разре-

j

0

			x
шающим. Введем обозначение: t	i		i	,	x	ij
		x				0
			ij0

чения	ti		ставим соответственно в последнем
Пусть	t		min t		0	. Тогда строка с номером
	i			i
		0	i

0		0	. Эти зна-

столбце таблицы. i0 является разре-

шающей, а разрешающим элементом симплексной таблицы яв-

ляется элемент

xi

0

, j

0

.

Далее необходимо из числа базисных векторов исключить

вектор

i

0

, и вместо него взять вектор a

j

0 .

Значение целевой

a

функции при этом возрастает на величину ti

0

j

0

.

5)

Построить

новую

симплексную

таблицу

для базиса

1

i 1

, a

j

, a

i

1

, ... , a

m

1

n

разложить

a , ... , a

0

0

0

, т.е. векторы b, a , ... , a

по новому базису.

Элементы таблицы x , не лежащие в разрешающем столбце

ij

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

x

x

x

j

x

x x

i

0

ij

0

,

x

x

i

0

ij

0

,

i i

,

j

0

i

i

x

ij

ij

x

j

j

i

0

0

i

0

0

j0

.

Элементы разрешающей строки делятся на разрешающий элемент:

63

xi0		xi0	,	xi0 j	xi0 j	,	j 1,..., n .
		xi0 j0			xi0 j0

Далее перейти к исследованию новой симплексной таблице, т.е. к пункту 4).

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

тельных координат крайней точки в таких задачах меньше	m , но
число базисных векторов всегда равняется рангу матрицы	A. Пе-

рейти от вырожденной задачи к невырожденной можно путем сколь угодно малого изменения начальных данных задачи. В вырожденных задачах возможны холостые шаги симплекс-метода, т.е. шаги, в результате которых значение целевой функции не изменяется. При этом теоретически возможно и зацикливание, т.е. бесконечное повторение холостых шагов. Для того чтобы избежать зацикливания, разработаны специальные алгоритмы – антициклины (см., например, Ф.П. Васильев «Методы оптимизации». М.: Факториал Пресс, 2002). На практике зацикливание происходит крайне редко, поэтому в данном курсе антициклины не рассматриваются.

Пример 1. Решить задачу линейного программирования в канонической форме с заданной начальной крайней точкой x0 0;0;2;4 , используя симплекс-метод:

f x

x1 2x2 x3 x4

x1 x2 x3 2,

x1 x2 x4 4, xi 0, i 1, ... ,4 .

max

;

Решение: Данная задача задана в канонической форме, также задана начальная крайняя точка. Построим симплексную таблицу. Матрица системы ограничений имеет вид:

1		1	1	0
A					.
	1	1	0	1

Базисная матрица задачи состоит из третьего и четвертого

	64
столбцов матрицы	A, соответствующих положительным коорди-

натам начальной крайней точки:

A		1
b		0

.

Так как базисная матрица в данной задаче является единич-

ной, то

x1

a	1

  

1
1

,

x	2	a	2

	1
	1

.

Построим и заполним симплексную таблицу:

		c		-1			2			-1			-1			t
базис			b xb	a	1		a	2		a	3		a	4
a		-1														2
	3		2	-1			1			1			0
a	4	-1	4	1			1			0			1			4
z			-6	0			-2			-1			-1
				1			-4			0			0

В последней строке таблицы содержится только один отри-

цательный элемент, соответствующий столбцу	a	2	. Поэтому этот

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

2, он соответствует базисному вектору

a	3

. Строка, соответству-

ющая

a	3

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

a	3

в базисе следует

заменить на				a	2	. Строим новую симплексную таблицу для нового
базиса a	2	, a		4	.
							c		-1	2	-1	-1	t
			базис					b xb	a1	a 2	a3	a 4
					2
				a			2	2	-1	1	1	0
				a	4		-1	2	2	0	-1	1
				z				2	-4	2	3	-1
									-3	0	4	0

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

								65
столбец	a		1	, содержащий только один положительный элемент,
соответствующий a					4	. Поэтому разрешающей строкой является
строка,	соответствующая a						4	. Столбец	a	4	в базисе заменяем на
столбец a		1		и для нового базиса строим симплексную таблицу.

базис

a	2
a	1
z

c

b x	b

2 3

-1 1

5

-1

a	1

0

1

-1

0

2

a	2

1

0

2

0

-1

a	3
1 2
1 2
3 2
5 2

-1		t
a	4
1 2
1 2
1 2
3 2

Так как

S	max	5

.

0

, то точка

xˆ 1;3;0;0

является решением задачи и

●

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

канонической	форме	с	заданной			начальной			крайней точкой
x0 0;1;2;0;1	, используя симплекс-метод:
	f x 2x1 x2			x3 x4 3x5 max ;
	x1 x2 6x3 10x5 23,
	x1 5x2 2x4 8x5 13,
	x1 5x2 x3 2x4 7x5 10 ,
			xi 0, i 1, ... ,5.
Матрица системы ограничений и базисная матрица имеют
вид:
	1 1 6		0	10		1		6	10
A 1 5 0			2	8	,	Ab	5	0	8	.
		1	2	7			5	1	7
	1 5

66

Найдем матрицу, обратную к

Ab , например, методом присо-

единенной матрицы. Для этого найдем определитель матрицы																Ab
и алгебраические дополнения элементов этой матрицы:
							det A		12,
								b
A	1,1		0	8	8,	1,2		5	8	5,	1,3		5	0	5,
						A					A
b			1	7		b		5	7		b		5	1
2,1			6	10	52,	2,2		1	10	43,	2,3		1	6	31,
A						A					A
b			1	7		b		5	7		b		5	1
3,1			6	10	48,	3,2		1	10	42,	3,3		1	6	30.
A						A					A
b			0	8		b		5	8		b		5	0

Присоединенная матрица

AV b

определяется как транспониро-

ванная к матрице, составленной из алгебраических дополнений соответствующих элементов матрицы Ab :

		A		1,1		A		2,1
			b				b
V	A		1,2			A	2,2
A
b		b				b
		A	1,3			A	2,3
		b				b
Тогда обратная матрица к									Ab

	A		3,1			8	52
		b
	A	3,2				5	43
	b
	A	3,3				5	31
	b

имеет вид:

48
42
30

.

						2 3		13 3
A	1		1	V			5 12	43 12
				A
b			det A	b
			b				5 12	31 12

4
7 2
5 2

.

Далее находим разложения векторов

1	, a	4
a

по базису a2 , a3 , a5 :

							1 3
1	A	1		1			1 3
								,
x			a
	b
							1 3

								2 3
x	4	A	1		4			1 6
				a
		b
								1 6

.

Разложением вектора b является вектор 1;2;1 ненулевых координат крайней точки. Составим симплексную таблицу:

67

базис

a	2
a	3
a	5
z

c	b x		2
				a	1
	b
1	1
				1 3
1	2
				1 3

3	1	1 3
	6	1 3

53

1

a	2

1

0

0

1

0

1		1		3
a	3	a	4	a	5
0		2 3		0
1		1 6		0

0	1 6	1
1	1 3	3

0

2 3

0

t

3

В последней строке имеются два	отрицательных числа.
Меньшее из них соответствует столбцу	a	1	. Этот столбец будет

разрешающим. В столбце a1 имеется один положительный эле-

мент, соответствующий a			5	, поэтому строка	a	5	будет разрешаю-
щей. Из числа базисных векторов исключаем вектор a								5	и вместо
него вводим вектор a	1	. Строим симплексную таблицу для нового

базиса:

базис

a	2
a	3
a	1
z

c

b x	b

1	2
1	3

2 3

11

2

a	1

0

0

1

2

0

1

a	2

1

0

0

1

0

1		1		3		t
a	3	a	4	a	5
0		1 2		1
1		0		1
0		1 2		3
1		1 2		8
0		3 2		5

Последняя строка новой таблицы содержит один отрица-

тельный элемент, соответствующий вектору	a	4	. В соответству-

ющем столбце только одно число является положительным. Это

число соответствует вектору	a	2	. На следующем этапе из числа

базисных векторов исключаем вектор a 2 и вводим вместо него вектор a 4 . Строим новую симплексную таблицу:

68

					c
	базис				1
	a	4
	a	3			1
	a	1			2
	z
	Так как
задачи и			Smax

	b x		2
			a	1
	b
	4		0
	3		0
	5		1

172

0

0	, то точка
17 .

1

a	2
2
0

1

4

3

xˆ

	1
	a	3
	0
	1
	0
	1
	0
5;0;3;

1		3		t
a	4	a	5
1		2
0		1

04

111

08

4;0	является решением
	●

Метод искусственного базиса нахождения начальной крайней точки

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

c, x max;

Ax b,

x

0

,

(зк)

где	x x1, ... ,		xn R	n	–	неизвестная	переменная,
c c ,	... , c Rn		и b b		, ... , b	Rm – заданные векторы,
1		n		1	m
A a
ij	i 1, ... ,m – заданная матрица размера m n. Будем считать,
	j 1, ... ,n
что b 0		(если b j 0 , то умножим обе части j -го уравнения на
(-1)).

Рассмотрим ные переменные

вспомогательную задачу, добавляя искусствен-
~	xn 1,..., xn m и единичную матрицу I :
x

	m	~			~
	xn i max;		b,	x 0,		0 .
		Ax Ix			x

i 1

з

Точка 0,...,0,b ,...,b Rn m				является начальной крайней
1			m
точкой для вспомогательной задачи з . Решение задачи з име-
ˆ			Тогда точка	x R	n	является начальной
ет вид: x x,0,...,0 .

крайней точкой исходной задачи (зк).

69

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

	f x 3x1 2x2 2x3 2x4 x5					max ;
	x1 x2 x3 1,
	x2 x3 x4 1,
	x	2	x	x	2
			3	5
	xi	0, i 1, ... ,5.
Решение: Составим вспомогательную задачу:
	x6 x7 x8 max					;
	x1 x2 x3 x6 1,
	x2 x3 x4 x7 1,
	x		x	x	x 2
		2	3	5	8
		xi 0, i 1, ... ,8 .
Начальной крайней точкой вспомогательной задачи являет-
ся точка	x0 0,0,0,0,0,1,1,2 . Заметим, что базисная матрица

вспомогательной

x	j	a	j	,	j 1, ... ,5

задачи есть единичная матрица. Поэтому

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

		c				0			0			0			0			0			-1			-1			-1			t
базис				b xb			a1			a 2			a3			a 4			a5			a6			a7			a8
a	6	-1		1			1			1			-1			0			0			1			0			0
a	7	-1	1				0		-1			1			1			0			0			1			0
a	8	-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. Так как в соответствующем столбце содержится только один положительный элемент, то соответству-

70

ющая строка a6 будет разрешающей. Исключаем из базиса век-

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

		c		0			0			0			0			0			-1			-1			-1			t
базис			b xb	a	1		a	2		a	3		a	4		a	5		a	6		a	7		a	8
a	1	0	1	1			1			-1			0			0			1			0			0
a	7	-1	1	0			-1			1			1			0			0			1			0			1
a	8	-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, соответствующий вектору

a	3

. Столбец

a	3	будет разрешающим. В этом столбце имеется два положи-

тельных элемента, поэтому заполняем последний столбец табли-

цы и находим наименьшее из получившихся чисел.																											Соответ-
ствующая строка a					7	является разрешающей.
	Выводим из базиса вектор												a	7	и строим таблицу для нового
базиса a1, a3 , a8 :
		c			0			0			0				0			0			-1			-1			-1			t
базис			b xb		a	1		a	2		a	3			a	4		a	5		a	6		a	7		a	8
a	1	0	2		1			0			0				1			0			1			1			0
a	3	0	1		0			-1			1				1			0			0			1			0
a	8	-1
			1		0			2			0				-1			1			0			-1			1
z			-1		0			-2			0				1			-1			0			1			-1
					0			-2			0				1			-1			1			2			0

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

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

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