運(yùn)籌學(xué)第五章整數(shù)規(guī)劃ppt課件

1、Page:1wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)管管理理運(yùn)運(yùn)籌籌學(xué)學(xué) 整整數(shù)數(shù)規(guī)規(guī)劃劃Page:2wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)第五章第五章 整數(shù)規(guī)劃整數(shù)規(guī)劃5.1 整數(shù)規(guī)劃問題的提出整數(shù)規(guī)劃問題的提出例例5-1 某廠擬用集裝箱托運(yùn)甲、乙兩種貨物。每箱的體積、分量、某廠擬用集裝箱托運(yùn)甲、乙兩種貨物。每箱的體積、分量、可獲利潤以及托運(yùn)所受限制如下表所示：可獲利潤以及托運(yùn)所受限制如下表所示：貨物 體積m3/箱） 分量kg/箱） 利潤百元/箱） 甲 5 2 20 乙 4 5 10托運(yùn)限制 24 13問兩種貨物各托運(yùn)多少箱，可使獲得的利潤最大？解：解： 設(shè)x1 , x2 分別為甲、乙

2、兩種貨物的托運(yùn)箱數(shù)，則模型為： Max z = 20 x1 +10 x2 St. 5x1 +4x2 242x1 +5 x2 13 x1 ，x2 0 x1 ，x2 整數(shù)暫不考慮整數(shù)約束，求得最優(yōu)解為x1 = 4.8 ，x2 = 0， Max z = 96Page:3wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué) Max z = 20 x1 +10 x2 St. 5x1 +4x2 242x1 +5 x2 13 x1 ，x2 0 x1 ，x2 整數(shù)（1假設(shè)x1 = 4.8 ，x2 = 0 x1 = 5 ，x2 = 0 不是可行解；（2假設(shè)x1 = 4.8 ，x2 = 0 x1 = 4，x2 = 0 是可

3、行解，但不是最優(yōu)解由于 x1 = 4，x2 = 0時，z = 80而可行解x1 = 4，x2 = 1時，z = 90Page:4wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)5.2 整數(shù)規(guī)劃的類型整數(shù)規(guī)劃的類型整數(shù)規(guī)劃按變量取值的不同，可以分為以下幾類：1. 純整數(shù)規(guī)劃：所有的變量都取整數(shù)值；2. 混合整數(shù)規(guī)劃：部分變量取整數(shù)值；3. 01規(guī)劃：所有變量只取0，1兩個值；4. 01混合規(guī)劃：部分變量只取0，1兩個值。Page:5wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)整數(shù)規(guī)劃整數(shù)規(guī)劃Integer ProgrammingInteger Programming問題的一般形式問題的一般形式max(m

4、in)zc xc xc xnn1122mnmnmmnnnnbxaxaxabxaxaxabxaxaxats).().().(. .22112222212111212111中部分或全部取整數(shù)nxxx,11Page:6wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)整數(shù)規(guī)劃與其松弛問題整數(shù)規(guī)劃與其松弛問題當(dāng)放棄整數(shù)約束時得到的線性規(guī)當(dāng)放棄整數(shù)約束時得到的線性規(guī)劃稱為整數(shù)規(guī)劃的松弛問題。劃稱為整數(shù)規(guī)劃的松弛問題。整數(shù)規(guī)劃的可行域是松弛問題的整數(shù)規(guī)劃的可行域是松弛問題的可行域，反之不成立?？尚杏?，反之不成立。Page:7wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)5.3.1 混合整數(shù)規(guī)劃的求解混合整數(shù)規(guī)劃的求解

5、-分枝定界方法分枝定界方法分枝：當(dāng)分枝：當(dāng) 不符合整數(shù)要求時，構(gòu)造不符合整數(shù)要求時，構(gòu)造兩個約束條件：兩個約束條件：iibx 1 iiiibxbx和加入松弛問題分別形成兩個子問題分枝）加入松弛問題分別形成兩個子問題分枝）定界：當(dāng)子問題獲得整數(shù)規(guī)劃的一個可行定界：當(dāng)子問題獲得整數(shù)規(guī)劃的一個可行解，則它的目標(biāo)函數(shù)值就構(gòu)成一個界限解，則它的目標(biāo)函數(shù)值就構(gòu)成一個界限5.3 整數(shù)規(guī)劃的解法整數(shù)規(guī)劃的解法Page:8wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)分枝定界法基本思想：分枝定界法基本思想：首先不考慮變量的整數(shù)約束，求解相應(yīng)的線性規(guī)劃問題：Max z = CX AX = b X 0OACDxr Ir

