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

1、Good is good, but better carries it.精益求精，善益求善。運(yùn)籌學(xué)復(fù)習(xí)參考資料-運(yùn)籌學(xué)復(fù)習(xí)參考資料資料加工、整理人楊峰（函授總站高級(jí)講師）要求掌握的各部分知識(shí)點(diǎn)HYPERLINKl第一部分第一部分線(xiàn)性規(guī)劃問(wèn)題的求解（相當(dāng)于教材的第一章）重要算法：?jiǎn)渭冃蔚?、大M法單純形迭代、表上作業(yè)法、匈牙利法HYPERLINKl第二部分第二部分動(dòng)態(tài)規(guī)劃問(wèn)題的求解（相當(dāng)于教材的第三章）重要算法：圖上標(biāo)號(hào)法HYPERLINKl第三部分第三部分網(wǎng)絡(luò)分析問(wèn)題的求解（相當(dāng)于教材的第四章）重要算法：破圈法、TP標(biāo)號(hào)法、尋求網(wǎng)絡(luò)最大流的標(biāo)號(hào)法HYPERLINKl第四部分第四部分存儲(chǔ)論簡(jiǎn)介（

2、相當(dāng)于教材的第七章）楊老師關(guān)于學(xué)習(xí)方法的提示：運(yùn)籌學(xué)屬于應(yīng)用數(shù)學(xué)的范疇，本門(mén)課程在管理類(lèi)本科生層次開(kāi)設(shè)時(shí)，又稱(chēng)“管理運(yùn)籌學(xué)”，是現(xiàn)代數(shù)學(xué)理論和計(jì)算機(jī)技術(shù)應(yīng)用于管理科學(xué)的新興學(xué)科。非應(yīng)用數(shù)學(xué)系（專(zhuān)業(yè)）學(xué)生學(xué)習(xí)本門(mén)課程之前務(wù)必先具備“高數(shù)”（線(xiàn)性代數(shù)、概率論與數(shù)理統(tǒng)計(jì)）的知識(shí)基礎(chǔ)。學(xué)員同志們通過(guò)學(xué)習(xí)，必須領(lǐng)會(huì)數(shù)學(xué)建模的思想、系統(tǒng)工程的思想。非全日制學(xué)生學(xué)習(xí)時(shí)，只要求知道若干典型數(shù)學(xué)模型及其算法的操作，即只須明白“怎樣做”，而不必去過(guò)問(wèn)“為什么”要這樣做。第一部分線(xiàn)性規(guī)劃問(wèn)題的求解一、兩個(gè)變量的線(xiàn)性規(guī)劃問(wèn)題的圖解法：概念準(zhǔn)備：定義：滿(mǎn)足所有約束條件的解為可行解；可行解的全體稱(chēng)為可行（解）域。定義：達(dá)

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

4、0有效總工時(shí)540450720問(wèn)：該廠應(yīng)如何組織生產(chǎn)，即生產(chǎn)多少甲、乙產(chǎn)品使得該廠的總利潤(rùn)為最大？（此題也可用“HYPERLINKlP2例1的單純形解法單純形法”或化“HYPERLINKlP7例1的對(duì)偶問(wèn)題大M解法對(duì)偶問(wèn)題”用大M法求解）解：設(shè)x1、x2為生產(chǎn)甲、乙產(chǎn)品的數(shù)量。maxz=70 x1+30 x2s.t.、可行解域?yàn)閛abcd0，最優(yōu)解為b點(diǎn)。由方程組解出x1=75，x2=15X*=（75，15）Tmaxz=Z*=7075+3015=5700例2：用圖解法求解maxz=6x1+4x2s.t.、解：可行解域?yàn)閛abcd0，最優(yōu)解為b點(diǎn)。由方程組解出x1=2，x2=6X*=（2，6）T

5、maxz=62+46=36例3：用圖解法求解minz=3x1+x2s.t.、解：可行解域?yàn)閎cdefb，最優(yōu)解為b點(diǎn)。由方程組解出x1=4，x2=X*=（4，）Tminz=34+=11二、標(biāo)準(zhǔn)型線(xiàn)性規(guī)劃問(wèn)題的單純形解法：一般思路：1、用簡(jiǎn)單易行的方法獲得初始基本可行解；2、對(duì)上述解進(jìn)行檢驗(yàn)，檢驗(yàn)其是否為最優(yōu)解，若是，停止迭代，否則轉(zhuǎn)入3；3、根據(jù)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)解。具體做法（可化歸標(biāo)準(zhǔn)型的情況）：設(shè)已知maxz=c1x1+c2x2+cnxns.t.對(duì)第i個(gè)方程加入松弛變

