運(yùn)籌學(xué)復(fù)習(xí)參考資料知識(shí)點(diǎn)及習(xí)題

1、第一部分線性規(guī)劃問題的求解一、兩個(gè)變量的線性規(guī)劃問題的圖解法：概念準(zhǔn)備：定義：滿足所有約束條件的解為可行解；可行解的全體稱為可 行（解）域。定義：達(dá)到目標(biāo)的可行解為最優(yōu)解。圖解法：圖解法采用直角坐標(biāo)求解：X,橫軸；X2豎軸。1、將約束條件（取等 號(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í)不

2、同，這些產(chǎn)品銷售后所能獲得利潤(rùn)以及這三種加工設(shè)問：該廠應(yīng)如何組織生產(chǎn)，即生產(chǎn)多少甲、乙產(chǎn)品使得該廠的總利潤(rùn)為最大？（此題也可用“單純形法”或化對(duì)偶問題”用大M法求解）解：設(shè)X X?為生產(chǎn)甲.乙產(chǎn)品的數(shù)量。max z = 70xi+30x2s. t.3! + 9x2 540(2)5Xj + 5x2 450(3)9X +3x? 0(5)、(6)可行解域?yàn)閛abcdO,最優(yōu)解為b點(diǎn)由方程組解出X尸75, X2二155 Xj +5x2 =4509x, +3x2 =720/.max z 二70X75+30X15-5700例2：用圖解法求解max z = 6xi+4x2s. t.2州 + x2 10(2)

3、Xj + x2 8(3)x2 0(5)、(6)A?：可行解域?yàn)閛abcdO,最優(yōu)解為b點(diǎn)由方程組J2X +x2 = 10 %! +x2 =8解出 X二2, X2二6X = E = (2, 6) T 帆丿max z = 6 X 2+4 X 6=36例3：用圖解法求解min z =3xj+x2s. tX4(2)x, 12(4)X + 2兀2 5 8(5)xf x2 0(6)、(7)A?：可行解域?yàn)閎cdefb,最優(yōu)解為b點(diǎn)。由方程組X =4+5x2 = 124解出 xi=4, x2=y45)T1niin z =3X4+y = 11 _ 二、標(biāo)準(zhǔn)型線性規(guī)劃問題的單純形解法：一般思路：1、用簡(jiǎn)單易行的

4、方法獲得初始基本可行解；2、對(duì)上述解進(jìn)行檢驗(yàn)，檢驗(yàn)其是否為最優(yōu)解，若是，停止迭代，否則轉(zhuǎn)入3；3、根據(jù)eL規(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)解。具體做法（可化歸標(biāo)準(zhǔn)型的情況）：設(shè)已知max z = C1X1+ c2x2+xn0內(nèi) +al2x2 +.+anxn bx+a22x2 + +d幼兀 0 確定所對(duì)應(yīng)的行的變量為出基變量，行、列交 aik.叉處為主元素，迭代時(shí)要求將主元素變?yōu)?,此列其余元素變?yōu)?。例1:用單純形法求解(本題即是本資料P2 “圖解法例1的單純形解法;也可化“對(duì)偶問題”

5、求解)max z 二70xi+30x2s. t.3州 +9吃 540+5x2 4509%j +3七 0解：加入松弛變量X3, x.t, x5,得到等效的標(biāo)準(zhǔn)模型：max z =70x1+30x2+0 x3+0 Xi+0 x5s. t.3x +9x2 + 兀3 =5405%! +5x2+x4 =4509Xj + 3x2+x5 = 720Xj 0J = l,2,.5列表計(jì)算如下:CbXbb70Xi30X20X30Xi0X50L0X354039100540/3 =1800X445055010450/5 =900X5720(9)3001720/9 =80070 f0300000000X33000810

6、-1/3300/8 =37.50Xi500(10/3)01-5/950/10/3 =1570Xi8011/3001/980/1/3 =24070070/320/3 t000070/9-70/90X3180001-12/5130X2150103/10-1/670Xi75100-1/101/65700700300002-220/3-20/3X*= (75, 15, 180, 0, 0) T/.max z =70X75+30X15=5700例2：用單純形法求解max z =7xi+12x2s. t.9xj +4兀2 3604州 + 5x2 2003X +IOX2 0解：加入松弛變量X3, x4, x

