第八章 运输问题在第一章里我们已给出运输问题：
发点收点
发量
收量
（1）
的数学模型如下：
它包含m×n个变量，（m+n）个约束条件，若用单纯形法求解，由于规模太大，计算起来非常繁杂，人们依据运输问题的特殊结构，创造出各种专门求解的简易方法，下面介绍两种最简单的方法。
§1 匈牙利方法首先容易证明对于运输问题（1）的费用矩阵的每一行，减去该行的最小值，之后，再对每一列减去该列的最小值，以所得新矩阵作为费用，这两个运输问题等价。
例 1 求解运输问题:
(5)
设经过上述处理后如下：
3 3 6 2 1 2
（6）
（6）中每行、每列都至少有一个0。显然如能找到运输问题的一个可行解,具下述性质：所有的地方，运费,则这个可行解一定是最优解。
那么如何找具有上述性质的可行解呢？设想在的地方与有一条边相连，对有边相连的二点实行足量分配，可得一方案。其中的边（简记）看作属于匹配的边，检查该方案是否满足行、列平衡条件（2）、（3），若满足则它即为最优解，否则必有某行中所有的和小于,于是于前标号，即是未盖点，考虑行的格子，在这些格子所在列上面标号,然后检查这些列使的行，看行前是否标号，对未标号的行前边标以列下标,再检查行中的那些列，若该列之和等于,则继续对的行进行标号，若该列之和小于,则说明已找到连接两个未盖点和的增广链（按标号倒向追踪即得此增广链），于是像求最大匹配那样，只对增广链上的格子进行足量调整，调整量等于行剩余发量、列剩余收量及增广链上中那些需减少分配量的诸值之最小者，对增广链上的格子依次一增一减。
按上述规则考察（6），则应在前标以，4行只一个0，故只须在上方标以4,4列中，大于0，从而前得到标号4（不产生新标号，作罢），继之上方得到标号1。至此，标号过程已不能再进行下去。
当标号不能再进行时，须对费用矩阵作下述变换：
先令等于已标号行和未标号列上的最小值，则必有＞0（因为若＝0，则等于0的那些列按规定应被标号），然后对所有已标号行减去，对所有已标号列加上，这样作的结果可由下面的表看出：
有标号的列
无标号的列
有标号的行
Ⅰ 不变
Ⅱ －
无标号的行
Ⅲ ＋
Ⅳ 不变
因为在表的第Ⅱ块中所有的元素都减少了。所以一定会多出一些0来，但在Ⅲ中可能减少一些0，注意这些0的格子一定有。不然，按规定对应的行就应该被标号了。这就保证了经等价变换后，的仍是在费用为0的格子里取得，故一旦满足（2）和（3），便是最优解了。
在对费用矩阵作变换之后，在新的矩阵上重复前述标号过程（可在原先标号的基础上往下做）直到求得最优解为止。
对于（6），已标号行和未标号列的最小值＝2，变换后的矩阵及标号情形见下表：
这里已标号，但该列之和小于，故已得增广链：
（4，4） （1，4） （1，6）
调整量。今于（4，4）处加1，（1，4）处减1，（1，6）处加1，便得下表：
（7）
对（7）重复标号，变换矩阵，再标号、调整的过程（总共调整4次），最后得：
此即最优解。它与用闭回路法得到的结果相同。
可用对偶理论对上述方法做出解释，故亦称原始对偶算法，这种方法被认为是比较有效的。
§2 最小调整法上节给出的方法是从（原问题或对偶问题的）可行解出发，寻找目标函数值有所改善的另一可行解。下边介绍的最小调整法不是从可行解出发，而是先置行平衡条件（2）于不顾，从满足列平衡条件（3）且使目标函数（4）取最小值的方案开始，然后通过适当调整，逐步实现行平衡，每次调整必须遵循如下二原则
（一）不得破坏列平衡条件（3），且对同一调整量，调整后的方案使目标函数（4）增值最小。
（二）按能以最少次数完成整个调整来确定调整量，即足量调整。
下面结合§1例1具体说明实现上述思想的步骤。
（A）对费用矩阵C先作行、列减值处理（此步并非必要但常能减少调整次数），所得矩阵不妨仍记为C，然后按C之各列最小值（若不唯一可适当任取其一）。
做如下方案：，其余，并称为最小方案，对例1的费用矩阵（6），最小方案为（的非0元素用方框标出）：
（8）
（B）检查是否满足行平衡条件（2），若满足，则即为最优方案。否则记
称使的行为调出行，的行为平衡行，的行为调入行，转（C）。
（8）中，显然不满足行平衡条件（2），其中2，3行是调出行，1，4行是调入行，无平衡行。
（C）检查是否有平衡行。若无，计算所谓最小直接差：{，且k为调出行,S为调入行}= (9)
则由原则（二），相应的调整量应为
（10）
据此做如下直接调整：
，，其余 （11）
若调整差（13）不唯一，则逐一处理，调整后的方案记为，转（B）。
若有平衡行，转（D）。
对（8），易见最小直接差（可先计算每列的最小直接差，再取它们中的最小者）及调整量为
，
调整后的方案为（为明显起见，调整路线用箭头在中标出）：
（12）
其中（1）行已变成平衡行。
（D）在有平衡行时，除了考虑直接差外，还要计算所谓间接差，即由调出行调一定数量于某些平衡行，再由这些平衡行调相同数量于其它平衡行，经中转最后至调入行所产生的费用增值。间接差的一般形式如下：
（13）
其中行是调出行，是调入行，是平衡行，且需满足条件，S＝0，，把（13）的最小值与（9）比较，取二者较小者为调整差，若是间接差（13），则调整量为
（14）
并做如下间接调整：
， （15）
记调整后的方案为，转（B），最后至某步P，若满足（2），则其即为最优方案。
由（12），易见调整差为
故可进行二次调整，每次调整量均为，得:
(16)
(16)中仍有非平衡行，继续调整：
，，得:
已满足行平衡，故为最优解。
若把前边所述的“行”换成“列”，即按各行最小值求最小方案，逐步调整使之满足列平衡（3），方法可照样实行。
可以严格证明由最小调整法得到的可行方案是最优方案（由于证明较长，这里略去），并且若所给数据是整数（进而可为有理数），则调整终止于有限步。至于调整次数，如果均为直接调整，则最多不会超过m+n-2次，若还含有间接调整，次数反而会更少，这是因为由最小方案到最优方案，总共增加的非0元素可不超过m-1，直接调整一次至多增一非0元素，而间接调整，如中经t个平衡行，则最多可增加（t+1）个非0元素，从而可更快地得到最优方案。实际上，调整次数一般也就是m左右，这比前两种方法的调整次数要少得多，特别对m较小而n较大的“狭长表”，方法格外有效。而发点较少，收点较多正是实际中常见的。例如象下面这样一个具3个发点、8个收点的问题：
只须直接调整二次，即可得到最优方案（调整路线在表上用箭头标出）。
方法对于退化问题尤其好用，而且退化程度越高，调整次数越少，比如对分配问题（它可看成是高度退化的特殊运输问题）如其最小方案中有q个调入行，则易证调整次数最多不超过q，同时这里也不存在退化型的循环问题。
最小调整法还表现出灵活方便的特点，对于不平衡以及需求是可变动的问题它可以不加区别的处理，用它还能解能力受限一类运输问题等。
当然，当m、n较大时，虽说求最小直接差并不难，但求最小间接差则要费点事，不过也不必穷举所有间接差，可以证明如果该次前的间接调整不产生新的平衡行，则最小间接差（13）中的每一括号内的数均非负，此时最小直接差即可作为上界，按（13）累计求和时，一旦超过了这个上界就不必再算下去了。总之，可以给出一个计算调整差的一般程序，它类似于求最短路的标号算法，实算表明按该程序求调整差，计算量并不大。
§3 运输问题“悖论”
在运输问题中，出现一个奇怪而有趣的现象：在最优方案的基础上再增加收发量运费反而减少了，这种现象称为运输问题“悖论”。用最小调整法很容易解释这种现象，并获得产生“悖论”的充要条件。
设是最小方案，是最优方案，为叙述方便先引入下面的定义。
定义1 对于最小方案和最优方案，若，则称为新值点；若且i为的调出行，则称点为旧值点。
定义2 对于以新值点为起点，旧值点为终点的路线：
（17）
如果其中自起点始，排在奇数位置上的点满足，则称之为的反调路线，而定义沿（17）的反调差和反调量分别为
（18）
（19）
有了以上的准备可以得到如下结果。
定理2 运输问题（1）产生“悖论”的充要条件是最优解中存在反调路线（17），且由（18）定义的反调差满足
（20）
这里是新值点所在的行。
注意，在研究“悖论”现象时，不能对费用矩阵C做行列减值变换，因为这里要比较既不同行也不同列的费用值。
现在对最优解，沿反调路线（17），做一次反调量为的反调整，然后于处增加，则得如下方案：
，，其余 （21）
则与比较，方案于行多发，于L列多收，其余各行、列收发不变，若（20）式成立，则相应于的运费：
(22)
可见多运了，运费反而减少了（。
产生了“悖论”现象，说明在最优解的基础上还有潜力可挖（当然也说明原来的收发布局不协调）。以上实际是给出了挖潜调整的具体步骤，对每一条满足（20）的反调路线均实行上述调整，最后便得到不仅运量增加最多而且所耗费用最少的所谓最终最佳方案。
例2 仍以§1例1为例，其最小方案（方框数字）及最优方案（圆圈数字）标示如下：
（23）
检查它的反调路线，发现已有一条：
的反调差，故必产生“悖论”现象，而，调整后，3行、4列各增加了3：
（24）
继续考察，发现还有两条满足（20）的反调路线：
调整后的方案为：
（25）
它的最优值为＝88，减少了8，而收发量增加了5。
（25）中已无满足（20）的反调路线，就是说再增加运量，运费不会再减少，但是存在一条反调路线：（1,6）→（3,6），它使（20）中的严格不等式变为等式，这意味着沿此路线做一次反调整，可以增加运量，但运费不减少，与（25）相比它当然更好些，但严格说来，对（25）而言，不能算是“悖论”发生，因运费并未减少，但对原问题（5）却是发生了，而且是最好的结果，可见把“悖论”的定义改为“增加运量，运费不增”更合适些（这时定理2中的（20）式应变＞为≧）。
可以利用位势和闭回路研究悖论产生的条件［16］。事实上，如果
（26）
则“悖论”一定发生，这时以点（i,j）做闭回路，适当调整，即可改进原来的结果，但条件（26）只在非退化情形是充要的，在退化情形（对“悖论”问题这是常见的）它只是充分的，如对例1即（5）用这种方法调整只能得到（24），而不能得到（25），更谈不上得到最终的最佳方案了。
如果用最小调整法求最优解，则可以证明只要某次调整的调整差大于所调入行的最小费用，即可断定“悖论”现象一定发生，从而在调整中即可进行挖潜处理，而不必等到求出最优解之后再调整。
发点收点
发量
收量
（1）
的数学模型如下：
它包含m×n个变量，（m+n）个约束条件，若用单纯形法求解，由于规模太大，计算起来非常繁杂，人们依据运输问题的特殊结构，创造出各种专门求解的简易方法，下面介绍两种最简单的方法。
§1 匈牙利方法首先容易证明对于运输问题（1）的费用矩阵的每一行，减去该行的最小值，之后，再对每一列减去该列的最小值，以所得新矩阵作为费用，这两个运输问题等价。
例 1 求解运输问题:
(5)
设经过上述处理后如下：
3 3 6 2 1 2
（6）
（6）中每行、每列都至少有一个0。显然如能找到运输问题的一个可行解,具下述性质：所有的地方，运费,则这个可行解一定是最优解。
那么如何找具有上述性质的可行解呢？设想在的地方与有一条边相连，对有边相连的二点实行足量分配，可得一方案。其中的边（简记）看作属于匹配的边，检查该方案是否满足行、列平衡条件（2）、（3），若满足则它即为最优解，否则必有某行中所有的和小于,于是于前标号，即是未盖点，考虑行的格子，在这些格子所在列上面标号,然后检查这些列使的行，看行前是否标号，对未标号的行前边标以列下标,再检查行中的那些列，若该列之和等于,则继续对的行进行标号，若该列之和小于,则说明已找到连接两个未盖点和的增广链（按标号倒向追踪即得此增广链），于是像求最大匹配那样，只对增广链上的格子进行足量调整，调整量等于行剩余发量、列剩余收量及增广链上中那些需减少分配量的诸值之最小者，对增广链上的格子依次一增一减。
按上述规则考察（6），则应在前标以，4行只一个0，故只须在上方标以4,4列中，大于0，从而前得到标号4（不产生新标号，作罢），继之上方得到标号1。至此，标号过程已不能再进行下去。
当标号不能再进行时，须对费用矩阵作下述变换：
先令等于已标号行和未标号列上的最小值，则必有＞0（因为若＝0，则等于0的那些列按规定应被标号），然后对所有已标号行减去，对所有已标号列加上，这样作的结果可由下面的表看出：
有标号的列
无标号的列
有标号的行
Ⅰ 不变
Ⅱ －
无标号的行
Ⅲ ＋
Ⅳ 不变
因为在表的第Ⅱ块中所有的元素都减少了。所以一定会多出一些0来，但在Ⅲ中可能减少一些0，注意这些0的格子一定有。不然，按规定对应的行就应该被标号了。这就保证了经等价变换后，的仍是在费用为0的格子里取得，故一旦满足（2）和（3），便是最优解了。
在对费用矩阵作变换之后，在新的矩阵上重复前述标号过程（可在原先标号的基础上往下做）直到求得最优解为止。
对于（6），已标号行和未标号列的最小值＝2，变换后的矩阵及标号情形见下表：
这里已标号，但该列之和小于，故已得增广链：
（4，4） （1，4） （1，6）
调整量。今于（4，4）处加1，（1，4）处减1，（1，6）处加1，便得下表：
（7）
对（7）重复标号，变换矩阵，再标号、调整的过程（总共调整4次），最后得：
此即最优解。它与用闭回路法得到的结果相同。
可用对偶理论对上述方法做出解释，故亦称原始对偶算法，这种方法被认为是比较有效的。
§2 最小调整法上节给出的方法是从（原问题或对偶问题的）可行解出发，寻找目标函数值有所改善的另一可行解。下边介绍的最小调整法不是从可行解出发，而是先置行平衡条件（2）于不顾，从满足列平衡条件（3）且使目标函数（4）取最小值的方案开始，然后通过适当调整，逐步实现行平衡，每次调整必须遵循如下二原则
（一）不得破坏列平衡条件（3），且对同一调整量，调整后的方案使目标函数（4）增值最小。
（二）按能以最少次数完成整个调整来确定调整量，即足量调整。
下面结合§1例1具体说明实现上述思想的步骤。
（A）对费用矩阵C先作行、列减值处理（此步并非必要但常能减少调整次数），所得矩阵不妨仍记为C，然后按C之各列最小值（若不唯一可适当任取其一）。
做如下方案：，其余，并称为最小方案，对例1的费用矩阵（6），最小方案为（的非0元素用方框标出）：
（8）
（B）检查是否满足行平衡条件（2），若满足，则即为最优方案。否则记
称使的行为调出行，的行为平衡行，的行为调入行，转（C）。
（8）中，显然不满足行平衡条件（2），其中2，3行是调出行，1，4行是调入行，无平衡行。
（C）检查是否有平衡行。若无，计算所谓最小直接差：{，且k为调出行,S为调入行}= (9)
则由原则（二），相应的调整量应为
（10）
据此做如下直接调整：
，，其余 （11）
若调整差（13）不唯一，则逐一处理，调整后的方案记为，转（B）。
若有平衡行，转（D）。
对（8），易见最小直接差（可先计算每列的最小直接差，再取它们中的最小者）及调整量为
，
调整后的方案为（为明显起见，调整路线用箭头在中标出）：
（12）
其中（1）行已变成平衡行。
（D）在有平衡行时，除了考虑直接差外，还要计算所谓间接差，即由调出行调一定数量于某些平衡行，再由这些平衡行调相同数量于其它平衡行，经中转最后至调入行所产生的费用增值。间接差的一般形式如下：
（13）
其中行是调出行，是调入行，是平衡行，且需满足条件，S＝0，，把（13）的最小值与（9）比较，取二者较小者为调整差，若是间接差（13），则调整量为
（14）
并做如下间接调整：
， （15）
记调整后的方案为，转（B），最后至某步P，若满足（2），则其即为最优方案。
由（12），易见调整差为
故可进行二次调整，每次调整量均为，得:
(16)
(16)中仍有非平衡行，继续调整：
，，得:
已满足行平衡，故为最优解。
若把前边所述的“行”换成“列”，即按各行最小值求最小方案，逐步调整使之满足列平衡（3），方法可照样实行。
可以严格证明由最小调整法得到的可行方案是最优方案（由于证明较长，这里略去），并且若所给数据是整数（进而可为有理数），则调整终止于有限步。至于调整次数，如果均为直接调整，则最多不会超过m+n-2次，若还含有间接调整，次数反而会更少，这是因为由最小方案到最优方案，总共增加的非0元素可不超过m-1，直接调整一次至多增一非0元素，而间接调整，如中经t个平衡行，则最多可增加（t+1）个非0元素，从而可更快地得到最优方案。实际上，调整次数一般也就是m左右，这比前两种方法的调整次数要少得多，特别对m较小而n较大的“狭长表”，方法格外有效。而发点较少，收点较多正是实际中常见的。例如象下面这样一个具3个发点、8个收点的问题：
只须直接调整二次，即可得到最优方案（调整路线在表上用箭头标出）。
方法对于退化问题尤其好用，而且退化程度越高，调整次数越少，比如对分配问题（它可看成是高度退化的特殊运输问题）如其最小方案中有q个调入行，则易证调整次数最多不超过q，同时这里也不存在退化型的循环问题。
最小调整法还表现出灵活方便的特点，对于不平衡以及需求是可变动的问题它可以不加区别的处理，用它还能解能力受限一类运输问题等。
当然，当m、n较大时，虽说求最小直接差并不难，但求最小间接差则要费点事，不过也不必穷举所有间接差，可以证明如果该次前的间接调整不产生新的平衡行，则最小间接差（13）中的每一括号内的数均非负，此时最小直接差即可作为上界，按（13）累计求和时，一旦超过了这个上界就不必再算下去了。总之，可以给出一个计算调整差的一般程序，它类似于求最短路的标号算法，实算表明按该程序求调整差，计算量并不大。
§3 运输问题“悖论”
在运输问题中，出现一个奇怪而有趣的现象：在最优方案的基础上再增加收发量运费反而减少了，这种现象称为运输问题“悖论”。用最小调整法很容易解释这种现象，并获得产生“悖论”的充要条件。
设是最小方案，是最优方案，为叙述方便先引入下面的定义。
定义1 对于最小方案和最优方案，若，则称为新值点；若且i为的调出行，则称点为旧值点。
定义2 对于以新值点为起点，旧值点为终点的路线：
（17）
如果其中自起点始，排在奇数位置上的点满足，则称之为的反调路线，而定义沿（17）的反调差和反调量分别为
（18）
（19）
有了以上的准备可以得到如下结果。
定理2 运输问题（1）产生“悖论”的充要条件是最优解中存在反调路线（17），且由（18）定义的反调差满足
（20）
这里是新值点所在的行。
注意，在研究“悖论”现象时，不能对费用矩阵C做行列减值变换，因为这里要比较既不同行也不同列的费用值。
现在对最优解，沿反调路线（17），做一次反调量为的反调整，然后于处增加，则得如下方案：
，，其余 （21）
则与比较，方案于行多发，于L列多收，其余各行、列收发不变，若（20）式成立，则相应于的运费：
(22)
可见多运了，运费反而减少了（。
产生了“悖论”现象，说明在最优解的基础上还有潜力可挖（当然也说明原来的收发布局不协调）。以上实际是给出了挖潜调整的具体步骤，对每一条满足（20）的反调路线均实行上述调整，最后便得到不仅运量增加最多而且所耗费用最少的所谓最终最佳方案。
例2 仍以§1例1为例，其最小方案（方框数字）及最优方案（圆圈数字）标示如下：
（23）
检查它的反调路线，发现已有一条：
的反调差，故必产生“悖论”现象，而，调整后，3行、4列各增加了3：
（24）
继续考察，发现还有两条满足（20）的反调路线：
调整后的方案为：
（25）
它的最优值为＝88，减少了8，而收发量增加了5。
（25）中已无满足（20）的反调路线，就是说再增加运量，运费不会再减少，但是存在一条反调路线：（1,6）→（3,6），它使（20）中的严格不等式变为等式，这意味着沿此路线做一次反调整，可以增加运量，但运费不减少，与（25）相比它当然更好些，但严格说来，对（25）而言，不能算是“悖论”发生，因运费并未减少，但对原问题（5）却是发生了，而且是最好的结果，可见把“悖论”的定义改为“增加运量，运费不增”更合适些（这时定理2中的（20）式应变＞为≧）。
可以利用位势和闭回路研究悖论产生的条件［16］。事实上，如果
（26）
则“悖论”一定发生，这时以点（i,j）做闭回路，适当调整，即可改进原来的结果，但条件（26）只在非退化情形是充要的，在退化情形（对“悖论”问题这是常见的）它只是充分的，如对例1即（5）用这种方法调整只能得到（24），而不能得到（25），更谈不上得到最终的最佳方案了。
如果用最小调整法求最优解，则可以证明只要某次调整的调整差大于所调入行的最小费用，即可断定“悖论”现象一定发生，从而在调整中即可进行挖潜处理，而不必等到求出最优解之后再调整。
