当前位置：文档库 › 胡运权习题及答案习题解答(3)

胡运权习题及答案习题解答(3)

习题解答（3）

7.3试判断表1和表2中给出的调运方案可否作为表上作业法迭代时的基可行解？

解：表1给出的调运方案不能作为基可行解。不满足存在1

m个数字格。

表2给出的调运方案不能作为基可行解。不满足存在1

m个数字格。

.3表3示出一个运输问题及它的一个解，试问：（1）表中给出的解是否为最优解？

请用位势法进行检验。（2）若价值系数

c由1变为3，所给的解是否仍为最优解？若不

是，请求出最优解。（3）若所有价值系数均增加1，最优解是否改变？为什么？（4）若所有价值系数均乘以2，最优解是否改变？为什么？（5）写出该运输问题的对偶问题，并给出其对偶问题的最优解。

解：（1）各空格（非基变量的）检验数以[ ]在下表中表出，因它们均0>，故原给出的

（2）当324=c 时，用位势法算出各行各列的位势，并在下表中填入j i v u ,相应的值。计算出的各空格的检验数也以[ ]在下表中给出

因01,022322<-=<-=σσ，从而22x 为换入变量，作闭回路

22424333312122B A B A B A B A B A B A B A →→→→→→，且偶数顶点处的最小运输

量为.2故24x 为换出变量，同上算出各行各列的位势以及各空格的检验数，并在下表中给

因各空格的检验数均0>，故此表给出的解即为324=c 时的最优解，且最优值为.43=z （3）、（4）的最优解均不变。因为在此两种情况下，各空格的检验数的非负性未改变，但目标函数值即总运费增加。

（5）原问题为：∑∑===

min i j ij ij

x c

st. ???

???

??==≥=++=++=++=++=+++=+++=+++)4,3,2,1.3,2,1(,03

658

41083424143323133222123121113433323124232221

14131211j i x x x x x x x x x x x x x x x x x x x x x x x x x ij

其中 ),(ij c C = .15

31621

6414????

?=C 故对偶问题为：432132136584108max v v v v u u u w ++++++= st. ???

???

????

???

??==≤+≤+≤+≤+≤+≤+≤+≤+≤+≤+≤+≤+.4,3,2,1.3,2,1,,1

5731

6216414

433323

134

322212413121

11j i v u v u v u v u v u v u v u v u v u v u v u v u v u j i

因原问题的最优函数值 ,43=*

z 而 )

0,4,1,0,1,1,0(),,,,,,(4321321==v v v v u u u Y 是对偶问题的一个可行解，且*

==z w 43，故Y 即为所求对偶问题的最优解。

12.3 1，2，3三个城市每年需分别供应电力320，12.3 1，2，3三个城市每年需分

别供应电力320，250和350单位，由Ⅰ，Ⅱ两个电站提供，它们的最大可供电量分别为400个单位和450个单位，单位费用（元）如下表所示。由于需要量大于可供量，决定城市1的供应量可减少0单位~30单位，城市2的供应量不变，城市3的供应量不能少于270单位，试求总费用最低的分配方案（将可供电量用完）。

于求，故虚拟一个电站Ⅲ，其可供电量为920-850=70个单位，其单位运价如下表所示。

因表中所有非基变量的检验数均,0>故表中的解是最优解，且最少运费为14650元。