指派問題的匈牙利法課件

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

1）表上作業(yè)法

2）匈牙利法例有四個工人和四臺不同的機(jī)床，每位工人在不同的機(jī)床上完成給定的任務(wù)的工時如表5.12所示，問安排哪位工人操作哪一臺機(jī)床可使總工時最少？任務(wù)1任務(wù)2任務(wù)3任務(wù)4工人1工人2工人3工人4215134104147314161378119舉例說明

1）表上作業(yè)法

2）匈牙利法例有四個工人和四臺獲得初始解：圈零/劃零操作將時間矩陣C的每一行都減去相應(yīng)行的最小元素和每一列都減去相應(yīng)列的最小元素，使每一行和每一列都含有零；從最少零數(shù)的行或列開始，將“零”圈起來，并劃去它所在行和所在列的其它零；反復(fù)做2），直到所有零被圈起或被劃掉為止。得到初始解。判斷是否為最優(yōu)解：圈起的零的個數(shù)是否等于n。獲得初始解：圈零/劃零操作將時間矩陣C的每一行都減去相應(yīng)行的確定調(diào)整行和列在沒有圈起的零所在行上打“√”；在打“√”行中所有零所在的列打“√”；在打“√”列中含有圈起零的行上打“√”，反復(fù)執(zhí)行2）和3）兩步，直到不能打“√”為止；用直線劃去打“√”的列和不打“√”的行，沒有劃去的行構(gòu)成調(diào)整的行，劃去的列構(gòu)成調(diào)整列。確定調(diào)整行和列在沒有圈起的零所在行上打“√”；調(diào)整可行解的方法在調(diào)整行中尋找最小的元素，將它作為調(diào)整量；將調(diào)整行各元素減去調(diào)整量，對調(diào)整列中各元素加上調(diào)整量。再次執(zhí)行“圈零”和“劃零”的操作，并循環(huán)以上的步驟，直到圈起的零數(shù)等于n為止。調(diào)整可行解的方法在調(diào)整行中尋找最小的元素，將它作為調(diào)整量；匈牙利法解例3.3時間矩陣各行各列減去最小元素后得匈牙利法解例3.3時間矩陣圈零劃零圈零劃零得最優(yōu)解將圈起的零改為1，其它元素改為0，即得最優(yōu)解如下最小總時間為22。得最優(yōu)解將圈起的零改為1，其它元素改為0，即得最優(yōu)解如下再看一例請求解如下矩陣表達(dá)的指派問題再看一例請求解如下矩陣表達(dá)的指派問題減去最小元素減去最小元素圈零劃零圈零劃零打勾劃線確定調(diào)整行和列√√√打勾劃線確定調(diào)整行和列√√√調(diào)整可行解調(diào)整可行解再圈零劃零再圈零劃零得最優(yōu)解得最優(yōu)解另一最優(yōu)解最小時間（成本）minz=32另一最優(yōu)解最小時間（成本）minz=32匈牙利算法示例匈牙利算法示例

（二）、解題步驟：

指派問題是0-1規(guī)劃的特例，也是運(yùn)輸問題的特例，當(dāng)然可用整數(shù)規(guī)劃，0-1規(guī)劃或運(yùn)輸問題的解法去求解，這就如同用單純型法求解運(yùn)輸問題一樣是不合算的。利用指派問題的特點可有更簡便的解法，這就是匈牙利法，即系數(shù)矩陣中獨立0元素的最多個數(shù)等于能覆蓋所有0元素的最少直線數(shù)。

第一步：變換指派問題的系數(shù)矩陣（cij）為(bij)，使在(bij)的各行各列中都出現(xiàn)0元素，即

(1)從（cij）的每行元素都減去該行的最小元素；

(2)再從所得新系數(shù)矩陣的每列元素中減去該列的最小元素。（二）、解題步驟：指派問題是0-1規(guī)劃的特例

第二步：進(jìn)行試指派，以尋求最優(yōu)解。在(bij)中找盡可能多的獨立0元素，若能找出n個獨立0元素，就以這n個獨立0元素對應(yīng)解矩陣(xij)中的元素為1，其余為0，這就得到最優(yōu)解。找獨立0元素，常用的步驟為：