6、Ir+1Max z = CX AX = b xr Ir X 0Max z = CX AX = b x r Ir+1 X 0.分枝分枝每一次分枝得到的子問題的最優(yōu)目標(biāo)函數(shù)值都要比上一層問題的最優(yōu)目標(biāo)函數(shù)值小，或者相等。z0z11z12z21z22z23z24整數(shù)解下界若z21 z11，z22 z11，則無須繼續(xù)分枝定界定界利用定界，可以終止許多不必要的分枝過程。如果在分枝過程中得到新的整數(shù)解且該整數(shù)解的目標(biāo)函數(shù)值大于已如果在分枝過程中得到新的整數(shù)解且該整數(shù)解的目標(biāo)函數(shù)值大于已記錄的下界，則應(yīng)將較大的整數(shù)解的目標(biāo)函數(shù)值代替原來的下界。記錄的下界，則應(yīng)將較大的整數(shù)解的目標(biāo)函數(shù)值代替原來的下界。Pag

7、e:9wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)當(dāng)所有最低一層子問題出現(xiàn)以下三種情況時，分枝定界法終止：1. 子問題無可行解；2. 子問題已獲得整數(shù)解；3. 子問題的目標(biāo)函數(shù)值未達(dá)到下界。Page:10wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)例例取整數(shù)2121212121, 0,3121451149x . .xz maxxxxxxxxtsx132X254X1 231)310,23(AS解解S得：得：629 310,23 :21zxxAPage:11wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)132X254X1 231)310,23(AS2對對S分枝：分枝：構(gòu)造約束：構(gòu)造約束：21x和和11x形

8、成分枝問題形成分枝問題S1和和S2，得解，得解B和和CS1)37, 1 (C)923, 2(B941923);(2, :zB31037);(1, :zCPage:12wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)SA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/911x21x4629zz4941zzPage:13wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)132X254X1 231)310,23(AS2對對S1分枝：分枝：構(gòu)造約束：構(gòu)造約束：32x和和22x形成分枝問題形成分枝問題S11和和S12，得解，得解DS12)2

9、 ,(1433D14611433);,2( :zDS11無可行解無可行解Page:14wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)SA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/9S11無可行解無可行解S12D:x1=33/14,x2=2Z=61/1411x32x22x21x4941zz4629zz41461zzPage:15wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)132X254X1 231)310,23(AS2對對S12分枝：分枝：構(gòu)造約束：構(gòu)造約束：31x和和21x形成分枝問題形成分枝問題S121和和S122

10、，得解，得解E和和FS121) 1 , 3(E4);(3,1 :zES122)2 , 2(F4);(2,2 :zFPage:16wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)SA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/9S11無可行解無可行解S12D:x1=33/14,x2=2Z=61/1411x32x22x21xS122F:x1=2,x2=2Z=4S121E:x1=3,x2=1Z=431x21x4z629z4z941z4z1461z4z4zPage:17wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué) 首先求解整數(shù)規(guī)

11、劃IP對應(yīng)的松弛問題LP），假設(shè)LP的最優(yōu)解不是整數(shù)解，則逐次增加一個新約束即割平面），它能割去松弛問題可行域中不含整數(shù)解的區(qū)域.逐次切割，直到得到一個整數(shù)最優(yōu)極點(diǎn)即整數(shù)解為止。 5.3.2 純整數(shù)規(guī)劃的求解純整數(shù)規(guī)劃的求解-Gomory割平面方法割平面方法基本思想：基本思想：（1首先放棄變量的整數(shù)要求，求得線性規(guī)劃的最優(yōu)解；（2如果最優(yōu)解是一個非整數(shù)解，則構(gòu)造一個新的約束，對線性規(guī)劃問題的可行域進(jìn)行切割，切除已得到的最優(yōu)解，但保留原可行域中所有的整數(shù)解，求解新的線性規(guī)劃問題；（3如果最優(yōu)解仍不是整數(shù)解，再以增加附加約束的方法將其切除，但仍保持最初可行域中所有的整數(shù)解，直至求得一個整數(shù)最優(yōu)解為

