第五講分配問(wèn)題指派問(wèn)題與匈牙利法

1、1第第5 5講講 分配問(wèn)題（指派問(wèn)題）與匈牙利法分配問(wèn)題（指派問(wèn)題）與匈牙利法2分配問(wèn)題的提出3分配問(wèn)題的提出分配問(wèn)題的提出若干項(xiàng)若干項(xiàng)工作或任務(wù)工作或任務(wù)需要若需要若干個(gè)人干個(gè)人去完成。由于每人的知識(shí)、去完成。由于每人的知識(shí)、能力、經(jīng)驗(yàn)的不同，故各人完成不同任務(wù)所需要的時(shí)間不同能力、經(jīng)驗(yàn)的不同，故各人完成不同任務(wù)所需要的時(shí)間不同（或其他資源）。（或其他資源）。問(wèn)：?jiǎn)枺?應(yīng)指派哪個(gè)人完成何項(xiàng)工作，可使完成所有工作所應(yīng)指派哪個(gè)人完成何項(xiàng)工作，可使完成所有工作所消消耗的總資源最少耗的總資源最少？4分配問(wèn)題的提出分配問(wèn)題的提出設(shè)某公司準(zhǔn)備派設(shè)某公司準(zhǔn)備派 n n 個(gè)工人個(gè)工人x x1 1，x x2

2、2，x xn n ，去作去作 n n 件工作件工作 y y1 1，y y2 2，y yn n。已知工人已知工人x xi i完成工作完成工作 y yj j 所需所需時(shí)間為時(shí)間為c cij ij ( (i i, ,j j=1,2,=1,2,n n) )。現(xiàn)問(wèn)：如何確定一個(gè)分派工人去工作的方案，使現(xiàn)問(wèn)：如何確定一個(gè)分派工人去工作的方案，使得工人們完成工作的得工人們完成工作的總時(shí)間為最少?？倳r(shí)間為最少。臺(tái)臺(tái)機(jī)機(jī)床床加加工工項(xiàng)項(xiàng)任任務(wù)務(wù)；條條航航線(xiàn)線(xiàn)有有艘艘船船去去航航行行等等。n n n n 還比如：還比如：5整體解題思路總結(jié)整體解題思路總結(jié)例題：例題：工作者工作者1工作者工作者2工作者工作者3工作者

3、工作者4工作者工作者5工作工作14871512工作工作279171410工作工作3691287工作工作46714610工作工作56912106單位：小時(shí)單位：小時(shí)6標(biāo)準(zhǔn)形式的分配問(wèn)題7標(biāo)準(zhǔn)形式的分配問(wèn)題標(biāo)準(zhǔn)形式的分配問(wèn)題分派方案滿(mǎn)足下述兩個(gè)條件：分派方案滿(mǎn)足下述兩個(gè)條件： 任一個(gè)工人都不能去做兩件或兩件以上的工作任一個(gè)工人都不能去做兩件或兩件以上的工作1.1.任一件工作都不能同時(shí)接受兩個(gè)及以上的工人去做任一件工作都不能同時(shí)接受兩個(gè)及以上的工人去做設(shè)某公司準(zhǔn)備派設(shè)某公司準(zhǔn)備派 n n 個(gè)工人個(gè)工人x x1 1，x x2 2，x xn n ，去作去作 n n 件工作件工作 y y1 1，y y2

4、2，y yn n。已知工人已知工人x xi i完成工作完成工作 y yj j 所需時(shí)間為所需時(shí)間為c cij ij ( (i i, ,j j=1,2,=1,2,n n) )?，F(xiàn)問(wèn)：如何確定一個(gè)分派工人去工作的方案，使得工人們現(xiàn)問(wèn)：如何確定一個(gè)分派工人去工作的方案，使得工人們完成工作的完成工作的總時(shí)間為最少?？倳r(shí)間為最少。8標(biāo)準(zhǔn)形式的分配問(wèn)題標(biāo)準(zhǔn)形式的分配問(wèn)題nn事事人人9數(shù)學(xué)模型數(shù)學(xué)模型nncij：第第i人做第人做第j事的費(fèi)用事的費(fèi)用xij1 若指派第若指派第i人做第人做第j事事0 若指派第若指派第i人不做第人不做第j事事總費(fèi)用總費(fèi)用：11nnijijijc xi，j1, ., nj1,.,n

