Лекция 4–6

8. Транспортная задача

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

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

Один из наиболее распространенных методов решения транспортной задачи – метод потенциалов, полностью использующий особенности условий этой задачи и приводящий к цели значительно быстрее и проще, симплекс-метод.

Транспортная задача формулируется так:

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

	b1	b2	…	…	bn
a1	c11 x11	c12 x12	…	…	c1n x1n
a2	c21 x21	c22 x22	…	…	c2n x2n
…	…	…	…	…	…
…	…	…	…	…	…
am	cm1 xm1	cm2 xm2	…	…	cmn xmn

(1.4.1)

Совокупность чисел, т.е. матрицу, будем называтьпланом перевозок, а матрицу матрицей транспортных издержек.

План называется допустимым, если числа удовлетворяют следующим естественным ограничениям:

(1.4.2)

(;),

(),

(),

в которых первые равенств означают, что из каждого пункта производства вывозится весь продукт, а последниеравенств означают, что каждый пункт потребления полностью удовлетворяется.

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

(1.4.3)

минимальна.

Если система (1.4.2) совместна,

,

таким образом, условие

(1.4.4)

необходимо для совместности (1.4.2). Условие (1.4.4) является и достаточным для совместности (1.4.2). В самом деле, при выполнении условия (1.4.4) значения

(;),

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

Таким образом, транспортная задача относится к задачам линейного программирования и решается алгоритмом симплекс-метода. Однако ввиду исключительной практической важности и специфики ограничений (1.4.2):

а) ограничения заданы в виде уравнений,

б) каждая неизвестная входит лишь в два уравнения,

в) коэффициенты при неизвестных – единицы, для ее решения созданы специальные алгоритмы, значительно менее громоздкие, чем алгоритм симплекс-метода. Один из них – м е т о д п о т е н ц и а л о в – представляет собой приспособление общего метода Л,В, Канторовича для решения транспортной задачи.

Другой, так называемый в е н г е р с к и й м е т о д усовершенствован для решения частного случая транспортной задачи – задачи о назначениях (или о выборе).