MO_conspect

Есть опорный	план!			Ищем		оптимальное			решение: m 3 ,			n 4,
m n 1 6.
		15– 14			35+ 10		14	2	10	5
		13		б	23	б	14
		8		11	4	5	20	4	12	11
							20	б
		10+		9	7	8	32	12	20	1
		2		б	7 –		1	б	20	б
v1 u1 14 ,					v2 u1 10 ,					v1 u3 9 ,
v3 u3 12 ,					v3 u2 4 ,					v4 u3 1,
u1 0	v1 14				v4 6
u2 13	v2 10
u3 5	v3 17
v4 u1 6 5 ,	v1 u2 1 11,					v2 u2 3 5,
v4 u2 7 11.
v3 u1 17 2 ,	v2 u3 5 8.
Максимальное 32 3,			x32 помечаем (–) и строим цикл, = 7. Система по-
тенциалов та же, потенциалы те же. x14 в базис с (+).
		15– 14			35	10	14	2	10	5
		6	б		30	б	14			+
		8		11	4	5	20	4	12	11
							20	б
		10+		9	7	8	32	12	20	1
		9		б			1	б	20 – б
min ', ", di	, j min 13, 10 9,
							10 1. Т.е.			x31 из базиса.
0	0
		15		14	35	10	14	2	10	5
		5		б	30	б	14		1	б
		8		11	4	5	20	4	12	11
							20	б
		10		9	7	8	32	12	20	1
		10					1	б	19	б
Система уравнений:
v1 u1 14 ,					v2 u1 10 ,					v4 u1 5 ,
v3 u3 12 ,					v3 u2 4 ,					v4 u3 1,
u1 0	v1 14				v4 5

101

u2 12	v2 10
u3 4	v3 16

Проверяем условия потенциальности для xij 0 :

v1 u2 2 11,	v2 u2 2 5 ,
v4 u2 7 11,	v2 u3 6 8
для xij dij :
v3 u1 16 2 ,	v1 u3 10 9.

Все условия выполняются, план оптимален.

Контрольные вопросы

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

2.К чему приводит наличие ограничений на пропускные способности?

3.Метод потенциалов для определения оптимального плана транспортной задачи с ограничениями?

4.Метод потенциалов для определения опорного плана транспортной задачи с ограничениями?

5.К чему может привести вырожденность в такой транспортной задаче?

11.Транспортная задача по критерию времени

Втакой транспортной задаче решающую роль играет не стоимость перевозок, а время, которое затрачивается на доставку груза. Оптимальным планом считается план, который минимизирует время перевозок [9]. Подобные задачи возникают при перевозках скоропортящихся продуктов, в военном деле, где зачастую стоимость перевозок играет второстепенную роль. Как и в предыдущей задаче имеется m пунктов отправления с запа-

сами однородного продукта ai , n пунктов назначения с потребностями b j .

	n	m
Задача закрытого типа, т.е.	bj	ai .
	j 1	i 1
Задана матрица T [tij ]m n ,	где tij	– время, необходимое для пере-

возки груза из пункта i в пункт j.

Необходимо выбрать среди допустимых такой план X [xij ]m,n , что

102

Tmin .

m
xij bj , j
		1, n
i 1
n
xij ai , i
	1, m
j 1

и грузы будут доставляться по этому плану за минимальное время Каждому допустимому плану X [xij ]m,n соответствует некоторый

набор tij X , состоящий из элементов матрицы T [tij ]m n , соответствую-

щих положительным компонентам xij плана X . Т.е. tij включается в на-

бор, если производится перевозка из пункта i в пункт j.

Время tX , необходимое для выполнения плана X , определяется следующим образом

tX max{tij}X .

Тогда время, необходимое для реализации оптимального плана X *

tX * min tX	min (max{tij}X ) .
X	X

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

1. Предварительный шаг.

Строим допустимый план по методу северо-западного угла или минимального элемента X 0 .

2. Общий шаг.

Просматриваем все tij , соответствующие положительным xij , и выбираем из них наибольшее

t

max{t

ij

}

ij

xij 0

и вычеркиваем все клетки, для которых t

ij

t

ij

,

x

0 .

ij

Далее производим исправление плана X 0 , для чего стремимся обра-

тить в 0 перевозку x ', соответствующую

t

max{t

ij

} (в той же клетке).

ij

ij

xij 0

Если это удается, то, естественно, уменьшается время, необходимое на реализацию нового допустимого плана X1 . Для построения плана X1 строится цикл как и в методе потенциалов.

Первой клеткой отрицательной полуцепи берем клетку с tij ', остальными клетками отрицательной полуцепи выбираем клетки с xij >0, клетка-

ми положительной полуцепи берем клетки с tij tij .

103

Затем перемещаем минимальный элемент отрицательной полуцепи в положительную. Если удается обратить xij ' в 0, то реализация нового

плана потребует меньшего времени.

