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


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


72

Получаем следующую задачу ЛП.

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

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

2>, = 1, i = l, 2,..., и.

5>„=1, У = 1,2,..., и, л:. = 0 или 1.

Оптимальное решение данной задачи ЛП останется неизменным, если ко всем элементам какой-либо строки или столбца матрицы стоимостей (с,.) прибавить константу или вычесть ее из этих элементов. Для доказательства этого обозначим через pt и <7у константы, вычитаемые из элементов строки i и столбца у" соответственно. Таким образом, стоимость с изменится и будет равна

Теперь покажем, что при коэффициентах целевой функции с получим те же оптимальные значения переменных jc ., что и при коэффициентах сц.

ХЕ<с« - а - я,)**=ХХсл - X р. (х** ] ~ X?; f Х-1= = XXca - X p> 0) X<?;( 0=ХХсл константа-

Поскольку новая целевая функция отличается от исходной только на константу, оптимальные значения переменных х должны быть одинаковы в обоих случаях. Таким образом показано, что этапы 1 и 2 венгерского метода, где р. вычитаются из элементов строки г, a. q - из элементов столбца у матрицы стоимостей, приводят к эквивалентной задаче о назначениях. Поэтому, если нулевые элементы в матрице стоимостей, созданные на этапе 1 и 2 венгерского метода, позволяют найти допустимое решение, то оно должно быть оптимальным, поскольку стоимости в измененной матрице стоимостей не могут быть меньше нуля.

Если созданные нулевые элементы не могут привести к допустимому решению (как в примере 5.4.2), необходимо выполнить описанный выше этап 2.1. Эта процедура опять основывается на симплекс-методе, и ее корректность можно обосновать, исходя из теории двойственности (глава 4) и теоремы о дополняющей нежесткости (глава 7). Пока мы не будем углубляться в это.

То, что сумма Хр, +Xjj равна оптимальному значению целевой функции,

вытекает из того, что данная сумма представляет собой целевую функцию двойственной задачи. Это видно из представленного в разделе 5.3.4 выражения для целевой функции задачи, двойственной транспортной задаче. (Подробности см. в [1].)

5.5. ТРАНСПОРТНАЯ МОДЕЛЬ С ПРОМЕЖУТОЧНЫМИ ПУНКТАМИ

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



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

В этом разделе показано, как транспортную модель с промежуточными пунктами можно преобразовать (и решить) в обычную транспортную с помощью введения буфера.

Пример 5.5.1

Два автомобильных завода Р1 и Р2 связаны с тремя дилерами Dl, D2 и D3, имеющими два транзитных (перевалочных) центра Т1 и Т2, как показано на рис. 5.9. Заводы Р1 и Р2 производят 1000 и 1200 автомобилей. Заказы дилеров составляют соответственно 800, 900 и 500 автомобилей. Стоимость перевозок одного автомобиля (в сотнях долларов) показана на рис. 5.9 возле соответствующих дуг.

1000-

120О

Рис. 5.9. Транспортная модель с промежуточными пунктами

В данной модели перевозки транзитом могут осуществляться через любые пункты (в соответствии с направлением дуг на схеме), даже через некоторые пункты назначения. Поэтому пункты, которым соответствуют как входящие, так и выходящие дуги на схеме рис. 5.9, назовем транзитными (пункты 71, 72, D1 и D2). Оставшиеся будут либо истинными пунктами отправления (пункты Р1 и Р2), либо истинными пунктами назначения (в данной схеме такой пункт только один - D3). Эту модель можно преобразовать в обычную транспортную модель с шестью пунктами отправления (PI, Р2, 71, 72, D1 и D2) и пятью пунктами назначения (71, 72, Dl, D2 и D3). Объемы спроса и предложения, соответствующие этим пунктам отправления и назначения, вычисляются следующим образом.

Объем предложения истинного пункта отправления = объем исходного предложения.

Объем предложения транзитного пункта - объем исходного предложения + объем буфера.

Объем спроса истинного пункта назначения = объем исходного спроса.

Объем спроса транзитного пункта = объем исходного спроса + + объем буфера.

Объем буфера должен быть таким, чтобы вместить объем всего предложения (или спроса). Обозначим через В объем буфера. Тогда



В - общий объем предложения (или спроса) = = 1000 + 1200 = (или = 800 + 900 + 500) = = 2200 автомобилей.

Построенная транспортная модель, эквивалентная исходной задаче, представлена в табл. 5.44. Решение этой транспортной модели, полученное с помощью программы TORA (файл ch5ToraTransshipEx5-5-l.txt), показано на рис. 5.10. Отметим "транзитный" эффект решения: дилер D2 получает 1400 автомобилей, из них 900 оставляет себе (для удовлетворения своего спроса), а 500 отправляет дилеру D3.

Таблица 5.44

1000

1200

800 + в

900 + в

1000

1200-

(D3)--500

Рис.6.10. Решение транспортной задачи с промежуточными пунктами

УПРАЖНЕНИЯ 5.5

1. В транспортной сети, показанной на рис. 5.11, осуществляются перевозки из пунктов 1 и 2 в пункты 5 и 6 через транзитные пункты 3 и 4. Стоимость перевозок показана на этом же рисунке.

a) Постройте транспортную модель с промежуточными пунктами и соответствующую ей обычную транспортную модель.

b) Решите транспортную задачу и покажите на схеме маршруты доставки грузов из пунктов отправления в пункты назначения.

° Для решения задач этого набора упражнений используйте программы TORA, Excel (со средством Поиск решения) и LINGO.

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