分配問題和匈牙利法

分配問題和匈牙利法第1頁，課件共32頁，創(chuàng)作于2023年2月分配問題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型分配問題也稱指派問題(assignmentproblem),在我們現(xiàn)實生活中,常有各種性質(zhì)的分配問題.例如：應(yīng)如何分配若干項工作給若干個人(或部門)來完成,以達(dá)到總體的最佳效果等等.由于分配問題的多樣性,我們有必要定義分配問題的標(biāo)準(zhǔn)形式.匈牙利解法一般的分配問題3分配問題與匈牙利法第2頁，課件共32頁，創(chuàng)作于2023年2月分配問題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型分配問題的標(biāo)準(zhǔn)形式（以人和任務(wù)為例）假定有n項任務(wù)分配給n個人去完成,并指定每人完成其中一項,每項只交給其中一人去完成,設(shè)第i人完成第j項任務(wù)費(fèi)用為Cij(i,j=1,2,……,n),應(yīng)如何分配使總費(fèi)用最少。

因此,我們可得分配問題的系數(shù)矩陣效率矩陣第3頁，課件共32頁，創(chuàng)作于2023年2月分配問題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型為了建立標(biāo)準(zhǔn)分配問題的數(shù)學(xué)模型,我們引入n2個

0－1變量,并且得到該問題的數(shù)學(xué)模型.第4頁，課件共32頁，創(chuàng)作于2023年2月例1.四個外語學(xué)院學(xué)生組成翻譯公司,接到一項業(yè)務(wù):把一個產(chǎn)品說明書翻譯成A、B、C、D四種語言,應(yīng)指派何人做何種工作,能使總的時間最少？

ABCD11494152117910313610541791513分配問題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型需時(h)語種學(xué)生第5頁，課件共32頁，創(chuàng)作于2023年2月解:這是一個標(biāo)準(zhǔn)的分配問題.若設(shè)0－1變量分配問題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型可用表上作業(yè)法求解第6頁，課件共32頁，創(chuàng)作于2023年2月匈牙利法匈牙利法的基本思想如果效率矩陣C中存在n

個位于不同行不同列的零元素,則只要令對應(yīng)于這些零元素位置的決策變量xij=1,其余的決策變量xij=0,則可取到最小值0,即該分配方案最優(yōu).

如：第7頁，課件共32頁，創(chuàng)作于2023年2月匈牙利法匈牙利法的計算步驟第一步:找出效率矩陣每行的最小元素,并分別從每行中減去;如例1中效率矩陣為u1=4u2=7u3=5u4=9定理1如果從分配問題效率矩陣C每一行元素中分別減去(或加上)常數(shù)ui,從每一列分別減去(或加上)常數(shù)vj,得到新的效率矩陣C’,C’與C具有相同的最優(yōu)解.第8頁，課件共32頁，創(chuàng)作于2023年2月匈牙利法匈牙利法的計算步驟第二步:找出效率矩陣每列的最小元素,再分別從每列中減去;接上,例1中效率矩陣轉(zhuǎn)換為C與C〞具有相同的最優(yōu)解v1=4v2=0v3=0v4=0第9頁，課件共32頁，創(chuàng)作于2023年2月匈牙利法匈牙利法的計算步驟第三步:確定能否找出n個位于不同行不同列的零元素集合來.根據(jù)定理2,該問題轉(zhuǎn)化為:要覆蓋上面矩陣中的所有零元素,至少需要多少條直線;怎么得到覆蓋零元素的最少直線數(shù)？從第一行開始,若該行只有一個零元素,就對這個零元素打上()號,將打()號零元素所在列畫一條直線.若該行沒有零元素或有兩個以上零元素(已劃去的不計在內(nèi)),則轉(zhuǎn)下一行,依次進(jìn)行到最后一行;從第一列開始,若該列只有一個零元素就對這個零元素打上()號(同樣不考慮已劃去的零元素),再對打()號零元素所在行畫一條直線.若該列沒有零元素或有兩個以上零元素,則轉(zhuǎn)下一列,依次進(jìn)行到最后一列;重復(fù)1和2兩個步驟,可能出現(xiàn)三種情況：定理2若矩陣A的元素可分成“0”和非“0”兩部分,則覆蓋“0”元素的最少直線數(shù)等于位于不同行不同列的“0”元素的最大個數(shù).第10頁，課件共32頁，創(chuàng)作于2023年2月匈牙利法第一種情況覆蓋零元素的最少直線數(shù)(或打()號的零元素個數(shù))等于nZ=4+11+5+9=29h

1234A149415B117910C136105D1791513第11頁，課件共32頁，創(chuàng)作于2023年2月匈牙利法第二種情況打()號的零元素個數(shù)小于n,但未被劃去的零元素之間存在閉回路,這時可順著閉回路的走向,對每個間隔的零元素打一()號,然后對所有打()號的零元素,或所在行,或所在列畫一條直線.第12頁，課件共32頁，創(chuàng)作于2023年2月此問題有多個最優(yōu)解第13頁，課件共32頁，創(chuàng)作于2023年2月匈牙利法第三種情況矩陣中所有零元素或被劃去,或打上()號,但打()號的零元素個數(shù)仍小于n.第14頁，課件共32頁，創(chuàng)作于2023年2月匈牙利法匈牙利法的計算步驟第四步:為設(shè)法使每一行都有一個打()號零元素,需繼續(xù)按定理1對矩陣進(jìn)行變換：從矩陣未被直線覆蓋的數(shù)字中找出一個最小的數(shù)k;

