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


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


92

Рис. 6.44. Сеть на итерации О

Итерация 1

Шаг 1. Определение вводимой в базис переменной. При решении системы уравнений

w, = 0,

w, - wj = cLj для базисных дуг получим значения переменных двойственной задачи.

Дуга (1, 3): w, - w3 = 7 w3 = -7.

Дуга (1, 4): w, - wt = 5 w4 = -5.

Дуга (2, 3): w2 - w3 = 2 w2 = -5.

Дуга (3, 5): w3 - w5 = 8 => wb = -15. Теперь вычисляем разности z,. - с . для небазисных переменных.

Дуга (1, 2): w, - w2 - с12 = 0 - (-5) -3 = 2.

Дуга(2, 5): w2-w5-с25 = (-5) - (-15) -1 = 9.

Дуга (4, 5): wt - w5 - с4б = (-5) - (-15) -4 = 6.

Таким образом, дуга (2, 5) будет введена в базисное решение.

Шаг 2. Определение исключаемой из базиса переменной. На рис. 6.44 видно, что дуга (2, 5) совместно с базисными дугами (2, 3) и (3, 5) образует цикл. По определению остовное дерево не может содержать циклов. Поскольку поток через дугу (2, 5) должен возрасти, необходимо выровнять потоки через дуги, составляющие цикл таким образом, чтобы новое решение осталось допустимым. Для этого поток через дугу (2, 5) пометим знаком "+", потоки через другие дуги цикла- знаком "+" или в зависимости от того, будут ли совпадать направления потоков в этих дугах с направлением потока в дуге (2, 5) при обходе цикла против часовой стрелки.5 Пометки дуг цикла показаны на рис. 6.44. При определении максимального потока, протекающего через дугу (2, 5), необходимо придерживаться следующих правил.

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



1. Новый поток в текущей базисной дуге не может быть отрицательным.

2. Поток через вводимую в базис дугу не может превышать ее пропускную способность.

Применение правила 1 показывает, что потоки через дуги (2, 3) и (3, 5) нельзя уменьшить более, чем на min{50, 60} = 50 единиц. Из правила 2 следует, что поток через дугу (2, 5) не может превышать 30 единиц (пропускная способность этой дуги равна 30). Поэтому поток через дуги цикла изменится не более, чем на min{30, 50} = 30 единиц. Таким образом, поток через дугу (2, 5) равен 30 единиц, через дугу (2, 3) 50 - 30 = 20 единиц, а через дугу (3, 5) - 60 - 30 = 30 единиц.

Поскольку никакая из текущих базисных переменных не приняла нулевого значения, дуга (2, 5) должна остаться небазисной, но с ненулевым значением в 30 единиц. Чтобы выполнить требование равенства нулю небазисных переменных, сделаем подстановку

*25 = 30 -х52,0<х52<30. Эта подстановка изменит уравнения для потоков, протекающих через узлы 2 и 5.

Текущее уравнение для потоков узла 2: 50 + х]2 = х23 + х2Ъ.

Текущее уравнение для потоков узла 5: х2ь + х35 + х45 = 60. После подстановки х2Ъ - 30 - хЬ2 получим следующее.

Новое уравнение для потоков узла 2: 20 + х12 + х52= х2Г

Новое уравнение для потоков узла 5: х35 + xi5 = хь2 + 30.

Результаты этих изменений показаны на рис. 6.45. Направление потока через дугу (2, 5) изменилось на обратное (от узла 5 к узлу 2), причем, как и ожидалось, хЬ2 = 0. Описанная подстановка также требует изменения стоимости прохождения потока по дуге (2, 5) до -1 долл. Те дуги, направления потоков которых изменены на противоположные, помечены в сети звездочкой.

w, = 0 w4 = -5

-1) = -9 = 6

Рис. 6.45. Сеть на итерации 1

Итерация 2. На рис. 6.45 представлены новые значения разностей z,. - сц (проверьте эти значения!). Очевидно, что в базис следует ввести дугу (4, 5). Введение в базис этой дуги также приводит к образованию цикла.

Величину потока через дугу (4, 5) можно увеличить до наименьшей из следующих величин.



1. Максимальный поток через дугу (4, 5), определяемый пропускной способностью, равен со.

2. Максимальное увеличение потока через дугу (1, 4) равно 35 - 30 = 5 единиц.

3. Максимальное уменьшение потока через дугу (1, 3) равно 10 единиц.

4. Максимальное уменьшение потока через дугу (3, 5) равно 30 единиц.

Таким образом, поток через дугу (4, 5) можно увеличить до 5 единиц; эта дуга входит в базис, а дуга (1, 4) с потоком в 35 единиц исключается из базиса.

Выполнив подстановку хы = 35 - х41, получим сеть, показанную на рис. 6.46, где дуги (1, 3), (2, 3), (3, 5) и (4, 5) формируют остовное дерево сети (базисное решение). Для дуги (1, 4) с обратным направлением потока изменена стоимость прохождения потока до -5 долл. Проверьте самостоятельно, что в уравнения для потоков в узлах 1 и 4 будет добавлено 5 единиц входного потока.

<4)[5]

5(оо)

12 *-12 z41 ~ с41=

с12=0-(-5)-3 = 2

11 - 0 - (-5) = -6 15-(-5)-(-1) = -9

[-30]

Рис. 6.46. Сеть на итерации 2

Итерация 3. Вычисленные новые значения разностей z(/ - ct/ для небазисных дуг (1, 2), (4, 1) и (5, 2) показаны на рис. 6.46. Из этих значений вытекает, что в базис следует ввести дугу (1, 2) с потоком в 5 единиц, тогда как дуга (1, 3) исключается из базиса с нулевым значением потока. Новое решение представлено на рис. 6.47.

w, = 0

41 Ml

= 0-(-5)-7 = -: 9 0-(-5) =

52 ь52

с52=-13-(-3)-(-1) = -9

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

;5, *1з=0 35 -0 = 35

х23=25

х„=30-0 = 30

*35:

= 25, х,

45"

Суммарная стоимость = 490 Рис. 6.47. Сеть на итерации 3

Итерация 4. Из новых значений разностей гц - ctj (рис. 6.47) видно, что последнее решение оптимально. Значения исходных переменных получаем путем обратной подстановки, как показано на рис. 6.47.

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