運(yùn)籌學(xué)第17講

1、第四節(jié)第四節(jié) 指派問(wèn)題指派問(wèn)題 在實(shí)際中經(jīng)常會(huì)遇到這樣的問(wèn)題，有在實(shí)際中經(jīng)常會(huì)遇到這樣的問(wèn)題，有n n 項(xiàng)不同的任項(xiàng)不同的任務(wù)，需要?jiǎng)?wù)，需要n n 個(gè)人分別完成其中的一項(xiàng)，但由于任務(wù)的個(gè)人分別完成其中的一項(xiàng)，但由于任務(wù)的性質(zhì)和各人的專長(zhǎng)不同，因此各人去完成不同的任務(wù)性質(zhì)和各人的專長(zhǎng)不同，因此各人去完成不同的任務(wù)的效率也就不同。于是產(chǎn)生了一個(gè)問(wèn)題，應(yīng)指派哪個(gè)的效率也就不同。于是產(chǎn)生了一個(gè)問(wèn)題，應(yīng)指派哪個(gè)人去完成哪項(xiàng)任務(wù)，使完成人去完成哪項(xiàng)任務(wù)，使完成 n n 項(xiàng)任務(wù)的總效率最高，項(xiàng)任務(wù)的總效率最高，這類問(wèn)題稱為指派問(wèn)題或分派問(wèn)題。這類問(wèn)題稱為指派問(wèn)題或分派問(wèn)題。 如果完成任務(wù)的效率表現(xiàn)為資源消耗

2、，考慮的是如果完成任務(wù)的效率表現(xiàn)為資源消耗，考慮的是如何分配任務(wù)使得目標(biāo)極小化；如果完成任務(wù)的效率如何分配任務(wù)使得目標(biāo)極小化；如果完成任務(wù)的效率表現(xiàn)為生產(chǎn)效率的高低，則考慮的是如何分配使得目表現(xiàn)為生產(chǎn)效率的高低，則考慮的是如何分配使得目標(biāo)函數(shù)極大化。標(biāo)函數(shù)極大化。 利用不同資源完成不同計(jì)劃活動(dòng)的效率通常用表利用不同資源完成不同計(jì)劃活動(dòng)的效率通常用表格形式表示為效率表，表格中數(shù)字組成格形式表示為效率表，表格中數(shù)字組成效率矩陣效率矩陣。例例1 1、 有一份中文說(shuō)明書，需譯成英、日、德、俄四種有一份中文說(shuō)明書，需譯成英、日、德、俄四種文字，分別記作文字，分別記作A A、B B、C C、D D?，F(xiàn)有甲

