现代物流学-第33部分

快捷操作: 按键盘上方向键 ← 或 → 可快速上下翻页 按键盘上的 Enter 键可回到本书目录页 按键盘上方向键 ↑ 可回到本页顶部! 如果本书没有阅读完，想下次继续接着阅读，可使用上方 "收藏到我的浏览器" 功能 和 "加入书签" 功能！


示。　
表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三个仓库进行搬运作业，其
中任一叉车都可以在任一仓库中进行搬运工作，只是搬运作业费不同，各台叉车相应作业
费Cij如表12…12所示，要求一台叉车只分配给一个仓库使用，试求搬运作业费用最小的分配
方案。　

12…6　



表12…12　效率矩阵表　

叉车　
cij
仓库　
B1　B2　B3　
A1　25　15　22　
A2　31　20　19　
A3　35　24　17　

对应于每个分配问题，　都有类似于表　12…12　的数字表，称之为效率矩阵，其元素　c　ij＞0（i；j=1；2；。。。；n）表示分配第i个单位去完成第j项任务时的效率（或时间、成本等）。根
据问题引入变量xij，并按以下规定取值：　

1第i个单位被分配去完成第j项任务　
xij　
0　第i个单位不去完成第j项任务其中i=1；2；。。。；n；　j=1；2；。。。；n


当问题要求极小时；有数学模型：　

min　z　
=Σ（n）　Σ（n）　

cij　
xij

i==j

11　

st。　

。。
。　


=

。　
。。。
。


n　


xij　
1；j　
1；2；。。。；　n　


in　
1　（12。2）　

xij　
1；　i　
1；2；。。。；　n　


=
=　
j　
1　

=　


=　


=　


Σ=　
Σ

　上述模型中；约束条件1表明第j项任务只能由1个单位去完成；约束条件2则说明第i个单
位只能完成1项任务。对于求极大问题时，可转化cij为c’ij；即令c’ij=cij…max｛cij｝；将原maxz=　
ΣΣcijxij转化为minz’=　c’ijxij求解。　

12。2。2　匈牙利算法
可以看到，分配问题是0…1规划问题，对于几个单位分配几项任务的分配问题，总共有
n！种可能的分配方案，若用隐枚举法求解，当n较大时，计算量是很大的。由匈牙利数学
家考尼格给出的匈牙利算法，是一种求解分配问题最简单、最有效的方法。　
匈牙利法的主要依据是，在效率矩阵的任何行或列中，加上或减去同一常数，并不改
变最优分配。利用此性质，可使原效率矩阵变换为含有很多0元素的新效率矩阵，找出在其
中的位于不同行、不同列的n个独立的0元素，将其取值为1，其它元素取值为0，即得原分
配问题的最优解。　
以下通过求解例12…2的分配问题，介绍匈牙利算法　
已知其效率矩阵为：　


。

2515　22

。　


。　
。　
。　
。。

。　
。　
。。

35　

　第一步　变换效率矩阵，使其每一行和每一列都至少有一个0元素，具体通过减去每行、每
列的最小元素，如下：　

10　
18　

。　
。　
。。


31　20　19　


24　17　


07　


007


。
。


。


。

。　
。　
。　
。。

2515　22　…15　
35　

。　
。　
。。


。　
。　
。。


。　
。　
。。


。　
。　
。。


12　1　0　


210


31　20　19　


　…19　→


　→　


70　


870


24　17　


…17　


。10　


12…7　



第二步　试求最优分配方案。　

（1）从1行开始，依次检查各行，找出只有一个未标记的0元素的行，并将该元素用
“0”表示，与该元素同行同列的其它0元素用“Ф”表示，其含义为，0元素对应的任

务仅由所对应的单位去完成，此单位不再去完成其它任务，这项任务也不再由其它单位

完成。0和Ф称为已标记的0元素。重复此过程，直到每一行没有一个尚未标记的0元

素，或至少有两个未标记的0元素。

（2）依次检查各列，找出只有一个未标记的0元素的列，将该元素标以0，并与该元
素同行同列的其它未标记0元素标以Ф，直到每列没有一个尚未标记的0元素，或至少有
两个未标记的0元素。　

（3）重复上述步骤，直到效率矩阵中没有未标记的0元素为止，若n行n列效率矩阵中
恰有n个0元素，就得到最优分配方案，否则，仍需进行效率矩阵调整，本例中为：　

。　
。　
。　
。。


0　Ф　7　
2　1　0　
8　7　Ф

。　
。　
。　
。。　


第三步　继续调整效率矩阵　

（1）对每个0元素划一条水平线或垂直线，使这些线覆盖所有0元素。直线个数与0元
素个数相同。本例中为：　

