Метод указ по МО

- 22 -

точки зрения составления и изменения плана перевозок продукций. Поэтому для транспортной задачи разработаны свои методы решения.

Рассмотрим один из общеизвестных методов решения транспортной задачи. Рассматриваемый метод основывается на том, что оптимальный план транспортной задачи достаточно находить среди опорных планов. Опорным планом называют допустимый план X , у которого ненулевых элементов не более чем m n 1. В случае, когда ненулевых элементов меньше, чем m n 1, опорный план называют вырожденным.

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

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

Пример 3.1. Решим транспортную задачу с матрицей транспортных издержек

7		8	5	3
		4	5
C 2				9
	6	3	1	2

и объемами запасов и потребностей

a1 11, a2 11, a3 8, b1 5, b2 9 , b3 9, b4 7.

Условие сбалансированности a1 a2 a3 b1 b2 b3 b4 соблюдено.

Составим первый опорный план методом северо-западного угла: сперва удовлетворим потребность пункта B1, затем пунктов B2 , B3 , B4 , поочередно опустошая пункты поставщиков A1, A2 , A3 (таб. 1).

- 23 -

				Таблица 1
	B1	B2	B3		B4	Запасы
A1						11
	5	6
A2						11
		3	8
A3						8
			1		7
Потребности
	5	9	9	7

Всего клеток - mn 3 4 12, из них заполненных - m n 1 3 4 1 7 .

Имеем первый опорный план:

	5		6	0	0
X (1)			3	8	0
	0					.
		0	0	1	7

На этом плане сумма транспортных издержек равна F(X (1) ) 150. Выясним,

является ли план	X (1)	оптимальным. Для этого находим потенциалы u ,				u	2	,
					1
u3 , v1, v2 , v3 , v4	из условия, что в каждой заполненной клетке (i,				j) должно
выполняться равенство		ui v j cij , полагая	u1 0 или v1	0 .	Затем	для
каждой пустой клетки		(i, j) находим оценку	ij cij (ui	v j ).	Если все

оценки неотрицательны, то опорный план оптимальный. Иначе, переходим к

другому опорному плану. Для плана	X (1)	имеем:
u1 0 , u2 4, u3 8,	v1 7 , v2 8, v3 9,			v4 10,
13 4, 14 7 , 21 1,		24 3,	31 7 ,	32 3.

Среди оценок есть отрицательная, следовательно, план X (1) не оптимальный.

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

одна из вершин которого есть выбранная клетка, остальные вершины –

- 24 -

заполненные клетки, и дуги которого направлены вертикально или горизонтально (таб. 2).

													Таблица 2
5	6
			-										+
	3										8
		+
								-
									1							7
							+							-

Вершины, начиная с пустой клетки, поочередно метим знаками «+» и «-». Из чисел, расположенных в клетках с меткой «-», вычитаем наименьшее из них и это же число прибавим к числам, расположенных в клетках с меткой «+». В

результате получаем второй опорный план (таб. 3).

										Таблица 3
	B1			B2				B3		B4	Запасы
A1											11
	5									6
A2											11
				9				2
A3											8
								7		1
Потребности
	5			9				9	7
			5	0	0	6
	X (2)			9	2	0			(2) ) 108.
		0						, F(X
				0	6	1
			0

Проверим оптимальность плана X (2) :
u1 0 ,	u2 3, u3 1, v1 7 , v2 1, v3 2,			v4 3,
12 7 ,	13 3, 21 8 ,	24 3,	31 0,	32 3.

Так как 21 8 0, план X (2) не оптимальный.

Построим цикл и переходим к другому опорному плану:

- 25 -

																				Таблица 4
		5																				6
			-																	+
								9					2
			+											-
															7						1
														+						-
Получаем третий опорный план:																		Таблица 5
		B1						B2								B3						B4		Запасы
A1																								11
		4																	7
A2																								11
		1						9					1
A3																								8
													8
Потребности
		5						9					9				7
							4	0	0		7
		X (3)						9	1								(3) ) 100.
						1				0 , F(X
								0	8	0
							0

Проверим оптимальность плана X (3) :
u1 0 , u2 5, u3 9, v1 7 ,												v2 9 , v3 10 , v4 3,
12 1,		13 5, 24 11,								31 8,			32 3, 34 8.
План X (3) не оптимальный. Переходим к четвертому опорному плану:
													Таблица 6
	4												7
			-						+
	1					9						1
			+						-
												8

- 26 -

	3		0	1	7
X (4)			9	0	0		F(X (4) ) 95.
	2					,
		0	0	8	0

План X (4) также не оптимальный, так как в этом случае имеем:

u1 0 ,	u2 5,	u3 4,	v1 7 , v2 9 , v3 5,	v4 3,
12 1,	23 5,	24 11,	31 3, 32 2 0,	34 1.

Переходим к пятому опорному плану:

		0	0	4		7
			6	0				F(X (5) ) 89,
	X (5) 5					0 ,
			3	5		0
		0
u1 0 , u2 3,		u3 4,			v1 5,			v2 7, v3 5,		v4 3,
11 2 ,	12 1,		23 3,			24 9, 31 5,			34 3.

Таким образом, оптимальным опорным планом является

0		0	4	7
		6	0
X * 5				0 .
	0	3	5	0

На нем достигается минимум суммы транспортных издержек:

Fmin F(X*) 89.

Задание № 3

Решить транспортную задачу с заданной матрицей транспортных

издержек C {cij}i				j			и объемами запасов	ai , i 1,3 и
		1,3,			1,5
потребностей bj , j			.
	1,5

- 27 -

						Варианты
1)				a		100,	2)				a	200,
6	1	2 3 1					1	1	2	3 1
	3	1 2 1			1			5			1
