Лабораторная работа № 4
Вариант №9
Студента ИТ 14-1 Красовского Абхая
Транспортные сети
Цель работы – Построение максимального потока в транспортной сети. Упрощение (оптимизация) транспортной сети
Задание
t = ] N/ 10[ = [ 9 / 10 ] = 9.
Решение
Определение максимального потока в сети:
-
Установим нулевой поток в каждой дуге сети.
2.Построим первую прибавляющую цепь(цепь, в которой все прямые дуги имеют поток, меньший за ее пропускную способность, а у обратных дуг поток больше нуля)
Прибавим ко всем потокам дуг 8(минимальная пропускная способность дуг), т.к. все дуги прямые(направлены в сторону t и их поток меньше проп. способн.)
S
12(0) a 8(0)
d 13(0) m
16(0) t 
12(8) 8(8) 13(8) 16(8)
Дуга ad – насыщенная(т.к. ее поток равен пропускной способности ), значит, удаляем ее из этой цепи.
3.Построим вторую прибавляющую цепь
Прибавим ко всем потокам дуг 4, т.к. все дуги прямые.
S
12(8) a
4(0) b
6(0) d
13(8) m
16(8) t 
12(12) 4(4) 6(4) 13(12) 16(12)
Дуга Sa и ab – насыщенные, значит, удаляем их из этой цепи.
4.Построим третью прибавляющую цепь
Прибавим ко всем потокам дуг 1, т.к. все дуги прямые.
S
14(0) b 6(4) d 13(12) m
16(12) t 
14(1) 6(5) 13(13) 16(13)
Дуга dm – насыщенная, значит, удаляем ее из этой цепи.
5.Построим четвертую прибавляющую цепь
Прибавим ко всем потокам дуг 1, т.к. все дуги прямые.
S
14(1) b 6(5)
d 9(0)
f 6(0) m
16(13) t
14(2) 6(6) 9(1) 6(1) 16(14)
Дуга bd – насыщенная, значит, удаляем ее из этой цепи.
6.Построим пятую прибавляющую цепь
Прибавим ко всем потокам дуг 2, т.к. все дуги прямые.
S
14(2) b 17(0)
f 6(1) m 16(14) t
14(4) 17(2) 6(3) 16(16)
Дуга mt – насыщенная, значит, удаляем ее из этой цепи.
7.Построим шестую прибавляющую цепь
Прибавим ко всем потокам дуг 8, т.к. все дуги прямые.
S
14(4) b 17(2)
f 8(0) t
14(12) 17(10) 8(8)
Дуга ft – насыщенная, значит, удаляем ее из этой цепи.
Больше представляющих цепей построить нельзя
8. Определим максимальный поток транспортной сети
Для этого проведем разрез и посчитаем его пропускную способность.
=
10 + 1 - 3 + 16 = 24
Проверим полученный результат, проведя и вычислив проп. способн. других разрезов
B
C(A-A) = 16 + 8 = 24
C(B-B) = 13 + 1 + 10 = 24
C(C-C) = 12 - 4 + 6 + 10 = 24
С(D-D) = 12 + 12 = 24
C(E-E) = 8 + 6 + 10 = 24
…
Модернизация сети
Найдем прибавляющие цепи, в которых есть только одна насыщенная дуга
S
14(12)
b 17(10)
f 8(8)
t
S
14(12)
b 17(10)
f 6(3)
m 16(16)
t
