《運籌學(xué)》復(fù)習(xí)參考資料

1、第一局部 線性規(guī)劃問題的求解重要算法：圖解法、單純形迭代、大M法單純形迭代、對偶問題、表上作業(yè)法找初始可行解：西北角法，最小元素法；最優(yōu)性檢驗：閉回路法，位勢法；、目標規(guī)劃：圖解法、整數(shù)規(guī)劃：分支定界法次重點，匈牙利法重點、第二局部 動態(tài)規(guī)劃問題的求解重要算法：圖上標號法第三局部 網(wǎng)絡(luò)分析問題的求解重要算法：破圈法、TP標號法、尋求網(wǎng)絡(luò)最大流的標號法第一局部 線性規(guī)劃問題的求解一、兩個變量的線性規(guī)劃問題的圖解法：概念準備：定義：滿足所有約束條件的解為可行解；可行解的全體稱為可行解域。定義：到達目標的可行解為最優(yōu)解。圖解法：圖解法采用直角坐標求解：x1橫軸；x2豎軸。1、將約束條件取等號用直線繪

2、出；2、確定可行解域；3、繪出目標函數(shù)的圖形等值線，確定它向最優(yōu)解的移動方向；注：求極大值沿價值系數(shù)向量的正向移動；求極小值沿價值系數(shù)向量的反向移動。4、確定最優(yōu)解及目標函數(shù)值。參考例題：只要求下面這些有唯一最優(yōu)解的類型例1：某廠生產(chǎn)甲、乙兩種產(chǎn)品，這兩種產(chǎn)品均需在A、B、C三種不同的設(shè)備上加工，每種產(chǎn)品在不同設(shè)備上加工所需的工時不同，這些產(chǎn)品銷售后所能獲得利潤以及這三種加工設(shè)備因各種條件限制所能使用的有效加工總時數(shù)如下表所示：品產(chǎn)耗消備設(shè) A B C利潤萬元甲乙3 5 99 5 37030有效總工時540 450 720問：該廠應(yīng)如何組織生產(chǎn)，即生產(chǎn)多少甲、乙產(chǎn)品使得該廠的總利潤為最大？此題

3、也可用“單純形法或化“對偶問題用大M法求解解：設(shè)x1、x2為生產(chǎn)甲、乙產(chǎn)品的數(shù)量。 max z = 70x1+30x2 s.t. 、 可行解域為oabcd0，最優(yōu)解為b點。由方程組 解出x1=75，x2=15X*=75，15Tmax z =Z*= 70×75+30×15=5700例2：用圖解法求解 max z = 6x1+4x2 s.t. 、 可行解域為oabcd0，最優(yōu)解為b點。由方程組 解出x1=2，x2=6X*=2，6Tmax z = 6×2+4×6=36例3：用圖解法求解 min z =3x1+x2s.t. 、解：可行解域為bcdefb，最優(yōu)解為

4、b點。由方程組 解出x1=4，x2=X*=4，Tmin z =3×4+=11二、標準型線性規(guī)劃問題的單純形解法：一般思路：1、用簡單易行的方法獲得初始根本可行解；2、對上述解進行檢驗，檢驗其是否為最優(yōu)解，假設(shè)是，停止迭代，否那么轉(zhuǎn)入3；3、根據(jù)L規(guī)那么確定改良解的方向；4、根據(jù)可能改良的方向進行迭代得到新的解；5、根據(jù)檢驗規(guī)那么對新解進行檢驗，假設(shè)是最優(yōu)解，那么停止迭代，否那么轉(zhuǎn)入3，直至最優(yōu)解。具體做法可化歸標準型的情況：設(shè)max z = c1x1+ c2x2+ cnxns.t.對第i個方程參加松弛變量xn+i，i =1，2，m，得到列表計算，格式、算法如下：CBXBbc1c2cn

5、+mLx1x2xn+mcn+1xn+1b1a11a12a1 n+mc n+2xn+2b2a21a22a2 n++mxn+mbnam1am2am n+mz1z2zn+m12n+m注： zj =cn+1 a1j+ cn+2 a2j + cn+m amj=，j=1，2，n+mj =cjzj ,當j 0時，當前解最優(yōu)。注：由maxj確定所對應(yīng)的行的變量為“入基變量；由L=確定所對應(yīng)的行的變量為“出基變量，行、列交叉處為主元素，迭代時要求將主元素變?yōu)?，此列其余元素變?yōu)?。例1：用單純形法求解此題即是本資料P2“圖解法例1的單純形解法；也可化“對偶問題求解max z =70x1+30x2s.t.