。


。　
。　
。。


。。。
。
。0　Ф　7　
2　1　0　
8　7　Ф
（2）在直线不穿过的所有元素中找出最小元素。　
（3）在没有水平线的各行减去此最小元素；有垂直线的各列加上此最小元素；得新的效率
矩阵。　
本例中，所求最小元素为1，计算过程为：　

。。。
。
。
。。。
。
。0　Ф　7　
2　1　0　
8　7　0　
。

008

。　


…1　→　


…1　


。　
。　
。。


100　


760　


。　
。　
。。


＋1　


第四步　回第二步；直到求出最优分配方案。　
本例中，对修改后的效率矩阵重复第二步得：　

Ф　8　
1　0　Ф　
7　6　0

。　
0

。　


。　
。　
。。


。　
。　
。。　


已经得3个0元素，故得最优分配方案为：　

Σ

　A1→B1，A2→B2，A3→B3
根据原效率矩阵，3叉车总搬运作业费为：　
25＋20＋17=62元　

12。2。3　巡回运输问题（旅行商问题）　
在单网点配送中，物流网点向所属用户送货，各用户的需求量bi（i=1；2；　…；n），货
车载重量为Q，若满足bi　
≤　
Q　
，则该网点只需一辆货车巡回送货即可。显然，在这种情

况下使费用最省的方案就是合理安排货车访问各用户的顺序，使货车的巡回线路的总距离
最短，这也就是旅行商问题。　

12…8　



例12…3已知5用户间距离如表12…13，其中d（i；j）=∝表示从第i个用户到第j个用户是
没有意义的；　用户1为物流网点所在位置，如果只考虑将每个用户都当作一个出发用户；每
个用户都当作一个到达用户；则对每个出发用户都要选择一个到达用户；而每个到达用户只
能有一个出发用户到达该地；将问题变成了一个分配问题；可用匈牙利法求解。　

表12…13　用户间距表　

到达　
出发　
1　2　3　4　5　
1　∝　1　7　4　3　
2　2　∝　6　3　43　1　6　∝　2　1　
4　1　5　4　∝　6　
5　7　5　4　5　∝　

以例12…13说明求解步骤　

第一步　令d（i；i）=∝；不存在通路的也记为∝；得距离阵；通常d（i；j）与d（j；i）不一定
相同；即矩阵不一定对称。　

第二步　对距离矩阵用匈牙利法求解；若得到无环路的路线；则就是最优路线；若路线有
环路；就不是最优路线；但所走总距离给出了旅行商问题总距离的下界。　

在本例中，匈牙利法求解过程为：　

∞


1743


∞


0632


∞


622


。


。


。


。
。


。


…1　


0　


。　
。　
。　
。　
。　
。。


。。。。。
。


。　
。　
。　
。　
。　
。。


。　
。　
。　
。　
。　
。。
。　
。　
。　
。　
。　
。。

→　

。　
。　
。　
。　
。　
。。


φ


2


∞


634　


0


∞


412


∞


4　


2


…2　


0　


…1


φ


φ


16


∞


21　


05


∞


10　


5


∞


→　


0　


…1


154


∞


6　


043


∞


5　


43


∞
φ


5


0　


…4


7545


∞


3101


∞


31


∞


0


。

。1

得不考虑环路下的最优方案：　
1→2，2→4，4→1，3→5，5→3　
所走总距离为：　


　1＋3＋1＋1＋4=10　
可以看出上述路线存在环路，不是原问题的最优路线，但给出了原问题的下界10。　
第三步　出现环路时，打开节点个数最少的环路。即在此环路上考虑某段路线不通的

各种情况，分别用匈牙利法求解，其中距离最短又无环路的路线即为最优路线。　
本例中，出现两个环路，1→2→4→1和3→5→3，打开节点数少的环路，分别令
d（3；5）=∝和d（5；3）=∝求解。　

（1）当d（3；5）=∝时；用匈牙利法求解　
0


φ


∞


1743


∞


0632


∞


62


。


。


。


。
。


。


…1　
…2　
…1　


。　
。　
。　
。　
。　
。。


。　
。　
。　
。　
。　
。。


。　
。　
。　
。　
。　
。。


。　
。　
。　
。　
。　
。。
。　
。　
。　
。　
。　
。。

→　

。　
。　
。　
。　
。　
。。


φ


φ


2


∞


634　


0


∞


412


∞


4　


0　


φ


16


∞


2


∞


05


∞


1


∞


5


∞


∞


→　


0　


…1　


…4　


154


∞


6　


043


∞


5　


43