Общий шаг продолжаем повторять до тех пор, пока станет невозможным обращение в 0 всей перевозки xij ' из клетки с максимальным

временем tij '.

Пример 1.

b j	7			13				9	11
ai
10	8				10			8	2
	7			3
18	12			7				3	1
				10				8
12	5			8				1	6
								1	11
b j	7			13				9	11
ai
10		8			10			8	2
	7			×				×	3
18	12			7				3	1
	×			13				5
12	5			4				1	6
								4	8
b j	7			13				9	11
ai
10	8			10				8	2
	×			×				×	10
18	12					7		3	1
	×			13				5
12	5			4				1	6
	7							4	1

104

				b j		7			13			9			11
		ai
			10			8					10			8			2
						×			×			×			10
			18			12					7			3			1
						×			8			9			1
			12			5					4			1			6
						7			5
									tmin		= 7
Пример 2.
		b j		30			80				20			30			90
	ai
	120					6			8		2			3			5
	30					8			5		6			6			2
	40					2			4		7			4			8
	60					3			4		2			1			4
		b j		30			80				20			30			90
	ai
	120					6			8		2			3			5
				×			×				20			30			70
	30					8			5		6			6			2
				30							×			×
	40					2			4		7			4			8
							40				×						×
	60					3			4		2			1			4
							40										20

tmin = 5

Контрольные вопросы

1.Как построить допустимый план транспортной задачи по критерию времени?

2.Как ищется оптимальный план?

105

12. Задача о максимальном потоке в транспортной сети

12.1. Постановка задачи

Определение 1. Транспортной сетью называется конечный граф G , состоящий из ( n 1) вершин P0 , P1 ,…, Pn и из дуг ( Pi , Pj ), соединяющих

некоторые пары этих вершин, причем каждой дуге поставлено в соответствие число cij 0, называемое пропускной способностью дуги ( Pi , Pj ).

Вершина P0 называется входом сети, а Pn – выходом транспортной

сети.

Будем считать, что граф симметрический, т.е. если в него входит дуга ( Pi , Pj ), то входит и дуга ( Pj , Pi ).

cij – определяет количество вещества (машин, и т.п.), которое может

протекать по дуге в единицу времени. Например:

3

cij

= 0, если Pi

и Pj

P1

P5

не соединены дугой.

6

1

5

По путям ( P0 ,

Pi ,

2

2

2

5

Pi ,…,

Pi

,

1

2

3

6

Pn ), состав-

2

k

2

4

3

P4

7

ленным

из

дуг сети

P0

P6

( P

, P ),

( P , P ),

…,

1

P2

7

8

8

0

i1

i1

i2

( Pi

, Pn )

направляется

4

k

9

транспорт из P0

в Pn .

2

Потоком x

3

10

по ду-

ij

P3

ге ( P ,

P )

( i, j 0,..., n ,

i

j

i j )

называется коли-

чество вещества, проходящее через эту дугу в единицу времени.

Потоком по сети или просто потоком будем называть совокупность

потоков { x	ij	} по всем дугам сети.
Потоки должны удовлетворять следующим ограничениям:
		0 xij cij ( i,		j 0,..., n , i j ),	(1)
		n 1	n
		xik	xkj ,	( k 1,...n 1),	(2)
		i 0	j 1

что означает: количество вещества, притекающее в вершину сети равно количеству вещества, вытекающего из него (кроме P0 и Pn ).

Поток, удовлетворяющий ограничениям (1) и (2), будем называть допустимым.

106

n

Из (2) видно, что общее количество вещества x0 j , вытекающего

j 1

				n 1
из P0 , совпадает с общим количеством вещества xin , притекающего в
				i 0
Pn , т.е.
n 1	n
xin x0 j Q .				(3)
i 0	j 1
Линейная форма Q называется потоком по сети.
Задача о максимальном потоке в транспортной сети заключается в
отыскании такого решения x*	( i, j		) системы (1) – (2), т.е. такого до-
		0, n
ij

пустимого потока, который максимизирует Q . Это решение { x* } называ-

ij

ется максимальным потоком сети.

Рассмотрим такой простейший пример.

Найти максималь-

P1

1

P4

ный поток из P в

0

1

P7 . Толстые дуги

1

насыщены,

т.е.

2

x

= c

,

полный

2

2

1

ij

ij

n

P0

2

P2

1

1

P5

2

P7 поток

x0 j

5 ,

j 1

а

максимальный

2

поток равен 6.

1

1

2

Разобьем мно-

жество

всех

вер-

шин

G

на

два

P3

1

P6

подмножества

U

и

V

так,

что

P0 U и Pn V . Сечением (U ,V ) сети G назовем совокупность всех дуг ( Pi , Pj ), концы которых принадлежат разным подмножествам.

Каждому сечению поставим в соответствие неотрицательное число C(U ,V ) – пропускную способность сечения, равную сумме cij всех дуг

сечения, начинающихся в U и кончающихся в V , т.е.