12、止。Page:18wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)整數(shù)規(guī)劃的求解整數(shù)規(guī)劃的求解-Gomory-Gomory割平面方法割平面方法為整數(shù)x,x 0 x,x 5x2x104x5x 3x23x . . x3xzmax 212121212121ts132X2X1 22.5154整數(shù)點(diǎn)整數(shù)點(diǎn)松弛問題最優(yōu)解松弛問題最優(yōu)解Page:19wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)松弛問題的最優(yōu)解松弛問題的最優(yōu)解Page:20wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)GomoryGomory定理定理000,ijjiibxax在松弛問題的最優(yōu)單純形表中，假如有一常數(shù)在松弛問題的最優(yōu)單純形表中，假如有一常數(shù)

13、項項 不是整數(shù)，且對應(yīng)的方程為：不是整數(shù)，且對應(yīng)的方程為：0ib000000,iiijijijifNbfNa分解分解 和和 成最大整數(shù)與正分?jǐn)?shù)之和：成最大整數(shù)與正分?jǐn)?shù)之和：jia,00ibPage:21wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)000,ijjiibxax00000)(,iijjijiifNxfNxjjiiijjiixffNxNx,000000,00jjiixff那么那么包含了整數(shù)規(guī)劃的所有整數(shù)可行解，但不包括包含了整數(shù)規(guī)劃的所有整數(shù)可行解，但不包括松弛問題的最優(yōu)解。松弛問題的最優(yōu)解。Page:22wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)例題求解例題求解選擇第一個方程：選擇第一

14、個方程：7137271531xxx分解為：分解為：5317271761xxx為整數(shù)x,x 0 x,x 5x2x104x5x 3x23x . . x3xzmax 212121212121tsPage:23wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)072717653xx在原松弛問題中加入約束：在原松弛問題中加入約束：767271653xxx即即形成松弛問題形成松弛問題2Page:24wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)Page:25wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)132X2X1 22.5154整數(shù)點(diǎn)整數(shù)點(diǎn)松弛問題松弛問題2的最優(yōu)解的最優(yōu)解010727176153xxx或：割平面割平

15、面Page:26wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)選擇第四個方程具有最大分?jǐn)?shù)部分）：選擇第四個方程具有最大分?jǐn)?shù)部分）：474341645xxx分解為：分解為：64654141431xxxxPage:27wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)在松弛問題在松弛問題2中加入約束：中加入約束：即即形成松弛問題形成松弛問題3041414364xx434141764xxxPage:28wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)得到最優(yōu)解得到最優(yōu)解Page:29wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)割平面：割平面：52 1045 323767271 43414152142132165364x

16、xxxxxxxxxxxxx3221 xx132X2X1 22.5154松弛問題松弛問題3的最優(yōu)解的最優(yōu)解松弛問題松弛問題2的最優(yōu)解的最優(yōu)解Page:30wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)如果選擇第二個方程：如果選擇第二個方程：454541642xxx分解為：分解為：6464243434112xxxxxPage:31wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)在松弛問題在松弛問題2中加入約束：中加入約束：即即形成松弛問題形成松弛問題3043434164xx414343764xxxPage:32wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)3-100000 x1x2x3x4x5x6x7RHS31

17、0000101-101000-104/3000100-508/3000001-105/30 00 000101-4/31/300000-40 x3x1x2檢驗數(shù)檢驗數(shù)x5x4沒有找到整數(shù)解，沒有找到整數(shù)解，繼續(xù)做下去繼續(xù)做下去Page:33wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)5.3.3 整數(shù)規(guī)劃的圖解法整數(shù)規(guī)劃的圖解法 Max z = 20 x1 +10 x2 St. 5x1 +4x2 242x1 +5 x2 13 x1 ，x2 0 x1 ，x2 整數(shù)x1x2*Page:34wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)5.3.4 整數(shù)規(guī)劃的計算機(jī)求解整數(shù)規(guī)劃的計算機(jī)求解

