指派問題的匈牙利法

指派問題指派問題是一種特殊的整數(shù)規(guī)劃問題一、問題的提出設(shè)有m個(gè)工人，能做n件事，但效率不同，并規(guī)定每個(gè)工人做且只能做一件事，每件事有且只能有一個(gè)工人做，問應(yīng)該如何安排他們的工作，使花費(fèi)的總時(shí)間（成本）最少或效率最高？指派問題的匈牙利法共43頁，您現(xiàn)在瀏覽的是第1頁!二、指派問題的數(shù)學(xué)模型設(shè)第i個(gè)工人做第j件事的時(shí)間是，決策變量是則數(shù)學(xué)模型如下指派問題的匈牙利法共43頁，您現(xiàn)在瀏覽的是第2頁!指派問題的匈牙利法共43頁，您現(xiàn)在瀏覽的是第3頁!舉例說明

1）表上作業(yè)法

2）匈牙利法例有四個(gè)工人和四臺不同的機(jī)床，每位工人在不同的機(jī)床上完成給定的任務(wù)的工時(shí)如表5.12所示，問安排哪位工人操作哪一臺機(jī)床可使總工時(shí)最少？任務(wù)1任務(wù)2任務(wù)3任務(wù)4工人1工人2工人3工人4215134104147314161378119指派問題的匈牙利法共43頁，您現(xiàn)在瀏覽的是第4頁!確定調(diào)整行和列在沒有圈起的零所在行上打“√”；在打“√”行中所有零所在的列打“√”；在打“√”列中含有圈起零的行上打“√”，反復(fù)執(zhí)行2）和3）兩步，直到不能打“√”為止；用直線劃去打“√”的列和不打“√”的行，沒有劃去的行構(gòu)成調(diào)整的行，劃去的列構(gòu)成調(diào)整列。指派問題的匈牙利法共43頁，您現(xiàn)在瀏覽的是第5頁!匈牙利法解例3.3時(shí)間矩陣各行各列減去最小元素后得指派問題的匈牙利法共43頁，您現(xiàn)在瀏覽的是第6頁!得最優(yōu)解將圈起的零改為1，其它元素改為0，即得最優(yōu)解如下最小總時(shí)間為22。指派問題的匈牙利法共43頁，您現(xiàn)在瀏覽的是第7頁!減去最小元素指派問題的匈牙利法共43頁，您現(xiàn)在瀏覽的是第8頁!打勾劃線確定調(diào)整行和列√√√指派問題的匈牙利法共43頁，您現(xiàn)在瀏覽的是第9頁!再圈零劃零指派問題的匈牙利法共43頁，您現(xiàn)在瀏覽的是第10頁!另一最優(yōu)解最小時(shí)間（成本）minz=32指派問題的匈牙利法共43頁，您現(xiàn)在瀏覽的是第11頁!（二）、解題步驟：指派問題是0-1規(guī)劃的特例，也是運(yùn)輸問題的特例，當(dāng)然可用整數(shù)規(guī)劃，0-1規(guī)劃或運(yùn)輸問題的解法去求解，這就如同用單純型法求解運(yùn)輸問題一樣是不合算的。利用指派問題的特點(diǎn)可有更簡便的解法，這就是匈牙利法，即系數(shù)矩陣中獨(dú)立0元素的最多個(gè)數(shù)等于能覆蓋所有0元素的最少直線數(shù)。

步：變換指派問題的系數(shù)矩陣（cij）為(bij)，使在(bij)的各行各列中都出現(xiàn)0元素，即(1)從（cij）的每行元素都減去該行的最小元素；(2)再從所得新系數(shù)矩陣的每列元素中減去該列的最小元素。指派問題的匈牙利法共43頁，您現(xiàn)在瀏覽的是第12頁!(4)若仍有沒有劃圈的0元素，且同行(列)的0元素至少有兩個(gè)，則從剩有0元素最少的行(列)開始，比較這行各0元素所在列中0元素的數(shù)目，選擇0元素少的那列的這個(gè)0元素加圈(表示選擇性多的要“禮讓”選擇性少的)。然后劃掉同行同列的其它0元素。可反復(fù)進(jìn)行，直到所有0元素都已圈出和劃掉為止。

（5）若◎元素的數(shù)目m等于矩陣的階數(shù)n，那么這指派問題的最優(yōu)解已得到。若m<n,則轉(zhuǎn)入下一步。

第三步：作最少的直線覆蓋所有0元素。(1)對沒有◎的行打√號；(2)對已打√號的行中所有含?元素的列打√號；(3)再對打有√號的列中含◎元素的行打√號；指派問題的匈牙利法共43頁，您現(xiàn)在瀏覽的是第13頁!例一：

任務(wù)人員ABCD甲215134乙1041415丙9141613丁78119指派問題的匈牙利法共43頁，您現(xiàn)在瀏覽的是第14頁!42指派問題的匈牙利法共43頁，您現(xiàn)在瀏覽的是第15頁!有一份中文說明書，需譯成英、日、德、俄四種文字，分別記作A、B、C、D?，F(xiàn)有甲、乙、丙、丁四人，他們將中文說明書譯成不同語種的說明書所需時(shí)間如下表所示，問如何分派任務(wù)，可使總時(shí)間最少？

任務(wù)人員ABCD甲67112乙4598丙31104丁5982例二、指派問題的匈牙利法共43頁，您現(xiàn)在瀏覽的是第16頁!第三步，作最少的直線覆蓋所有0元素：

