例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；而已