C 2			,	a2 200,			C 2		1 2 1 ,		a2 100,
	4	2 1 4		a3 300,				4	2		a3 200,
1							1			4 2
b1 100,		b2 50,		b3 100,			b1 100,		b2 50,		b3 100,
b4 200,		b5 150.					b4 100,		b5 150.
3)				a		200,	4)				a	100,
4	1	2 1 1					1	1	2	3 1
	3	1 2 1			1			5			1
C 2			,	a2 100,			C 2		1 2 1 ,		a2 200,
	2	2 1 2		a3 300,				4	2		a3 200,
1							1			4 2
b1 50,	b2 100,			b3 100,			b1 70,	b2		80,	b3 100,
b4 200,		b5 150.					b4 150,		b5 100.
5)				a		150,	6)				a	200,
1	1	2 3 1					3	1	2 3 1
	3	1 2 1			1			5			1
C 2			,	a2 50,			C 2		1 2 1 ,		a2 200,
1	4	2 1 3		a	3	300,	1	6	2 4 1		a	100,
											3
b1 90,		b2 60,		b3 150,			b1 40,	b2 110,			b3 100,
b4 100,		b5 100.					b4 100,		b5 150.
7)				a		200,	8)				a	200,
3	1	2 5 1					5	1	2 3 1
	1	1 2 1		1				1			1
C 2			,	a2 100,			C 2		1 2 3 ,		a2 100,
1	2	2 1 2		a	3	300,	1	4	2 1 2		a	200,
											3
b1 50,	b2 100,			b3 100,			b1 70,		b2 80,		b3 100,
b4 200,		b5 150.					b4 100,		b5 150.

- 28 -

9)				a	100,
1	1	2 3 1
	1			1
C 2		1 2 1 ,		a2 200,
	4			a3 300,
1		1 1 4
b1 100,		b2 50,		b3 100,
b4 200,		b5 150.
11)				a	200,
3	1	2 1 1
	2	1 2 1		1
C 2			,	a2 100,
1	2	3 2 2		a	300,
				3
b1 50,	b2 100,			b3 100,
b4 200,		b5 150.
13)				a	150,
5	1	2 3 5
	3	1 2 1		1
C 2			,	a2 150,
1	4	5 5 3		a	300,
				3
b1 90,		b2 60,		b3 150,
b4 100,		b5 200.
15)				a	200,
3	1	2 5 2
	2	1 2 1		1
C 2			,	a2 100,
1	2	3 1 2		a	300,
				3
b1 50,	b2 100,			b3 100,
b4 200,		b5 150.
17)				a	100,
1	1	2 3 1
	1			1
C 2		1 2 1 ,		a2 200,
1	4	1 1 4		a	300,
				3

10)				a	200,
2	1	2 3 1
	2	1 2 1		1
C 2			,	a2 100,
1	4	2 3 2		a	200,
				3
b1 100,		b2 50,		b3 100,
b4 100,		b5 150.
12)				a	100,
4	1	2 1 1
	5			1
C 2		1 2 1 ,		a2 200,
1	4	2 1 2		a	200,
				3
b1 70,		b2 80,		b3 100,
b4 150,		b5 100.
14)				a	200,
1	1	2 3 1
	2			1
C 2		1 2 1 ,		a2 200,
1	6	1 4 1		a	100,
				3
b1 40,	b2 110,			b3 100,
b4 100,		b5 150.
16)				a	200,
4	1	2 3 1
	1	3 2 3		1
C 2			,	a2 100,
1	4	2 1 2		a	200,
				3
b1 70,		b2 80,		b3 100,
b4 100,		b5 150.
18)				a	200,
2	1	2 3 1
	2	1 2 1		1
C 2			,	a2 100,
1	4	2 4 2		a	200,
				3

- 29 -

b1 100,		b2 50,			b3 100,
b4 200,			b5 150.
19)					a	200,
3	1		2 1 1
	3		1 2 1		1
