Транспортные задачи (стр. 4 )

Аналогом цикла пересчета является увеличивающая цепь. Это цепь, соединяющая исток и сток, все дуги которой допустимые. Дуга является допустимой увеличивающей, если ее направление совпадает с направлением потока и поток на ней меньше пропускной способности, то есть xij<dij. Дуга считается допустимой уменьшающей, если направление дуги противоположно потоку и xij >0.

На увеличивающей дуге поток может возрасти на величину qij=dij-xij, а на уменьшающей дуге возможно снижение потока, равное qij=xij. Следовательно, максимальное допустимое изменение величины потока по увеличивающей цепи определяется как минимальное из возможных:

q0= (5.38)

Таким образом, максимальный поток сети может быть определен по следующему алгоритму.

1.  Задать начальную величину потока, обеспечиваемую потоками дуг при выполнении условий (5.35)-(5.37).

Примечание. Очевидно, что в качестве начального всегда можно взять нулевой поток.

2.  Построить увеличивающую цепь. Если построить невозможно, то решение завершено.

3.  По формуле (5.38) вычислить q0.

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

Пример 5.6. Определить максимальный поток сети на рис. 5.8. Пропускные способности дуг показаны у стрелок перед косой чертой.

Задаем начальный поток. Значения начальных потоков дуг даны за косой чертой, они удовлетворяют условиям задачи. Величина потока сети Z(0)=7.

Первая итерация.

Строим увеличивающую цепь. Она показана на рис. 5.8 утолщенными линиями. Определяем приращение потока: q0 = min(7-3, 5-1, 6-4)=2. Увеличиваем потоки дуг цепи на 2 (рис. 5.9). Z(1)= Z(0) + q0=7+2=9.

Вторая итерация.

Строим увеличивающую цепь {t,1; 1,4; 4,s} (рис. 5.9). q0 = min(7-5, 3-2, 5-1)=1.Увеличиваем потоки по дугам цепи на q0 (рис. 5.10). Z(2)= Z(1) + q0 = 9+1=10.

Третья итерация.

Новая цепь состоит из увеличивающих дуг t,3 и 4,s и уменьшающей дуги 4,3 (рис. 5.10). q0 = min(4-2, 1, 5-2)=1. Изменяем потоки: на дугах t,3 и 4,s увеличиваем, а на дуге 4,3 уменьшаем на величину q0. Тогда получаем Z(3)= Z(2) + q0 = 10+1=11 (рис. 5.11).

Так как увеличивающую цепь построить нельзя, последнее решение является оптимальным. Максимальный поток сети равен 11.

Минимальный разрез рассмотренной сети соответствует множеству вершин А={t,1,2,3,5,6}, то есть P(A)={1,4; 5,s; 6,s}. Его пропускная способность d(A)=d14+d5s+d6s=3+2+6=11 равна величине максимального потока, что согласно теореме Форда-Фалкерсона также является признаком оптимальности найденного решения.

5.7. Задания для самостоятельной работы

I. Следующие Т-задачи решить методом потенциалов.

№1. №2.

bj ai	10	20	20	10		bj ai	80	30	50	40
10	10	15	15	8		70	8	7	4	7
20	40	10	30	5		40	3	5	6	4
10	35	25	40	10		20	9	2	5	3

№3. №4.

bj ai	30	25	18	20		bj ai	20	60	55	45
40	1	2	6	4		45	2	5	3	4
30	3	1	3	2		35	6	1	2	5
20	5	7	5	1		70	3	4	3	8

№5. №6.

bj ai	120	40	60	80		bj ai	20	18	44	75
180	2	3	4	3		40	1	7	2	5
60	5	3	1	2		30	3	8	4	1
80	2	1	4	2		50	6	3	5	3

№7. №8.

bj ai	10	40	20	60		bj ai	15	40	20	50
30	2	7	3	6		48	4	7	2	5
70	9	4	5	7		25	3	5	8	6
50	5	7	6	2		30	6	10	9	7

№9. №10.

bj ai	2	3	3	16		bj ai	10	2	30	40
68	18	2	9	7		45	5	4	0	5
55	30	4	1	55		20	3	5	3	0
40	6	4	8	3		35	0	6	7	6

№11. №12.