運籌學(xué)目標(biāo)規(guī)劃與整數(shù)規(guī)劃ppt課件

1、Page:1QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)運運籌籌學(xué)學(xué)目目的的規(guī)規(guī)劃劃Page:2QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)多目的決策問題多目的決策問題實踐問題決策經(jīng)常面臨的問題：實踐問題決策經(jīng)常面臨的問題：方案優(yōu)劣并不以單一準那么為目的，而是以多重準那么為方案優(yōu)劣并不以單一準那么為目的，而是以多重準那么為目的目的約束條件并不完全符合嚴厲的剛性條件，具有一定的彈性約束條件并不完全符合嚴厲的剛性條件，具有一定的彈性能夠的彈性約束：能夠的彈性約束：最好等于最好等于最好不大于最好不大于最好不小于最好不小于Page:3QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)彈性約束的處置方法彈性約束的處置方法實踐量

2、 dd+ = 目的值負偏向變量負偏向變量正偏向變量正偏向變量 ddMin 最好等于：最好等于：dMin 最好不大于：最好不大于：dMin 最好不小于：最好不小于：Page:4QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)顧客訪問戰(zhàn)略顧客訪問戰(zhàn)略 老顧客老顧客 新顧客新顧客 正?？捎迷L問時間正?？捎迷L問時間 訪問每一顧客所需時間訪問每一顧客所需時間 2 3 640 小時小時 平均可獲銷售利潤平均可獲銷售利潤 250 125 目的：目的：訪問時間最好不超越訪問時間最好不超越680680小時；小時；訪問時間最好不少于訪問時間最好不少于600600小時；小時；銷售收入盡量不少于銷售收入盡量不少于70,0007

3、0,000；訪問老顧客數(shù)最好不少于訪問老顧客數(shù)最好不少于200200個；個；訪問新顧客數(shù)最好不少于訪問新顧客數(shù)最好不少于120120個個Page:5QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)模型顧客訪問戰(zhàn)略模型顧客訪問戰(zhàn)略0 120 200000,70125250 60032 68032 5524413321222111215544332211所有變量ddxddxddxxddxxddxxStdPdPdPdPdPZMinPage:6QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)目的規(guī)劃解的幾何分析目的規(guī)劃解的幾何分析X100300200600500400X21002003004005001(1)1d1d(2

4、)2d2d(3)3d3d(4)4d4d(5)5d5dPage:7QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)0 120 200000,70125250 60032 68032 5524413321222111215544332211所有變量ddxddxddxxddxxddxxStdPdPdPdPdPZMin目的規(guī)劃的求解目的規(guī)劃的求解-序貫算法序貫算法Page:8QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)068032 11211所有變量ddxxStdZMin068032 0 211所有變量xxd第一級目的第一級目的X100300200600500400X21002003004005001(1)1d1dP

5、age:9QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué) 060032 68032 2221212所有變量ddxxxxStdZMin第二級目的第二級目的06003268032 0 21212所有變量xxxxdX100300200600500400X21002003004005001(1)1d1d(2)2d2dPage:10QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)第三級目的第三級目的 0000,701252506003268032 0 2121213所有變量xxxxxxdX100300200600500400X21002003004005001(1)1d1d(2)2d2d(3)3d3d 0 000,701

6、25250 60032 68032 332121213所有變量ddxxxxxxStdZMinPage:11QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)X100300200600500400X21002003004005001(1)1d1d(2)2d2d(3)3d3d(4)4d4d 0 200000,70125250 60032 68032 4412121214所有變量ddxxxxxxxStdZMin第四級目的第四級目的 0200000,701252506003268032 0 12121214所有變量xxxxxxxdPage:12QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)X100300200600500

7、400X21002003004005001(1)1d1d(2)2d2d(3)3d3d(4)4d4d(5)5d5d第五級目的第五級目的Page:13QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)目的規(guī)劃的求解目的規(guī)劃的求解-多階段算法多階段算法0 120 200000,70125250 60032 68032 5524413321222111215544332211所有變量ddxddxddxxddxxddxxStdPdPdPdPdPZMinPage:14QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)初始單純形表初始單純形表000P1P20P30P40P50 x1x2d1-d1+d2-d2+d3-d3+d4-d4

