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

1、精選課件1 指派問(wèn)題n指派問(wèn)題是一種特殊的整數(shù)規(guī)劃問(wèn)題一、問(wèn)題的提出一、問(wèn)題的提出 設(shè)有m個(gè)工人，能做n件事，但效率不同，并規(guī)定每個(gè)工人做且只能做一件事，每件事有且只能有一個(gè)工人做，問(wèn)應(yīng)該如何安排他們的工作，使花費(fèi)的總時(shí)間（成本）最少或效率最高？精選課件2二、指派問(wèn)題的數(shù)學(xué)模型n設(shè)第i個(gè)工人做第j件事的時(shí)間是 ，決策變量是n則數(shù)學(xué)模型如下件事個(gè)工人不做第第，件事個(gè)工人做第第jijixij0, 1ijc精選課件3njmixnjxmixxczijmiijnjijnjmiijij, 2 , 1;, 2 , 1; 1 , 0, 2 , 1, 1, 2 , 1, 1min1111精選課件4舉例說(shuō)明1）表

2、上作業(yè)法2）匈牙利法n例 有四個(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精選課件5獲得初始解：圈零/劃零操作n將時(shí)間矩陣C的每一行都減去相應(yīng)行的最小元素和每一列都減去相應(yīng)列的最小元素，使每一行和每一列都含有零；n從最少零數(shù)的行或列開(kāi)始，將“零”圈起來(lái)，并劃去它所在行和所在列的其它零；n反復(fù)做2），直到所有零被圈起或被劃掉為止。得到初始解。n判斷是否為最優(yōu)解：圈起的零的個(gè)數(shù)是否等于n。 精選課件6確定調(diào)整行和列n在沒(méi)

3、有圈起的零所在行上打“”；n在打“”行中所有零所在的列打“”；n在打“”列中含有圈起零的行上打“”，n反復(fù)執(zhí)行2）和3）兩步，直到不能打“”為止；n用直線(xiàn)劃去打用直線(xiàn)劃去打“”的列和不打的列和不打“”的行的行，沒(méi)有劃去的行構(gòu)成調(diào)整的行，劃去的列構(gòu)成調(diào)整列。精選課件7調(diào)整可行解的方法n在調(diào)整行中尋找最小的元素，將它作為調(diào)整量；n將調(diào)整行各元素減去調(diào)整量，對(duì)調(diào)整列中各元素加上調(diào)整量。n再次執(zhí)行“圈零”和“劃零”的操作，并循環(huán)以上的步驟，直到圈起的零數(shù)等于n為止。精選課件8匈牙利法解例3.3n時(shí)間矩陣n各行各列減去最小元素后得9137411161413814415731025830043249011

4、5080精選課件9圈零劃零58300432490115080精選課件10得最優(yōu)解n將圈起的零改為1，其它元素改為0，即得最優(yōu)解如下n最小總時(shí)間為22。0001100000100100)ijx（精選課件11再看一例n請(qǐng)求解如下矩陣表達(dá)的指派問(wèn)題 9107104106614159141217766698979712精選課件12減去最小元素563601000892751000003220205精選課件13圈零劃零563601000892751000003220205精選課件14打勾劃線(xiàn)確定調(diào)整行和列563601000892751000003220205精選課件15調(diào)整可行解3414010008110

5、53800003420207精選課件16再圈零劃零341401000811053800003420207精選課件17得最優(yōu)解0000101000100000010000010)(ijx精選課件18另一最優(yōu)解n最小時(shí)間（成本）min z=32 0000100100100000100000010)(ijx精選課件19匈牙利算法示例精選課件20 （二）、解題步驟：（二）、解題步驟： 指派問(wèn)題是指派問(wèn)題是0-1 規(guī)劃的特例，也是運(yùn)輸問(wèn)題的特例，規(guī)劃的特例，也是運(yùn)輸問(wèn)題的特例，當(dāng)然可用整數(shù)規(guī)劃，當(dāng)然可用整數(shù)規(guī)劃，0-1 規(guī)劃或運(yùn)輸問(wèn)題的解法去求規(guī)劃或運(yùn)輸問(wèn)題的解法去求解，這就如同用單純型法求解運(yùn)輸問(wèn)題一

6、樣是不合算解，這就如同用單純型法求解運(yùn)輸問(wèn)題一樣是不合算的。利用指派問(wèn)題的特點(diǎn)可有更簡(jiǎn)便的解法，這就是的。利用指派問(wèn)題的特點(diǎn)可有更簡(jiǎn)便的解法，這就是匈牙利法，即匈牙利法，即系數(shù)矩陣中獨(dú)立系數(shù)矩陣中獨(dú)立 0 0 元素的最多個(gè)數(shù)等于元素的最多個(gè)數(shù)等于能覆蓋所有能覆蓋所有 0 0 元素的最少直線(xiàn)數(shù)。元素的最少直線(xiàn)數(shù)。 第一步：變換指派問(wèn)題的系數(shù)矩陣（第一步：變換指派問(wèn)題的系數(shù)矩陣（cij）為）為(bij)，使，使在在(bij)的各行各列中都出現(xiàn)的各行各列中都出現(xiàn)0元素，即元素，即 (1) 從（從（cij）的每行元素都減去該行的最小元素；）的每行元素都減去該行的最小元素； (2) 再?gòu)乃眯孪禂?shù)矩陣的

