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


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


59

Пункты отправления Пункты назначения

Объемы предложений

Рис. 5.1. Представление транспортной задачи

Пример 5.1.1

Автомобильная компания MG Auto имеет три завода в Лос-Анджелесе, Детройте и Новом Орлеане и два распределительных центра в Денвере и Майами. Объемы производства заводов компании в следующем квартале составят соответственно 1000, 1500 и 1200 автомобилей. Ежеквартальная потребность распределительных центров составляет 2300 и 1400 автомобилей. Расстояния (в милях) между заводами и распределительными центрами приведены в табл. 5.1.

Таблица 5.1

Денвер

Майами

Лос-Анджелес

1000

2690

Детройт

1250

1350

Новый Орлеан

1275

Транспортная компания оценивает свои услуги в 8 центов за перевозку одного автомобиля на расстояние в одну милю. В результате получаем следующую стоимость перевозок (с округлением до доллара) по каждому маршруту.

Таблица 5.2

Денвер (1)

Майами (2)

Лос-Анджелес (1)

Детройт (2)

Новый Орлеан (3)

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

Минимизировать z = 80jc„ + 215.v12 + 100.v21 +108x22 + 102jt31 + 68x32 при ограничениях

xu + jc12 = 1000 (Лос-Анджелес),

jc21 + jc22 = 1500 (Детройт),

*3i + хз2 = 1200 (Новый Орлеан),



хи + х21 + х31 = 2300 (Денвер),

х12 + х22 + х32 = 1400 (Майами),

xtj>0, /=1,2,3,7 = 1,2.

Эти ограничения выражены в виде равенств, поскольку общий объем произведенных автомобилей (1000 + 1500 + 1200 = 3700) равен суммарному спросу распределительных центров(2300 + 1400 = 3700).

Данную задачу ЛП можно решить симплекс-методом. Но специфическая структура ограничений позволяет решить эту задачу более простым способом с помощью так называемой транспортной таблицы (табл. 5.3).

Таблица 5.3

Денвер Майами Объем производства

Лос-Анджелес

1000

Детройт

1500

Новый Орлеан

Х.12

1200

Спрос

2300

1400

Оптимальное решение (полученное с помощью программы TORA ) показано на рис. 5.2. Оно предполагает перевозку 1000 автомобилей из Лос-Анджелеса в Денвер, 1300 автомобилей- из Детройта в Денвер, 200 автомобилей- из Детройта в Майами и 1200 - из Нового Орлеана в Майами. Минимальная стоимость перевозок составляет 313 200 долл.

1000-

150О

120О

2300

1400

Новый Орлеан

Рис. 5.2. Схема оптимальных перевозок

Чтобы получить в программе TORA решение транспортной задачи, в меню Main Menu выберите команду Transportation Model (Транспортная модель). Затем в меню SOLVE/MODIFY выберите команду Solved Final solution. Более подробно решение транспортных задач в программе TORA описано в разделе 5.3.3.



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

Пример 5.1.2

В рамках модели компании MG Auto предположим, что завод в Детройте уменьшил выпуск продукции до 1300 автомобилей (вместо 1500, как было ранее). В этом случае общее количество произведенных автомобилей (3500) меньше общего числа заказанных (3700). Таким образом, очевидно, что часть заказов распределительных центров Денвера и Майами не будет выполнена.

Поскольку в данной ситуации спрос превышает предложение, для восстановления баланса введем фиктивный завод (пункт отправления), производящий 200 (3700 - 3500) автомобилей. Назначим нулевую стоимость транспортных перевозок от фиктивного завода до пунктов назначения, поскольку такого завода не существует. В принципе, стоимость транспортных перевозок от фиктивного пункта назначения может иметь любое положительное значение. Например, чтобы гарантировать выполнение всех заказов распределительного центра Майами, можно назначить очень высокую стоимость перевозок (штраф) от фиктивного завода до Майами.

В табл. 5.4 представлена сбалансированная модель и ее оптимальное решение. Решение показывает, что фиктивный завод поставит в Майами 200 автомобилей. Это означает, что для данного распределительного центра из заказа на 1400 автомобилей не будет поставлено 200 автомобилей.

Таблица 5.4

Денвер

Майами

Объем производства

>•

Лос-Анджелес

1000

1000

Детройт

1300

1300

Новый Орлеан

1200

1200

Фиктивный завод

Спрос

2300

1400

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