8、+d5-d5+RHS比值比值0231-100000000680680/3P223001-1000000600600/3P325012500001-100007000070000/125P4100000001-100200-P501000000001-1120120/1P1000100000000P2-2-30001000000P3-250 -1250000010000P4-100000000100P50-10000000001d3-d1-d2-d4-d5-檢驗數(shù)檢驗數(shù)Page:15QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)單純形表運算單純形表運算000P1P20P30P40P50 x1x2d1-d

9、1+d2-d2+d3-d3+d4-d4+d5-d5+RHS比值比33320320/3P220001-10000-33240240/3P3250000001-100-1251255500055000/125P4100000001-100200-001000000001-1120-P1000100000000P2-20000100003-3P3-250000000100125-125P4-100000000100P5000000000010d3-d1-d2-d4-x2檢驗數(shù)檢驗數(shù)Page:16QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)單純形表運算單純形表運算000P1P20

10、P30P40P50 x1x2d1-d1+d2-d2+d3-d3+d4-d4+d5-d5+RHS比值比值0001-1-1100000080-02/30001/3 -1/30000-118080/(2/3)P3500/3000-125/3-125/31-100004500045000/(500/3)P4100000001-100200200/102/31001/3 -1/3000000200200/(2/3)P1000100000000P2000011000000P3-500/3000125/3125/3010000P4-100000000100P5000000000010d3-d1-d5+d4-

11、x2檢驗數(shù)檢驗數(shù)Page:17QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)運運籌籌學(xué)學(xué)整整數(shù)數(shù)線線性性規(guī)規(guī)劃劃Page:18QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)整數(shù)線性規(guī)劃問題的普通方式整數(shù)線性規(guī)劃問題的普通方式max(min)zc xc xc xnn1122mnmnmmnnnnbxaxaxabxaxaxabxaxaxats).().().(. .22112222212111212111中部分或全部取整數(shù)nxxx,11Page:19QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)整數(shù)線性規(guī)劃問題的分類整數(shù)線性規(guī)劃問題的分類全整數(shù)線性規(guī)劃全整數(shù)線性規(guī)劃混合整數(shù)線性規(guī)劃混合整數(shù)線性規(guī)劃0-1整數(shù)線性規(guī)劃整數(shù)線性

12、規(guī)劃Page:20QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)整數(shù)規(guī)劃與其松弛問題整數(shù)規(guī)劃與其松弛問題當(dāng)放棄整數(shù)約束時得到的線性規(guī)當(dāng)放棄整數(shù)約束時得到的線性規(guī)劃稱為整數(shù)規(guī)劃的松弛問題。劃稱為整數(shù)規(guī)劃的松弛問題。整數(shù)規(guī)劃的可行域是松弛問題的整數(shù)規(guī)劃的可行域是松弛問題的可行域，反之不成立。可行域，反之不成立。Page:21QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)全整數(shù)規(guī)劃的求解全整數(shù)規(guī)劃的求解-Gomory-Gomory割平面方割平面方法法為整數(shù)x,x 0 x,x 5x2x104x5x 3x23x . . x3xzmax 212121212121ts132X2X1 22.5154整數(shù)點整數(shù)點松弛問題最優(yōu)解

13、松弛問題最優(yōu)解Page:22QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)松弛問題的最優(yōu)解松弛問題的最優(yōu)解3-1000 x1x2x3x4x5RHS3101/702/713/7-101-2/703/79/7000-3/7122/731/700-5/70-3/7x4x1x2檢驗數(shù)檢驗數(shù)Page:23QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)GomoryGomory定理定理000,ijjiibxax在松弛問題的最優(yōu)單純形表中，假設(shè)有一常數(shù)在松弛問題的最優(yōu)單純形表中，假設(shè)有一常數(shù)項項 不是整數(shù)，且對應(yīng)的方程為：不是整數(shù)，且對應(yīng)的方程為：0ib000000,iiijijijifNbfNa分解分解 和和 成最大整數(shù)與