C 2				,	a2 100,
1	2		3 1 2		a	300,
					3
b1 50,	b2		100,		b3 100,
b4 200,			b5 150.
21)					a	150,
5	1		2 3 1
	5		1 2 1		1
C 2				,	a2 150,
1	4		5 1 3		a	300,
					3
b1 90,		b2 60,			b3 150,
b4 100,			b5 200.
23)					a	200,
4	1		2 5 1
	5		1 2 1		1
C 2				,	a2 100,
1	2		4 1 2		a	300,
					3
b1 50,	b2		100,		b3 100,
b4 200,			b5 150.
25)					a	100,
3	2	2 3 1
	3				1
C 2		1 2 1 ,			a2 200,
1	4	2 1 4			a	300,
					3
b1 100,	b2		50,	b3 100,
b4 200,		b5 150.

b1 100,		b2 50,	b3 100,
b4 100,		b5 150.
20)			a	100,
4	1	2 3 1
	4		1
C 2		1 2 1 ,	a2 200,
1	4	4 4 2	a	200,
			3
b1 70,		b2 80,	b3 100,
b4 150,		b5 100.
22)			a	200,
6	1	2 3 1
	6		1
C 2		1 2 1 ,	a2 200,
1	6	6 4 1	a	100,
			3
b1 40,	b2 110,		b3 100,
b4 100,		b5 150.
24)			a	200,
5	1	2 3 1
	2		1
C 2		1 2 3 ,	a2 100,
1	4	2 1 2	a	200,
			3
b1 70,		b2 80,	b3 100,
b4 100,		b5 150.

(x*,u*)

- 30 -

§4. Метод выпуклого программирования

Метод выпуклого программирования применяется для нахождения минимума выпуклой функции при ограничениях, заданных системой неравенств:

f (x) min , gk (x) 0, k 1, m,

где функции f (x), gk (x) , k 1, m определены на выпуклом множестве D ,

непрерывны и выпуклы. Данную задачу называют задачей выпуклого программирования.

Множество D называют выпуклой, если для любых x , y D, [0,1]

имеет место x (1 )y D . Функцию f , определенную на		выпуклом
множестве D , называют	выпуклой, если при любых x , y D,	[0,1]
выполняется неравенство	f ( x (1 )y) f (x) (1 ) f ( y).

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

Лагранжа

L(x,u) f (x) u1g1(x) ... um gm (x),

где u (u1, ..., um ) называют вектором множителей Лагранжа. Пару называют седловой точкой функции Лагранжа, если для любого вектора x D

и любого неотрицательного вектора множителей Лагранжа u выполняются неравенства

L(x*,u) L(x*,u*) L(x,u*).

Следующее условие называют условием Слейтера: существует x(0) D

такой, что gk (x(0) ) 0 при всех k 1, m.

Основу метода выпуклого программирования составляет следующая теорема.

Теорема Куна-Таккера. Пусть выполнено условие Слейтера. Тогда вектор x* D будет решением задачи выпуклого программирования только в

(x*,u*)

- 31 -

том случае, когда существует неотрицательный вектор u *, образующий вместе с x * седловую точку функции Лагранжа.

Седловую точку (x*,u*) можно находить среди критических точек функции Лагранжа, если функция Лагранжа дифференцируема:

	L	(x,u) 0, i		,	L	(x,u) 0, k		.
			1, n				1, m
	xi				uk

Пример 4.1. Найдем методом выпуклого программирования расстояние от точки A(3; 3) до выпуклого шестиугольника с вершинами в точках

A1( 3; 2) ,

A2 (1; 2) , A3(4; 2) ,

A4 (2; 8),

A5( 2; 7) ,

A6 ( 6; 2) .

Составим задачу выпуклого программирования. Целевой функцией

является функция расстояния от точки A(3; 3) до точек шестиугольника

A1A2 A3 A4 A5 A6 . Шестиугольник A1A2 A3 A4 A5 A6 есть множество,

ограниченное прямыми линиями

x2 2,

4x1 3x2 10,

3x1 x2 14,

x1 4x2 30,

5x1 4x2 38, 4x1 3x2 18.

Расстояние

от точки

A(3; 3) до любой

точки

x (x1, x2 )

определяется

.

формулой

(x

3)

2 (x

2

3)2

Легко

проверить, что

множество точек

1

шестиугольника

(вместе

с

внутренностью)

и

функция

f (x) (x

3)2

(x

2

3)2

выпуклые. Таким образом, получаем следующую

1

задачу выпуклого программирования:

f (x) (x 3)2

(x

2

3)2 min ,

1

x2 2 0,

4x1 3x2 10 0,

3x1 x2 14 0,

x1 4x2 30 0,

5x1 4x2 38 0 ,

4x1 3x2 18 0.

Условие Слейтера выполняется, так как внутренность

шестиугольника

непустая.