5、i1,.,nniijx11njijx11事事人人時(shí)間、原料、時(shí)間、原料、金錢(qián)等資源金錢(qián)等資源10數(shù)學(xué)模型數(shù)學(xué)模型ninjijijxcz11minniijx11njijx11j1,.,ni1,.,n,.,n,i,jxij21 10 或s.t.線(xiàn)性規(guī)劃問(wèn)題線(xiàn)性規(guī)劃問(wèn)題運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題0-1型整數(shù)規(guī)劃問(wèn)題型整數(shù)規(guī)劃問(wèn)題11匈牙利匈牙利法法 1955 1955年由美國(guó)數(shù)學(xué)家年由美國(guó)數(shù)學(xué)家W.W.kuhn(W.W.kuhn(庫(kù)恩庫(kù)恩) )提出，利用了提出，利用了匈牙利數(shù)學(xué)家匈牙利數(shù)學(xué)家D.Konig(D.Konig(康尼格康尼格) )證明的證明的2 2個(gè)定理。個(gè)定理。nnnnnncccccccccC.1

6、12222111211nnnnnnxxxxxxxxxX.112222111211系數(shù)矩陣系數(shù)矩陣(效率矩陣效率矩陣)解矩陣解矩陣(決策變量矩決策變量矩陣陣)nn12定義定義：在系數(shù)矩陣在系數(shù)矩陣C中，中，處在不同行不同列處在不同行不同列的一的一組零元素，稱(chēng)為組零元素，稱(chēng)為獨(dú)立零元素組獨(dú)立零元素組，其中每個(gè)元素，其中每個(gè)元素稱(chēng)為稱(chēng)為獨(dú)立零元素獨(dú)立零元素。0084765000320205C4431321243312412,cccccccc44313241,cccc0100000110000010Xninjijijxcz11min最優(yōu)解最優(yōu)解13014丙丙085乙乙210甲甲CBA時(shí)時(shí) 工作工作 間

7、間 人員人員004丙丙075乙乙200甲甲CBA時(shí)時(shí) 工作工作 間間 人員人員458丙丙4129乙乙987甲甲CBA時(shí)時(shí) 工作工作 間間 人員人員定理：定理：若若將分配問(wèn)題系數(shù)矩陣的將分配問(wèn)題系數(shù)矩陣的每一行每一行及及每一列每一列分別分別減去減去各行及各列的各行及各列的最小元素最小元素，則則新分配問(wèn)題與原分配新分配問(wèn)題與原分配問(wèn)題有問(wèn)題有相同的最優(yōu)解相同的最優(yōu)解，只有最優(yōu)值差一常數(shù)。，只有最優(yōu)值差一常數(shù)。相關(guān)定理相關(guān)定理使每行每列使每行每列都出現(xiàn)零元素都出現(xiàn)零元素步驟步驟1：變換系數(shù)矩陣，使其每行每列都出現(xiàn)變換系數(shù)矩陣，使其每行每列都出現(xiàn)0元素元素 把各把各行行元素分別減去本行元素的最小值，然

8、后元素分別減去本行元素的最小值，然后在此基礎(chǔ)上在此基礎(chǔ)上再把每再把每列列元素減去本列中的最小值。元素減去本列中的最小值。6 10 12 9 610 6 14 7 67 8 12 9 610 14 17 9 712 15 7 8 40 4 3 2 04 0 5 0 01 2 3 2 03 7 7 1 08 11 0 3 00 4 6 3 04 0 8 1 01 2 6 3 03 7 01 2 08 11 3 4 066674min00310min此時(shí)每行及每列中肯定都有此時(shí)每行及每列中肯定都有0元素元素步驟步驟2：進(jìn)行試分配，判斷是否存在進(jìn)行試分配，判斷是否存在n個(gè)獨(dú)立零元素個(gè)獨(dú)立零元素 嘗試對(duì)

