分配問(wèn)題和匈牙利法

1、分配問(wèn)題和匈牙利法第1頁(yè)，共32頁(yè)，2022年，5月20日，11點(diǎn)7分，星期一分配問(wèn)題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型分配問(wèn)題也稱(chēng)指派問(wèn)題(assignment problem),在我們現(xiàn)實(shí)生活中,常有各種性質(zhì)的分配問(wèn)題.例如：應(yīng)如何分配若干項(xiàng)工作給若干個(gè)人(或部門(mén))來(lái)完成,以達(dá)到總體的最佳效果等等.由于分配問(wèn)題的多樣性,我們有必要定義分配問(wèn)題的標(biāo)準(zhǔn)形式.匈牙利解法一般的分配問(wèn)題3 分配問(wèn)題與匈牙利法第2頁(yè)，共32頁(yè)，2022年，5月20日，11點(diǎn)7分，星期一 分配問(wèn)題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型分配問(wèn)題的標(biāo)準(zhǔn)形式（以人和任務(wù)為例）假定有n項(xiàng)任務(wù)分配給n個(gè)人去完成,并指定每人完成其中一項(xiàng),每項(xiàng)只交給其中一人去

2、完成, 設(shè)第i人完成第j項(xiàng)任務(wù)費(fèi)用為 Cij(i,j=1,2,n),應(yīng)如何分配使總費(fèi)用最少。 因此,我們可得分配問(wèn)題的系數(shù)矩陣 效率矩陣第3頁(yè)，共32頁(yè)，2022年，5月20日，11點(diǎn)7分，星期一 分配問(wèn)題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型為了建立標(biāo)準(zhǔn)分配問(wèn)題的數(shù)學(xué)模型,我們引入n個(gè) 01變量,并且得到該問(wèn)題的數(shù)學(xué)模型.第4頁(yè)，共32頁(yè)，2022年，5月20日，11點(diǎn)7分，星期一例1.四個(gè)外語(yǔ)學(xué)院學(xué)生組成翻譯公司,接到一項(xiàng)業(yè)務(wù):把一個(gè)產(chǎn)品說(shuō)明書(shū)翻譯成A、B、C、D四種語(yǔ)言,應(yīng)指派何人做何種工作,能使總的時(shí)間最少？ ABCD11494152117910313610541791513 分配問(wèn)題的標(biāo)準(zhǔn)形式及其數(shù)

3、學(xué)模型需時(shí)(h)語(yǔ)種學(xué)生第5頁(yè)，共32頁(yè)，2022年，5月20日，11點(diǎn)7分，星期一解:這是一個(gè)標(biāo)準(zhǔn)的分配問(wèn)題.若設(shè)01變量 分配問(wèn)題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型可用表上作業(yè)法求解第6頁(yè)，共32頁(yè)，2022年，5月20日，11點(diǎn)7分，星期一 匈牙利法匈牙利法的基本思想如果效率矩陣 C 中存在 n 個(gè)位于不同行不同列的零元素,則只要令對(duì)應(yīng)于這些零元素位置的決策變量xij=1,其余的決策變量xij=0,則 可取到最小值0,即該分配方案最優(yōu). 如： 第7頁(yè)，共32頁(yè)，2022年，5月20日，11點(diǎn)7分，星期一 匈牙利法匈牙利法的計(jì)算步驟第一步:找出效率矩陣每行的最小元素,并分別從每行中減去;如例1中效率矩