3、、乙、丙、丁四。現(xiàn)有甲、乙、丙、丁四人，他們將中文說(shuō)明書譯成不同語(yǔ)種的說(shuō)明書所需時(shí)人，他們將中文說(shuō)明書譯成不同語(yǔ)種的說(shuō)明書所需時(shí)間如下表所示，問(wèn)如何分派任務(wù)，可使總時(shí)間最少？間如下表所示，問(wèn)如何分派任務(wù)，可使總時(shí)間最少？ 任務(wù)任務(wù)人員人員ABCD甲甲67112乙乙4598丙丙31104丁丁5982一、指派問(wèn)題的數(shù)學(xué)模型一、指派問(wèn)題的數(shù)學(xué)模型設(shè)決策變量設(shè)決策變量 1 1 分配第分配第i i 個(gè)人譯第個(gè)人譯第j j 件語(yǔ)言件語(yǔ)言 xij = 0 相反相反 ( i,j=1.2.3.4)其數(shù)學(xué)模型為：其數(shù)學(xué)模型為： )4.3.2.1,1(0)4.3.2.1( 1)4.3.2.1( 1min414141

4、41jixjxixxcZijiijjijijijij或一般指派問(wèn)題一般指派問(wèn)題 設(shè)設(shè)n n 個(gè)人被分配去做個(gè)人被分配去做n n 件工作，規(guī)定每個(gè)人只做件工作，規(guī)定每個(gè)人只做一件工作，每件工作只有一個(gè)人去做。已知第一件工作，每件工作只有一個(gè)人去做。已知第I I 個(gè)人個(gè)人去做第去做第j j 件工作的的效率（件工作的的效率（ 時(shí)間或費(fèi)用）為時(shí)間或費(fèi)用）為C Cijij( (i i=1.2=1.2n n; ;j j=1.2=1.2n n) )并假設(shè)并假設(shè)C Cijij 0 0。問(wèn)應(yīng)如何分。問(wèn)應(yīng)如何分配才能使總效率（配才能使總效率（ 時(shí)間或費(fèi)用）最高？時(shí)間或費(fèi)用）最高？設(shè)決策變量設(shè)決策變量 1 分配第分

5、配第i 個(gè)人去做第個(gè)人去做第j 件工作件工作 xij = 0 相反相反 ( i,j=1.2. n )標(biāo)準(zhǔn)形式指派問(wèn)標(biāo)準(zhǔn)形式指派問(wèn)題數(shù)學(xué)模型為：題數(shù)學(xué)模型為： ).2.1,1(0).2.1( 1).2.1( 1min1111njixnjxnixxcZijniijnjijninjijij或或二、指派問(wèn)題的解法二、指派問(wèn)題的解法 匈牙利法匈牙利法 匈牙利數(shù)學(xué)家克尼格匈牙利數(shù)學(xué)家克尼格（ Konig ）求解指派問(wèn)題的求解指派問(wèn)題的計(jì)算方法被稱為匈牙利法計(jì)算方法被稱為匈牙利法，他證明了如下兩個(gè)定理：他證明了如下兩個(gè)定理： 指派問(wèn)題是指派問(wèn)題是0-1 規(guī)劃的特例，也是運(yùn)輸問(wèn)題的特例，規(guī)劃的特例，也是運(yùn)輸問(wèn)

6、題的特例，當(dāng)然可用整數(shù)規(guī)劃，當(dāng)然可用整數(shù)規(guī)劃，0-1 規(guī)劃或運(yùn)輸問(wèn)題的解法去求規(guī)劃或運(yùn)輸問(wèn)題的解法去求解，這就如同用單純型法求解運(yùn)輸問(wèn)題一樣是不合算解，這就如同用單純型法求解運(yùn)輸問(wèn)題一樣是不合算的。利用指派問(wèn)題的特點(diǎn)可有更簡(jiǎn)便的解法，這就是的。利用指派問(wèn)題的特點(diǎn)可有更簡(jiǎn)便的解法，這就是匈牙利法匈牙利法 定理定理1 1 如果從分配問(wèn)題效率矩陣如果從分配問(wèn)題效率矩陣 a aijij 的每一行的每一行元素中分別減去（或加上）一個(gè)常數(shù)元素中分別減去（或加上）一個(gè)常數(shù) u ui i ( (被稱為該被稱為該行的位勢(shì)行的位勢(shì)) )，從每一列分別減去（或加上）一個(gè)常數(shù)，從每一列分別減去（或加上）一個(gè)常數(shù) v

7、vj j（被稱為該列的位勢(shì)），得到一個(gè)新的效率矩陣（被稱為該列的位勢(shì)），得到一個(gè)新的效率矩陣 b bijij ，若其中，若其中 b bij ij = = a aijij- -u ui i- -v vj j，則，則 b bijij 的最優(yōu)解的最優(yōu)解等價(jià)于等價(jià)于 a aijij 的最優(yōu)解。的最優(yōu)解。 定理定理2 2 若矩陣若矩陣 A A 的元素可分成的元素可分成“ 0 0 ”與非與非“ 0 0 ”兩部分，則覆蓋兩部分，則覆蓋“ 0 0 ”元素的最少直線數(shù)等于位于元素的最少直線數(shù)等于位于不同行不同列的不同行不同列的“ 0 0 ”元素的最大個(gè)數(shù)。元素的最大個(gè)數(shù)。 第一步：變換指派問(wèn)題的系數(shù)矩陣第一步：

8、變換指派問(wèn)題的系數(shù)矩陣（cij）為為(bij)，使使在在(bij)的各行各列中都出現(xiàn)的各行各列中都出現(xiàn)0 0元素，即元素，即 (1) (1) 從從（cij）的每行元素都減去該行的最小元素；的每行元素都減去該行的最小元素； (2) (2) 再?gòu)乃眯孪禂?shù)矩陣的每列元素中減去該列的再?gòu)乃眯孪禂?shù)矩陣的每列元素中減去該列的最小元素。最小元素。 第二步：進(jìn)行試指派，以尋求最優(yōu)解。第二步：進(jìn)行試指派，以尋求最優(yōu)解。 在在(bij)中找盡可能多的獨(dú)立中找盡可能多的獨(dú)立0元素元素( (不同行不同列不同行不同列) )，若能找出若能找出n n個(gè)獨(dú)立個(gè)獨(dú)立0元素，就以這元素，就以這n個(gè)獨(dú)立個(gè)獨(dú)立0元素對(duì)應(yīng)解元素對(duì)

