Представление о том, что такое транспортная задача, у специалиста по исследованию операций и у менеджера отдела логистики очень сильно отличаются. С точки зрения менеджера, транспортные задачи – это любые задачи, связанные оптимизацией перевозок.
С точки зрения специалиста по исследованию операций, транспортная задача – это специальный вид задачи линейной оптимизации, для которой, в силу ее формулировки и в виду очень специальных ограничений, существуют исключительно эффективные алгоритмы решения.
В этот тип попадают и такие реальные задачи, в которых ничего никуда не перевозится. Кроме транспортных задач такими полезными свойствами обладают, например, задачи о кратчайшем маршруте в сети дорог (используются в системах глобального позиционирования GPS для прокладывания маршрутов).
Транспортная задача.
Классическая транспортная задача имеет целью минимизацию транспортных издержек при перевозках однотипных грузов от нескольких поставщиков (с различных складов), расположенных в разных местах, к нескольким потребителям. При этом, в транспортной задаче, принимают в расчет только переменные транспортные издержки, т.е. считают, что суммарные издержки пропорциональны количеству перевезенных единиц груза.
Постановка транспортной задачи
При постановке транспортной задачи необходимо прежде всего задать таблицу транспортных издержек для перевозок единицы груза cij от i-го поставщика к j-му потребителю. Эта таблица имеет m строк (по числу поставщиков) и n столбцов (по числу потребителей).
Таблица перевозок xij имеет те же размеры (m x n) и содержит переменные решения.
Необходимо также задать запасы поставщиков, готовые к вывозу и величины заказов потребителей.
В транспортной задаче предполагается, что необходимо вывести запасы каждого i-го поставщика и удовлетворить заказ каждого j-го потребителя.
Это возможно только если сумма запасов всех поставщиков равна сумме заказов всех потребителей.
Запасы всех постащиков
=
Заказы всех потребителей
Это важнейшее условие применимости эффективных алгоритмов.
Ограничения.
Ограничения транспортной задачи имеют очень простой вид:
сумма переменных решения вдоль каждой i-ой строки должна быть равна запасу поставщика Si, а сумма переменных решения вдоль каждого j-го столбца должна быть равна заказу соответствующего потребителя Dj
Целевая функция
Целевая функция - это суммарные издержки. Чтобы найти суммарные издержки, необходимо найти суммы произведений каждой строки таблицы транспортных издержек на соответствующую строку таблицы перевозок и сложить их, суммируя по i от 1 до m.
Если задача сбалансирована и никаких других ограничений, кроме упомянутых выше нет, Поиск решения использует эффективный алгоритм решения для этой задачи, причем, если запасы и заказы выражены целыми числами, то и переменные решения xij получатся целыми, даже если не требовать этого специально.
Несбалансированность в транспортной задаче
Если сумма запасов превышает сумму заказов (излишек запасов) или, наоборот сумма запасов меньше, чем сумма заказов (дефицит запасов) необходимо сбалансировать задачу.
Если
Запасы всех постащиков
>
Заказы всех потребителей
нужно добавить в таблицу транспортных издержек и в таблицу перевозок по одному лишнему столбцу.
Это можно трактовать так, как если бы появился еще один «фиктивный» потребитель.
Для решения задачи нужно потребовать:
Заказ Фиктивного потребителя = Запасы всех постащиков - Заказы всех потребителейИздержки перевозок грузов к Фиктивному покупателю от любого поставщика = 0 .
При этом получится сбалансированная транспортная задача. Переменные решения в последнем столбце дадут количество грузов, которые должны остаться на каждом из складов.
Если
Запасы всех постащиков
<
Заказы всех потребителей
нужно добавить в таблицу транспортных издержек и в таблицу перевозок по одной лишней строке.
Это можно трактовать так, как если бы появился еще один «фиктивный» поставщик.
Для решения задачи нужно потребовать:
Запас Фиктивного поставщика = Заказы всех потребителе - Запасы всех поставщиковИздержки перевозок грузов от Фиктивного поставщика к любому покупателю = 0 .
При этом получится сбалансированная транспортная задача. Переменные решения в лишней строчке – это тот объем грузов, которые не получит каждый потребитель.
Несбалансированные транспортные задачи можно решать и просто заменив в соответствующих ограничениях знаки равенств на знаки нестрогих неравенств. Современный MS Excel корректно решает такие задачи. При этом удается сформулировать задачу так, что решение заведомо получается целочисленным даже при отсутствии соответствующих ограничений. Разумеется, задача в этих случаях решается очень быстро и при большом числе переменных, так как для решения по-прежнему используется алгоритм симплекс-метода.
Запрещение определенной перевозки
Иногда возникает необходимость запретить перевозку от i-го поставщика к j-му потребителю (ремонт дороги, неплатеж и пр.). В этом случае можно просто ввести ограничение xij =0. Однако, это означает невозможность использования эффективных «транспортных» алгоритмов решения.
Чтобы сохранить форму транспортной задачи и учесть этот запрет, достаточно в таблице транспортных издержек заменить cij на очень большое число (на порядок большее, чем максимальная цена перевозки в таблице транспортных издержек). Фактически это будет означать, что оптимизационный алгоритм наверняка примет соответствующее значение перевозки xij равным нулю, поскольку перевозка по этому маршруту будет крайне невыгодна.
Примеры решения транспортных задач
1
Мини-кейс: Ремонт дорог
С восьми асфальтобетонных заводов должен вывозиться асфальт для ремонта пяти больших участков автодорог области. Менеджер подрядной организации хочет минимизировать транспортные расходы для данных условий.
Транспортные издержки перевозкок указаны в таблице:
Участок A
Участок B
Участок C
Участок D
Участок E
АБЗ 16
2 860
3 220
3 100
2 275
3 220
АБЗ 17
3 145
2 140
1 900
2 050
2 290
АБЗ 18
2 245
2 050
2 785
2 650
2 365
АБЗ 19
2 815
1 960
2 590
2 080
2 725
АБЗ 20
2 770
3 250
2 635
2 275
3 400
АБЗ 21
2 200
2 590
3 265
2 560
3 250
АБЗ 22
2 110
2 290
3 085
2 110
2 245
АБЗ 23
2 005
2 275
2 500
2 950
2 785
Заказы дорожно-строительных бригад на следующую неделю:
Участок A
Участок B
Участок C
Участок D
Участок E
Количество машин
160
186
123
165
135
Заводы в состоянии предоставить за это время:
Источник
АБЗ 16
АБЗ 17
АБЗ 18
АБЗ 19
АБЗ 20
АБЗ 21
АБЗ 22
АБЗ 23
Количество машин
128
104
76
78
60
117
130
56
Каковы наименьшие транспортные издержки?
Какие участки недополучат заказанный ими асфальт и в каком количестве?
Найдите разницу между наилучшим и наихудшим планом перевозок.
Выяснилось, что из-за аварийного состояния моста перевозка асфальта с АБЗ 20 на участок D по прямому маршруту невозможна. Объездной маршрут увеличивает стоимость рейса на 1000 рублей. Как из-за этого возрастут транспортные расходы?
Решение задачи с помощью MS Excel
Проверим, сбалансированна ли задача. Сумма всех Заказов больше, чем производительность всех заводов. Поэтому используем при записи ограничения для заказов нестрогое равенство.