(1)從只有一個0元素的行(列)開始，給這個0元素加圈，記作◎。然后劃去◎所在列(行)的其它0元素，記作?；這表示這列所代表的任務(wù)已指派完，不必再考慮別人了。

(2)給只有一個0元素的列(行)中的0元素加圈，記作◎；然后劃去◎所在行的0元素，記作?．

(3)反復(fù)進(jìn)行(1)，(2)兩步，直到盡可能多的0元素都被圈出和劃掉為止。第二步：進(jìn)行試指派，以尋求最優(yōu)解。(4)若仍有沒有劃圈的0元素，且同行(列)的0元素至少有兩個，則從剩有0元素最少的行(列)開始，比較這行各0元素所在列中0元素的數(shù)目，選擇0元素少的那列的這個0元素加圈(表示選擇性多的要“禮讓”選擇性少的)。然后劃掉同行同列的其它0元素?？煞磸?fù)進(jìn)行，直到所有0元素都已圈出和劃掉為止。

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

第三步：作最少的直線覆蓋所有0元素。

(1)對沒有◎的行打√號；

(2)對已打√號的行中所有含?元素的列打√號；

(3)再對打有√號的列中含◎元素的行打√號；(4)若仍有沒有劃圈的0元素，且同行(列)的0元素(4)重復(fù)(2)，(3)直到得不出新的打√號的行、列為止；

(5)對沒有打√號的行畫橫線，有打√號的列畫縱線，這就得到覆蓋所有0元素的最少直線數(shù)l。l應(yīng)等于m，若不相等，說明試指派過程有誤，回到第二步(4)，另行試指派；若l＝m<n，須再變換當(dāng)前的系數(shù)矩陣，以找到n個獨立的0元素，為此轉(zhuǎn)第四步。第四步：變換矩陣(bij)以增加0元素。在沒有被直線覆蓋的所有元素中找出最小元素，然后打√各行都減去這最小元素；打√各列都加上這最小元素（以保證系數(shù)矩陣中不出現(xiàn)負(fù)元素）。新系數(shù)矩陣的最優(yōu)解和原問題仍相同。轉(zhuǎn)回第二步。(4)重復(fù)(2)，(3)直到得不出新的打√號的行、列為例一：

任務(wù)人員ABCD甲215134乙1041415丙9141613丁78119例一：任務(wù)ABCD甲215134乙1041415249724974242◎?◎??◎◎◎?◎??◎◎

有一份中文說明書，需譯成英、日、德、俄四種文字，分別記作A、B、C、D?，F(xiàn)有甲、乙、丙、丁四人，他們將中文說明書譯成不同語種的說明書所需時間如下表所示，問如何分派任務(wù)，可使總時間最少？

任務(wù)人員ABCD甲67112乙4598丙31104丁5982例二、有一份中文說明書，需譯成英、日、德、俄求解過程如下：第一步，變換系數(shù)矩陣：－5第二步，試指派：◎◎◎??

找到3個獨立零元素但m=3<n=

4求解過程如下：－5第二步，試指派：◎◎◎??找到3個

第三步，作最少的直線覆蓋所有0元素：

◎◎◎??√√√獨立零元素的個數(shù)m等于最少直線數(shù)l，即l＝m=3<n=4；

第四步，變換矩陣(bij)以增加0元素：沒有被直線覆蓋的所有元素中的最小元素為1，然后打√各行都減去1；打√各列都加上1，得如下矩陣，并轉(zhuǎn)第二步進(jìn)行試指派：第三步，作最少的直線覆蓋所有0元素：◎◎◎??√√000000得到4個獨立零元素，所以最優(yōu)解矩陣為：

