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

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

2、將約束條件（取等號(hào)）用直線繪出;2、確定可行解域；3、 繪出目標(biāo)函數(shù)的圖形（等值線），確定它向最優(yōu)解的移動(dòng)方向；注：求極大值沿價(jià)值系數(shù)向量的正向移動(dòng)；求極小值沿價(jià)值系數(shù)向量的反向移動(dòng)4、確定最優(yōu)解及目標(biāo)函數(shù)值。參考例題：（只要求下面這些有唯一最優(yōu)解的類型）例1某廠生產(chǎn)甲、乙兩種產(chǎn)品，這兩種產(chǎn)品均需在A、B、C三種不同的設(shè)備上加工，每種產(chǎn)品在不同設(shè)備上加工所需的工時(shí)不同，這些產(chǎn)品銷售后所能獲得利潤(rùn)以及這三種加工設(shè)備因各種條件限制所能使用的有效加工總時(shí)數(shù)如下 表所示：消產(chǎn)、口仃設(shè)備耗ABC利潤(rùn)（萬(wàn)兀）甲35970乙95330有效總工時(shí)540450720問(wèn)：該廠應(yīng)如何組織生產(chǎn)，即生產(chǎn)多少甲、乙產(chǎn)品使

3、得該廠的總利潤(rùn)為最大?（此題也可用“單純形法”或化“對(duì)偶問(wèn)題”用大M法求解） 解：設(shè)Xi、X2為生產(chǎn)甲、乙產(chǎn)品的數(shù)量。max z = 70x 1+30x23x19x25405x15x24509x13x2720X1,X20、!-可行解域?yàn)閛abcd0，最優(yōu)解為b點(diǎn)。由方程組5x15x24509x13x2720解出 xi=75, X2=15Xi=(75,15) T X*=X2/ max z =Z=70 75+30 15=5700例2:用圖解法求解max z = 6x 1+4x2S.t.2x1X210XiX2X2Xi,X2、d刁匚0可行解域?yàn)閛abcd0,最優(yōu)解為b點(diǎn)。 由方程組!-X2Xi=(2,

4、 6)x210x28 max z = 6 例3:用圖解法求解min z = 3xi+X21+4X6=36解出 xi=2, X2=6S.t.Xi4X232xi5x2i2Xi2x28Xi,x20、解:i33：cL!* (1-C嚴(yán)汪可行解域?yàn)閎cdefb，最優(yōu)解為b點(diǎn)。由方程組2x15x2124解出 Xi=4, X2=5XiX*=X2 min z = 3X4+ = ii _55!-二、標(biāo)準(zhǔn)型線性規(guī)劃問(wèn)題的單純形解法：一般思路：1、用簡(jiǎn)單易行的方法獲得初始基本可行解；2、 對(duì)上述解進(jìn)行檢驗(yàn)，檢驗(yàn)其是否為最優(yōu)解，若是，停止迭代，否則轉(zhuǎn)入3;3、根據(jù)0 l規(guī)則確定改進(jìn)解的方向；4、根據(jù)可能改進(jìn)的方向進(jìn)行迭

5、代得到新的解；am1 X1am2X2 amn XnXn mbm5、根據(jù)檢驗(yàn)規(guī)則對(duì)新解進(jìn)行檢驗(yàn)，若是最優(yōu)解，則停止迭代，否則轉(zhuǎn)入3,直至最優(yōu)解。具體做法（可化歸標(biāo)準(zhǔn)型的情況）：設(shè)已知max z =C1X1+ C2X2+ CnXns.t.a1a2 X2.a1nXn0a?1 Xa?2 X2.a2nXnb2am1 X1am2 X2.amn XnXj0, j 1,2 , . , n對(duì)第i個(gè)方程加入松弛變量Xn+i , i =1 ,2,m，得到a“ X1812X2.a1nXnXn 1b1a21 X1a22 X2.a2nXnXn 2thXj0, j 1,2 , . , n列表計(jì)算，格式、算法如下:CBXBb

