x21?min?a2,b1??min?3,5??3. 这个格子填上数后，B1的要求满足了，可用线划去该列.于是只需考虑B2、B3、B4的需求. 从表3-5看到，在未划线的格子中
cij最小者是c24?c33?2. 任选一个，比如考虑c33所在的格子. 此处的供求情况是：最多可供7，但最多需要4. 于是应填入的数是x33?min?a3,b3??min?7,4??4. 这样B3的需求也满足了，用线划去该列.后面只需考虑B2和B4的需求. 这时最小的cij（≠c11，≠c13）是c24=2. 此处，最大可供量为5－3=2（c21处已占用了），需求量为6，从而应令x24?min?a2?x21,b4??min?5?3,6??2. 这时A2的供应量用完了，用线划去该行. 后面只需考虑A1和A3的供应、B2和B4需求了，??这样依次分析下去，便得到：
x32?min?a3?x33,b2??min?7?4,8??3 x14?min?a1,b4?x24??min?9,6?2??4 x12?min?a1?x14,b2?x32??min?9?4,8?3??5
将上述六个数填在运输表内（为了与其它数字相区别，用圈号标记），其余为非基变量取0值，就可作为初始调运方案（见表3-5）.
从表3-5容易算出，这个初始方案的总运费是 5×9+4×7+3×1+2×2+3×4+4×2 =100（百元）， 即10000元.
（3）以上两种方法在求初始基可行解时，均会遇到一些特殊情况，一般称为“退化”. 大致有两种情况：①当选定元素xij后，发现该元素所在行的供给量等于需求量时，此时只能划去一行或一列，不能同时划去. ②当选定元素xij后，发现对应供给量ai和需求量bj均为0，那么xij?min?ai,bj??0，此时仍应把
xij作为基变量，把0值填入相应格子中（即基变量取0，退化）.
（二）最优性检验
上面已经得到初始基可行解，那是否为最优解呢？需要验证. 依单纯形法原理，要求出各变量的检验数；由于基变量的检验数恒为0，所以只要求出非基变量的检验数. 另外运输问题是极小化的线性规划问题，只要检验数全部非负即达最优解. 在表上作业法中常有闭回路法和位势法.
- 6 -
（1）闭回路法 我们试从定义出发计算检验数. 先看x11的检验数C11，分析一个闭回路（表3-6中虚线所示）. 由于供求条件的限制，当从0增加到1时，将引起连锁反应：x21减少1，x24增加1，x14减少1. 于是根据检验数的定义得到C11=1c11+（-1）c21+1c24+（-1）c14= c11-c21+c24-c14=2-1+2-7= -4，即x11每增加1个单位，将使运费减少4个单位，这说明初始解非最优. 类似地，我们可以求出其他非基变量的检验数，但是，一般说来这种求检验数的方法是比较繁琐的. 例如，求x31的检验数时，必须考虑下面那样的复杂闭回路(表3-6中实线所示)．
表3-6 运输问题作业表
县城 医院 A1 医院抽B1 2 1 8 ③ 3 8 4 ⑤ 3 ④ 4 B2 9 4 2 B3 10 ④ ② B4 7 出人数 9 2 5 5 7 x11 A2 A3 县需人数 ③ x31 6 （2） 用位势法 位势法又叫U-V法，它是由解运输问题的对偶问题引出来的. 平衡型运输问题的对偶问题为：
MaxY??aiui??bivji?1j?1mn
s.t.ui?vj?cij(i?1,?,m;j?1,?,n)对偶模型里的变量ui与m个供应约束方程对应，vj与n个需求约束方程对应，分别称它们为原问题变量xij的行位势和列位势.
定理3-2 运输问题的决策变量xij的检验数Cij?cij?(ui?vj). (证明略) 由于基变量的检验数等于0，所以对于基变量xij有： ui?vj?cij. 而平衡型
- 7 -
运输问题中的基变量个数为m?n?1，从而得到m?n?1个类似ui?vj?cij这样方程构成的方程组. 但它有m?n个未知量，要解出这个方程组，必须给其中一个自由未知量赋值，比如令u1?0（这样不会影响结果），就可求出所有变量的位势，进而算出所有非基变量的检验数. 仍用例3-1来说明具体求法. 对于最小费用法得到的初始基本可行解（见表3-5），得到方程组
?u1?v2?9?u?v?74?1?u1?0,u2??5,u3??5,???u2?v1?1 令 ，解得：u?0??1u?v?24?v?6,v?9,v?7,v?7?2234?1?u3?v2?4???u3?v3?2
计算非基变量的检验数：C11?c11?(u1?v1)?2?0?6??4，与闭回路法结果一致，其它检验数可类似求出填入作业表中，用（ ）圈起来，见表3-7.
表3-7 运输问题作业表——位势法求检验数
县城 医院 0 A1 （-4） -5 A2 -5 A3 县需人数 （7） 3 ③ 8 1 6 B1 2 9 B2 ⑤ （-1） ③ 8 4 3 9 （3） 4 7 B3 10 ④ ② （3） 6 2 5 （2） ④ 4 2 7 B4 7 医院抽出人数 9 5 7 从表3-7可以看出，x11的检验数C11=-4（与前面用定义求得的结果是一致的）是所有检验数中负值最小者. 这说明应当让x11进基，以改进表3-5中的初始方案.
（三）用闭回路法调整运输方案——改进基本可行解
如果经过检验所得的解不是最优的，就需要对基变量进行迭代. 前面已经有选取进基变量的规则，即在所有非基变量中取检验数是负值最小者为进基变量.
- 8 -
下面，用闭回路法选取出基变量及基变量取值的调整量，以实现解的改进. 步骤是：① 找出入基变量所在的闭回路，并以该变量所在格为起点，沿闭回路顶点依次交替把它们所取的值前面加“+”、“-”号. 如表3-8所示； ② 所有被标“-”号格子中变量xij取值最小者作为出基变量，即被标“-”号的圆圈中数字最小者：
??min{闭回路顶点上所有标\号的xij的取值}. 在表3-8中??min?3,4??3.
表3-8 基变量迭代调整表
县城 医院 + 0 A1 （-4） -5 A2 - ③ -5 A3 县需人数 （7） 3 8 1 6 B1 2 9 B2 ⑤ （-1） ③ 8 4 3 9 （3） 4 7 B3 10 - ④ + ② （3） 6 2 5 （2） ④ 4 2 7 B4 7 医院抽出人数 9 5 7 表3-9 迭代后的运输方案表
县城 医院 0 A1 ③ -5 A2 （4） -5 A3 县需人数 （11） 3 8 1 2 B1 2 9 B2 ⑤ （-1） ③ 8 4 3 9 （3） 4 7 B3 10 ① ⑤ （3） 6 2 5 （2） ④ 4 2 7 B4 7 医院抽出人数 9 5 7 ③ 进行基的迭代,出基变量当然取值为0，即将所有带“+” 号的格子原取值加
?，带“-”号的格子原取值减?,就得到一个新的调运方案（闭回路不涉及的基变量取值不变动，见表3-9）. 再求检验数，重复上述步骤，直至最优.
- 9 -
从表3-9中容易算出，这个方案的总运费是 3×2+5×9+1×7+5×2+3×4+4×2 =88（百元）， 即8800元. 比初始表的方案优秀了，但在表中求出各非基变量的检验数显示，它还不是最优的. x22要作为入基变量. 再经过迭代得到调运方案如表3-10所示.
表3-10 再次迭代后的运输方案表
县城 医院 0 A1 ③ -5 A2 （4） -5 A3 县需人数 （11） 3 8 1 2 B1 2 9 B2 -⑤ + 3 9 （3） 4 7 B3 10 -⑤ （3） 6 +① 7 B4 7 9 <6> 2 5 （-1） <5> ③ 8 4 （2） ④ 4 2 医院抽出人数 <0> 5 7 从表3-10容易得出，x11?3,x14?6,x22?5,x32?3,x33?4,其它非基变量为0；这时的总费用为：3×2+6×7+5×3+3×4+4×2 =83（百元）， 即8300元. 这时算出非基变量的所有检验数均非负，从而是最优的运输方案.
在计算过程中需要注意的是，可能会有非基变量（空格）的检验数为0的情况，这时，该供销平衡的运输问题存在无穷多最优解. 在已得到的一个最优解的表格中，从这样的空格出发做闭回路重新进行调整，可以得到另一个最优解.
三 、其他运输问题的处理
前面的讨论都是以供销平衡（即?ai??bj）为前提的. 但在实际问题中，
i?1j?1mn这一条件常常不能满足，称为不平衡型运输问题.此时有“供大于销”和“供小于销” 两种情形. 下面只讨论第一种，另一种情况可类似推出. 由于“供大于销”有：?ai??bj．这时可虚设一个销地Bn?1，Bn?1的需求量为总供给与总
i?1j?1mn- 10 -