◎◎◎??√√√◎◎◎??15◎◎◎??◎000000得到4個獨立零元素，所以最優(yōu)解矩陣為：練習(xí)：115764戊69637丁86458丙9117129乙118957甲EDCBA費(fèi)工作用人員練習(xí)：115764戊69637丁86458丙9117129乙-1-2-1-2◎?◎◎◎??◎?◎◎◎??◎?◎◎◎??√√√l=m=4<n=5◎?◎◎◎??√√√l=m=4<n=5◎?◎◎◎??◎?◎◎◎??◎?◎?◎?◎?√√√√√√√◎?◎?◎?◎?√√√√√√√◎?◎?◎?◎?√√√√√√√l=m=4<n=5◎?◎?◎?◎?√√√√√√√l=m=4<n=5◎?◎?◎?◎?√√√√√√√◎?◎?◎?◎?√√√√√√√◎??◎??◎?◎?◎此問題有多個最優(yōu)解28◎??◎??◎?◎?◎此問題有多個最優(yōu)解28◎??◎??◎?◎?◎◎??◎??◎?◎?◎◎??◎??◎?◎?◎◎??◎??◎?◎?◎用匈牙利法求解下列指派問題，已知效率矩陣分別如下：用匈牙利法求解下列指派問題，已知效率矩陣分別如下：知識回顧KnowledgeReview祝您成功！知識回顧KnowledgeReview祝您成功！

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

1）表上作業(yè)法

2）匈牙利法例有四個工人和四臺不同的機(jī)床，每位工人在不同的機(jī)床上完成給定的任務(wù)的工時如表5.12所示，問安排哪位工人操作哪一臺機(jī)床可使總工時最少？任務(wù)1任務(wù)2任務(wù)3任務(wù)4工人1工人2工人3工人4215134104147314161378119舉例說明

1）表上作業(yè)法

2）匈牙利法例有四個工人和四臺獲得初始解：圈零/劃零操作將時間矩陣C的每一行都減去相應(yīng)行的最小元素和每一列都減去相應(yīng)列的最小元素，使每一行和每一列都含有零；從最少零數(shù)的行或列開始，將“零”圈起來，并劃去它所在行和所在列的其它零；反復(fù)做2），直到所有零被圈起或被劃掉為止。得到初始解。判斷是否為最優(yōu)解：圈起的零的個數(shù)是否等于n。獲得初始解：圈零/劃零操作將時間矩陣C的每一行都減去相應(yīng)行的確定調(diào)整行和列在沒有圈起的零所在行上打“√”；在打“√”行中所有零所在的列打“√”；在打“√”列中含有圈起零的行上打“√”，反復(fù)執(zhí)行2）和3）兩步，直到不能打“√”為止；用直線劃去打“√”的列和不打“√”的行，沒有劃去的行構(gòu)成調(diào)整的行，劃去的列構(gòu)成調(diào)整列。確定調(diào)整行和列在沒有圈起的零所在行上打“√”；調(diào)整可行解的方法在調(diào)整行中尋找最小的元素，將它作為調(diào)整量；將調(diào)整行各元素減去調(diào)整量，對調(diào)整列中各元素加上調(diào)整量。再次執(zhí)行“圈零”和“劃零”的操作，并循環(huán)以上的步驟，直到圈起的零數(shù)等于n為止。調(diào)整可行解的方法在調(diào)整行中尋找最小的元素，將它作為調(diào)整量；匈牙利法解例3.3時間矩陣各行各列減去最小元素后得匈牙利法解例3.3時間矩陣圈零劃零圈零劃零得最優(yōu)解將圈起的零改為1，其它元素改為0，即得最優(yōu)解如下最小總時間為22。得最優(yōu)解將圈起的零改為1，其它元素改為0，即得最優(yōu)解如下再看一例請求解如下矩陣表達(dá)的指派問題再看一例請求解如下矩陣表達(dá)的指派問題減去最小元素減去最小元素圈零劃零圈零劃零打勾劃線確定調(diào)整行和列√√√打勾劃線確定調(diào)整行和列√√√調(diào)整可行解調(diào)整可行解再圈零劃零再圈零劃零得最優(yōu)解得最優(yōu)解另一最優(yōu)解最小時間（成本）minz=32另一最優(yōu)解最小時間（成本）minz=32匈牙利算法示例匈牙利算法示例

（二）、解題步驟：

指派問題是0-1規(guī)劃的特例，也是運(yùn)輸問題的特例，當(dāng)然可用整數(shù)規(guī)劃，0-1規(guī)劃或運(yùn)輸問題的解法去求解，這就如同用單純型法求解運(yùn)輸問題一樣是不合算的。利用指派問題的特點可有更簡便的解法，這就是匈牙利法，即系數(shù)矩陣中獨立0元素的最多個數(shù)等于能覆蓋所有0元素的最少直線數(shù)。