∞
φ　


5　


∞　


0　


7545


∞


3101


∞


31　


0　


。1　。　
2

可得无环路的最优方案：　5→3→4→1→2→5　

12…9　



所走总距离为：　1＋4＋2＋1＋4=12　

（2）当d（5；3）=∝时；用匈牙利法求解　
。


∞17　4　3　
2∞6　3　4　
1　6∞2　1　
1　5　4∞6　
7　5∞5∞　


。


…1


。


∞0　6　3　2　
0∞4　1　2　
0　5∞1　0　
0　4　3∞5　
2　0∞0∞　


。
。


0　


332


。


∞　


。。。。。


。。。。。


。。。。。


。。。。。


112

∞

0


…2　


…1　→　


…1　


41

∞

0


→　


4　


0　


5

∞　


…5


。。。。。0。
。　
3
得路线：　1→2；2→1；3→5；4→3；5→4　
总距离：　1＋2＋1＋4＋5=13　
可以看到：　

20

∞

∞　


上述方案出现环路1→2→1和3→5→4→3；如果打开环路求解；其总距离一定不小于13；而已
经得到总距离为12的路线；故不必再作计算；　

因此得上述旅行商的最优路线为：5→3→4→1→2→5；总距离为12。　

12。2。4　旅行商问题的神经网络求解　
虽然可以应用匈牙利算法求解旅行商问题，但是该方法需要进行多次试探，只适用于
小规模的问题，而随着距离矩阵维数的增加，求解的时间将大量增长，求解的复杂度也急
剧增加，该方法变得不再适用，此时可采用人工智能的方法——神经网络方法进行求解。　

1。连续Hopfield神经网络模型　
连续Hopfield神经网络模型如图12…1所示。第i个神经元的输入为ui　，输出状态为vi；
运算放大器模拟神经元的转移函数g（其中g为sigmoid函数），跨导T　ij模拟神经元之间互连的
突触特性，电容c　i　及电阻R　i用来模拟生物神经元的输出时间常数。设有n个神经元互连，则
可用下述非线性微分方程描述：　


（a）Hopfield神经元　

。。。。。


。。。。。


φ　


φ


12…10　



（b）Hopfield神经网络
图12…1　连续时间神经网络模型　

n

。　
dui　
（t）　ui　
（t）

。ci　
=ΣTijv　
j　
（t）　。＋　
Ii

。　dt　=1　Ri　
（12。3）
。v　
（t）　=　
g（u　）（i）　

。　ii　

对式（12。3）可以定义系统的能量函数为：　

11　v

E　=。Σ（n）　Σ（n）　Σ（n）　Σ（n）　i　
（v）dv　
（12。4）

2　i　
j　
iiR11111i　
∫
==
。
==
＋。iijiijgvITvv0

可以证明，对于该能量函数，恒有　
dE≤　
0　，即当t→∞，网络达到稳态。显然应用网

dt　


络的这一特性，可以进行优化问题的求解。求解时，只需将优化问题的目标函数转化成

（12。4）式的形式，然后应用式（12。3）运算到网络收敛即可。通常在用Hopfield神经网络求
解实际问题时，一般忽略能量式中的积分项，将能量函数简化为下式（12。5），以便目标函
数的映射。　
E　=。　1　ΣΣn（n）　Tijviv　
j　
。Σ（n）　viIi　
（12。5）
2　i=1　j=1　i=1　

2。神经网络求解旅行商问题　
对于n个用户的TSP问题，任何一个用户在最终访问路径上的访问次序可用一个n维向量
表示，因此每一个用户可用n个神经元表示。下面仍以例12…3为例说明，如果用户1第3个被
访问，则表示为00100，即第三个神经元输出为1，其余为0。为了表示n个用户，可简单地
用n╳n换位矩阵表示，如表12…14所示。　

表　12…14　换位矩阵　

用户　
次序　1　2　3　4　5　
1　0　0　1　0　0　
2　0　1　0　0　0　
3　1　0　0　0　0　
4　0　0　0　1　0　
5　0　0　0　0　1　

上述换位矩阵表示巡回线路为：3→2→1→4→5　
巡回距离为：distance=d（3；2）＋d（2；1）＋d（1；4）＋d（4；5）　

12…11　



显然，一条换位距阵可表示一条有效路径，如果要构成一条有效的最短巡回路线，必然要求满足下列条件：　

