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

1、運(yùn)籌學(xué)復(fù)習(xí)參考資料資料加工、整理人一一楊峰（函授總站高級(jí)講師）要求掌握的各部分知識(shí)點(diǎn)第一部分線性規(guī)劃問題的求解（相當(dāng)于教材的第一章）資一重要算法：?jiǎn)渭冃蔚?、?M法單純形迭代、表上作業(yè)法、匈牙利法第二部分動(dòng)態(tài)規(guī)劃問題的求解（相當(dāng)于教材的第三章）資一重要算法：圖上標(biāo)號(hào)法第三部分網(wǎng)絡(luò)分析問題的求解（相當(dāng)于教材的第四章）資一重要算法：破圈法、TP標(biāo)號(hào)法、尋求網(wǎng)絡(luò)最大流的標(biāo)號(hào)法第 四部分 存儲(chǔ)論簡(jiǎn)介（相當(dāng)于教材的第七章）楊老師關(guān)于學(xué)習(xí)方法的提示：運(yùn)籌學(xué)屬于應(yīng)用數(shù)學(xué)的范疇，本門課程在管理類本 科生層次開設(shè)時(shí)，又稱“管理運(yùn)籌學(xué)”，是現(xiàn)代數(shù)學(xué)理論和計(jì)算機(jī)技術(shù)應(yīng)用于管理科學(xué)的新 興學(xué)科。非應(yīng)用數(shù)學(xué)系（專業(yè)）

2、學(xué)生學(xué)習(xí)本門課程之前務(wù)必先具備“高數(shù)（線性代數(shù)、 概率論與數(shù)理統(tǒng)計(jì)）的知識(shí)基礎(chǔ)。學(xué)員同志們通過學(xué)習(xí)，必須領(lǐng)會(huì)數(shù)學(xué)建模的思想、系統(tǒng)工 程的思想。非全日制學(xué)生學(xué)習(xí)時(shí)，只要求知道若干典型數(shù)學(xué)模型及其算法的操作，即只須明白“怎樣做”，而不必去過問“為什么”要這樣做。第一部分線性規(guī)劃問題的求解一、兩個(gè)變量的線性規(guī)劃問題的圖解法：概念準(zhǔn)備：定義：滿足所有約束條件的解為可行解；可行解的全體稱為可 行（解）域。定義：達(dá)到目標(biāo)的可行解為最優(yōu)解。圖解法:圖解法采用直角坐標(biāo)求解：X1 橫軸；X2 豎軸。1、將約束條件（取等號(hào)）用直線繪出；2、確定可行解域；3、繪出目標(biāo)函數(shù)的圖形（等值線），確定它向最優(yōu)解的移動(dòng)方向；

3、注：求極大值沿價(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)（萬元）甲35970乙95330啟效總工時(shí)540450720問：該廠應(yīng)如何組織生產(chǎn)，即生產(chǎn)多少甲、乙產(chǎn)品使得該廠的總利潤(rùn)為最大?（此題也可用“單純形法”或化“對(duì)偶問題”用大M法求解）解：設(shè)Xi、X2為生產(chǎn)甲、乙產(chǎn)品的數(shù)

4、量。max z = 70Xi+30X2s.t.、3xi 9x25405xi 5x24509x1 3x2720x1, x20可行解域?yàn)閛abcd。，最優(yōu)解為b點(diǎn)。由方程組5x1 5x24509x1 3x2 720 解出 x1=75, x2=15、.* XiT.X = (75, 15) Tx2. max z =Z*= 70 >75+305=5700s.t.2x1x210x1乂28乂27x1,乂20、解:可行解域?yàn)閛abcdQ最優(yōu)解為b點(diǎn)。由方程組2x1 x2 10Q解出 x1=2, X2=6x1 x2 8x1T.X = v = (2, 6) TX2max z = 6 2+4X6=36s.t.

