Пункты отправления Пункты назначения
Объемы предложений
Рис. 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 | | |