第3章 运输问题
3.1 判断表3-l 和表3-2中给出的调运方案能否作为用表上作业法求解时的初始解?为什么?
表3-1 表3-2
解：表3-l 中有5个基格，而要作为初始解，应有m+n-l=3+4-1=6个基格，所以表3-l 给出的调运方案不能作为表上作业法的初始解；
表3-2中，有10个数基格，而理论上只应有m+n-l=9个，多出了一个，所以表3-2给出的调运方案不能作为表上作业法的初始解。

3.2 表3-3和表3-4中，分别给出两个运输问题的产销平衡表和单位运价表，试用伏格尔(Vogel)法直接给出近似最优解。

表3-3 表3-4
解：（1）第一步：在表3-3中分别求各行和各列的最小运价和次小运价的差额，并分别填入该表的最右列和最下行，如表3-5所示。

表3-5
第二步：从行差额或列差额中选出最大者，选择它所在行或列中的最小元素。

在表3-5中,第3列是最大差额所在列。

第3列中最小元素为1，可确定产地2的产品优先供应销地3的需要，得表3-6。

同时将运价表中的第3列数字划去，如表3-7所示。

表3-6 表3-7
第三步：对表3-7中未划去的元素再分别计算出各行、各列的最小运价和次小运价的差额，并填入该表的最右列和最下行。

重复第一、二步，直到给出初始解为止，初始解如表3-8所示。

表3-8
（2）第一步：在表3-4中分别计算各行和各列的最小运价和次小运价的差额，并分别填入该表的最右列和最下行，如表3-9所示。

表3-9
第二步：从行或列差额中选出最大者，选择它所在行或列中的最小元素。

在表3-9中第3列是最大差额所在列。

第3列中最小元素为3，可确定产地1的产品优先供应销地3的需要。

同时将运价表中的第1行数字划去，如表3-10所示。

表3-10
第三步：对表3-10中未划去的元素再分别计算出各行、各列的最小运价和次小运价的差额，填入该表的最右列和最下行。

重复第一、二步，直到给出初始解为止，初始解见表3-10的单位运价中格子的右上方方格中的数据。

3.3 用表上作业法求表3-11至表3-14中给出的运输问题的最优解(表中数字M为任意大正数)。

表3-11 表3-12
表3-13 表3-14
解：（1）解表3-11 第一步：用伏格尔法求初始可行解（过程类似于上一题，不再赘述），求得的初始解如表3-15所示。

表3-15
第二步：用位势法进行最优解的判断。

在对应于表3-15的数字格处填入单位运价，并增加一行一列，在行中填入j v ，在列中填入i u 。

令10v =，并按照i j ij u v c +=(,i j B ∈)求出所有的i u 和j v ，如表3-16所示。

对于表3-16中的空格，依据()ij ij i j c u v σ=−+(,i j N ∈)计算其检验数，如表3-17所示。

表3-16 表3-17
由表3-17可知，所有空格处的检验数均为非负。

所以，表3-15中的运输方案，即为此问题的最优调运方案，最小运价为32。

由于非基变量的检验数中34
0σ=，所以该运输问
题有无穷多最优解。

（2）解表3-12
第一步：用伏格尔法求初始可行解，求得的初始解，如表3-18所示。

表3-l8
第二步：用位势法进行最优解的判断。

在对应于表3-18的数字格处填入单位运价，并增加一行一列，在行中填入j v ，在列中填入i u 。

令10u =，按照i j ij u v c +=求出所有的i u 和j v ，并依据()ij ij i j c u v σ=−+计算所有空格处的检验数，计算结果如表3-19所示。

表3-19
由表3-19可知，所有空格处的检验数均为非负。

所以，表3-18中的运输方案即为此。