6、量xn+i，i=1，2，m，得到列表計(jì)算，格式、算法如下：CBXBbc1c2cn+mLx1x2xn+mcn+1xn+1b1a11a12a1n+mcn+2xn+2b2a21a22a2n+mxn+mbnam1am2amn+mz1z2zn+m12n+m注：zj=cn+1a1j+cn+2a2j+cn+mamj=，（j=1，2，n+m）j=cjzj,當(dāng)j0時(shí)，當(dāng)前解最優(yōu)。注：由maxj確定所對(duì)應(yīng)的行的變量為“入基變量”；由L=確定所對(duì)應(yīng)的行的變量為“出基變量”，行、列交叉處為主元素，迭代時(shí)要求將主元素變?yōu)?，此列其余元素變?yōu)?。例1：用單純形法求解（本題即是本資料P2“HYPERLINKlP7例1的圖解

7、法圖解法”例1的單純形解法；也可化“HYPERLINKlP7例1的對(duì)偶問(wèn)題大M解法對(duì)偶問(wèn)題”求解）maxz=70 x1+30 x2s.t.解：加入松弛變量x3，x4，x5，得到等效的標(biāo)準(zhǔn)模型：maxz=70 x1+30 x2+0 x3+0 x4+0 x5s.t.列表計(jì)算如下：CBXBb7030000Lx1x2x3x4x50 x354039100540/3=1800 x445055010450/5=900 x5720（9）3001720/9=800000070300000 x33000810-1/3300/8=37.50 x4500（10/3）01-5/950/10/3=1570 x18011/

8、3001/980/1/3=2407070/30070/9020/30070/90 x318000112/5130 x2150103/10-1/670 x175100-1/101/6570070300220/3000-220/3X*=（75，15，180，0，0）Tmaxz=7075+3015=5700例2：用單純形法求解maxz=7x1+12x2s.t.解：加入松弛變量x3，x4，x5，得到等效的標(biāo)準(zhǔn)模型：maxz=7x1+12x2+0 x3+0 x4+0 x5s.t.列表計(jì)算如下：CBXBb712000Lx1x2x3x4x50 x336094100360/4=900 x42004501020

9、0/5=400 x53003（10）001300/10=30000007120000 x324078/10010-2/5240/78/10=2400/780 x450（5/2）001-1/250/5/2=2012x2303/101001/1030/3/10=10018/512006/517/50006/50 x38400178/2529/257x1201002/5-1/512x2240103/254/28428712034/2511/3500034/2511/35X*=（20，24，84，0，0）Tmaxz=720+1224=428三、非標(biāo)準(zhǔn)型線(xiàn)性規(guī)劃問(wèn)題的解法：1、一般地，對(duì)于約束條件組：若

10、為“”，則加松弛變量，使方程成為“”；若為“”，則減松弛變量，使方程成為“”。我們?cè)谇懊鏄?biāo)準(zhǔn)型中是規(guī)定目標(biāo)函數(shù)求極大值。如果在實(shí)際問(wèn)題中遇到的是求極小值，則為非標(biāo)準(zhǔn)型。可作如下處理：由目標(biāo)函數(shù)minz=變成等價(jià)的目標(biāo)函數(shù)max（z）=令z=z/，minz=maxz/2、等式約束大M法：通過(guò)加人工變量的方法，構(gòu)造人造基，從而產(chǎn)生初始可行基。人工變量的價(jià)值系數(shù)為M，M是很大的正數(shù)，從原理上理解又稱(chēng)為“懲罰系數(shù)”。（課本P29）類(lèi)型一：目標(biāo)函數(shù)仍為maxz，約束條件組與。例1：maxz=3x1+5x2s.t.解：加入松弛變量x3，x4，得到等效的標(biāo)準(zhǔn)模型：maxz=3x1+5x2s.t.其中第三個(gè)約

