8.1. Постановка задачи
На автомобильном транспорте наиболее часто встречаются следующие задачи, относящиеся к транспортным:
прикрепление потребителей ресурса к производителям;
привязка пунктов отправления к пунктам назначения;
взаимная привязка грузопотоков прямого и обратного направлений;
отдельные задачи оптимальной загрузки промышленного оборудования;
оптимальное распределение объемов выпуска промышленной продукции между заводами-изготовителями и др.
Рассмотрим экономико-математическую модель прикрепления пунктов отправления к пунктам назначения.
Имеются т пунктов отправления груза и объемы отправления по каждому пункту аь а2, ..., ат. Известна потребность в грузах Ьь Ь2, Ьп по каждому из п пунктов назначения. Задана матрица стоимостей доставки по каждому варианту Су, і = l,m,j = I, п. Необходимо рассчитать оп-Таблица 8.1
Исходные данные Поставщики Потребители Запасы (объемы отправления) Вх в2 ... Вп л. С\\ С\2
*12 С\п
х\п А2 С21
*21 ^22
*22 с2п
х2п 02 ... ... * Ат ст\
Хт\ Ст2
хт2 Сщп
Хтп Потребность Ьх Ь2 ьп
тимальный план перевозок, т. е. определить, сколько груза должно быть отправлено из каждого /-го пункта отправления (от поставщика) в каждый у-й пункт назначения (до потребителя) Ху с минимальными транспортными издержками.
В общем виде исходные данные представлены в табл. 8.1.
Транспортная задача называется закрытой, если суммарный
т
і
М J
объем отправляемых грузов
равен суммарному объему по^
п
Ibj
U=i .
требности в этих грузах по пунктам назначения
т п
(8.1)
X Д/ = X Ь;.
/=1 y=iЕсли такого равенства нет (потребности выше запасов или наоборот), задачу называют открытой, т. е.:
(8.2)
т п
/=1 у=1
Для написания модели необходимо все условия (ограничения) и целевую функцию представить в виде математических уравнений. Все грузы из / пунктов должны быть отправлены, т. е.:
(8.3)
j?Xy=ah / = 1,/я.
у=і
Все у пункты (потребители) должны быть обеспечены грузами в плановом объеме:
т —
lXjj=bj, У = (8.4)
/=1
Суммарные объемы отправления должны равняться суммарным объемам назначения:
т п
Xai = Xbj. (8.5)
/=1 у=1
Должно выполняться условие неотрицательности переменных: Ху > 0, / = 1,/я; j = 1 ,п. Перевозки необходимо осуществить с минимальными транспортными издержками (функция цели):
т п
zm{n = 2 2 (8.6)
/=1у=1
В модели (8.3) — (8.6) вместо матрицы стоимостей перевозок (с,у) могут задаваться матрицы расстояний. В таком случае в качестве целевой функции рассматривается минимум суммарной транс-портной работы. Как видно из выражения (8.5), уравнение баланса является обязательным условием решения транспортной задачи. Поэтому, когда в исходных условиях дана открытая задача, то ее необходимо привести к закрытой форме. В случае если
потребности по пунктам назначения превышают запасы пунктов отправления, то вводится фиктивный поставщик с недостающим объемом отправления;
запасы поставщиков превышают потребности потребителей, то вводится фиктивный потребитель с необходимым объемом потребления.
Варианты, связывающие фиктивные пункты с реальными, имеют нулевые оценки. После введения фиктивных пунктов задача решается как закрытая.
Транспортным задачам присущи следующие особенности:
распределению подлежат однородные ресурсы;
условия задачи описываются только уравнениями;
все переменные выражаются в одинаковых единицах измерения;
во всех уравнениях коэффициенты при неизвестных равны единице;
каждая неизвестная встречается только в двух уравнениях си-стемы ограничений.
Транспортные задачи могут решаться симплекс-методом. Однако перечисленные особенности позволяют для транспортных задач применять более простые методы решения.