◎◎◎??√√√獨(dú)立零元素的個(gè)數(shù)m等于最少直線數(shù)l，即l＝m=3<n=4；第四步，變換矩陣(bij)以增加0元素：沒有被直線覆蓋的所有元素中的最小元素為1，然后打√各行都減去1；打√各列都加上1，得如下矩陣，并轉(zhuǎn)第二步進(jìn)行試指派：指派問題的匈牙利法共43頁，您現(xiàn)在瀏覽的是第17頁!練習(xí)：115764戊69637丁86458丙9117129乙118957甲EDCBA費(fèi)工作用人員指派問題的匈牙利法共43頁，您現(xiàn)在瀏覽的是第18頁!◎?◎◎◎??指派問題的匈牙利法共43頁，您現(xiàn)在瀏覽的是第19頁!◎?◎◎◎??指派問題的匈牙利法共43頁，您現(xiàn)在瀏覽的是第20頁!◎?◎?◎?◎?√√√√√√√l=m=4<n=5指派問題的匈牙利法共43頁，您現(xiàn)在瀏覽的是第21頁!◎??◎??◎?◎?◎此問題有多個(gè)最優(yōu)解28指派問題的匈牙利法共43頁，您現(xiàn)在瀏覽的是第22頁!◎??◎??◎?◎?◎指派問題的匈牙利法共43頁，您現(xiàn)在瀏覽的是第23頁!獲得初始解：圈零/劃零操作將時(shí)間矩陣C的每一行都減去相應(yīng)行的最小元素和每一列都減去相應(yīng)列的最小元素，使每一行和每一列都含有零；從最少零數(shù)的行或列開始，將“零”圈起來，并劃去它所在行和所在列的其它零；反復(fù)做2），直到所有零被圈起或被劃掉為止。得到初始解。判斷是否為最優(yōu)解：圈起的零的個(gè)數(shù)是否等于n。指派問題的匈牙利法共43頁，您現(xiàn)在瀏覽的是第24頁!調(diào)整可行解的方法在調(diào)整行中尋找最小的元素，將它作為調(diào)整量；將調(diào)整行各元素減去調(diào)整量，對調(diào)整列中各元素加上調(diào)整量。再次執(zhí)行“圈零”和“劃零”的操作，并循環(huán)以上的步驟，直到圈起的零數(shù)等于n為止。指派問題的匈牙利法共43頁，您現(xiàn)在瀏覽的是第25頁!圈零劃零指派問題的匈牙利法共43頁，您現(xiàn)在瀏覽的是第26頁!再看一例請求解如下矩陣表達(dá)的指派問題指派問題的匈牙利法共43頁，您現(xiàn)在瀏覽的是第27頁!圈零劃零指派問題的匈牙利法共43頁，您現(xiàn)在瀏覽的是第28頁!調(diào)整可行解指派問題的匈牙利法共43頁，您現(xiàn)在瀏覽的是第29頁!得最優(yōu)解指派問題的匈牙利法共43頁，您現(xiàn)在瀏覽的是第30頁!匈牙利算法示例指派問題的匈牙利法共43頁，您現(xiàn)在瀏覽的是第31頁!第二步：進(jìn)行試指派，以尋求最優(yōu)解。在(bij)中找盡可能多的獨(dú)立0元素，若能找出n個(gè)獨(dú)立0元素，就以這n個(gè)獨(dú)立0元素對應(yīng)解矩陣(xij)中的元素為1，其余為0，這就得到最優(yōu)解。找獨(dú)立0元素，常用的步驟為：(1)從只有一個(gè)0元素的行(列)開始，給這個(gè)0元素加圈，記作◎。然后劃去◎所在列(行)的其它0元素，記作?；這表示這列所代表的任務(wù)已指派完，不必再考慮別人了。(2)給只有一個(gè)0元素的列(行)中的0元素加圈，記作◎；然后劃去◎所在行的0元素，記作?．(3)反復(fù)進(jìn)行(1)，(2)兩步，直到盡可能多的0元素都被圈出和劃掉為止。指派問題的匈牙利法共43頁，您現(xiàn)在瀏覽的是第32頁!(4)重復(fù)(2)，(3)直到得不出新的打√號的行、列為止；(5)對沒有打√號的行畫橫線，有打√號的列畫縱線，這就得到覆蓋所有0元素的最少直線數(shù)l。l應(yīng)等于m，若不相等，說明試指派過程有誤，回到第二步(4)，另行試指派；若l＝m<n，須再變換當(dāng)前的系數(shù)矩陣，以找到n個(gè)獨(dú)立的0元素，為此轉(zhuǎn)第四步。第四步：變換矩陣(bij)以增加0元素。在沒有被直線覆蓋的所有元素中找出最小元素，然后打√各行都減去這最小元素；打√各列都加上這最小元素（以保證系數(shù)矩陣中不出現(xiàn)負(fù)元素）。新系數(shù)矩陣的最優(yōu)解和原問題仍相同。轉(zhuǎn)回第二步。指派問題的匈牙利法共43頁，您現(xiàn)在瀏覽的是第33頁!2497指派問題的匈牙利法共43頁，您現(xiàn)在瀏覽的是第34頁!◎?◎??◎◎指派問題的匈牙利法共43頁，您現(xiàn)在瀏覽的是第35頁!求解過程如下：步，變換系數(shù)矩陣：－5第二步，試指派：◎◎◎??找到3個(gè)獨(dú)立零元素但m=3<n=

4指派問題的匈牙利法共43頁，您現(xiàn)在瀏覽的是第36頁!000000得到4個(gè)獨(dú)立零元素，所以最優(yōu)解矩陣為：

◎◎◎??√√√◎◎◎??15◎◎◎??◎指派問題的匈牙利法共43頁，您現(xiàn)在瀏覽的是第37頁!-1-2指派問題的匈牙利法共43頁，您現(xiàn)在瀏覽的是第38頁!◎?◎◎◎??√√√l=m=4<n=5指派問題的匈牙利法共43頁，您現(xiàn)在瀏覽的是第39頁!◎?