14、正分數(shù)之和：成最大整數(shù)與正分數(shù)之和：jia,00ibPage:24QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)000,ijjiibxax00000)(,iijjijiifNxfNxjjiiijjiixffNxNx,000000,00jjiixff那么那么包含了整數(shù)規(guī)劃的一切整數(shù)可行解，但不包括包含了整數(shù)規(guī)劃的一切整數(shù)可行解，但不包括松弛問題的最優(yōu)解松弛問題的最優(yōu)解Page:25QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)例題求解例題求解選擇第一個方程：選擇第一個方程：7137271531xxx分解為：分解為：5317271761xxxPage:26QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)072717653x

15、x在原松弛問題中參與約束：在原松弛問題中參與約束：767271653xxx即即構(gòu)成松弛問題構(gòu)成松弛問題2Page:27QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)3-10000 x1x2x3x4x5x6RHS3101/702/7013/7-101-2/703/709/7000-3/7122/7031/7000-1/70-2/71-6/700-5/70-3/70 x4x1x2檢驗數(shù)檢驗數(shù)x63-10000 x1x2x3x4x5x6RHS31000011-1010-1/40-5/45/40001-1/20-11/25/200001/41-3/47/4000-1/40-17/4x3x1x2檢驗數(shù)檢驗數(shù)x5

16、Page:28QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)132X2X1 22.5154整數(shù)點整數(shù)點松弛問題松弛問題2的最優(yōu)解的最優(yōu)解010727176153xxx或：割平面割平面Page:29QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)選擇第四個方程具有最大分數(shù)部分：選擇第四個方程具有最大分數(shù)部分：474341645xxx分解為：分解為：64654141431xxxxPage:30QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)在松弛問題在松弛問題2中參與約束：中參與約束：即即構(gòu)成松弛問題構(gòu)成松弛問題3041414364xx434141764xxxPage:31QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)3-10000

17、0 x1x2x3x4x5x6x7RHS310000101-1010-1/40-5/405/40001-1/20-11/205/200001/41-3/407/40 00 000-1/40-1/41 1-3/4000-1/40-17/40 x3x1x2檢驗數(shù)檢驗數(shù)x5x73-100000 x1x2x3x4x5x6x7RHS310000101-101000-1-12000100-5-24000001-1110 00 000101-4300000-40 x3x1x2檢驗數(shù)檢驗數(shù)x5x7得到最優(yōu)解得到最優(yōu)解Page:32QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)割平面：割平面：52 1045 323767

18、271 43414152142132165364xxxxxxxxxxxxxx3221 xx132X2X1 22.5154松弛問題松弛問題3的最優(yōu)解的最優(yōu)解松弛問題松弛問題2的最優(yōu)解的最優(yōu)解Page:33QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)假設(shè)選擇第二個方程：假設(shè)選擇第二個方程：454541642xxx分解為：分解為：6464243434112xxxxxPage:34QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)在松弛問題在松弛問題2中參與約束：中參與約束：即即構(gòu)成松弛問題構(gòu)成松弛問題3043434164xx414343764xxxPage:35QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)3-100000

19、x1x2x3x4x5x6x7RHS310000101-1010-1/40-5/405/40001-1/20-11/205/200001/41-3/407/40 00 000-3/40-3/41 1-1/4000-1/40-17/40 x3x1x2檢驗數(shù)檢驗數(shù)x5x73-100000 x1x2x3x4x5x6x7RHS310000101-101000-104/3000100-508/3000001-105/30 00 000101-4/31/300000-40 x3x1x2檢驗數(shù)檢驗數(shù)x5x4沒有找到整數(shù)解，沒有找到整數(shù)解，繼續(xù)做下去繼續(xù)做下去Page:36QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)