18、LP OPTIMUM FOUND AT STEP 1 OBJECTIVE VALUE = 96.0000000 NEW INTEGER SOLUTION OF 90.0000076 AT BRANCH 0 PIVOT 3 BOUND ON OPTIMUM: 90.00001 ENUMERATION COMPLETE. BRANCHES= 0 PIVOTS= 3 LAST INTEGER SOLUTION IS THE BEST FOUND RE-INSTALLING BEST SOLUTION. OBJECTIVE FUNCTION VALUE 1) 90.00000 VARIABLE VAL

19、UE REDUCED COST X1 4.000000 -16.000000 X2 1.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 0.000000 3) 0.000000 2.000000 NO. ITERATIONS= 3 BRANCHES= 0 DETERM.= 1.000E 0 Max z = 20 x1 +10 x2 St. 5x1 +4x2 242x1 +5 x2 13 x1 ，x2 0 x1 ，x2 整數(shù)Max 20 x1 +10 x2 st 5x1 +4x2 24 2x1 +5x2 0 0 當(dāng)不生產(chǎn)第

20、 i 種容器，即 xi =0 目標(biāo)函數(shù)：為扣除了固定費(fèi)用后的利潤約束條件：金屬板、勞動力、機(jī)器設(shè)備的限制為避免出現(xiàn)某種容器不投入固定費(fèi)用就生產(chǎn)這樣一種不合理情況，必須加上如下約束：x1 y1 Mx2 y2 Mx3 y3 MM是充分大的數(shù)，例如，此問題中，M可取200 x1 200y1 x2 200y2 x3 200y3 Page:40wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)線性規(guī)劃模型為：目標(biāo)函數(shù)Max z = 4x1 + 5x2 + 6x3 100y1 150y2 200y3 金屬板限制2x1 + 4x2 + 8x3 500勞動力限制2x1 + 3x2 + 4x3 300機(jī)器設(shè)備限制x1

21、+ 2x2 + 3x3 100 x1 y1 Mx2 y2 Mx3 y3 Mx1 ，x2 ，x3 0y1 ，y2 ，y3 為01變量求解得：x1 =100，x2 =0，x3 =0y1 =1，y2 =0，y3 =0Page:41wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué) 例例5-5 分布系統(tǒng)設(shè)計分布系統(tǒng)設(shè)計某企業(yè)在A1 地已有一個工廠，其產(chǎn)品的生產(chǎn)能力為30千箱。為了擴(kuò)大生產(chǎn)，打算在A2 、 A3 、 A4 、 A5 地中再選擇幾個地方建廠。已知在A2 、 A3 、 A4 、 A5 地建廠的固定成本分別為175、300、375、500千元，各產(chǎn)地的產(chǎn)量及各銷地的銷量及從產(chǎn)地到銷地的單位運(yùn)價如下表所

22、示。銷地單位運(yùn)價產(chǎn)地B1 B2 B3 產(chǎn)量千箱）A1 8 4 3 30A2 5 2 3 10A3 4 3 4 20A4 9 7 5 30A5 10 4 2 40銷量千箱） 30 20 20（1問應(yīng)該在哪幾個地方建廠，在滿足銷量的前提下，使得總固定成本和總運(yùn)輸費(fèi)用之和最小；（2如果由于政策要求必須在A2 、 A3 建一個廠，應(yīng)在哪幾個地方建廠？Page:42wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)解： 設(shè) xij 為從Ai 到Bj 的運(yùn)輸量；yi =1 當(dāng)Ai 廠址被選中；0 當(dāng)Ai 廠址沒被選中Min z = 175y2 +300y3 +375y4 + 500y5 + 8x11 + 4x12

