第八章运输问题 在第一章里我们已给出运输问题 发点 BB,….B发量 收点 A2 A 收量 的数学模型如下 h(( (3) > 它包含皿×n个变量,(mtn)个约束条件,若用单纯形法求解,由于规模太大,计算起来非常繁杂, 人们依据运输问题的特殊结构,创造出各种专门求解的简易方法,下面介绍两种最简单的方法 §1匈牙利方法 首先容易证明对于运输问题(1)的费用矩阵C=(c)mxn的每一行,减去该行的最小值,之后, 再对每一列减去该列的最小值,以所得新矩阵C作为费用,这两个运输问题等价 例1求解运输问题 B1 B2 B4 Bs B6 A153 B72 385 A328348 433 A4961051097 336212 设经过上述处理后如下:
142 第八章 运输问题 在第一章里我们已给出运输问题： 发点 收点 B B B 1 2 n 发量 1 2 m A A A 11 12 1 21 22 2 1 2 n n m m mn c c c c c c c c c 1 2 m a a a 收量 b b b 1 2 n （1） 的数学模型如下： 1 1 1 1 ,( 1, , ) (2) ,( 1, , ) (3) 0 (4) n ij i j m ij j i ij m n ij ij i j x a i m x b j n x min f c x = = = = = = = = = 它包含 m×n 个变量，（m+n）个约束条件，若用单纯形法求解，由于规模太大，计算起来非常繁杂， 人们依据运输问题的特殊结构，创造出各种专门求解的简易方法，下面介绍两种最简单的方法。 §1 匈牙利方法 首先容易证明对于运输问题（1）的费用矩阵 ( ) C c = ij m n 的每一行，减去该行的最小值，之后， 再对每一列减去该列的最小值，以所得新矩阵 C 作为费用，这两个运输问题等价。 例 1 求解运输问题: 5 3 7 3 8 5 4 5 6 12 5 7 11 3 2 8 3 4 8 2 3 9 6 10 5 10 9 7 3 3 6 2 1 2 A1 A2 A3 A4 B1 B2 B3 B4 B5 B6 (5) 设经过上述处理后如下：
B, B, B3 B4 Bs B 4A2030324 A20160063 40602403 A4414034 336212 (6) (6)中每行、每列都至少有一个0。显然如能找到运输问题的一个可行解X,具下述性质: 所有X>0的地方,运费Cn=0,则这个可行解一定是最优解 那么如何找具有上述性质的可行解呢?设想在Cn=0的地方A与B,有一条边相连,对有边相 连的二点实行足量分配,可得一方案。其中X>0的边4B(简记(,j)看作属于匹配的边,检 查该方案是否满足行、列平衡条件(2)、(3),若满足则它即为最优解,否则必有某i行中所有X,的 和小于a1,于是于A前标号S,A即是未盖点,考虑i行Cn=0的格子,在这些格子所在列B上面 标号i,然后检查这些列使X>0的行4,看44行前是否标号,对未标号的4行前边标以列下标j 再检查A行中=0的那些列,若该列X之和等于b,则继续对x>0的行进行标号,若该列X 之和小于b,则说明已找到连接两个未盖点A和B,的增广链(按标号倒向追踪即得此增广链),于 是像求最大匹配那样,只对增广链上的格子进行足量调整,调整量9等于i行剩余发量、j列剩余收 量及增广链上X>0中那些需减少分配量的诸值之最小者,对增广链上的格子依次一增一减9。 按上述规则考察(6),则应在A4前标以S,4行只一个0,故只须在B4上方标以4,4列中X14 x4大于0,从而A前得到标号4(X4不产生新标号,作罢),继之B2上方得到标号1。至此,标 号过程已不能再进行下去 当标号不能再进行时,须对费用矩阵C"作下述变换 先令δ等于已标号行和未标号列上C的最小值,则必有δ>0(因为若δ=0,则等于0的那些 列按规定应被标号),然后对所有已标号行减去,对所有已标号列加上δ,这样作的结果可由下面 的表看出 有标号的列 无标号的列
143 1 2 3 4 5 6 1 2 3 4 2 0 3 0 3 2 4 0 1 6 0 0 6 3 0 6 0 2 4 0 3 4 1 4 0 3 4 7 B B B B B B A A A A ① ③ ③ ① 1 4 4 S ③ 3 3 6 2 1 2 （6） （6）中每行、每列都至少有一个 0。显然如能找到运输问题的一个可行解 Xij ,具下述性质： 所有 Xij 0 的地方，运费 cij = 0 ,则这个可行解一定是最优解。 那么如何找具有上述性质的可行解呢？设想在 cij = 0 的地方 Ai 与 Bj 有一条边相连，对有边相 连的二点实行足量分配，可得一方案。其中 Xij 0 的边 Ai Bj （简记 ( , ) i j ）看作属于匹配的边，检 查该方案是否满足行、列平衡条件（2）、（3），若满足则它即为最优解，否则必有某 i 行中所有 Xij 的 和小于 i a ,于是于 Ai 前标号 S ， Ai 即是未盖点，考虑 i 行 cij = 0 的格子，在这些格子所在列 Bj 上面 标号 i ,然后检查这些列使 Xij 0 的行 Ak ，看 Ak 行前是否标号，对未标号的 Ak 行前边标以列下标 j , 再检查 Ak 行中 ckj = 0 的那些列，若该列 Xij 之和等于 j b ,则继续对 Xij 0 的行进行标号，若该列 Xij 之和小于 j b ,则说明已找到连接两个未盖点 Ai 和 Bj 的增广链（按标号倒向追踪即得此增广链），于 是像求最大匹配那样，只对增广链上的格子进行足量调整，调整量 等于 i 行剩余发量、 j 列剩余收 量及增广链上 Xij 0 中那些需减少分配量的诸值之最小者，对增广链上的格子依次一增一减 。 按上述规则考察（6），则应在 A4 前标以 S ，4 行只一个 0，故只须在 B4 上方标以 4,4 列中 X14 ， X44 大于 0，从而 A1 前得到标号 4（ X44 不产生新标号，作罢），继之 B2 上方得到标号 1。至此，标 号过程已不能再进行下去。 当标号不能再进行时，须对费用矩阵 C 作下述变换： 先令 等于已标号行和未标号列上 Cij 的最小值，则必有 ＞0（因为若 ＝0，则等于 0 的那些 列按规定应被标号），然后对所有已标号行减去 ，对所有已标号列加上 ，这样作的结果可由下面 的表看出： 有标号的列 无标号的列
有标号的行 I不变 无标号的行 Ⅲ+δ ⅣV 不变 因为在表的第Ⅱ块中所有的元素都减少了δ。所以一定会多出一些0来,但在Ⅲ中可能减少一些0, 注意这些θ的格子一定有X=0。不然,按规定对应的行就应该被标号了。这就保证了经等价变换 后,X>0的仍是在费用为0的格子里取得,故一旦满足(2)和(3),便是最优解了。 在对费用矩阵C作变换之后,在新的矩阵上重复前述标号过程(可在原先标号的基础上往下做) 直到求得最优解为止。 对于(6),已标号行和未标号列的最小值δ=2,变换后的矩阵及标号情形见下表 B B2 B B4 Bs B6 0 04 A4A 036 024 080 04 63 A42120127 3362 这里B6已标号,但该列X6之和小于b,故已得增广链 (1,6) 调整量9=Mn{a4-x4,b6,x14}=Mn{6,2,1=1。今于(4,4)处加1,(1,4)处减1,(1,6) 处加1,便得下表 B B2 B3 B2 Bs B 400 04 A20362063 440 sA421 026 0127 33 2 对(7)重复标号,变换矩阵,再标号、调整的过程(总共调整4次),最后得:
144 有标号的行 Ⅰ 不变 Ⅱ － 无标号的行 Ⅲ ＋ Ⅳ 不变 因为在表的第Ⅱ块中所有的元素都减少了 。所以一定会多出一些 0 来，但在Ⅲ中可能减少一些 0， 注意这些 0 的格子一定有 Xij = 0 。不然，按规定对应的行就应该被标号了。这就保证了经等价变换 后， Xij 0 的仍是在费用为 0 的格子里取得，故一旦满足（2）和（3），便是最优解了。 在对费用矩阵 C 作变换之后，在新的矩阵上重复前述标号过程（可在原先标号的基础上往下做） 直到求得最优解为止。 对于（6），已标号行和未标号列的最小值 ＝2，变换后的矩阵及标号情形见下表： ① ① ③ ③ ③ 1 2 3 4 5 6 1 2 3 4 0 0 1 0 1 0 4 0 3 6 2 0 6 3 0 8 0 4 4 0 3 2 1 2 0 1 2 7 3 3 6 2 1 2 B B B B B B A A A A 1 1 4 1 4 S 这里 B6 已标号，但该列 Xi6 之和小于 6 b ，故已得增广链： （4，4） （1，4） （1，6） 调整量 4 44 6 14 = − = = Min a X b X Min { , , } {6,2,1} 1 。今于（4，4）处加 1，（1，4）处减 1，（1，6） 处加 1，便得下表： ① ③ ② ③ ③ 1 2 3 4 5 6 1 2 3 4 0 0 1 0 1 0 4 0 3 6 2 0 6 3 0 8 0 4 4 0 3 2 1 2 0 1 2 7 3 3 6 2 1 2 B B B B B B A A A A 4 S （7） 对（7）重复标号，变换矩阵，再标号、调整的过程（总共调整 4 次），最后得：
B B,B3 B4 Bs B A 9 113 05.006 36.02 050 4337 此即最优解。它与用闭回路法得到的结果相同。 可用对偶理论对上述方法做出解释,故亦称原始对偶算法,这种方法被认为是比较有效的 §2最小调整法 上节给出的方法是从(原问题或对偶问题的)可行解出发,寻找目标函数值有所改善的另 行解。下边介绍的最小调整法不是从可行解出发,而是先置行平衡条件(2)于不顾,从满足列平衡 条件(3)且使目标函数(4)取最小值的方案开始,然后通过适当调整,逐步实现行平衡,每次调 整必须遵循如下二原则 (一)不得破坏列平衡条件(3),且对同一调整量θ,调整后的方案使目标函数(4)增值最小 (二)按能以最少次数完成整个调整来确定调整量,即足量调整 下面结合§1例1具体说明实现上述思想的步骤。 (A)对费用矩阵C先作行、列减值处理(此步并非必要但常能减少调整次数),所得矩阵不妨 仍记为C,然后按C之各列最小值(若不唯一可适当任取其一)。 做如下方案X=(X0)mn:X8=b,j=1…n,其余x0=0,并称X°为最小方案,对例1 的费用矩阵(6),最小方案为(X0的非0元素用方框标出) 203 6 1613 002 4 6212 (8) (B)检查X0是否满足行平衡条件(2),若满足,则X0即为最优方案。否则记 14
145 ① ① ③ ② ② ② ③ ③ 1 2 3 4 5 6 1 2 3 4 0 0 0 1 1 0 4 0 3 5 3 0 6 3 1 9 0 6 5 1 3 1 0 0 0 0 1 7 3 3 6 2 1 2 B B B B B B A A A A 此即最优解。它与用闭回路法得到的结果相同。 可用对偶理论对上述方法做出解释，故亦称原始对偶算法，这种方法被认为是比较有效的。 §2 最小调整法 上节给出的方法是从（原问题或对偶问题的）可行解出发，寻找目标函数值有所改善的另一可 行解。下边介绍的最小调整法不是从可行解出发，而是先置行平衡条件（2）于不顾，从满足列平衡 条件（3）且使目标函数（4）取最小值的方案开始，然后通过适当调整，逐步实现行平衡，每次调 整必须遵循如下二原则 （一）不得破坏列平衡条件（3），且对同一调整量 ，调整后的方案使目标函数（4）增值最小。 （二）按能以最少次数完成整个调整来确定调整量，即足量调整。 下面结合§1 例 1 具体说明实现上述思想的步骤。 （A）对费用矩阵 C 先作行、列减值处理（此步并非必要但常能减少调整次数），所得矩阵不妨 仍记为 C，然后按 C 之各列最小值（若不唯一可适当任取其一）。 1 , 1, , kj ij i m c Min c j n = = 做如下方案 0 0 ( ) X X = ij m n ： (0) , 1, , X b j n kj j = = ，其余 (0) Xij = 0 ，并称 0 X 为最小方案，对例 1 的费用矩阵（6），最小方案为（ 0 Xij 的非 0 元素用方框标出）： 2 0 3 0 3 2 4 0 1 6 0 0 6 3 0 6 0 2 4 0 3 4 1 4 0 3 4 7 3 3 6 2 1 2 1 2 3 2 3 6 （8） （B）检查 0 X 是否满足行平衡条件（2），若满足，则 0 X 即为最优方案。否则记
d=∑x-an,l=1…m 称使d0>0的行为调出行,d=0的行为平衡行,d0,j=1…,n,且k为调出行,S为调入行}=cAb-c 则由原则(二),相应的调整量应为 9=min{1,0,一}>0 (10) 据此做如下直接调整 X=XC-9,H=X+日,其余X=X0 (11) 若调整差(13)不唯一,则逐一处理,调整后的方案记为X1,转(B)。 若X0有平衡行,转(D)。 对(8),易见最小直接差(可先计算每列的最小直接差,再取它们中的最小者)及调整量为 h=c16-c6=2,9=min{2,5,1=1 调整后的方案X为(为明显起见,调整路线用箭头在X°中标出) 2030324 60 060240°3 4140 47 3362 (12) 其中(1)行已变成平衡行。 (D)在有平衡行时,除了考虑直接差外,还要计算所谓间接差,即由调出行调一定数量于某些 平衡行,再由这些平衡行调相同数量于其它平衡行,经中转最后至调入行所产生的费用增值。间接 差的一般形式如下: (C,b1-C1)+(Cn1-C)+…+(Ck-CA)+(c1-Cb) (13) 146
146 0 0 1 , 1, , n i ij i j d X a i m = = − = 称使 0 di 0 的行为调出行， 0 di = 0 的行为平衡行， 0 di 0 的行为调入行，转（C）。 （8）中，显然 0 X 不满足行平衡条件（2），其中 2，3 行是调出行，1，4 行是调入行，无平衡 行。 （ C ） 检 查 0 X 是 否 有 平 衡 行 。 若 无 ， 计 算 所 谓 最 小 直 接 差 ： h1 = min { 0 | 0, 1, , sj kj kj c c X j n − = ，且 k 为调出行,S 为调入行}= 1 0 0 0 k j k j c c − (9) 则由原则（二），相应的调整量应为 0 0 0 1 0 0 0 1 = − min{ , , } 0 X d d k j k k （10） 据此做如下直接调整： 0 0 0 0 1 0 X X k j k j = −1 ， 1 1 0 1 0 1 0 Xk j = Xk j + ，其余 1 0 X X ij ij = （11） 若调整差（13）不唯一，则逐一处理，调整后的方案记为 1 X ，转（B）。 若 0 X 有平衡行，转（D）。 对（8），易见最小直接差（可先计算每列的最小直接差，再取它们中的最小者）及调整量为 h c c 1 16 36 = − = 2 ，1 = = min{2,5,1} 1 调整后的方案 1 X 为（为明显起见，调整路线用箭头在 0 X 中标出）： ③ 2 0 3 0 3 2 4 0 1 6 0 0 6 3 0 6 0 2 4 0 3 4 1 4 0 3 4 7 3 3 6 2 1 2 ⑥ ① ③ ② ① ① （12） 其中（1）行已变成平衡行。 （D）在有平衡行时，除了考虑直接差外，还要计算所谓间接差，即由调出行调一定数量于某些 平衡行，再由这些平衡行调相同数量于其它平衡行，经中转最后至调入行所产生的费用增值。间接 差的一般形式如下： 1 1 1 1 2 1 1 1 1 0 0 0 ( ) ( ) ( ) ( ) t t t t t t t t k j k j k j k j k j k j k j k j c c c c c c c c + − − − − + − + + − + − （13）
其中k行是调出行,k是调入行,k,k2…,k是平衡行,且需满足条件x5>0,S=0, 1…t,把(13)的最小值与(9)比较,取二者较小者为调整差h,若h是间接差(13),则调整 量为 =mn{y,…,x,d1}0 (14) 并做如下间接调整 x0+9 9,X=X+9 X,+9 记调整后的方案为X1,转(B),最后至某步P,若X满足(2),则其即为最优方案。 由(12),易见调整差为 5-c2) 故可进行二次调整,每次调整量均为9=1,得X 303 0160063 060240|3 4140 47 336212 (16) (16)中仍有非平衡行,继续调整: h2=c43-c3=4,9=min{6,3,3}=3,得X3 20303214 0602403 4 47 X3已满足行平衡,故为最优解 147
147 其中 0 k 行是调出行， t 1 k + 是调入行， 1 2 , , , t k k k 是平衡行，且需满足条件 0 0 S S Xk j ，S＝0， 1, ,t ，把（13）的最小值与（9）比较，取二者较小者为调整差 1 h ，若 1 h 是间接差（13），则调整 量为 min , , , , 0 0 0 0 0 1 0 0 0 1 = − t t t+ Xk j Xk j dk dk （14） 并做如下间接调整： 0 0 0 0 1 0 1 0 1 0 1 0 1 1 , X X X X k j k j k j k j = − = + ， 1 1 1 1 2 1 2 1 1 0 1 0 1 1 , , , X X X X k j k j k j k j = − = + 1 1 1 0 X X k j k j t t t t + + = +1 （15） 记调整后的方案为 1 X ，转（B），最后至某步 P，若 P X 满足（2），则其即为最优方案。 由（12），易见调整差为 2 45 25 45 12 16 36 h c c c c c c = − = − + − = ( ) ( ) 3 故可进行二次调整，每次调整量均为 2 =1 ，得 2 X : ① ② ② ② ③ 2 0 3 0 3 2 4 0 1 6 0 0 6 3 0 6 0 2 4 0 3 4 1 4 0 3 4 7 3 3 6 2 1 2 ⑥ ① (16) (16)中仍有非平衡行，继续调整： h c c 2 43 33 = − = 4，3 = = min{6,3,3} 3 ，得 3 X : ① ③ ② ② ② ③ ③ 2 0 3 0 3 2 4 0 1 6 0 0 6 3 0 6 0 2 4 0 3 4 1 4 0 3 4 7 3 3 6 2 1 2 ① 3 X 已满足行平衡，故为最优解
若把前边所述的“行”换成“列”,即按各行最小值求最小方案,逐步调整使之满足列平衡(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)满足 148
148 若把前边所述的“行”换成“列”，即按各行最小值求最小方案，逐步调整使之满足列平衡（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 + = 满 足
X1>0,s=0,1,…t,则称之为X”的反调路线,而定义沿(17)的反调差和反调量分别为 h 18) =mn (19) 有了以上的准备可以得到如下结果。 定理2运输问题(1)产生“悖论”的充要条件是最优解X中存在反调路线(17),且由(18) 定义的反调差h满足 > min ck, (20) 这里k1是新值点(k4)所在的行 注意,在研究“悖论”现象时,不能对费用矩阵C做行列减值变换,因为这里要比较既不同行 也不同列的费用值 现在对最优解X”,沿反调路线(17),做一次反调量为9的反调整,然后于(K,,D)处增加9 则得如下方案X: X=X+9,K,=X x=+9…=XC1-9,R,1=xC1+9,其余石=X (21) 则与X比较,方案X于k行多发⑨,于L列多收9,其余各行、列收发不变,若(20)式成立, 则相应于X的运费 f(X)=f()-h8+ck,0<f(x* 可见多运了9,运费反而减少了(h-c)0 产生了“悖论”现象,说明在最优解的基础上还有潜力可挖(当然也说明原来的收发布局不 协调)。以上实际是给出了挖潜调整的具体步骤,对每一条满足(20)的反调路线均实行上述调整, 最后便得到不仅运量增加最多而且所耗费用最少的所谓最终最佳方案。 例2仍以§1例1为例,其最小方案X0(方框数字)及最优方案X(圆圈数字)标示如下
149 1 0, 0,1, , s s X s t k j + = ，则称之为 X 的反调路线，而定义沿（17）的反调差和反调量分别为 1 1 0 0 0 ( ) ( ) t t t t h c c c c k j k j k j k j + = − + + − （18） 1 0 min{ } s s k j s t X + = （19） 有了以上的准备可以得到如下结果。 定理 2 运输问题（1）产生“悖论”的充要条件是最优解 X 中存在反调路线（17），且由（18） 定义的反调差 h 满足 k j k l j n t t h c c min 1 1 1 + + = （20） 这里 t 1 k + 是新值点 1 ( , ) t t k j + 所在的行。 注意，在研究“悖论”现象时，不能对费用矩阵 C 做行列减值变换，因为这里要比较既不同行 也不同列的费用值。 现在对最优解 X ，沿反调路线（17），做一次反调量为 的反调整，然后于 ( , ) 1 K l t+ 处增加 ， 则得如下方案 X ： 0 0 0 0 1 0 1 0 , X X X X k j k j k j k j = + = − ， 1 1 1 1 1 1 , , , t t t t X X X X k j k j k j k j + + = + = − X X k k t t 1 1 1 1 + + = + ，其余 X X ij ij = （21） 则与 X 比较，方案 X 于 0 k 行多发 ，于 L 列多收 ，其余各行、列收发不变，若（20）式成立， 则相应于 X 的运费： ( ) ( ) ( *) 1 * f X f X h ck l f X t = − + + (22) 可见多运了 ，运费反而减少了（ ) 1 k l t h c + − 。 产生了“悖论”现象，说明在最优解的基础上还有潜力可挖（当然也说明原来的收发布局不 协调）。以上实际是给出了挖潜调整的具体步骤，对每一条满足（20）的反调路线均实行上述调整， 最后便得到不仅运量增加最多而且所耗费用最少的所谓最终最佳方案。 例 2仍以§1 例 1 为例，其最小方案 0 X （方框数字）及最优方案 X （圆圈数字）标示如下：
7 61257113 8写4 3362 2 检查它的反调路线,发现已有一条: 的反调差h=c3-c3=10-3=7>minc=c4=5,故必产生“悖论”现象,而6=3,调整后, 3行、4列各增加了3: ③ 482-6 960105610097 (24 继续考察,发现还有两条满足(20)的反调路线: (4,2)→(1,2)→>(1,6)→>(3,6) (4,5)→(2,5)→>(2,1)→(3,1) 调整后的方案为: 56125 山 4828 9610501097 (25) 它的最优值为∫=88,减少了8,而收发量增加了5。 (25)中已无满足(20)的反调路线,就是说再增加运量,运费不会再减少,但是存在一条反 150
150 ① ③ ② ② ② ③ ③ ① 5 3 7 3 8 5 4 5 6 12 5 7 11 3 2 8 3 4 8 2 3 9 6 10 5 10 9 7 3 3 6 2 1 2 0 3 6 2 1 3 2 （23） 检查它的反调路线，发现已有一条： (4,3) (3,3) → 的反调差 43 33 4 44 1 6 10 3 7 min 5 j j h c c c c = − = − = = = ，故必产生“悖论”现象，而 = 3 ，调整后， 3 行、4 列各增加了 3： ① ① ② ② ③ 5 3 7 3 8 5 4 5 6 12 5 7 11 3 2 8 3 4 8 2 6 9 6 10 5 10 9 7 3 3 6 5 1 2 0 3 6 2 1 3 5 ⑥ 0 ⑤ （24） 继续考察，发现还有两条满足（20）的反调路线： (4,2) (1,2) (1,6) (3,6) → → → (4,5) (2,5) (2,1) (3,1) → → → 调整后的方案为： ① ① ③ ① 5 3 7 3 8 5 4 5 6 12 5 7 11 3 2 8 3 4 8 2 8 9 6 10 5 10 9 7 3 3 6 7 1 2 0 3 6 2 1 3 7 0 ⑥ ⑦ ① （25） 它的最优值为 f ＝88，减少了 8，而收发量增加了 5。 （25）中已无满足（20）的反调路线，就是说再增加运量，运费不会再减少，但是存在一条反
调路线:(1,6)亠(3,6),它使(20)中的严格不等式变为等式,这意味着沿此路线做一次反调整, 可以增加运量,但运费不减少,与(25)相比它当然更好些,但严格说来,对(25)而言,不能算 是“悖论”发生,因运费并未减少,但对原问题(5)却是发生了,而且是最好的结果,可见把“悖 论”的定义改为“增加运量,运费不增”更合适些(这时定理2中的(20)式应变>为孟)。 可以利用位势和闭回路研究悖论产生的条件[6]。事实上,如果 t.+v.<0 则“悖论”一定发生,这时以点(i,j)做闭回路,适当调整,即可改进原来的结果,但条件(26) 只在非退化情形是充要的,在退化情形(对“悖论”问题这是常见的)它只是充分的,如对例1即 (5)用这种方法调整只能得到(24),而不能得到(25),更谈不上得到最终的最佳方案了 如果用最小调整法求最优解,则可以证明只要某次调整的调整差大于所调入行的最小费用 即可断定“悖论”现象一定发生,从而在调整中即可进行挖潜处理,而不必等到求出最优解之后再 调整。 51
151 调路线：（1,6）→（3,6），它使（20）中的严格不等式变为等式，这意味着沿此路线做一次反调整， 可以增加运量，但运费不减少，与（25）相比它当然更好些，但严格说来，对（25）而言，不能算 是“悖论”发生，因运费并未减少，但对原问题（5）却是发生了，而且是最好的结果，可见把“悖 论”的定义改为“增加运量，运费不增”更合适些（这时定理 2 中的（20）式应变＞为≧）。 可以利用位势和闭回路研究悖论产生的条件［16］。事实上，如果 u v i j + 0 （26） 则“悖论”一定发生，这时以点（i,j）做闭回路，适当调整，即可改进原来的结果，但条件（26） 只在非退化情形是充要的，在退化情形（对“悖论”问题这是常见的）它只是充分的，如对例 1 即 （5）用这种方法调整只能得到（24），而不能得到（25），更谈不上得到最终的最佳方案了。 如果用最小调整法求最优解，则可以证明只要某次调整的调整差 k h 大于所调入行的最小费用， 即可断定“悖论”现象一定发生，从而在调整中即可进行挖潜处理，而不必等到求出最优解之后再 调整