6、c1x1c2-x2-cn+m xn+m0 Lcn+1xn+1b1a11a12-a1 n+mc n+2xn+2b2a21a22-a2 n+mcn+mxn+mbnam1am2-am n+mz1z2zn+md 1d 2-d n+mm注： zj =cn+1 a1j+ cn+2 a2j + + cn+m amj= cn i aij , (j=1 , 2,，n+m)i 1d j =cj zj ,當(dāng)c j w 0時(shí)，當(dāng)前解最優(yōu)。注：由max cj確定所對(duì)應(yīng)的行的變量為“入基變量”；!-b由o L=min |aik0確定所對(duì)應(yīng)的行的變量為“出基變量”，行、列交叉處為主元素，迭代時(shí)要求將主元i aik素變?yōu)?，

7、此列其余元素變?yōu)?0。例1:用單純形法求解（本題即是本資料P2 “圖解法”例1的單純形解法；也可化“對(duì)偶問(wèn)題”求解）max z =70x 什30x2s.t.3x1 9x25405x1 5x24509x1 3x2720x1? x20解：加入松弛變量 X3, X4, X5，得到等效的標(biāo)準(zhǔn)模型:max z =70x 1+30x2+0 X3+0 X4+0 x5s.t.3x19x2X35405x15x2x44509x13x2X5720Xj0,j1,2,.,5列表計(jì)算如下:7030000CBXBbx1x2x3x4x5oL0x354039100540/3=1800x445055010450/5=900x57

8、20(9)3001720/9=800000070 f300000x33000810-1/3300/8=37.50x4500(10/3 )01-5/950/10/3=1570x18011/3001/980/1/3=2407070/30070/9020/3 f00-70/90x3180001-12/5130x2150103/10-1/670x175100-1/101/670300220/35700000-2-20/3二 X*= (75, 15, 180, 0, 0) T/ max z =70 X 75+30 X 15=5700!- 例2 :用單純形法求解max z =7x 1+12x2s.t.9x

9、1 4x2 3604xi 5X22003x1 10x2300x1, x20解：加入松弛變量 X3, X4, X5，得到等效的標(biāo)準(zhǔn)模型:max z =7x 1+12x2+0 X3+0 X4+0 x5s.t.9x14x2X33604x15x2x42003x110x2x5300Xj0,j1,2,.,5列表計(jì)算如下:712000CBXBbx1x2x3x4x50 L0x336094100360/4 =900x420045010200/5 =400x53003(10)001300/10 =3000000712 f0000x324078/10010-2/5240/78/10 =2400/780x450(5/

10、2 )001-1/250/5/2 =2012x2303/101001/1030/3/10 =10018/512006/517/5 f0006/50x38400178/2529/257x1201002/5-1/512x2240103/254/28712034/2511/3542800034/2511/35二 X*= (20, 24, 84, 0, 0) max z =7 X 20+12 X 24=428!-三、非標(biāo)準(zhǔn)型線性規(guī)劃問(wèn)題的解法：1、一般地，對(duì)于約束條件組：若為w”，則加松弛變量，使方程成為=”；若為”，則減松弛變量，使方程成為=”。我們?cè)谇懊鏄?biāo)準(zhǔn)型中是規(guī)定目標(biāo)函數(shù)求極大值。如果在實(shí)際問(wèn)

11、題中遇到的是求極小值，則為nn由目標(biāo)函數(shù) min z= Cj Xj變成等價(jià)的目標(biāo)函數(shù) max （- z） =（ CjXj）j 1j 1令一z=z/,. min z= max Z2、等式約束一一大 M法：通過(guò)加人工變量的方法，構(gòu)造人造基，從而產(chǎn)生初始可行基。人工變量的價(jià)值系數(shù)為- 理上理解又稱為“懲罰系數(shù)”。（課本P29）非標(biāo)準(zhǔn)型。可作如下處理:M , M是很大的正數(shù)，從原類型一：目標(biāo)函數(shù)仍為 max z,約束條件組w與=。s.t.X142x2123x12x218X1,x20例 1: max z =3x i+5x2解：加入松弛變量 X3, X4,得到等效的標(biāo)準(zhǔn)模型：max z =3x 1+5x2