6、解：參加松弛變量x3，x4，x5，得到等效的標準模型：max z =70x1+30x2+0 x3+0 x4+0 x5s.t.列表計算如下：CBXBb7030000Lx1x2x3x4x50x354039100540/3 =1800x445055010450/5 =900x572093001720/9 =800000070300000x33000810- 1/3300/8 =37.50x450010/301 - 5/950/10/3 =1570x1801 1/300 1/980/1/3 =2407070/30070/9020/30070/90x318000112/5130x215010 3/10-

7、 1/670x175100- 1/10 1/6570070300220/3000-220/3X*=75，15，180，0，0Tmax z =70×75+30×15=5700例2：用單純形法求解max z =7x1+12x2s.t.解：參加松弛變量x3，x4，x5，得到等效的標準模型：max z =7x1+12x2+0 x3+0 x4+0 x5s.t.列表計算如下：CBXBb712000Lx1x2x3x4x50x336094100360/4 =900x420045010200/5 =400x5300310001300/10 =30000007120000x324078/100

8、10- 2/5240/78/10 =2400/780x4505/2001- 1/250/5/2 =2012x2303/10100 1/1030/3/10 =10018/512006/517/50006/50x38400178/2529/257x1201002/5- 1/512x224010 3/254/28428712034/2511/3500034/2511/35X*=20，24，84，0，0Tmax z =7×20+12×24=428三、非標準型線性規(guī)劃問題的解法：1、一般地，對于約束條件組：假設(shè)為“，那么加松弛變量，使方程成為“；假設(shè)為“，那么減松弛變量，使方程成為“

9、。我們在前面標準型中是規(guī)定目標函數(shù)求極大值。如果在實際問題中遇到的是求極小值，那么為非標準型。可作如下處理：由目標函數(shù)min z=變成等價的目標函數(shù)maxz=令z=z/，min z=max z/2、等式約束大M法：通過加人工變量的方法，構(gòu)造人造基，從而產(chǎn)生初始可行基。人工變量的價值系數(shù)為M，M是很大的正數(shù)，從原理上理解又稱為“懲罰系數(shù)。課本P29類型一：目標函數(shù)仍為max z，約束條件組與。例1：max z =3x1+5x2s.t.解：參加松弛變量x3，x4，得到等效的標準模型：max z =3x1+5x2s.t.其中第三個約束條件雖然是等式，但因無初始解，所以增加一個人工變量x5，得到： m

10、ax z =3x1+5x2Mx5s.t. 單純形表求解過程如下：CBXBb3500MLx1x2x3x4x50x34101004/1 =40x41202010Mx5183200118/3 =63M2M00M3M352M0003x14101000x4120201012/2 =6Mx56023016/2 =332M33M0M0533M003x14101004/1 =40x46003116/3 =25x23013/201/23/(2/3) =9/2359/205/2009/20M5/2305x121001/31/3x320011/31/3x260101/20363503/210003/2M1X*=2，

11、6，2，0Tmax z =3×2+5×6=36類型二：目標函數(shù)min z，約束條件組與。例2：用單純形法求解min z =4x1+3x2s.t.解：減去松弛變量x3，x4，并化為等效的標準模型：max z/ =4x13x2s.t.增加人工變量x5、x6，得到：max z/ =4x13x2Mx5Mx6s.t單純形表求解過程如下：CBXBb400MMLx1x2x3x4x5x6Mx51624101016/4=4Mx61232010112/2=65M6MMMMM5M46M3MM003x241/211/401/404/1/2=8Mx64201/211/214/2=22M3/233/4

12、M/2MM/23/4M2M5/20M/23/4M3/43M/203x23013/81/43/81/44x12101/41/21/41/217431/85/41/85/4001/85/4M1/8M5/4X*=2，3，0，0Tmin z =max z/ =17=17四、對偶問題的解法：什么是對偶問題？1、在資源一定的條件下，作出最大的奉獻；2、完成給定的工作，所消耗的資源最少。引例與本資料P2例1 “圖解法、P7例1 “單純形法同：某工廠生產(chǎn)甲、乙兩種產(chǎn)品，這些產(chǎn)品均需在A、B、C三種不同的設(shè)備上加工，每種產(chǎn)品在不同設(shè)備上加工時需要不同的工時，這些產(chǎn)品售后所能獲得的利潤值以及這三種加工設(shè)備因各種條

13、件下所能使用的有效總工時數(shù)如下表：品產(chǎn)耗消備設(shè) A B C利潤萬元甲乙3 5 99 5 37030有效總工時540 450 720問：該廠應(yīng)如何組織生產(chǎn)，即生產(chǎn)多少甲、乙產(chǎn)品使得該廠的總利潤為最大？解：原問題設(shè)x1、x2為生產(chǎn)甲、乙產(chǎn)品的數(shù)量。max z = 70x1+30x2s.t.將這個原問題化為它的對偶問題設(shè)y1、y2、y2分別為設(shè)備A、B、C單位工時數(shù)的加工費。min w = 540y1+450y2+720y3s.t.用大M法，先化為等效的標準模型：max w/ =540y1450y2720y3s.t.增加人工變量y6、y7，得到：max z/ =540y1450y2720y3My6M

