物流系统工程 ——
西南交通大学电子讲义
1
5.3 物流分配规划
?任务分配问题的数学模型
?用匈牙利法求解分配问题
物流系统工程 ——
第 5章 物流系统规划
2
一, 任务分配问题的数学模型
? 在物流系统中或其它的管理工作中，管理人员经常面临的
一个问题是：如何根据有限的资源 (人力、物力、财力等 )，
进行工作任务分配，以达到降低成本或提高经济效益的目
的。如：
?有 A,B,C,D四门课程，上课的老师可以从甲、乙、丙、丁四名老
师中选择，不同的老师上不同的课程，其费用是不同的，并且规定，
每人只讲一门课程，每门课程只需要一人讲授。问：如何安排，才
能使总的上课费用最低？
?又如：运输任务的分配问题。有 n条航线的运输任务指派给 n艘船去
完成，不同的船完成不同的航线其运输成本不同。要求每条船完成
一条航线，并且一条航线只能由一条船去完成。如何分配任务，才
能使总的费用最小？
? 这类问题是常见的任务分配问题，也叫指派问题，它的任
务是如何进行合理的任务分配，使总的费用最小。
物流系统工程 ——
第 5章 物流系统规划
3
一, 任务分配问题的数学模型
? 以运输问题的 n项任务由 n个司机去完成的情况为例，有 n个
司机被分配完成 n项运输任务，不同的司机完成任务某一项
任务的费用都不一样。要求每个司机完成其中一项任务，
每个任务只能由一名司机完成，如何分配任务，才能使总
的费用最小？
10
1
1..
1
1
1 1
或?
?
?
?
?
?
? ?
?
?
? ?
ij
n
i
ij
n
j
ij
n
i
n
i
ijij
x
x
xts
xcM inZ
令：
cij表示第 i个司机完成第 j项任务的运输成
本（工作成本或工作时间等价值系
数）；
xij表示第 i个司机去完成第 j项任务，其值
为 1或 0。
?当其值为 1时表示第 i个司机被分配去完
成第 j项任务；
?其值为 0时，表示第 i个司机不被分配去
完成第 j项任务。
物流系统工程 ——
第 5章 物流系统规划
4
一, 任务分配问题的数学模型
?任务分配问题属于整数规划问题，其变量 xij的取值
为整数，（本例为 0或 1）。
?任务分配问题可以用一般的整数规划求解方法进
行求解。但是，整数规划问题的求解也是非常困
难的，到目前为止，还缺乏统一的求解方法。
?本书采用匈牙利法求解任务分配问题。
物流系统工程 ——
第 5章 物流系统规划
5
二, 匈牙利法求解分配问题
? 可以证明，对于分配问题，在其费用矩阵 Cij中，各行、各
列均减去一个常数,Cij改变以后的最优解，仍为原问题的
最优解。
? 利用这个性质，通过对 Cij的行、列进行加减常数的计算，
把一些矩阵元素变为 0，在 Cij为 0的元素上进行分解，就可
得到原问题的最优解。
? 该方法应用了匈牙利数学家 Konig矩阵性质定理，因此这种
方法被称为匈牙利法。
物流系统工程 ——
西南交通大学电子讲义
6
5.4 其他规划问题
?选址问题
?货物装配问题
?物流服务系统中的配置问题
物流系统工程 ——
第 5章 物流系统规划
7
一, 选址问题
?物流调运规划问题, 是一种有固定发点, 固定收
点和固定道路的运输规划问题 。
?还有一类运输问题, 他的收货点和发货点是待定
的, 这就是选址问题 。 这类问题在物流系统规划
中经常遇到 。
?选址问题要考虑多种因素, 本节只讨论选址问题
中的物流问题 。 分为两个问题：
?单一地址选址方法；
?图上作业法 。
物流系统工程 ——
第 5章 物流系统规划
8
1,单一地址选址方法
建立一个新工厂（或仓库），应合理选择厂址（或库址）。
所谓选址问题，就是从多个候选厂址中选取一个最优地址
建厂，使物流费用达到最低。
问题描述,假设厂址候选地点有 s个，分别用 D1,D2,…,Ds
表示；原材料、燃料、零配件的供应地有 m个，分别用
A1,A2,…,Am表示，其供应量分别用 P1,P2,…,Pm表示；产品
销售地有 n个，分别用 B1,B2,…,Bn表示，其销售量分别为
Q1,Q2,…,Qn表示。
设 cij为供应地 Ai到候选厂址 Dj的单位运输成本；
djk为候选厂址 Dj到销售地 Bk的单位运输成本；
设选址变量为 xj(j=1,2,…,s),其中,xj=0或 1,1表示在 Dj点建
厂,0表示不在 Dj点建厂。
01
1
mi n
D
BD
D
c运输DA
1
1 11
1 11
1
j
kj
1
j
ji
或
以表示为：选址问题的数学模型可
为：所有候选地的运输成本
费用为：到所有的销售地的运输候选地
的运输费用为：到销售地从候选地
的运输费用为：所有的供应点到候选地
费用为：点的到候选地从供应点
?
?
?????
?
?????
??
??
??
??
?
? ??
? ??
?
?
?
? ??
? ??
?
?
j
s
j
j
j
s
j
n
k
kjk
m
i
iij
s
j
n
k
jkjk
m
i
jiij
n
k
jkjk
jkjk
m
i
jiij
jiij
x
xs, t,
x)QdPc(Z
)xQdxPc(
xQd
xQd
xPc
xP
?单一选址问题是一种线性规划问题,并且变量的取
值为 0或 1,属于整数规划问题 。
?单一地址的选址模型的求解方法比较简单, 从目
标函数表达式的右边可以看出,通过计算模型中
括号内的算式值, 就能够确定运输成本最小的方
案 。
?当要选定的地址不是单一的, 而是多个时, 问题
不再属于线性规划问题 。
物流系统工程 ——
第 5章 物流系统规划
12
2,图上作业法
对于运输路线不含回路的选址问题，可用图上作业法求解。
下面以一个实际例子来说明图上作业法的选址问题：
例题 8 假定有六个矿井．产量分别为 5000吨,6000吨,7000吨、
2000吨,4000吨和 3000吨，运输路线如图所示，这些矿石要经过加工
后才能转运到其他地方。这些矿井之间道路不含回路，欲选择一个矿
井，在此矿井上建立一个加工厂，使各矿井到工厂的运输总费用最低。
为了便于分析, 用一个新的图来代替原图, 新图圈内数字表示矿井编
号, 产量记在圈的旁边, 道路交叉点看作产量为零的矿井, 把那些只
有一条道路连接的矿井称为端点 。
? 首先计算这些矿井的总产量, 本例为 27000吨 。
? 然后分析各端点, 都没有超过总产量的一半, 因此把各端点的数量合并
到前一站, 即 ① 和 ② 的数量合并到 ③ ；把 ④ 的数量合并到 ⑤ ； 把 ⑦
的 数量合并到 ⑥, 如下图所示 。
3 5 6
11000 9000 7000
? 各端点都合并到前一站后, ③ 和 ⑥ 变成了图中的端点 。 对它们进行分
析, 其数量都不超过总产量的一半, 所以他们不是最佳点 。
? 再把它们合并到前一站, 即把 ② 和 ⑥ 的数量合并到 ⑤ 。 则 ⑤ 的数量为
27000,超过总量的一半, 所以 ⑤ 是最佳点 。
? 结论：加工厂应建在第 5号矿井 。
物流系统工程 ——
第 5章 物流系统规划
14
二, 货物装配
货物配装的目的是在车辆载重量为额定值的情况下，合理
进行货物的安排，使车辆装载货物的价值最大（如：重量
最大、运费最低等）。
物流系统工程 ——
第 5章 物流系统规划
15
1,运用动态规划解装货问题
设货车的载重量上限为 G，用于运送 n种不同的货
物，货物的重量分别为 W1,W2,...,Wn，每一种
货物对应于一个价值系数，分别用 P1,P2,...,Pn
表示，它表示价值、运费或重量等。设 Xk表示第 k
种货物的装入数量，货物配装问题的数学模型可
以表示为：
),.,,,1(0
..
)(ma x
1
1
nkX
GXWts
XPxf
k
k
n
k
k
n
k
kk
??
??
??
?
?
?
?
? 可以把装入一件货物作为一个阶段，把装货问题看作动
态规划问题。一般情况下，动态规划问题的求解过程是
从最后一个阶段开始由后向前进行的。由于装入货物的
先后次序不影响装货问题的最优解。所以我们的求解过
程可以从第一阶段开始，由前向后逐步进行。
? 求解过程：
（ 1）装入第 1种货物 X1件，其最大价值为
111 m a x)( XPWf ??
其中,X1表示第 1种货物的装载数量；其取值范围,0<X1< [G/W1], 方
括号表示取整；
P1：第 1种货物的价值系数 （ 重量, 运费, 价值等 ） ；
f1(W)：第一种货物的价值 。
(2)装入第 2种货物 X2件，其最大价值为
其中,X2表示第 2种货物的装载数量；
其取值范围,0<X2< [G/W2] ；
P2：第 2种货物的价值系数 （ 重量, 运费, 价值
等 ） ；
：第一种货物的重量；
：第一种货物的价值 。
（ 3）装入第 3种货物 X3件，其最大价值为
其中,X3表示第 3种货物的装载数量；
其取值范围,0<X3< [G/W3]；
P3：第 3种货物的价值系数；
? ?)(m a x)( 221222 XWWfXPwf ????
22 XWW ?
)( 221 XWWf ?
? ?)(m a x)( 332333 XWWfXPwf ????
……
(n) 装入第 n种货物 Xn件，其最大价值为
其中,Xn表示第 n种货物的装载数量；
其取值范围,0<Xn< [G/Wn] ；
Pn：第 n种货物的价值系数；
? ?)(m a x)( 1 nnnnnn XWWfXPwf ???? ?
例题 9 载重量为 8t的载重汽车, 运输 4种机电产品, 产品重量分别为 3吨,
3吨, 4吨, 5吨, 试问如何配装才能充分利用货车的运载能力?
解,第一步, 按照前面的公式, 分成四个阶段计算每一阶段的价值 。
计算结果以表格表示如下：
货物装配例题
载重量
件数
价值 (重量 )
载重量 第 2种货
物的件数
第 1种货
物的重量
价值计算 价值Max
载重量 第 3种货
物的件数
第 1,2种货物的重量 价值计算 价值Max
第二步：寻找最优方案 。 寻找最优解方案的次序与计算顺序相反, 由第 4阶段向第 1
阶段进行 。 从价值最大的装载情况, 逐步向前寻找最优方案 。
（ 1） 在第 4阶段计算表中, 在载重量为 8时, 价值 (本例为载重量 )最大值 f4(W)＝ 8，
对应两组数据 (加 *号的数据 ),1） X4＝ 0； 2） X4＝ 1；
先看 X4＝ 1时的情况：
当 X4＝ 1时, 即第 4种货物装入 1件 (5吨 ),表中第 3列数字表示其余种类货物
的装载量 。 当 X4＝ 1时, 其他 3种货物装载量为 3吨 ；
（ 2） 按相反方向, 在第 3阶段计算表中, 查 W=3吨时, 得到最大价值 f3(W)＝ 3，
对应的 X3=0。 查表中第 3列数字, W=3,X3=0时, 其余两类货物装入重量 3；
（ 3） 在 第 2阶段计算表中, 查 W=3,f2(W)=3对应两组数据：
1） X2=0；
2) X2=1；
即 当 X2 =1或 0时, 其他 (第 1种 )货物装载量为 3或 0；
（ 4） 查第 1阶段计算表,
1） 当 W＝ 3时, 对应 X1=1；
2） 当 W＝ 0时, 对应 X1=0；
根据当前面的寻找过程, 可以得到 两组最优解,
第一组,X1=1,X2=0,X3=0,X4=1；
第二组,X1=0,X2=1,X3=0,X4=1；
这两组最优解的实际载重量为：
第一组,X1 * 3 + X4 * 5 = 1*3+1*5 = 8
第二组,X2 * 3 + X4 * 5 = 1*3+1*5 = 8
前面的最优方案是在第四阶段取 X4＝ 1时得出的方案 。
如果在第 4阶段计算表中取 X4＝ 0,则其余种类的货物装载量 W - W4X4=8；
在第 3阶段计算表中, 查 W=8一栏, f3(w)=8对应 X3＝ 2,再仿照前面的方
法, 可以得到第 3组最优解：
第三组,X1=0,X2=0,X3=2,X4=0；
装载量为,X3 * 2 = 2*4 = 8
以上三组装载方案, 都最大限度地发挥了车辆的载重能力, 都是最优方
案 。
最终的最优装载方案为：
第一组,X1=1,X2=0,X3=0,X4=1；
第二组,X1=0,X2=1,X3=0,X4=1；
第三组,X1=0,X2=0,X3=2,X4=0；
物流系统工程 ——
第 5章 物流系统规划
27
2,品种混装问题
在实际的物流过程中，储运仓库 (或货运车站 )要把客户所需
的货物组成整车，运往各地。不同客户的货物，要分别在
一站或多站卸货。在装货、运输和卸货过程中，为了减少
装卸、运输过程中出现差错，一般要按照品种、形状、颜
色、规格、到达地点，把货物分为若干类，在装车时分别
进行处理。这就是品种混装问题。
? 设装车的货物可以分为 1类,2类,…, m类。共有 N件 (捆 )
待运货物，其中 1类货物有 N1件 (捆 )，它们的重量分别 G11，
G12,……, G1N1； 2类货物有 N2件 (捆 )，它们的重量分别为
G21,G22,……, G2N2；第 s类货物共有 Ns件，它们的重量
分别为 Gs1,Gs2,……, GsNs；以此类推，可以看出：
货物总的件数：
其中,Ns：第 s类货物的件数；
m：货物的种类数；
N：货物的总件数；
设：
品种混装问题要求同一货车内每类货物至多装入一件（捆），同一客
户的多件同类货物可记作一件（捆）。在这样的假设条件下，可以把
品种混装问题的数学模型表示如下：
ms
NN
m
s
s
,....,2,1
1
?
? ?
?
?
?
??
件货物不装入类第第
件货物装入类第第
sr
srX
rs 0
1
该数学模型的目的是对合理进行分类后的货物进行装载, 使
实际载重量 G的值最大 。 该数学模型属于整数规划的问题,
可以用单纯形法进行求解 。
?
?
?
?
?
?
?
?
??
?
? ?
?
? ?
? ?
?
? ?
m
r
N
s
rsrs
m
s
rs
m
r
N
s
rsrs
r
r
GXG
mrX
ts
XGG
1 1
0
1
1 1
,...,2,11
..
ma x
其中
m：货物的类别数；
Nr：第 r类货物的件数；
Grs：第 r类第 s件货物的重量；
G0：货车载重量的上限。
图 5-20表示 8件货物分为 4类, 在图中同一列的方框表示同一类货物,
方框内的数字 (符号 )表示货物重量 。
上述 品种混装问题就是在网络中自右向左寻找一条路线, 使路线所经
过的方框中的重量之和达到最大, 但又不超过货车的载重量的上限 Go。
? 这种问题可以用穷举法求解, 即比较各条路线的载重量从而求出不超过 Go
的最大装载量的路线；
? 也可以将四类货物看作 4个阶段, 将上述问题化为动态规划问题求解 。 下
面介绍动态规划的解法 。
例题 10 货车载重量上限 Go＝ 50；第 1类货物 2件, G11=20,G12=11；第
2类货物 1件, G21=13；第 3类货物 3件, G31＝ 6,G32＝ 11,G33＝ 8；第 4
类货物 2件, G41＝ 19,G42＝ 17。
19
17
6
11
8
13
20
11
计算过程见表 5-31~34,分成四个阶段进行 。
可装重量
实装重量
剩余容量
第 1阶段的可装容量 W值对应第 2阶
段的剩余容量 W-G
寻找最优解的次序与计算顺序相反，从第一阶段计算表开始，直到第
四阶段。
要使装载量达到最大，对应的剩余余量应当最小。
（ 1）在第一阶段计算表中,余量 W-G1的最小值为零,为最好的方案，
此时，对应的实际装载量 G1为 20，可装载容量 W值为 20。
（ 2）第一阶段的可装载容量 W=20为第二阶段的剩余装载容量，即 W-
G2的值为 20，从表中可以看出第二阶段的剩余装载容量为 20的实际装
载方式有两种，分别是：
G2=0 和 G2=13
对应的可装容量分别为 W=20和 33。
（ 3）第二阶段的可装容量 W=20和 33为第三阶段的剩余装载容量，查
表可得：
对应于剩余可装载容量为 20的实际装载量为 G3=11,可装载容量为
W=31。
对应于剩余可装载容量为 33的实际装载量为 G3=0,可装载容量为
W=33。
（ 4）同理可得第四阶段的 G4为 19和 17。
最后的最优解为,G1=20 G2=0 G3=11 G4=19
G1=20 G2=13 G3=0 G4=17
每组方案的装载量都是 50，达到满载，充分利用了货车的装载能力。
可装重量
实装重量
剩余容量
第 1阶段的可装容量 W值对应第 2阶
段的剩余容量 W-G
物流系统工程 ——
第 5章 物流系统规划
35
三, 物流服务系统中的配置问题
? 随机服务系统
?物流服务系统由服务的机构和顾客组成。
?物流服务系统是一个综合服务系统，许多服务项目具有随机性质。
如：装卸系统、运输系统。
?物流服务系统中的顾客（人、货物等）到来的时间和服务时间随不
同的时机和条件而变化，这种变化具有随机性质，这类系统称为随
机服务系统。
?随机服务系统包含三个过程：顾客输入、排队、服务三个过程。
?排队论是处理随机服务系统的专门理论。
? 服务系统中的设备配置
?服务机构越大，顾客越方便，但机构过大，导致成本升高或浪费。
?服务机构过小，便不能完全满足顾客的需要，使服务质量降低，导
致信誉损失和顾客流失。
?合理配置服务系统，使他既能满足顾客的需要，又能使系统的花费
最为经济，是物流系统配置所关心的主要问题。
? 例题,(P110)，按某仓库的统计数据表明，该仓库必要的车辆数量有
一定的分布规律，如表 5-35和图 5-21所示。每台车辆每天的费用如下：
自备车辆使用费用,C1=500元；自备车辆闲置费用,C2=300元；租
用车辆费用,C3=1000元。
车辆 (台 ) <10 10-15 16-20 21-25 26-30 31-35 35-40
频率 10% 20% 25% 20% 15% 5% 5%
频率累计 10% 30% 55% 75% 90% 95% 100%
表 5-35 仓库每天必要的车辆分布
频
率
台数10
40353015 20 25
10%
20%
25%
20%
15%
5% 5%
图 5-21 仓库每天必要的车辆分布
问题：如何配备车辆数量，才能使车辆费用为最少？
? 解：设仓库配备车辆数为 X，而实际需要的车辆数为 Y，自备车辆使用费用
为 C1，自备车辆闲置费用为 C2，租用车辆费用为 C3。
（ 1）当 Y<X时，（即实际需要的车辆数目比配备的车辆数目少），所需的费
用等于运行费用与闲置费用之和，即：
（ 2）当 Y>X时，（即实际需要的车辆数目比配备的车辆数目多），所需的费
用等于运行费用与租车费用之和，即：
自备车闲置费用自备车运行费用总费用 ??
????? 21 )( CYXCYC
租车费用自备车运行费用总费用 ??
????? 31 )( CXYCXC
设 P(y) 为实际需要车辆对应的概率，则费用目标函数为
])([)()( 31
1
CXYCXYPXF
Xr
?????? ?
?
??
利用微分求极值的方法，并利用下面的等式
可以证明，当 C1< C3 (自备车费用小于租车费用 )时，通过选取 X的值，使
下面的等式成立，就可以使目标费用最少。
? ?
?
?? ?
??
1 1
)(1)(
Xr
X
r
YPYP
?
? ??
??X
r CCC
CCYP
1 132
13)(
代入 C1,C2,C3的数据，可求得
%5.62
5 0 01 0 0 03 0 0
5 0 01 0 0 0)(
1 132
13 ?
??
??
??
???
?
X
r CCC
CCYP
按频率累计数 62.5%与表 5-35对照，可知 X的取值范围在 21~25之间。
以上是在自备车辆费用小于租车费用的前提下计算的，如果自备车辆费
用大于租车费用，则应尽量租车。
物流系统工程 ——
第 5章 物流系统规划
39
本章重点
?物流调运规划
?表上作业法确定产、销地之间的供需联系和数量最优搭
配
?图上作业法进行运输线路的选择
?最短路径与最大流量
?分配规划
?选址问题
?货物装配
西南交通大学电子讲义
1
5.3 物流分配规划
?任务分配问题的数学模型
?用匈牙利法求解分配问题
物流系统工程 ——
第 5章 物流系统规划
2
一, 任务分配问题的数学模型
? 在物流系统中或其它的管理工作中，管理人员经常面临的
一个问题是：如何根据有限的资源 (人力、物力、财力等 )，
进行工作任务分配，以达到降低成本或提高经济效益的目
的。如：
?有 A,B,C,D四门课程，上课的老师可以从甲、乙、丙、丁四名老
师中选择，不同的老师上不同的课程，其费用是不同的，并且规定，
每人只讲一门课程，每门课程只需要一人讲授。问：如何安排，才
能使总的上课费用最低？
?又如：运输任务的分配问题。有 n条航线的运输任务指派给 n艘船去
完成，不同的船完成不同的航线其运输成本不同。要求每条船完成
一条航线，并且一条航线只能由一条船去完成。如何分配任务，才
能使总的费用最小？
? 这类问题是常见的任务分配问题，也叫指派问题，它的任
务是如何进行合理的任务分配，使总的费用最小。
物流系统工程 ——
第 5章 物流系统规划
3
一, 任务分配问题的数学模型
? 以运输问题的 n项任务由 n个司机去完成的情况为例，有 n个
司机被分配完成 n项运输任务，不同的司机完成任务某一项
任务的费用都不一样。要求每个司机完成其中一项任务，
每个任务只能由一名司机完成，如何分配任务，才能使总
的费用最小？
10
1
1..
1
1
1 1
或?
?
?
?
?
?
? ?
?
?
? ?
ij
n
i
ij
n
j
ij
n
i
n
i
ijij
x
x
xts
xcM inZ
令：
cij表示第 i个司机完成第 j项任务的运输成
本（工作成本或工作时间等价值系
数）；
xij表示第 i个司机去完成第 j项任务，其值
为 1或 0。
?当其值为 1时表示第 i个司机被分配去完
成第 j项任务；
?其值为 0时，表示第 i个司机不被分配去
完成第 j项任务。
物流系统工程 ——
第 5章 物流系统规划
4
一, 任务分配问题的数学模型
?任务分配问题属于整数规划问题，其变量 xij的取值
为整数，（本例为 0或 1）。
?任务分配问题可以用一般的整数规划求解方法进
行求解。但是，整数规划问题的求解也是非常困
难的，到目前为止，还缺乏统一的求解方法。
?本书采用匈牙利法求解任务分配问题。
物流系统工程 ——
第 5章 物流系统规划
5
二, 匈牙利法求解分配问题
? 可以证明，对于分配问题，在其费用矩阵 Cij中，各行、各
列均减去一个常数,Cij改变以后的最优解，仍为原问题的
最优解。
? 利用这个性质，通过对 Cij的行、列进行加减常数的计算，
把一些矩阵元素变为 0，在 Cij为 0的元素上进行分解，就可
得到原问题的最优解。
? 该方法应用了匈牙利数学家 Konig矩阵性质定理，因此这种
方法被称为匈牙利法。
物流系统工程 ——
西南交通大学电子讲义
6
5.4 其他规划问题
?选址问题
?货物装配问题
?物流服务系统中的配置问题
物流系统工程 ——
第 5章 物流系统规划
7
一, 选址问题
?物流调运规划问题, 是一种有固定发点, 固定收
点和固定道路的运输规划问题 。
?还有一类运输问题, 他的收货点和发货点是待定
的, 这就是选址问题 。 这类问题在物流系统规划
中经常遇到 。
?选址问题要考虑多种因素, 本节只讨论选址问题
中的物流问题 。 分为两个问题：
?单一地址选址方法；
?图上作业法 。
物流系统工程 ——
第 5章 物流系统规划
8
1,单一地址选址方法
建立一个新工厂（或仓库），应合理选择厂址（或库址）。
所谓选址问题，就是从多个候选厂址中选取一个最优地址
建厂，使物流费用达到最低。
问题描述,假设厂址候选地点有 s个，分别用 D1,D2,…,Ds
表示；原材料、燃料、零配件的供应地有 m个，分别用
A1,A2,…,Am表示，其供应量分别用 P1,P2,…,Pm表示；产品
销售地有 n个，分别用 B1,B2,…,Bn表示，其销售量分别为
Q1,Q2,…,Qn表示。
设 cij为供应地 Ai到候选厂址 Dj的单位运输成本；
djk为候选厂址 Dj到销售地 Bk的单位运输成本；
设选址变量为 xj(j=1,2,…,s),其中,xj=0或 1,1表示在 Dj点建
厂,0表示不在 Dj点建厂。
01
1
mi n
D
BD
D
c运输DA
1
1 11
1 11
1
j
kj
1
j
ji
或
以表示为：选址问题的数学模型可
为：所有候选地的运输成本
费用为：到所有的销售地的运输候选地
的运输费用为：到销售地从候选地
的运输费用为：所有的供应点到候选地
费用为：点的到候选地从供应点
?
?
?????
?
?????
??
??
??
??
?
? ??
? ??
?
?
?
? ??
? ??
?
?
j
s
j
j
j
s
j
n
k
kjk
m
i
iij
s
j
n
k
jkjk
m
i
jiij
n
k
jkjk
jkjk
m
i
jiij
jiij
x
xs, t,
x)QdPc(Z
)xQdxPc(
xQd
xQd
xPc
xP
?单一选址问题是一种线性规划问题,并且变量的取
值为 0或 1,属于整数规划问题 。
?单一地址的选址模型的求解方法比较简单, 从目
标函数表达式的右边可以看出,通过计算模型中
括号内的算式值, 就能够确定运输成本最小的方
案 。
?当要选定的地址不是单一的, 而是多个时, 问题
不再属于线性规划问题 。
物流系统工程 ——
第 5章 物流系统规划
12
2,图上作业法
对于运输路线不含回路的选址问题，可用图上作业法求解。
下面以一个实际例子来说明图上作业法的选址问题：
例题 8 假定有六个矿井．产量分别为 5000吨,6000吨,7000吨、
2000吨,4000吨和 3000吨，运输路线如图所示，这些矿石要经过加工
后才能转运到其他地方。这些矿井之间道路不含回路，欲选择一个矿
井，在此矿井上建立一个加工厂，使各矿井到工厂的运输总费用最低。
为了便于分析, 用一个新的图来代替原图, 新图圈内数字表示矿井编
号, 产量记在圈的旁边, 道路交叉点看作产量为零的矿井, 把那些只
有一条道路连接的矿井称为端点 。
? 首先计算这些矿井的总产量, 本例为 27000吨 。
? 然后分析各端点, 都没有超过总产量的一半, 因此把各端点的数量合并
到前一站, 即 ① 和 ② 的数量合并到 ③ ；把 ④ 的数量合并到 ⑤ ； 把 ⑦
的 数量合并到 ⑥, 如下图所示 。
3 5 6
11000 9000 7000
? 各端点都合并到前一站后, ③ 和 ⑥ 变成了图中的端点 。 对它们进行分
析, 其数量都不超过总产量的一半, 所以他们不是最佳点 。
? 再把它们合并到前一站, 即把 ② 和 ⑥ 的数量合并到 ⑤ 。 则 ⑤ 的数量为
27000,超过总量的一半, 所以 ⑤ 是最佳点 。
? 结论：加工厂应建在第 5号矿井 。
物流系统工程 ——
第 5章 物流系统规划
14
二, 货物装配
货物配装的目的是在车辆载重量为额定值的情况下，合理
进行货物的安排，使车辆装载货物的价值最大（如：重量
最大、运费最低等）。
物流系统工程 ——
第 5章 物流系统规划
15
1,运用动态规划解装货问题
设货车的载重量上限为 G，用于运送 n种不同的货
物，货物的重量分别为 W1,W2,...,Wn，每一种
货物对应于一个价值系数，分别用 P1,P2,...,Pn
表示，它表示价值、运费或重量等。设 Xk表示第 k
种货物的装入数量，货物配装问题的数学模型可
以表示为：
),.,,,1(0
..
)(ma x
1
1
nkX
GXWts
XPxf
k
k
n
k
k
n
k
kk
??
??
??
?
?
?
?
? 可以把装入一件货物作为一个阶段，把装货问题看作动
态规划问题。一般情况下，动态规划问题的求解过程是
从最后一个阶段开始由后向前进行的。由于装入货物的
先后次序不影响装货问题的最优解。所以我们的求解过
程可以从第一阶段开始，由前向后逐步进行。
? 求解过程：
（ 1）装入第 1种货物 X1件，其最大价值为
111 m a x)( XPWf ??
其中,X1表示第 1种货物的装载数量；其取值范围,0<X1< [G/W1], 方
括号表示取整；
P1：第 1种货物的价值系数 （ 重量, 运费, 价值等 ） ；
f1(W)：第一种货物的价值 。
(2)装入第 2种货物 X2件，其最大价值为
其中,X2表示第 2种货物的装载数量；
其取值范围,0<X2< [G/W2] ；
P2：第 2种货物的价值系数 （ 重量, 运费, 价值
等 ） ；
：第一种货物的重量；
：第一种货物的价值 。
（ 3）装入第 3种货物 X3件，其最大价值为
其中,X3表示第 3种货物的装载数量；
其取值范围,0<X3< [G/W3]；
P3：第 3种货物的价值系数；
? ?)(m a x)( 221222 XWWfXPwf ????
22 XWW ?
)( 221 XWWf ?
? ?)(m a x)( 332333 XWWfXPwf ????
……
(n) 装入第 n种货物 Xn件，其最大价值为
其中,Xn表示第 n种货物的装载数量；
其取值范围,0<Xn< [G/Wn] ；
Pn：第 n种货物的价值系数；
? ?)(m a x)( 1 nnnnnn XWWfXPwf ???? ?
例题 9 载重量为 8t的载重汽车, 运输 4种机电产品, 产品重量分别为 3吨,
3吨, 4吨, 5吨, 试问如何配装才能充分利用货车的运载能力?
解,第一步, 按照前面的公式, 分成四个阶段计算每一阶段的价值 。
计算结果以表格表示如下：
货物装配例题
载重量
件数
价值 (重量 )
载重量 第 2种货
物的件数
第 1种货
物的重量
价值计算 价值Max
载重量 第 3种货
物的件数
第 1,2种货物的重量 价值计算 价值Max
第二步：寻找最优方案 。 寻找最优解方案的次序与计算顺序相反, 由第 4阶段向第 1
阶段进行 。 从价值最大的装载情况, 逐步向前寻找最优方案 。
（ 1） 在第 4阶段计算表中, 在载重量为 8时, 价值 (本例为载重量 )最大值 f4(W)＝ 8，
对应两组数据 (加 *号的数据 ),1） X4＝ 0； 2） X4＝ 1；
先看 X4＝ 1时的情况：
当 X4＝ 1时, 即第 4种货物装入 1件 (5吨 ),表中第 3列数字表示其余种类货物
的装载量 。 当 X4＝ 1时, 其他 3种货物装载量为 3吨 ；
（ 2） 按相反方向, 在第 3阶段计算表中, 查 W=3吨时, 得到最大价值 f3(W)＝ 3，
对应的 X3=0。 查表中第 3列数字, W=3,X3=0时, 其余两类货物装入重量 3；
（ 3） 在 第 2阶段计算表中, 查 W=3,f2(W)=3对应两组数据：
1） X2=0；
2) X2=1；
即 当 X2 =1或 0时, 其他 (第 1种 )货物装载量为 3或 0；
（ 4） 查第 1阶段计算表,
1） 当 W＝ 3时, 对应 X1=1；
2） 当 W＝ 0时, 对应 X1=0；
根据当前面的寻找过程, 可以得到 两组最优解,
第一组,X1=1,X2=0,X3=0,X4=1；
第二组,X1=0,X2=1,X3=0,X4=1；
这两组最优解的实际载重量为：
第一组,X1 * 3 + X4 * 5 = 1*3+1*5 = 8
第二组,X2 * 3 + X4 * 5 = 1*3+1*5 = 8
前面的最优方案是在第四阶段取 X4＝ 1时得出的方案 。
如果在第 4阶段计算表中取 X4＝ 0,则其余种类的货物装载量 W - W4X4=8；
在第 3阶段计算表中, 查 W=8一栏, f3(w)=8对应 X3＝ 2,再仿照前面的方
法, 可以得到第 3组最优解：
第三组,X1=0,X2=0,X3=2,X4=0；
装载量为,X3 * 2 = 2*4 = 8
以上三组装载方案, 都最大限度地发挥了车辆的载重能力, 都是最优方
案 。
最终的最优装载方案为：
第一组,X1=1,X2=0,X3=0,X4=1；
第二组,X1=0,X2=1,X3=0,X4=1；
第三组,X1=0,X2=0,X3=2,X4=0；
物流系统工程 ——
第 5章 物流系统规划
27
2,品种混装问题
在实际的物流过程中，储运仓库 (或货运车站 )要把客户所需
的货物组成整车，运往各地。不同客户的货物，要分别在
一站或多站卸货。在装货、运输和卸货过程中，为了减少
装卸、运输过程中出现差错，一般要按照品种、形状、颜
色、规格、到达地点，把货物分为若干类，在装车时分别
进行处理。这就是品种混装问题。
? 设装车的货物可以分为 1类,2类,…, m类。共有 N件 (捆 )
待运货物，其中 1类货物有 N1件 (捆 )，它们的重量分别 G11，
G12,……, G1N1； 2类货物有 N2件 (捆 )，它们的重量分别为
G21,G22,……, G2N2；第 s类货物共有 Ns件，它们的重量
分别为 Gs1,Gs2,……, GsNs；以此类推，可以看出：
货物总的件数：
其中,Ns：第 s类货物的件数；
m：货物的种类数；
N：货物的总件数；
设：
品种混装问题要求同一货车内每类货物至多装入一件（捆），同一客
户的多件同类货物可记作一件（捆）。在这样的假设条件下，可以把
品种混装问题的数学模型表示如下：
ms
NN
m
s
s
,....,2,1
1
?
? ?
?
?
?
??
件货物不装入类第第
件货物装入类第第
sr
srX
rs 0
1
该数学模型的目的是对合理进行分类后的货物进行装载, 使
实际载重量 G的值最大 。 该数学模型属于整数规划的问题,
可以用单纯形法进行求解 。
?
?
?
?
?
?
?
?
??
?
? ?
?
? ?
? ?
?
? ?
m
r
N
s
rsrs
m
s
rs
m
r
N
s
rsrs
r
r
GXG
mrX
ts
XGG
1 1
0
1
1 1
,...,2,11
..
ma x
其中
m：货物的类别数；
Nr：第 r类货物的件数；
Grs：第 r类第 s件货物的重量；
G0：货车载重量的上限。
图 5-20表示 8件货物分为 4类, 在图中同一列的方框表示同一类货物,
方框内的数字 (符号 )表示货物重量 。
上述 品种混装问题就是在网络中自右向左寻找一条路线, 使路线所经
过的方框中的重量之和达到最大, 但又不超过货车的载重量的上限 Go。
? 这种问题可以用穷举法求解, 即比较各条路线的载重量从而求出不超过 Go
的最大装载量的路线；
? 也可以将四类货物看作 4个阶段, 将上述问题化为动态规划问题求解 。 下
面介绍动态规划的解法 。
例题 10 货车载重量上限 Go＝ 50；第 1类货物 2件, G11=20,G12=11；第
2类货物 1件, G21=13；第 3类货物 3件, G31＝ 6,G32＝ 11,G33＝ 8；第 4
类货物 2件, G41＝ 19,G42＝ 17。
19
17
6
11
8
13
20
11
计算过程见表 5-31~34,分成四个阶段进行 。
可装重量
实装重量
剩余容量
第 1阶段的可装容量 W值对应第 2阶
段的剩余容量 W-G
寻找最优解的次序与计算顺序相反，从第一阶段计算表开始，直到第
四阶段。
要使装载量达到最大，对应的剩余余量应当最小。
（ 1）在第一阶段计算表中,余量 W-G1的最小值为零,为最好的方案，
此时，对应的实际装载量 G1为 20，可装载容量 W值为 20。
（ 2）第一阶段的可装载容量 W=20为第二阶段的剩余装载容量，即 W-
G2的值为 20，从表中可以看出第二阶段的剩余装载容量为 20的实际装
载方式有两种，分别是：
G2=0 和 G2=13
对应的可装容量分别为 W=20和 33。
（ 3）第二阶段的可装容量 W=20和 33为第三阶段的剩余装载容量，查
表可得：
对应于剩余可装载容量为 20的实际装载量为 G3=11,可装载容量为
W=31。
对应于剩余可装载容量为 33的实际装载量为 G3=0,可装载容量为
W=33。
（ 4）同理可得第四阶段的 G4为 19和 17。
最后的最优解为,G1=20 G2=0 G3=11 G4=19
G1=20 G2=13 G3=0 G4=17
每组方案的装载量都是 50，达到满载，充分利用了货车的装载能力。
可装重量
实装重量
剩余容量
第 1阶段的可装容量 W值对应第 2阶
段的剩余容量 W-G
物流系统工程 ——
第 5章 物流系统规划
35
三, 物流服务系统中的配置问题
? 随机服务系统
?物流服务系统由服务的机构和顾客组成。
?物流服务系统是一个综合服务系统，许多服务项目具有随机性质。
如：装卸系统、运输系统。
?物流服务系统中的顾客（人、货物等）到来的时间和服务时间随不
同的时机和条件而变化，这种变化具有随机性质，这类系统称为随
机服务系统。
?随机服务系统包含三个过程：顾客输入、排队、服务三个过程。
?排队论是处理随机服务系统的专门理论。
? 服务系统中的设备配置
?服务机构越大，顾客越方便，但机构过大，导致成本升高或浪费。
?服务机构过小，便不能完全满足顾客的需要，使服务质量降低，导
致信誉损失和顾客流失。
?合理配置服务系统，使他既能满足顾客的需要，又能使系统的花费
最为经济，是物流系统配置所关心的主要问题。
? 例题,(P110)，按某仓库的统计数据表明，该仓库必要的车辆数量有
一定的分布规律，如表 5-35和图 5-21所示。每台车辆每天的费用如下：
自备车辆使用费用,C1=500元；自备车辆闲置费用,C2=300元；租
用车辆费用,C3=1000元。
车辆 (台 ) <10 10-15 16-20 21-25 26-30 31-35 35-40
频率 10% 20% 25% 20% 15% 5% 5%
频率累计 10% 30% 55% 75% 90% 95% 100%
表 5-35 仓库每天必要的车辆分布
频
率
台数10
40353015 20 25
10%
20%
25%
20%
15%
5% 5%
图 5-21 仓库每天必要的车辆分布
问题：如何配备车辆数量，才能使车辆费用为最少？
? 解：设仓库配备车辆数为 X，而实际需要的车辆数为 Y，自备车辆使用费用
为 C1，自备车辆闲置费用为 C2，租用车辆费用为 C3。
（ 1）当 Y<X时，（即实际需要的车辆数目比配备的车辆数目少），所需的费
用等于运行费用与闲置费用之和，即：
（ 2）当 Y>X时，（即实际需要的车辆数目比配备的车辆数目多），所需的费
用等于运行费用与租车费用之和，即：
自备车闲置费用自备车运行费用总费用 ??
????? 21 )( CYXCYC
租车费用自备车运行费用总费用 ??
????? 31 )( CXYCXC
设 P(y) 为实际需要车辆对应的概率，则费用目标函数为
])([)()( 31
1
CXYCXYPXF
Xr
?????? ?
?
??
利用微分求极值的方法，并利用下面的等式
可以证明，当 C1< C3 (自备车费用小于租车费用 )时，通过选取 X的值，使
下面的等式成立，就可以使目标费用最少。
? ?
?
?? ?
??
1 1
)(1)(
Xr
X
r
YPYP
?
? ??
??X
r CCC
CCYP
1 132
13)(
代入 C1,C2,C3的数据，可求得
%5.62
5 0 01 0 0 03 0 0
5 0 01 0 0 0)(
1 132
13 ?
??
??
??
???
?
X
r CCC
CCYP
按频率累计数 62.5%与表 5-35对照，可知 X的取值范围在 21~25之间。
以上是在自备车辆费用小于租车费用的前提下计算的，如果自备车辆费
用大于租车费用，则应尽量租车。
物流系统工程 ——
第 5章 物流系统规划
39
本章重点
?物流调运规划
?表上作业法确定产、销地之间的供需联系和数量最优搭
配
?图上作业法进行运输线路的选择
?最短路径与最大流量
?分配规划
?选址问题
?货物装配