12、s.t.捲 X342x2x4 123x1 2x218Xj0, j 1,2,3,4其中第三個(gè)約束條件雖然是等式，但因無(wú)初始解，所以增加一個(gè)人工變量X5，得到:X1X3 42x2x4 12s.t.3x1 2x2x5 18Xj0, j 1,2,.,5max z =3x1+5x2 M X5!-單純形表求解過(guò)程如下:3500MCBXBbx1x2x3x4x50 L0x34(1)01004/1 =40x41202010Mx5183200118/3 =63M2M00M3M + 3 f5+ 2M0003x14101000x4120201012/2 =6Mx560(2)3016/2 =332M3+ 3M0M05f

13、3 3M003x14101004/1 =40x4600(3)116/3 =25x23013/201/23/( 2/3) = 9/2359/205/2009/2 f0M 5/23x121001/31/3x320011/31/30x260101/2053503/21360003/2M 1二 x*= (2, 6, 2, 0)/ max z =3 x 2+5 x 6=36類型二:目標(biāo)函數(shù) min z，約束條件組與=。例2:用單純形法求解s.t.min z =4x 1+3x22x14x2163x12x212x1, x2 0解：減去松弛變量 X3, X4,并化為等效的 標(biāo)準(zhǔn)模型:max z/ = 4xi

14、3x2s.t.2x14x2X3163x12x2X412Xjo,j123,4增加人工變量x5、 X6，得到：max z/=4x1 3x2 Mx5 MX6S.t2x14x2X3X5163x12x2X4X 12Xj0,j1,2,.,6!-單純形表求解過(guò)程如下:CBXBb4x1x20x30x4Mx5Mx60 LMx5162(4)101016/4=4Mx61232010112/2=65M6MMMMM5M 46M 3 fMM003x241/211/401/404/1/2=8Mx64(2)01/211/214/2=22M 3/233/4 M/2MM/2 3/4M2M 5/2 f0M/2 3/4M3/4 3M

