按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！
素个数相同。本例中为：
。
。
。
。。
。。。
。
。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
显然，一条