第26章--基于匈牙利算法的指派问题优化分析.ppt

《第26章--基于匈牙利算法的指派问题优化分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二十六章MATLAB优化算法案例分析与应用第26章基于匈牙利算法的指派问题优化分析第二十六章MATLAB优化算法案例分析与应用26.1匈牙利算法1955年，库恩（w·w·Kuhn）提出了匈牙利算法，它是一种关于指派问题的求解方法。匈牙利算法引用了匈牙利数学家康尼格（D.konig）的一个关于矩阵中独立0元素个数的定理：矩阵中独立0元素的个数等于能够覆盖所有0元素的最少直线数。匈牙利算法的基本思想是修改效益矩阵的行或列，使得每一行或列中至少有一个为零的元素，经过修正后，直至在不同行、不同列中至少有一

2、个零元素，从而得到与这些零元素相对应的一个完全分配方案。当它用于效益矩阵时，这个完全分配方案就是一个最优分配，它使总的效益为最小。这种方法总是在有限步内收敛于一个最优解。该方法的理论基础是：在效益矩阵的任何行或列中，加上或减去一个常数后不会改变最优分配。其求解步骤如下：第一步，修正效益矩阵，使之变成每一行和每一列至少有一个零元素的缩减矩阵：（1）从效益矩阵的每一行元素减去各该行中最小元素；（2）再从所得缩减矩阵的每列减去各该列的最小元素。第二步，试制一个完全分配方案，它对应于不同行不同列只有一个零元

3、素的缩减矩阵，以求得最优解：（1）如果得到分布在不同行不同列的N个零元素，那么就完成了求最优解的过程。结束。（2）如果所分布于不同行不同列中的零元素不够N个，则转下步。第二十六章MATLAB优化算法案例分析与应用第三步，作出覆盖所有零元素的最少数量的直线集合：（1）标记没有完成分配的行。（2）标记已标记行上所有未分配零元素所对应的列。（3）对标记的列中，已完成分配的行进行标记。（4）重复（2）、（3）直到没有可标记的零元素。（5）对未标记的行和已标记的列画纵、横线，这就得到能覆盖所有零元素的最少数量

4、的直线集合。第四步，修改缩减矩阵，以达到每行每列至少有一个零元素的目的：（1）在没有直线覆盖的部分中找出最小元素。（2）对没有画直线的各元素都减去这个元素。（3）对画了横线和直线交叉处的各元素都加上这个最小元素。（4）对画了一根直线或横线的各元素保持不变。（5）转第二步。第二十六章MATLAB优化算法案例分析与应用26.2匈牙利算法计算实例步骤以下列矩阵为例：计算步骤如下：（1）先让矩阵C中每行元素减去该行元素中的最小值，再让每列元素减去该列元素中的最小值，这样每行必然会产生至少一个零元素：第二十六

5、章MATLAB优化算法案例分析与应用（2）先找出仅有一个“0”元素的行，并划去与该“0”同列的其他“0”元素，然后找出仅有一个“0”元素的列，并划去与该“0”同行的其他“0”元素。（3）观察矩阵中的零元素的个数是否等于矩阵的阶数，若两者相等则算法结束，否则需要对矩阵进行变化。直到矩阵中零元的个数与矩阵的阶数相等则算法结束。第二十六章MATLAB优化算法案例分析与应用26.3指派问题的数学模型第二十六章MATLAB优化算法案例分析与应用任务人员ABCD甲1174乙0630丙8718丁2803戊8241

6、表26-1效率矩阵指派问题%匈牙利算法clc,clear,closeall%清屏、清工作区、关闭窗口warningoff%消除警告featurejitoff%加速代码执行A=[11740630871828038241];[Matching,Cost]=Hungarian(A)第二十六章MATLAB优化算法案例分析与应用function[Matching,Cost]=Hungarian(Perf)%[MATCHING,COST]=Hungarian_New(WEIGHTS)%匈牙利算法%给定一个nxn

7、矩阵的边权矩阵，使用匈牙利算法求解最小边权值和问题，类似最小树问题%如果矩阵中出现inf，则表示没有边与之相连%输出：%Matching为一个nxn的矩阵，只有0和1%COST为对应Matching处为1所在位置的元素和%初始化变量Matching=zeros(size(Perf));%初始化%移除Inf，加速算法执行效率%针对每一列找infnum_y=sum(~isinf(Perf),1);%求列和%针对每一行找infnum_x=sum(~isinf(Perf),2);%行和%寻找独立的列向量和行

8、向量x_con=find(num_x~=0);第二十六章MATLAB优化算法案例分析与应用Matching=01001000000000100001Cost=6有结果可知，甲做B任务，乙做A任务，丙不做任务，丁做C任务，戊做D任务。匈牙利算法对于目标分配是适用的，且仿真速度较快。