9、應(yīng)解矩陣矩陣(xij)中的元素為中的元素為1，其余為其余為0，這就得到最優(yōu)解。找這就得到最優(yōu)解。找獨(dú)立獨(dú)立0 0元素，常用的步驟為：元素，常用的步驟為： (1)(1)從只有一個(gè)從只有一個(gè)0元素的行元素的行( (列列) )開始，給這個(gè)開始，給這個(gè)0元素元素加圈，記作加圈，記作 。然后劃去然后劃去 所在列所在列( (行行) )的其它的其它0元素，元素，記作記作 ；這表示這列所代表的任務(wù)已指派完，不必再這表示這列所代表的任務(wù)已指派完，不必再考慮別人了?？紤]別人了。 (2)(2)給只有一個(gè)給只有一個(gè)0 0元素的列元素的列( (行行) )中的中的0 0元素加圈，記作元素加圈，記作；然后劃去然后劃去 所在

10、行的所在行的0 0元素，記作元素，記作 (3)(3)反復(fù)進(jìn)行反復(fù)進(jìn)行(1)(1)，(2)(2)兩步，直到盡可能多的兩步，直到盡可能多的0 0元素元素都被圈出和劃掉為止都被圈出和劃掉為止。 (4)(4)若仍有沒(méi)有劃圈的若仍有沒(méi)有劃圈的0 0元素，且同行元素，且同行( (列列) )的的0 0元素元素至少有兩個(gè)，則從剩有至少有兩個(gè)，則從剩有0 0元素最少的行元素最少的行( (列列) )開始，比較開始，比較這行各這行各0 0元素所在列中元素所在列中0 0元素的數(shù)目，選擇元素的數(shù)目，選擇0 0元素少的那元素少的那列的這個(gè)列的這個(gè)0 0元素加圈元素加圈( (表示選擇性多的要表示選擇性多的要“禮讓禮讓”選擇

11、選擇性少的性少的) )。然后劃掉同行同列的其它。然后劃掉同行同列的其它0 0元素?？煞磸?fù)進(jìn)元素。可反復(fù)進(jìn)行，直到所有行，直到所有0 0元素都已圈出和劃掉為止。元素都已圈出和劃掉為止。 （5 5）若）若 元素的數(shù)目元素的數(shù)目m m 等于矩陣的階數(shù)等于矩陣的階數(shù)n n，那么這，那么這指派問(wèn)題的最優(yōu)解已得到。若指派問(wèn)題的最優(yōu)解已得到。若m m n n, , 則轉(zhuǎn)入下一步。則轉(zhuǎn)入下一步。 第三步：作最少的直線覆蓋所有第三步：作最少的直線覆蓋所有0 0元素。元素。 (1)(1)對(duì)沒(méi)有對(duì)沒(méi)有的行打的行打號(hào)；號(hào)； (2)(2)對(duì)已打?qū)σ汛蛱?hào)的行中所有含號(hào)的行中所有含元素的列打元素的列打號(hào)；號(hào)； (3)(3)