4、陣為u1=4u2=7u3=5u4=9定理1 如果從分配問(wèn)題效率矩陣C每一行元素中分別減去(或加上)常數(shù)ui,從每一列分別減去(或加上) 常數(shù)vj,得到新的效率矩陣C,C與C具有相同的最優(yōu)解.第8頁(yè)，共32頁(yè)，2022年，5月20日，11點(diǎn)7分，星期一 匈牙利法匈牙利法的計(jì)算步驟第二步:找出效率矩陣每列的最小元素,再分別從每列中減去;接上,例1中效率矩陣轉(zhuǎn)換為C 與 C具有相同的最優(yōu)解v1=4v2=0v3=0v4=0第9頁(yè)，共32頁(yè)，2022年，5月20日，11點(diǎn)7分，星期一 匈牙利法匈牙利法的計(jì)算步驟第三步:確定能否找出n個(gè)位于不同行不同列的零元素集合來(lái).根據(jù)定理2,該問(wèn)題轉(zhuǎn)化為:要覆蓋上面矩

5、陣中的所有零元素,至少需要多少條直線;怎么得到覆蓋零元素的最少直線數(shù)？從第一行開(kāi)始,若該行只有一個(gè)零元素,就對(duì)這個(gè)零元素打上( )號(hào),將打( )號(hào)零元素所在列畫(huà)一條直線.若該行沒(méi)有零元素或有兩個(gè)以上零元素(已劃去的不計(jì)在內(nèi)),則轉(zhuǎn)下一行,依次進(jìn)行到最后一行;從第一列開(kāi)始,若該列只有一個(gè)零元素就對(duì)這個(gè)零元素打上( )號(hào)(同樣不考慮已劃去的零元素),再對(duì)打( )號(hào)零元素所在行畫(huà)一條直線.若該列沒(méi)有零元素或有兩個(gè)以上零元素,則轉(zhuǎn)下一列,依次進(jìn)行到最后一列;重復(fù)1和2兩個(gè)步驟,可能出現(xiàn)三種情況：定理2 若矩陣A的元素可分成“0”和非“0”兩部分,則覆蓋“0”元素的最少直線數(shù)等于位于不同行不同列的“0”

6、元素的最大個(gè)數(shù).第10頁(yè)，共32頁(yè)，2022年，5月20日，11點(diǎn)7分，星期一 匈牙利法第一種情況覆蓋零元素的最少直線數(shù)(或打( )號(hào)的零元素個(gè)數(shù))等于nZ=4+11+5+9=29h 1234A149415B117910C136105D1791513第11頁(yè)，共32頁(yè)，2022年，5月20日，11點(diǎn)7分，星期一 匈牙利法第二種情況打( )號(hào)的零元素個(gè)數(shù)小于n,但未被劃去的零元素之間存在閉回路,這時(shí)可順著閉回路的走向,對(duì)每個(gè)間隔的零元素打一( )號(hào),然后對(duì)所有打( )號(hào)的零元素,或所在行,或所在列畫(huà)一條直線.第12頁(yè)，共32頁(yè)，2022年，5月20日，11點(diǎn)7分，星期一此問(wèn)題有多個(gè)最優(yōu)解第13頁(yè)

7、，共32頁(yè)，2022年，5月20日，11點(diǎn)7分，星期一 匈牙利法第三種情況矩陣中所有零元素或被劃去,或打上( )號(hào),但打( )號(hào)的零元素個(gè)數(shù)仍小于n.第14頁(yè)，共32頁(yè)，2022年，5月20日，11點(diǎn)7分，星期一 匈牙利法匈牙利法的計(jì)算步驟第四步:為設(shè)法使每一行都有一個(gè)打( )號(hào)零元素,需繼續(xù)按定理1對(duì)矩陣進(jìn)行變換：從矩陣未被直線覆蓋的數(shù)字中找出一個(gè)最小的數(shù)k; 對(duì)矩陣的每行,當(dāng)該行有直線覆蓋時(shí),令ui=0,無(wú)直線覆蓋時(shí),令ui=k;每行元素減去ui；對(duì)矩陣中有直線覆蓋的列,令vj=-k,對(duì)無(wú)直線覆蓋的列,令vj=0;每列元素減去vj；得到一個(gè)新矩陣；第五步:回到第三步,反復(fù)進(jìn)行,一直到矩陣的