14、y7s.t大M法單純形表求解過程如下：CBXBb54045072000MMLy1y2y3y4y5y6y7My670359101070/3My730953010130/9=10/312M10M12MMMMM12M54010M45012M720MM00My660010/3811/311/360/8=2.5540y110/315/91/301/901/910/3/1/3=10-300+10/3M-8M180MM/3+60MM/3600-150+10/3M8M-540MM/3600M/3+60720y315/205/1211/81/241/81/2415/2/5/12=18540y15/615/120

15、1/241/81/241/85/6/5/12=2540572720135/2475/12135/275/201250135/2475/12135/2M75/2M720450y320/31011/61/61/61/6y2212/5101/103/101/103/1057003604507207515751518000751575M15M該對偶問題的最優(yōu)解是y*=0，2，0，0T最優(yōu)目標函數(shù)值min w =5700=5700五、運輸規(guī)劃問題：運輸規(guī)劃問題的特殊解法“表上作業(yè)法解題步驟：1、找出初始調(diào)運方案。即在(m×n)產(chǎn)銷平衡表上給出m+n-1個數(shù)字格。最小元素法2、對空格求檢驗數(shù)。判

16、別是否到達最優(yōu)解。如已是最優(yōu)解，那么停止計算，否那么轉(zhuǎn)到下一步。閉回路法3、對方案進行改善，找出新的調(diào)運方案。根據(jù)檢驗結(jié)果選擇入基變量，用表上閉回路法調(diào)整即迭代計算，得新的根本可行解4、重復(fù)2、3，再檢驗、再迭代，直到求得最優(yōu)調(diào)運方案。類型一：供求平衡的運輸規(guī)劃問題又稱“供需平衡、“產(chǎn)銷平衡引例：某鋼鐵公司有三個鐵礦和四個煉鐵廠，鐵礦的年產(chǎn)礦石量分別為100萬噸、80萬噸和50萬噸，煉鐵廠年需礦石量分別為50萬噸、70萬噸、80萬噸和30萬噸，這三個鐵礦與四個煉鐵廠的距離如下：礦鐵廠鐵離距煉 B1 B2 B3 B4A1A2A315 20 3 3070 8 14 2012 3 20 15問：該公

17、司應(yīng)如何組織運輸，既滿足各煉鐵廠需要，又使總的運輸費用為最小按噸.公里計？解：用“表上作業(yè)法求解。1 用最低費用法最小元素法求此問題的初始根底可行解：地產(chǎn)用費地銷B1B2B3B4產(chǎn)量SiA11520673306510020×80×A2708144420803020×30A3125332033251050×50××銷量dj50708030 230230初始方案：B2203030B1B3A22080B1B3A1B250A3Z=15×20+3×80+70×30+8×20+20×30+3

18、15;50=3550噸.公里2 的初始可行解進行迭代表上閉回路法，求最優(yōu)解：地產(chǎn)用費地銷B1B2B3B4產(chǎn)量SiA11520143301210020×80×A2705381492080×50×30A312320202510503020××銷量dj50708030 230230用表上閉回路法調(diào)整后，從上表可看出，所有檢驗數(shù)>=0，已得最優(yōu)解。最優(yōu)方案：3020B1B2A35030B2B4A22080B1B3A1Z=15×20+3×80+8×50+20×30+12×30+3×

19、;20=1960噸.公里解法分析：如何求檢驗數(shù)并由此確定入基變量？有數(shù)字的空格稱為“基格、打×的空格稱為“空格，標號為偶數(shù)的頂點稱為偶點、標號為奇數(shù)的頂點稱為奇點，出發(fā)點算0故為偶點。找出所有空格的閉回路后計算它們的檢驗數(shù)，必須0，才得到最優(yōu)解。否那么，應(yīng)選所有中正的最大者對應(yīng)的變量xj為入基變量進行迭代調(diào)整。檢驗后調(diào)整運輸方案的方法是：在空格的閉回路中所有的偶點均加上奇點中的最小運量，所有的奇點均減去奇點中的最小運量。重復(fù)以上兩步，再檢驗、再調(diào)整，直到求得最優(yōu)運輸方案。求下面運輸問題的最小值解：12341311310721923437410593656解：由最小元素法得到初始解：v

