Под термином «транспортные задачи» понимается широкий круг задач не только транспортного характера. Общим для них является, как правило, распределение ресурсов, находящихся у т производителей (поставщиков), по п потребителям этих ресурсов.
На автомобильном транспорте наиболее часто встречаются следующие задачи, относящиеся к транспортным:
• прикрепление потребителей ресурса к производителям;
• привязка пунктов отправления к пунктам назначения;
• взаимная привязка грузопотоков прямого и обратного направлений;
• отдельные задачи оптимальной загрузки промышленного оборудования;
• оптимальное распределение объемов выпуска промышленной
продукции между заводами-изготовителями и др.
Рассмотрим экономико-математическую модель прикрепления пунктов отправления к пунктам назначения. Имеются т пунктов отправления груза и объемы отправления по каждому пункту а1, а2,…аm . Известна потребность в грузах b1, b2,…bn по каждому из п пунктов назначения. Задана матрица стоимостей доставки по каждому варианту cij, i = , j = . Необходимо рассчитать оптимальный план перевозок, т. е. определить, сколько груза должно быть отправлено из каждого i–го пункта отправления (от поставщика) в каждый j-й пункт назначения (до потребителя) xij с минимальными транспортными издержками. В общем виде исходные данные представлены в табл. 7.1.
Таблица 7.1 – Исходные данные
Транспортная задача называется закрытой, если суммарный объем отправляемых грузов равен суммарному объему потребности в этих грузах по пунктам назначения :
(1)
Если такого равенства нет (потребности выше запасов или наоборот), задачу называют открытой, т. е.:
(2)
Для написания модели необходимо все условия (ограничения) и целевую функцию представить в виде математических уравнений. Все грузы из i-х пунктов должны быть отправлены, т. е.:
(3)
Все j-е пункты (потребители) должны быть обеспечены грузами в плановом объеме:
(4)
Суммарные объемы отправления должны равняться суммарным объемам назначения:
(5)
Должно выполняться условие неотрицательности переменных: xij ≥0, , i = , j = . Перевозки необходимо осуществить с минимальными транспортными издержками (функция цели):
(6)
В модели (3) — (6) вместо матрицы стоимостей перевозок (Cij) могут задаваться матрицы расстояний. В таком случае в качестве целевой функции рассматривается минимум суммарной транспортной работы. Как видно из выражения (5), уравнение баланса является обязательным условием решения транспортной задачи. Поэтому, когда в исходных условиях дана открытая задача, то ее необходимо привести к закрытой форме. В случае если
o потребности по пунктам назначения превышают запасы пунктов
отправления, то вводится фиктивный поставщик с недостающим
объемом отправления;
o запасы поставщиков превышают потребности потребителей, то
вводится фиктивный потребитель с необходимым объемом потребления.
Варианты, связывающие фиктивные пункты с реальными, имеют нулевые оценки. После введения фиктивных пунктов задача решается как закрытая.
Транспортным задачам присущи следующие особенности:
o распределению подлежат однородные ресурсы;
o условия задачи описываются только уравнениями;
o все переменные выражаются в одинаковых единицах измерения;
o во всех уравнениях коэффициенты при неизвестных равны единице;
o каждая неизвестная встречается только в двух уравнениях системы ограничений.
Транспортные задачи могут решаться симплекс-методом. Однако перечисленные особенности позволяют для транспортных задач применять более простые методы решения.