Справочник по математике для экономистов

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

Формулировка транспортной задачи. Имеется т пунктов П1, П2, Пт, в которых производится некоторый однородный продукт соответственно в количествах ау, а2, — ... , ат единиц. Этот продукт необходимо доставить в л пунктов потребления Qlt Q2, .... Qn, потребности которых в продукте соответственно составляют Ъх. Ь2, .... Ь„ единиц. Стоимость перевозки из каждого пункта производства П, (і— 1, 2, т) в каждый пункт потребления QjQ—, 2, п) известна и равна Cjj единиц. Требуется найти план перевозок, при котором были бы удовлетворены все потребности, а суммарная стоимость всех перевозок была бы наименьшей.

т л

Очевидно, что если а'< Z то транспортная задача нераз-решима.

т          я        /            т п

Можно считать, что ХЙ| = Х*> [если £лі>Х     то вводят ■-і     >-1           і-і >-і дополнительный (фиктивный) пункт потребления с потребно-

стью, равной Yja>~Yj   единиц )■

Обозначим через х,-, количество продукта, перевозимого из пункта Пі (і=, 2, т) в пункт Qj (j=l, 2, и). Если/— стоимость перевозок по этому плану, то

т л

f= X I СУ*У

■-і;-i

При этом из пункта П, (i=l, 2, /и) будет вывезено всего J^Xjj единиц продукта, а в пункт Qj(j=l, 2,       п) завезено

m

J] Xjj единиц продукта. , Значит,

л т

£ х,-,=д,, i= 1, 2,     m; £ x,j=bhj=, 2, п. j-i /-і

Таким образом, транспортная задача является задачей линейного программирования в канонической форме:

 

/=EZWmin), (9-39) i-iy-i

8-421 225

2>y=e„f=l,2    m,        (9.40)

j-i

2, ...,л,  (9.41)

XiJ>0, f= 1, 2,     т;У= 1, 2      n.         (9.42)

Свойства транспортной задачи 1°. Транспортная задача (9.39) — (9.42) имеет оптимальное

Л! в

решение тогда и только тогда, когда X fl<= Z

2°. Если все числа alt а2, .... от и bir Ьг, .... А„ — целые, причем

т я

Ха,= £б,, ТО транспортная задача (9.39) — (9.42) имеет опти-i-i j-i

мальное решение с целыми координатами.

3°. Ранг системы векторов условий транспортной задачи (9.39) — (9.42) равен т + п— 1 (т — число пунктов производства, п — число пунктов потребления).

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