11、束條件雖然是等式，但因無(wú)初始解，所以增加一個(gè)人工變量x5，得到：maxz=3x1+5x2Mx5s.t.單純形表求解過(guò)程如下：CBXBb3500MLx1x2x3x4x50 x34（1）01004/1=40 x41202010Mx5183200118/3=63M2M00M3M352M0003x14101000 x4120201012/2=6Mx560（2）3016/2=332M33M0M0533M003x14101004/1=40 x4600（3）116/3=25x23013/201/23/(2/3)=9/2359/205/2009/20M5/2305x121001/31/3x320011/31/

12、3x260101/20363503/210003/2M1X*=（2，6，2，0）Tmaxz=32+56=36類(lèi)型二：目標(biāo)函數(shù)minz，約束條件組與。例2：用單純形法求解minz=4x1+3x2s.t.解：減去松弛變量x3，x4，并化為等效的標(biāo)準(zhǔn)模型：maxz/=4x13x2s.t.增加人工變量x5、x6，得到：maxz/=4x13x2Mx5Mx6s.t單純形表求解過(guò)程如下：CBXBb400MMLx1x2x3x4x5x6Mx5162（4）101016/4=4Mx61232010112/2=65M6MMMMM5M46M3MM003x241/211/401/404/1/2=8Mx64（2）01/21

13、1/214/2=22M3/233/4M/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，0）Tminz=maxz/=（17）=17四、對(duì)偶問(wèn)題的解法：什么是對(duì)偶問(wèn)題？1、在資源一定的條件下，作出最大的貢獻(xiàn)；2、完成給定的工作，所消耗的資源最少。引例（與本資料P2例1“HYPERLINKlP7例1的圖解法圖解法”、P7例1“HYPERLINKlP2例1的單純形解法單純形法”同）：某工廠生產(chǎn)甲、乙兩種產(chǎn)品，這些產(chǎn)品均需在A、B、C三

14、種不同的設(shè)備上加工，每種產(chǎn)品在不同設(shè)備上加工時(shí)需要不同的工時(shí)，這些產(chǎn)品售后所能獲得的利潤(rùn)值以及這三種加工設(shè)備因各種條件下所能使用的有效總工時(shí)數(shù)如下表：品產(chǎn)耗消備設(shè)ABC利潤(rùn)（萬(wàn)元）甲乙3599537030有效總工時(shí)540450720問(wèn)：該廠應(yīng)如何組織生產(chǎn)，即生產(chǎn)多少甲、乙產(chǎn)品使得該廠的總利潤(rùn)為最大？解：原問(wèn)題設(shè)x1、x2為生產(chǎn)甲、乙產(chǎn)品的數(shù)量。maxz=70 x1+30 x2s.t.將這個(gè)原問(wèn)題化為它的對(duì)偶問(wèn)題設(shè)y1、y2、y2分別為設(shè)備A、B、C單位工時(shí)數(shù)的加工費(fèi)。minw=540y1+450y2+720y3s.t.用大M法，先化為等效的標(biāo)準(zhǔn)模型：maxw/=540y1450y2720y3s

15、.t.增加人工變量y6、y7，得到：maxz/=540y1450y2720y3My6My7s.t大M法單純形表求解過(guò)程如下：CBXBb54045072000MMLy1y2y3y4y5y6y7My670359101070/3My730（9）53010130/9=10/312M10M12MMMMM12M54010M45012M720MM00My660010/3（8）11/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/

16、205/1211/81/241/81/2415/2/5/12=18540y15/61（5/12）01/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該對(duì)偶問(wèn)題的最優(yōu)解是y*=（0，2，0，0）T最優(yōu)目標(biāo)函數(shù)值minw=（5700）=5700五、運(yùn)輸規(guī)劃問(wèn)題：運(yùn)輸規(guī)劃問(wèn)題的特殊解法“表上作業(yè)法”解題步驟：1、找出初