20、混合整數(shù)規(guī)劃的求解混合整數(shù)規(guī)劃的求解-分枝定界方法分枝定界方法分枝：當(dāng)分枝：當(dāng) 不符合整數(shù)要求時，構(gòu)造不符合整數(shù)要求時，構(gòu)造兩個約束條件：兩個約束條件：iibx 1 iiiibxbx和參與松弛問題分別構(gòu)成兩個子問題分枝參與松弛問題分別構(gòu)成兩個子問題分枝定界：當(dāng)子問題獲得整數(shù)規(guī)劃的一個可行定界：當(dāng)子問題獲得整數(shù)規(guī)劃的一個可行解，那么它的目的函數(shù)值就構(gòu)成一個界限解，那么它的目的函數(shù)值就構(gòu)成一個界限Page:37QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)例例取整數(shù)2121212121, 0,3121451149x . .xz maxxxxxxxxtsx132X254X1 231)310,23(AS解解S

21、得：得：941 310,23 :21zxxAPage:38QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)132X254X1 231)310,23(AS2對對S分枝：分枝：構(gòu)造約束：構(gòu)造約束：21x和和11x構(gòu)成分枝問題構(gòu)成分枝問題S1和和S2，得解，得解B和和CS1)37, 1 (C)923, 2(B941923);(2, :zB31037);(1, :zCPage:39QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)SA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/911x21xPage:40QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)

22、132X254X1 231)310,23(AS2對對S1分枝：分枝：構(gòu)造約束：構(gòu)造約束：32x和和22x構(gòu)成分枝問題構(gòu)成分枝問題S11和和S12，得解，得解DS12)2 ,(1433D14611433);,2( :zDS11無可行解無可行解Page:41QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(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/1411x32x22x21xPage:42QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)132X254X1 231)

23、310,23(AS2對對S12分枝：分枝：構(gòu)造約束：構(gòu)造約束：31x和和21x構(gòu)成分枝問題構(gòu)成分枝問題S121和和S122，得解，得解E和和FS121) 1 , 3(E4);(3,1 :zES122)2 , 2(F4);(2,2 :zFPage:43QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(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=431x21x

24、Page:44QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)0-10-1整數(shù)規(guī)劃整數(shù)規(guī)劃變量只能取變量只能取0或或1的整數(shù)線性規(guī)劃的整數(shù)線性規(guī)劃Page:45QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)0-10-1規(guī)劃的運用規(guī)劃的運用- -工程投資預(yù)算工程投資預(yù)算 資金需求資金需求(1000$) 項項 目目 估計現(xiàn)值估計現(xiàn)值 第一年第一年 第二年第二年 第三年第三年 第四年第四年 工廠擴建工廠擴建 90 15 20 20 15 銷售網(wǎng)點擴建銷售網(wǎng)點擴建 40 10 15 20 5 新生產(chǎn)流水線新生產(chǎn)流水線 10 10 0 0 4 新產(chǎn)品研究新產(chǎn)品研究 37 15 10 10 10 可用資金可用資金 40 5

25、0 40 35 Page:46QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)模型模型變量假設(shè)變量假設(shè):項目沒有選中如果第選中目項第果如iixi 0 1max z= 90 x1+40 x2+10 x3+37x4s.t.15x1+10 x2+10 x3+15x44020 x1+15x2 + 10 x45020 x1+20 x2+ 10 x44015x1+5x2+4x3+10 x435x1, x2, x3, x4, =0,1模型模型:Page:47QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)0-10-1規(guī)劃的運用規(guī)劃的運用- -工廠工廠- -銷售點配置問題銷售點配置問題消費廠消費廠顧客需求顧客需求銷售點銷售點45

26、DCBA7IIIII213IPage:48QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)工廠工廠- -銷售點配置問題銷售點配置問題- -問題描畫問題描畫IIIIII生產(chǎn)能力生產(chǎn)能力1 18008001,0001,0001,2001,20030030035,00035,0002 240040050050070070020020045,00045,0003 380080060060050050030030040,00040,0004 450050060060070070020020042,00042,0005 570070060060050050040040040,00040,000ABCDI404080

