天天书屋

手机浏览器扫描二维码访问

第45部分（第1页）

ΣΣ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

。

。

。

。

。

。

瓦岗英雄  你为什么是穷人  苍狼与白鹿  唤起心中的巨人  真本事来自好观念  蛟郎  心理操纵术  企业员工哲学:终极期望  杀手的任务穿越  泣画  不忍放开你的手  狼性法则  二战大兵  痞子将军:战争之王  美国厚黑学-人生必胜之道  长沙王传  黑天鹅(军旅)  红色风暴  著名女性演说精粹  宇宙第一军