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


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


86

Шаг 5. N2 = {1, 2, 3, 4, 5} и/2 = min{oo, 20, 40,10, 20} = 10. Вычисляем остаточные пропускные способности вдоль пути N2:

(с12, с21) - (20 - 10, 0 + 10) = (10, 10),

(ся, с32) = (40 - 10, 0 + 10) = (30, 10),

(cM,cJ-(10-10, 5+ 10)-(0,15),

(с4б, cj = (20 - 10, 0 + 10) - (10, 10).

Итерация 3

Шаг1.

Назначаем а, = оо и помечаем узел 1 меткой [оо, -]. Полагаем i = 1.

Шаг 2.

= {2, 3,4}.

ШагЗ.

к =2, назначаем аг = с12 = тах{10, 10, 10} = 10 и помечаем узел 2

меткой [10, 1]. Полагаем / = 2 и возвращаемся к шагу 2.

Шаг 2.

52={3,5}.

ШагЗ.

=3ия, = св = 30. Помечаем узел 3 меткой [30, 2]. Полагаем i = 3

и возвращаемся к шагу 2.

Шаг 2.

Sa = 0 (поскольку с34 = с35 = 0). Переходим к шагу 4.

Шаг 4.

Метка [30, 2] узла 3 показывает номер предшествующего узла г-2.

На этой итерации узел 3 в дальнейшем во внимание не принимается,

его метку вычеркиваем. Полагаем / = г = 2 и возвращаемся к шагу 2.

Шаг 2.

St = {5} (поскольку узел 3 удален из возможного сквозного пути).

Шаг 3.

к = 5 и а5 = с25 = 30. Помечаем узел 5 меткой [30, 2]. Получен

сквозной путь. Переходим к шагу 5.

Шаг 5.

Лз = {1, 2, 5} и/а = min{oo, 10, 30} = 10. Вычисляем остаточные про-

пускные способности вдоль пути N3:

(с12, с21) - (10 - 10, 10 + 10) = (0, 20),

(с». О = («О " 10, 0 + 10) = (20, 10).

Итерация 4. На этой итерации получен путь N4 = {1, 3, 2, 5} с/4 = 10 (проверьте!).

Итерация 5. На этой итерации получен путь Ns = {1, 4, 5} с/5 = 10 (проверьте!).

Итерация 6. Новые сквозные пути невозможны, поскольку все ребра, исходящие из узла 1, имеют нулевые остаточные пропускные способности. Переходим к шагу 6 для определения решения.

Шаг6. Максимальный объем потока в сети равен F = /, +/2 + ... +/5 = 20 + 10 + 10 + 10 + 10 = 60 единиц. Значения потоков по различным ребрам вычисляются путем вычитания последних значений оста-



точных пропускных способностей (т.е. (с/( с.()6) из первоначальных значений пропускных способностей (С,у,С\). Результаты вычислений приведены в следующей таблице.

Ребро (CjpCV) - (с,у, Су,)6 Величина потока Направление

(1.2)

(20, 0) - (0, 20) = (20, -20)

1 ->2

(1.3)

(30, 0) - (0, 30) = (30, -30)

1 ->3

(1.4)

(10, 0)-(0, 10) = (10, -10)

1 ->4

(2, 3)

(40, 0) - (40, 0) = (0, 0)

(2, 5)

(30, 0) - (10, 20) = (20,-20)

2->5

(3, 4)

(10, 5)-(0, 15) = (10, -10)

3->4

(3, 5)

(20, 0) - (0, 20) = (20, -20)

3->5

(4, 5)

(20, 0) - (0, 20) = (20, -20)

4->5

Программа TORA позволяет найти максимальный поток или в автоматическом режиме, или последовательно - так, как показано ранее. В меню SOLVE/MODIFY выберите команду Solve problem. После задания выходного формата перейдите в выходное окно и выберите команду Maximum Flows (Максимальный поток) или Iterations. На рис. 6.32 показано выходное окно TORA с первыми двумя итерациями решения задачи из примера 6.4.2 (файл ch6ToraMaxFlowEx6-4-2.txt).

УПРАЖНЕНИЯ 6.4.2

1. В задаче из примера 6.4.2

a) для всех ребер определите величины неиспользованных пропускных способностей;

b) найдите величину потока, проходящего через узлы 2, 3 и 4;

c) можно ли увеличить максимальный поток в сети путем повышения пропускных спесобностей в направлениях 3 -> 5 и 4 -> 5?

2. Найдите максимальный поток и значения потоков, проходящих через каждое ребро сети, показанной на рис. 6.33.

3. Три нефтеперегонных завода транспортируют свою продукцию двум распределительным терминалам по сети трубопроводов, которая включает и насосные станции (рис. 6.34). Направления потоков в сети показаны стрелками, пропускные способности отдельных сегментов сети указаны в миллионах баррелей в день.

a) Определите ежедневную производительность каждого нефтеперегонного завода, соответствующую максимальной пропускной способности сети трубопроводов.

b) Определите ежедневную потребность каждого распределительного терминала, соответствующую максимальной пропускной способности сети трубопроводов.

c) Определите ежедневную пропускную способность каждой насосной станции, соответствующую максимальной пропускной способности сети трубопроводов.



Нефте-

Рис. 6.33. Сеть для задачи упражнения 2 рцс g м Сеть дм задачи упражнения 3

4. Пусть в сети из предыдущего упражнения (рис. 6.34) пропускная способность насосной станции 6 ограничена 60 миллионами баррелей в день. Найдите максимальную пропускную способность сети с учетом этого ограничения.

5. Зерно из трех зернохранилищ доставляется на грузовиках четырем птицеводческим фермам, при этом некоторые зернохранилища не могут

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