27、809090505040,00040,000II707040406060808020,00020,000III808030305050606060,00060,000需求量需求量200200300300150150250250運輸成本運輸成本: 工廠工廠-銷售點銷售點開設(shè)的固開設(shè)的固定成本定成本開設(shè)的固開設(shè)的固定成本定成本運輸成本運輸成本: 銷售點銷售點-客戶客戶問題問題: 為使運營本錢最低為使運營本錢最低,應(yīng)開設(shè)那些工廠及銷售點應(yīng)開設(shè)那些工廠及銷售點?Page:49QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)工廠工廠- -銷售點配置問題銷售點配置問題- -模型參數(shù)模型參數(shù)銷售點不開設(shè)第銷售點開設(shè)第

28、廠不開設(shè)第廠開設(shè)第jjviiuji 0 1 0 1 客戶運輸量銷售點到第第銷售點運輸量廠到第第客戶需求量第廠供應(yīng)能力第銷售點開設(shè)成本第廠開設(shè)成本第客戶運價銷售點到第第銷售點運價廠到第第kjyjixkDiBjcickjcjicjkijkijijkij Page:50QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)工廠工廠- -銷售點配置問題銷售點配置問題- -模型模型 KkDy,N,jvyxMiuBxStvcucycxcZMinkNjjkKkjjkMiijiiNjijjNjjiNjMiijkKkjkMiijNjij, 2 , 1 , 21 , )( , 2 , 1 , 1111111111客戶需求：供銷平

29、衡：供應(yīng)能力：Page:51QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)0-10-1規(guī)劃的求解規(guī)劃的求解隱枚舉方法隱枚舉方法10,x6 4 3 x44x22x . .523xz max3213221321321321或xxxxxxxxxtsxxPage:52QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(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隱枚舉方法求解過程隱枚舉

30、方法求解過程Page:53QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)經(jīng)典指派問題經(jīng)典指派問題n個員工分配作個員工分配作n項任務(wù)，一致項任務(wù)，一致的的i個員任務(wù)的個員任務(wù)的j項任務(wù)的本錢為項任務(wù)的本錢為cij，i=1,n; j=1,n。求最正。求最正確分配方案。確分配方案。Page:54QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(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:55QSC華東理工大學(xué) 工商經(jīng)濟學(xué)

31、院運籌學(xué)nnnnnnnnccccccccccccccccC321333323122322211131211指派問題的解應(yīng)對應(yīng)于本錢矩陣的不同指派問題的解應(yīng)對應(yīng)于本錢矩陣的不同行與不同列，且總本錢最小行與不同列，且總本錢最小Page:56QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)例例B1B2B3B4B5A14871512A279171410A3691287A46714610A56912106cijPage:57QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)指派問題的性質(zhì)指派問題的性質(zhì)定理：對于指派問題，本錢矩陣的任一定理：對于指派問題，本錢矩陣的任一行行(或列或列)減去減去(或加上或加上)一個一樣的數(shù)得到一

32、個一樣的數(shù)得到的新指派問題與原問題同解的新指派問題與原問題同解Page:58QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)s)( s)(xcxc xs)(xcxc s)x(cxc=z n1jkjkjnki1in1jijijn1jkjn1jkjkjnki1in1jijijn1jkjkjnki1in1jijijzPage:59QSC華東理工大學(xué) 工商經(jīng)濟學(xué)院運籌學(xué)指派問題的求解指派問題的求解- -匈牙利方法匈牙利方法本錢矩陣的每一行及每一列減去該行或本錢矩陣的每一行及每一列減去該行或列的最小數(shù)，使每行每列至少有一個列的最小數(shù)，使每行每列至少有一個0。假設(shè)劃去這些假設(shè)劃去這些0所需求的直線數(shù)不少于所需求的直線數(shù)不少于n，那么此時就可以求得最優(yōu)解。那么此時就可以求得最