5
3 3 6 6 5
2 1 3 6
7 4 9
• 由上述检验数可知，所有检验数都大于或等于“0”，
因此，表5所示的解是最优运输方案。 最优解
B1 A1 A2 A3 B2 B3 B4 产量
5
3 6 6
销 量
3
5
2 1 3 6
7 4 9
总运费=85
产地 销地 B 1
B2
4 5
B3
6 5
产量
200 300
A1 A2
6 6
销 量
150
150
200
单位运价
问应如何安排运输才能使总运费为最小？
分析：这是一个产销平衡的运输问题。
设Xij表示从产地Ai调运到Bj的运输量（i=1,2 j=1,2,3)
一个运输方案可列表如下：
销地 产地
A1 A2
B1
B2
B3
( ) -1 3
+1
4 1 6 6
-1 +1
3 3 6
7 4 9
A1 A2 A3
B1 3 1 7
B2 11 9 4 6
B3 3 2 10 5
B4 10 8 5 6
产量 7 4 9销 量35销量 3
λ11=(+1)×3+(-1) ×3+(+1) ×2+(-1) ×1=1 λ11=1， λ12=2， λ22=1， λ24=-1， λ31=10， λ33=12
a = b
i =1 i j =1
m
n
j
，问应如何安排运输可使总运费最小？
假定 x ij 表示由 Ai 到 B j 的运输量，则平衡条件下的运输问题可写出
如下的线性规划模型：
min z = cij xij
i =1 j =1
m
n
. s.t
x
j =1
n
ij
= ai
= bj
(i = 1,2,..., m) ( j = 1,2,..., n)
最优方案的判别标准是：如果所有空格的检验数 均已非负，则相应的调运方案已是最优方案；否 则若某空格中仍有负数，则需要对方案进行调整。
本例中，初始运输方案的检验数中， λ24=-1 因此，该运输方案不是最优方案。
方法2：位势法
步1：将运输方案中的调运量换成其单位运价； 表1
B1 A1 A2 A3
调运方案
闭回路是运输问题求解过程中非常重要的一个基本概念。 定义 如表所示，变量组 x11x13x23x21 即称作为一个闭回路， 其中每一个变量称作该闭回路的一个顶点。同样，变量组 x11x12x22x21和x13x14x34x32x22x23也都是闭回路。
表 闭回路在表中的表示法 B1 X11 X21 X31 B2 B3 X13 X23 X33 B4 X14 X24 X34
管理优化之—
运输问题
1
运输问题的数学模型
运输问题在工商管理上有着广泛的应用，其主要目的是物资调 运、车辆调度选择最经济的运输路线。 有些问题，比如有m台机床加工n种零件的问题，工厂的合理 布局问题等,虽要求与提法不同,但经过适当变化也可以使用本模 型求得最优解。
例.1 某公司从两个产地A1、A2将物品运往三个销售地 B1、B2、B3，由于供需双方两两间的相对位置不同因而运 价不同，有关数据如下表：
某种物资有 m 个产地 Ai ，产量分别为 a i (i = 1,2,..., m ) ，有 n 个销 地 B j ，销量（需求量）分别为 b j ( j = 1,2,..., n) , 已知 Ai 到 B j 的单位运 价为 c ij (i = 1,2,..., m; n = 1,2,..., n) ，又假设产销是平衡的，即：
Ui 0
-1 -5
A1
A2 A3 销 量
3
1 4 3 2 6 9 5 3 2
10
5 6 10
7
4 9
λ12=C12－U1 －V2=2 λ22=C22－U2 －V2=1 λ24=C24－U2 －V4=-1 λ31=C31－U3 －V1=10 λ33=C33－U3 －V3=12
Vj
第三步，调整运输方案
7
3
4
6
10
5
5
6
9
问应如何安排运输才能使总运费为最小？
第一步，确定初始基本可行解
方法1：西北角法 对西北角的变量分配运输量
B1 A1 A2 A3 B2 B3 B4 产量
3
4 2
7
2
3 6
4 9
销 量
3
6
5
6
总运输费用=135
方法2：最小元素法
• 基本思路是“就近供应”，即对单位运价 最小的变量分配运输量。 上例中以此方法确定的初始基可行解为：
销 量
3
6
5
6
6 6
5
2 7 1 4 3 9 6
调整量：是闭回路中标负号拐角点上的最小调运量。
• 对表5给出的运输方案，再用位势法进行检验： 表5 λ11=C11－U1 －V1=0
B1 A1
A2 A3 销 量
B2
B3
B4
产量
λ12=C12－U1 －V2=2
λ22=C22－U2 －V2=2 λ23=C23－U2 －V3=1 λ31=C31－U3 －V1=9 λ33=C33－U3 －V3=12
A1 A2 A3
X12 X22 X32
上例中，我们把连接平衡表中 x11 ， x13 ， x23 ， x21 所在格形成的图 形称为闭回路。一般地，在调运方案表中，从一个空格出发 , 沿水平或垂 直方向前进，遇到一个适当的有数字的格子时 , 就按与前进方向垂直的方 向转向前进，这样经过若干 次拐弯后，必然回到原来出发的那个空格 , 于 是就形成了一条由水平线段和垂直线段组成的封闭折线即闭回路。 在理论上可以证明：过每一个空格一定可以做唯一的一条闭回路。
B1
A1 A2 A3 销 量
B2
B3
B4
产量
4 3 6 3 6 5 1
3
7 4
3 6
9
一般地，就把过空格 x ij 的闭回路中第奇数次拐角点上的运费总和减 第偶数次拐角点上的运费总和之差称作空格 x ij 的检验数，记为 l ij 。 如上表中各空格的检验数是：
B1 A1 A2 A3 B2 B3 B4 产量
x
i =1
m
ij
xij 0
2
运输问题的表上作业法
2.1表上作业法的解题步骤
表上作业法的基本思想是:先设法给出一个初始方案,然后根据确定 的判别准则对初始方案进行检查、调整、改进，直至求出最优方案，如 图3-1所示。这和单纯形法的求解思想完全一致，但是具体的作法则更 加简捷。
确定初始方 案（初始基 本可行解）
产量
x11 x21 150
x12 x22 150
x13 x23 200
200 300
销 量
•满足产地产量的约束条件为： x11+x12+x13=200 x21+x22+x23=300 满足销地销量的约束条件为： x11+x21=150
x12+x22=150 x13+x23=200 使运输费用最小的目标函数为： Min f=6x11+4x12+6x13+6x21+5x22+5x23
Ui
3 1 4 3 6 5 2
10 5 6
7 4 9
3 1 4 3 6 5 2
10 5 6
7 4 9
0 -1 -5
Vj
2
9
3
10
• 步3 依据求出的Vj和Ui值，计算所有空格位置的检验 数。 λ ij= Cij －（Ui+ Vj） • 表4 λ11=C11－U1 －V1=1
B1 B2 B3 B4 产 量
B2 B3 B4 产 量
表2 单位运价
B1 A1 A2 A3 B2 B3 B4 产 量
3
4 1
6 6
3
3 6
7 4 9
1
3 2
4 6
销 量
3
5
销 量
3
5
10 7 4 5 9 6
• 步2 在表2中增加一行Vj ，增加一列Ui,使Vj和Ui满足： Ui+ Vj=Cij
表3 位势表
B1 A1 A2 A3 销 量 B2 B3 B4 产 量 B1 A1 A2 A3 销 量 B2 B3 B4 产 量
产销平衡表 单位运价表 B1 3 1 7 B2 11 9 4 6 B3 3 2 10 5 B4 10 8 5 6 产量 7 4 9 B1 B2 B3 B4 产量
A1 A2 A3
A1
A2 A3 销 量
4 3 6 3 6 5 6 1
3
7
4
销量 3
3 9
总运输费用=86
第二步，求检验数，判别最优方案
方法1：闭回路法
判定是否最优？
是
结束
否
改进调整 （换基迭代）
运输问题求解思路图
例2 某食品公司有三个生产面包的分厂A1、A2、A3 ，有四个销 售公司B1、B2、B3，B4，由于供需双方两两间的相对位置不同 因而单位运价不同，有关数据如下表：
B1
A1 A2 3 1
B2
11 9
B3
3 2
B4
10 8
产量
7 4
A3
销 量
• 该运输问题的线性规划模型为： Min f=6x11+4x12+6x13+6x21+5x22+5x23 x11+x12+x13=200 x21+x22+x23=300 x11+x21=150 x12+x22=150 x13+x23=200 Xij i=1,2;j=1,2,3)