15、/203x23013/81/43/81/44x12101/41/21/41/21740301/81/85/45/41/8M + 1/85/4M + 5/4 X*= (2, 3, 0, 0) T/ min z = max z/ = ( 17) =17四、對(duì)偶問(wèn)題的解法：什么是對(duì)偶問(wèn)題？1、在資源一定的條件下，作出最大的貢獻(xiàn)；“單純形法”同):某工廠生產(chǎn)甲、乙兩種產(chǎn)品，這些產(chǎn)品均需在C三種不同的設(shè)備上加工，每種產(chǎn)品在不同設(shè)備上加工時(shí)需要不同的工時(shí)，這些產(chǎn)品售后所能獲得的利潤(rùn)值以及這三2、完成給定的工作，所消耗的資源最少。 引例(與本資料P2例1 “圖解法” P7例1!-甲35970乙95330有效

16、總工時(shí)540450720問(wèn)：該廠應(yīng)如何組織生產(chǎn)，即生產(chǎn)多少甲、乙產(chǎn)品使得該廠的總利潤(rùn)為最大?解：原問(wèn)題一一設(shè)XI、X2為生產(chǎn)甲、乙產(chǎn)品的數(shù)量。max z = 70x 1+30x2s.t.3x19x25405x15x24509x13x2720Xpx20將這個(gè)原問(wèn)題化為它的對(duì)偶問(wèn)題設(shè)yi、y2、y2分別為設(shè)備 A、B、C單位工時(shí)數(shù)的加工費(fèi)。min w = 540y 1+450y2+720y3s.t.3y15y29y3709y15y23y330yi0, i1,2,3用大M法，先化為等效的標(biāo)準(zhǔn)模型：max w/=540yi 450y2 720y3s.t.3y15y29y3y4709y15y23y3y5

17、30yj0,j1,2,.,5增加人工變量y6、y7,得到：max z :=540yi450y2 720y3 My 6 My 7s.t3yi5y29y3y4y6709yi5y23y3y5y730yj0,j1,2,.,5大M法單純形表求解過(guò)程如下:CBXBb540y1450y2720y30y40y5My6My70 LMy670359101070/3My730(9)53010130/9=10/312M10M12MMMMM12M 540 f10M 45012M 720MM00My660010/3(8)11/311/360/8=2.5540yi10/315/91/301/901/910/3/1/3=10

18、-300+10/3 M-8M 180MM/3+6 0MM/3 600-150+10/3 M8M-540 fMM/3 600M/3+6 0720y315/205/1211/81/241/81/2415/2/5/12=18540yi5/61(5/12 )01/241/81/241/85/6/5/12=2540572720135/2475/12135/275/20125 f0135/2475/12135/2 M75/2 M720y320/31011/61/61/61/6450y2212/5101/103/101/103/1036045072075157515570018000751575 M15 M

19、!-20該對(duì)偶問(wèn)題的最優(yōu)解是y*=( 0, 2,o, o)最優(yōu)目標(biāo)函數(shù)值 min w = （ 5700） =5700五、運(yùn)輸規(guī)劃問(wèn)題：運(yùn)輸規(guī)劃問(wèn)題的特殊解法一一“表上作業(yè)法”解題步驟:1、找出初始調(diào)運(yùn)方案。即在 （mx n）產(chǎn)銷平衡表上給出 m+n-1個(gè)數(shù)字格。（最小元素法）2、（對(duì)空格）求檢驗(yàn)數(shù)。判別是否達(dá)到最優(yōu)解。如已是最優(yōu)解，則停止計(jì)算，否則轉(zhuǎn)到下一步。（閉回路法）3、對(duì)方案進(jìn)行改善，找出新的調(diào)運(yùn)方案。（根據(jù)檢驗(yàn)結(jié)果選擇入基變量，用 表上閉回路法 調(diào)整一一即迭代計(jì)算，得新的基本可行解）4、重復(fù)2、3,再檢驗(yàn)、再迭代，直到求得最優(yōu)調(diào)運(yùn)方案。類型一：供求平衡的運(yùn)輸規(guī)劃問(wèn)題（又稱“供需平衡”、

20、“產(chǎn)銷平衡”）引例：某鋼鐵公司有三個(gè)鐵礦和四個(gè)煉鐵廠，鐵礦的年產(chǎn)礦石量分別為 100萬(wàn)噸、80萬(wàn)噸和50萬(wàn)噸，煉鐵廠年需!-Ai1520330A27081420A31232015問(wèn)：該公司應(yīng)如何組織運(yùn)輸，既滿足各煉鐵廠需要，又使總的運(yùn)輸費(fèi)用為最?。ò磭?公里計(jì)）？解：用“表上作業(yè)法”求解。 用最低費(fèi)用法（最小元素法） 求此問(wèn)題的初始基礎(chǔ)可行解：!-AiBiB3BiB2A350 一B2B3費(fèi)銷地 產(chǎn)地BiB2B3B4產(chǎn)量SiAii5206733065i0020X80XA2708i44420803020X30A3i2533203325i050X50XX銷量dj50708030 230230初始方案

21、:Z=15 X 20+3 X 80+70 X 30+8X 20+20 X 30+3 X 50=3550 （噸 . 公里） 的初始可行解進(jìn)行迭代（表上閉回路法），求最優(yōu)解：BiBi費(fèi)銷地BiB2B3B4產(chǎn)量SiAii520i4330i2i0020X80XA270538i492080X50X30A3i23202025i0503020XX銷量dj50708030230230用表上閉回路法調(diào)整后，從上表可看出，所有檢驗(yàn)數(shù)b=0,已得最優(yōu)解。最優(yōu)方案：!-Z=15 X 20+3 X 80+8 X 50+20 X 30+12 X 30+3 X 20=1960 （噸 公里）解法分析：如何求檢驗(yàn)數(shù)并由此確定入

22、基變量？有數(shù)字的空格稱為“基格”、打X的空格稱為“空格”，標(biāo)號(hào)為偶數(shù)的頂點(diǎn)稱為偶點(diǎn)、標(biāo)號(hào)為奇數(shù)的頂點(diǎn)稱為奇點(diǎn)，出發(fā)點(diǎn)算0故為偶點(diǎn)。找出所有空格的閉回路后計(jì)算它們的檢驗(yàn)數(shù)ijCijCij ,必須jj w 0,才得到最優(yōu)解。否則，應(yīng)選所有中正的最大者對(duì)應(yīng)的變量Xj為入基變量進(jìn)奇點(diǎn)偶點(diǎn)行迭代（調(diào)整）。檢驗(yàn)后調(diào)整運(yùn)輸方案的辦法是：在空格的閉回路中所有的偶點(diǎn)均加上奇點(diǎn)中的最小運(yùn)量，所有的奇點(diǎn)均減去奇點(diǎn)中的最小運(yùn)量。重復(fù)以上兩步，再檢驗(yàn)、再調(diào)整，直到求得最優(yōu)運(yùn)輸方案。求下面運(yùn)輸問(wèn)題的最小值解:12341311310721923437410593656解：由最小元素法得到初始解:v1=2V2=9v3=3V4

23、=101934U1=01311341037U2=-121392134U3=-53746105393656則：111, 122 , 221, 246 , 3110 , 33 1 2，最小值為-6，非基變量為X24，閉回路X24：X24X23為3X14X24，最大調(diào)整量為1，得新解:X135,X142,X213,X241,X326,Xm 3,重新計(jì)算位勢(shì)及影響系數(shù)，得下表:!-V1=8V2=9V3=3V4=101234u1=01311351027U2=-721392314U3=-53746105393656115, 122, 227, 236, 314, 3312，最小值為-5，非基變量為x11，

24、閉回路x11: x11x4x24x21x11，最大調(diào)整為2,得新解：X112,X13重新計(jì)算位勢(shì)及影響系數(shù)，得下表:5,X2i 1, X243,X326,X343V1=3V2=4V3=3V4=51234U1=01321135107U2=-221192334U3=0374610539365612 7, 14 5 , 22 7 , 23 1, 31 4 , 33 7,此時(shí)， j 0，故當(dāng)前解為最優(yōu)解。最優(yōu)解值為:Y 323511334653 70。六、目標(biāo)規(guī)劃問(wèn)題 已知目標(biāo)規(guī)劃問(wèn)題min z= p 1 d1- + p2d2- + p3 X1 +2x2 + d1- - d1+ =6(5d3- + 3

25、d4-)+ p4 d1 +X1 +2x2 + d2- - d2+ =9X1 -2x2 + d3- - d3+ =4X2 + d4- - d4+ =2X1 , X2 0, di- , di+0(i=1,2,3,4)!-分別用圖解法和單純形法求解d2+X25432124X1七（ 1）、整數(shù)規(guī)劃問(wèn)題（分枝定界法）用分枝定界法求解整數(shù)規(guī)劃max z%X2951X214,142x1X21J3xx20且為整數(shù).七（ 2）、工作指派問(wèn)題：工作指派問(wèn)題的數(shù)學(xué)模型一一假定有n項(xiàng)工作需要完成，恰好有 n個(gè)人每人可去完成其中一項(xiàng)工作，效果要好。 工作指派問(wèn)題的特殊解法一一“匈牙利法”（考！ ！解題步驟：1、使系數(shù)矩

26、陣（效率矩陣）各行、各列出現(xiàn)零元素。作法：行約簡(jiǎn) 一系數(shù)矩陣各行元素減去所在行的最小元素，列約簡(jiǎn)一再?gòu)乃镁仃嚨母髁袦p去所在列最小元素。Xj= 1，其余Xj = 0 ,得最優(yōu)解，結(jié)束；否則下2、試求最優(yōu)解。如能找出 n個(gè)位于不同行不同列的零元素，令對(duì)應(yīng)的止zjo!-作法：由獨(dú)立0元素的行（列）開(kāi)始，獨(dú)立 0元素處畫（）標(biāo)記，在有（）的行列中劃去（也可打*）其它0 元素；再在剩余的0元素中重復(fù)此做法，直至不能標(biāo)記（）為止。3、作能覆蓋所有0元素的最少數(shù)直線集合。作法： 對(duì)沒(méi)有（）的行打號(hào)；對(duì)已打2號(hào)的行中所有0元素的所在列打號(hào)；再對(duì)打有號(hào)的列中0元素的所在行打號(hào)；重復(fù)、直到得不出新的打號(hào)的行（列