第一步：變換指派問題的系數(shù)矩陣（cij）為(bij)，使在(bij)的各行各列中都出現(xiàn)0元素，即

(1)從（cij）的每行元素都減去該行的最小元素；

(2)再從所得新系數(shù)矩陣的每列元素中減去該列的最小元素。（二）、解題步驟：指派問題是0-1規(guī)劃的特例

第二步：進(jìn)行試指派，以尋求最優(yōu)解。在(bij)中找盡可能多的獨立0元素，若能找出n個獨立0元素，就以這n個獨立0元素對應(yīng)解矩陣(xij)中的元素為1，其余為0，這就得到最優(yōu)解。找獨立0元素，常用的步驟為：

(1)從只有一個0元素的行(列)開始，給這個0元素加圈，記作◎。然后劃去◎所在列(行)的其它0元素，記作?；這表示這列所代表的任務(wù)已指派完，不必再考慮別人了。

(2)給只有一個0元素的列(行)中的0元素加圈，記作◎；然后劃去◎所在行的0元素，記作?．

(3)反復(fù)進(jìn)行(1)，(2)兩步，直到盡可能多的0元素都被圈出和劃掉為止。第二步：進(jìn)行試指派，以尋求最優(yōu)解。(4)若仍有沒有劃圈的0元素，且同行(列)的0元素至少有兩個，則從剩有0元素最少的行(列)開始，比較這行各0元素所在列中0元素的數(shù)目，選擇0元素少的那列的這個0元素加圈(表示選擇性多的要“禮讓”選擇性少的)。然后劃掉同行同列的其它0元素?？煞磸?fù)進(jìn)行，直到所有0元素都已圈出和劃掉為止。

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

第三步：作最少的直線覆蓋所有0元素。

(1)對沒有◎的行打√號；

(2)對已打√號的行中所有含?元素的列打√號；

(3)再對打有√號的列中含◎元素的行打√號；(4)若仍有沒有劃圈的0元素，且同行(列)的0元素(4)重復(fù)(2)，(3)直到得不出新的打√號的行、列為止；

(5)對沒有打√號的行畫橫線，有打√號的列畫縱線，這就得到覆蓋所有0元素的最少直線數(shù)l。l應(yīng)等于m，若不相等，說明試指派過程有誤，回到第二步(4)，另行試指派；若l＝m<n，須再變換當(dāng)前的系數(shù)矩陣，以找到n個獨立的0元素，為此轉(zhuǎn)第四步。第四步：變換矩陣(bij)以增加0元素。在沒有被直線覆蓋的所有元素中找出最小元素，然后打√各行都減去這最小元素；打√各列都加上這最小元素（以保證系數(shù)矩陣中不出現(xiàn)負(fù)元素）。新系數(shù)矩陣的最優(yōu)解和原問題仍相同。轉(zhuǎn)回第二步。(4)重復(fù)(2)，(3)直到得不出新的打√號的行、列為例一：

任務(wù)人員ABCD甲215134乙1041415丙9141613丁78119例一：任務(wù)ABCD甲215134乙1041415249724974242◎?◎??◎◎◎?◎??◎◎

有一份中文說明書，需譯成英、日、德、俄四種文字，分別記作A、B、C、D?，F(xiàn)有甲、乙、丙、丁四人，他們將中文說明書譯成不同語種的說明書所需時間如下表所示，問如何分派任務(wù)，可使總時間最少？

任務(wù)人員ABCD甲67112乙4598丙31104丁5982例二、有一份中文說明書，需譯成英、日、德、俄求解過程如下：第一步，變換系數(shù)矩陣：－5第二步，試指派：◎◎◎??

找到3個獨立零元素但m=3<n=

4求解過程如下：－5第二步，試指派：◎◎◎??找到3個

第三步，作最少的直線覆蓋所有0元素：

◎◎◎??√√√獨立零元素的個數(shù)m等于最少直線數(shù)l，即l＝m=3<n=4；

第四步，變換矩陣(bij)以增加0元素：沒有被直線覆蓋的所有元素中的最小元素為1，然后打√各行都減