4 Маршрутизация перевозок. Поиск оптимальных маршрутов в сетях

Задание

Для транспортной сети с n = 10 пунктами, заданной графом на рис. 4.1 (N – последняя цифра номера варианта), выполнить следующее:

Рис. 4.1

1) построить матрицу смежности для графа транспортной сети;

2) построить кратчайший путь от пункта (вершины) Z до вершины W, вариант определяется по числу букв в фамилии студента (Z, W) по табл. 4.1;

Таблица 4.1

Число букв в фамилии
5	6	7	8	9	10	11	12
(2,9)	(1,8)	(2,8)	(5,6)	(4,10)	(1,6)	(3,10)	(1,9)

3) найти кратчайший путь от пункта (вершины) Z (из табл. 4.1) до всех остальных пунктов (вершин);

4) построить сеть минимальной дины (минимальное дерево) с начальной вершиной в W (из табл. 4.1);

5) найти максимальный поток от пункта 1 до пункта 10 для графа, представленного на рис 4.2. (S – Число букв в фамилии студента).

Рис. 4.2

Определить минимальный разрез графа;

6) решить задачу коммивояжера для транспортной сети, представленной на рис. 4.3. (N – последняя цифра в номере варианта, F – число букв в имени студента, S – число букв в фамилии студента).

Рис. 4.3

Методические указания по выполнению задания

1 Пусть транспортная сеть задана схемой (рис. 4.4).

Рис. 4.4

n = 7 – число вершин.

Матрица смежности n * n:

.

2 Найдем кратчайший пункт от вершины 2 до вершины 7 (рис. 4.5).

Рис. 4.5

3 Помечаем вершину 2 пометкой (0, 2) и изменяем пометки вершин, связанных с вершиной 2:

1: (6,2); 4: (7,2); 3: (15, 2); 6: (16,2).

4 Отмечаем вершину 2 как помеченную и просмотренную (рис. 4.6).

5 Выбираем непросмотренную вершину с пометкой с минимальным весом: эта вершина 1.

6 Просматриваем все вершины, связанные с 1, и пересматриваем их пометки

7 Сравниваем текущий вес вершины 7 с новым вариантом с включением пути с вершиной 1, т.е. 6 +9 = 15; поскольку 15 > 7, пометку вершины 4 оставляем без изменения.

Отмечаем вершину 1 как помеченную и просмотренную (рис 4.6).

Рис. 4.6

8 Выбираем непросмотренную вершину с пометкой с минимальным весом: эта вершина 4.

9 Просматриваем все вершины, связанные с 4, и пересматриваем их пометки

10 Сравниваем текущий вес вершины 15 с новым вариантом пути с включением вершины 4, т.е. 7 + 10 = 17; поскольку 17 > 15, поэтому пометка вершины 3 оставляем без изменения.

11 Определяем пометку вершины 5: 7 + 7=14; поэтому пометка вершины 5 будет (14,4). (рис. 4.7.)

Отмечаем вершину 4 как помеченную и просмотренную (рис. 4.7).

Рис. 4.7

Рис. 4.8

12 Выбираем непросмотренную вершину с пометкой с минимальным весом: эта вершина 5.

13 Просматриваем все вершины, связанные с 5, и пересматриваем их пометки

14 Сравниваем текущий вес вершины 15 с новым вариантом пути с включением вершины 4, т.е. 14 + 8 = 22; поскольку 22 > 15, пометку вершины 3 оставляем без изменения.

15 Определяем пометку вершины 7: 14 + 15 = 29; поэтому пометка вершины 7 будет (29,5).

16 Отмечаем вершину 5 как помеченную и просмотренную (рис 4.9).

Рис. 4.9

17 Выбираем непросмотренную вершину с пометкой с минимальным весом: эта вершина 3.

18 Просматриваем все вершины, связанные с 3, и пересматриваем их пометки.

19 Сравниваем текущий вес вершины 16 с новым вариантом пути с включением вершины 3, т.е. 15 + 8= 23; поскольку 23 > 16, пометку вершины 6 оставляем без изменения.

20 Отмечаем вершину 3 как помеченную и просмотренную (рис 4.10).

Рис. 4.10

21 Выбираем непросмотренную вершину с пометкой с минимальным весом: эта вершина 6.

22 Просматриваем все вершины, связанные с 6 и пересматриваем их пометки.

23 Сравниваем текущий вес вершины 29 с новым вариантом пути с включением вершины 6, т.е. 16 + 9=25; поскольку 25 > 29, пометка вершины 7 будет (25,6).

24 Отмечаем вершину 6 как помеченную и просмотренную.

Рис. 4.11

25 Помечаем последнюю вершину 7. (рис. 4.11).

26 Восстанавливаем в обратном порядке кратчайший путь от вершины 7 к вершине 2.: 7 – 6 – 2. Кратчайшее расстояние равно 25 ед.

27 Находим кратчайший путь из пункта 2 в остальные пункты (вершины) графа;

1) 2 – 1; кратчайшее расстояние равно 6 ед.

2) 2 – 3; кратчайшее расстояние равно 15 ед.

3) 2 – 4; кратчайшее расстояние равно 7 ед.

4) 2 – 4 – 5; кратчайшее расстояние равно 14 ед.

