Программа 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
5. Предположим, что в предыдущей задаче (рис. 6.8) все добывающие платформы разбиты на две группы в зависимости от давления газа в скважинах: к группе с высоким давлением газа относятся платформы 2, 3, 4 и 6, с низким давлением - 5, 7, 8 и 9. Из-за разницы в давлении газопроводы от платформ разных групп нельзя соединять между собой. В то же время газопроводы от этих групп могут подсоединяться к приемному пункту через платформу 1. Определите минимальную сеть трубопроводов для данной ситуации.
6. Компания производит 15 типов изделий на 10 станках. Она планирует сгруппировать станки так, чтобы минимизировать "несходство" операций, выполняемых на каждой группе станков. Мерой "несходства" между станками i и у служит величина d,., вычисляемая по формуле
где пц - количество изделий, обрабатываемых как на станке i, так и на станке у, тц - количество изделий, обрабатываемых только на станке i или только на станке у.
В следующей таблице показано, изделия каких типов на каких станках обрабатываются.
Станок | Типы изделий |
| |
| 2, 3, 7, 8, 9, 12, 13, 15 |
| 3, 5, 10, 14 |
| 2, 7, 8,11,12,13 |
| 3, 5, 10, 11, 14 |
| 1,4, 5, 9, 10 |
| 2, 5, 7, 9, 10 |
| 3, 4, 15 |
| 4, 10 |
| 3, 8, 10, 14, 15 |
a) Сформулируйте данную задачу как сетевую.
b) Покажите, что разбить множество станков на группы можно, решив задачу нахождения минимального остовного дерева.
c) Решите данную задачу для разбиения станков на две и три группы.
6.3. ЗАДАЧА ПОИСКА КРАТЧАЙШЕГО ПУТИ
Данная задача состоит в определении в транспортной сети кратчайшего пути между заданными исходным пунктом и пунктом назначения. Такую модель можно использовать для описания разнообразных ситуаций, как показано в следующем разделе.