第26章--基于匈牙利算法的指派問題優(yōu)化分析.ppt

《第26章--基于匈牙利算法的指派問題優(yōu)化分析.ppt》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、第二十六章MATLAB優(yōu)化算法案例分析與應用第26章基于匈牙利算法的指派問題優(yōu)化分析第二十六章MATLAB優(yōu)化算法案例分析與應用26.1匈牙利算法1955年，庫恩（w·w·Kuhn）提出了匈牙利算法，它是一種關于指派問題的求解方法。匈牙利算法引用了匈牙利數(shù)學家康尼格（D.konig）的一個關于矩陣中獨立0元素個數(shù)的定理：矩陣中獨立0元素的個數(shù)等于能夠覆蓋所有0元素的最少直線數(shù)。匈牙利算法的基本思想是修改效益矩陣的行或列，使得每一行或列中至少有一個為零的元素，經(jīng)過修正后，直至在不同行、不同列中至少有一

2、個零元素，從而得到與這些零元素相對應的一個完全分配方案。當它用于效益矩陣時，這個完全分配方案就是一個最優(yōu)分配，它使總的效益為最小。這種方法總是在有限步內收斂于一個最優(yōu)解。該方法的理論基礎是：在效益矩陣的任何行或列中，加上或減去一個常數(shù)后不會改變最優(yōu)分配。其求解步驟如下：第一步，修正效益矩陣，使之變成每一行和每一列至少有一個零元素的縮減矩陣：（1）從效益矩陣的每一行元素減去各該行中最小元素；（2）再從所得縮減矩陣的每列減去各該列的最小元素。第二步，試制一個完全分配方案，它對應于不同行不同列只有一個零元

3、素的縮減矩陣，以求得最優(yōu)解：（1）如果得到分布在不同行不同列的N個零元素，那么就完成了求最優(yōu)解的過程。結束。（2）如果所分布于不同行不同列中的零元素不夠N個，則轉下步。第二十六章MATLAB優(yōu)化算法案例分析與應用第三步，作出覆蓋所有零元素的最少數(shù)量的直線集合：（1）標記沒有完成分配的行。（2）標記已標記行上所有未分配零元素所對應的列。（3）對標記的列中，已完成分配的行進行標記。（4）重復（2）、（3）直到?jīng)]有可標記的零元素。（5）對未標記的行和已標記的列畫縱、橫線，這就得到能覆蓋所有零元素的最少數(shù)量

4、的直線集合。第四步，修改縮減矩陣，以達到每行每列至少有一個零元素的目的：（1）在沒有直線覆蓋的部分中找出最小元素。（2）對沒有畫直線的各元素都減去這個元素。（3）對畫了橫線和直線交叉處的各元素都加上這個最小元素。（4）對畫了一根直線或橫線的各元素保持不變。（5）轉第二步。第二十六章MATLAB優(yōu)化算法案例分析與應用26.2匈牙利算法計算實例步驟以下列矩陣為例：計算步驟如下：（1）先讓矩陣C中每行元素減去該行元素中的最小值，再讓每列元素減去該列元素中的最小值，這樣每行必然會產(chǎn)生至少一個零元素：第二十六

5、章MATLAB優(yōu)化算法案例分析與應用（2）先找出僅有一個“0”元素的行，并劃去與該“0”同列的其他“0”元素，然后找出僅有一個“0”元素的列，并劃去與該“0”同行的其他“0”元素。（3）觀察矩陣中的零元素的個數(shù)是否等于矩陣的階數(shù)，若兩者相等則算法結束，否則需要對矩陣進行變化。直到矩陣中零元的個數(shù)與矩陣的階數(shù)相等則算法結束。第二十六章MATLAB優(yōu)化算法案例分析與應用26.3指派問題的數(shù)學模型第二十六章MATLAB優(yōu)化算法案例分析與應用任務人員ABCD甲1174乙0630丙8718丁2803戊8241

6、表26-1效率矩陣指派問題%匈牙利算法clc,clear,closeall%清屏、清工作區(qū)、關閉窗口warningoff%消除警告featurejitoff%加速代碼執(zhí)行A=[11740630871828038241];[Matching,Cost]=Hungarian(A)第二十六章MATLAB優(yōu)化算法案例分析與應用function[Matching,Cost]=Hungarian(Perf)%[MATCHING,COST]=Hungarian_New(WEIGHTS)%匈牙利算法%給定一個nxn

7、矩陣的邊權矩陣，使用匈牙利算法求解最小邊權值和問題，類似最小樹問題%如果矩陣中出現(xiàn)inf，則表示沒有邊與之相連%輸出：%Matching為一個nxn的矩陣，只有0和1%COST為對應Matching處為1所在位置的元素和%初始化變量Matching=zeros(size(Perf));%初始化%移除Inf，加速算法執(zhí)行效率%針對每一列找infnum_y=sum(~isinf(Perf),1);%求列和%針對每一行找infnum_x=sum(~isinf(Perf),2);%行和%尋找獨立的列向量和行

8、向量x_con=find(num_x~=0);第二十六章MATLAB優(yōu)化算法案例分析與應用Matching=01001000000000100001Cost=6有結果可知，甲做B任務，乙做A任務，丙不做任務，丁做C任務，戊做D任務。匈牙利算法對于目標分配是適用的，且仿真速度較快。