指派問(wèn)題的匈牙利法ppt

指派問(wèn)題的匈牙利法二、指派問(wèn)題得數(shù)學(xué)模型設(shè)第i個(gè)工人做第j件事得時(shí)間就是,決策變量就是則數(shù)學(xué)模型如下舉例說(shuō)明

1)表上作業(yè)法

2)匈牙利法例有四個(gè)工人與四臺(tái)不同得機(jī)床,每位工人在不同得機(jī)床上完成給定得任務(wù)得工時(shí)如表5、12所示,問(wèn)安排哪位工人操作哪一臺(tái)機(jī)床可使總工時(shí)最少？任務(wù)1任務(wù)2任務(wù)3任務(wù)4工人1工人2工人3工人4215134104147314161378119獲得初始解:圈零/劃零操作將時(shí)間矩陣C得每一行都減去相應(yīng)行得最小元素與每一列都減去相應(yīng)列得最小元素,使每一行與每一列都含有零;從最少零數(shù)得行或列開(kāi)始,將“零”圈起來(lái),并劃去它所在行與所在列得其它零;反復(fù)做2),直到所有零被圈起或被劃掉為止。得到初始解。判斷就是否為最優(yōu)解:圈起得零得個(gè)數(shù)就是否等于n。確定調(diào)整行與列在沒(méi)有圈起得零所在行上打“√”;在打“√”行中所有零所在得列打“√”;在打“√”列中含有圈起零得行上打“√”,反復(fù)執(zhí)行2)與3)兩步,直到不能打“√”為止;用直線(xiàn)劃去打“√”得列與不打“√”得行,沒(méi)有劃去得行構(gòu)成調(diào)整得行,劃去得列構(gòu)成調(diào)整列。調(diào)整可行解得方法在調(diào)整行中尋找最小得元素,將它作為調(diào)整量;將調(diào)整行各元素減去調(diào)整量,對(duì)調(diào)整列中各元素加上調(diào)整量。再次執(zhí)行“圈零”與“劃零”得操作,并循環(huán)以上得步驟,直到圈起得零數(shù)等于n為止。匈牙利法解例3、3時(shí)間矩陣各行各列減去最小元素后得圈零劃零10大家應(yīng)該也有點(diǎn)累了,稍作休息大家有疑問(wèn)得,可以詢(xún)問(wèn)與交流得最優(yōu)解將圈起得零改為1,其它元素改為0,即得最優(yōu)解如下最小總時(shí)間為22。再瞧一例請(qǐng)求解如下矩陣表達(dá)得指派問(wèn)題減去最小元素圈零劃零打勾劃線(xiàn)確定調(diào)整行與列√√√調(diào)整可行解再圈零劃零得最優(yōu)解另一最優(yōu)解最小時(shí)間(成本)minz=32匈牙利算法示例(二)、解題步驟:指派問(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元素得最少直線(xiàn)數(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)入下一步。

第三步:作最少得直線(xià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à)橫線(xiàn),有打√號(hào)得列畫(huà)縱線(xiàn),這就得到覆蓋所有0元素得最少直線(xiàn)數(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)有被直線(xiàn)覆蓋得所有元素中找出最小元素,然后打√各行都減去這最小元素;打√各列都加上這最小元素(以保證系數(shù)矩陣中不出現(xiàn)負(fù)元素)。新系數(shù)矩陣得最優(yōu)解與原問(wèn)題仍相同。轉(zhuǎn)回第二步。例一:

任務(wù)人員ABCD甲215134乙1041415丙9141613丁78119249742◎?◎??◎◎有一份中文說(shuō)明書(shū),需譯成英、日、德、俄四種文字,分別記作A、B、C、D?，F(xiàn)有甲、乙、丙、丁四人,她們將中文說(shuō)明書(shū)譯成不同語(yǔ)種得說(shuō)明書(shū)所需時(shí)間如下表所示,問(wèn)如何分派任務(wù),可使總時(shí)間最少？

任務(wù)人員ABCD甲67112乙4598丙31104丁5982例二、求解過(guò)程如下:第一步,變換系數(shù)矩陣:－5第二步,試指派:◎◎◎??找到3個(gè)獨(dú)立零元素但m=3<n=

4第三步,作最少得直線(xiàn)覆蓋所有0元素:

◎◎◎??√√√獨(dú)立零元素得個(gè)數(shù)m等于最少直線(xiàn)數(shù)l,即l＝m=3<n=4;第四步,變換矩陣(bij)以增加0元素:沒(méi)有被直線(xiàn)覆蓋得所有元素中得最小元素為1,然后打√各行都減去1;打√各列都加上1,得如下矩陣,并轉(zhuǎn)第二步進(jìn)行試指派:000000得到4個(gè)獨(dú)立零元素,所以最優(yōu)解矩陣為:◎◎◎??√√√◎◎◎??15◎◎◎??◎練習(xí):115764戊69637丁86458丙9117129乙118957甲EDCBA費(fèi)工作用人員-1-2◎?◎◎◎??◎?◎◎◎??√√√l=m=4<n=5◎?◎◎◎??◎?◎?◎?◎?√√√√√√√◎?◎