23、 + 3x13 + 5x21 + 2x22 + 3x23 + 4x31 + 3x32 + 4x33 + 9x41 + 7x42 + 5x43 + 10 x51 + 4x52 + 2x53 A1 廠的產(chǎn)量限制x11 + x12 + x13 30對于A2 、 A3 、 A4 、 A5 ，只有廠址被選中，才會有生產(chǎn)量x21 + x22 + x23 10 y2 x31 + x32 + x33 20 y3 x41 + x42 + x43 30 y4 x51 + x52 + x53 40 y5 各銷地的銷量限制x11 + x21 + x31 +x41 + x51 = 30 x12 + x22 + x32

24、+x42 + x52 = 20 x13 + x23 + x33 +x43 + x53 = 20 xij 0，為整數(shù)， yi 為01變量（1）Page:43wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)求解得： y5 =1， x52 = 20， x53 = 20， x11 = 30，其余為0，最優(yōu)目標(biāo)函數(shù)值=860（2）在上述模型上加上約束條件：y2 + y3 =1求解得： y2 =1， y4 =1， x22 = 10， x41 = 30， x12 = 10， x13 = 20，其余為0，最優(yōu)目標(biāo)函數(shù)值=940Page:44wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)0-10-1規(guī)劃的求解規(guī)劃的求解隱

25、枚舉方法隱枚舉方法10,x6 4 3 x44x22x . .523xz max3213221321321321或xxxxxxxxxtsxxPage:45wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)(x1,x2,x3)z值值過濾條件過濾條件（1） （2） （3） （4）（0，0，0）0z0（0，0，1）5z5（0，1，0）-2（0，1，1）3（1，0，0）3（1，0，1）8z8（1，1，0）1（1，1，1）6約束條件約束條件最優(yōu)解最優(yōu)解x1,x2,x3)=(1,0,1); z=8隱枚舉方法求解過程隱枚舉方法求解過程Page:46wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué) n個員工分配做個員工分配做

26、n項工作，已知項工作，已知第第i個員工做第個員工做第j項工作的成本為項工作的成本為cij，i=1,n; j=1,n。求最佳分配方。求最佳分配方案。案。4.5 指派問題與匈亞利法指派問題與匈亞利法Page:47wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)指派問題的數(shù)學(xué)模型指派問題的數(shù)學(xué)模型 0 1否則項工作員工分配做第第jixijn1in1jijijc=zMin xn,1,2,=i 1xn1jijn ,1,2,=j 1xn1iijn,1,=jn;,1,2,=i 1,0 xij或s.t.Page:48wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)nnnnnnnnccccccccccccccccC3213

27、33323122322211131211指派問題的解應(yīng)對應(yīng)于成本矩陣的不同指派問題的解應(yīng)對應(yīng)于成本矩陣的不同行與不同列，且總成本最小行與不同列，且總成本最小Page:49wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)Page:50wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)對于每個指派問題，需要有效率矩陣cij ）（cij ）= c11 c12 c1nc21 c22 c2n cn1 cn2 cnn 引入變量 xij = 1 當(dāng)指派第i 個人完成第j項任務(wù)0 當(dāng)不指派第i 個人完成第j項任務(wù)則每人的效率及目標(biāo)為c11 x11 +c12 x12 +. +c1n x1n c21 x21 +c22 x22

28、+. +c2n x2n .cn1 xn1 +cn2 xn2 +. +cnn xnn jnjjxc111jnjjxc212.njnjnjxc1ninjijijxc11 Z=Min n項任務(wù)，恰好有n個人承擔(dān)去完成。由于每人的專長不同，各人完成不同的任務(wù)效率也不同。于是就產(chǎn)生了應(yīng)指派哪個人去完成哪項任務(wù)，使完成n項任務(wù)的總效率最高。Page:51wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué) 第1項任務(wù)只能由1人完成 x11 + x21 + . xn1 = 1 第2項任務(wù)只能由1人完成 x12 + x22 + . xn2 = 1. 第j項任務(wù)只能由1人完成 x1j + x2j + . xnj = 1.

