Этап 4. Полагаем k = 4, ведущие строка и столбец в матрице D3 выделены. Получаем новые матрицы Dt и S4.
Этап 5. Полагаем k - 5, ведущие строка и столбец в матрице Б4 выделены.
Никаких действий на этом этапе не выполняем; вычисления закончены.
Конечные матрицы £>4 и St содержат всю информацию, необходимую для определения кратчайших путей между любыми двумя узлами сети. Например, кратчайшее расстояние между узлами 1 и 5 равно diS = 12.
Для определения соответствующих маршрутов напомним, что сегмент маршрута (i,j) состоит из ребра (/, /) только тогда, когда stj = j. В противном случае узлы i и j связаны, по крайней мере, через один промежуточный узел. Например, поскольку s,5 = 4 и siS = 5, сначала кратчайший маршрут между узлами 1 и 5 будет иметь вид 1 -» 4 -» 5. Но так как д-,4 ф 4, узлы 1 и 4 в определяемом пути не связаны одним ребром (но в исходной сети они могут быть связаны непосредственно). Далее следует определить промежуточный узел (узлы) между первым и четвертым узлами. Имеем su - 2 и s2i = 4, поэтому маршрут 1 -» 4 заменяем 1 -» 2 -> 4. Поскольку д-,2 = 2 и$24 = 4, других промежуточных узлов нет. Комбинируя определенные сегменты маршрута, окончательно получаем следующий кратчайший путь от узла 1 до узла 5:1-»2-»4-»5. Длина этого пути равна 12 милям.
Программа TORA также может применять алгоритм Флойда для решения сетевых задач. Для этого в меню SOLVE/MODIFY выберите команду Solve problem Iterations Floyds algoritm (Алгоритм Флойда). На рис. 6.22 показано выходное окно TORA с решением задачи из примера 6.3.5 (файл ch6ToraFloydEx6-3-5.txt).
УПРАЖНЕНИЯ 6.3.3
1. В задаче из примера 6.3.5 определите кратчайшие пути между следующими парами узлов.
a) От узла 5 к узлу 1.
b) От узла 3 к узлу 5.
c) От узла 5 к узлу 3.
d) От узла 5 к узлу 2.
2. Примените алгоритм Флойда к сети, показанной на рис. 6.23. Заметьте, что ребра (7, 6) и (6, 4) ориентированы. Определите кратчайшие пути между следующими парами узлов.
- TORA D:\Work\ToraFiles\ch6ToraFloydEx6 ЗЪ.Ы
то ид орт, Ли i»i».mh- ид -и \ш ripii. Аичпаш на
NETWORK MODELS
FLOYu S SHORTEST ROUTE ALGuRITHM Select Output Option
| | | | | | | |
| | | | | n5 Hi | hz *i | n4 n5 |
| | | 10,00 | mnn»y; | | | 4 5 |
| 1 зло | | | 5,00 | infinity H 1 | | 4 5 |
| | | | 5.00 | 15,00 H 1 | | |
| | 5,oo | «,00 | |
| Zu ~J | MiMyl | If IV | 4,00 | H№ 1 | | « |
tar 1 | | | | | | | |
| | | | | n5 hi | n2 n3 | n4 hs |
i°uc. 6.22. Решение задачи из примера 6.3.5
a) От узла 1 к узлу 7.
b) От узла 7 к узлу 1.
c) От узла 6 к узлу 7.
Рис. 6.23. Сеть для задачи из упражнения 2
3. Телефонная компания обслуживает шесть удаленных друг от друга районов, которые связаны сетью, показанной на рис. 6.24. Расстояния на схеме сети указаны в милях. Компании необходимо определить наиболее эффективные маршруты пересылки сообщений между любыми двумя районами.
Рис. 6.24. Сеть для задачи из упражнения 3
6.3.3. Формализация задачи поиска кратчайшего пути как задачи ЛП
В этом разделе рассмотрим две формализации задачи определения кратчайшего пути как задачи линейного программирования. Эти формализации достаточно общие в том смысле, что позволяют находить кратчайшие пути между двумя любыми узлами сети (как в алгоритме Флойда).
Пусть сеть состоит из п узлов и нужно найти кратчайший путь между некоторыми узлами s и t этой сети.
Формализация 1. В этой формализации предполагается, что в узел s входит одна единица внешнего потока и этот поток выходит через узел t сети. Обозначим
х1} - величина потока, проходящего по дуге (£, у), су - длина дуги (г, у).
Поскольку только одна единица потока может пройти через любую дугу в каждый момент времени, переменные хц должны быть двоичными (т.е. они могут принимать только значения 0 или 1). В этих обозначениях целевая функция запишется как
минимизировать ХСЛ
по всем существующим яутам (l,/)
Для каждого узла определяется только одно ограничение, задающее баланс потока, проходящего через данный узел:
общий входной поток = общий выходной поток.
Формализация 2. Эта формализация фактически определяет двойственную задачу к прямой задаче, формализованной первым способом. Поскольку количество ограничений в первой формализации равно количеству узлов, двойственная задача будет иметь столько же переменных, сколько узлов в сети. Эти переменные будут свободными (т.е. могут принимать как положительные, так и отрицательные значения), так как в прямой задаче все ограничения выражаются в виде равенств.
Пусть
у. - переменная двойственной задачи, ассоциированная с узлом у.
Считая узлы s и t начальным и конечным узлами сети, двойственная задача запишется следующим образом.
Максимизировать z = у, - уг
при ограничениях
!/.-!/,< сц для всех возможных пар / и у, все yt свободные переменные.