運(yùn)籌學(xué)匈牙利法PPT

1、第一張，PPT共二十六頁，創(chuàng)作于2022年6月 8 3 -2 5 0 x1 . x2. x3滿足約束條件（是 否）Z 值 (1) (2) (3) (4)( 0. 0. 0 ) ( 0. 0. 1 )( 0. 1. 0 )( 1. 0. 0 )( 0. 1. 1 )( 1. 0. 1 )( 1. 1. 0 )( 1. 1. 1 )一、01 整數(shù)規(guī)劃枚舉法 8第二張，PPT共二十六頁，創(chuàng)作于2022年6月首先，找到一個可行解，并計算其目標(biāo)函數(shù)值；然后，以其目標(biāo)值作為一個過濾條件，優(yōu)于其值的再判斷約束條件，直到找到最優(yōu)解。二、01 整數(shù)規(guī)劃隱枚舉法 8 6 1 3 3 -2 5 0 x1 . x2.

2、 x3滿足約束條件（是 否）過濾條件 (1) (2) (3) (4)( 0. 0. 0 ) ( 0. 0. 1 )( 0. 1. 0 )( 1. 0. 0 )( 0. 1. 1 )( 1. 0. 1 )( 1. 1. 0 )( 1. 1. 1 ) 8思考：如果將目標(biāo)函數(shù)變?yōu)橄率綍倪M(jìn)嗎？第三張，PPT共二十六頁，創(chuàng)作于2022年6月三、指派問題的匈牙利法指派問題（The Assignment Problem）第四張，PPT共二十六頁，創(chuàng)作于2022年6月1、指派問題的形式表述給定了一系列所要完成的任務(wù)（tasks）以及一系列完成任務(wù)的被指派者（assignees），所需要解決的問題就是要確定出

3、哪一個人被指派進(jìn)行哪一項任務(wù) 2、指派問題的假設(shè)被指派者的數(shù)量和任務(wù)的數(shù)量是相同的每一個被指派者只完成一項任務(wù) 每一項任務(wù)只能由一個被指派者來完成 每個被指派者和每項任務(wù)的組合有一個相關(guān)成本 目標(biāo)是要確定怎樣進(jìn)行指派才能使得總成本最小 第五張，PPT共二十六頁，創(chuàng)作于2022年6月設(shè)n 個人被分配去做n 件工作，每人只能完成一項任務(wù)，每項任務(wù)只能由一人完成。已知第i 個人去做第j 件工作的的效率為Cij(i=1.2n;j=1.2n)并假設(shè)Cij 0。問應(yīng)如何分配才能使總效率（ 時間或費用）最高？3、指派問題模型（The Model for Assignment Problem）第六張，PPT共

4、二十六頁，創(chuàng)作于2022年6月典型問題 例1：有一份說明書，要分別譯成英、日、德、俄四種文字，交與甲、乙、丙、丁四個人去完成，因各人專長不同，他們完成翻譯不同文字所需要的時間（小時）如表所示。規(guī)定每項工作只能交與其中的一個人完成，每個人只能完成其中的一項工作。 第七張，PPT共二十六頁，創(chuàng)作于2022年6月問：如何分配，能使所需的總時間最少？甲 乙 丙 丁工作人譯英文譯日文譯德文譯俄文2 10 9 715 4 14 813 14 16 114 15 13 9 第八張，PPT共二十六頁，創(chuàng)作于2022年6月建立模型設(shè) xij=10若第i項工作交與第j個人完成若第i項工作不交與第j個人完成譯英文：

5、x11+ x12 + x13 + x14 =1譯日文：x21+ x22 + x23 + x24 =1譯德文：x31+ x32 + x33 + x34 =1譯俄文：x41+ x42 + x43 + x44 =1甲：x11+ x21 + x31 + x41 =1乙：x12+ x22 + x32 + x42 =1丙：x13+ x23 + x33 + x43 =1?。簒14+ x24 + x34 + x44 =1xij =0或1 (i=1,2,3,4; j=1,2,3,4)甲 乙 丙 丁工作人譯英文譯日文譯德文譯俄文2 10 9 715 4 14 813 14 16 114 15 13 9 第九張，P

6、PT共二十六頁，創(chuàng)作于2022年6月4、指派問題的匈牙利解法第十張，PPT共二十六頁，創(chuàng)作于2022年6月2497第1步：變換指派問題的系數(shù)矩陣（cij），使各行各列中都出現(xiàn)0元素(1) 從（cij）的每行元素都減去該行的最小元素；(2)再從所得新系數(shù)矩陣無零元素的列中減去該列的最小元素。42第十一張，PPT共二十六頁，創(chuàng)作于2022年6月在變化后的效率矩陣中找盡可能多的獨立0元素，若能找出n個獨立0元素，就以這n個獨立0元素對應(yīng)解矩陣(xij)中的元素為1，其余為0，這就得到最優(yōu)解。第2步：進(jìn)行試指派，即確定獨立零元素（1）從有唯一的零元素的行或列開始確定獨立零元素，并用 表示，并劃掉其所在

7、行或列的其他零。直到盡可能多的零元素都被圈出和劃掉為止。0（2）若獨立零元素的數(shù)目m等于矩陣的階數(shù)n，那么這指派問題的最優(yōu)解已得到。若m n, 則轉(zhuǎn)入下一步。第十二張，PPT共二十六頁，創(chuàng)作于2022年6月第十三張，PPT共二十六頁，創(chuàng)作于2022年6月例2 有甲、乙、丙、丁四個工人，要分別派他們完成四鄉(xiāng)不同的任務(wù)，分別記作A、B、C、D。他們完成各項任務(wù)所需時間如下表所示，問如何分派任務(wù)，可使總時間最少？ 任務(wù)人員ABCD甲67112乙4598丙31104丁5982第十四張，PPT共二十六頁，創(chuàng)作于2022年6月第1步，變換系數(shù)矩陣：-5第2步，確定獨立零元素 找到 3 個獨立零元素， 但

8、m = 3 工作數(shù)時：假想工作數(shù)，使得與人數(shù)能夠匹配, 對應(yīng)的效率設(shè)定為0值。 當(dāng)工作數(shù)人數(shù)時：假想人數(shù)，使得與工作數(shù)能夠匹配, 對應(yīng)的效率設(shè)定為0值。第十九張，PPT共二十六頁，創(chuàng)作于2022年6月人數(shù)和工作數(shù)不等的指派問題第二十張，PPT共二十六頁，創(chuàng)作于2022年6月（2）一個人可做幾項工作的指派問題A1可同時做三項工作第二十一張，PPT共二十六頁，創(chuàng)作于2022年6月（3）某項工作一定不能由某人做的指派問題A1不能做B4;A3不能做B3第二十二張，PPT共二十六頁，創(chuàng)作于2022年6月（4）若目標(biāo)函數(shù)為求max z的處理(如效益） max z= - min (-z ) = - min ( z)等價于求解 min z =(-aij)xiji=1j=1 n n第二十三張，PPT共二十六頁，創(chuàng)作于2022年6月最大化指派問題最大化指派問題最大值最小化指派問題第二十四張，PPT共二十六頁，創(chuàng)作于2022年6月 學(xué)生A，B，C