求解指派問題的匈牙利算法.doc

《求解指派問題的匈牙利算法.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫(kù)。

1、3.2求解指派問題的匈牙利算法由于指派問題的特殊性，又存在著由匈牙利數(shù)學(xué)家D.Konig提出的更為簡(jiǎn)便的解法—匈牙利算法。算法主要依據(jù)以下事實(shí)：如果系數(shù)矩陣一行（或一列）中每一元素都加上或減去同一個(gè)數(shù)，得到一個(gè)新矩陣?，則以或?yàn)橄禂?shù)矩陣的指派問題具有相同的最優(yōu)指派。利用上述性質(zhì)，可將原系數(shù)陣C變換為含零元素較多的新系數(shù)陣B，而最優(yōu)解不變。若能在B中找出n個(gè)位于不同行不同列的零元素，令解矩陣中相應(yīng)位置的元素取值為1，其它元素取值為零，則所得該解是以B為系數(shù)陣的指派問題的最優(yōu)解，從而也是原問題的最優(yōu)解。由C到B的轉(zhuǎn)

2、換可通過先讓矩陣C的每行元素均減去其所在行的最小元素得矩陣D，D的每列元素再減去其所在列的最小元素得以實(shí)現(xiàn)。下面通過一例子來說明該算法。例7求解指派問題，其系數(shù)矩陣為解將第一行元素減去此行中的最小元素15，同樣，第二行元素減去17，第三行元素減去17，最后一行的元素減去16，得再將第3列元素各減去1，得以為系數(shù)矩陣的指派問題有最優(yōu)指派由等價(jià)性，它也是例7的最優(yōu)指派。有時(shí)問題會(huì)稍復(fù)雜一些。例8求解系數(shù)矩陣的指派問題解：先作等價(jià)變換如下容易看出，從變換后的矩陣中只能選出四個(gè)位于不同行不同列的零元素，但，最優(yōu)指派還無

3、法看出。此時(shí)等價(jià)變換還可進(jìn)行下去。步驟如下：(1)對(duì)未選出0元素的行打；(2)對(duì)行中0元素所在列打；(3)對(duì)列中選中的0元素所在行打；重復(fù)（2）、（3）直到無法再打?yàn)橹??？梢宰C明，若用直線劃沒有打的行與打的列，就得到了能夠覆蓋住矩陣中所有零元素的最少條數(shù)的直線集合，找出未覆蓋的元素中的最小者，令行元素減去此數(shù)，列元素加上此數(shù)，則原先選中的0元素不變，而未覆蓋元素中至少有一個(gè)已轉(zhuǎn)變?yōu)?，且新矩陣的指派問題與原問題也等價(jià)。上述過程可反復(fù)采用，直到能選取出足夠的0元素為止。例如，對(duì)例5變換后的矩陣再變換，第三行、第五

4、行元素減去2，第一列元素加上2，得現(xiàn)在已可看出，最優(yōu)指派為。