29、 第n項任務(wù)只能由1人完成 x1n + x2n + . xnn = 111iix12iix.1iijx.1iinx.1iijx(j =1, 2, , n)第1個人只能完成1項任務(wù)x11 + x12 + . x1n = 1第2個人只能完成1項任務(wù)x21 + x22 + . x2n = 1.第i個人只能完成1項任務(wù)xi1 + xi2 + . xin = 1.第n個人只能完成1項任務(wù)xn1 + xn2 + . xnn = 111jjx12jjx.1jijx.1jnjx1jijx (i =1, 2, , n) Page:52wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)故模型為ijijijxczMin 1

30、iijx(j =1, 2, , n)第j項任務(wù)只能由1人完成1jijx (i =1, 2, , n)第i個人只能完成1項任務(wù) xij = 0或1 滿足上述約束條件的可行解xij 可寫成矩陣形式，稱為解矩陣（xij ）= 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 1Page:53wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)指派問題的求解方法指派問題的求解方法（1計算機(jī)求解（2匈牙利法（3隱枚舉法Page:54wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)指派問題的性質(zhì)指派問題的性質(zhì)定理：對于指派問題，成本矩陣的任一定理：對于指派問題，成本矩陣的任一行行(或列或列)減去減去(或加上或加

31、上)一個相同的數(shù)得到一個相同的數(shù)得到的新指派問題與原問題同解。的新指派問題與原問題同解。定理：定理：系數(shù)矩陣中獨(dú)立系數(shù)矩陣中獨(dú)立0元素的最多個數(shù)等于能元素的最多個數(shù)等于能覆蓋所有覆蓋所有0元素的最少直線數(shù)。元素的最少直線數(shù)。Page:55wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)s)( s)(xcxc xs)(xcxc s)x(cxc=z n1jkjkjnki1in1jijijn1jkjn1jkjkjnki1in1jijijn1jkjkjnki1in1jijijzPage:56wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)匈牙利法的計算步驟為：第一步：使系數(shù)矩陣出現(xiàn)0元素。 第二步：進(jìn)行試指派，以

32、尋求最優(yōu)解。第三步：作最少的直線覆蓋所有的0元素，以確定該系數(shù)矩陣中能找到最 多的獨(dú)立元素數(shù)。第四步：變換矩陣增加0元素，再返回第二步。第四步說明：調(diào)整效益矩陣，使之增加一些零元素：(1) 在沒有被直線覆蓋的元素中，找出最小元素；(2) 在沒有被直線覆蓋的元素中，減去最小元素；(3) 在直線交叉處的元素中，加上最小元素；(4) 被一條直線覆蓋的元素不變. Page:57wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué) 例4-6 有一份中文說明書，需譯成英、日、德、俄四種文字，分別記作E、J、G、R?，F(xiàn)有甲、乙、丙、丁四人，他們將中文說明書翻譯成不同語種的說明書所需的時間如下表所示： 義務(wù) E J G

33、 R人員 甲 2 15 13 4 乙 10 4 14 15 丙 9 14 16 13 丁 7 8 11 9問應(yīng)指派何人去完成何工作，使所需總時間最少？解：用匈牙利法。解：用匈牙利法。第一步：使系數(shù)矩陣出現(xiàn)0元素。（cij ）= 2 15 13 4 10 4 14 15 9 14 16 13 7 8 11 9 2 4 9 7 0 13 11 2 6 0 10 110 5 7 40 1 4 24 2Page:58wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué) 0 13 11 2 6 0 10 110 5 7 40 1 4 24 20 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0 =（b

34、ij ）第二步：進(jìn)行試指派。0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0可見，m = n = 4，所以得最優(yōu)解為（xij ）= 0 0 0 1 0 1 0 01 0 0 00 0 1 0即指定甲譯俄文，乙譯日文，丙譯英文，丁譯德文，所需總時間最少。所需時間為ijijijccccxcz28min14432231Page:59wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)例例4-7 求下表所示效率矩陣的指派問題的最優(yōu)解。求下表所示效率矩陣的指派問題的最優(yōu)解。 義務(wù) A B C D E 人員 甲 12 7 9 7 9 乙 8 9 6 6 6 丙 7 17 12 14 9 丁 15 1

