分配問(wèn)題指派問(wèn)題與匈牙利法課件

第5講分配問(wèn)題（指派問(wèn)題）與匈牙利法分配問(wèn)題的提出分配問(wèn)題的提出若干項(xiàng)工作或任務(wù)需要若干個(gè)人去完成。由于每人的知識(shí)、能力、經(jīng)驗(yàn)的不同，故各人完成不同任務(wù)所需要的時(shí)間不同（或其他資源）。問(wèn)：應(yīng)指派哪個(gè)人完成何項(xiàng)工作，可使完成所有工作所消耗的總資源最少？整體解題思路總結(jié)例題：工作者1工作者2工作者3工作者4工作者5工作14871512工作279171410工作3691287工作46714610工作56912106單位：小時(shí)標(biāo)準(zhǔn)形式的分配問(wèn)題標(biāo)準(zhǔn)形式的分配問(wèn)題分派方案滿足下述兩個(gè)條件：任一個(gè)工人都不能去做兩件或兩件以上的工作任一件工作都不能同時(shí)接受兩個(gè)及以上的工人去做設(shè)某公司準(zhǔn)備派n個(gè)工人x1，x2，…，xn，去作n件工作y1，y2，…，yn。已知工人xi完成工作yj所需時(shí)間為cij(i,j=1,2,…,n)?，F(xiàn)問(wèn)：如何確定一個(gè)分派工人去工作的方案，使得工人們完成工作的總時(shí)間為最少。數(shù)學(xué)模型n個(gè)人n件事cij：第i人做第j事的費(fèi)用xij＝1若指派第i人做第j事0若指派第i人不做第j事總費(fèi)用：i，j＝1,

...,

nj＝1,...,ni＝1,...,n每件事必有且只有一個(gè)人去做每個(gè)人必做且只做一件事時(shí)間、原料、金錢(qián)等資源數(shù)學(xué)模型j＝1,...,ni＝1,...,ns.t.線性規(guī)劃問(wèn)題運(yùn)輸問(wèn)題0-1型整數(shù)規(guī)劃問(wèn)題匈牙利法1955年由美國(guó)數(shù)學(xué)家W.W.kuhn(庫(kù)恩)提出，利用了匈牙利數(shù)學(xué)家D.Konig(康尼格)證明的2個(gè)定理。系數(shù)矩陣(效率矩陣)解矩陣(決策變量矩陣)n個(gè)人n件事014丙085乙210甲CBA時(shí)工作間人員004丙075乙200甲CBA時(shí)工作間人員458丙4129乙987甲CBA時(shí)工作

間

