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


[Старт] [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]


83

Пример 6.3.6

Рассмотрим сеть из примера 6.3.4. Предположим, что необходимо определить кратчайший путь из узла 1 в узел 2. Таким образом, здесь s = 1 и t = 2. На рис. 6.25 показано, как одна единица потока входит в узел 1 и выходит из узла 2.

Рис. 6.25. Входной и выходной потоки

Первая формализация дает следующую задачу ЛП.

Минимизировать z =

Узел 1

= -1

Узел 2

Узел 3

Узел 4

Узел 5

Ограничения представляют балансы потоков, протекающих через каждый узел. Например, в узле 2 баланс потоков "входной поток = выходной поток" выражается как равенство х12 + х42 - 1 + х23. Отметим, что одно из ограничений всегда будет излишним. Например, сумма четырех последних ограничений дает равенство х12 + хп = 1, которое совпадает с первым ограничением.

Оптимальным решением (полученным с помощью программы TORA, файл ch6ToraLpShortRouteEx6-3-6.txt) является z - 55, х13 = 1, x3i = 1, xt2 = 1. Это решение дает кратчайший путь 1-»3-»4-»2из узла 1 в узел 2 длиной 2 = 55 (миль).

При использовании второй формализации задача, двойственная к представленной выше задаче ЛП, имеет вид.

Максимизировать z = у2 - уг

при ограничениях

y2-yt< 100 (маршрут 1-2), y3-yt< 30 (маршрут 1-3), у3-у2< 20 (маршрут 2-3), у4-у3< 10 (маршрут 3-4), Уь~Уг 60 (маршрут3-5),



y2-yt<15 (маршрут 4-2),

У5-у4< 50 (маршрут 4-5),

yv у2, у5 - свободные переменные.

Хотя двойственная задача строится чисто математическим путем на основе прямой задачи, ее можно сформулировать, не опираясь напрямую задачу.

Определим yt как расстояние до узла £.2 Из этого определения следует, что кратчайшее расстояние между узлами 1 и 2 можно найти путем максимизации величины у2 - уг Ограничение, связанное с маршрутом (£, у), показывает, что расстояние от узла i до узла у не может превышать длину этого маршрута. Это расстояние может быть меньше длины маршрута, если узел у можно достичь из узла t через другие промежуточные узлы, как предлагает кратчайший путь. Например, расстояние от узла 1 до узла 2 не может превышать 100.

Если переменные yt интерпретируются как расстояния, то мы вправе предположить, что все эти переменные неотрицательны (вместо условия, что они свободны). Мы также можем положить, что уг = 0 как расстояние до узла 1. Исходя из этих предположений получаем оптимальное решение: z = 55, у1 = 0, у2 - 55, у3 = 30, yt = 40, ys = 0. Значение z = 55 дает кратчайшее расстояние от узла 1 до узла 2. Это же значение можно получить как у2 - у = 55 - 0 = 55.

Определение кратчайшего пути из этого решения не очевидно. Нетрудно проверить непосредственными вычислениями, что решение удовлетворяет ограничениям для маршрутов 1-3, 3-4 и 4-2 в виде равенств. Эти ограничения и определяют кратчайший путь как 1 -> 3 -> 4 -> 2.

Другой способ найти ограничения, которые выполняются в виде равенств, заключается в использовании решения двойственной задачи, полученной с помощью второй формализации. Любое ограничение, которое включает ненулевую двойственную переменную, должно выполняться в виде равенства (см. раздел 4.2.4). Следующая таблица показывает маршруты (ограничения) и значения соответствующих двойственных переменных.

Маршрут (ограничение)

Двойственная переменная

УПРАЖНЕНИЯ 6.3.4

1. В примере 6.3.6, используя обе формализации, найдите кратчайшие пути для следующих пар узлов.

a) От узла 1 до узла 5.

b) От узла 2 до узла 5.

Здесь предполагается отсчитывать расстояние от некоторой фиксированной точки, одной для всех узлов. Ниже в качестве такой начальной точки взят узел 1. - Прим. ред.



Входные данные

BCD Е f S н~

Задана нахождения кратчайшего пути

"i--

К-во умов

N1 NZ NJ Ш N5

Спрос

.«.максимум Ш

Матрица удельных стоимостей

Предложения

9999 100 30 9999 9999

9999 9999 30 9999 9999

9999 9999 9999 10 60

9999 15 9999 9999 50

9999 9999 9999 9999 9999

Опттшальное решение

Общая стоимость 55

От- в

N1 -N2 N1 - N3 N1 -N4 N1 -N5 N2-N1 N2-N3 N2-N4 N2-N5 N3-N1 N3-N2 N3-N4 N3-N5 N4 - N1

Поток

0 1 0 0 0 0 0 О

о о 1

1Е-13 0

Ъ спос 999999 999999 999999 999999

999999 999999 999999 999999 999999 999999 999999

999999 999999

Промежуточные вычисления

Имя Узел

N2 N3 N4 N5

Поток

1Е-11 0

1Е 13

Спрос

От В Уд. стоимость

100 30 9999 9999 9999 30 9999 9999

1 9999

2 9999

4 10

5 60

1 9999

2 15

Поиск решения

Установить целевую ячейку:

1*8*18

Равной: <~

максимальному значению

ЭНЭЧбНИО

Выполнить ~] Закрыть I

с минимальному значению Иэменая ячейки.

$B*20:$S$39

Ограничения

$F*19:$F$23 = $G$19:$G$23

"31 Предположить

ры {

Добавить

Изменить

У далить

Параметры

Восстановить

Справка

Рис. 6.26. Вычисление кратчайшего пути в Excel

На рис. 6.26 строки от 11 до 15 и столбец К скрыты для экономии места.

Шаблон Excel, предназначенный для решения общей транспортной задачи (см. раздел 5.3.3), можно немного модифицировать для решения задачи нахождения кратчайшего пути. Для решения задачи используется первая формализация (раздел 6.3.3). Максимальный размер сети - 10 узлов. На рис. 6.26 показан рабочий лист, на котором решается задача из примера 6.3.4 (файл ch6SolverShortestRoute.xls). Матрица расстояний записана в диапазоне В6:К15.3 "Бесконечное" значение расстояния (равное здесь 9999 или другому достаточно большому числу) вводится для несуществующих дуг. Поскольку определяется кратчайшее расстояние между узлами 1 и 2, величина предложения для узла 1 и величина спроса для узла 2 устанавливаются равными 1. Остальные значения спроса и предложения остаются равными нулю.

[Старт] [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]