C(U ,V ) cij

P U

i

Pj V

107

Любой путь из P0 в Pn обязательно содержит хоть одну дугу сечения

(U ,V ), которая начинается в U и заканчивается в V . Ясно, что пропускная способность пути не превышает пропускной способности каждой его дуги. Поэтому величина любого потока из P0 в Pn , которая является сум-

марной величиной пропускной способности всех путей из P0 в Pn , не мо-

жет превысить пропускной способности любого сечения (U ,V ), т.е. всегда

Q C(U ,V ) .

Теорема Форда-Фалкерсона утверждает следующее.

Теорема [9]. Для заданной транспортной сети наибольшая величина потока равна наименьшей пропускной способности сечения, т.е.

max Q min С(U ,V ) C(U *,V * )

(U ,V )

по всем возможным сечениям.

Таким образом, если удастся построить такой поток { x* }, что

ij

Q* C(U *,V * ) , то этот поток будет максимальным, а сечение C(U *,V * ) – обладать минимальной пропускной способностью.

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

12.2. Алгоритм построения максимального потока в транспортной сети

Предварительный шаг. Условия (1) записываются в виде следую-

щей таблицы. Если	cij	0,	c ji 0, то в клетке ji ставим 0. Если же
cij c ji 0, то клетки ij		и ji не заполняем.
Начальная таблица:	(4)

	P0	…	Pi	…	Pj	…	Pn
P0			c0i		c0 j		c0n
…
Pi	ci0 0				cij		cin
…
Pj	c j 0 0		c ji				c jn
…
Pn	cn0 0		cni 0		cnj 0

108

Пример:

		P1		3			P6
				2
					1		5		6
		4		5
5
											8
						2
							P5
	0									6
					6						0
	9	P2
P0						3				0	P7
					2
	0						0		3	4
				1	3
		7					P4			0
							4
		0				5
				P3
							0

	P0	P1	P2	P3	P4	P5	P6	P7
P0		5	9	7
P1	0		4				3
P2	0	5			2	6	2
P3	0					4		5
P4			1			0		4
P5			3	3	3		6	6
P6		2	1			5		8
P7				0	0	0	0

Общий шаг состоит из трех действий.

1. Отыскивается по таблице новый путь из P0 в Pn .

Сначала отмечаем P0 -й столбец *. Затем отыскиваем в строке P0 все положительные c0i и содержащие их столбцы отмечаем сверху числом 0 (номером вершины P0 )

Т.е. выделили все дуги ( P0 , Pi ), которые могут быть первыми дугами различных путей из P0 в Pn .

Просматриваем затем строки, имеющие те же номера, что и отмеченные столбцы.

109

В каждой такой строке (например Pi ) отыскиваем все неотрицательные cij , расположенные в неотмеченных столбцах, и отмечаем эти столбцы

номером рассматриваемой строки (например i ).

Этим самым будут выделены дуги ( Pi , Pj ) с положительной пропу-

скной способностью, которые могут служить вторыми дугами различных путей из P0 в Pn , т.е. уже выделены ( P0 , Pi ) и ( Pi , Pj ).

Продолжаем аналогичный просмотр строк с номерами отмеченных столбцов. Процесс оканчивается, если:

а) Отмечен Pn -й столбец, т.е. удалось выделить дугу ( Pk , Pn ) с ckn >0, которая служит последней дугой некоторого пути из P0 в Pn .

б) Просмотрены все строки и нельзя отметить новых столбцов (т.е. в неотмеченных столбцах нет cij > 0), это означает отсутствие пути из P0 в

Pn , все дуги которого обладают положительными пропускными способностями (Алгоритм закончен).

В случае (а) искомый новый путь из P0 в Pn , начиная от Pn , отыскиваем следующим образом. Пусть столбец Pn был отмечен номером k, т.е. предшествующая вершина в пути, соединяющем P0 с Pn , – Pk . (Столбец Pn был отмечен при просмотре строки Pk ). Число ckn > 0 помечаем знаком

“–“ ( c ). Число cnk , расположенное симметрично к диагонали, помечаем

kn

знаком “+” ( c ). Так как рассматривалась P -я строка, значит перед этим
n k			k
был отмечен столбец Pk	номером l (например). По столбцу Pk двигаемся
вверх до P -й строки. c	lk	отмечаем “–“ ( c	), а c	kl	знаком “+”. Этот про-
l		lk

цесс продолжаем до тех пор, пока не придем к P0 -й строке и не отметим элемент этой строки и соответствующий симметричный элемент.

2. Определяется пропускная способность найденного пути

min{ c }.

ij

3. Вычисляются новые пропускные способности дуг найденного

пути и симметричных с ними

c ,	c c		,
ij	ij	ij
c ,	c c .
ij	ij	ij

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

Величина представляет собой пропускную способность найденного пути. Если дуга ( Pi , Pj ) входила в предыдущий путь, то по ней уже про-

110