人員定理：若將分配問(wèn)題系數(shù)矩陣的每一行及每一列分別減去各行及各列的最小元素，則新分配問(wèn)題與原分配問(wèn)題有相同的最優(yōu)解，只有最優(yōu)值差一常數(shù)。相關(guān)定理使每行每列都出現(xiàn)零元素步驟1：變換系數(shù)矩陣，使其每行每列都出現(xiàn)0元素把各行元素分別減去本行元素的最小值，然后在此基礎(chǔ)上再把每列元素減去本列中的最小值。此時(shí)每行及每列中肯定都有0元素步驟2：進(jìn)行試分配，判斷是否存在n個(gè)獨(dú)立零元素嘗試對(duì)所有零元素做標(biāo)記，確定獨(dú)立零元素。（1）逐行檢驗(yàn)對(duì)只有一個(gè)未標(biāo)記的零元素的行，用記號(hào)O將該零元素圈起，然后將被圈起的零元素所在列的其他未標(biāo)記的零元素用記號(hào)/劃去。重復(fù)行檢驗(yàn)，直到每一行都沒(méi)有未被標(biāo)記的零元素或至少有兩個(gè)未被標(biāo)記的零元素為止。表示此人只能做該事（此事只能由該人做）表示此事已不能由其他人來(lái)做（此人已不能做其他事）步驟2：進(jìn)行試分配，判斷是否存在n個(gè)獨(dú)立零元素嘗試對(duì)所有零元素做標(biāo)記，確定獨(dú)立零元素。（2）逐列檢驗(yàn)與行檢驗(yàn)類似：對(duì)只有一個(gè)未標(biāo)記的零元素的列，用記號(hào)O將該零元素圈起，然后將被圈起的零元素所在行的其他未標(biāo)記的零元素用記號(hào)/劃去。重復(fù)列檢驗(yàn)，直到?jīng)]有未被標(biāo)記的零元素或至少有兩個(gè)未被標(biāo)記的零元素為止。圈0即獨(dú)立零元素步驟2：進(jìn)行試分配，判斷是否存在n個(gè)獨(dú)立零元素嘗試對(duì)所有零元素做標(biāo)記，確定獨(dú)立零元素。（2）逐列檢驗(yàn)可能出現(xiàn)三種情況1.每一行均有圈0出現(xiàn)，圈0的個(gè)數(shù)恰好等于n2.存在未標(biāo)記過(guò)的零元素，但它們所在的行和列中，未被標(biāo)記過(guò)的零元素的個(gè)數(shù)均至少有兩個(gè)。3.不存在未被標(biāo)記過(guò)的零元素，但圈0的個(gè)數(shù)<n可進(jìn)行分配：令圈0位置的決策變量取值為1，其他為0（3）判斷獨(dú)立零元素的個(gè)數(shù)可能出現(xiàn)三種情況3.不存在未被標(biāo)記過(guò)的零元素，但圈0的個(gè)數(shù)<n（3）判斷獨(dú)立零元素的個(gè)數(shù)圈0個(gè)數(shù)4<n=5作最少直線覆蓋當(dāng)前所有零元素，便于下步增加獨(dú)立零元素的個(gè)數(shù)。定理：系數(shù)矩陣C中獨(dú)立零元素的最多個(gè)數(shù)等于能覆蓋所有零元素的最少線數(shù)。由匈牙利數(shù)學(xué)家D.Konig(康尼格)所證明例：分別求下列矩陣中的獨(dú)立零元素的最多個(gè)數(shù)。44獨(dú)立零元素的個(gè)數(shù)最多：⑥找未被直線覆蓋的最小數(shù)字k；⑦對(duì)矩陣的每行：當(dāng)該行有直線覆蓋時(shí)，令ui=0；當(dāng)該行無(wú)直線覆蓋時(shí)，令ui=k。ui01100⑧對(duì)矩陣的每列：當(dāng)該列有直線覆蓋時(shí)，令vj=-k；當(dāng)該列無(wú)直線覆蓋時(shí)，令vj=0。vj-10000ui01100vj-10000⑨從原矩陣的每個(gè)元素aij中分別減去ui和vj，得到新元素對(duì)不含圈0的行打；在打的行中，對(duì)所有零元素所在列打；在所有打的列中，對(duì)圈0所在行打；重復(fù)2,3步，直到不能打?yàn)橹?。?duì)未打的每一行畫(huà)一橫線，對(duì)已打的每一列畫(huà)一縱線，即得到覆蓋當(dāng)前0元素的最少直線集。圈0個(gè)數(shù)4<n=5⑥找未被直線覆蓋的最小數(shù)字k；⑦對(duì)矩陣的每行：當(dāng)該行有直線覆蓋時(shí)，令ui=0；當(dāng)該行無(wú)直線覆蓋時(shí)，令ui=k。ui00202⑧對(duì)矩陣的每列：當(dāng)該列有直線覆蓋時(shí)，令vj=-k；當(dāng)該列無(wú)直線覆蓋時(shí)，令vj=0。vj-20000⑨從原矩陣的每個(gè)元素aij中分別減去ui和vj，得到新元素ui00202vj-20000⑩再次尋找獨(dú)立零元素分配方案B⑩再次尋找獨(dú)立零元素分配方案B整體解題思路總結(jié)整體解題思路總結(jié)例題：人1人2人3人4人5工作14871512工作279171410工作3691287工作46714610工作56912106單位：小時(shí)整體解題思路總結(jié)例題：步驟1：變換系數(shù)矩陣，使其每行每列都出現(xiàn)0元素把各行元素分別減去本行元素的最小值，然后在此基礎(chǔ)上再把每列元素減去本列中的最小值。此時(shí)每行及每列中肯定都有0元素圈0即獨(dú)立零元素步驟2：進(jìn)行試分配，判斷是否存在n個(gè)獨(dú)立零元素嘗試對(duì)所有零元素做標(biāo)記，確定獨(dú)立零元素。（2）逐行檢驗(yàn)可能出現(xiàn)三種情況3.不存在未被標(biāo)記過(guò)的零元素，但圈0的個(gè)數(shù)<n（3）判斷獨(dú)立零元素的個(gè)數(shù)圈0個(gè)數(shù)4<n=5作最少直線覆蓋當(dāng)前所有零元素，便于下步增加獨(dú)立零元素的個(gè)數(shù)。對(duì)不含圈0的行打；在打的行中，對(duì)所有零元素所在列打；在所有打的列中，對(duì)圈0所在行打；重復(fù)2,3步，直到不能打?yàn)橹?。?duì)未打的每一行畫(huà)一橫線，對(duì)已打的每一列畫(huà)一縱線，即得到覆蓋當(dāng)前0元素的最少直線集。⑥找未被直線覆蓋的最小數(shù)字k；⑦對(duì)矩陣的每行：當(dāng)該行有直線覆蓋時(shí)，令ui=0；當(dāng)該行無(wú)直線覆蓋時(shí)，令ui=k。ui01100⑧對(duì)矩陣的每列：當(dāng)該列有直線覆蓋時(shí)，令vj=-k；