8、每一行都有一個(gè)打( )號(hào)零元素為止,即找到了最優(yōu)分配方案.第15頁(yè)，共32頁(yè)，2022年，5月20日，11點(diǎn)7分，星期一 匈牙利法上述例子完成一、二、三步之后如右：轉(zhuǎn)向第四步：回到第三步：k=2u1=2u2=2u3=0u4=2v1=-2v2=-2v3=0v4=0第16頁(yè)，共32頁(yè)，2022年，5月20日，11點(diǎn)7分，星期一 匈牙利法第17頁(yè)，共32頁(yè)，2022年，5月20日，11點(diǎn)7分，星期一 匈牙利法第四步：最優(yōu)解所對(duì)應(yīng)的最小值Z=3+2 +4 +3+9=21.第18頁(yè)，共32頁(yè)，2022年，5月20日，11點(diǎn)7分，星期一一般分配問(wèn)題1、人數(shù)和工作任務(wù)不相等的分配問(wèn)題(不平衡的分配問(wèn)題) （

9、1）人少任務(wù)多 （2）人多任務(wù)少 類(lèi)似產(chǎn)銷(xiāo)不平衡問(wèn)題(虛設(shè)假想的人,增添假想任務(wù))2、某項(xiàng)任務(wù)一定不能由某人做的分配問(wèn)題 將相應(yīng)的費(fèi)用系數(shù)取作足夠大的數(shù)M3、一個(gè)人可做幾項(xiàng)任務(wù)的分配問(wèn)題4、目標(biāo)函數(shù)為求最大值(最大化的分配問(wèn)題)效率矩陣中元素全為負(fù)數(shù),根據(jù)定理1,讓效率矩陣中所有元素變成非負(fù)數(shù),再利用匈牙利法求解.第19頁(yè)，共32頁(yè)，2022年，5月20日，11點(diǎn)7分，星期一例1.已知下列五名運(yùn)動(dòng)員各種姿勢(shì)的游泳成績(jī)(各為50m)如下表.試問(wèn)如何從中選拔一個(gè)450m混合泳的接力隊(duì),使預(yù)期的比賽成績(jī)?yōu)樽詈茫?趙錢(qián)張王周仰泳37.732.938.837.035.4蛙泳43.433.142.234.

10、741.8蝶泳33.328.538.930.433.6自由泳29.226.429.628.531.1需時(shí)(s)隊(duì)員項(xiàng)目 不平衡的分配問(wèn)題第20頁(yè)，共32頁(yè)，2022年，5月20日，11點(diǎn)7分，星期一解:非標(biāo)準(zhǔn)的分配問(wèn)題,先轉(zhuǎn)化成標(biāo)準(zhǔn)分配問(wèn)題. 一般分配問(wèn)題 趙錢(qián)張王周仰泳37.732.938.837.035.4蛙泳43.433.142.234.741.8蝶泳33.328.538.930.433.6自由泳29.226.429.628.531.1E00000需時(shí)(s)隊(duì)員項(xiàng)目第21頁(yè)，共32頁(yè)，2022年，5月20日，11點(diǎn)7分，星期一 不平衡的分配問(wèn)題第22頁(yè)，共32頁(yè)，2022年，5月20日，

11、11點(diǎn)7分，星期一 不平衡的分配問(wèn)題第23頁(yè)，共32頁(yè)，2022年，5月20日，11點(diǎn)7分，星期一 不平衡的分配問(wèn)題第24頁(yè)，共32頁(yè)，2022年，5月20日，11點(diǎn)7分，星期一 某任務(wù)一定不能由某人做的分配問(wèn)題 例2. 分配甲、乙、丙、丁四個(gè)人去完成A、B、C、D、E五項(xiàng)任務(wù)。每個(gè)人完成各項(xiàng)任務(wù)的時(shí)間如表所示。由于任務(wù)數(shù)多于人數(shù)，考慮任務(wù)E必須完成，其它4項(xiàng)可任選3項(xiàng)完成。試確定最優(yōu)分配方案，使完成任務(wù)的總時(shí)間最少。 ABCDE甲2529314237乙3938262033丙3427284032丁2442362345第25頁(yè)，共32頁(yè)，2022年，5月20日，11點(diǎn)7分，星期一 某任務(wù)一定不能