17、始調(diào)運(yùn)方案。即在(mn)產(chǎn)銷(xiāo)平衡表上給出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)方案。類(lèi)型一：供求平衡的運(yùn)輸規(guī)劃問(wèn)題（又稱(chēng)“供需平衡”、“產(chǎn)銷(xiāo)平衡”）引例：某鋼鐵公司有三個(gè)鐵礦和四個(gè)煉鐵廠，鐵礦的年產(chǎn)礦石量分別為100萬(wàn)噸、80萬(wàn)噸和50萬(wàn)噸，煉鐵廠年需礦石量分別為50萬(wàn)噸、70萬(wàn)噸、80萬(wàn)噸和30萬(wàn)噸，這三個(gè)鐵礦與四個(gè)煉鐵廠的距離如下：礦鐵廠

18、鐵離距煉B1B2B3B4A1A2A3152033070814201232015問(wèn)：該公司應(yīng)如何組織運(yùn)輸，既滿(mǎn)足各煉鐵廠需要，又使總的運(yùn)輸費(fèi)用為最小（按噸.公里計(jì)）？解：用“表上作業(yè)法”求解。先用最低費(fèi)用法（最小元素法）求此問(wèn)題的初始基礎(chǔ)可行解：地產(chǎn)用費(fèi)地銷(xiāo)B1B2B3B4產(chǎn)量SiA1152067330651002080A270814442080302030A312533203325105050銷(xiāo)量dj50708030230230初始方案：B2203030B1B3A22080B1B3A1B250A3Z=1520+380+7030+820+2030+350=3550（噸.公里）對(duì)的初始可行解進(jìn)行迭

19、代（表上閉回路法），求最優(yōu)解：地產(chǎn)用費(fèi)地銷(xiāo)B1B2B3B4產(chǎn)量SiA1152014330121002080A27053814920805030A312320202510503020銷(xiāo)量dj50708030230230用表上閉回路法調(diào)整后，從上表可看出，所有檢驗(yàn)數(shù)0，已得最優(yōu)解。最優(yōu)方案：3020B1B2A35030B2B4A22080B1B3A1Z=1520+380+850+2030+1230+320=1960（噸.公里）解法分析：如何求檢驗(yàn)數(shù)并由此確定入基變量？有數(shù)字的空格稱(chēng)為“基格”、打的空格稱(chēng)為“空格”，標(biāo)號(hào)為偶數(shù)的頂點(diǎn)稱(chēng)為偶點(diǎn)、標(biāo)號(hào)為奇數(shù)的頂點(diǎn)稱(chēng)為奇點(diǎn)，出發(fā)點(diǎn)算0故為偶點(diǎn)。找出所有空格

20、的閉回路后計(jì)算它們的檢驗(yàn)數(shù)，必須0，才得到最優(yōu)解。否則，應(yīng)選所有中正的最大者對(duì)應(yīng)的變量xj為入基變量進(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)輸方案。類(lèi)型二：供求不平衡的運(yùn)輸規(guī)劃問(wèn)題若，則是供大于求（供過(guò)于求）問(wèn)題，可設(shè)一虛銷(xiāo)地Bn+1，令ci,n+1=0，dn+1=，轉(zhuǎn)化為產(chǎn)銷(xiāo)平衡問(wèn)題。若，則是供小于求（供不應(yīng)求）問(wèn)題，可設(shè)一虛產(chǎn)地Am+1，令cm+1,j=0，sm+1=，轉(zhuǎn)化為產(chǎn)銷(xiāo)平衡問(wèn)題。（=1，2，m；=1，2，n）六、工作指派問(wèn)題：工作指派問(wèn)題的數(shù)學(xué)模型

21、假定有n項(xiàng)工作需要完成，恰好有n個(gè)人每人可去完成其中一項(xiàng)工作，效果要好。工作指派問(wèn)題的特殊解法“匈牙利法”（考?。┙忸}步驟：1、使系數(shù)矩陣（效率矩陣）各行、各列出現(xiàn)零元素。作法：行約簡(jiǎn)系數(shù)矩陣各行元素減去所在行的最小元素，列約簡(jiǎn)再?gòu)乃镁仃嚨母髁袦p去所在列最小元素。2、試求最優(yōu)解。如能找出n個(gè)位于不同行不同列的零元素，令對(duì)應(yīng)的xij=1，其余xij=0，得最優(yōu)解，結(jié)束；否則下一步。作法：由獨(dú)立0元素的行（列）開(kāi)始，獨(dú)立0元素處畫(huà)（）標(biāo)記，在有（）的行列中劃去（也可打*）其它0元素；再在剩余的0元素中重復(fù)此做法，直至不能標(biāo)記（）為止。3、作能覆蓋所有0元素的最少數(shù)直線(xiàn)集合。作法：對(duì)沒(méi)有（）的行打