9、所有零元素做嘗試對(duì)所有零元素做標(biāo)記標(biāo)記，確定確定獨(dú)立零元素獨(dú)立零元素。（1）逐）逐行行檢驗(yàn)檢驗(yàn)對(duì)對(duì)只有一個(gè)只有一個(gè)的零元素的的零元素的行行，用，用記號(hào)記號(hào)O將該零元素圈起，然后將該零元素圈起，然后將將被圈起的零元素所在列被圈起的零元素所在列的其他的其他未標(biāo)記的零元素未標(biāo)記的零元素用用記號(hào)記號(hào)/劃去。劃去。01370606905320100重復(fù)行檢驗(yàn)，直到重復(fù)行檢驗(yàn)，直到每一行都沒(méi)有未被標(biāo)記每一行都沒(méi)有未被標(biāo)記的零元素的零元素或或至少有兩個(gè)未至少有兩個(gè)未被標(biāo)記被標(biāo)記的零元素為止。的零元素為止。表示此人只能做該事表示此人只能做該事（此事只能由該人做）（此事只能由該人做）表示此事已不能由表示此事已不

10、能由其他人來(lái)做其他人來(lái)做（此人已不能做其他事）（此人已不能做其他事）1604320405001232037710811030圈圈0即獨(dú)立零元素即獨(dú)立零元素步驟步驟2：進(jìn)行試分配，判斷是否存在進(jìn)行試分配，判斷是否存在n個(gè)獨(dú)立零元素個(gè)獨(dú)立零元素 嘗試對(duì)所有零元素做嘗試對(duì)所有零元素做標(biāo)記標(biāo)記，確定確定獨(dú)立零元素獨(dú)立零元素。（2）逐）逐行行檢驗(yàn)檢驗(yàn)17步驟步驟2：進(jìn)行試分配，判斷是否存在進(jìn)行試分配，判斷是否存在n個(gè)獨(dú)立零元素個(gè)獨(dú)立零元素 嘗試對(duì)所有零元素做嘗試對(duì)所有零元素做標(biāo)記標(biāo)記，確定確定獨(dú)立零元素獨(dú)立零元素。（2）逐）逐列列檢驗(yàn)檢驗(yàn)與行檢驗(yàn)類(lèi)似：與行檢驗(yàn)類(lèi)似：對(duì)只有一個(gè)未標(biāo)記的零元素的對(duì)只有一個(gè)未

11、標(biāo)記的零元素的列列，用記號(hào)，用記號(hào)O將該將該零元素圈起，然后將被圈起的零元素所在零元素圈起，然后將被圈起的零元素所在行行的其他未標(biāo)記的零元的其他未標(biāo)記的零元素用記號(hào)素用記號(hào)/劃去。劃去。重復(fù)重復(fù)列列檢驗(yàn)，直到檢驗(yàn)，直到?jīng)]有未被標(biāo)記沒(méi)有未被標(biāo)記的零元素的零元素或或至少有兩個(gè)未被標(biāo)記至少有兩個(gè)未被標(biāo)記的零元素為止。的零元素為止。013706069053201001804320405001232037710811030圈圈0即獨(dú)立零元素即獨(dú)立零元素步驟步驟2：進(jìn)行試分配，判斷是否存在進(jìn)行試分配，判斷是否存在n個(gè)獨(dú)立零元素個(gè)獨(dú)立零元素 嘗試對(duì)所有零元素做嘗試對(duì)所有零元素做標(biāo)記標(biāo)記，確定確定獨(dú)立零元素獨(dú)

12、立零元素。（2）逐）逐列列檢驗(yàn)檢驗(yàn)可能出現(xiàn)三種情況可能出現(xiàn)三種情況1.每一行均有圈每一行均有圈0出現(xiàn)，圈出現(xiàn)，圈0的個(gè)數(shù)恰好等于的個(gè)數(shù)恰好等于n2.存在未標(biāo)記過(guò)的零元素，但它們所在的行和列中，未被標(biāo)存在未標(biāo)記過(guò)的零元素，但它們所在的行和列中，未被標(biāo)記過(guò)的零元素的個(gè)數(shù)均至少有兩個(gè)。記過(guò)的零元素的個(gè)數(shù)均至少有兩個(gè)。3.不存在未被標(biāo)記過(guò)的零元素，但圈不存在未被標(biāo)記過(guò)的零元素，但圈0的個(gè)數(shù)的個(gè)數(shù)n可進(jìn)行分配：令可進(jìn)行分配：令圈圈0位置的決策變量取值位置的決策變量取值為為1，其他為，其他為0（3）判斷）判斷獨(dú)立零元素獨(dú)立零元素的個(gè)數(shù)的個(gè)數(shù)013706069053201000001010010000010