12、再對(duì)打有再對(duì)打有號(hào)的列中含號(hào)的列中含 元素的行打元素的行打號(hào)；號(hào)； (4)(4)重復(fù)重復(fù)(2)(2)，(3)(3)直到得不出新的打直到得不出新的打號(hào)的行、列號(hào)的行、列為止；為止； (5)(5)對(duì)沒(méi)有打?qū)](méi)有打號(hào)的行畫橫線，有打號(hào)的行畫橫線，有打號(hào)的列畫縱號(hào)的列畫縱線，這就得到覆蓋所有線，這就得到覆蓋所有0 0元素的最少直線數(shù)元素的最少直線數(shù) l 。l 應(yīng)等應(yīng)等于于m m，若不相等，說(shuō)明試指派過(guò)程有誤，回到第二步，若不相等，說(shuō)明試指派過(guò)程有誤，回到第二步(4)(4)，另行試指派；若，另行試指派；若 lm nm n，須再變換當(dāng)前的系，須再變換當(dāng)前的系數(shù)矩陣，以找到數(shù)矩陣，以找到n n個(gè)獨(dú)立的個(gè)獨(dú)立

13、的0 0元素，為此轉(zhuǎn)第四步。元素，為此轉(zhuǎn)第四步。第四步：變換矩陣第四步：變換矩陣( (b bijij) )以增加以增加0 0元素。元素。在沒(méi)有被直線覆蓋的所有元素中找出最小元素，在沒(méi)有被直線覆蓋的所有元素中找出最小元素，然后未被直線覆蓋的元素都減去這最小元素；被然后未被直線覆蓋的元素都減去這最小元素；被直線覆蓋兩次的元素加上這最小元素（以保證系直線覆蓋兩次的元素加上這最小元素（以保證系數(shù)矩陣中不出現(xiàn)負(fù)元素），其他不變。新系數(shù)矩?cái)?shù)矩陣中不出現(xiàn)負(fù)元素），其他不變。新系數(shù)矩陣的最優(yōu)解和原問(wèn)題仍相同。轉(zhuǎn)回第二步。陣的最優(yōu)解和原問(wèn)題仍相同。轉(zhuǎn)回第二步。 例例1 1、 有一份中文說(shuō)明書，需譯成英、日、德、