22、號(hào)；對(duì)已打號(hào)的行中所有0元素的所在列打號(hào)；再對(duì)打有號(hào)的列中0元素的所在行打號(hào)；重復(fù)、直到得不出新的打號(hào)的行(列)為止；對(duì)沒(méi)有打號(hào)的行畫(huà)一橫線(xiàn)，對(duì)打號(hào)的列畫(huà)一縱線(xiàn)，這就得到覆蓋所有0元素的最少直線(xiàn)數(shù)。未被直線(xiàn)覆蓋的最小元素為cij,在未被直線(xiàn)覆蓋處減去cij,在直線(xiàn)交叉處加上cij。4、重復(fù)2、3，直到求得最優(yōu)解。類(lèi)型一：求極小值的匈牙利法：（重點(diǎn)掌握這種基本問(wèn)題）例1：有甲、乙、丙、丁四個(gè)人，要派去完成A、B、C、D四項(xiàng)工作，他們完成的工時(shí)如下表：人務(wù)時(shí)工任ABCD甲乙丙丁61213410312147141316881210試問(wèn)：應(yīng)如何分配任務(wù)可使總工時(shí)為最少？解：用“匈牙利法”求解。已知條件

23、可用系數(shù)矩陣（效率矩陣）表示為：列約簡(jiǎn)行約簡(jiǎn)（cij）=ABCD標(biāo)號(hào)甲乙丙丁使總工時(shí)為最少的分配任務(wù)方案為：甲D，乙B，丙A，丁C此時(shí)總工時(shí)數(shù)W=4+3+7+12=26例2：求效率矩陣的最優(yōu)解。列約簡(jiǎn)行約簡(jiǎn)解：標(biāo)號(hào)所畫(huà)（）0元素少于n，未得到最優(yōu)解，需要繼續(xù)變換矩陣（求能覆蓋所有0元素的最少數(shù)直線(xiàn)集合）：未被直線(xiàn)覆蓋的最小元素為cij=1,在未被直線(xiàn)覆蓋處減去1,在直線(xiàn)交叉處加上1。標(biāo)號(hào)得最優(yōu)解：類(lèi)型二：求極大值的匈牙利法：minz=max（z）（cij）（Mcij）=（bij），（cij）中最大的元素為Mmaxz=HYPERLINKl要求掌握的各部分知識(shí)點(diǎn)第一部分到此結(jié)束第二部分動(dòng)態(tài)規(guī)劃只要

24、求掌握動(dòng)態(tài)規(guī)劃的最短路問(wèn)題用“圖上標(biāo)號(hào)法”解決：具體解題步驟請(qǐng)參看教材P103（這是本套資料少見(jiàn)的與教材完全相同的算法類(lèi)型之一，務(wù)必看書(shū)掌握）學(xué)員們只有完全理解了這種作法（思路：逆向追蹤）才有可能做題，考試時(shí)數(shù)字無(wú)論如何變化都能作出正確求解！HYPERLINKl要求掌握的各部分知識(shí)點(diǎn)第二部分到此結(jié)束第三部分網(wǎng)絡(luò)分析一、求最小生成樹(shù)（最小支撐樹(shù)、最小樹(shù)）問(wèn)題：破圈法任取一個(gè)圈，從圈中去掉一條權(quán)最大的邊（如果有兩條或兩條以上的邊都是權(quán)最大的邊，則任意去掉其中一條）。在余下的圖中，重復(fù)這個(gè)步驟，直到得到一個(gè)不含圈的圖為止，這時(shí)的圖便是最小樹(shù)。參考例題：例：求下圖的最小生成樹(shù)：67941510v2v1v3v5v4v6328解：用“破圈法”求得最小生成樹(shù)為：9415v2v1v3v5v4v62已得最小樹(shù)，此時(shí)權(quán)w=1+2+4+5+9=21為最小。二、最短路問(wèn)題：（有向圖）TP標(biāo)號(hào)法（狄克斯托算法）具體解題步驟請(qǐng)