圣才电子书 www.100xuexi.com 十万种考研考证电子书、题库视频学习平台 第4章 运输问题
4.1判断表4-l和表4-2中给出的调运方案能否作为用表上作业法求解时的初始解?为什么?
表4-1 表4-2
解：表4-l中有5个基格，而要作为初始解，应有m+n-l=3+4-1=6个基格，所以表4-l给出的调运方案不能作为表上作业法的初始解；
表4-2中，有10个基格，而理论上只应有m+n-l=9个，所以表4-2给出的调运方案不能作为表上作业法的初始解。
4.2判断下列说法是否正确。
（1）在运输问题中，只要任意给出一组含（m+n+1）个非零的{xij}，且满足
，就可以作为一个初始基可行解；
（2）表上作业法实质上就是求解运输问题的单纯形法；
（3）如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k，最优调运方案将不发生变化；
（4）运输问题单位运价表的全部元素乘上一个常数k（k>0），最优调运方案将不发生
1 / 19
圣才电子书 www.100xuexi.com变化。
十万种考研考证电子书、题库视频学习平台 解：（1）×（2）√（3）×（4）√
4.3用表上作业法和伏格尔（Vogel）法求表4-3、表4-4中给出的运输问题的最优解和近似最优解（表中数字M为任意大正数）。
表4-3 表4-4
解：（1）解表4-3
由于表4-3中产大于销，因此需要增添一个假想的销地“己”，其运价为0，销量为2，如表4-5所示：
2 / 19
圣才电子书 www.100xuexi.com 十万种考研考证电子书、题库视频学习平台 表4-5
第一步：用伏格尔法求得初始可行解如表4-6所示：
表4-6
第二步：用位势法进行最优解的检验。在对应于表4-6的数字格处填入单位运价，并增加一行一列，在行中填入vj，在列中填入ui。令u1=0，按照ui+vj=cij（i,j?B）求出所有的ui和vj，并依据
?ij=cij?(ui+vj)（i,j?N）计算所有空格处的检验数，计算结果如表4-7所示：
表4-7
3 / 19
圣才电子书 www.100xuexi.com 十万种考研考证电子书、题库视频学习平台
由表4-7可知，所有空格处的检验数均为非负。所以，表4-6中的运输方案即为此问题的最优调运方案，最小运价为90。由于非基变量的检验数中?16=?26=0，所以该运输问题有无穷多最优解。
（4）解表4-4
由于表4-4中产大于销，因此需要增添一个假想的销地“己”，其运价为0，销量为40，如表4-8所示：
表4-8
第一步：用伏格尔法求得初始可行解如表4-9所示：
表4-9
4 / 19
圣才电子书 www.100xuexi.com 十万种考研考证电子书、题库视频学习平台
第二步：用位势法进行最优解的判断。在对应于表4-7的数字格处填入单位运价，并增加一行一列，在行中填入vj，在列中填入ui。令v1=0，按照ui+vj=cij（i,j?B）求出所有的ui和vj，并依据
?ij=cij?(ui+vj)（i,j?N）计算所有空格处的检验数，计算结果如表4-10所示：
表4-10
在表4-10中，所以，表4-9中的运输方案不是此问题的最优调运方案，?33=?7?0。需进一步调整。
第三步：利用闭回路法进行解的改进。
从表4-10中的空格（3，1）出发点作一闭回路，并对闭回路上的点进行正负编号，如表4-11所示：
5 / 19
运筹学教材编写组《运筹学》课后习题-运输问题(圣才出品)
