МО-Лекции

	ai											b j
					7			13					9				11
	10				8					10					8		2
					×			×					×				10
	18				12						7				3		1
					×			13					5
	12				5					4					1		6
					7								4				1
	ai											b j
					7			13					9				11
	10				8					10					8		2
					×			×					×			10
	18				12					7					3		1
					×			8					9				1
	12				5					4					1		6
					7			5
								tmin		= 7
Пример 2
ai												b j
			30			80						20			30			90
120					6			8				2			3			5
30					8			5				6			6			2
40					2			4				7			4			8
60					3			4				2			1			4
ai												b j
			30			80						20			30			90
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

130

КОНТРОЛЬНЫЕ ВОПРОСЫ

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

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

12.ЗАДАЧА О МАКСИМАЛЬНОМ ПОТОКЕ

ВТРАНСПОРТНОЙ СЕТИ

12.1. ПОСТАНОВКА ЗАДАЧИ

Определение 1. Транспортной сетью называется конечный граф

G , состоящий из ( n 1 ) вершин P ,	P ,…,	P	и из дуг ( P ,	P ), соеди-
0	1	n	i	j

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

в соответствие число cij

0, называемое пропускной способностью

дуги ( P ,

P ).

i

j

Вершина P

называется входом сети, а P – выходом транспортной

0

n

сети.

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

дуга ( P ,

P ), то входит и дуга ( P

, P ).

i

j

j

i

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

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

Например (рис. 12.1): c

= 0, если

P

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

ij

i

j

По путям

( P ,

P ,

P

,…,

P

,

P ), составленным из дуг сети

0

i1

i2

ik

n

( P

, P ), ( P

,

P

), …, ( P

, P ), направляется транспорт из P

в P .

0

i1

i1

i2

ik

n

0

n

Потоком

x

по дуге ( P ,

P ) ( i, j

0,..., n , i j ) называется коли-

ij

i

j

чество вещества, проходящее через эту дугу в единицу времени. Потоком по сети или просто потоком будем называть совокупность

потоков { xij } по всем дугам сети.

Потоки должны удовлетворять следующим ограничениям:

0 xij cij ( i, j 0,..., n , i j ),

(1)

131

	P1			3		P5
6			1	5
2				2	2		3
			2
4				3				7
2							P4
P0
1	P2			7					P6
								8
						8
						4
	2
				P3
Рис. 12.1. Пример транспортной сети
n 1			n
xik				xkj , ( k		1,...n 1 ).			(2)
i 0			j 1

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

P и P ).

0 n

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

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

из P0 , совпадает с общим количеством вещества

в Pn , т. е.

n 1	n
xin	x0 j Q .
i 0	j 1

n

x0 j , вытекающего

j 1

n 1

xin , притекающего

i 0

(3)

132

Линейная форма Q называется потоком по сети.

Задача о максимальном потоке в транспортной сети заключается в отыскании такого решения x*ij ( i, j 0, n ) системы (1) – (2), т. е. такого

допустимого потока, который максимизирует Q . Это решение x*ij

называется максимальным потоком сети. Рассмотрим такой простейший пример.

P1

1

P4

2

2

2

P0

2

P2

P5

2

P7

				2
P3
	1	P6
Рис. 12.2. Пример простейшей транспортной сети
Найти максимальный поток из		P в		P . Толстые дуги насыще-
		0		7
	n
ны, т. е. xij = cij , полный поток		x0 j		5 , а максимальный поток
	j	1

равен 6.

Разобьем множество всех вершин G на два подмножества U и V

так, что P U и	P V . Сечением (U , V ) сети G		назовем совокуп-
0		n
ность всех дуг ( P ,		P ), концы которых принадлежат разным подмно-
	i	j

жествам.

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

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

133

		C(U , V )	cij .
		Pi	U
		Pj	V
Любой путь из P	в P	непременно содержит хоть одну дугу сече-
0	n

ния (U , V ), которая начинается в U и заканчивается в V . Ясно, что пропускная способность пути не превышает пропускной способности

каждой его дуги. Поэтому величина любого потока из P	в P , которая
0	n

является суммарной величиной пропускной способности всех путей из

