第四节 运输问题一,运输问题的一般提法在经济建设中，经常碰到物资调拨中的运输问题。
例如 煤、钢材、粮食、木材等物资，在全国都有若干生产基地，分别将这些物资调到各消费基地去，应如何制定调运方案，
使总的运输费用最少？
，,? 1A
运输问题的一般提法是：
1.产销平衡问题 1 m 1 m
1 n 1 n
11
A A,
B B,
,,A B c
AB
mn
i j i j ij
ij
i j ij
m a a
n b b
ab
x
已知,个产地,,,产 量分别是,,,
个销售地,,,销量分别是,,,
产销平衡 即 由 的运价为 。
问:应 如何调运使总费用最省即求 的运量,使运费可达极小化。
2.产销不平衡问题此时分为两种情形来考虑：
供不应求,即产量小于销量时有供过于求,即产量大于销量时有求解的形式来这两种情形都可以化为 ji ba
二,运输问题的模型产销平衡问题模型
11
1
1
1,......
1,......
0
mn
ij ij
n
ij i
j
m
ij j
i
ij
M in z a x
x a i m
x b j n
x
将约束方程式展开可得
11 1 1
21 2 2
1
11 21 1 1
12 22 2
n
n
m m n m
m
m
x x a
x x a
x x a
x x x b
x x x
2
12
n n m n n
b
x x x b
约束方程式中共 mn个变量,m+n个约束。
上述模型是一个线性规划问题。但是其结构很特殊，特点如下：
1.变量多（ mn
个），但结构简单。
技术系数矩阵
1 1
11
A= 1 1
1 1 1
1 1 1
ijab
2.m+n个约束中有一个是多余的（因为其间含有一个平衡关系式 ）
所以 R(A)=m+n-1，即解的 mn个变量中基变量为 m+n-1个。
三,运输问题的解法运输问题仍然是线性规划问题，可以用线性规划法中的单纯形法来解决。但是：
1.运输问题所涉及的 变量多，造成单纯形表太大；
2.若把技术系数矩阵 A中的 0迭代成非 0，
会使问题更加复杂。
以上两个原因使得我们不得不利用运输问题的特点设计出它的特殊解法 —— 表上作业法 。
表上作业法，实质上还是单纯形法。其步骤如下：
1.确定一个初始可行调运方案。 可以通过最小元素法、西北角法,Vogel 法来完成；
2.检验当前可行方案是否最优,常用的方法有闭回路法和位势法，用这两种方法计算出检验数，从而判别方案是否最优；
3.方案调整,从当前方案出发寻找更好方案，常采用闭回路法。
（ Ⅰ ）运输问题的常用解法：
最小元素法 （确定初始方案） → 闭回路法 （检验当前方案） → 闭回路法 （方案调整）
以下面例题说明这种方法的具体步骤：
例 12：某食品公司下设 3个加工厂 A1,A2,A3，
和 4个门市部 B1,B2,B3,B4。各加工厂每天的产量、各门市部每天的销售量以及从各加工厂到各门市部的运价如下表所示。
问：该公司应如何调运，在满足各门市部销售需要的情况下，使得运费支出为最少？
门市部加工厂
B1 B2 B3 B4 产 量
A1
A2
A3
7
4
9
销 量 3 6 5 6 20
门市部加工厂
B1 B2 B3 B4
A1
A2
A3
3 11 3 10
1 9 2 8
7 4 10 5
产销平衡表 单位：吨单位运价表 单位：元 /吨解,1.确定初始方案,
(最小元素法基本思想：就近供应，即从单位运价表上最小的运价开始确定产销关系，以此类推，
直到给出初始方案为止 )
① 从运价表上找出最小运价 C21=1,A2 先保证供应
B1,X21=3,划去运价表上 B1 列 ；
②再从运价表上其余元素中找到最小的运价 C23=2，
加工厂 A2 应供给 B3,X23=1，划去 A2行；
③再从运价表上其余元素中找到最小的运价 C13=3，
所以 A1先保证供应 B3,B3 尚缺 4单位，因此 X13=4，
划去 B3 列。
以此类推，得到一初始方案（如下图）：
X21=3,X32=6,X13=4,X23=1,X14=3,X34=3（有数格）
X11=X31=X12=X22=X33=X24=0（空格）
B1 B2 B3 B4
A1 4 3
A2 3 1
A3 6 3
注：
（ ⅰ ） 有数格是基变量，共 m+n-
1=3+4-1=6个。空格是非基变量，
共划去 m+n=7条线；
（ ⅱ ）如果填上一个运量之后能同时划去两条线（一行与一列），就须在所划去的该行或该列填一个 0，
此 0格当有数个对待。
初始方案运费
Z0=3× 1+6× 4+4× 3+1× 2+3× 10+3× 5=86(元 )
2.检验 （闭回路法,计算空格的检验数）
①找出任意空格的闭回路 — 除此空格外，其余顶点均为有数格。如可找 （ A1 B1 ） → （ A1 B3 ） → （ A2 B3 ） →
（ A2 B1 ）；
②计算出空格的检验数 — 等于闭回路上由此空格起奇数顶点运价与偶数顶点运价的 代数和 。如 σ11＝ c11-
c13+c13-c21=3-3+2-1
③ 计算出此空格的检验数 σij,若 σij ≥０，则该方案为最优方案，否则转３；
注：检验数的经济意义，以 σ11为例，空格表示原方案中 X11=0,
即 A1 → B1 的运输量为 0。若试着运 1单位，则这样所引起的总费用的变化恰是 σ11,可见检验数 σij的意义是,Ai → Bj增运 １
单位所引起的总费用的增量。 σij＞ ０,说明若增运一单位则在总运输量不变情况下，总运费会增加。此时不应在 Ai → Bj上增运。
3.调整,从 σij 为最小负值的空格出发,对其闭回路上的奇数顶点运量增加 θ,偶数顶点的运量减少 θ(这才能保证新的平衡 ),其中 θ为该空格闭回路中偶数顶点的最小值。
∵ σ24<0,∴ 从（ A2 B4） 出发其闭回路上 θ=1，调整后得到一个新方案（如下表），运量为 θ=1的 （ A2 B3）
变空格，得到新方案后再转 2。
经再计算新方案的检验数全部大于 0。所以，该新方案为最优方案，可计算得总运费为 85元。
注：若闭回路的偶数顶点中同时有两个格以上运量为 θ，
则调整后其中一个变空格，
其余填 0。（保证基变量个数不变）
3 6
13
25
（ Ⅱ ）运输问题的其他解法简介
1.确定初始方案的方法之二 — 西北角法仍以例 12为例 (如表 ),其原则是每次均考虑西北角位置,
初始方案的运费为
3× 3+4 × 11+2
× 9+2 × 2+3 ×
10+6 ×
5=135>86
显然,由于它仅考虑地理位置而不考虑运价,其效果不如用最小元素法好,
2.确定初始方案的方法之三 — 伏格尔法（ Vogel法）
⑴ 求各行各列运价最小与次小之差额，选其中最大的行或列中最小运价进行供应；
⑵如果某一行或某一列按照这种方法已被供应满，则划去该行或该列，在剩下的行列中重复这种方法，
即得最优方案。 如上图，一步即可得最优解。
3.求空格检验数的方法之二 — 位势法原理：设有运输问题
()
0
ij ij
ij i
j
ij j
i
ij
M in Z c x
xa
p x b
x
()
()
,
i i j j
i j i j
ij
Ma x W a u b v
u v c mn
d
uv
个约束为自由变量的对偶问题为
( ),( * )i j i j i j i jd u v c对 加松弛变量 则 + +
问题,σij与原问题有什么关系？
由对偶性质,σij是原问题结构变量 xij 的检验数当 xij是基时,σij=0，此时有 由此求 ui 和
vj，再代回（ *）式求非基变量的 σij（空格检验数）
1 ()BC C B A 自证
i j iju v c
当找出 σij<0的格后，调整方法仍用闭回路法。
仍以例一为例：对偶变量表面上是 7个，实际上只有 6个。 ∴ 有一个是自由变量。
作法如右表，结果与闭回路法一样，但比闭回路法简单，尤其当变量多的时候，用位势法比较好。
位势法步骤：
①由有数格 ui+vj求得 ui和 vj （先令 u1=0）,原有数格（基变量）的检验数 σij=0；
②空格 σij=cij-(ui+vj)；
③由此可得检验数表。
（ Ⅲ ）产销不平衡的运输问题
1.产大于销的情况：
1
0
n
ij i
j
ij j
i
ij
M in Z C X
xa
xb
x
添加松弛变量 xin+1
1
1
0
n
ij i
j
ij j
i
ij
M in Z C X
xa
xb
x
xin+1的定义：由 Ai向 Bn+1的运量，而 Bn+1并不存在，
相当于增加了一个虚设的销地 — Ai自己的仓库里，自己往自己的地方运，运费 cin+1显然为 0。
实际上 xin+1即的剩余量。
A1
Am
B1 …… Bn Bn+1
C11 0
0
C1n
Cm1 Cmn
产大于销的单位运价表产大于销的产销量表
A1
Am
a1
am
B1 …… Bn Bn+1
b1 …… bn
1 i jabnb
2.销大于产的情况：
1
0
m
ij j
i
ij i
ij
Min Z C X
xb
xa
x
添加松弛变量 xm+1j
1
1
0
m
ij j
i
ij i
ij
Min Z C X
xb
xa
x
同理，此时 xm+1j的意义为销售短缺的量，同样,Am+1
不存在,cm+1j为 0。
销大于产的产销量表
A1
Am
a1
am
B1 …… Bn
b1 …… bn
Am+1
1 j ia b am
A1
Am
B1 …… Bn
C11
0 0
C1n
Cm1 Cmn
销大于产的单位运价表
Am+1 ……
例如 煤、钢材、粮食、木材等物资，在全国都有若干生产基地，分别将这些物资调到各消费基地去，应如何制定调运方案，
使总的运输费用最少？
，,? 1A
运输问题的一般提法是：
1.产销平衡问题 1 m 1 m
1 n 1 n
11
A A,
B B,
,,A B c
AB
mn
i j i j ij
ij
i j ij
m a a
n b b
ab
x
已知,个产地,,,产 量分别是,,,
个销售地,,,销量分别是,,,
产销平衡 即 由 的运价为 。
问:应 如何调运使总费用最省即求 的运量,使运费可达极小化。
2.产销不平衡问题此时分为两种情形来考虑：
供不应求,即产量小于销量时有供过于求,即产量大于销量时有求解的形式来这两种情形都可以化为 ji ba
二,运输问题的模型产销平衡问题模型
11
1
1
1,......
1,......
0
mn
ij ij
n
ij i
j
m
ij j
i
ij
M in z a x
x a i m
x b j n
x
将约束方程式展开可得
11 1 1
21 2 2
1
11 21 1 1
12 22 2
n
n
m m n m
m
m
x x a
x x a
x x a
x x x b
x x x
2
12
n n m n n
b
x x x b
约束方程式中共 mn个变量,m+n个约束。
上述模型是一个线性规划问题。但是其结构很特殊，特点如下：
1.变量多（ mn
个），但结构简单。
技术系数矩阵
1 1
11
A= 1 1
1 1 1
1 1 1
ijab
2.m+n个约束中有一个是多余的（因为其间含有一个平衡关系式 ）
所以 R(A)=m+n-1，即解的 mn个变量中基变量为 m+n-1个。
三,运输问题的解法运输问题仍然是线性规划问题，可以用线性规划法中的单纯形法来解决。但是：
1.运输问题所涉及的 变量多，造成单纯形表太大；
2.若把技术系数矩阵 A中的 0迭代成非 0，
会使问题更加复杂。
以上两个原因使得我们不得不利用运输问题的特点设计出它的特殊解法 —— 表上作业法 。
表上作业法，实质上还是单纯形法。其步骤如下：
1.确定一个初始可行调运方案。 可以通过最小元素法、西北角法,Vogel 法来完成；
2.检验当前可行方案是否最优,常用的方法有闭回路法和位势法，用这两种方法计算出检验数，从而判别方案是否最优；
3.方案调整,从当前方案出发寻找更好方案，常采用闭回路法。
（ Ⅰ ）运输问题的常用解法：
最小元素法 （确定初始方案） → 闭回路法 （检验当前方案） → 闭回路法 （方案调整）
以下面例题说明这种方法的具体步骤：
例 12：某食品公司下设 3个加工厂 A1,A2,A3，
和 4个门市部 B1,B2,B3,B4。各加工厂每天的产量、各门市部每天的销售量以及从各加工厂到各门市部的运价如下表所示。
问：该公司应如何调运，在满足各门市部销售需要的情况下，使得运费支出为最少？
门市部加工厂
B1 B2 B3 B4 产 量
A1
A2
A3
7
4
9
销 量 3 6 5 6 20
门市部加工厂
B1 B2 B3 B4
A1
A2
A3
3 11 3 10
1 9 2 8
7 4 10 5
产销平衡表 单位：吨单位运价表 单位：元 /吨解,1.确定初始方案,
(最小元素法基本思想：就近供应，即从单位运价表上最小的运价开始确定产销关系，以此类推，
直到给出初始方案为止 )
① 从运价表上找出最小运价 C21=1,A2 先保证供应
B1,X21=3,划去运价表上 B1 列 ；
②再从运价表上其余元素中找到最小的运价 C23=2，
加工厂 A2 应供给 B3,X23=1，划去 A2行；
③再从运价表上其余元素中找到最小的运价 C13=3，
所以 A1先保证供应 B3,B3 尚缺 4单位，因此 X13=4，
划去 B3 列。
以此类推，得到一初始方案（如下图）：
X21=3,X32=6,X13=4,X23=1,X14=3,X34=3（有数格）
X11=X31=X12=X22=X33=X24=0（空格）
B1 B2 B3 B4
A1 4 3
A2 3 1
A3 6 3
注：
（ ⅰ ） 有数格是基变量，共 m+n-
1=3+4-1=6个。空格是非基变量，
共划去 m+n=7条线；
（ ⅱ ）如果填上一个运量之后能同时划去两条线（一行与一列），就须在所划去的该行或该列填一个 0，
此 0格当有数个对待。
初始方案运费
Z0=3× 1+6× 4+4× 3+1× 2+3× 10+3× 5=86(元 )
2.检验 （闭回路法,计算空格的检验数）
①找出任意空格的闭回路 — 除此空格外，其余顶点均为有数格。如可找 （ A1 B1 ） → （ A1 B3 ） → （ A2 B3 ） →
（ A2 B1 ）；
②计算出空格的检验数 — 等于闭回路上由此空格起奇数顶点运价与偶数顶点运价的 代数和 。如 σ11＝ c11-
c13+c13-c21=3-3+2-1
③ 计算出此空格的检验数 σij,若 σij ≥０，则该方案为最优方案，否则转３；
注：检验数的经济意义，以 σ11为例，空格表示原方案中 X11=0,
即 A1 → B1 的运输量为 0。若试着运 1单位，则这样所引起的总费用的变化恰是 σ11,可见检验数 σij的意义是,Ai → Bj增运 １
单位所引起的总费用的增量。 σij＞ ０,说明若增运一单位则在总运输量不变情况下，总运费会增加。此时不应在 Ai → Bj上增运。
3.调整,从 σij 为最小负值的空格出发,对其闭回路上的奇数顶点运量增加 θ,偶数顶点的运量减少 θ(这才能保证新的平衡 ),其中 θ为该空格闭回路中偶数顶点的最小值。
∵ σ24<0,∴ 从（ A2 B4） 出发其闭回路上 θ=1，调整后得到一个新方案（如下表），运量为 θ=1的 （ A2 B3）
变空格，得到新方案后再转 2。
经再计算新方案的检验数全部大于 0。所以，该新方案为最优方案，可计算得总运费为 85元。
注：若闭回路的偶数顶点中同时有两个格以上运量为 θ，
则调整后其中一个变空格，
其余填 0。（保证基变量个数不变）
3 6
13
25
（ Ⅱ ）运输问题的其他解法简介
1.确定初始方案的方法之二 — 西北角法仍以例 12为例 (如表 ),其原则是每次均考虑西北角位置,
初始方案的运费为
3× 3+4 × 11+2
× 9+2 × 2+3 ×
10+6 ×
5=135>86
显然,由于它仅考虑地理位置而不考虑运价,其效果不如用最小元素法好,
2.确定初始方案的方法之三 — 伏格尔法（ Vogel法）
⑴ 求各行各列运价最小与次小之差额，选其中最大的行或列中最小运价进行供应；
⑵如果某一行或某一列按照这种方法已被供应满，则划去该行或该列，在剩下的行列中重复这种方法，
即得最优方案。 如上图，一步即可得最优解。
3.求空格检验数的方法之二 — 位势法原理：设有运输问题
()
0
ij ij
ij i
j
ij j
i
ij
M in Z c x
xa
p x b
x
()
()
,
i i j j
i j i j
ij
Ma x W a u b v
u v c mn
d
uv
个约束为自由变量的对偶问题为
( ),( * )i j i j i j i jd u v c对 加松弛变量 则 + +
问题,σij与原问题有什么关系？
由对偶性质,σij是原问题结构变量 xij 的检验数当 xij是基时,σij=0，此时有 由此求 ui 和
vj，再代回（ *）式求非基变量的 σij（空格检验数）
1 ()BC C B A 自证
i j iju v c
当找出 σij<0的格后，调整方法仍用闭回路法。
仍以例一为例：对偶变量表面上是 7个，实际上只有 6个。 ∴ 有一个是自由变量。
作法如右表，结果与闭回路法一样，但比闭回路法简单，尤其当变量多的时候，用位势法比较好。
位势法步骤：
①由有数格 ui+vj求得 ui和 vj （先令 u1=0）,原有数格（基变量）的检验数 σij=0；
②空格 σij=cij-(ui+vj)；
③由此可得检验数表。
（ Ⅲ ）产销不平衡的运输问题
1.产大于销的情况：
1
0
n
ij i
j
ij j
i
ij
M in Z C X
xa
xb
x
添加松弛变量 xin+1
1
1
0
n
ij i
j
ij j
i
ij
M in Z C X
xa
xb
x
xin+1的定义：由 Ai向 Bn+1的运量，而 Bn+1并不存在，
相当于增加了一个虚设的销地 — Ai自己的仓库里，自己往自己的地方运，运费 cin+1显然为 0。
实际上 xin+1即的剩余量。
A1
Am
B1 …… Bn Bn+1
C11 0
0
C1n
Cm1 Cmn
产大于销的单位运价表产大于销的产销量表
A1
Am
a1
am
B1 …… Bn Bn+1
b1 …… bn
1 i jabnb
2.销大于产的情况：
1
0
m
ij j
i
ij i
ij
Min Z C X
xb
xa
x
添加松弛变量 xm+1j
1
1
0
m
ij j
i
ij i
ij
Min Z C X
xb
xa
x
同理，此时 xm+1j的意义为销售短缺的量，同样,Am+1
不存在,cm+1j为 0。
销大于产的产销量表
A1
Am
a1
am
B1 …… Bn
b1 …… bn
Am+1
1 j ia b am
A1
Am
B1 …… Bn
C11
0 0
C1n
Cm1 Cmn
销大于产的单位运价表
Am+1 ……