7、每列元素中減去該列的最再?gòu)乃眯孪禂?shù)矩陣的每列元素中減去該列的最小元素。小元素。精選課件21 第二步：進(jìn)行試指派，以尋求最優(yōu)解。第二步：進(jìn)行試指派，以尋求最優(yōu)解。 在在(bij)中找盡可能多的獨(dú)立中找盡可能多的獨(dú)立0元素，若能找出元素，若能找出n個(gè)獨(dú)個(gè)獨(dú)立立0元素，就以這元素，就以這n個(gè)獨(dú)立個(gè)獨(dú)立0元素對(duì)應(yīng)解矩陣元素對(duì)應(yīng)解矩陣(xij)中的元中的元素為素為1，其余為，其余為0，這就得到最優(yōu)解。找獨(dú)立，這就得到最優(yōu)解。找獨(dú)立0元素，常元素，常用的步驟為：用的步驟為： (1)從只有一個(gè)從只有一個(gè)0元素的行元素的行(列列)開(kāi)始，給這個(gè)開(kāi)始，給這個(gè)0元素加元素加圈，記作圈，記作 。然后劃去。然后劃去

8、所在列所在列(行行)的其它的其它0元素，記元素，記作作 ；這表示這列所代表的任務(wù)已指派完，不必再考；這表示這列所代表的任務(wù)已指派完，不必再考慮別人了。慮別人了。 (2)給只有一個(gè)給只有一個(gè)0元素的列元素的列(行行)中的中的0元素加圈，記作元素加圈，記作；然后劃去；然后劃去 所在行的所在行的0元素，記作元素，記作 (3)反復(fù)進(jìn)行反復(fù)進(jìn)行(1)，(2)兩步，直到盡可能多的兩步，直到盡可能多的0元素都元素都被圈出和劃掉為止。被圈出和劃掉為止。精選課件22 (4)若仍有沒(méi)有劃圈的若仍有沒(méi)有劃圈的0元素，且同行元素，且同行(列列)的的0元素至元素至少有兩個(gè)，則從剩有少有兩個(gè)，則從剩有0元素最少的行元素最

9、少的行(列列)開(kāi)始，比較這開(kāi)始，比較這行各行各0元素所在列中元素所在列中0元素的數(shù)目，選擇元素的數(shù)目，選擇0元素少的那列元素少的那列的這個(gè)的這個(gè)0元素加圈元素加圈(表示選擇性多的要表示選擇性多的要“禮讓禮讓”選擇性選擇性少的少的)。然后劃掉同行同列的其它。然后劃掉同行同列的其它0元素?？煞磸?fù)進(jìn)行，元素。可反復(fù)進(jìn)行，直到所有直到所有0元素都已圈出和劃掉為止。元素都已圈出和劃掉為止。 （5）若）若 元素的數(shù)目元素的數(shù)目m 等于矩陣的階數(shù)等于矩陣的階數(shù)n，那么這指，那么這指派問(wèn)題的最優(yōu)解已得到。若派問(wèn)題的最優(yōu)解已得到。若m n, 則轉(zhuǎn)入下一步。則轉(zhuǎn)入下一步。 第三步：作最少的直線(xiàn)覆蓋所有第三步：作最

10、少的直線(xiàn)覆蓋所有0元素。元素。 (1)對(duì)沒(méi)有對(duì)沒(méi)有的行打的行打號(hào)；號(hào)； (2)對(duì)已打?qū)σ汛蛱?hào)的行中所有含號(hào)的行中所有含元素的列打元素的列打號(hào)；號(hào)； (3)再對(duì)打有再對(duì)打有號(hào)的列中含號(hào)的列中含 元素的行打元素的行打號(hào)；號(hào)； 精選課件23 (4)重復(fù)重復(fù)(2)，(3)直到得不出新的打直到得不出新的打號(hào)的行、列為止；號(hào)的行、列為止； (5)對(duì)沒(méi)有打?qū)](méi)有打號(hào)的行畫(huà)橫線(xiàn)，有打號(hào)的行畫(huà)橫線(xiàn)，有打號(hào)的列畫(huà)縱線(xiàn)，號(hào)的列畫(huà)縱線(xiàn)，這就得到覆蓋所有這就得到覆蓋所有0元素的最少直線(xiàn)數(shù)元素的最少直線(xiàn)數(shù) l 。l 應(yīng)等于應(yīng)等于m，若不相等，說(shuō)明試指派過(guò)程有誤，回到第二步若不相等，說(shuō)明試指派過(guò)程有誤，回到第二步(4)，另

