Транспортные задачи линейного программирования. Постановка задачи

Под термином «транспортные задачи» понимается широкий круг задач не только транспортного характера. Общим для них является, как правило, распределение ресурсов, находящихся у m производителей (поставщиков), по n потребителям этих ресурсов.

На автомобильном транспорте наиболее часто встречаются следующие задачи, относящиеся к транспортным:

– прикрепление потребителей ресурса к производителям;

– привязка пунктов отправления к пунктам назначения;

– взаимная привязка грузопотоков прямого и обратного направлений;

– отдельные задачи оптимальной загрузки промышленного оборудования;

– оптимальное распределение объемов выпуска промышленной продукции между заводами-изготовителями и др.

Рассмотрим экономико-математическую модель прикрепления пунктов отправления к пунктам назначения. Имеются m пунктов отправления груза и объемы отправления по каждому пункту а₁, а₂,..., а_m. Известна потребность в грузах b₁,b₂,…,b_n по каждому из n пунктов назначения. Задана матрица стоимостей доставки по каждому варианту c_ij, i = 1, m, j = 1, n. Необходимо рассчитать оптимальный план перевозок, т. е. определить, сколько груза должно быть отправлено из каждого i -го пункта отправления (от поставщика) в каждый j -й пункт назначения (до потребителя) x_ij с минимальными транспортными издержками.

В общем виде исходные данные представлены в табл.9.1.

Транспортная задача называется закрытой, если суммарный объем

отправляемых грузов равен суммарному объему потребности в этих грузах по пунктам назначения :

= (9.1)

Таблица 9.1

Поставщики	Потребители	Запасы груза, т.
B1	B2	…	Bn
A1		c11		c12		…		c1n	a1
x11	x12	…	x1n
A2		c21		c22		…		c2n	a2
x21	x22	…	x2n
A3		c31		c32		…		c3n	a3
x31	x32	…	x3n
…		…		…		…		…	…
…	…	…	…
Am		cm1		cm2		…		cmn	am
xm1	xm2	…	xmn
Потребность в грузе,т.	b1	b2	…	bn

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

(9.2)

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

= i =1, m (9.3)

Все i пункты (потребители) должны быть обеспечены грузами в плановом объеме:

= j =1, n (9.4)

Суммарные объемы отправления должны равняться суммарным объемам назначения:

= (9.5)

Должно выполняться условие неотрицательности переменных: x _ij ≥ 0, i = 1, m; j = 1, n. Перевозки необходимо осуществить с минимальными транспортными издержками (функция цели):

Z min = (9.6)

В модели (9.3) - (9.6) вместо матрицы стоимостей перевозок (с_ij) могут задаваться матрицы расстояний. В таком случае в качестве целевой функции рассматривается минимум суммарной транспортной работы. Как видно из выражения (9.5), уравнение баланса является обязательным условием решения транспортной задачи. Поэтому, когда в исходных условиях дана открытая задача, то ее необходимо привести к закрытой форме. В случае если:

- потребности по пунктам назначения превышают запасы пунктов отправления, то вводится фиктивный поставщик с недостающим объемом отправления;

- запасы поставщиков превышают потребности потребителей, то вводится фиктивный потребитель с необходимым объемом потребления.

Варианты, связывающие фиктивные пункты с реальными, имеют нулевые оценки. После введения фиктивных пунктов задача решается как закрытая.

Транспортным задачам присущи следующие особенности:

- распределению подлежат однородные ресурсы;

- условия задачи описываются только уравнениями;

- все переменные выражаются в одинаковых единицах измерения;

- во всех уравнениях коэффициенты при неизвестных равны единице;

- каждая неизвестная встречается только в двух уравнениях системы ограничений.

Транспортные задачи могут решаться симплекс-методом. Однако перечисленные особенности позволяют для транспортных задач применять более простые методы решения.