7、5,得到等效的標(biāo)準(zhǔn)模型:max z =7xi+12x2+0 x3+0 x4+0 x59Xj +4x2 +七=3604x, + 5x2+x4 = 2003X+10x2+x5 =3000,y = 1,2,.5列表計(jì)算如下:CbXbb7Xi12X20X30Xi0X50i.0X336094100360/4 =900X420045010200/5 =400X53003(10)001300/10 =3007012 t0000000X324078/10010- 2/5240/78/10 =2400/780X450(5/2)001-1/250/5/2 =2012X2303/101001/1030/3/10 =

8、10018/517/5 t12000006/5-6/50X384001-78/2529/257Xi201002/5- 1/512X224010-3/254/28428701200034/25-34/2511/35-11/35X*= (20, 24, 84, 0, 0) TAmax z =7X20+12X24=428三、非標(biāo)準(zhǔn)型線性規(guī)劃問題的解法:1、一般地，對(duì)于約束條件組：若為“W”，則加松弛變量，使方程成為“ = ”；若為“鼻”，則減松弛變量，使方程成為“=”。我們?cè)谇懊鏄?biāo)準(zhǔn)型中是規(guī)定目標(biāo)函數(shù)求極大值。如果在實(shí)際問題中遇到的是求 極小值，則為非標(biāo)準(zhǔn)型?？勺魅缦绿幚恚河赡繕?biāo)函數(shù)min z= X

9、 cjxj變成等價(jià)的目標(biāo)函數(shù)max （z）二工（一勺）7=11令一z二z ,min z=max z2、等式約束大M法：通過加人工變量的方法，構(gòu)造人造基，從而產(chǎn)生初始可行基。人工變量的價(jià) 值系數(shù)為一M, M是很大的正數(shù)，從原理上理解又稱為“懲罰系數(shù)”。（課本P29） 類型_:目標(biāo)函數(shù)仍為max z,約束條件組W與=。例 1： max z =3xi+5x2x, 42x, 120解：加入松弛變量X3, X,得到等效的標(biāo)準(zhǔn)模型：max z 二3xi+5x2s. tXj + x3 = 42x2+x4 = 123X 4- 2x2= 18xj 0, j = 1,2,3,4其中第三個(gè)約束條件雖然是等式，但因無

10、初始解，所以增加一個(gè)人工變量X5,得到： max z =3xi+5x2Mx5 + 也=42兀2+屯=12s. t.3兀+ 2x2+ 兀5 =18“ n0J = l,2,.5單純形表求解過程如下:CbXbb3Xi5X20X30Xi-MX50i.0X34(1)01004/1 =40X41202010-MX5183200118/3 =6-3M-2M00-M3M+3 t5+2M0003Xl4101000X4120201012/2 =6-MX560(2)-3016/2 =33-2M3+3M0-M05 t-3-3M003Xl4101004/1 =40X4600(3)1-16/3 =25X2301-3/20

11、1/23/(-2/3)=-9/235-9/205/2009/2 t0M5/23Xi2100-1/31/30X320011/3-1/35X260101/203503/2136000-3/2-M-lX*= (2, 6, 2, 0) T/. max z =3 X 2+5 X 6=36類型二目標(biāo)函數(shù)min z,約束條件組N與=。例2：用單純形法求解min z 二4xi+3x2s. t.2xt +4x2 16 12X, x2 0解：減去松弛變量X3, X4,并化為等效的標(biāo)準(zhǔn)模型:max z =4xi 3x2s. t2X| +4x2 x3 = 160, J = 1,23,4增加人工變量X5、X6,得到：m

12、ax z 二4xi 3x2Mx.5Mx(；s. t2X + 4x2 -x3+x5 = 16、3x, + 2x2-x4+x6 = 12Xj 0,y = 1,2,., 6單純形表求解過程如下:CbXbb-40X30Xi-MX5-MX60LXiX2-MX5162(4)-101016/4=4-MX612320-10112/2=6-5M6MMM-M-M5M46M-3 t-M-M00-3X241/21-1/401/404/l/2=8-MX64(2)01/2-1-1/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

13、1/43/8-1/4-4Xi2101/4-1/2-1/41/2-17-40-301/8-1/85/4 5/4-1/8M+1/8-5/4M+5/4X*= (2, 3, 0, 0) 1/.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è) 備因各種條件下所能使用的有效總工

