若把前边所述的“行”换成“列”,即按各行最小值求最小方案,逐步调整使之满足列平衡(3), 方法可照样实行。 可以严格证明由最小调整法得到的可行方案是最优方案(由于证明较长,这里略去),并且若所 给数据是整数(进而可为有理数),则调整终止于有限步。至于调整次数,如果均为直接调整,则最 多不会超过m+n-2次,若还含有间接调整,次数反而会更少,这是因为由最小方案X到最优方案X 总共增加的非0元素可不超过m-1,直接调整一次至多增一非0元素,而间接调整,如中经t个平 衡行,则最多可增加(t+1)个非0元素,从而可更快地得到最优方案。实际上,调整次数一般也就 是m左右,这比前两种方法的调整次数要少得多,特别对m较小而n较大的“狭长表”,方法格外有 效。而发点较少,收点较多正是实际中常见的。例如象下面这样一个具3个发点、8个收点的问题: 四1,262817295259 92618-620302836 l62319253416-251071 191630341533127 只须直接调整二次,即可得到最优方案(调整路线在表上用箭头标出)。 方法对于退化问题尤其好用,而且退化程度越高,调整次数越少,比如对分配问题(它可看成 是高度退化的特殊运输问题)如其最小方案中有q个调入行,则易证调整次数最多不超过q,同时 这里也不存在退化型的循环问题。 最小调整法还表现出灵活方便的特点,对于不平衡以及需求是可变动的问题它可以不加区别的 处理,用它还能解能力受限一类运输问题等。 当然,当m、n较大时,虽说求最小直接差并不难,但求最小间接差则要费点事,不过也不必穷 举所有间接差,可以证明如果该次前的间接调整不产生新的平衡行,则最小间接差(13)中的每一 括号内的数均非负,此时最小直接差即可作为上界,按(13)累计求和时,一旦超过了这个上界就 不必再算下去了。总之,可以给出一个计算调整差的一般程序,它类似于求最短路的标号算法,实 算表明按该程序求调整差,计算量并不大 §3运输问题“惇论” 在运输问题中,出现一个奇怪而有趣的现象:在最优方案的基础上再增加收发量运费反而减少 了,这种现象称为运输问题“悖论”。用最小调整法很容易解释这种现象,并获得产生“悖论”的充 要条件。 设X是最小方案,X是最优方案,为叙述方便先引入下面的定义 定义1对于最小方案X和最优方案X,若X>X0=0,则称(为新值点;若X0>X 且i为X°的调出行,则称点(,为旧值点 定义2对于以新值点(k,方)为起点,旧值点(k,J)为终点的路线: (k+1,)→(k,)→(k,j1)→…→(k,j)→(k0,J) (17) 如果其中自起点(k1,)始,排在奇数位置上的点(k1,S=1,…1,0)满足 148148 若把前边所述的“行”换成“列”，即按各行最小值求最小方案，逐步调整使之满足列平衡（3）， 方法可照样实行。 可以严格证明由最小调整法得到的可行方案是最优方案（由于证明较长，这里略去），并且若所 给数据是整数（进而可为有理数），则调整终止于有限步。至于调整次数，如果均为直接调整，则最 多不会超过 m+n-2 次，若还含有间接调整，次数反而会更少，这是因为由最小方案 0 X 到最优方案 X ， 总共增加的非 0 元素可不超过 m-1，直接调整一次至多增一非 0 元素，而间接调整，如中经 t 个平 衡行，则最多可增加（t+1）个非 0 元素，从而可更快地得到最优方案。实际上，调整次数一般也就 是 m 左右，这比前两种方法的调整次数要少得多，特别对 m 较小而 n 较大的“狭长表”，方法格外有 效。而发点较少，收点较多正是实际中常见的。例如象下面这样一个具 3 个发点、8 个收点的问题： 15 7 17 26 28 17 29 5 59 28 9 26 18 6 20 30 28 36 16 23 19 25 34 16 25 10 71 19 16 30 34 15 33 12 7 15 33 7 12 19 16 34 30 只须直接调整二次，即可得到最优方案（调整路线在表上用箭头标出）。 方法对于退化问题尤其好用，而且退化程度越高，调整次数越少，比如对分配问题（它可看成 是高度退化的特殊运输问题）如其最小方案中有 q 个调入行，则易证调整次数最多不超过 q，同时 这里也不存在退化型的循环问题。 最小调整法还表现出灵活方便的特点，对于不平衡以及需求是可变动的问题它可以不加区别的 处理，用它还能解能力受限一类运输问题等。 当然，当 m、n 较大时，虽说求最小直接差并不难，但求最小间接差则要费点事，不过也不必穷 举所有间接差，可以证明如果该次前的间接调整不产生新的平衡行，则最小间接差（13）中的每一 括号内的数均非负，此时最小直接差即可作为上界，按（13）累计求和时，一旦超过了这个上界就 不必再算下去了。总之，可以给出一个计算调整差的一般程序，它类似于求最短路的标号算法，实 算表明按该程序求调整差，计算量并不大。 §3 运输问题“悖论” 在运输问题中，出现一个奇怪而有趣的现象：在最优方案的基础上再增加收发量运费反而减少 了，这种现象称为运输问题“悖论”。用最小调整法很容易解释这种现象，并获得产生“悖论”的充 要条件。 设 0 X 是最小方案， X  是最优方案，为叙述方便先引入下面的定义。 定义 1 对于最小方案 0 X 和最优方案 X  ，若 0 X X ij ij 0   = ，则称 ( , ) i j 为新值点；若 0 X X ij ij   且 i 为 0 X 的调出行，则称点 ( , ) i j 为旧值点。 定义 2 对于以新值点 1 ( , ) t t k j + 为起点，旧值点 0 0 ( , ) k j 为终点的路线： 1 1 1 0 0 0 ( , ) ( , ) ( , ) ( , ) ( , ) t t t t t t k j k j k j k j k j + − → → → → → （17） 如果其中自起点 1 ( , ) t t k j + 始 ， 排 在 奇 数 位 置 上 的 点 1 ( , )( , ,1,0) s s k j s t + = 满 足