20、1=2v2=9v3=3v4=101934u1=01311310743u2=-121923431u3=-53741059633656那么：，最小值為-6，非基變量為，閉回路，最大調(diào)整量為1，得新解：，重新計算位勢及影響系數(shù)，得下表：v1=8v2=9v3=3v4=101234u1=01311310752u2=-721923431u3=-53741059633656，最小值為-5，非基變量為，閉回路，最大調(diào)整為2，得新解：重新計算位勢及影響系數(shù)，得下表：v1=3v2=4v3=3v4=51234u1=01311310725u2=-221923413u3=03741059633656，此時，故當前解為最

21、優(yōu)解。最優(yōu)解值為：。六、目標規(guī)劃問題目標規(guī)劃問題min z= p1 d1- + p2d2- + p35d3- + 3d4- + p4 d1+x1 +2x2 + d1- - d1+ =6x1 +2x2 + d2- - d2+ =9x1 -2x2 + d3- - d3+ =4x2 + d4- - d4+ =2x1 ，x20，di- , di+0 (i=1,2,3,4)分別用圖解法和單純形法求解x2d2+54d2-d4+d3-d1+3Ad4-d1-2d3+B10 2 4 6 8 x1七1、整數(shù)規(guī)劃問題分枝定界法：用分枝定界法求解整數(shù)規(guī)劃七2、工作指派問題：工作指派問題的數(shù)學(xué)模型假定有n項工作需要完成

22、，恰好有n個人每人可去完成其中一項工作，效果要好。工作指派問題的特殊解法“匈牙利法考！解題步驟：1、使系數(shù)矩陣效率矩陣各行、各列出現(xiàn)零元素。作法：行約簡系數(shù)矩陣各行元素減去所在行的最小元素，列約簡再從所得矩陣的各列減去所在列最小元素。2、試求最優(yōu)解。如能找出n個位于不同行不同列的零元素，令對應(yīng)的xij= 1，其余xij = 0，得最優(yōu)解，結(jié)束；否那么下一步。作法：由獨立0元素的行列開始，獨立0元素處畫 標記 ，在有 的行列中劃去也可打*其它0元素；再在剩余的0元素中重復(fù)此做法，直至不能標記 為止。3、作能覆蓋所有0元素的最少數(shù)直線集合。作法： 對沒有 的行打號；對已打號的行中所有0元素的所在列

23、打號；再對打有號的列中0元素的所在行打號；重復(fù)、直到得不出新的打號的行(列)為止；對沒有打號的行畫一橫線，對打號的列畫一縱線，這就得到覆蓋所有0元素的最少直線數(shù)。未被直線覆蓋的最小元素為cij,在未被直線覆蓋處減去cij,在直線交叉處加上cij。4、重復(fù)2、3，直到求得最優(yōu)解。類型一：求極小值的匈牙利法：重點掌握這種根本問題例1：有甲、乙、丙、丁四個人，要派去完成A、B、C、D四項工作，他們完成的工時如下表：人務(wù)時工任 A B C D甲乙丙丁6 12 13 410 3 12 147 14 13 168 8 12 10試問：應(yīng)如何分配任務(wù)可使總工時為最少？解：用“匈牙利法求解。條件可用系數(shù)矩陣效

24、率矩陣表示為：行約簡列約簡cij= ABCD標號甲乙丙丁 使總工時為最少的分配任務(wù)方案為：甲D，乙B，丙A，丁C此時總工時數(shù)W=4+3+7+12=26例2：求效率矩陣的最優(yōu)解。列約簡行約簡解： 標號 所畫0元素少于n，未得到最優(yōu)解，需要繼續(xù)變換矩陣求能覆蓋所有0元素的最少數(shù)直線集合：未被直線覆蓋的最小元素為cij=1,在未被直線覆蓋處減去1,在直線交叉處加上1。標號 得最優(yōu)解：類型二：求極大值的匈牙利法：min z=maxzcijMcij=bij，cij中最大的元素為Mmax z=第二局部 動態(tài)規(guī)劃只要求掌握動態(tài)規(guī)劃的最短路問題用“圖上標號法解決：具體解題步驟請參看教材這是本套資料少見的與教材完全相同的算法類型之一，務(wù)必看書掌握只有完全理解了這種作法思路：逆向追蹤才有可能做題，考試時數(shù)字無論如何變化都能作出正確求解！第二局部到此結(jié)束第三局部 網(wǎng)絡(luò)分析一、求最小生成樹最小支撐樹、最小樹問題：破圈法任取一個圈，從圈中去掉一條權(quán)最大的邊如果有兩條或兩條以上的邊都是權(quán)最大的邊，那么任意去掉其中一條。在余下的圖中，重復(fù)這個步驟，直到得到一個不含圈的圖為止，這時的圖便是最小樹