P в	P , не может превысить пропускной способности любого сечения
0	n
(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	не заполняем.

134

Начальная таблица будет выглядеть следующим образом:

P0

…

P

…

P

…

P

i

j

n

P0

c

c0 j

c0n

0i

(4)

…

P

c

0

c

c

i

i0

ij

in

…

Pj

c j0

0

c ji

c jn

…

Pn

cn0

0

cni

0

cnj

0

Будем рассматривать алгоритм на примере следующей транспорт-

ной сети (рис. 12.3)

P1

P6

3

5

4

5

5

6

8

0

6

0

P0

9

P2

3

0

P7

0

0

3

4

3

0

4

5

0

Рис. 12.3. Транспортная сеть

135

Построенная начальная таблица примет вид

	P0	P	P	P	P	P	P	P
		1	2	3	4	5	6	7
P0		5	9	7
P	0		4				3
1
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. Отыскивается по таблице новый путь из P	в P .
0	n
Сначала отмечаем P -й столбец *. Затем отыскиваем в строке P
0	0

все положительные c0i и содержащие их столбцы отмечаем сверху

числом 0 (номером вершины P ), т. е. выделили все дуги ( P ,		P ), ко-
0	0	i
торые могут быть первыми дугами различных путей из P	в P .
0	n

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

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

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

ных путей из P		в P , т. е. уже выделены ( P ,		P ) и ( P ,		P ).
	0	n	0	i	i	j
	Продолжаем аналогичный просмотр строк с номерами отмеченных
столбцов. Процесс оканчивается, если:
	а) отмечен Pn -й столбец, т. е.		удалось выделить дугу ( Pk ,				Pn ) с
c	> 0, которая служит последней дугой некоторого пути из P в						P ;
kn						0	n

136

б) просмотрены все строки и		нельзя		отметить новых		столбцов
(т. е. в неотмеченных столбцах нет		cij >	0),		это означает отсутствие
пути из P	в P , все дуги которого обладают положительными пропу-
0	n
скными способностями (алгоритм закончен).
В случае (а) искомый новый путь из P				в	P , начиная от	P , оты-
		0			n	n

скиваем следующим образом. Пусть столбец Pn был отмечен номером

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

помечаем знаком « – » ckn . Число cnk , расположенное симметрично к диагонали, помечаем знаком « + » cnk . Так как рассматривалась Pk -я строка, значит, перед этим был отмечен столбец Pk номером на-

пример,	l . По столбцу Pk двигаемся вверх до Pl -й строки. clk отмеча-
ем « – »	clk , а ckl знаком « + ». Этот процесс продолжаем до тех пор,

пока не придем к P - й строке и не отметим элемент этой строки и со-

0

ответствующий симметричный элемент.

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

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

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

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

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

137

ственно, что в этом пути по ней нельзя пропустить больше чем cij –

вещества в единицу времени.

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

P	в P .
0	n
	По этой таблице легко определить любую дугу, по которой проте-

кает поток. Пропускная способность дуг, по которым протекает поток, уменьшилась по сравнению с cij на величину xij , а пропускная спо-

собность противоположно направленной (симметричной) дуги увеличилась на xij , что свидетельствует об отсутствии потока по ней.

Обозначим через U множество вершин сети G , которые достижи-

мы из

P по некоторому пути в последней таблице,

а множество ос-

0

тальных вершин через V . Тогда увидим, что все дуги сечения ( U , V ),

направленные из U

в V , загружены полностью до пропускных спо-

собностей (т. е.

x

для

дуги ( P ,

P ), такой что

P

U ,

P

V ,

ij

i

j

i

j

x

c

), а дуги (

P ,

P ) противоположного направления, идущие из V

ij

ij

j

i

в

U , в построенном потоке не используются (т. е.

x

= 0,

P

U ,

ij

i

Pj

V ), так что величина потока равна

Q

xij

x ji

cij C(U , V ),

Pi

U

Pi

U

Pi

U

Pj

V

Pj

V

Pj

V

т. е. построенный поток максимален, а (U , V ) – сечение с минималь-

ной пропускной способностью.

Для

определения полученного

максимального

потока

x* ,

ij

i, j 0, n , вычитаем из всех элементов начальной таблицы (4) соответствующие элементы таблицы, полученной на последнем шаге. Положительные значения найденных разностей дают величины потоков xij*

по дугам ( Pi , Pj ), а величина потока в сети вычисляется по следующей формуле:

138

Q	n 1 x*in	n	x*0 j .
	i 0	j	1

Построим максимальный поток для нашего примера.

			*	0		0	0	2	2	1	3
			P0	P		P	P	P	P	P	P
				1		2	3	4	5	6	7
P				5		9	7 –
0
P			0			4				3
1
P2			0	5				2	6	2
P			0 +						4		5 –
3
P4						1			0		4
P5						3	3	3		6	6
P6				2		1			5		8
P							0 +	0	0	0
7
min	{ c		–} = min{7, 5} = 5.
		ij

Путь		1( P	, P		, P ) состоит из дуг ( P								, P ), ( P		, P ).
		0	3		7						0		3	3	7
		*			0	0				0			2		2	1	6
		P0			P		P			P			P		P	P	P
					1		2			3			4		5	6	7
P					5 –		9			2
0
P		0 +					4									3 –
1
P2		0			5								2		6	2
P3		5													4		0
P4							1								0		4
P5							3			3			3			6	6
P					2 +		1								5		8 –
6
P										5			0		0	0 +
7
= min{8, 3, 5} = 3;						2(P0, P ,		P ,		P	).
						1		6		7

139