第六章运输问题 在线性规划问题中，有一类特殊类型的问题一运输问题。这类问题主要研究把某种 物资从若干个产地调运到若干个销地，每个产地的供应量和每个销地的销售量及从一个 产地到一个销地的运输费用已知，要求确定一个总运费最少的方案， 6.1运输问题的线性规划模型 引例设某种物资（如粮食，棉花，煤炭等）有m个产地A1,42,,Am,产量分别为 a1,a1,am个单位：另外有n个销地B1,B2,,Bn,销量分别为b1,b1,,bn个单位。 又假设产销是平衡的，即 三- 此外，由产地A:向销地B运输每单位货物的运价为，问应该如何调运这种货物才能 使总的运费最小？ 解设为由产地A:向销地B调运这种货物的数量。连同单位运价可以列成 表6-1和表6-2 单位运价表 表6-1 销地 B Bn 产地 4 92 21 C2n Am Cml Cm2 Cmn 平衡表 表6-2 销地 B2 产量 产地 11 11 12 A2 x22 0 A 销量 02 由A,运出去的物资总量应等于A,的产量，即 xy=a,i=1,2.…m 1￾✂✁✂✄ ☎✂✆✂✝✂✞ ✟✡✠✡☛✡☞✡✌✡✍✡✎✑✏, ✒✡✓✡✔✡✕✡✖✡✔✡✗✡✘✍✡✎ —- ✙✡✚✍✡✎✡✛✢✜✔ ✍✡✎✡✣✡✤✡✥✡✦✡✧✡★✡✩ ✪✬✫✬✭✬✮✬✯✬✰✬✱✬✲✬✳✙✬✴✮✬✯✬✰✬✵✬✲, ✶ ✰✬✱✬✲✘✬✷✬✸✬✹✬✺✬✶✰✬✵✬✲✘ ✵✬✻✹✬✼✭ ✓ ✰ ✱✡✲✴✡✓✰✡✵✡✲✘✡✙✡✚✡✽✡✾✑✿❁❀, ✤✡❂✡❃✡❄✓ ✰✡❅✙✡✽✡❆✡❇✡✘✡❈✡❉✛ §6.1 ❊●❋●❍●■●❏●❑●▲●▼●◆●❖◗P ❘✡❙ ❚✡★✡✩✪✡✫ (❯✡❱✡❲, ❳✡❨, ❩✡❬✡❭) ✒ m ✰✡✱✡✲ A1, A2, . . . , Am, ✱✹✡❪✡❫✡❴ a1, a1, . . . , am ✰✡❵✡❛; ❜✡❝✡✒ n ✰✡✵✡✲ B1, B2, . . . , Bn, ✵✹✡❪✡❫✡❴ b1, b1, . . . , bn ✰✡❵✡❛✛ ❞✡❡❚✱✡✵✡❢✡❣✡❤✘, ✐ Xm i=1 ai = Xn j=1 bj . ❥❝, ❦ ✱✡✲ Ai ❧✵✡✲ Bj ✙✡✚✡✶❵✡❛✡♠✡✪✘✡✙✡♥✡❴ cij ✛♦✍✸✡♣✡❯✡q✳✙ ✜✡✩♠✡✪✡r✡s t✡❅✘✡✙✡✽✡❆✡✉? ✈ ❚ xij ❴✑❦ ✱✡✲ Ai ❧✵✡✲ Bj ✳✙ ✜✡✩♠✡✪✘✡✇✡✹, ①✡②❵✡❛✙✡♥ cij ③✡④✡⑤✡⑥ ⑦ 6-1 ✺⑦ 6-2✛ ❵✡❛✙✡♥⑦ ⑦ 6–1 ✵✡✲ B1 B2 . . . Bn ✱✡✲ A1 c11 c12 . . . c1n A2 c21 c22 . . . c2n . . . . . . . . . . . . . . . Am cm1 cm2 . . . cmn ❣✡❤✡⑦ ⑦ 6–2 ✵✡✲ B1 B2 . . . Bn ✱✹ ✱✡✲ A1 x11 x12 . . . x1n a1 A2 x21 x22 . . . x2n a2 . . . . . . . . . . . . . . . . . . Am xm1 xm2 . . . xmn am ✵✹ b1 b2 . . . bn ❦ Ai ✙✡⑧✡⑨✡✘✪✡✫✡❅✹✡✸✡❭✡⑩ Ai ✘✱✹, ✐ Xn j=1 xij = ai ,i = 1, 2, . . . , m. 1