12、由某人做的分配問(wèn)題 解：1) 這是不平衡的分配問(wèn)題，首先轉(zhuǎn)換為標(biāo)準(zhǔn)型，再用匈牙利法求解。2) 由于任務(wù)數(shù)多于人數(shù)，所以假定一名虛擬人，設(shè)為戊。因?yàn)楣ぷ鱁必須完成，故設(shè)戊完成E的時(shí)間為M(M是非常大的數(shù))，其余效率系數(shù)為0，則標(biāo)準(zhǔn)型效率矩陣表為： ABCDE甲2529314237乙3938262033丙3427284032丁2442362345戊0000M第26頁(yè)，共32頁(yè)，2022年，5月20日，11點(diǎn)7分，星期一 某任務(wù)一定不能由某人做的分配問(wèn)題 解續(xù)：用匈牙利法求出最優(yōu)分配方案為：即甲-B，乙-D，丙-E，丁-A，任務(wù)C放棄，最少時(shí)間為105h。第27頁(yè)，共32頁(yè)，2022年，5月20日，

13、11點(diǎn)7分，星期一一個(gè)人可做幾項(xiàng)任務(wù)的分配問(wèn)題 若某人可同時(shí)做幾項(xiàng)任務(wù),則將該人化作相同的 幾個(gè)“人”來(lái)接受分配,且費(fèi)用系數(shù)取值相同. 例如：丙可以同時(shí)任職A和C工作，求最優(yōu)分配方案。 ABCD甲37.732.938.837.0乙43.433.142.234.7丙33.328.538.930.4 ABCD甲37.732.938.837.0乙43.433.142.234.7丙33.328.538.930.4丙33.328.538.930.4第28頁(yè)，共32頁(yè)，2022年，5月20日，11點(diǎn)7分，星期一一個(gè)人可做幾項(xiàng)任務(wù)的分配問(wèn)題 例2. 分配甲、乙、丙、丁四個(gè)人去完成A、B、C、D、E五項(xiàng)任務(wù)。

14、每個(gè)人完成各項(xiàng)任務(wù)的時(shí)間如表所示。由于任務(wù)數(shù)多于人數(shù)，考慮其中一人完成兩項(xiàng)，其他每人完成一項(xiàng)。試確定最優(yōu)分配方案，使完成任務(wù)的總時(shí)間最少。 ABCDE甲2529314237乙3938262033丙3427284032丁2442362345第29頁(yè)，共32頁(yè)，2022年，5月20日，11點(diǎn)7分，星期一一個(gè)人可做幾項(xiàng)任務(wù)的分配問(wèn)題 解：虛擬戊，它完成任務(wù)的效率由每列最小效率構(gòu)成，則標(biāo)準(zhǔn)型效率矩陣表為： ABCDE甲2529314237乙3938262033丙3427284032丁2442362345戊2427262032第30頁(yè)，共32頁(yè)，2022年，5月20日，11點(diǎn)7分，星期一例2續(xù) 分配甲、乙、丙、丁四個(gè)人去完成A、B、C、D、E五項(xiàng)任務(wù)。每個(gè)人呢完成各項(xiàng)任務(wù)的時(shí)間如表所示。由于任務(wù)數(shù)多于人數(shù)，考慮任務(wù)A由甲或丙完成，任務(wù)C由丙或丁完成，任務(wù)E由甲、乙或丁完成，且規(guī)定4人中丙或丁完成兩項(xiàng)任務(wù)，其他每人完成一項(xiàng)。試確定最