(Назад)
(Cкачать работу)x4
2
1
4
x5
2
3
6
x6
2
4
12
x7
3
1
10
x8
3
2
12
x9
3
4
18
x10
4
1
8
x11
4
2
10
x12
4
3
4
Сумма входящих и исходящих маршрутов в каждом пункте равна 1. Следовательно, система условий-ограничений выглядит следующим образом:
x1 + x2 + x3 = 1 (1)
x4 + x5 + x6 = 1 (2)
x7 + x8 + x9 = 1 (3)
x10 + x11 + x12 = 1 (4)
x4 + x7 + x10 = 1 (5)
x1 + x8 + x11 = 1 (6)
x2 + x5 + x12 = 1 (7)
x3 + x6 + x9 = 1 (8)
Функция цели: 8x1 + 8x2 + 6x3 + 4x4 + 6x5 + 12x6 + 10x7 + 12x8 + 18x9 + 8x10+ 10x11 + 4x12min
Исходная матрица условий задачи представлена в таблице 2.3.
Таблица 2.3
№ | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | х10 | x11 | x12 | Св.чл. | Зн |
1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | = |
2 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | = |
3 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | = |
4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | = |
5 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | = |
6 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | = |
7 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | = |
8 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | = |
Фц. | 8 | 8 | 6 | 4 | 6 | 12 | 10 | 12 | 18 | 8 | 10 | 4 | min |
x3 = 1
x5 = 1
x7 = 1
x8 = 0
x11 = 1
Это означает, что на графике остаются только пути, соответствующие переменным х3, х5, х7, х11 (14, 23, 31, 42). Функционал равен 12, т. е. время пути будет равно 12 единицам. График при этом выглядит следующим образом. Задание №3
Тема: Графы
Задача о максимальном потоке
Имеется трубопроводная сеть с заданной Sij пропускной способностью каждого участка из i-го узла в j-й узел и мощностью насосной станции, расположенной в узле. Необходимо рассчитать максимальную пропускную способность сети из начального узла в конечный узел. истоксток Пропускная способность Sij , тыс. тонн
S12 = 4
S13 = 7
S14 = 8
S23 = 3
S25 = 5
S34 = 8
S35 = 9
S45 = 9
Математическая модельОбозначим за х1, 2, …, 8 перевозки по
Похожие работы
Интересная статья: Быстрое написание курсовой работы