5、Xi4(2)X232xi5X212X12x28X1'x20、解：可行解域?yàn)閎cdefb,最優(yōu)解為b點(diǎn)由方程組X142x1 5x2412斛出 X1=4, X2=5*X1X* =X24(4, 5)Tmin z = -3><4+4 = 11" 55二、標(biāo)準(zhǔn)型線性規(guī)劃問題的單純形解法: 一般思路: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、根據(jù)檢驗(yàn)規(guī)則對(duì)新解進(jìn)行檢驗(yàn)，若是最優(yōu)解，則停止迭代，否則轉(zhuǎn)入3,直至最優(yōu)解。具體做法（可

6、化歸 標(biāo)準(zhǔn)型的情況）：設(shè)已知max z = C1X1+ C2X2+ CnXns.t.allxl a12x2a21X1 a 22 x2. . . . amlXl am2X2 Xj 0，j對(duì)第i個(gè)方程加入松弛變量a11X1 a12X2a21X1 a 22 X2. . . . amlXl am2X2 Xj 0，j列表計(jì)算，格式、算法如下a1n Xna2nXnblb2. amnXn1,2,.Xn+i, i =1,bm2,m,得到a1nXnXn 1b1a2nXnXn 2b2. amnXn1,2,., nXn mbmCbXbbC1C2Cn+me lX1X2Xn+mCn+1xn+1b1a11a12ai n+

7、mC n+2 .xn+2 .b2 .a21a22a2 n+m .Cn+m.xn+m.bnam1a2am n+mZ1Z2Zn+ma 12 2CT n+m注：Zj=Cn+1a1j+ Cn+2a2j + Cn+mamj =mCn iaij , (j=1 , 2, i 1，n+m)（T j =Cj Zj ,當(dāng)（T j W0時(shí)，當(dāng)前解最優(yōu)。注：由max bj確定所對(duì)應(yīng)的行的變量為“入基變量”；由0 L=min.航0確定所對(duì)應(yīng)的行的變量為“出基變量”，行、列交 i叉處為主元素，迭代時(shí)要求將主元素變?yōu)?,此列其余元素變?yōu)?。例1：用單純形法求解（本題即是本資料P2 “圖解法”例1的單純形解法；也可化“對(duì) 偶

8、問題”求解）max z =70Xi+30X2s.t.3xi 9x2 5405xi 5x24509xi 3x2720x1, x2 0解：加入松弛變量x3, x4, x5,得到等效的標(biāo)準(zhǔn)模型：max z =70xi+30x2+0 x3+0 x4+0 x5s.t.3x1 9x2 x3 5405xi 5x2X4 4509x1 3x2X5 720Xj 0,j 1,2,5列表計(jì)算如下:7030000CbXbbx1x2x3x4x5eL0x354039100540/3=1800x445055010450/5=900x5720(9)3001720/9=800000070 T300000x33000810-1/3

9、300/8=37.50x4500(10/3)01-5/950/10/3=1570x18011/3001/980/1/3=2407070/30070/9020/3 T00-70/90x3180001 12/5130x2150103/10-1/670x175100-1/101/6570070 030 0002-220/3-20/3X*= (75, 15, 180, 0, 0) T. max z =70 X 75+30 X 15=5700例2:用單純形法求解max z =7x1+12x2s.t.9xi 4x2 3604xi 5x2 2003xi 10X2 300X1, x2 0解：加入松弛變量X3,

10、 X4, X5,得到等效的標(biāo)準(zhǔn)模型:max z =7xi+12x2+0 X3+0 X4+0 X5s.t.9xi 4X2 X3 3604x1 5x2x4 2003xi 10x2x5 300xj 0, j 1,2,5列表計(jì)算如下：CbXbb7x112x20x30x40x5e l0乂336094100360/4 =900x420045010200/5 =400x53003(10)001300/10 =3000000712T0000x324078/10010-2/5240/78/10 =2400/780x450(5/2)001-1/250/5/2 =2012x2303/101001/1030/3/10

