问题、分配运输问题、最短路径问题、最小费用最大流问题、送货（集货）问题等，下面
就这些问题的优化求解进行介绍。
12。1 产销运输问题
销售商在组织某一产品销售时，需要从多个厂家或产地采购，运输到其不同的销售门
店，而每个厂家或产地可提供的产品数量和运价各不相同，如何组织运输才能使总运费最
低？或生产厂家从多个地方采购原料时，各地原料可供数量和运价不同，如何确定各地原
料调拨量，才能使运输费用最省？这就是产销运输问题，根据供求双方的物资数量关系，
可分为产销平衡的运输问题和产销不平衡的运输问题。
12。1。1 产销平衡的运输问题
12。1。1。1 模型分析
产销平衡的运输问题一般可表述为：某种物资有m个产地A 1，A2；。。。；Am，其供应量分为
a1；a2；。。。；am；有n 个销地B1；B2；。。。；Bn；其销量分为b 1；b2；。。。；bn；产地物资供应量总合等于销
地物资销量（需求量）总合；从产地A i到销地Bj的物资量和单位物资运价为分为x ij；cij；求
此时调运物资最佳方案。
对此问题可有下述线性规划模型：
n
min z
=ΣΣ（m） cij xij i=1 j=1
s。t。
Σ（n） xij
= ai （i
=
1；。。。； m）
j=1
（12。1）
Σ（m） xij = bj
（ j = 1；。。。； n）
i=1
Σ（n） bj
=Σ（m） ai
j=1 i=1
xij
≥
0（i
=
1；。。。； m； j
=
1；。。。； n）
12。1。1。2 表上作业法求解
12…1
上述模型是一种线性规划模型，自然可以用单纯形法求解，但是根据其特殊结构而建
立的表上作业法比起用单纯形法要简单得多。其思路为：由初始运输方案开始，通过检
验、改进，最后获得最优运输方案。
下面结合例12…1具体说明表上作业法的步骤和方法：
例12…1设有两个煤矿供应三个城市用煤，煤矿A 1和A2的日产量分别为a 1=200吨；a 2=250
吨。三城市（B 1；B2；B3）的日销量分别为b 1=100吨，b 2=150吨，b 3=200吨。假定每吨货物的
社会运输费与出行公里线性有关，取cij代表煤矿I至城市j的最短距离。已知c 11=90公里，
c12=70公里，c 13=100公里，c 21=80公里，c 22=65 公里，c 23=80公里。问如何安排运输使运输
费用最省？
解：设xij为煤矿I运往j的煤量，根据每个煤矿产煤总量和城市的用煤总量，
xij（I=1；2；j=1；2；3）必须满足下列条件：
x11＋x12＋x13=200
x21＋x22＋x23=250
x11＋x21=100
x12＋x22=150
x13＋x23=200
目标函数为：minz=90x11＋70x12＋100x13＋80x21＋65x22＋80x23
1。列运输平衡表
列表时要求表内供销平衡，并将运费标入表内空格，如下表12…1所示：
表 12…1 运输平衡表
B1 B2 B3供应量
A1 X11 X12 X13 200
A2 X21 X22 X23 250
需求量 100 150 200 450
需
供
90 70 100
80 65 80
2。建立初始调运方案
鉴于最好运输方案是使总运费最小，采用最小元素法，即在平衡表中挑取运价最小或
较小的供需点格子尽量优先分配的调运方法。一行（或一列）满足了，就划去一行（或一
列），如果运费相等时可任选一个，直到全部分配完为止。分配时注意一个问题，即分配
数字的格数要为“行数＋列数…1”，若分配完时出现规定数时，应在适当的空格补零，这个
补零的格子在数量上是零，但要当成非零数字格对待。如表12…2所示：
表 12…2 初始调运方案表
B1 B2 B3供应量
A1 0 200 200
需
供
90 70 100
80 65 80
12…2
A2 100 150 250
需求量 100 150 200 450
表12…2先从A 2；B2（c22最小）开始，确定c22=150；划去余下的B 2 列，然后确定x21=100（c21
为剩下方格中最小运价），划去余下的B 1列，A2的供应量也同时得到满足，故此时余下的A 2
也被划去，最后确定x12为200，形成初始调运方案。
3。方案的检验和调整
（1）闭回路
从调运方案的任意空格出发，沿水平方向或垂直方向前进，而遇到填有数字的方格，
折转90度前进，当然可以直接穿过数字格和空格，但只能遇有数字的格才能折转，只能水
平、垂直方向前进，不能对角线移动，这样经过多次折转直到回到原来出发的空格，形成
一条闭回路。
（2）位势法检验
①由方案表列出检验表。表中行列数与方案表一样，运价在每个格的右上角，原方案
表中的空格填写检验数，原方案表中的数字格为检验表中的空格，原方案表中的供应量、
需求量格填写行与列的位势，称为行或列位势格。
②求位势。记第i行位势为u i ，第j列位势为vj，可任选一个位势格填任意数，通常取0
作为该格的位势。其它位势格的位势由下列法则求出：每个空格右上角的运价c ij等于该行
位势与该列位势之和，即cij=ui＋vj。 例如在表12…2中，任取左下端的位势格为0，由上述法
则求出其它4个位势格的位势；如表12…3。
表12…3 位势表
B1 B2 B3 Vj
A1 0 200 90
A2 100 150 80
Ui 0 …15 10
需
供
90 70 100
80 65 80
③求检验数。若空格位于第i行第j列，则其检验数σij按下式求出：
σ=
c
。
u
。
v
ij
ijij
例如由表12…3可求出1行2列空格的检验数σ 12=70＋15…90=…5，其它如检验数表12…4所
示。
表12…4 检验数表
B1 B2 B3 vj
A1 …5 90
供
需
90 70 100
80 65 80
12…3
A2 …10 80
ui 0 …15 10
由表12…4知，有负的检验数存在，这表明12…2所给的运输方案不是最优的，需要进行
调整。
（3）调整运输方案。当运输表对应的检验表中有负的检验数时，需在运输方案表上对
运输方案进行调整。
①确定闭回路。在需调整的运输方案表上选取对应的检验数为负的格作为调整格，
若有两个以上格的检验数为负，选其中检验数绝对值最大的格为检验格，从检验格出发在
运输方案表上作闭回路。
例如在表12…4中，A2B3格的检验数是…10，为绝对值最大的负检验格，故选取此格为调
整格，并用虚线在运输方案表上作闭回路，如表 12…5所示。
表12…5 闭回路表
B1 B2 B3供应量需
A1 0 200
200
A2 100 150
250
需求量 100 150 200 450
90
供
70 100
80 65 80
②在闭回路上作运输量最大的调整；得出新的运输方案。从空格开始，沿闭回路在各偶
数格中挑选运量最小的作为调整量，调整闭回路各点的运输量。
例如在表12…5中，闭回路上偶数格最小运输量为min（200；100）=100；调整闭回路各点运
输量，得表12…6。
表12…6 新运输方案1表
B1 B2 B3供应量
A1 100 100
200
A2 150 100
250
需求量 100 150 200 450
需
供
90 70 100
80 65 80
（4）返回（2），对新运输方案进行位势法检验。若无负检验数，则此方案为最优方
案，否则继续进行调整。
例如对于表12…6，得检验表12…7。
12…4
表12…7 新运输方案1检验表
B1 B2 B3 vj
A1 …15 90
供
需
90 70 100
A2
10
70
ui 0 …5 10
80 65 80
表12…7中有负得检验数，继续进行调整，得新运输方案表12…8。
表12…8 新运输方案2表
B1 B2 B3
供应量
A1 100 100 200
A2 50 200 250
需求量 100 150 200 450
对表12…8进行检验，得检验表12…9
表12…9 新运输方案2检验表
需
供
90 70 100
80 65 80
B1 B2 B3 Vj
A1 15 90
A2 …5 85
ui 0 …20 …5
表中有负检验数，继续进行调整，得新运输方案表12…10
表12…10 新运输方案3表
供
需
90 70 100
80 65 80
B1 B2 B3
供应量
A1 50 150 200
90 70 100
80 65 80
需
供
12…5
A2 50 200 250
需求量 100 150 200 450
对此运输方案进行检验，得检验表12…11
表12…11 新运输方案3检验表
B1 B2 B3 Vj
供
需
A1 10 90
A2 5 80
Ui 0 …20 0
90 70 100
80 65 80
从表12…11中可以看到，检验数全是正数，因此表12…10中的运输方案为最优方案，即
应确定A1向B1、B2调运煤数量分别为50、150；A2向B1、B3调运数量分别为50、200。
二。产销不平衡时的运输问题
（一）产大于销的运输问题
对于产量大于销量即Σ（n） bj
Σ（m） a
的运输问题，必然有一些销地不能得到满足，发生
i
j=1 i=1
缺货，此时引入虚拟供应点，并设其相应运价为0。这样，就可以用产销平衡的表上作业法
求解销大于产的运输问题。
12。2 分配运输问题
在运输过程中经常遇到这样的问题，需完成几条运输线路的任务，恰好有几个运输单
位可承担这些任务。由于每个单位的情况各不相同，其完成各项任务的效率（或效益）也
不同，如何安排这些运输单位去完成任务，使效率（或效益）也最高，这一类问题统称为
分配问题。
12。1。1 模型分析
例12…2某材料厂有B 1、B2、B3三台叉车可分配给A 1、A2、A3三个仓库进行搬运作业，其
中任一叉车都可以在任一仓库中进行搬运工作，只是搬运作业费不同，各台叉