14、時(shí)數(shù)如下表：設(shè) 消備ABC利潤(rùn) （萬(wà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. t3召 + 9心 5405兀+ 5兀2 4509兀+3x2 0將這個(gè)原問題化為它的對(duì)偶問題設(shè)yi. y2. y2分別為設(shè)備A、B、C單位工時(shí)數(shù)的加工費(fèi)。 min w = 540y!+450y2+720y3s. t.+5），2+9）“7 9）+5y2 +3）b 30y, 0, i = 1,2,3用大M法，先化為等效的標(biāo)準(zhǔn)模型：max w 二一540y

15、】一450丫2720y3s. t.3兀+5歹2+9兒一九=709）+5），2+3為-y5 = 30yj 0,j = l,2,.,5增加人工變量y6. y7,得到：max z =540y!450y2720y3My6_My7s. t3必+5力+9力一），4+6=70*9）|+5，2+3兒一）i+ +77=30yj 0, j =1,2,., 5大M法單純形表求解過程如下:該對(duì)偶問題的最優(yōu)解是/二（0, 2,2030,最優(yōu)目標(biāo)函數(shù)值min w(-5700) =5700CbXbb-540yi-450y2-720y300ysMye-M0L-Mye70359-101070/3-My?30(9)530-101

16、30/9=10/3-12M-10M-12MMM-M-M12M-540 f10M-45012M-720-M-M00-My660010/3(8)-11/31-1/360/8=2. 5-540yi10/315/91/30-1/901/910/3/1/3=10-300+10/3M-8M-180-M-M/3+60-MM/3-600-150+10/3M8M-540 tMM/3-600-M/3+6015/2/5/1-720y315/205/121-1/81/241/8-1/242=18-540y5/61(5/12)01/24-1/8-1/241/85/6/5/12=2540-572-720-135/2475

17、/12-135/2-75/20125 t0135/2-475/12135/2-M75/2M-720ys20/3-1011/61/61/6-1/6-450y2212/5101/10-3/10-1/103/10-360-450-7207515-75-15-5700-18000-75-1575-M15-M五、運(yùn)輸規(guī)劃問題：運(yùn)輸規(guī)劃問題的特殊解法一一“表上作業(yè)法”解題步驟：1、找出初始調(diào)運(yùn)方案。即在（mXn）產(chǎn)銷平衡表上給出m+n-l個(gè)數(shù)字格。（最小元素法）2、（對(duì)空格）求檢驗(yàn)數(shù)。判別是否達(dá)到最優(yōu)解。如已是最優(yōu)解，則停止計(jì)算，否則轉(zhuǎn)到下一 步。（閉回路法）3、對(duì)方案進(jìn)行改善，找出新的調(diào)運(yùn)方案。（根據(jù)檢

18、驗(yàn)結(jié)果選擇入基變量，用表上閉回路法調(diào) 整一一即迭代計(jì)算，得新的基本可行解）4、重復(fù)2、3,再檢驗(yàn)、再迭代，直到求得最優(yōu)調(diào)運(yùn)方案。類型一:供求平衡的運(yùn)輸規(guī)劃問題（又稱“供需平衡”、“產(chǎn)銷平衡”）引例：某鋼鐵公司有三個(gè)鐵礦和四個(gè)煉鐵廠，鐵礦的年產(chǎn)礦石量分別為100萬(wàn)噸、80萬(wàn)噸和50萬(wàn)噸，煉鐵廠年需礦石量分別為50萬(wàn)噸、70萬(wàn)噸、80萬(wàn)噸問：該公司應(yīng)如何組織運(yùn)輸，既滿足各煉鐵廠需要，又使總的運(yùn)輸費(fèi)用為最?。ò磭嵐镉?jì)）？ 解：用“表上作業(yè)法”求解。先用最低費(fèi)用法（最小元素法）求此問題的初始基礎(chǔ)可行解：費(fèi)銷BiB2b3B4產(chǎn)量SiAi1520-673306510020X80XA27081444208