11、 =10018/512006/517/5 T000 6/50x38400178/2529/257x1201002/5-1/512x224010 3/254/28428712034/2511/3500034/25-11/35X*= (20，24, 84,0, 0)T. max z =7 X 20+12 X 24=428三、非標(biāo)準(zhǔn)型線性規(guī)劃問題的解法：1、一般地，對(duì)于約束條件組：若為 公”，則加松弛變量，使方程成為；若為，則減松弛變量，使方程成為一。我們?cè)谇懊鏄?biāo)準(zhǔn)型中是規(guī)定目標(biāo)函數(shù)求極大值。如果在實(shí)際問題中遇到的是求極小值，則為非標(biāo)準(zhǔn)型?？勺魅缦绿幚恚簄n由目標(biāo)函數(shù)min z= cjxj變成等價(jià)的

12、目標(biāo)函數(shù) max(z) = ( cjxj) j ij i令一z=z， . min z= max z/2-等式約束一一大M法：通過加人工變量的方法，構(gòu)造人造基，從而產(chǎn)生初始可行基。人工變量的價(jià)值系數(shù)為M, M是很大的正數(shù)，從原理上理解又稱為“懲罰系數(shù)”。(課本P29)類型一:目標(biāo)函數(shù)仍為max z,約束條件組w與=。例 1: max z =3xi+5x2s.t.x142x2 123x1 2x218x1, x20解：加入松弛變量x3, x4,得到等效的標(biāo)準(zhǔn)模型：max z =3xi+5x2s.t.Xi X342X2X4 123x1 2x218Xj 0,j 1,2,3,4其中第三個(gè)約束條件雖然是等式

13、，但因無初始解，所以增加一個(gè)人工變量X5,得至 U:max z =3xi+5x2 M X5Xi X342x2x4 12st 3x1 2x2x5 18Xj0, j 1,2，,5單純形表求解過程如下:3500-MCbXbbe lX1X2X3X4X50X34(1)01004/1 =40X41202010-MX5183200118/3 =6-3M-2M00-M3M+3 T5+2M0003X14101000X4120201012/2 =6-MX560(2)-3016/2 =33-2M3+ 3M0-M05T-3-3M003X14101004/1 =40x4600(3)1-16/3 =25x2301 3/2

14、01/23/( 2/3) = 9/235 9/205/2009/2 T0M 5/23x12100-1/31/30x320011/3-1/35x260101/203503/2136000 3/2-M-1X*= (2, 6, 2, 0).max z =3X2+5X6=36類型二:目標(biāo)函數(shù)min z,約束條件組n與=。例2:用單純形法求解min z =4xi+3x2s.t.2xi 4x2 163x1 2x2 12x1, x2 0解：減去松弛變量x3, x4,并化為等效的標(biāo)準(zhǔn)模型:max z/ = - 4xi 3x2s.t.2x1 4x2 x3 163x1 2x2x4 12xj 0,j 1,2,3,4

15、增加人工變量X5、X6,得到：max z/ = 4xi 3x2 Mx5 Mx6s.t2x1 4x2 x3X5 163x1 2x2X4x6 12xj 0,j 1,2,6單純形表求解過程如下:CbXbb一 40x30x4-Mx5-Mx6e lx1x2-Mx5162(4)-101016/4=4-Mx61232010112/2=6-5M-6MMMMM5M -46M 3T-M-M00-3x241/21-1/401/404/1/2=8Mx64(2)01/211/214/2=2-2M-3/2-33/4 M/2MM/2 3/4一 M2M 5/2 T0M/2 3/4一 M3/4-3M/20-3x2301 3/8

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

17、下所能使用的有效總工時(shí)數(shù)如下表：設(shè)消耗m備ABC利潤(rùn)（萬元）甲35970乙95330啟效總工時(shí)540450720問：該廠應(yīng)如何組織生產(chǎn)，即生產(chǎn)多少甲、乙產(chǎn)品使得該廠的總利潤(rùn)為最大?解:原問題設(shè)XI、X2為生產(chǎn)甲、乙產(chǎn)品的數(shù)量max z = 70Xi+30X2s.t.3xi 9X25405xi 5X24509x1 3x2720X1, x20將這個(gè)原問題化為它的對(duì)偶問題一一設(shè)yi、V2、y2分別為設(shè)備a、b、C單位工時(shí)數(shù)的加工費(fèi)。min w = 540yi+450y2+720y3s.t.3y1 5y2 9y3 709 y1 5y2 3y3 30V, 0, i 123用大M法，先化為等效的標(biāo)準(zhǔn)模型：

