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


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


84

После того как будут введены значения спроса и предложения, рабочий лист пе-ресчитывается автоматически. Выделенные столбцы В, С, F и G содержат исходные данные задачи, необходимые для использования средства Поиск решения. Диапазон В20:В39 (изменяемые ячейки для средства Поиск решения) содержит величины потоков, проходящие по каждой дуге. Столбец С содержит значение пропускных способностей дуг (диапазон С20:С39). В задаче поиска кратчайшего пути эти пропускные способности в вычислениях не участвуют, поэтому они имеют "бесконечные" значения (равные 99999). Ограничения модели представляют балансы потоков, проходящих через каждый узел. Как показано в разделе 5.3.3, с помощью функций СУММЕСЛИ вычисляются чистые потоки через каждый узел, для чего используются данные из столбцов I и J. Все эти вычисления выполняются автоматически. Все, что необходимо сделать вам для решения задачи, - это указать диапазон изменяемых ячеек и задать ограничения в диалоговом окне средства Поиск решения. На рис. 6.26 видно, что изменяемые ячейки составляют диапазон В20:В39, а ограничения задаются в виде равенства F19:F23=G19:G23.

Решение N1-N3 = 1, N3-N4 = 1 и N4-N2 = 1, показанное на рис. 6.26, дает общее расстояние 55 миль. Это решение означает, что кратчайший путь проходит через узлы 1 -» 3 -> 4 -> 2.

УПРАЖНЕНИЯ 6.3.5

1. Измените рабочую книгу ch6SolverShortestRoute.xls применительно к задаче примера 6.3.4, чтобы найти кратчайшие пути между следующими парами узлов.

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

b) От узла 4 до узла 3.

2. Измените рабочую книгу ch6SolverShortestRoute.xls применительно к задаче из упражнения 6.3.1.2, чтобы найти кратчайший путь между узлами 4 и 7.

6.4. ЗАДАЧА О МАКСИМАЛЬНОМ ПОТОКЕ

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

При решении данной задачи исходную сеть необходимо свести к сети с одним источником и одним стоком. Этого можно достичь, вводя дополнительные дуги с бесконечной пропускной способностью от источника к скважинам и от нефтеперегонных заводов к стоку (на рис. 6.27 эти дуги показаны пунктирными линиями).

Для ребра (/, у), где i < у, используем запись (С,Су,) для представления пропускных способностей в направлениях i -> у и у -> i соответственно. Во избежание недоразумений на схеме сети С. будем располагать на ребре (t, у) ближе к узлу i, a Cjt - ближе к узлу у, как показано на рис. 6.28.



Источник"

Скважиньп Насосные станции i Нефтеперегонные заводы

Рис. 6.27. Сеть, связывающая скважины, насосные станции и нефтеперегонные заводы

Рис. 6.28. Обозначение пропускных способностей

6.4.1. Перебор разрезов

Разрез определяет множество ребер, при удалении которых из сети полностью прекращается поток от источника к стоку. Пропускная способность разреза равна сумме пропускных способностей "разрезанных" ребер. Среди всех разрезов сети разрез с минимальной пропускной способностью определяет максимальный поток в сети.

Пример 6.4.1

Рассмотрим сеть, показанную на рис. 6.29. На этом рисунке при обозначении пропускных способностей двунаправленных ребер придерживались соглашения, принятого ранее (рис. 6.28). Например, для ребра (3, 4) пропускная способность в направлении 3 -> 4 равна 10, а в направлении 4 -> 3 - только 5. >•

Разрез 2

Рис. 6.29. Пример разрезов сети



Разрезы, представленные на рис. 6.29, имеют следующие пропускные способности.

Разрез

"Разрезанные" ребра

Пропускная способность

(1,2), (1.3), (1,4)

10 + 30 + 20 =60

(1,3), (1,4), (2, 3), (2, 5)

30 + 10 + 40 + 30 = 110

(2, 5), (3, 5), (4, 5)

30 + 20 + 20 = 70

Вывод, который можно сделать на основе этих трех разрезов, заключается в том, что максимальный поток не может превышать 60 единиц. Но мы не можем сказать, каков максимальный поток на самом деле, так как не перебрали все возможные разрезы сети. К сожалению, перебор всех разрезов является непростой задачей. Поэтому для определения максимального потока в сети не используются алгоритмы, основанные на полном переборе разрезов. В следующем разделе будет показан эффективный алгоритм вычисления максимального потока.

УПРАЖНЕНИЕ 6.4.1

1. Для сети, показанной на рис. 6.29, проведите еще два разреза и найдите их пропускные способности.

6.4.2. Алгоритм нахождения максимального потока

Идея данного алгоритма состоит в поиске сквозных путей с положительными потоками от источника к стоку.

Рассмотрим ребро (i, у) с (начальной) пропускной способностью (С..С,,). В процессе выполнения алгоритма части этих пропускных способностей "забираются" потоками, проходящими через данное ребро, в результате каждое ребро будет иметь остаточную пропускную способность. Будем использовать запись (сц, с\,) для представления остаточных пропускных способностей. Сеть, в которой все ребра имеют остаточную пропускную способность, назовем остаточной.

Для произвольного узла у, получающего поток от узла i, определим метку [ау, Л, где а - величина потока, протекающего от узла у к узлу i. Чтобы найти максимальный поток, выполним следующие действия.

Этап 1. Для всех ребер (£, у) положим остаточную пропускную способность равной первоначальной пропускной способности, т.е. приравняем (cijt с\,) = (С,С;,) . Назначим а1 = оо и пометим узел 1 меткой [оо, -]. Полагаем i = 1 и переходим ко второму этапу.

Этап 2. Определяем множество Sl как множество узлов у, в которые можно перейти из узла i по ребру с положительной остаточной пропускной способностью (т.е. с, > 0 для всех у 6 St). Если S, Ф 0, выполняем третий этап, в противном случае переходим к п. 4.

Этап 3. В множестве Sl находим узел к, такой, что

Положим ак = с1к и пометим узел к меткой [ак, i]. Если последней меткой помечен узел стока (т.е. если к = п), сквозной путь найден,

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