14、俄四種有一份中文說(shuō)明書，需譯成英、日、德、俄四種文字，分別記作文字，分別記作A A、B B、C C、D D?，F(xiàn)有甲、乙、丙、丁四?，F(xiàn)有甲、乙、丙、丁四人，他們將中文說(shuō)明書譯成不同語(yǔ)種的說(shuō)明書所需時(shí)人，他們將中文說(shuō)明書譯成不同語(yǔ)種的說(shuō)明書所需時(shí)間如下表所示，問(wèn)如何分派任務(wù)，可使總時(shí)間最少？間如下表所示，問(wèn)如何分派任務(wù)，可使總時(shí)間最少？ 任務(wù)任務(wù)人員人員ABCD甲甲67112乙乙4598丙丙31104丁丁5982求解過(guò)程如下：求解過(guò)程如下：第一步，變換系數(shù)矩陣：第一步，變換系數(shù)矩陣：2142 289541013895421176)( ijc 0673390245100954 01733402401

15、004545第二步，試指派：第二步，試指派：找到找到 3 3 個(gè)獨(dú)立零元素個(gè)獨(dú)立零元素 但但 m m = 3 3 n = 4 00102350960607130 2410475011100621113042 00102350960607130 0100000100101000 第三步，作最少的直線覆蓋所有第三步，作最少的直線覆蓋所有0 0元素：元素：立零元素的個(gè)數(shù)獨(dú)立零元素的個(gè)數(shù)m m等于最少直線數(shù)等于最少直線數(shù)l，即即lm=3n=4； 第四步，變換矩陣第四步，變換矩陣( (bij) )以增加以增加0 0元素：沒(méi)有被直線覆蓋元素：沒(méi)有被直線覆

16、蓋的所有元素中的最小元素為的所有元素中的最小元素為1 1，然后打，然后打各行都減去各行都減去1 1；打打各列都加上各列都加上1 1，得如下矩陣，并轉(zhuǎn)第二步進(jìn)行試指，得如下矩陣，并轉(zhuǎn)第二步進(jìn)行試指派：派： 6244251343000 0 00 0100001000011000得到得到4 4個(gè)獨(dú)個(gè)獨(dú)立零元素，立零元素， 所以最優(yōu)解所以最優(yōu)解矩陣為：矩陣為：0624425134315 6244251343 三、非標(biāo)準(zhǔn)的指派問(wèn)題三、非標(biāo)準(zhǔn)的指派問(wèn)題 1. 1. 指派問(wèn)題中人數(shù)和工作任務(wù)不相等時(shí)指派問(wèn)題中人數(shù)和工作任務(wù)不相等時(shí) 當(dāng)人數(shù)多于工作任務(wù)數(shù)時(shí)，可以添加假想任務(wù)使當(dāng)人數(shù)多

17、于工作任務(wù)數(shù)時(shí)，可以添加假想任務(wù)使得人數(shù)與工作任務(wù)數(shù)相同，因?yàn)楣ぷ魅蝿?wù)是假想的，得人數(shù)與工作任務(wù)數(shù)相同，因?yàn)楣ぷ魅蝿?wù)是假想的，因此完成這些任務(wù)的時(shí)間是零。當(dāng)任務(wù)數(shù)多于人數(shù)時(shí)，因此完成這些任務(wù)的時(shí)間是零。當(dāng)任務(wù)數(shù)多于人數(shù)時(shí)，可添加假想的人。這樣的方法和運(yùn)輸問(wèn)題中處理的方可添加假想的人。這樣的方法和運(yùn)輸問(wèn)題中處理的方法類似。法類似。 2. 2. 當(dāng)問(wèn)題目標(biāo)變?yōu)榍髽O大時(shí)當(dāng)問(wèn)題目標(biāo)變?yōu)榍髽O大時(shí)mimjijijxaz11max可改寫為可改寫為mimjijijxaz11)(min此時(shí)效率矩陣中元素都變?yōu)榱素?fù)值，可利用定理此時(shí)效率矩陣中元素都變?yōu)榱素?fù)值，可利用定理1 1，使效率矩陣中全部元素都變?yōu)榉秦?fù)的，就

18、可以利用匈使效率矩陣中全部元素都變?yōu)榉秦?fù)的，就可以利用匈牙利法進(jìn)行求解。牙利法進(jìn)行求解。 3. 3. 某某“任務(wù)任務(wù)”一定不能由某一定不能由某“人員人員”做的指派問(wèn)題做的指派問(wèn)題對(duì)于極小化的指派問(wèn)題，某對(duì)于極小化的指派問(wèn)題，某“任務(wù)任務(wù)”一定不能由某一定不能由某“人員人員”做的指派問(wèn)題，可令相應(yīng)效率系數(shù)為充分大做的指派問(wèn)題，可令相應(yīng)效率系數(shù)為充分大的的M M一、案例分析一、案例分析二、二、WINQSB軟件應(yīng)用軟件應(yīng)用第五節(jié)第五節(jié) 案例分析及案例分析及WINQSB軟件應(yīng)用軟件應(yīng)用人力資源分配問(wèn)題人力資源分配問(wèn)題 某個(gè)中型百貨商場(chǎng)對(duì)售貨人員（周工資某個(gè)中型百貨商場(chǎng)對(duì)售貨人員（周工資200200元）