（1）换位矩阵中每行只能有一个为“1”；　（2）换位矩阵中每列只能有一个为“1”；　（3）换位矩阵中元素“1”之和应为n；　（4）所构造的函数的极小值对应。　ΣΣΣΣΣΣΣΣE（。）＋＋vvvvvn=（n）　（n）　（n）　（n）　xixjxiyixi2221i1jii111i1≠≠x===x=yxx==（n）　nΣΣΣd（）（）＋＋xyvvv；i1＋y；；式（12。5）中第1、2、3项对应于换位矩阵的条件（1）、（2）、（3），第4项对应于条件（4），即使路径最短的目标要求。A、B、C、D为4个正常系数，将式（12。6）写成如IT（12。5）所表示的Hopfield能量函数标准形式，得的表达式和的值如下：xiyixi；。。。由（12。6）　得Hopfiled网络运行方程式如式（12。8）：　（n）　（n）　

用n╳n=25个神经元的输出　vxi　
（1　≤x　
≤　
n；1　≤　
i　
≤　
n）　表示换位矩阵中的某一元素（取值
为“0”或“1”），其中x表示用户，i表示访问次序，则可以写出与本问题对应的计算能
量函数为：　

n　
nn

A　
BC　
2　

（12。6）　
D　


xi　
1　yi。
2　x=1　y≠　
xi=1　


Txi；　yi　
=。Aδxy　
（1。δij　
）　。　
Bδij　
（1。δ　
xy　
）　。　
C　
。　
Dd（x；　y）（δ　
j；i＋1　＋δ　
j；i。1）（1。δ　
xy　
）　

　（12。7）　
I　
xi　
=　
CN　


其中δxy　
=　
1　if　
x　
=　
y　


0　

。。
。　


nn　
nnn　


xi　
xi

du　
=。　
u　
。　
C（ΣΣvxj　
。　
n）　。　
AΣvxj　
。　
BΣvyi　
。　
DΣd（x；　y）（vy；i＋1　＋　
vy；i。1）　

　（12。8）
dt　
τx=1　j=1　j≠iy≠xy≠x　


v　


。。
。　
。。

=　


g（uxi　
）　x　
1；2；L；n；　i　
=；2；L；n；

=　


xi　


作用函数　g选用sigmoid函数　g（uxi　
）　=12　
（1＋　
th（uxi　
/　u0　））　；网络初始值可置为　

uxi　
=　
1/　n；在选择适当的系数A；B；C；D；　τ；进行迭代运算，得网络收敛稳定输出vxi　
，即可
获得巡回配送的最短路径。　

12。3　网络流问题　
12。3。1图的基本概念　
考虑6个城市间的交通路线图；如图12…12所示；图中的点V1、V2、V3、V4、V5、V6代表6
个城市，又称为顶点，连接各顶点的弧记作（V1、V2）、（V2、V3）、。。。等。这种表明各点
之间连接关系的图形，通常称为图。　
从一个顶点沿着弧、顶点、弧、顶点的顺序，回到出发点的路线称为回路，如图12…2
中，V1→V2→V4→V3→V1、V4→V5→V6→V4都是回路，不含回路、各顶点又相互连通的图称为
树，如图12…3就是一个树。　

V1　V2　


V2　

V3　

V4　V3　

V4　

VB5　

VB6　

VB5　

VB6　

图12…2　回路　图12…3树

12…12　



10（5）　
3（2）　
5（1）　
10（5）　
3（2）　
5（1）　
在实际问题中，对于一个图，总要考虑它们代表的各城市间道路的交通流量、流动方
向，因此需在各顶点弧上标明流动方向和流量限制，这种表示流动方向和流量限制的图称
为网络或网络流，如图12…4。　

V1　V2　

V3　

V4　

V5　

V6　


图12…4　

在网络流中有些点只有发出，称不发点或源点，如图12…4中的V　1；有些点只有收入，
无发出，称为收点或汇点，如图12…4中的V　6，还有些顶点既有收入又有发出，称为中间
点。　

12。3。2　网络最大流问题　
1。问题的提出　
已知连接产地V1与销地Vn的交通网，每一弧（Vi；Vj）代表从Vi到Vj的运输线，产品经由　
Vi输送到Vj，弧旁括号外的数字Cij为弧的容量，括号内的数字Xij为Vi到Vj的货运量，要求合
理安排Xij，使V1到V　n的货运量最大。这种问题称为最大流问题，如图12…5所示。　

V4

V2　6（3）　

11（6）　

10（5）　
2（3）　

V1　

V6　

17（2）　

8（3）　
6（3）　
图12…5　


2。寻求最大流的标号法　
对于包含n个顶点V1，V2。。。；Vn的网络流，V　1为发点，Vn为收点，各段弧（V　i；Vj）上容量为　
Cij，设｛Xij｝是一个可行流，如果存在一条从V1到Vn的路