ΣΣ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的路线，这条路线具有以下特点：
（1）所有正向弧