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

精品文档

销量 8 14 12 14 48 σ23 = C23 + C14 - (C13 + C24) = 3 + 11– ( 4 + 9 ) = 14-13=1 销地 产地 A1 A2 A3 销量 销地 产地 A1 A2 A3 销量 8 8 8 X31 8 B1 4 2 8 14 14 B2 12 10 5 12 B3 4 3 11 12 4 2 8 14 B4 11 9 6 产量 16 10 22 48 σ31 = C31+ C24 - (C21 +C34) = 8 + 9– ( 2 + 6 ) = 17-8 = 9 B1 4 2 8 14 14 B2 12 10 5 12 X33 B3 4 3 11 12 4 2 8 14 B4 11 9 6 产量 16 10 22 48 σ33 = C33 + C14 - (C13 + C34) = 11 + 11– ( 4 + 6 ) = 22-10 = 12

由于所有非基变量的检验数都大于零，说明当前方案是最优方案，最优解为： x11=12，x14=4，x21=8，x24=2，x32=14，x34=8。

2位势法

（1）首先对用最小元素法所确定的初始基本可行解进行检验。参见前面的计算结果，可知基变量分别为：x13，x14，x21，x23，x32，x34。

销地 产地 A1 A2 A3 销量 构造方程组：

u1 + v3 = c13 = 4 u1 + v4 = c14 = 11 u2 + v1 = c21 = 2 精品文档

8 8 B1 4 2 8 14 14 B2 12 10 5 10 2 B3 4 3 11 12 6 8 14 B4 11 9 6 产量 16 10 22 48 精品文档

u2 + v3 = c23 = 3 u3 + v2 = c32 = 5 u3 + v4 = c34 = 6

令自由变量u1 = 0 ，将其代入方程组，得：

u1 = 0，v3 = 4，v4 = 11，u3 = -5，v2 = 10，u2 = -1，v1 = 3，将其代入非基变量检验数： σij=Cij - (ui + vj)，得：

σ11=C11 - (u1 + v1) = 4 – ( 0 + 3 ) = 1 σ12=C12 - (u1 + v2) = 12 – ( 0 + 10 ) = 2 σ22=C22 - (u2 + v2) = 10 – ( -1 + 10 ) = 1 σ24=C24 - (u2 + v4) = 9 – ( -1 + 11 ) = -1 σ31=C31 - (u3 + v1) = 8 – ( -5 + 3 ) = 10 σ33=C33 - (u3 + v3) = 11 – ( -5 + 4 ) = 12 与闭回路法计算的结果相同。

（2）然后对用伏格尔法所确定的初始基本可行解进行检验。参见前面的计算结果，可知基变量分别为：x13，x14，x21，x24，x32，x34。 销地 产地 A1 A2 A3 销量 8 8 B1 4 2 8 14 14 B2 12 10 5 12 B3 4 3 11 12 4 2 8 14 B4 11 9 6 产量 16 10 22 48 构造方程组：

u1 + v3 = c13 = 4 u1 + v4 = c14 = 11 u2 + v1 = c21 = 2 u2 + v4 = c24 = 9 u3 + v2 = c32 = 5 u3 + v4 = c34 = 6

令自由变量u1 = 0 ，将其代入方程组，得：

u1 = 0，v3 = 4，v4 = 11，u3 = -5，v2 = 10，u2 = -2，v1 = 4，将其代入非基变量检验数： σij=Cij - (ui + vj)，得：

σ11=C11 - (u1 + v1) = 4 – ( 0 + 4 ) = 0 σ12=C12 - (u1 + v2) = 12 – ( 0 + 10 ) = 2 σ22=C22 - (u2 + v2) = 10 – ( -2 + 10 ) = 2 σ23=C23 - (u2 + v3) = 3 – ( -2 + 4 ) = -1 σ31=C31 - (u3 + v1) = 8 – ( -5 + 4 ) = 9 σ33=C33 - (u3 + v3) = 11 – ( -5 + 4 ) = 12 与闭回路法计算的结果相同。 精品文档

精品文档

四、解的改进（用闭回路法调整）

在使用最小元素法求得的初始方案中，由于σ24<0，说明当前方案不是最优，需要改进或调整。见表1中非基变量x24所在的闭回路，调整量为ε = min{2,6} = 2。调整过程见表2：

表1 销地 产地 A1 A2 A3 8 B1 4 2 8 14 B2 12 10 5 表2

销地 产地 A1 A2 A3 8 B1 4 2 8 14 B2 12 10 5 表3

销地 产地 A1 A2 A3 8 B1 4 2 8 14 B2 12 10 5 12 B3 4 3 11 4 2 8 B4 11 9 6 产量 16 10 22 10+2 2-2 B3 4 3 11 6-2 0+2 8 B4 11 9 6 产量 16 10 22 10 2 B3 4 3 11 6 8 B4 11 9 6 产量 16 10 22

调整后的结果如表3所示，此结果正好与使用伏格尔法求得的结果相同，因此最优性检验过程同前，由于非基变量的检验系数都大于等于零，因此该方案是最优方案，最优解为： x13=12，x14=4，x21=8，x24=2，x32=14，x34=8。将最优解代入到目标函数中，得总运费为（目标函数值）： 34cijxij?12?4?4?11?8?2?2?9?14?5?8?6?244 maxZ?i?1j?1

??精品文档

精品文档

P66： 9.

解：首先列出这一问题的产销平衡表，见表1。

表1

销地 产地 A1 A2 A3 销量 B1 3 1 7 3 B2 11 9 4 6 B3 3 2 10 5 B4 10 8 5 6 产量 7 4 9

一、该运输问题的数学模型为：

34

cijxij?3x11?11x12?3x13?10x14?x21 minz?i?1j?1

?9x22?2x23?8x24?7x31?4x32?10x33?5x34

?7?x11?x12?x13?x14

?x?4 ?21?x22?x23?x24 ?x31?x32?x33?x34?9?

?x11?x21?x31?3?

?x12?x22?x32?6

?x13?x23?x33?5 ??x14?x24?x34?6

?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??精品文档