5) 2 – 6; кратчайшее расстояние равно 16 ед.

6) 2 – 6 – 7. кратчайшее расстояние равно 25 ед.

28 Построим сеть минимальной длины (минимальное дерево) с начальной вершиной 2.

Результат имеет следующий вид (рис. 4.12).

Рис. 4.12

Найти максимальный поток от пункта 1 до пункта 7 для графа, представленного на рис 4.13.

Рис. 4.13

Находим цепь между вершинами 1 и 7 с ненулевой пропускной способностью (все дуги, входящие в цепь, имеют ненулевую пропускную способность).

Пусть эта цепь 1 – 3 – 2 – 5 – 4 – 7. Пропускная способность цепи равна 5 (минимальный вес дуги с в цепи), S = 5. Уменьшаем пропускные способности дуг цепи на 5 (Рис 4.14).

Рис. 4.14

Находим очередную цепь между вершинами 1 и 7 с ненулевой пропускной способностью.

Пусть эта цепь 1 – 3 – 6 – 7. Пропускная способность цепи равна 10 (минимальный вес дуги с в цепи), S = 5 + 10 = 15. Уменьшаем пропускные способности дуг цепи на 10 (рис 4.15).

Рис 4.15

Очередной цепи между вершинами 1 и 7 с ненулевой пропускной способностью нет.

Максимальная пропускная способность равна 15.

Определим минимальный разрез графа.

Поскольку в минимальный разрез входят дуги с нулевыми весами, минимальный разрез {(3,6); (4,7)}. Вес минимального разреза 5 + 10= 15 ед.

Решим задачу коммивояжера для транспортной сети, представленной на рис. 4.16.

Рис 4.16

Определим матрицу связей между вершинами:

A = .

Находим минимальный вес в каждой строке:

A = .

Вычитаем минимальный вес от каждого элемента в строке.

Находим минимальный вес в каждом столбце:

A = .

Вычитаем минимальный вес от каждого элемента в столбце:

A = .

Нижняя оценка всех гамильтоновых контуров равна

F(G₀) = 6 + 9 + 7 + 4 + 9 + 2 + 14 = 51.

Выбираем дугу для разбиения. Определяем минимальный вес в каждой строке для нулевых весов без учета веса данной (нулевой) дуги. Эти величины записаны верхними индексами.

A =

Выбираем дугу с максимальной дополнительной оценкой. Из полученных дуг эта дуга (5,4). Исходное множество G₀ разбиваем на два подмножества: в первый включены гамильтоновы контуры, содержащие дугу (5,4), во втором эта дуга исключена . G₀=G₁G₂, G₁G₂=. G₁={(5,4)}; G₂={ }.

Для первого подмножества имеем матрицу с исключенными 5-й строкой и 4-м столбцом и весом дуги (4,5), равным , для второго подмножества та же матрица с весом дуги (5,4), равным . Определяем нижние оценки для гамильтоновых контуров в подмножествах G₁ и G₂,:

G₁ : A =

F(G₁) = 51

G₂ : A = ,

A = ,

A = ,

F(G₂) = 51 + 10 + 5 = 66.

Для очередного разбиения выбираем подмножество с минимальной оценкой : G₁.

Для разбиения выбираем дугу (4,3). Множество G₁ разбиваем на два подмножества: в первый включены гамильтоновы контуры, содержащие дугу (4,3), во втором эта дуга исключена . G₁ = G₃G₄, G₃G₄ = . G₃ = {(5,4), (4,3)}; G₄ = {(5,4), }.

Проведем изменения в матрице весов:

G₃ : A = , F(G₃) = 51.

G₄ : A = , A = , A = ,

F(G₄) = 66 + 9 = 75.

Для очередного разбиения выбираем подмножество с минимальной оценкой : G₃.

Для разбиения выбираем дугу (1,5). Множество G₃ разбиваем на два подмножества: в первый включены гамильтоновы контуры, содержащие дугу (1,5), во втором эта дуга исключена . G₃ = G₅G₆, G₅G₆ = . G₅ = {(5,4), (4,3), (1,5)}; G₄ = {(5,4), (4,3), }.

Проведем изменения в матрице весов:

G₅ : A = , A = , A = ,

F(G₅) = 51.

G₆ : A = , A = , F(G₆) = .

Для очередного разбиения выбираем подмножество с минимальной оценкой : G₅.

Для разбиения выбираем дугу (2,1). Множество G₅ разбиваем на два подмножества: в первый включены гамильтоновы контуры, содержащие дугу (2,1), во втором эта дуга исключена . G₅ = G₇G₈, G₇G₈ = . G₇ = {(2,1), (5,4), (4,3), (1,5)}; G₄ = { , (5,4), (4,3), (1,5)}.

Проведем изменения в матрице весов:

G₇ : A =

В G₇ осталась единственная нерассмотренная дуга (3,2) с весом 0.

F(G₇) = 51. Гамильтонов контур: (1,5) – (5,4) – (4,3) – (3,2) – (2,1). Длина контура равна 51. Нижние оценки остальных подмножеств больше чем 51, поэтому их можно исключить из рассмотрения.

Таким образом, контур минимальной длины, проходящий один раз через каждую вершину, имеет вид

(1,5) – (5,4) – (4,3) – (3,2) – (2,1).

Длина контура 51 ед.