運(yùn)籌學(xué)復(fù)習(xí)大綱1

.約束方程標(biāo)準(zhǔn)化處理：[xx+3x.<4如I：《[2玉+5x2>6,線性規(guī)劃問(wèn)題的解：P9線性規(guī)劃問(wèn)題的解的判定(尤其對(duì)偶問(wèn)題解的狀況)。minZ=3玉+2x2-3x3+4x433.線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題轉(zhuǎn)化(表2.2)：如3.線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題轉(zhuǎn)化(表2.2)：如X]-lx2+3x3+4x3.線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題轉(zhuǎn)化(表2.2)：如<2X]—3%2-IX3-4x4—2石之0,x2<0,x3>z無(wú)約束maxW=3%一5y2+2y3Yi+2丫3<3對(duì)偶問(wèn)題:對(duì)偶問(wèn)題:對(duì)偶問(wèn)題:-2yi+y2-3Y3-2<3y1+3y2-7y3=-3

4yl+4y2-4y3=4對(duì)偶問(wèn)題:Yi^0,y220?3無(wú)約束4.對(duì)偶問(wèn)題的基本性質(zhì)：P45-P46重點(diǎn)是性質(zhì)1—5。如：已知原問(wèn)題的最優(yōu)解為X*=(0.0.4),Z=12試求對(duì)偶問(wèn)題的最優(yōu)解?minW=2y+y2+4y32M+3%+%之1(1)解：對(duì)偶問(wèn)題)3%一%+%<4(2)-5必+6y2+必=3(3)712。,％(。-3無(wú)約束將X*=(0.0.4)代入原問(wèn)題中，有下式：所以，依據(jù)互補(bǔ)松弛條件，必有y*產(chǎn)y*2=0,代入對(duì)偶問(wèn)題(3)式，y3=3。因此，對(duì)偶問(wèn)題的最優(yōu)解為丫於(0.0.3),W=12o5.靈敏度分析：重點(diǎn)分析也的影響。maxZ=5%+4x2%+3x2<90如：2否+々(80仇在什么范圍內(nèi)變化，原最優(yōu)基不變？或者給定b的值求最優(yōu)解的變化。V%+x2<45xpx2>0最優(yōu)基：54000CbXbbxlx2x3x4x50x3250012-55xl351001-14x210010-12C「Zj000-1-3B=(尸3，Pi，P2)解得40助3350,即當(dāng)必￡[40,50]時(shí)，最優(yōu)基B不變。6.初始方案的確定Vogel法、位勢(shì)法方案的調(diào)整。如：已知運(yùn)輸問(wèn)題的產(chǎn)銷平衡表、最優(yōu)調(diào)運(yùn)方案及單位運(yùn)價(jià)表如下表所示:產(chǎn)股、Bib2產(chǎn)股、Bib2b3b4產(chǎn)量A)A?A305510151015255銷量5151510產(chǎn)銷平衡表及最優(yōu)方案地產(chǎn)疝、Bib2b3b4A\1012011A2127920A32141618單位運(yùn)價(jià)表試分析：從A2到B2的單位運(yùn)價(jià)C24在什么范圍變化時(shí)，上述最優(yōu)調(diào)運(yùn)方案不變?或者什么狀況下有多個(gè)最優(yōu)方案。7.整數(shù)規(guī)劃問(wèn)題：重點(diǎn)把握割平面法匈牙利法maxZ=x2如:3玉+2x2<6<一3否+2x2<0如:不々>。且為整數(shù)對(duì)應(yīng)LP模型的最終單純形表Cj0100CBXBbxlx2x3x40Xl1101/6-1/61X23/2011/41/4Cj%00-1/4-1/4解：對(duì)X2一行，引入割平面方程：-X3+-X4>-43442標(biāo)準(zhǔn)化：X?X4+5,=434412222Cj01000CbXbbXlX2X3X4si0Xl1101/6-1/601X23/2011/41/400Si-1/200-1/4-1/41Cj%00-1/4-1/40CBXBbXlX2X3上4Si0Xl2/3100-1/32/31X21010010X320011-4Cj?幻0000-1對(duì)汨一行，引入割平面方程：一%+—與之一34313一222標(biāo)準(zhǔn)化：％+5*2=CbXbbXlX2X3X4SiS20Xl2/3100-1/32/301X21010010

8.目標(biāo)規(guī)劃問(wèn)題：重點(diǎn)理解目標(biāo)規(guī)劃為題的建模和圖解法求解。0X320011-400$2-2/3000?2/3-2/310000-10CbXbbXlX2X4SiS20XI0100-1011X20010-103/20X3600150-60Si100011-3/2勺為00010-3/2CBXbbXlX2K3X4si$20Xl110001-1/21X210100100X310010-53/20X4100011-3/2Cjlj000010如：已知一個(gè)生產(chǎn)方案線性規(guī)劃模型如下：其中目標(biāo)函數(shù)為總利潤(rùn)，xl,x2為產(chǎn)品A、B產(chǎn)量?，F(xiàn)有下列目標(biāo):1、要求總利潤(rùn)必需超過(guò)2500元；2、考慮產(chǎn)品受市場(chǎng)影響，為避開(kāi)積壓，A、B的生產(chǎn)量不超過(guò)60件和100件；3、由于甲資源供應(yīng)比較緊急，不要超過(guò)現(xiàn)有量140。試建立目標(biāo)規(guī)劃模型，并用圖解法求解。解：以產(chǎn)品A、B的單件利潤(rùn)比2.5：1為權(quán)系數(shù)，模型如下：圖解法求解：（留意需要簡(jiǎn)潔分析）結(jié)論:C（60,58.3）為所求的滿足解。.用Dijkstra算法求下圖從w到V6的最短路。樹(shù)的性質(zhì)、中國(guó)郵路問(wèn)題（歐拉回路、歐拉通路）.最大流問(wèn)題：?？诉d標(biāo)號(hào)法：此時(shí)可行流即為最大流流量：3+2=51L對(duì)策論：（把握基本概念，最優(yōu)純策略的求解，（最大最小和最小最大優(yōu)勢(shì)原則））.A、B兩人分別有10分（1角）、5分、1分的硬幣各一枚，雙方都不知道的狀況下各出一枚，規(guī)定和為偶數(shù)，A贏得B所出硬幣；和為奇數(shù)，B贏得A所出硬幣。試據(jù)此列出二人零和對(duì)策模型。解：G=S，S2;A}15-「A的贏得矩陣4=15-5-10-1010（2）試通過(guò)對(duì)策分析，