對矩陣的每行,當(dāng)該行有直線覆蓋時,令ui=0,無直線覆蓋時,令ui=k;每行元素減去ui；對矩陣中有直線覆蓋的列,令vj=-k,對無直線覆蓋的列,令vj=0;每列元素減去vj；得到一個新矩陣；第五步:回到第三步,反復(fù)進(jìn)行,一直到矩陣的每一行都有一個打()號零元素為止,即找到了最優(yōu)分配方案.第15頁，課件共32頁，創(chuàng)作于2023年2月匈牙利法上述例子完成一、二、三步之后如右：轉(zhuǎn)向第四步：回到第三步：k=2u1=2u2=2u3=0u4=2v1=-2v2=-2v3=0v4=0第16頁，課件共32頁，創(chuàng)作于2023年2月匈牙利法第17頁，課件共32頁，創(chuàng)作于2023年2月匈牙利法第四步：最優(yōu)解所對應(yīng)的最小值Z=3+2+4+3+9=21.第18頁，課件共32頁，創(chuàng)作于2023年2月一般分配問題1、人數(shù)和工作任務(wù)不相等的分配問題(不平衡的分配問題)（1）人少任務(wù)多（2）人多任務(wù)少類似產(chǎn)銷不平衡問題(虛設(shè)假想的人,增添假想任務(wù))2、某項任務(wù)一定不能由某人做的分配問題

將相應(yīng)的費(fèi)用系數(shù)取作足夠大的數(shù)M3、一個人可做幾項任務(wù)的分配問題4、目標(biāo)函數(shù)為求最大值(最大化的分配問題) 效率矩陣中元素全為負(fù)數(shù),根據(jù)定理1,讓效率矩陣中所有元素變成非負(fù)數(shù),再利用匈牙利法求解.第19頁，課件共32頁，創(chuàng)作于2023年2月例1.已知下列五名運(yùn)動員各種姿勢的游泳成績(各為50m)如下表.試問如何從中選拔一個4×50m混合泳的接力隊,使預(yù)期的比賽成績?yōu)樽詈茫?/p>

趙錢張王周仰泳37.732.938.837.035.4蛙泳43.433.142.234.741.8蝶泳33.328.538.930.433.6自由泳29.226.429.628.531.1需時(s)隊員項目不平衡的分配問題第20頁，課件共32頁，創(chuàng)作于2023年2月解:非標(biāo)準(zhǔn)的分配問題,先轉(zhuǎn)化成標(biāo)準(zhǔ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需時(s)隊員項目第21頁，課件共32頁，創(chuàng)作于2023年2月不平衡的分配問題第22頁，課件共32頁，創(chuàng)作于2023年2月不平衡的分配問題第23頁，課件共32頁，創(chuàng)作于2023年2月不平衡的分配問題第24頁，課件共32頁，創(chuàng)作于2023年2月某任務(wù)一定不能由某人做的分配問題例2.分配甲、乙、丙、丁四個人去完成A、B、C、D、E五項任務(wù)。每個人完成各項任務(wù)的時間如表所示。由于任務(wù)數(shù)多于人數(shù)，考慮任務(wù)E必須完成，其它4項可任選3項完成。試確定最優(yōu)分配方案，使完成任務(wù)的總時間最少。

ABCDE甲2529314237乙3938262033丙3427284032丁2442362345第25頁，課件共32頁，創(chuàng)作于2023年2月某任務(wù)一定不能由某人做的分配問題解：1)這是不平衡的分配問題，首先轉(zhuǎn)換為標(biāo)準(zhǔn)型，再用匈牙利法求解。2)由于任務(wù)數(shù)多于人數(shù)，所以假定一名虛擬人，設(shè)為戊。因為工作E必須完成，故設(shè)戊完成E的時間為M(M是非常大的數(shù))，其余效率系數(shù)為0，則標(biāo)準(zhǔn)型效率矩陣表為：

ABCDE甲2529314237乙3938262033丙3427284032丁2442362345戊0000M第26頁，課件共32頁，創(chuàng)作于2023年2月某任務(wù)一定不能由某人做的分配問題解續(xù)：用匈牙利法求出最優(yōu)分配方案為：即甲-B，乙-D，丙-E，丁-A，任務(wù)C放棄，最少時間為105h。第27頁，課件共32頁，創(chuàng)作于2023年2月一個人可做幾項任務(wù)的分配問題若某人可同時做幾項任務(wù),則將該人化作相同的

幾個“人”來接受分配,且費(fèi)用系數(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頁，課件共32頁，創(chuàng)作于2023年2月一個人可做幾項任務(wù)的分配問題例2.分配甲、乙、丙、丁四個人去完成A、B、C、D、E五項任務(wù)。每個人完成各項任務(wù)的時間如表所示。由于任務(wù)數(shù)多于人數(shù)，考慮其中一人完成兩項，其他每人完成一項。試確定最優(yōu)分配方案，使完成任務(wù)的總時間最少。

ABCDE甲2529314237乙3938262033丙3427284032丁2442362345第29頁，課件共32頁，創(chuàng)作于2023年2月一個人可做幾項任務(wù)的分配問題解：虛擬戊，它完成任務(wù)的效率由每列最小效率構(gòu)成，則標(biāo)準(zhǔn)型效率矩陣表為：

ABCDE甲2529314237乙3938262033丙3427284032丁2442362345戊2427262032第30頁，課件共32頁，創(chuàng)作于2023年2月例2續(xù)分配甲、乙、丙、丁四個人去完成A、B、C、D、E五項任務(wù)。每個人呢完成各項任務(wù)的時間如表所示。由于任務(wù)數(shù)多于人數(shù)，考慮任務(wù)A由甲或丙完成，任務(wù)C由丙或丁完成，任務(wù)E由甲、乙或丁完成，且規(guī)定4人中丙或丁完成兩項任務(wù)，其他每人完成一項。試確定最優(yōu)分配方案，使完成任務(wù)