Задание №3
Тема: Графы
Задача о максимальном потоке
Имеется трубопроводная сеть с заданной Sij пропускной способностью каждого участка из i-го узла в j-й узел и мощностью насосной станции, расположенной в узле. Необходимо рассчитать максимальную пропускную способность сети из начального узла в конечный узел.
aисток aсток
Пропускная способность Sij , тыс. тонн
S12 = 4
S13 = 7
S14 = 8
S23 = 3
S25 = 5
S34 = 8
S35 = 9
S45 = 9
Обозначим за х1, 2, …, 8 перевозки по маршрутам 12, 13, 14, 23, 25, 34, 35, 45 соответственно, а за х9 – пропускную способность конечного узла сети.
Сумма входящих в каждый узел потоков равна сумме выходящих, причем интенсивность каждого потока не может превышать пропускную способность своего участка сети. Поэтому система условий-ограничений выглядит следующим образом.
х9 - х1 – х2 – х3 = 0 (1)
х1 – х4 – х5 = 0 (2)
х2 + х4 – х6 – х7 = 0 (3)
х3 + х6 – х8 = 0 (4)
х5 + х7 + х8 – х9 = 0 (5)
х1 £ 4 (6)
х2 £ 7 (7)
х3 £ 8 (8)
х4 £ 3 (9)
х5 £ 5 (10)
х6 £ 8 (11)
х7 £ 9 (12)
х8 £ 9 (13)
Функция цели: х9 max
Таблица 3.1
Исходная матрица
№
х1
х2
х3
х4
х5
х6
х7
х8
х9
Знак
Св.чл.
1
-1
0
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34