9.12. транспортная задача
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 (т — число пунктов производства, п — число пунктов потребления).
Транспортную задачу можно решать симплекс-методом. Однако в силу специфики ее системы ограничений можно значительно упростить все этапы решения.
Обсуждение Справочник по математике для экономистов
Комментарии, рецензии и отзывы