19、的需求經(jīng)統(tǒng)計(jì)如下表元）的需求經(jīng)統(tǒng)計(jì)如下表 為了保證銷售人員充分休息，銷售人員為了保證銷售人員充分休息，銷售人員每周工作每周工作5 5天，休息天，休息2 2天。問(wèn)應(yīng)如何安排銷天。問(wèn)應(yīng)如何安排銷售人員的工作時(shí)間，使得所配售貨人員的售人員的工作時(shí)間，使得所配售貨人員的總費(fèi)用最??？總費(fèi)用最??？星期星期一一二二三三四四五五六六七七人數(shù)人數(shù)1212151512121414161618181919模型假設(shè)模型假設(shè)每天工作每天工作8 8小時(shí)，不考慮夜班的情況；小時(shí)，不考慮夜班的情況；每個(gè)人的休息時(shí)間為連續(xù)的兩天時(shí)間；每個(gè)人的休息時(shí)間為連續(xù)的兩天時(shí)間；每天安排的人員數(shù)不得低于需求量，但可以每天安排的人員數(shù)不得低

20、于需求量，但可以超過(guò)需求量超過(guò)需求量問(wèn)題分析問(wèn)題分析因素：不可變因素：需求量、休息時(shí)間、單位費(fèi)用；因素：不可變因素：需求量、休息時(shí)間、單位費(fèi)用；可變因素：安排的人數(shù)、每人工作的時(shí)間、總費(fèi)用可變因素：安排的人數(shù)、每人工作的時(shí)間、總費(fèi)用方案：確定每天工作的人數(shù)，由于連續(xù)休息方案：確定每天工作的人數(shù)，由于連續(xù)休息2 2天，當(dāng)確天，當(dāng)確定每個(gè)人開始休息的時(shí)間就等于知道工作的時(shí)間，定每個(gè)人開始休息的時(shí)間就等于知道工作的時(shí)間，因而確定每天開始休息的人數(shù)就知道每天開始工作因而確定每天開始休息的人數(shù)就知道每天開始工作的人數(shù)，從而求出每天工作的人數(shù)。的人數(shù)，從而求出每天工作的人數(shù)。變量：每天開始休息的人數(shù)變量：

21、每天開始休息的人數(shù) 約束條件約束條件 ： 1.1.每人休息時(shí)間每人休息時(shí)間2 2天，自然滿足。天，自然滿足。 3.3.變量非負(fù)約束：變量非負(fù)約束：7,.,2 , 1, 0ixi 目標(biāo)函數(shù)：總費(fèi)用最小，總費(fèi)用與使用的總目標(biāo)函數(shù)：總費(fèi)用最小，總費(fèi)用與使用的總?cè)藬?shù)成正比。由于每個(gè)人必然在且僅在某人數(shù)成正比。由于每個(gè)人必然在且僅在某一天開始休息，所以總?cè)藬?shù)等于一天開始休息，所以總?cè)藬?shù)等于模型模型7,.,2 , 1, 019181614121512. .200min5432174321763217652117654765436543271ixxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxtsxiii ?；@球隊(duì)教練要確定比賽的首發(fā)陣容。全隊(duì)共有?；@球隊(duì)教練要確定比賽的首發(fā)陣容。全隊(duì)共有7 7名球員，根名球員，根據(jù)技術(shù)水平，對(duì)每名運(yùn)動(dòng)員的控球（據(jù)技術(shù)水平，對(duì)每名運(yùn)動(dòng)員的控球（ball-handingball-handing）、投籃）、投籃（shootingshooting）、藍(lán)板（）、藍(lán)板（rebounding