第八章运输问题 在第一章里我们已给出运输问题 发点 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的行为平衡行,d<0的行为调入行,转(C) (8)中,显然X°不满足行平衡条件(2),其中2,3行是调出行,1,4行是调入行,无平衡 C)检查X°是否有平衡行。若无,计算所谓最小直接差 内=min{c-|x>0,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）