Итерация 1 Итерация 2

Итерация 3 Итерация 4

Итерация 5 Итерация 6

(Минимальное остовное дерево)

Рис. 6.5. Последовательные итерации выполнения алгоритма построения минимального остовного дерева

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

соединяющего его с узлом 1). Поэтому/ = 2 и С, = {1, 2}, С2 = {3, 4, 5, 6}.

Решение в виде минимального остовного дерева получено на 6-й итерации (рис. 6.5). Минимальная длина кабеля для построения такой сети равна 1 + 3 + 4 + 4- 3 + 5 = 16 милям.

Программа TORA может находить минимальное остовное дерево. Для этого из меню Main menu выберите команду Network modelsOMinimal spanning tree (Сетевые моделиОМинимальное остовное дерево). Далее из меню SOLVE/MODIFY выберите команду Solve problemOGo to output screen (Решить задачу=>Перейти к выходному окну). В выходном окне щелкните на кнопке Starting node (Начальный узел) и затем на кнопке Next iteration (Следующя итерация) или All iterations (Все итерации) для получения решения. Чтобы получить решение с новым начальным узлом, щелкните на кнопке Starting node. На рис. 6.6 показаны выходные результаты для задачи из примера 6.2.1 (файл ch6ToraMinSpanEx6-2-l.txt).

4Mb \WokUwattte*Vh6we*Ainai Qt t / i Ut

NETWORK MODEL

Рис. 6.6. Построенное минимальное остовное дерево для задачи из примера 6.2.1 УПРАЖНЕНИЯ 6.2

1. Решите задачу из примера 6.2.1, начиная с узла 5 (вместо узла 1), и убедитесь, что будет получено то же самое решение.

2. Найдите минимальное остовное дерево для сети из примера 6.2.1 при выполнении каждого из следующих условий в отдельности.

a) Узлы 5 и 6 связаны 2-мильным кабелем.

b) Узлы 2 и 5 не связаны.

c) Узлы 2 и 6 связаны 4-мильным кабелем.

d) Узлы 1 и 2 связаны кабелем длиной 8 миль.

e) Узлы 3 и 5 связаны кабелем длиной 2 мили.

f) Узел 2 не связан непосредственно с узлами 3 и 5.

3. В модульных перевозках груженые трейлерные платформы перевозятся по железной дороге между специальными перевалочными железнодорожными терминалами, где платформы снова присоединяются к трейлерам и далее следуют к потребителям по автомобильным дорогам. На рис. 6.7 показаны основные железнодорожные терминалы Соединенных Штатов и существующие железнодорожные пути между ними. Выделите сегменты железных дорог так, чтобы связать все железнодорожные терминалы и минимизировать суммарную стоимость перевозок трейлерных платформ (стоимость перевозок пропорциональна длине железнодорожных путей).

Рис. 6.7. Сеть для задачи из упражнения 3

4. На рис. 6.8 показаны расстояния между платформами, добывающими газ в открытом море, и приемным пунктом, расположенным на берегу. Поскольку платформа 1 ближе остальных к берегу, она оснащена необходимым оборудованием для перекачки газа от остальных платформ к приемному пункту. Спроектируйте сеть трубопроводов минимальной длины, соединяющую приемный пункт со всеми добывающими платформами.

Приемный пункт

Рис. 6.8. Сеть для задачи из упражнения 4