Материал: 4639
6
точников к стокам. С учетом этого рассматриваемая задача может быть представлена в следующем виде /1/
m n |
|
|
|
cijxij min |
|
||
i 1 j 1 |
|
|
|
n |
|
|
|
xij |
Si |
|
|
j 1 |
|
|
|
m |
|
|
(1.2) |
|
. |
||
xij |
D j |
|
|
i 1 |
|
|
|
xij 0 |
|
|
|
xij N 0 |
|
|
|
|
|
||
|
|
|
|
|
|
|
|
Последнее ограничение означает, что объемы поставок являются натуральными (то есть целыми числами) включая ноль. Это ограничение необязательно и зависит от формулировки задачи.
На рисунке 1.1 показано представление транспортной задачи в виде сети с m пунктами отправления и n пунктами назначения, которые показаны в виде узлов сети. Дуги, соединяющие узлы сети, соответствуют маршрутам, связывающим пункты отправления и назначения. С дугой (i, j), соединяющей пункт отправления i с пунктом назначения j, соотносятся два вида данных: стоимость сij перевозки единицы груза из пункта i в пункту и количество перевозимого груза хij. Объем грузов в пункте отправления i равен Si, а потребность в пункте назначения j равна Dj. Задача состоит в определении неизвестных величин хij, минимизирующих суммарные транспортные расходы и удовлетворяющих ограничениям, накладываемым на объемы грузов в пунктах отправления (предложение) и потребности пунктах назначения (спрос).
7
Предложение |
Спрос |
|||
S1 |
1 |
c11x11 |
1 |
D |
|
|
1 |
||
S2 |
2 |
|
2 |
D |
|
|
2 |
||
Sm |
m |
|
n |
D |
|
cmnxmn |
n |
||
|
|
|
|
|
Рис. 1.1 – Представление транспортной задачи в виде сети
1.2. Решение классической транспортной задачи в Excel
Рассмотрим решение классической транспортной задачи на основе примера, заимствованного из книги Хэмди А. Таха /2/. Из того же источника взяты задачи для самостоятельного решения, представленные в конце пункте 1.3.
Пример 1.1. Автомобильная компания «MG Auto» имеет три завода
вЛос-Анджелесе, Детройте и Новом Орлеане и два распределительных центра, в Денвере и Майами. Объемы производства заводов компании в следующем квартале составят соответственно 1000, 1500 и 1200 автомобилей. Ежеквартальная потребность распределительных центров составляет 2300 и 1400 автомобилей.
Расстояния между заводами и распределительными центрами приведены
втаблице 1.1.
Таблица 1.1
Расстояния между заводами и распределительными центрами, мили
Поставщик |
|
Потребитель |
|
|
|
|
|
|
Денвер |
|
Майами |
Лос-Анджелес |
1000 |
|
2690 |
Детройт |
1250 |
|
1350 |
|
|
|
|
Новый Орлеан |
1275 |
|
850 |
|
|
|
|
8
Транспортная компания оценивает свои услуги в 8 центов за перевозку одного автомобиля на 1 милю. В результате получаем представленную в таблице 1.2 стоимость перевозок (с округлением до 1 долл.) по каждому маршруту.
|
|
|
|
Таблица 1.2 |
|
|
Стоимость перевозок, долл. |
|
|
||
|
|
|
|
|
|
Поставщик |
|
Потребитель |
|
|
|
|
|
|
|
|
|
|
Денвер |
|
Майами |
|
|
|
|
|
|
||
Лос-Анджелес |
|
80 |
|
215 |
|
Детройт |
|
100 |
|
108 |
|
|
|
|
|
|
|
Новый Орлеан |
|
102 |
|
68 |
|
|
|
|
|
|
|
Основываясь на данных таблицы 1.2, формулируем следующую задачу линейного программирования. Минимизировать
F = 80∙х11 + 215∙х12 + 100∙х21 + 108∙х22 + 102∙х31 + 68∙х32 → min,
при ограничениях
x11 x12 |
1000 (Лос Анжелес) |
||||||||
x 21 x 22 |
1500 (Детройт ) |
|
|||||||
|
|||||||||
x31 x32 |
1200 (Новый Орлеан) |
||||||||
x11 x 21 |
x31 2300 (Денвер) |
. |
|||||||
|
|||||||||
x |
21 |
x |
22 |
x |
32 |
1400 (Майами) |
|||
|
|
|
|
|
|
||||
x |
|
0, i 1, 2, 3, |
j 1, 2. |
||||||
ij |
|
||||||||
|
|
|
|
|
|
|
|
|
|
(1.3)
(1.4)
Эти ограничения выражены в виде равенств, нескольку общий объем произведенных автомобилей (S = 1000 + 1500 + 1200 = 3700) равен суммарному спросу распределительных центров (D = 2300 + 1400 = 3700).
Данную задачу можно решить симплекс-методом /2, 3/ или с помощью так называемой транспортной таблицы. Решение данной задачи в Excel представлено на рисунке 1.2.
9
Исходные данные для решения классической транспортной задачи целесообразно представить в виде двух таблиц, в первой из которых представлены значения стоимости перевозок единицы товара сij от i-го поставщика к j- му потребителю. Во второй таблице представлены значения Si предложения каждого i-го поставщика; значения Dj, спроса каждого j-го потребителя, переменные хij, первоначально принимающие нулевые значения; вспомогательная строка и вспомогательный столбец Сумма. Целевая ячейка С17 должна содержать формулу, выражающую целевую функцию /1, 2/
=СУММПРОИЗВ (C3:D5;C12:D14) |
(1.5) |
Используя меню Сервис Поиск решения, открываем диалоговое окно Поиск решения, в котором устанавливаем целевую ячейку равной минимальному значению, определяем диапазон изменяемых ячеек и ограничения и запускаем процедуру вычисления, щелкнув по кнопке Выполнить.
Оптимальное решение данной задачи предполагает перевозку 1000 автомобилей из Лос-Анджелеса в Детройт, 1300 автомобилей – из Детройта в Денвер, 200 автомобилей – из Детройта в Майами и 1200 – из Нового Орлеана в Майами. Минимальная стоимость перевозок составляет $ 313200.
Когда суммарный объем предложений (грузов, имеющихся в пунктах отправления) не равен общему объему спроса на товары (грузы), запрашиваемые пунктами назначения, транспортная задача называется несбалансированной. В этом случае при решении классической транспортной задачи методом потенциалов применяют прием, позволяющий несбалансированную транспортную задачу сделать сбалансированной. Для этого вводят фиктивные пункты назначения или отправления.
10
Рис. 1.2. Решение классической транспортной задачи
Выполнение баланса транспортной задачи необходимо для того, чтобы иметь возможность применить алгоритм решения, построенный на использовании транспортных таблиц. В Excel несбалансированная транспортная задача