11、，另行試指派；若行試指派；若 lm n，須再變換當(dāng)前的系數(shù)矩陣，須再變換當(dāng)前的系數(shù)矩陣，以找到以找到n個(gè)獨(dú)立的個(gè)獨(dú)立的0元素，為此轉(zhuǎn)第四步。元素，為此轉(zhuǎn)第四步。第四步：變換矩陣第四步：變換矩陣(bij)以增加以增加0元素。元素。在沒(méi)有被直線(xiàn)覆蓋的所有元素中找出最小元素，然后在沒(méi)有被直線(xiàn)覆蓋的所有元素中找出最小元素，然后打打各行都減去這最小元素；打各行都減去這最小元素；打各列都加上這最小元各列都加上這最小元素（以保證系數(shù)矩陣中不出現(xiàn)負(fù)元素）。新系數(shù)矩陣素（以保證系數(shù)矩陣中不出現(xiàn)負(fù)元素）。新系數(shù)矩陣的最優(yōu)解和原問(wèn)題仍相同。轉(zhuǎn)回第二步。的最優(yōu)解和原問(wèn)題仍相同。轉(zhuǎn)回第二步。 精選課件24例一：例一：

12、任務(wù)任務(wù)人員人員ABCD甲甲215134乙乙1041415丙丙9141613丁丁78119精選課件25 9118713161491514410413152 241047501110062111302497精選課件26 00102350960607130 2410475011100621113042精選課件27 00102350960607130 0100000100101000精選課件28 有一份中文說(shuō)明書(shū)，需譯成英、日、德、俄四種有一份中文說(shuō)明書(shū)，需譯成英、日、德、俄四種文字，分別記作文字，分別記作A、B、C、D。現(xiàn)有甲、乙、丙、丁四?，F(xiàn)有甲、乙、丙、丁四人，他們將中文說(shuō)明書(shū)譯成不同語(yǔ)種的說(shuō)

13、明書(shū)所需時(shí)人，他們將中文說(shuō)明書(shū)譯成不同語(yǔ)種的說(shuō)明書(shū)所需時(shí)間如下表所示，問(wèn)如何分派任務(wù)，可使總時(shí)間最少？間如下表所示，問(wèn)如何分派任務(wù)，可使總時(shí)間最少？ 任務(wù)任務(wù)人員人員ABCD甲甲67112乙乙4598丙丙31104丁丁5982例二、例二、精選課件29求解過(guò)程如下：求解過(guò)程如下：第一步，變換系數(shù)矩陣：第一步，變換系數(shù)矩陣：2142 289541013895421176)( ijc 0673390245100954 01733402401004545第二步，試指派：第二步，試指派：找到找到 3 3 個(gè)獨(dú)立零元素個(gè)獨(dú)立零元素 但但 m m = 3 3 n = 4精選課件30

14、 第三步，作最少的直線(xiàn)覆蓋所有第三步，作最少的直線(xiàn)覆蓋所有0 0元素：元素：立零元素的個(gè)數(shù)獨(dú)立零元素的個(gè)數(shù)m等于最少直線(xiàn)數(shù)等于最少直線(xiàn)數(shù)l，即，即lm=3n=4； 第四步，變換矩陣第四步，變換矩陣( (bij) )以增加以增加0 0元素：沒(méi)有被直線(xiàn)元素：沒(méi)有被直線(xiàn)覆蓋的所有元素中的最小元素為覆蓋的所有元素中的最小元素為1 1，然后打，然后打各行都減各行都減去去1 1；打；打各列都加上各列都加上1 1，得如下矩陣，并轉(zhuǎn)第二步進(jìn)，得如下矩陣，并轉(zhuǎn)第二步進(jìn)行試指派：行試指派： 精選課件31 6244251343000 0 00 0100001000011000得到得到4 4

15、個(gè)獨(dú)個(gè)獨(dú)立零元素，立零元素， 所以最優(yōu)解所以最優(yōu)解矩陣為：矩陣為：0624425134315 6244251343精選課件32練習(xí)：練習(xí)：115764戊戊69637丁丁86458丙丙9117129乙乙118957甲甲EDCBA費(fèi)費(fèi) 工作工作 用用人員人員精選課件334347511576469637964589117129118957 7132036304520142405263402-1 -2精選課件34 5032015304310140305242402 5032015304310140305242402精選課件35 5032015304310140305242402l =m=4 n=5精選課件36 5032015304310140305242402 5033004203310240306231301精選課件37 5033004203310240306231301 5033004203310240306231301精選課件38 5033004203310240306231301l =m=4 n=5精選課件39 5033004203310240306231301 6044003202300230206130300精選課件40 6044003202300230206130300 60440032023002302061303