назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [ 82 ] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [248] [249] [250] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [267] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293]


82

Этап 4. Полагаем k = 4, ведущие строка и столбец в матрице D3 выделены. Получаем новые матрицы Dt и S4.

Da 3

Этап 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 свободные переменные.

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [ 82 ] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [248] [249] [250] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [267] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293]