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


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


91

2. С помощью непосредственной проверки найдите допустимое решение задачи определения потока минимальной стоимости в модели распределения рабочих из примера 6.5.3 (см. рис. 6.40). Интерпретируйте найденное решение в терминах первоначальной постановки задачи (как количество нанимаемых рабочих), проверьте выполнение ограничений модели и найдите соответствующую общую стоимость.

3. Переформулируйте задачу распределения рабочих (пример 6.5.3), предполагая, что рабочие нанимаются не менее, чем на два месяца. Запишите соответствующую задачу линейного программирования и преобразуйте ее в задачу определения потока минимальной стоимости в сети с ограниченной пропускной способностью.

4. Сформулируйте задачи ЛП и соответствующие задачи определения потока минимальной стоимости для модели распределения рабочих из примера 6.5.3, используя следующие данные о потребностях рабочих в течение последующих пяти месяцев. Стоимость найма одного рабочего в эти месяцы составит соответственно 50, 70, 85, 100 и 130 долл.

Месяц

К-во рабочих

Месяц

К-во рабочих

5. Преобразование сети с ограниченной пропускной способностью в сеть с неограниченной пропускной способностью. Покажите, что дугу (i -> j) с ограниченным потоком xtj<ult можно заменить двумя дугами, не имеющими ограничений на величину потока, - (i -> k) и (k -»j) с результирующим (выходным) потоком [-и ] в узле k и дополнительным (входным) потоком [+и:/] в узле у. В результате сеть с ограниченной пропускной способностью преобразуется Тв сеть с неограниченной пропускной способностью, т.е. в транспортную модель (раздел 5.1). Примените описанное преобразование к сети на рис. 6.42 и найдите оптимальное решение полученной транспортной задачи с помощью программы TORA.

Рис. 6.42. Сеть для задачи из упражнения 5



6.5.3. Симплексный алгоритм для сетей с ограниченной пропускной способностью

Предлагаемый алгоритм повторяет в точности те же этапы, что и обычный симплекс-метод. Вместе с тем здесь учитывается специальная структура сетевой модели. Используя определения из раздела 6.5.2, где /, - результирующий поток через

узел i, строим симплексный алгоритм на основе условия =0 . Это условие оз-

начает, что в сети суммарный объем предложений равен суммарному объему спроса. Мы всегда можем удовлетворить данное условие, введя фиктивный источник или сток, которые можно связать с остальными узлами сети дугами с нулевой стоимостью и бесконечной пропускной способностью. Однако сбалансированность сети не гарантирует существования допустимого решения, поскольку этому может воспрепятствовать ограниченность пропускных способностей дуг.

Опишем алгоритм нахождения потока минимальной стоимости для сетей с ограниченной пропускной способностью. Отметим, что он базируется на стандартном симплекс-методе и теории двойственности (главы 3 и 4). Здесь также полезно знакомство с симплекс-методом для задач ЛП с ограниченными переменными (раздел 7.3).

ШагО. Определяем для данной сети начальное базисное допустимое решение (множество дуг). Переходим к шагу 1.

Шаг 1. С помощью условия оптимальности симплекс-метода определяем вводимую в базис переменную (дугу). Если на основе условия оптимальности определяем, что последнее решение оптимально, вычисления заканчиваются. В противном случае переходим к шагу 2.

Шаг 2. На основе условия допустимости симплекс-метода определяем исключаемую из базиса переменную (дугу). Изменив базис, возвращаемся к шагу 1.

Сети с п узлами и нулевым результирующим потоком (т.е. при выполнении равенства Д + f2 + ... + fn = 0) соответствуют п - 1 независимым ограничениям в виде равенств. Поэтому базисное решение должно содержать п - 1 переменных. Можно показать, что базисное решение соответствует остовному дереву данной сети (см. раздел 6.2).

Вводимая переменная (дуга) на шаге 1 определяется путем вычисления разностей ztj - ctj для всех текущих небазисных дуг (t, j). Если для всех разностей z - ctj< 0, тогда текущее базисное решение оптимально. Иначе в качестве вводимой в базис переменной выбираем дугу, которой соответствует наибольшее положительное значение разности гц - сц.

Вычисление разностей ztj - сц основано на соотношениях двойственности точно так же, как в транспортной модели (см. раздел 5.3.4). Обозначим через wt переменную задачи, двойственной к задаче ЛП (определенной в разделе 6.5.2), которая (переменная) соответствует ограничению узла /. Тогда данная двойственная задача формулируется следующим образом.

Максимизировать z = £/wi

при выполнении условий

w,-w< сц, (/, у) е А,

переменные wt произвольного знака (i = 1, 2, п).

Из теории линейного программирования следует, что wt - w = с для любой базисной дуги (/, j). Поскольку исходная задача ЛП (раздел 6.5.2) по определению



имеет одно избыточное ограничение, мы можем присвоить произвольное значение одной из переменных двойственной задачи (сравните с алгоритмом решения транспортной задачи из раздела 5.3). Для определенности положим wx = 0. Затем следует решить (базисную) систему уравнений wt - w. = ci;, чтобы вычислить остальные переменные двойственной задачи. Далее находим разности z - сц для небазисных переменных согласно формуле

zlj-cirwl-wrclj.

Теперь осталось показать, как определяется исключаемая из базиса переменная. Для этого рассмотрим следующий числовой пример.

Пример 6.5.4

Сеть трубопроводов связывает две станции опреснения воды с двумя городами. Ежедневное предложение опреснительных станций составляет 40 и 50 миллионов галлонов воды, города ежедневно потребляют 30 и 60 миллионов галлонов воды. Каждая станция трубопроводами соединена с каждым городом непосредственно, однако они могут также перекачивать воду в города через специальную насосную станцию. Кроме того, станция 1 может транспортировать воду на станцию 2, а город 1 - в город 2. Данная сеть сбалансирована, так как в ней суммарный спрос равен суммарному предложению. Описанная сеть показана на рис. 6.43.

Удельная стоимость Пропускная способность

Рис. 6.43. Сеть для примера 6.5.4

Определение начального допустимого базисного решения. Нетрудно построить остовное дерево (на рис. 6.44 показано сплошными дугами) для рассматриваемой сети. Отсюда получаем начальное допустимое базисное решение. Обычно, чтобы найти такое решение, используется метод введения искусственных переменных (подробности см. в [2]).

На рис. 6.44 показано, что базисному решению соответствуют дуги (1, 3), (1, 4), (2, 3) и (3, 5) с потоками 30, 10, 50 и 60 единиц соответственно. Оставшиеся дуги (показаны пунктиром) представляют небазисные переменные. Запись х(с) показывает, что через соответствующую дугу с пропускной способностью с проходит поток х. По умолчанию считается, что х = 0 и с = со.

Итерация 0 Шаг 0.

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