管理运筹学谢家平 博士 副教授研究领域,系统建模与优化、生产与运作管理、物流与供应链管理讲授课程,管理运筹学、管理系统工程、生产运作管理、
供应链管理、国际物流管理、企业资源计划单 位,上海财经大学 国际工商管理学院 供应链管理研究中心
E-mail,jiaping_xie@sina.com.cn
电 话,55036936(H) 65903541(O)
上海财经大学 国际工商管理学院
SHUFE
2
第五章 运输问题
运输问题是线性规划问题的特例。
产地,货物发出的地点。
销地,货物接收的地点。
产量,各产地的可供货量。
销量,各销地的需求数量。
运输问题就是研究如何组织调运，既满足各销地的需求，
又使总运费最小。
上海财经大学 国际工商管理学院
SHUFE
3
第一节 运输模型某饮料在国内有三个生产厂,分布在城市 A1,A2,A3,其一级承销商有 4个,分布在城市 B1,B2,B3,B4,已知各厂的产量,各承销商的销售量及从 Ai到 Bj的每吨饮料运费为 Cij,为发挥集团优势,公司要统一筹划运销问题,求运费最小的调运方案 。
一,运输问题举例销地产地 B1 B2 B3 B4 产量
A1 6 3 2 5 5
A2 7 5 8 4 2
A3 3 2 9 7 3
销量 2 3 1 4
上海财经大学 国际工商管理学院
SHUFE
4
第一节 运输模型
(1)决策变量 。 设从 Ai到 Bj的运输量为 xij，
(2)目标函数
minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34
(3)约束条件 。产量之和等于销量之和,故要满足：
供应平衡条件 x11+x12+x13+x14=5
x21+x22+x23+x24=2
x31+x32+x33+x34 =3
销售平衡条件 x11+x21+x31=2
x12+x22+x32=3
x13+x23+x33=1
x14+x24+x34=1
非负性约束 xij≥0 (i=1,2,3； j=1,2,3,4)
运输问题的 LP模型上海财经大学 国际工商管理学院
SHUFE
5
第一节 运输模型销地产地二、表式运输模型
A1
A2
…
Am
产量
a1
a2
…
am
B1 B2 … Bn
销地 b1 b2 … bn
c11 c12 … c1n
c21 c22 … c2n
… … … …
cm1 cm2 … cmn
x11 x12 x1n
x21 x22 x2n
xm1 xm2 xmn
上海财经大学 国际工商管理学院
SHUFE
6
第一节 运输模型
产销平衡三、运输问题的三种类型
m
i
n
j
ji ba
1 1
0
,.,,,2,1,
,.,,,2,1,
m i n
1
1
1 1
ij
m
i
jij
n
j
iij
m
i
n
j
ijij
x
njbx
miax
xcZ
上海财经大学 国际工商管理学院
SHUFE
7
第一节 运输模型
产大于销
m
i
n
j
ji ba
1 1
0
,.,,,2,1,
,.,,,2,1,
m i n
1
1
1 1
ij
m
i
jij
n
j
iij
m
i
n
j
ijij
x
njbx
miax
xcZ
上海财经大学 国际工商管理学院
SHUFE
8
第一节 运输模型
产小于销
m
i
n
j
ji ba
1 1
0
,.,,,2,1,
,.,,,2,1,
m i n
1
1
1 1
ij
m
i
jij
n
j
iij
m
i
n
j
ijij
x
njbx
miax
xcZ
上海财经大学 国际工商管理学院
SHUFE
9
第一节 运输模型决策变量 m?n 约束方程 m+n 系数矩阵的结构如下：
四、运输模型的特点
1
1
1
1
1
1
1
1
1
111
111
111
A
x11 x12 … x1n x21 x22 … x2n … … … … xm1 xm2 … xmn
m
行
n
列上海财经大学 国际工商管理学院
SHUFE
10
第二节 表上作业法
表上作业法适合于产销平衡的运输问题
求解步骤：
找出初始方案（初始基可行解）：在 m?n维产销平衡表上给出 m+n-1个数字。
最优性检验：计算各非基变量的检验数，当?ij?0最优。
方案调整与改进：确定进基变量和离基变量，找出新的基可行解。
上海财经大学 国际工商管理学院
SHUFE
11
第二节 表上作业法
最小元素法
,就近运给”，
从单位运价表中最小运价开始确定供销关系，
逐次挑选最小元素，安排运量 min{ai,bj}。
最大差额法
不能按最小运费就近供应，就考虑次小运费。
各行 (各列 )的最小运费与次小运费之差称为行差 (列查 )。 差额越大，说明不能按最小运费调运时，运费增加最多。
对最大差额处就采用最小运费调运。
一、确定初始方案上海财经大学 国际工商管理学院
SHUFE
12
第二节 表上作业法
从单位运价表中逐次挑选最小元素，安排运量 min{ai,bj}。
然后，划去该元素所在行或列：
当产大于销，划去该元素所在列；
当产小于销，划去该元素所在行。
最小元素法销地产地 B
1 B2 B3 B4 产量
A1 6 3 2 5 5
A2 7 5 8 4 2
A3 3 2 9 7 3
销量 2 3 1 4
1
30
2
22
初始基可行解,x11=2,x13=1,x14=2,x24=2,x31=0,x32=3,Z=38
上海财经大学 国际工商管理学院
SHUFE
13
第二节 表上作业法
判别方法是计算非基变量的检验数,
ij= cij – CBPij’= cij – CBB-1Pij
运输问题的目标函数要求为最小，即当?ij?0视为最优。
位势法 计算检验数
ij= cij – CBPij’= cij – CBB-1Pij
ij = cij –(ui+vj )
ui代表产地 Ai的位势量,vj代表销地 Bj的位势量。
基变量的检验数为 0，即?ij= cij –ui – vj =0，
并令 u1 =0，计算各行各列的 位势量。
二、最优性检验上海财经大学 国际工商管理学院
SHUFE
14
第二节 表上作业法
基变量的检验数?ij= cij –ui – vj =0,即 cij =ui +vj,
且令 u1 =0，计算位势量 ui和 vj
位势法销地产地 B1 B2 B3 B4 产量
A1 6 2 3 2 1 5 2 5
A2 7 5 8 4 2 2
A3 3 0 2 3 9 7 3
销量 2 3 1 4
ui
vj
0
6 2 5
-1
-3
5
上海财经大学 国际工商管理学院
SHUFE
15
第二节 表上作业法
计算非基变量的检验数?ij= cij –ui – vj
位势法（续 ）
销地产地 B1 B2 B3 B4 产量 ui
A1 6 2 3 2 1 5 2 5 0
A2 7 5 8 4 2 2 -1
A3 3 0 2 3 9 7 3 -3
销量 2 3 1 4
vj 6 5 2 5
-2
2 1 7
10 5
非基变量 x12的检验数?12= c12 –u1– v2 =-2,即让非基变量 x12从 0增到
1，可使总运费减少 2个单位。
上海财经大学 国际工商管理学院
SHUFE
16
第二节 表上作业法
确定进基变量
检查非基变量 xij的检验数?ij,按 min{?ij|?ij <0}=?lk 确定 xlk进基。
确定离基变量
非基变量 xlk进基之后，能让它的运量增加多少呢？
就要求它所在行和列的运量保持 产销平衡 。
保持产销平衡的方法是 闭回路法 。
闭回路法,以进基变量 xlk所在格为始点和终点，其余顶点均为基变量的封闭回路。
闭回路的画法,从进基变量 xlk所在格开始，用水平或垂直线向前划，
每碰到一个基变量格转 90o，继续前进，直到返回始点。
奇偶点,始点是偶点，依次奇偶相间标注；偶点标,+”,表示运量增加量；奇点标,-”,表示运量减少量。
调整量,最小可减少的运量，即奇点运量的最小值。
奇点运量的最小值所在格的基变量离基。
三、改进的方法（闭回路调整法）
上海财经大学 国际工商管理学院
SHUFE
17
第二节 表上作业法
x12 进基
最小调整量为 2,x11 离基销地产地 B1 B2 B3 B4 产量
A1 6 2 3 x
12
2
1
5
2 5
A2 7 5 8 4 2 2
A3 3 0 2 3 9 7 3
销量 2 3 1 4
+-
+ -
上海财经大学 国际工商管理学院
SHUFE
18
第二节 表上作业法
非最优方案的调整
所有偶点的值都加上调整量；
所有奇点的值都减去调整量；
获得一个新的运输方案。
销地产地 B1 B2 B3 B4 产量
A1 6 3 2 1 5 2 5
A2 7 5 8 4 2 2
A3 3 2 9 7 3
销量 2 3 1 4
基可行解,x12=2,x13=1,x14=2,x24=2,x31=2,x32=1,Z=34
2
0 3
2
2 1
上海财经大学 国际工商管理学院
SHUFE
19
第二节 表上作业法
基变量的检验数?ij= cij –ui – vj =0，且令 u1 =0，计算位势量 ui
和 vj
四、最优性检验销地产地 B1 B2 B3 B4 产量
A1 6 3 2 2 1 5 2 5
A2 7 5 8 4 2 2
A3 3 2 2 1 9 7 3
销量 2 3 1 4
ui
vj
0
4
-1
-1
3 2 5
所有非基变量 xij的检验数?ij= cij –ui– vj≥0,即得最优解。
上海财经大学 国际工商管理学院
SHUFE
20
第三节 产销不平衡问题
产销平衡的运输问题采取表上作业法求解。
产销不平衡的运输问题需划成产销平衡问题再求解。
产大于销：
虚设一个销地 Bk (多于物资在产地存储 )，其运价为 0，
销量 (存储量 )为产销量之差 bk =?ai-? bj。
产小于销：
虚设一个产地 Al (不足物资的脱销量 )，其运价为 0，产量
(脱销量 )为销产量之差 ak =? bj -?ai 。
上海财经大学 国际工商管理学院
SHUFE
21
第三节 产销不平衡问题
增加一个销地一、产大于销 销地产地 B
1 B2 B3 产量
A1 5 9 2 15
A2 3 1 7 18
A3 6 2 8 17
销量 18 12 16
销地产地 B1 B2 B3 产量
A1 5 9 2 15
A2 3 1 7 18
A3 6 2 8 17
销量 18 12 16
50-46
B4
0
0
0
4
5046
5050
上海财经大学 国际工商管理学院
SHUFE
22
第三节 产销不平衡问题
初始基可行解销地产地 B1 B2 B3 B4 产量
A1 5 9 2 0 15
A2 3 1 7 0 18
A3 6 2 8 0 17
销量 18 12 16 4
12
15
6
12 1 4
初始基可行解,x13=15,x21=6,x22=12,x31=12,x33=1,x34=4,Z=140
上海财经大学 国际工商管理学院
SHUFE
23
第三节 产销不平衡问题
最优性检验销地产地 B1 B2 B3 B4 产量 ui
A1 5 9 2
15
0 15
A2 3
6
1
12
7 0 18
A3 6
12
2 8
1
0
4
17
销量 18 12 16 4
vj
0
2
6
0 -6
3
-2
5 11 6
2 3
-2
非基变量 x32的检验数?32= -2，即让非基变量 x32进基。
上海财经大学 国际工商管理学院
SHUFE
24
第三节 产销不平衡问题
闭回路调整
– x32 进基
– 最小调整量为 12,x31 离基销地产地 B
1 B2 B3 B4 产量
A1 5 9 2 15 0 15
A2 3 6 1 12 7 0 18
A3 6 12 2
x32
8
1
0
4
17
销量 18 12 16 4
-+
- +
上海财经大学 国际工商管理学院
SHUFE
25
第三节 产销不平衡问题
非最优方案的调整
所有偶点的值都加上调整量；所有奇点的值都减去调整量。
基可行解,x13=15,x21=18,x31=0,x32=12,x31=1,x34=4,Z=34
销地产地 B
1 B2 B3 B4 产量
A1 5 9 2 15 0 15
A2 3 1 7 0 18
A3 6 2 8 1 0 4 17
销量 18 12 16 4
6 12
12
18
0 12
上海财经大学 国际工商管理学院
SHUFE
26
第三节 产销不平衡问题
基变量的检验数?ij= cij –ui – vj =0，且令 u1 =0，计算位势量 ui和 vj
最优性检验所有非基变量 xij的检验数?ij= cij –ui– vj≥0，即得最优解。
销地产地 B1 B2 B3 B4 产量 ui
A1 5 9 2
15
0 15
A2 3
18
1 7 0 18
A3 6
0
2
12
8
1
0
4
17
销量 18 12 16 4
vj
0
2
6
0 -4 -6
3
5 13 6
2 32
上海财经大学 国际工商管理学院
SHUFE
27
第三节 产销不平衡问题
增加一个产地二、产小于销 销地产地 B
1 B2 B3 产量
A1 4 1 2 10
A2 3 4 3 12
销量 8 10 5
销地产地 B1 B2 B3 产量
A1 4 1 2 10
A2 3 4 3 12
A3
销量 8 10 5
23-22
0 0 0 1
2223
2323
上海财经大学 国际工商管理学院
SHUFE
28
第三节 产销不平衡问题
初始基可行解销地产地 B1 B2 B3 产量
A1 4 1 2 10
A2 3 4 3 12
A3 0 0 0 1
销量 8 10 5
10 0
57
1
初始基可行解,x12=10,x13=0,x21=7,x23=5,x31=1,Z=46
上海财经大学 国际工商管理学院
SHUFE
29
第三节 产销不平衡问题
最优性检验销地产地 B1 B2 B3 产量 ui
A1 4 1 10 2 0 10
A2 3 7 4 3 5 12
A3 0 1 0 0 1
销量 8 10 5
vj
0
1 2
1
2
-2
2
2
1 0
– 检验数?ij≥0，得最优解,x12=10,x13=0,x21=7,x23=5,x31=1,Z=46
– 由于非基变量 x33 的检验数?33=0，为多最优解。
让 x33进基,x31离基,得另一最优解,x12=10,x13=0,x21=8,x23=4,x33=1
上海财经大学 国际工商管理学院
SHUFE
30
第四节 运输模型的应用
短缺资源分配，“产小于销”，需注意产销配比问题。
上例 x12=10,x13=0,x21=7,x23=5,x31=1,表示销地 B1脱销 1个单位；
然而 x12=10,x13=0,x21=8,x23=4,x33=1,则表示销地 B3 脱销 1个单位；
但销地 B3 的销量为 5，本身就很少，不允许脱销，如何处理呢？
自来水分配问题,水价 90元 /kt，管理费 45元 /kt，引水费如下表：
一、短缺资源的分配问题供区水库 甲 乙 丙 丁 供水量 kt/d
A 16 13 22 17 50
B 14 13 19 15 60
C 19 20 23 -- 50
最低需求 kt/d 30 70 0 10
最高需求 kt/d 50 70 30 不限如何分配供水量，保障各区最低需求，获利最大？
上海财经大学 国际工商管理学院
SHUFE
31
第四节 运输模型的应用利润 =收入 -成本，收入最大，成本最小，则利润最大。
收入：
每天供水总量是一常数，水价也是常数，则每天总收入也是常数。
每天供水总量若能全部售出，每天总收入则能达到最大。
丁区最高需求不限，每天总供水量能全售出。
每天总收入是常数，与水量分配无关，可以不与考虑。
成本：
各区管理费相同 45元 /kt，每天售水总量是一常数，则管理费也是常数。
各区引水费不同，如果总的引水费达到最小，总成本则最低。
如何分配水量，既满足最低需求，又使总的引水费最低？
最大需求量：
供水总量 =50+60+50=160，四区最低需求量 =30+70+10=110，故丁区最大需求量 160-110+10=60。
四区最大需求 =50+70+30+60=210，比供水总量 160多 50，则是一个产小于销的不平衡问题。
分析上海财经大学 国际工商管理学院
SHUFE
32
第四节 运输模型的应用
产小于销的运输问题化为平衡问题，虚设水库 D，供水量 50。
各区的最低需求为基本需求，不允许脱销，不能由虚设水库 D供水，故单位引水费（运费）为 M。
各区的最大需求与最低需求的差为额外需求，可以由虚设水库 D供水，故单位引水费（运费）为 0 。
供区水库 供水量
A 50
B 60
C 50
甲 1 甲 2 乙 丙 丁 1 丁 2
16 16 13 22 17 17
14 14 13 19 15 15
19 19 20 23 M M
销量 30 20 70 30 10 50
D M 0 M 0 M 0 50
上海财经大学 国际工商管理学院
SHUFE
33
第四节 运输模型的应用
用表上作业法求得最优方案供区水库 甲 1 甲 2 乙 丙 丁 1 丁 2 供水量
A 50 50
B 20 10 30 60
C 30 20 0 50
D 30 20 50
销量 30 20 70 30 10 50
– 最优分配方案：水库 A向乙区供水 50，水库 B分别向乙区、丁区供水 20和
40，水库 C向甲区供水 50，不给丙区供水。
– 最小引水费,13?50+13?20+ 15?(10+30)+19?(30+20) =2460
引水 管理费,45?(50+60+50)=7200
总成本,2460+7200=9600 总收入,90?(50+60+50)=14400
最大获利,14400-9600=4740
上海财经大学 国际工商管理学院
SHUFE
34
第四节 运输模型的应用
产地与销地之间存在转运站。
面粉转运问题,三个面粉加工厂，两个糕点生产厂，两个中转站。
二、资源转运问题终点始点面粉厂 中转站 糕点厂 生产能力A1 A2 A3 T1 T2 B1 B2
面粉厂
A1 3 2 3 - 6 8 3
A2 4 2 5 2 13 7 4
A3 - 2 3 2 11 4 3
中转站
T1 3 5 2 6 2 5
T2 - 3 2 7 - 2
糕点厂
B1 6 - - 2 - 9 4
B2 - - 4 - 3 9 6
如何调运，总运费最低？
上海财经大学 国际工商管理学院
SHUFE
35
第四节 运输模型的应用
最小转运能力 t=max{?ai,?bj}=10
销地产地面粉厂 中转站 糕点厂 产量A
1 A2 A3 T1 T2 B1 B2
面粉厂
A1
A2
A3
中转站
T1
T2
糕点厂
B1
B2
销量
0 3 2 3 M 6 8
4 0 2 5 2 13 7
M 2 0 3 2 11 4
3 5 2 0 6 2 5
M 3 2 7 0 M 2
6 M M 2 M 0 9
M M 4 M 3 9 0
13
14
13
10
10
10
10
面粉厂产量,ai+t
糕点厂产量,t
转运站产量,t
面粉厂销量,t
糕点厂销量,bj+t
转运站销量,t
10 10 10 10 10 14 16
- 3
4
- 3
- -
- - - 4
- - - 6
上海财经大学 国际工商管理学院
SHUFE
36
第四节 运输模型的应用
用表上作业法求得最优方案
– 最优分配方案,面粉厂 A3向糕点厂 B2直接运输 2吨,A1,A2,A3向中转站 T1和 T2运输 3,4,1吨，中转站 T1和 T2分别向糕点厂 B1,B2运输 4,4吨。
– 最小运费,3?3+2?4+ 3?1+4?2 +2?4 +2?4 =44
销地产地面粉厂 中转站 糕点厂 产量A
1 A2 A3 T1 T2 B1 B2
面粉厂
A1
A2
A3
中转站
T1
T2
糕点厂
B1
B2
销量
10 3 13
10 4 14
10 1 2 13
6 4 10
6 4 10
10 10
10 10
10 10 10 10 10 14 16
3
4
3
4 6
供应链管理、国际物流管理、企业资源计划单 位,上海财经大学 国际工商管理学院 供应链管理研究中心
E-mail,jiaping_xie@sina.com.cn
电 话,55036936(H) 65903541(O)
上海财经大学 国际工商管理学院
SHUFE
2
第五章 运输问题
运输问题是线性规划问题的特例。
产地,货物发出的地点。
销地,货物接收的地点。
产量,各产地的可供货量。
销量,各销地的需求数量。
运输问题就是研究如何组织调运，既满足各销地的需求，
又使总运费最小。
上海财经大学 国际工商管理学院
SHUFE
3
第一节 运输模型某饮料在国内有三个生产厂,分布在城市 A1,A2,A3,其一级承销商有 4个,分布在城市 B1,B2,B3,B4,已知各厂的产量,各承销商的销售量及从 Ai到 Bj的每吨饮料运费为 Cij,为发挥集团优势,公司要统一筹划运销问题,求运费最小的调运方案 。
一,运输问题举例销地产地 B1 B2 B3 B4 产量
A1 6 3 2 5 5
A2 7 5 8 4 2
A3 3 2 9 7 3
销量 2 3 1 4
上海财经大学 国际工商管理学院
SHUFE
4
第一节 运输模型
(1)决策变量 。 设从 Ai到 Bj的运输量为 xij，
(2)目标函数
minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34
(3)约束条件 。产量之和等于销量之和,故要满足：
供应平衡条件 x11+x12+x13+x14=5
x21+x22+x23+x24=2
x31+x32+x33+x34 =3
销售平衡条件 x11+x21+x31=2
x12+x22+x32=3
x13+x23+x33=1
x14+x24+x34=1
非负性约束 xij≥0 (i=1,2,3； j=1,2,3,4)
运输问题的 LP模型上海财经大学 国际工商管理学院
SHUFE
5
第一节 运输模型销地产地二、表式运输模型
A1
A2
…
Am
产量
a1
a2
…
am
B1 B2 … Bn
销地 b1 b2 … bn
c11 c12 … c1n
c21 c22 … c2n
… … … …
cm1 cm2 … cmn
x11 x12 x1n
x21 x22 x2n
xm1 xm2 xmn
上海财经大学 国际工商管理学院
SHUFE
6
第一节 运输模型
产销平衡三、运输问题的三种类型
m
i
n
j
ji ba
1 1
0
,.,,,2,1,
,.,,,2,1,
m i n
1
1
1 1
ij
m
i
jij
n
j
iij
m
i
n
j
ijij
x
njbx
miax
xcZ
上海财经大学 国际工商管理学院
SHUFE
7
第一节 运输模型
产大于销
m
i
n
j
ji ba
1 1
0
,.,,,2,1,
,.,,,2,1,
m i n
1
1
1 1
ij
m
i
jij
n
j
iij
m
i
n
j
ijij
x
njbx
miax
xcZ
上海财经大学 国际工商管理学院
SHUFE
8
第一节 运输模型
产小于销
m
i
n
j
ji ba
1 1
0
,.,,,2,1,
,.,,,2,1,
m i n
1
1
1 1
ij
m
i
jij
n
j
iij
m
i
n
j
ijij
x
njbx
miax
xcZ
上海财经大学 国际工商管理学院
SHUFE
9
第一节 运输模型决策变量 m?n 约束方程 m+n 系数矩阵的结构如下：
四、运输模型的特点
1
1
1
1
1
1
1
1
1
111
111
111
A
x11 x12 … x1n x21 x22 … x2n … … … … xm1 xm2 … xmn
m
行
n
列上海财经大学 国际工商管理学院
SHUFE
10
第二节 表上作业法
表上作业法适合于产销平衡的运输问题
求解步骤：
找出初始方案（初始基可行解）：在 m?n维产销平衡表上给出 m+n-1个数字。
最优性检验：计算各非基变量的检验数，当?ij?0最优。
方案调整与改进：确定进基变量和离基变量，找出新的基可行解。
上海财经大学 国际工商管理学院
SHUFE
11
第二节 表上作业法
最小元素法
,就近运给”，
从单位运价表中最小运价开始确定供销关系，
逐次挑选最小元素，安排运量 min{ai,bj}。
最大差额法
不能按最小运费就近供应，就考虑次小运费。
各行 (各列 )的最小运费与次小运费之差称为行差 (列查 )。 差额越大，说明不能按最小运费调运时，运费增加最多。
对最大差额处就采用最小运费调运。
一、确定初始方案上海财经大学 国际工商管理学院
SHUFE
12
第二节 表上作业法
从单位运价表中逐次挑选最小元素，安排运量 min{ai,bj}。
然后，划去该元素所在行或列：
当产大于销，划去该元素所在列；
当产小于销，划去该元素所在行。
最小元素法销地产地 B
1 B2 B3 B4 产量
A1 6 3 2 5 5
A2 7 5 8 4 2
A3 3 2 9 7 3
销量 2 3 1 4
1
30
2
22
初始基可行解,x11=2,x13=1,x14=2,x24=2,x31=0,x32=3,Z=38
上海财经大学 国际工商管理学院
SHUFE
13
第二节 表上作业法
判别方法是计算非基变量的检验数,
ij= cij – CBPij’= cij – CBB-1Pij
运输问题的目标函数要求为最小，即当?ij?0视为最优。
位势法 计算检验数
ij= cij – CBPij’= cij – CBB-1Pij
ij = cij –(ui+vj )
ui代表产地 Ai的位势量,vj代表销地 Bj的位势量。
基变量的检验数为 0，即?ij= cij –ui – vj =0，
并令 u1 =0，计算各行各列的 位势量。
二、最优性检验上海财经大学 国际工商管理学院
SHUFE
14
第二节 表上作业法
基变量的检验数?ij= cij –ui – vj =0,即 cij =ui +vj,
且令 u1 =0，计算位势量 ui和 vj
位势法销地产地 B1 B2 B3 B4 产量
A1 6 2 3 2 1 5 2 5
A2 7 5 8 4 2 2
A3 3 0 2 3 9 7 3
销量 2 3 1 4
ui
vj
0
6 2 5
-1
-3
5
上海财经大学 国际工商管理学院
SHUFE
15
第二节 表上作业法
计算非基变量的检验数?ij= cij –ui – vj
位势法（续 ）
销地产地 B1 B2 B3 B4 产量 ui
A1 6 2 3 2 1 5 2 5 0
A2 7 5 8 4 2 2 -1
A3 3 0 2 3 9 7 3 -3
销量 2 3 1 4
vj 6 5 2 5
-2
2 1 7
10 5
非基变量 x12的检验数?12= c12 –u1– v2 =-2,即让非基变量 x12从 0增到
1，可使总运费减少 2个单位。
上海财经大学 国际工商管理学院
SHUFE
16
第二节 表上作业法
确定进基变量
检查非基变量 xij的检验数?ij,按 min{?ij|?ij <0}=?lk 确定 xlk进基。
确定离基变量
非基变量 xlk进基之后，能让它的运量增加多少呢？
就要求它所在行和列的运量保持 产销平衡 。
保持产销平衡的方法是 闭回路法 。
闭回路法,以进基变量 xlk所在格为始点和终点，其余顶点均为基变量的封闭回路。
闭回路的画法,从进基变量 xlk所在格开始，用水平或垂直线向前划，
每碰到一个基变量格转 90o，继续前进，直到返回始点。
奇偶点,始点是偶点，依次奇偶相间标注；偶点标,+”,表示运量增加量；奇点标,-”,表示运量减少量。
调整量,最小可减少的运量，即奇点运量的最小值。
奇点运量的最小值所在格的基变量离基。
三、改进的方法（闭回路调整法）
上海财经大学 国际工商管理学院
SHUFE
17
第二节 表上作业法
x12 进基
最小调整量为 2,x11 离基销地产地 B1 B2 B3 B4 产量
A1 6 2 3 x
12
2
1
5
2 5
A2 7 5 8 4 2 2
A3 3 0 2 3 9 7 3
销量 2 3 1 4
+-
+ -
上海财经大学 国际工商管理学院
SHUFE
18
第二节 表上作业法
非最优方案的调整
所有偶点的值都加上调整量；
所有奇点的值都减去调整量；
获得一个新的运输方案。
销地产地 B1 B2 B3 B4 产量
A1 6 3 2 1 5 2 5
A2 7 5 8 4 2 2
A3 3 2 9 7 3
销量 2 3 1 4
基可行解,x12=2,x13=1,x14=2,x24=2,x31=2,x32=1,Z=34
2
0 3
2
2 1
上海财经大学 国际工商管理学院
SHUFE
19
第二节 表上作业法
基变量的检验数?ij= cij –ui – vj =0，且令 u1 =0，计算位势量 ui
和 vj
四、最优性检验销地产地 B1 B2 B3 B4 产量
A1 6 3 2 2 1 5 2 5
A2 7 5 8 4 2 2
A3 3 2 2 1 9 7 3
销量 2 3 1 4
ui
vj
0
4
-1
-1
3 2 5
所有非基变量 xij的检验数?ij= cij –ui– vj≥0,即得最优解。
上海财经大学 国际工商管理学院
SHUFE
20
第三节 产销不平衡问题
产销平衡的运输问题采取表上作业法求解。
产销不平衡的运输问题需划成产销平衡问题再求解。
产大于销：
虚设一个销地 Bk (多于物资在产地存储 )，其运价为 0，
销量 (存储量 )为产销量之差 bk =?ai-? bj。
产小于销：
虚设一个产地 Al (不足物资的脱销量 )，其运价为 0，产量
(脱销量 )为销产量之差 ak =? bj -?ai 。
上海财经大学 国际工商管理学院
SHUFE
21
第三节 产销不平衡问题
增加一个销地一、产大于销 销地产地 B
1 B2 B3 产量
A1 5 9 2 15
A2 3 1 7 18
A3 6 2 8 17
销量 18 12 16
销地产地 B1 B2 B3 产量
A1 5 9 2 15
A2 3 1 7 18
A3 6 2 8 17
销量 18 12 16
50-46
B4
0
0
0
4
5046
5050
上海财经大学 国际工商管理学院
SHUFE
22
第三节 产销不平衡问题
初始基可行解销地产地 B1 B2 B3 B4 产量
A1 5 9 2 0 15
A2 3 1 7 0 18
A3 6 2 8 0 17
销量 18 12 16 4
12
15
6
12 1 4
初始基可行解,x13=15,x21=6,x22=12,x31=12,x33=1,x34=4,Z=140
上海财经大学 国际工商管理学院
SHUFE
23
第三节 产销不平衡问题
最优性检验销地产地 B1 B2 B3 B4 产量 ui
A1 5 9 2
15
0 15
A2 3
6
1
12
7 0 18
A3 6
12
2 8
1
0
4
17
销量 18 12 16 4
vj
0
2
6
0 -6
3
-2
5 11 6
2 3
-2
非基变量 x32的检验数?32= -2，即让非基变量 x32进基。
上海财经大学 国际工商管理学院
SHUFE
24
第三节 产销不平衡问题
闭回路调整
– x32 进基
– 最小调整量为 12,x31 离基销地产地 B
1 B2 B3 B4 产量
A1 5 9 2 15 0 15
A2 3 6 1 12 7 0 18
A3 6 12 2
x32
8
1
0
4
17
销量 18 12 16 4
-+
- +
上海财经大学 国际工商管理学院
SHUFE
25
第三节 产销不平衡问题
非最优方案的调整
所有偶点的值都加上调整量；所有奇点的值都减去调整量。
基可行解,x13=15,x21=18,x31=0,x32=12,x31=1,x34=4,Z=34
销地产地 B
1 B2 B3 B4 产量
A1 5 9 2 15 0 15
A2 3 1 7 0 18
A3 6 2 8 1 0 4 17
销量 18 12 16 4
6 12
12
18
0 12
上海财经大学 国际工商管理学院
SHUFE
26
第三节 产销不平衡问题
基变量的检验数?ij= cij –ui – vj =0，且令 u1 =0，计算位势量 ui和 vj
最优性检验所有非基变量 xij的检验数?ij= cij –ui– vj≥0，即得最优解。
销地产地 B1 B2 B3 B4 产量 ui
A1 5 9 2
15
0 15
A2 3
18
1 7 0 18
A3 6
0
2
12
8
1
0
4
17
销量 18 12 16 4
vj
0
2
6
0 -4 -6
3
5 13 6
2 32
上海财经大学 国际工商管理学院
SHUFE
27
第三节 产销不平衡问题
增加一个产地二、产小于销 销地产地 B
1 B2 B3 产量
A1 4 1 2 10
A2 3 4 3 12
销量 8 10 5
销地产地 B1 B2 B3 产量
A1 4 1 2 10
A2 3 4 3 12
A3
销量 8 10 5
23-22
0 0 0 1
2223
2323
上海财经大学 国际工商管理学院
SHUFE
28
第三节 产销不平衡问题
初始基可行解销地产地 B1 B2 B3 产量
A1 4 1 2 10
A2 3 4 3 12
A3 0 0 0 1
销量 8 10 5
10 0
57
1
初始基可行解,x12=10,x13=0,x21=7,x23=5,x31=1,Z=46
上海财经大学 国际工商管理学院
SHUFE
29
第三节 产销不平衡问题
最优性检验销地产地 B1 B2 B3 产量 ui
A1 4 1 10 2 0 10
A2 3 7 4 3 5 12
A3 0 1 0 0 1
销量 8 10 5
vj
0
1 2
1
2
-2
2
2
1 0
– 检验数?ij≥0，得最优解,x12=10,x13=0,x21=7,x23=5,x31=1,Z=46
– 由于非基变量 x33 的检验数?33=0，为多最优解。
让 x33进基,x31离基,得另一最优解,x12=10,x13=0,x21=8,x23=4,x33=1
上海财经大学 国际工商管理学院
SHUFE
30
第四节 运输模型的应用
短缺资源分配，“产小于销”，需注意产销配比问题。
上例 x12=10,x13=0,x21=7,x23=5,x31=1,表示销地 B1脱销 1个单位；
然而 x12=10,x13=0,x21=8,x23=4,x33=1,则表示销地 B3 脱销 1个单位；
但销地 B3 的销量为 5，本身就很少，不允许脱销，如何处理呢？
自来水分配问题,水价 90元 /kt，管理费 45元 /kt，引水费如下表：
一、短缺资源的分配问题供区水库 甲 乙 丙 丁 供水量 kt/d
A 16 13 22 17 50
B 14 13 19 15 60
C 19 20 23 -- 50
最低需求 kt/d 30 70 0 10
最高需求 kt/d 50 70 30 不限如何分配供水量，保障各区最低需求，获利最大？
上海财经大学 国际工商管理学院
SHUFE
31
第四节 运输模型的应用利润 =收入 -成本，收入最大，成本最小，则利润最大。
收入：
每天供水总量是一常数，水价也是常数，则每天总收入也是常数。
每天供水总量若能全部售出，每天总收入则能达到最大。
丁区最高需求不限，每天总供水量能全售出。
每天总收入是常数，与水量分配无关，可以不与考虑。
成本：
各区管理费相同 45元 /kt，每天售水总量是一常数，则管理费也是常数。
各区引水费不同，如果总的引水费达到最小，总成本则最低。
如何分配水量，既满足最低需求，又使总的引水费最低？
最大需求量：
供水总量 =50+60+50=160，四区最低需求量 =30+70+10=110，故丁区最大需求量 160-110+10=60。
四区最大需求 =50+70+30+60=210，比供水总量 160多 50，则是一个产小于销的不平衡问题。
分析上海财经大学 国际工商管理学院
SHUFE
32
第四节 运输模型的应用
产小于销的运输问题化为平衡问题，虚设水库 D，供水量 50。
各区的最低需求为基本需求，不允许脱销，不能由虚设水库 D供水，故单位引水费（运费）为 M。
各区的最大需求与最低需求的差为额外需求，可以由虚设水库 D供水，故单位引水费（运费）为 0 。
供区水库 供水量
A 50
B 60
C 50
甲 1 甲 2 乙 丙 丁 1 丁 2
16 16 13 22 17 17
14 14 13 19 15 15
19 19 20 23 M M
销量 30 20 70 30 10 50
D M 0 M 0 M 0 50
上海财经大学 国际工商管理学院
SHUFE
33
第四节 运输模型的应用
用表上作业法求得最优方案供区水库 甲 1 甲 2 乙 丙 丁 1 丁 2 供水量
A 50 50
B 20 10 30 60
C 30 20 0 50
D 30 20 50
销量 30 20 70 30 10 50
– 最优分配方案：水库 A向乙区供水 50，水库 B分别向乙区、丁区供水 20和
40，水库 C向甲区供水 50，不给丙区供水。
– 最小引水费,13?50+13?20+ 15?(10+30)+19?(30+20) =2460
引水 管理费,45?(50+60+50)=7200
总成本,2460+7200=9600 总收入,90?(50+60+50)=14400
最大获利,14400-9600=4740
上海财经大学 国际工商管理学院
SHUFE
34
第四节 运输模型的应用
产地与销地之间存在转运站。
面粉转运问题,三个面粉加工厂，两个糕点生产厂，两个中转站。
二、资源转运问题终点始点面粉厂 中转站 糕点厂 生产能力A1 A2 A3 T1 T2 B1 B2
面粉厂
A1 3 2 3 - 6 8 3
A2 4 2 5 2 13 7 4
A3 - 2 3 2 11 4 3
中转站
T1 3 5 2 6 2 5
T2 - 3 2 7 - 2
糕点厂
B1 6 - - 2 - 9 4
B2 - - 4 - 3 9 6
如何调运，总运费最低？
上海财经大学 国际工商管理学院
SHUFE
35
第四节 运输模型的应用
最小转运能力 t=max{?ai,?bj}=10
销地产地面粉厂 中转站 糕点厂 产量A
1 A2 A3 T1 T2 B1 B2
面粉厂
A1
A2
A3
中转站
T1
T2
糕点厂
B1
B2
销量
0 3 2 3 M 6 8
4 0 2 5 2 13 7
M 2 0 3 2 11 4
3 5 2 0 6 2 5
M 3 2 7 0 M 2
6 M M 2 M 0 9
M M 4 M 3 9 0
13
14
13
10
10
10
10
面粉厂产量,ai+t
糕点厂产量,t
转运站产量,t
面粉厂销量,t
糕点厂销量,bj+t
转运站销量,t
10 10 10 10 10 14 16
- 3
4
- 3
- -
- - - 4
- - - 6
上海财经大学 国际工商管理学院
SHUFE
36
第四节 运输模型的应用
用表上作业法求得最优方案
– 最优分配方案,面粉厂 A3向糕点厂 B2直接运输 2吨,A1,A2,A3向中转站 T1和 T2运输 3,4,1吨，中转站 T1和 T2分别向糕点厂 B1,B2运输 4,4吨。
– 最小运费,3?3+2?4+ 3?1+4?2 +2?4 +2?4 =44
销地产地面粉厂 中转站 糕点厂 产量A
1 A2 A3 T1 T2 B1 B2
面粉厂
A1
A2
A3
中转站
T1
T2
糕点厂
B1
B2
销量
10 3 13
10 4 14
10 1 2 13
6 4 10
6 4 10
10 10
10 10
10 10 10 10 10 14 16
3
4
3
4 6