35、4 6 6 10 戊 4 10 7 10 9解：第一輪解：第一輪第一步：使系數(shù)矩陣出現(xiàn)0元素。 12 7 9 7 9 8 9 6 6 6 7 17 12 14 9 15 14 6 6 10 4 10 7 10 976764 5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6 3 6 5Page:60wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)第二步：進(jìn)行試指派。 5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6 3 6 5由于m = 4，n = 5，解題沒有完成。第三步：作最少的直線覆蓋所有的0元素，以確定該系數(shù)矩陣中

36、能找到最多的獨(dú)立元素不同行不同列的零元素數(shù)。 5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6 3 6 5 由于 l = 4 n = 5，轉(zhuǎn)第四步。Page:61wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)第四步：變換矩陣增加0元素。 5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6 3 6 5最小元素為270202430000835011800404143第一輪結(jié)束。 第二輪：按第二步，得70202430000835011800404143由于m = n = 5，故得最優(yōu)解，解矩陣為（xij ）= 0 1 0 0

37、0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0最優(yōu)的任務(wù)指派為：甲B；乙C；丙E；丁D；戊A。Min z = 7+6+9+6+4 = 32Page:62wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)第四步：調(diào)整效益矩陣，使之增加一些零元素：(1) 在沒有被直線覆蓋的元素中，找出最小元素；(2) 在沒有被直線覆蓋的元素中，減去最小元素；(3) 在直線交叉處的元素中，加上最小元素；(4) 被一條直線覆蓋的元素不變. Page:63wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)此問題還有一個最優(yōu)解由第二步得：70202430000835011800404143由于m =

38、n = 5，故得最優(yōu)解，解矩陣為（xij ）= 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0最優(yōu)的任務(wù)指派為：甲B；乙D；丙E；丁C；戊A。Min z = 7+6+9+6+4 = 32Page:64wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)一般指派問題一般指派問題最大化指派問題最大化指派問題人數(shù)和工作數(shù)不等的指派問題人數(shù)和工作數(shù)不等的指派問題一個人可做幾項工作的指派問題一個人可做幾項工作的指派問題某項工作一定不能由某人做的指派問題某項工作一定不能由某人做的指派問題Page:65wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)最大化指派問題最大化指

39、派問題610129610617711781296101429121215784最大化指派問題最大化指派問題最大值最大值617101712179176171017617171771711177178171217917617101714172179171217121715177178174171175811711010610958117315855210913最最小小化化指指派派問問題題Page:66wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)人數(shù)和工作數(shù)不等的指派問題人數(shù)和工作數(shù)不等的指派問題10129661771181296142912157841012966177118129614291215

40、78400000Page:67wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)一個人可做幾項工作的指派問題一個人可做幾項工作的指派問題78329824763195232154321BBBBBAAA 31952319527832982476319525432111321BBBBBAAAAAA1可同時做可同時做三項工作三項工作Page:68wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)某項工作一定不能由某人做的指派問題某項工作一定不能由某人做的指派問題452782946178298247639525432154321BBBBBAAAAA4 5 2 782 9 4 6178298247639525432154

41、321MMAAAAABBBBBA1不能做不能做B4;A3不能做不能做B3Page:69wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)例題：例題：0-10-1規(guī)劃的應(yīng)用規(guī)劃的應(yīng)用- -項目投資預(yù)項目投資預(yù)算算 資金需求資金需求(1000$) 項項 目目 估計現(xiàn)值估計現(xiàn)值 第一年第一年 第二年第二年 第三年第三年 第四年第四年 工廠擴(kuò)建工廠擴(kuò)建 90 15 20 20 15 銷售網(wǎng)點(diǎn)擴(kuò)建銷售網(wǎng)點(diǎn)擴(kuò)建 40 10 15 20 5 新生產(chǎn)流水線新生產(chǎn)流水線 10 10 0 0 4 新產(chǎn)品研究新產(chǎn)品研究 37 15 10 10 10 可用資金可用資金 40 50 40 35 Page:70wxj浙江理工大學(xué) 經(jīng)濟(jì)管理學(xué)院管理運(yùn)籌學(xué)模型模型變量假設(shè)變量假設(shè):項目沒有選中如果第選中目項第果如iixi 0