运筹学(胡运权版)第三章运输问题课后习题答案

P66： 8.某部门有3个生产同类产品的工厂（产地），生产的产品由4个销售点出售，各工厂A1， A2，A3的生产量、各销售点B1，B2，B3，B4的销售量（假定单位为t）以及各工厂到销售点的单位运价（元/t）示于下表中，问如何调运才能使总运费最小？ 表

销地 产地 A1 A2 A3 销量 B1 4 2 8 8 B2 12 10 5 14 B3 4 3 11 12 B4 11 9 6 14 产量 16 10 22 48 解：一、该运输问题的数学模型为：

34

cijxij?4x11?12x12?4x13?11x14?2x21 minz?i?1j?1

?10x22?3x23?9x24?8x31?5x32?11x33?6x34

?16?x11?x12?x13?x14

?x?10 ?21?x22?x23?x24 ?x31?x32?x33?x34?22?

?x11?x21?x31?8?

?x12?x22?x32?14

?x13?x23?x33?12 ??x14?x24?x34?14

?xij?0,i?1,2,3;j?1,2,3,4 ?

xx12x13x14x21x22x23x24x31x32x33x3411 7?12可以证明：约束矩阵的秩为r (A) = 6. 从而基变量的个数为 6.

???1111???1111???1111???11?1??1?11??111????111??二、给出运输问题的初始可行解（初始调运方案） 1. 最小元素法

思想：优先满足运价（或运距）最小的供销业务。 销地 产地 A1 A2 A3 销量 销地 产地 A1 A2 8 8 ① 8 8 ① B1 4 2 8 14 B2 12 10 5 B3 4 3 11 12 14 B4 11 9 6 8 产量 16 10 2 22 48 B1 4 2 8 B2 12 10 5 14 2 B3 4 3 11 10 B4 11 9 6 14 8 产量 16 10 ② 22 48 A3 销量 销地 产地 A1 A2 B1 8 8 ① 4 2 8 B2 12 10 5 14 10 2 B3 4 3 11 10 ③ B4 11 9 6 14 产量 16 6 10 10 8 22 48 ② A3 销量

销地 产地 A1 A2 8 8 ① B1 4 2 8 14 14 ④ B2 12 10 5 10 2 B3 4 3 11 10 ③ 14 B4 11 9 6 产量 16 6 10 10 8 22 8 14 48 ② A3 销量 销地 产地 A1 A2 A3 销量 销地 产地 A1 A2 A3 销量 B1 8 8 ① 4 2 8 14 B2 12 10 5 14 ④ 10 2 B3 4 3 11 10 ③ 8 B4 11 9 6 产量 16 6 10 10 8 22 0 14 48 ⑤ ② 14 6 B1 8 8 4 2 8 14 B2 12 10 5 14 ④ 10 2 B3 4 3 11 10 ③ 6 8 B4 11 9 6 产量 16 0 10 10 0 8 22 0 14 48 ⑥ ② ⑤ ① 此时得到一个初始调运方案（初始可行解）： x?10,x?6,x21?8,x23?2,x32?14,x34?8,1413

其余（非基）变量全等于零。此解满足所有约束条件，且基变量（非零变量）的个数为6（等于m+n-1=3+4-1=6).

总运费为（目标函数值） 34 Z?cijxij?10?4?6?11?8?2?2?3?14?5?8?6?246 14 0 ⑥ ??i?1j?1