18、max w/ =- 540y1 450y2 720y3s.t.3y1 5y2 9y3 y4709y1 5 y2 3y3y5 30yj 0,j 1,2,5增加人工變量y6、y7,得到：max z/ = 540y1 450y2 720y3 My 6 My 7s.t3y1 5 y2 9 y3 y4v& 709y1 5 y2 3y3V5 V7 30yj 0,j 1,2,5大M法單純形表求解過程如下： 540 450 72000-M-MCbXbbe ly1y2y3y4y5y6y7-My670359101070/3-My730（9）530-10130/9=10/3-12M-10M-12MMMMM1

19、2M -540 T10M -45012M -720-M-M00My660010/3(8)11/31 1/360/8=2.5 540yi10/315/91/30-1/901/910/3/1/3=10-300+10/3 M-8M-180-MM/3+6 0-MM/3 600-150+10/3 M8M -540 TMM/3 600M/3+6 0-720y315/205/121-1/81/241/8-1/2415/2/5/12=18 540yi5/61(5/12)01/24-1/8-1/241/85/6/5/12=2 540 572-720 -135/2475/12135/2 75/20125 T013

20、5/2-475/12135/2 M75/2 M-720y320/3-1011/61/61/6-1/6 450y2212/5101/10 3/10-1/103/10 360 450-720751575-15 5700M15-My*= (0,2,20-Q，0， 30) T以內(nèi)1 口型陽取1 兀用牛最優(yōu)目標(biāo)函數(shù)值 min w = （ 5700） =5700五、運(yùn)輸規(guī)劃問題：運(yùn)輸規(guī)劃問題的特殊解法一一“表上作業(yè)法”解題步驟：1、找出初始調(diào)運(yùn)方案。即在（m x n）產(chǎn)銷平衡表上給出m+n-1個(gè)數(shù)字格。（最小元素法）2、（對(duì)空格）求檢驗(yàn)數(shù)。判別是否達(dá)到最優(yōu)解。如已是最優(yōu)解，則停止

21、計(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ī)劃問題（又稱“供需平衡”、“產(chǎn)銷平衡”）弓I例：某鋼鐵公司有三個(gè)鐵礦和四個(gè)煉鐵廠， 鐵礦的年產(chǎn)礦石量分別為100萬噸、80萬噸和50萬噸，煉鐵廠年需礦石量分別為 50萬噸、70萬噸、80萬噸解：用“表上作業(yè)法”求解先用最低費(fèi)用法（最小元素法）求此問題的初始基礎(chǔ)可行解:初始方案:費(fèi)銷BiB2B3B4SiAi1520673306510020X80XA270814442

22、0803020X30A3125332033251050x50xx銷量dj50708030 230230 50B2Z=15 X 20+3 X 80+70 X 30+8 乂 20+20X 30+3 乂 50=3550 （噸.公里）對(duì)的初始可行解進(jìn)行迭代 （表上閉回路法），求最優(yōu)解：最優(yōu)方案:Ai. A 2A3費(fèi)銷BiB2B3B4SiAi1520143301210020X80XA27053814一 92080X50X30A312320202510503020Xx銷量dj50708030230 230 用表上閉回路法調(diào)整后，從上表可看出，所有檢驗(yàn)數(shù)0,已得最優(yōu)解Z=15 X 20+3 x 80+8x

23、50+20x 30+12X 30+3 x 20=1960 （噸.公里）解法分析：如何求檢驗(yàn)數(shù)并由此確定入基變量？有數(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ù) ij Cj Cj,必須j00,才得到最優(yōu)奇點(diǎn) 偶點(diǎn)解。否則，應(yīng)選所有中正的最大者對(duì)應(yīng)的變量 為為入基變量進(jì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)輸規(guī)劃問題mn