13、20可能出現(xiàn)三種情況可能出現(xiàn)三種情況2.存在未標(biāo)記過(guò)的零元素，但它們所在的行和列中，未被標(biāo)存在未標(biāo)記過(guò)的零元素，但它們所在的行和列中，未被標(biāo)記過(guò)的零元素的個(gè)數(shù)均至少有兩個(gè)。記過(guò)的零元素的個(gè)數(shù)均至少有兩個(gè)。3.不存在未被標(biāo)記過(guò)的零元素，但圈不存在未被標(biāo)記過(guò)的零元素，但圈0的個(gè)數(shù)的個(gè)數(shù)n從某從某行行（列列）的）的兩個(gè)兩個(gè)未被標(biāo)記過(guò)的零元素中未被標(biāo)記過(guò)的零元素中任選一個(gè)任選一個(gè)加上加上圈圈，然后給然后給同同列列、同、同行行的其他未被標(biāo)記的零元素都加的其他未被標(biāo)記的零元素都加/，然后再，然后再進(jìn)行行、列檢驗(yàn)，可能出現(xiàn)情況進(jìn)行行、列檢驗(yàn)，可能出現(xiàn)情況1或或3。（3）判斷）判斷獨(dú)立零元素獨(dú)立零元素的個(gè)數(shù)的

14、個(gè)數(shù)502092300801057598004063600100000100100000001000001圈圈0個(gè)數(shù)個(gè)數(shù)等于等于n=5多重最優(yōu)解多重最優(yōu)解21可能出現(xiàn)三種情況可能出現(xiàn)三種情況3.不存在未被標(biāo)記過(guò)的零元素，但圈不存在未被標(biāo)記過(guò)的零元素，但圈0的個(gè)數(shù)的個(gè)數(shù)n（3）判斷）判斷獨(dú)立零元素獨(dú)立零元素的個(gè)數(shù)的個(gè)數(shù)圈圈0個(gè)數(shù)個(gè)數(shù)4 n=5作作最少直線(xiàn)覆蓋當(dāng)前所有零元素最少直線(xiàn)覆蓋當(dāng)前所有零元素，便，便于下步增加獨(dú)立零元素的個(gè)數(shù)。于下步增加獨(dú)立零元素的個(gè)數(shù)。0432040500123203771081103022定理：定理：系數(shù)矩陣系數(shù)矩陣C中中獨(dú)立零元素的最多個(gè)數(shù)獨(dú)立零元素的最多個(gè)數(shù)等于等于

15、能覆能覆蓋所有零元素的蓋所有零元素的最少線(xiàn)數(shù)最少線(xiàn)數(shù)。由匈牙利數(shù)學(xué)家由匈牙利數(shù)學(xué)家D.Konig(康尼格康尼格)所證明所證明502023000567480050202230000105729800406365例例：分別求下列矩陣中的獨(dú)立零元素的最多個(gè)數(shù)。：分別求下列矩陣中的獨(dú)立零元素的最多個(gè)數(shù)。44獨(dú)立零元素獨(dú)立零元素的個(gè)數(shù)最多：的個(gè)數(shù)最多：23 對(duì)對(duì)不含圈不含圈0的行打的行打； 在打在打的行中，對(duì)所有零元素所在的行中，對(duì)所有零元素所在列列打打； 在所有打在所有打的列中，對(duì)圈的列中，對(duì)圈0所在所在行行打打； 重復(fù)重復(fù)2,3步，直到不能步，直到不能打打?yàn)橹埂橹埂?對(duì)對(duì)未打未打的每一行的每一行畫(huà)

