當(dāng)前位置：信管網(wǎng) >> 信息系統(tǒng)項(xiàng)目管理師 >> 綜合知識(shí)
>> 文章內(nèi)容
運(yùn)籌學(xué)中匈牙利算法解題步驟
分享到微信
解題步驟：
指派問(wèn)題是0-1 規(guī)劃的特例，也是運(yùn)輸問(wèn)題的特例，當(dāng)然可用整數(shù)規(guī)劃，0-1 規(guī)劃或運(yùn)輸問(wèn)題的解法去求解，這就如同用單純型法求解運(yùn)輸問(wèn)題一樣是不合算的。利用指派問(wèn)題的特點(diǎn)可有更簡(jiǎn)便的解法，這就是匈牙利法，即系數(shù)矩陣中獨(dú)立 0 元素的最多個(gè)數(shù)等于能覆蓋所有 0 元素的最少直線數(shù)。
第一步：變換指派問(wèn)題的系數(shù)矩陣（cij）為(bij)，使在(bij)的各行各列中都出現(xiàn)0元素，即
(1) 從（cij）的每行元素都減去該行的最小元素；
(2) 再?gòu)乃眯孪禂?shù)矩陣的每列元素中減去該列的最小元素。
第二步：進(jìn)行試指派，以尋求最優(yōu)解。
在(bij)中找盡可能多的獨(dú)立0元素，若能找出n個(gè)獨(dú)立0元素，就以這n個(gè)獨(dú)立0元素對(duì)應(yīng)解矩陣(xij)中的元素為1，其余為0，這就得到最優(yōu)解。找獨(dú)立0元素，常用的步驟為：
(1)從只有一個(gè)0元素的行(列)開(kāi)始，給這個(gè)0元素加圈，記作◎ 。然后劃去◎ 所在列(行)的其它0元素，記作Ø ；這表示這列所代表的任務(wù)已指派完，不必再考慮別人了。
(2)給只有一個(gè)0元素的列(行)中的0元素加圈，記作◎；然后劃去◎ 所在行的0元素，記作Ø ．
(3)反復(fù)進(jìn)行(1)，(2)兩步，直到盡可能多的0元素都被圈出和劃掉為止。
(4)若仍有沒(méi)有劃圈的0元素，且同行(列)的0元素至少有兩個(gè)，則從剩有0元素最少的行(列)開(kāi)始，比較這行各0元素所在列中0元素的數(shù)目，選擇0元素少的那列的這個(gè)0元素加圈(表示選擇性多的要“禮讓”選擇性少的)。然后劃掉同行同列的其它0元素?？煞磸?fù)進(jìn)行，直到所有0元素都已圈出和劃掉為止。
(5)若◎ 元素的數(shù)目m 等于矩陣的階數(shù)n，那么這指派問(wèn)題的最優(yōu)解已得到。若m < n, 則轉(zhuǎn)入下一步。
第三步：作最少的直線覆蓋所有0元素。
(1)對(duì)沒(méi)有◎的行打√號(hào)；
(2)對(duì)已打√號(hào)的行中所有含Ø元素的列打√號(hào)；
(3)再對(duì)打有√號(hào)的列中含◎ 元素的行打√號(hào)；
(4)重復(fù)(2)，(3)直到得不出新的打√號(hào)的行、列為止；
(5)對(duì)沒(méi)有打√號(hào)的行畫(huà)橫線，有打√號(hào)的列畫(huà)縱線，這就得到覆蓋所有0元素的最少直線數(shù) l 。l 應(yīng)等于m，若不相等，說(shuō)明試指派過(guò)程有誤，回到第二步(4)，另行試指派；若 l＝m < n，須再變換當(dāng)前的系數(shù)矩陣，以找到n個(gè)獨(dú)立的0元素，為此轉(zhuǎn)第四步。
第四步：變換矩陣(bij)以增加0元素。
在沒(méi)有被直線覆蓋的所有元素中找出最小元素，然后打√各行都減去這最小元素；打√各列都加上這最小元素（以保證系數(shù)矩陣中不出現(xiàn)負(fù)元素）。新系數(shù)矩陣的最優(yōu)解和原問(wèn)題仍相同。轉(zhuǎn)回第二步。
掃碼關(guān)注公眾號(hào)
溫馨提示：因考試政策、內(nèi)容不斷變化與調(diào)整，信管網(wǎng)網(wǎng)站提供的以上信息僅供參考，如有異議，請(qǐng)以權(quán)威部門公布的內(nèi)容為準(zhǔn)！
信管網(wǎng)致力于為廣大信管從業(yè)人員、愛(ài)好者、大學(xué)生提供專業(yè)、高質(zhì)量的課程和服務(wù)，解決其考試證書(shū)、技能提升和就業(yè)的需求。
信管網(wǎng)軟考課程由信管網(wǎng)依托10年專業(yè)軟考教研傾力打造，官方教材參編作者和資深講師坐鎮(zhèn)，通過(guò)深研歷年考試出題規(guī)律與考試大綱，深挖核心知識(shí)與高頻考點(diǎn)，為學(xué)員考試保駕護(hù)航。面授、直播＆錄播，多種班型靈活學(xué)習(xí)，滿足不同學(xué)員考證需求，降低課程學(xué)習(xí)難度，使學(xué)習(xí)效果事半功倍。
相關(guān)內(nèi)容
| 發(fā)表評(píng)論 查看完整評(píng)論 | |
考試新手指南
學(xué)習(xí)計(jì)劃攻略
精華備考資料
案例論文干貨
章節(jié)模擬試題
免費(fèi)試聽(tīng)課程
考試信息推送