24、若 Sidj ,則是供大于求（供過于求）問題，可設(shè)一虛銷地 Bn+1 ,令i 1j 1mnmnCin+1=0, dn+l= S dj ,轉(zhuǎn)化為產(chǎn)銷平衡問題。若sidj ,則是供小'i 1 j 1i 1j 1nm于求（供不應(yīng)求）問題，可設(shè)一虛產(chǎn)地 Am+1,令Cm+1,j=0, Sm+1= djsi ,j 1i 1轉(zhuǎn)化為產(chǎn)銷平衡問題。（,2,，m , 2,，n）六、工作指派問題：工作指派問題的數(shù)學(xué)模型假定有n項(xiàng)工作需要完成，恰好有n個(gè)人每人可去完成其中一項(xiàng)工作，效果要好。工作指派問題的特殊解法一一“匈牙利法”（考?。┙忸}步驟：1、使系數(shù)矩陣（效率矩陣）各行、各列出現(xiàn)零元素。作法：行約簡(jiǎn)一

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

26、號(hào)的列畫一縱線，這就得到覆蓋所有 0元素的最少直線數(shù)。未被直線覆蓋的最小元素為 Cj,在未被直線覆蓋處減去Cj,在直線交叉處加上 cij04、重復(fù)2、3,直到求得最優(yōu)解。類型一:求極小值的匈牙利法：（重點(diǎn)掌握這種基本問題）例1:有甲、乙、丙、丁四個(gè)人，要派去完成 A、B、C、D四項(xiàng)工作，他們完成的工時(shí)如下表:一工ABCD甲612134乙1031214丙7141316丁881210試問：應(yīng)如何分配任務(wù)可使總工時(shí)為最少?解：用“匈牙利法”求解 已知條件可用系數(shù)矩陣（效率矩陣）表示為:61213_ 10312714138812列約簡(jiǎn)01192A B2857050720000119228號(hào)(0)稱號(hào)(

27、0)乙511(0)=>成9* *00X0)2使總工時(shí)為最少的分配任務(wù)方案為：甲fD,乙-B,丙A, 丁 C此時(shí)總工時(shí)數(shù)W=4+3+7+12=26例2:求效率矩陣109758754623487的最優(yōu)解。55解:10977643 , 2在約簡(jiǎn)10:50121213列約簡(jiǎn)32003210201232(0)01 林0)3201(0)2一 *2012*010*所畫（）0元素少于n,未得到最優(yōu)解,2需要繼續(xù)變換矩陣（求能覆蓋所有0元素的最少數(shù)直線集合）32(0)31(0)*01*(0)021*2022未被直線覆蓋的最小元素為 %=1,在未被直線覆蓋處減去1,在直線交叉處加上1。40202200012

28、1*10(0)(0)121*0*0(0)10010100000010100類型二：求極大值的匈牙利法:min z= max ( z)(5) (MCj) = (bj), (q)中最大的元素為 Mmaxz=cij xij =(M cij )xiji ji j=(M cij )xij -cij xiji ji j第一部分到此結(jié)束第二部分動(dòng)態(tài)規(guī)劃只要求掌握動(dòng)態(tài)規(guī)劃的最短路問題一一用“圖上標(biāo)號(hào)法”解決：具體解題步 驟請(qǐng)參看教材P103 （這是本套資料少見的與教材完全相同的算法類型之一，務(wù) 必看書掌握）學(xué)員們只有完全理解了這種作法（思路： 逆向追蹤）才有可能做題，考試時(shí)數(shù)字無論如 何變化都能作出正確求解！第二部分到此結(jié)束第三部分網(wǎng)絡(luò)分析、求最小生成樹（最小支撐樹、最小樹）問題:破圈法一一任取一個(gè)圈，從圈中去掉一條權(quán)最大的邊（如果有兩條或