16、一橫線(xiàn)，對(duì)畫(huà)一橫線(xiàn)，對(duì)已打已打的每一列的每一列畫(huà)畫(huà)一縱線(xiàn)，即得到覆蓋當(dāng)前一縱線(xiàn)，即得到覆蓋當(dāng)前0元素的元素的最少直線(xiàn)最少直線(xiàn)集。集。0432040500123203771081103024找未被直線(xiàn)覆蓋的最小數(shù)字找未被直線(xiàn)覆蓋的最小數(shù)字k k；對(duì)矩陣的每行：當(dāng)該行對(duì)矩陣的每行：當(dāng)該行有直線(xiàn)覆蓋時(shí)有直線(xiàn)覆蓋時(shí)，令，令u ui i=0=0； 當(dāng)該行當(dāng)該行無(wú)直線(xiàn)覆蓋無(wú)直線(xiàn)覆蓋時(shí)時(shí)，令，令u ui i=k=k。04320405001232037710811030uiui0 01 11 10 00 0對(duì)矩陣的每列：當(dāng)該對(duì)矩陣的每列：當(dāng)該列列有直線(xiàn)覆蓋時(shí)有直線(xiàn)覆蓋時(shí)，令，令v vj j=-k=-k； 當(dāng)該

17、當(dāng)該列列無(wú)直線(xiàn)覆蓋無(wú)直線(xiàn)覆蓋時(shí)時(shí)，令，令v vj j=0=0。vjvj-1-10 00 00 00 02504320405001232037710811030uiui0 01 11 10 00 0vjvj-1-10 00 00 00 0 04320405000121026600811030從原矩陣的每個(gè)元素從原矩陣的每個(gè)元素aij 中分別減去中分別減去ui和和vj，得到新元，得到新元素素26再次尋找獨(dú)立零元素再次尋找獨(dú)立零元素 04320405000121026600811030逐逐列列檢驗(yàn)檢驗(yàn) 10000010000000100010001006 10 12 9 610 6 14 7 67

18、8 12 9 610 14 17 9 712 15 7 8 4原題：原題：分配方案分配方案A=7+9+6+6+6=3427再次尋找獨(dú)立零元素再次尋找獨(dú)立零元素 04320405000121026600811030逐逐列列檢驗(yàn)檢驗(yàn) 00001010001000000010001006 10 12 9 610 6 14 7 67 8 12 9 610 14 17 9 712 15 7 8 4分配方案分配方案B=7+9+7+6+6=3528 對(duì)對(duì)不含圈不含圈0的行打的行打； 在打在打的行中，對(duì)所有零元素所在的行中，對(duì)所有零元素所在列列打打； 在所有打在所有打的列中，對(duì)圈的列中，對(duì)圈0所在所在行行打打

19、； 重復(fù)重復(fù)2,3步，直到不能步，直到不能打打?yàn)橹?。為止?對(duì)對(duì)未打未打的每一行的每一行畫(huà)一橫線(xiàn)，對(duì)畫(huà)一橫線(xiàn)，對(duì)已打已打的每一列的每一列畫(huà)畫(huà)一縱線(xiàn)，即得到覆蓋當(dāng)前一縱線(xiàn)，即得到覆蓋當(dāng)前0元素的元素的最少直線(xiàn)最少直線(xiàn)集。集。5020223000010572980040636550202230000105729800406365圈圈0個(gè)數(shù)個(gè)數(shù)4 n=529找未被直線(xiàn)覆蓋的最小數(shù)字找未被直線(xiàn)覆蓋的最小數(shù)字k k；對(duì)矩陣的每行：當(dāng)該行對(duì)矩陣的每行：當(dāng)該行有直線(xiàn)覆蓋時(shí)有直線(xiàn)覆蓋時(shí)，令，令u ui i=0=0； 當(dāng)該行當(dāng)該行無(wú)直線(xiàn)覆蓋無(wú)直線(xiàn)覆蓋時(shí)時(shí)，令，令u ui i=k=k。uiui0 00 02 20

