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 的那些 列按规定应被标号），然后对所有已标号行减去  ，对所有已标号列加上  ，这样作的结果可由下面 的表看出： 有标号的列 无标号的列