19、03020X30A312533203a25-1050X50XX銷量d-50708030 230230 初始方案:Z=15X20+3 X 80+70 X 30+8 X20+20 X 30+3 X 50=3550 （噸公里）對(duì)（1）的初始可行解進(jìn)行迭代（表上閉回路法），求最優(yōu)解：費(fèi)銷BiB2BsB4產(chǎn)量SiAi1520-14330-1210020X80XA270-53814-92080X50X30A312320-2025-10503020XX銷量d-50708030 230230 用表上閉回路法調(diào)整后，從上表可看出，所有檢驗(yàn)數(shù)。0,已得最優(yōu)解。最優(yōu)方案:,B.50B230B.AiA2A380* B

20、s30*B420*b2Z二 15 X 20+3 X 80+8 X 50+20 X 30+12 X 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ù)= co 一力勺，必須6j W0,才得到最優(yōu) 奇點(diǎn) 偶點(diǎn)解。否則,應(yīng)選所有b中正的最大者對(duì)應(yīng)的變量X,為入基變量進(jìn)行迭代（調(diào)整）。檢驗(yàn)后 調(diào)整運(yùn)輸方案的辦法是:在空格的閉回路中所有的偶,盤均加上奇點(diǎn)中的最小運(yùn)量,所有的奇 點(diǎn)、均減去奇點(diǎn)中的最小運(yùn)量。重復(fù)以

21、上兩步,再檢驗(yàn)、再調(diào)整,直到求得最優(yōu)運(yùn)輸方案。類型二供求不平衡的運(yùn)輸規(guī)劃問題mn若Ddj,則是供大于求（供過于求）問題，可設(shè)一虛銷地場(chǎng)切 令 注 I;=1mnmnCi”l=O, dn+i=2-2Z，轉(zhuǎn)化為產(chǎn)銷平衡問題。若 D 則是供小/=y=i/=jy=inm于求（供不應(yīng)求）問題，可設(shè)一虛產(chǎn)地&田，令Cm+l,j=O, Sm+1二廠乞，;=1/=1轉(zhuǎn)化為產(chǎn)銷平衡問題。（,2,，m；, 2,，n）六、工作指派問題：工作指派問題的數(shù)學(xué)模型假定有n項(xiàng)工作需要完成，恰好有n個(gè)人每人可 去完成其中一項(xiàng)工作，效果要好。工作指派問題的特殊解“匈牙利法”（考?。┙忸}步驟：1、使系數(shù)矩陣（效率矩陣）各行、各列出

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

23、J號(hào)的列畫一縱線，這就得到覆蓋所有0元素的 最少直線數(shù)。未被直線覆蓋的最小元素為Cij,在未被直線覆蓋處減去Cij,在直線交叉處加 上 Cij。4、重復(fù)2、3,直到求得最優(yōu)解。類型一求極小值的匈牙利法：（重點(diǎn)掌握這種基本問題）例1:有甲、乙、丙、丁四個(gè)人，要派去完成A、B、C、D四項(xiàng)工作，他們完成的工時(shí)如下表:試問：應(yīng)如何分配任務(wù)可使總工時(shí)為最少？ 解：用“匈牙利法”求解。已知條件可用系數(shù)矩陣（效率矩陣）表示為:f 61012313124、14（C;；）二1J71413161 881210丿89097604ABCD甲285(0)、，2850、70511標(biāo)號(hào)r乙7(0)51107291 :/丙(

24、0)72954651021 2345;0、010o o得最優(yōu)解：罕 0 11000類型二求極大值的匈牙利法:min z=max (z)（切）f （Mcj7）二（切），（切）中最大的元素為MmaxZ=Z Z 勺勺二工 E (M Cij)% i Ji j=Z Z(Mcxij - XX cijxa i 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)最大的邊（如果有兩條或兩條 以上的邊都是權(quán)最大的邊，則任意去掉其中一條）。在余下的圖中，重復(fù)這個(gè)步 驟，直到得到一個(gè)不含圈的圖為止，這時(shí)的圖便是最小樹。參考例題：例：求下圖的最小生成樹：V2V4V1V3V510V6解：用“破圈法”求得最小生成樹為:V3V5已得最小樹,此時(shí)權(quán)w= 1+2+4+5+9=21為最小。二、最短路問題：（有向圖）TP標(biāo)號(hào)法（狄克斯托算法）一一具體解題步驟請(qǐng)參看教材P125 （這是本套 資料少見的與教