20、 02 2對(duì)矩陣的每列：當(dāng)該對(duì)矩陣的每列：當(dāng)該列列有直線(xiàn)覆蓋時(shí)有直線(xiàn)覆蓋時(shí)，令，令v vj j=-k=-k； 當(dāng)該當(dāng)該列列無(wú)直線(xiàn)覆蓋無(wú)直線(xiàn)覆蓋時(shí)時(shí)，令，令v vj j=0=0。vjvj-2-20 00 00 00 05020223000010572980040636530 3414040089053800003220205從原矩陣的每個(gè)元素從原矩陣的每個(gè)元素aij 中分別減去中分別減去ui和和vj，得到新元，得到新元素素uiui0 00 02 20 02 2vjvj-2-20 00 00 00 05020223000010572980040636531 34140400890538000032

21、20205再次尋找獨(dú)立零元素再次尋找獨(dú)立零元素分配方案分配方案B 000010010010000010000001032 3414040089053800003220205再次尋找獨(dú)立零元素再次尋找獨(dú)立零元素分配方案分配方案B 000010100010000001000001033整體解題思路總結(jié)整體解題思路總結(jié)34整體解題思路總結(jié)整體解題思路總結(jié)例題：例題：人人1人人2人人3人人4人人5工作工作14871512工作工作279171410工作工作3691287工作工作46714610工作工作56912106單位：小時(shí)單位：小時(shí)35整體解題思路總結(jié)整體解題思路總結(jié)6 10 12 9 610 6

22、14 7 67 8 12 9 610 14 17 9 712 15 7 8 4例題：例題：36步驟步驟1：變換系數(shù)矩陣，使其每行每列都出現(xiàn)變換系數(shù)矩陣，使其每行每列都出現(xiàn)0元素元素 把各把各行行元素分別減去本行元素的最小值，然后元素分別減去本行元素的最小值，然后在此基礎(chǔ)上在此基礎(chǔ)上再把每再把每列列元素減去本列中的最小值。元素減去本列中的最小值。6 10 12 9 610 6 14 7 67 8 12 9 610 14 17 9 712 15 7 8 40 4 3 2 04 0 5 0 01 2 3 2 03 7 7 1 08 11 0 3 00 4 6 3 04 0 8 1 01 2 6 3

23、03 7 01 2 08 11 3 4 066674min00310min此時(shí)每行及每列中肯定都有此時(shí)每行及每列中肯定都有0元素元素3704320405001232037710811030圈圈0即獨(dú)立零元素即獨(dú)立零元素步驟步驟2：進(jìn)行試分配，判斷是否存在進(jìn)行試分配，判斷是否存在n個(gè)獨(dú)立零元素個(gè)獨(dú)立零元素 嘗試對(duì)所有零元素做嘗試對(duì)所有零元素做標(biāo)記標(biāo)記，確定確定獨(dú)立零元素獨(dú)立零元素。（2）逐）逐行行檢驗(yàn)檢驗(yàn)38可能出現(xiàn)三種情況可能出現(xiàn)三種情況3.不存在未被標(biāo)記過(guò)的零元素，但圈不存在未被標(biāo)記過(guò)的零元素，但圈0的個(gè)數(shù)的個(gè)數(shù)n（3）判斷）判斷獨(dú)立零元素獨(dú)立零元素的個(gè)數(shù)的個(gè)數(shù)圈圈0個(gè)數(shù)個(gè)數(shù)4 n=5作作最少直線(xiàn)覆蓋當(dāng)前所有零元素最少直線(xiàn)覆蓋當(dāng)前所有零元素，便，便于下步增加獨(dú)立零元素的個(gè)數(shù)。于下步增加獨(dú)立零元素的個(gè)數(shù)。0432040500123203771081103039 對(duì)對(duì)不含圈不含圈0的行打的行打； 在打在打的行中，對(duì)所有零元素所在的行中，對(duì)所有零元素所在列列打打； 在所有打在所有打的列中，對(duì)圈的列中，對(duì)圈0所在所在行行打打； 重復(fù)重復(fù)2,3步，直到不能步，直到不能打打?yàn)橹埂橹埂?對(duì)對(duì)未打未打的每一行的每一行畫(huà)一橫線(xiàn)，對(duì)畫(huà)一橫線(xiàn)，對(duì)已打已打的每一列的每一列畫(huà)畫(huà)