Транспортная задача

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

Постановка задачи

Однородный груз сосредоточен у m поставщиков в объемах a₁, a₂, ... a_m.
Данный груз необходимо доставить n потребителям в объемах b_1, b₂ ... b_n.
Известны с_ij , i=1,2,...m; j=1,2,...n — стоимости перевозки единиц груза от каждого i-го поставщика каждому j-му потребителю. Переменными (неизвестными) транспортной задачи являются x_ij , i=1,2,...,m j=1,2,...,n — объемы перевозок от i-го поставщика каждому j-му потребителю.
Требуется составить такой план перевозок, при котором запасы всех поставщиков вывозятся полностью, запросы всех потребителей удовлетворяются полностью, и суммарные затраты на перевозку всех грузов являются минимальными.

Математическая модель транспортной задачи:

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

Пример 1. Сбалансированная задача

Рассмотрим задачу доставки товара с четырех заводов на четыре склада. Товары могут доставляться с любого завода на любой склад, но при этом различается стоимость доставки. Завод не может отправить больше продукции, чем он производит.  На склад может быть доставлено больше продукции, чем им запрошено. Требуется определить объемы перевозок между каждым заводом и складом таким образом, чтобы удовлетворить производственные возможности заводов и потребности складов и минимизировать затраты на перевозку товаров.

	Стоимость перевозки				Произведено заводом
	Склад1	Склад2	Склад3	Склад4
Завод1	1	3	4	5	20
Завод2	5	2	10	3	30
Завод3	3	2	1	4	50
Завод4	6	4	2	6	30
Запрошено складом	30	20	60	20	Сумма = 130

Задача сбалансирована, поскольку суммарный объем производства (130) равен суммарному спросу (130).

Решение

Создадим таблицу по образцу, дадим имена диапазонам, создадим формулы, используя имена диапазонов.

Имя Диапазон Стоимость B3:E6 Произведено F3:F6 Запрошено B7:E7 Объемы B11:E14 Отправлено F11:F14 Получено B15:E15 Расходы D17

Пояснения к таблице.

Искомые объемы перевозок укажем поначалу равными 1. Подсчитаем сумму объемов, отправленных каждым заводом, и сумму объемов, полученных каждым складом. Подсчитаем суммарные транспортные расходы.

Вызовем Поиск решения:

Установить целевую ячейку: Расходы
равной минимальному значению.
Изменяя ячейки: Объемы
Ограничения:

• Объемы > 0
• Отправлено <= Произведено
• Получено >= Запрошено

Ответ: Транспортные расходы = 240. Спрос складов полностью удовлетворен. Вся произведенная продукция отправлена с заводов на склады. Объемы перевозок представлены в таблице:

	Объемы перевозок				Отправлено заводом
	Склад1	Склад2	Склад3	Склад4
Завод1	20	0	0	0	20
Завод2	0	10	0	20	30
Завод3	10	10	30	0	50
Завод4	0	0	30	0	30
Получено складом	30	20	60	20

Пример 2. Несбалансированная задача. Предложение превышает спрос.

Изменим исходные данные Примера1. Например, объем производства завода 4 увеличим с 30 до 40.

Найдем оптимальное решение с помощью Поиска решения при тех же ограничениях.

Ответ: Транспортные расходы = 240. Спрос складов полностью удовлетворен. Вся произведенная продукция отправлена с заводов на склады, за исключением завода 4, там остался объем продукции =10. План перевозок такой же как в сбалансированной задаче.

Пример 3. Несбалансированная задача. Спрос превышает предложение

Изменим исходные данные Примера1. Например, объем производства завода 4 уменьшим с 30 до 20. (Спрос превышает предложение на 10 единиц).

Найдем оптимальное решение с помощью Поиска решения при тех же ограничениях.

Ответ: Поиск не может найти подходящего решения. Промежуточные результаты расчетов представлены в таблице. Вся произведенная продукция отправлена с заводов на склады. Склад 2 недополучил 10 единиц по сравнению с заказом равным 20.

	Объемы перевозок				Отправлено заводом
	Склад1	Склад2	Склад3	Склад4
Завод1	10	10	0	0	20
Завод2	3E-10	0	10	20	30
Завод3	0	0	50	0	50
Завод4	20	0	0	0	20
Получено складом	30	10	60	20
Транспортные расходы			370

Решение транспортной задачи с дефицитом товаров (спрос превышает предложение)

Для того, чтобы всё-таки решить эту задачу надо добавить фиктивный завод, объем производства которого равен объему дефицита товаров (=СУММ(Запрошено)-СУММ(Произведено)), в нашем случае дефицит составляет 10 единиц, а стоимость перевозки товаров с этого завода на склады сделаем равной штрафу за недопоставку товаров, например, 12. Сделайте таблицу как показано ниже. Вам придется заново дать имена диапазонам и создать формулы. Лучше сделать это в новой книге, чтобы не запутаться со старыми именами. Сделайте эту работу самостоятельно.

	Стоимости перевозок
	Склад1	Склад2	Склад3	Склад4	Произведено заводом
Завод1	1	3	4	5	20
Завод2	5	2	10	3	30
Завод3	3	2	1	4	50
Завод4	6	4	2	6	20
Завод5	12	12	12	12	10
Запрошено складом	30	20	60	20
	Объемы перевозок
	Склад1	Склад2	Склад3	Склад4	Отправлено заводом
Завод1	1	1	1	1	4
Завод2	1	1	1	1	4
Завод3	1	1	1	1	4
Завод4	1	1	1	1	4
Завод5	1	1	1	1	4
Получено складом	5	5	5	5
Транспортные расходы			109

Ответ. Транспортные расходы = 320. Из решения мы увидим, якобы с фиктивного завода отправлено 10 единиц продукции на Склад1. На самом деле Склад1 недополучит эти 10 единиц. Стало быть должен получить компенсацию за недопоставку товаров в размере 10 единиц товара * 12 денежных единиц штрафа за недопоставку.