Исходные данные транспортной задачи

Имеется три пункта поставки однородного груза a₁, a₂ и a₃ и три пункта потребления этого груза B₁, B₂ и B₃. Запасы груза у поставщиков: A₁, A₂ и А₃, соответственно. Потребности потребителей: B₁, B₂ и B₃. Суммарная мощность поставщиков оказывается недостаточной, поэтому принято решение об ее увеличении, причем имеется два альтернативных варианта: 1 – реконструкция первого предприятия поставщика, 2 – строительство нового предприятия. Известна стоимость перевозки 1 т груза c _ij из i -го пункта поставки в j -й пункт потребления. Кроме того, имеется дополнительное ограничение – второй поставщик А₂ может поставить первому потребителю B₁ ограниченное количество груза. Необходимо при имеющихся ограничениях так распределить перевозки между поставщиками и потребителями, чтобы суммарные транспортные расходы были минимальны (таблица 3.2.18).

Таблица 3.2.18 – Исходные данные транспортной задачи

Поставщик	Потребитель
В₁	В₂	В₃
A₁= 50 (E+5)	A+B	B+C	C+D

A₂= 50 (F+1)	D+E	E+F	A+C
ограничения на поставки
A₃= 10 (Е+F)	B+D	C+E	D+F

Необходимо составить математическую модель задачи с учетом дополнительного ограничения; найти первоначальный опорный план производства и организации перевозок методом наименьшего элемента; оптимизировать план производства и организации перевозок методом потенциалов или методом оценки циклов; сделать технико-экономическое истолкование найденного оптимального решения; определить экономическую эффективность решения задачи оптимизации перевозок.

Составление кольцевых маршрутов. Задача коммивояжера

Многие потребители заказывают со складов партии «меньше чем вагон», «меньше чем трейлер», что значительно увеличивает издержки, связные с доставкой таких грузов. Для сокращения транспортных расходов склад может организовать объединение небольших партий грузов для нескольких клиентов, до полной загрузки транспортных средств. Маршрут от склада до нескольких потребителей с возвратом на склад называется кольцевым маршрутом.

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

Пример решения задачи составления кольцевых маршрутов

Имеется сеть магазинов, снабжаемых из одного распределительного склада. Снабжение производится автомобилями грузоподъемностью 5 т. Средние величины заказов магазинов приведены в таблице 3.2.19.

Таблица 3.2.19

№ магазина
Величина заказа, т	1,0	2,2	0,8	1,5	0,7	0,5	1,8	1,6	0,4	1,1	2,0	0,9	0,7	2,9

Задача решается с помощью алгоритма Свира или алгоритма дворника-стеклоочистителя.

Зададим положение магазинов в полярной системе координат. Полюс системы – точку 0, разместим в месте расположения распределительного склада (рисунок 3.6).

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

Рисунок 3.6 – Декомпозиция транспортной сети при составлении маршрутов

Составление кольцевого маршрута осуществляется путем решения задачи коммивояжера.

Естественно, что в данном случае начальный и конечный пункты маршрута совпадают (распределительный склад).

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

В 4-й магазин можно приехать из 5-го, 6-го или 7-го; в 5-й – из 4-го, 6-го или 7-го; в 6-й – из 4-го, 5-го или 7-го; в 7-й – из 4-го, 5-го или 6-го.

В дальнейшем процесс решения разворачивается алогично. Слева от стрелок ставим суммарные расстояния.

Оптимальными оказываются маршруты «склад-7-6-5-4-склад» и «склад-4-5-6-7-склад», т.к. они обеспечивают минимальный километраж (15 км). Однако 4-й магазин расположен ближе к складу, чем 7 магазин и целесообразнее ехать по маршруту «склад-4-5-6-7-склад», чтобы быстрее начать разгрузку (рисунок 3.7).