2015-04-30
1816
Сущность транспортной задачи линейного программирования состоит в наивыгоднейшем прикреплении поставщиков однородного продукта ко многим потребителям этого продукта. На практике постоянно возникает необходимость решения таких задач, особенно когда количество пунктов отправления и получения грузов увеличивается.
Условие транспортной задачи обычно записывается в виде матрицы, в которой потребители однородного груза размещаются по столбцам, а поставщики - по строкам. В последнем столбце матрицы проставляют запас груза, имеющийся у каждого поставщика, а в последней строке - потребность в нем потребителей. На пересечении строк со столбцами (в клетках матрицы) записывают размер поставки, а также расстояние пробега по всем возможным маршрутам время доставки груза или затраты на перевозку единицы груза по этим маршрутам.
Математически транспортная задача по критерию стоимости формируется следующим образом. Имеется п потребителей и т поставщиков однородного груза. Мощность i-гo поставщика (i = 1,m) обозначим аi, спрос j-го потребителя (j = 1, п) bj. Затраты на перевозку одной тонны груза от i-гo поставщика до j-го потребителя обозначим сij. Размер поставки продукции поставщиком i потребителю j обозначим хij; общую сумму затрат на перевозку груза обозначим через F.
|
|
|
Запишем математическую модель задачи:
1) объем поставок i-гo поставщика должен равняться количеству имеющегося у него груза:
2) объем поставок j-му потребителю должен быть равен его спросу:
3) запас груза у поставщиков должен равняться суммарному спросу потребителей:
4) размер поставок должен выражаться неотрицательным числом:
5) общая сумма затрат на перевозку груза должна быть минимальной:
Поставленная в задаче цель может быть достигнута различными методами, например, распределительным методом или методом потенциалов.
Модель транспортной задачи линейного программирования может использоваться для планирования ряда операций, не связанных с перевозкой грузов. Так, с ее помощью решаются задачи по оптимизации размещения производства, топливно-энергетического баланса, планов загрузки оборудования распределения сельскохозяйственных культур по участкам различного плодородия
Пример
Автомобильная компания MG Auto имеет три завода в Лос-Анджелесе, Детройте и Новом Орлеане и два распределительных центра в Денвере и Майами. Объемы производства заводов компании в следующем квартале составят соответственно 1000, 1500 и 1200 автомобилей. Ежеквартальная потребность распределительных центров составляет 2300 и 1400 автомобилей. Расстояние (в милях) между заводами и распределительными центрами приведены в табл. 1.
|
|
|
Таблица 1
| Поставщики | Потребители | |
| Денвер | Майами | |
| Лос-Анджелес | ||
| Детройт | ||
| Новый Орлеан |
Транспортная компания оценивает свои услуги в 8 центов за перевозку одного автомобиля на одну милю. В результате получаем, представленную в табл. 2, стоимость перевозок (с округлением до доллара) по каждому маршруту.
Таблица 2
| Поставщики | Потребители | |
| Денвер | Майами | |
| Лос-Анджелес | $80 | $215 |
| Детройт | $100 | $108 |
| Новый Орлеан | $102 | $68 |
Основываясь на данных из табл. 2, формулируем следующую задачу линейного программирования.
Минимизировать
F=80x11+215x12+100x21+108x22+102x31+68x32 Þ min
при ограничениях
x11+x12=1000 (Лос-Анджелес),
x21+x22=1500 (Детройт),
x31+x32=1200 (Новый Орлеан),
x11+x21+x31=2300 (Денвер),
x12+x22+x32=1400 (Майами),
x ij ³0, i =1,2,3, j =1,2.
Эти ограничения выражены в виде равенств, поскольку общий объем произведенных автомобилей (S =1000+1500+1200= =3700) равен суммарному спросу распределительных центров (D =2300+1400=3700).
Исходные данные для решения классической транспортной задачи целесообразно представить в виде двух таблиц (см. рис. 1), в первой из которых представлены значения стоимости перевозок единицы товара cij от i -го поставщика к j -му потребителю. Во второй таблице представлены: предложения каждого i -го поставщика; значения спроса каждого j -го потребителя; переменные xij, первоначально принимающие нулевые значения; вспомогательная строка и вспомогательный столбец "Сумма".
Целевая ячейка C17 должна содержать формулу, выражающую целевую функцию:
=СУММПРОИЗВ(C3:D6;C12:D14).
 |
Используя меню СервисÞПоиск решения открываем диалоговое окно Поиск решения (см. рис. 2), в котором устанавливаем целевую ячейку равной минимальному значению, определяем диапазон изменяемых ячеек и ограничения и запускаем процедуру вычисления, щелкнув по кнопке Выполнить.
 |
Рис. 2.
Оптимальное решение данной задачи представлено на рис. 3. Оно предполагает перевозку 1000 автомобилей из Лос-Анджелеса в Детройт, 1300 автомобилей - из Детройта в Денвер, 200 автомобилей - из Детройта в Майами и 1200 - из Нового Орлеана в Майами. Минимальная стоимость перевозок составляет 313200 долларов.
 |
Рис. 3.
В рамках модели компании MG Auto предположим, что завод в Детройте уменьшил выпуск продукции до 1300 автомобилей (вместо 1500, как было ранее). В этом случае общее количество произведенных автомобилей (=3500) меньше общего количества заказанных (=3700) автомобилей. Таким образом, очевидно, что часть заказов распределительных центров Денвера и Майами не будет выполнена.
В Excel несбалансированная транспортная задача решается путем изменения ограничений по спросу (если спрос превышает предложение) или по предложению (если предложение превышает спрос). ПРИВЕСТИ СИСТЕМУ ОГРАНИЧЕНИЙ
На рис. 4 и рис. 5 представлено решение данной задачи в Excel.
 |
Рис. 4.
 |
Рис. 5.
В таблице-плане оптимального закрепления на рис. 5 представлено оптимальное решение. Решение показывает, что спрос распределительного центра Денвера будет удовлетворен полностью, а в распределительный центр Майами из заказа в 1400 автомобилей не будет поставлено 200 автомобилей.
Если предположить, что заказ распределительного центра Денвера составляет всего 1900 автомобилей, то получим ситуацию, когда предложение превышает спрос. Решение данной задачи в Excel представлено на рис. 6 и рис. 7. Решение показывает, 400 автомобилей завода Детройта не востребованы.
Рис. 6.
Рис. 7.