27、）為止；對(duì)沒(méi)有打號(hào)的行畫一橫線，對(duì)打號(hào)的列畫一縱線，這就得到覆蓋所有0元素的最少直線數(shù)。未被直線覆蓋的最小元素為Cj,在未被直線覆蓋處減去Cjj,在直線交叉處加上cij。4、重復(fù)2、3,直到求得最優(yōu)解。類型一：求極小值的匈牙利法:（重點(diǎn)掌握這種基本問(wèn)題） 例1 :試問(wèn)：應(yīng)如何分配任務(wù)可使總工時(shí)為最少? 解：用“匈牙利法”求解。已知條件可用系數(shù)矩陣（效率矩陣）6121342890(Cj )=1031214 行約簡(jiǎn)709111 - 7141316 07698812100042表示為:列約簡(jiǎn)2857050720 0 0ABCD甲285(0)0標(biāo)號(hào)11乙7(0)5119，丙(0)7292丁*0*0(0

28、)2使總工時(shí)為最少的分配任務(wù)方案為：甲t D，乙t B，丙t A，丁t C此時(shí)總工時(shí)數(shù) W=4+3+7+12=26例2 :求效率矩陣109785877的最優(yōu)解5465234510978行約簡(jiǎn)32 01列約簡(jiǎn)解：5584767501320221234501 2332(0)*032000321號(hào) 標(biāo)(0)32100元素少于n,未得到最優(yōu)解，需要繼續(xù)1020IZZ. 1(0)20* 所畫0122*0122變換矩陣（求能覆蓋所有0元素的最少數(shù)直線集合）!-V(0)321*V1(0)20*0122V未被直線覆蓋的最小元素為cij=1，在未被直線覆蓋處減去42(0)0(0)21*0號(hào) 標(biāo)2*02(0)得最

29、優(yōu)解*0(0)11類型二:求極大值的匈牙利法：*min z= max ( z)(旳)t( M Cj) = (bj), ( Cj )中最大的元素為 M01000 1 00 0 00 0 11 0 0max z=iCij Xij(M cij )xiji j(M Cij)xiji jCij xiji j32(0)0*420002101,在直線交叉處加上1。20200011!-第二部分動(dòng)態(tài)規(guī)劃只要求掌握動(dòng)態(tài)規(guī)劃的最短路問(wèn)題一一用“圖上標(biāo)號(hào)法”解決：具體解題步驟請(qǐng)參看教材（這是本套資料少見(jiàn)的與教材完全相同的算法類型之一，務(wù)必看書掌握）只有完全理解了這種作法（思路：逆向追蹤）才有可能做題，考試時(shí)數(shù)字無(wú)論如何變化都能作出正確求解！第二部分到此結(jié)束 第三部分網(wǎng)絡(luò)分析一、求最小生成樹 （最小支撐樹、最小樹） 問(wèn)題