運(yùn)籌學(xué)知識(shí)點(diǎn)總結(jié)

1、運(yùn)籌學(xué)考試時(shí)間：2009-1-4 10:00-12:00考試地點(diǎn)：金融1、2：（二）201 ，會(huì)計(jì)1 、2： （二）106人資1、2：（二）203，工商1 、2： （二）205林經(jīng)1、 2： （二）306答疑時(shí)間：17周周二周四上午8：00-11 ：0018周周一周三上午8：00-11 ：00地點(diǎn)：基礎(chǔ)樓201線性規(guī)劃如何建立線性規(guī)劃的數(shù)學(xué)模型；線性規(guī)劃的標(biāo)準(zhǔn)形有哪些要求？如何把一般的線性規(guī)劃化為標(biāo)準(zhǔn)形式？如何用圖解法求解兩個(gè)變量的線性規(guī)劃問題？由圖解法總結(jié)出線性規(guī)劃問題的解有哪些性質(zhì)？如何用單純形方法求解線性規(guī)劃問題？如何確定初始可行基或如何求初始基本可行解？（兩階段方法）如何寫出一個(gè)線性規(guī)

2、劃問題的對偶問題？如果已知原問題的最優(yōu)解如何求解對偶問題的最優(yōu)解？（對偶的性質(zhì)，互補(bǔ)松緊條件）對偶單純形方法適合解決什么樣的問題？如何求解？對于已經(jīng)求解的一個(gè)線性規(guī)劃問題如果改變價(jià)值向量和右端向量原最優(yōu)解/ 基是否仍是最優(yōu)解/ 基？如果不是，如何進(jìn)一步求解？1、建立線性規(guī)劃的數(shù)學(xué)模型：特點(diǎn)：(1)每個(gè)行動(dòng)方案可用一組變量(X1,，Xn)的值表示，這些變量一般取非負(fù)值；( 2)變量的變化要受某些限制，這些限制條件用一些線性等式或不等式表示；( 3)有一個(gè)需要優(yōu)化的目標(biāo)，它也是變量的線性函數(shù)。2、 線性規(guī)劃的標(biāo)準(zhǔn)形有哪些限制？如何把一般的線性規(guī)劃化為標(biāo)準(zhǔn)形式？目標(biāo)求極?。患s束為等式；變量為非負(fù)。m

3、in z CTXAX bX0例：把下列線性規(guī)劃化為標(biāo)準(zhǔn)形式：maX z 2X1 3X2X1 2X28X1X21X12X1 0, X20解：令X1X3, X2X4 x5，標(biāo)準(zhǔn)型為：minz,2X3 3(X4 X5)X3 2(X4 X5 ) X6 8X3 (X4 X5) X7 1X3+X8 2Xi 0,i 3,4,5,6,7,83、如何用圖解法求解兩個(gè)變量的線性規(guī)劃問題？由圖解法總結(jié)出線性規(guī)劃問題的解有哪些性質(zhì)？例：參看ppt （唯一最優(yōu)解、無窮多最優(yōu)解、無界解、無解）線性規(guī)劃解的性質(zhì)：（基、基本解、基本可行解、凸集、頂點(diǎn)）定理1線性規(guī)劃的可行域是凸集。定理2 X是線性規(guī)劃基可行解的充分必要條件是

4、 X是可行域的頂點(diǎn)。定理3線性規(guī)劃如果有可行解，則一定有基可行解；如果有最優(yōu)解，則一定有基可行解是最優(yōu)解。4、如何用單純形方法求解線性規(guī)劃問題？（單純形表）單純形法的基本法則法則1最優(yōu)性判定法則（檢驗(yàn)數(shù)全部小于等于零時(shí)最優(yōu)）法則2換入變量確定法則（誰最正誰進(jìn)基）法則3換出變量確定法則（最小比值原則）法則4換基迭代運(yùn)算法則min z 2x1 5x2x1 2x2 x385x1 2x2x4204x2x5 12x1 , x2 , x3, x4, x5x1x2乂3x4乂5RHSz250000x3121008x45201020乂50400112z2000-5/4-15x31010-1/22x45001-1

5、/214乂201001/43z00-20-1/4-19x11010-1/22x400-5124x201001/43最優(yōu)解 X*=(2, 3, 0, 4, 0) z*=-2 X2-5 X3=-19。5、如何確定初始可行基或如何求初始基本可行解？(兩階段方法) 例求下列LP問題的最優(yōu)解min z 3x1 x2 x3x1 2x2 x3 114x1 x22x12x33x31用兩階段法來求解它的第一階段是先解輔助問題:min g x6 x7Xi 4X1 2X1 X1,L2x2x2 :,X7 0X3X411312x33X3)X5X6X7XiX2X3X4X5X6X7RHSg00000-1-10X41-211

6、00011X6-4120-1103X7-20100011g-6130-1004X41-21100011X6-4120-1103X7-20100011g0100-10-31X43-20100-110X60100-11-21X3-20100011g00000-1-10X43001-22-512X20100-11-21X3-20100011第二階段:xix2x3x4x5RHSz-311000x43001-212x20100-11x3-201001z-10001-2x43001-212x20100-11x3-201001原問題無界。6、如何寫出原問題的對偶問題？如果已知原問題的最優(yōu)解，如何求解對偶問題

7、的最優(yōu)解？max bTws.t.wi0wi 0AT w cj TAj w cj min c xs.t.aTxbii1,L , paT xbiip 1,L,mXj 0 j 1,L ,qXj0jq 1,L,n例 寫出下面線性規(guī)劃問題的對偶問題min z 2x1 3x2 5x3 x4xix23x3x42x12x3 4x4x2x3x4x1, x2,x30, x40解：原問題的對偶問題為:maxy5 w 14 w 26 w 3w 12 w 22w 1w 333 w12 w2w 35w 14 w2w 31w J,w 20, w 307、對偶單純形方法適合解決什么樣的問題？如何求解?例:min z 15x1

8、24x2 5x36 x2 x3 x425x12x2x3x51x1, x2, x3, x4, x5對偶單純形法的基本法則 法則1最優(yōu)性判定法則（檢驗(yàn)數(shù)全部小于等于零時(shí)最優(yōu)）法則2換出變量確定法則（誰最負(fù)誰出基）法則3換入變量確定法則（最小比值原則）法則4換基迭代運(yùn)算法則x1乂2乂3x4XsRHSz-15-24-5000乂40-6-110-2乂5-5-2-101-1z-150-1-408x2011/6-1/601/3乂5-50-2/3-1/31-1/3z-15/200-7/2-3/217/2x2-5/410-1/41/41/4x315/2011/2-3/21/2寫出對偶問題并求解？(利用互補(bǔ)松緊條

9、件)8、對于已經(jīng)求解的一個(gè)線性規(guī)劃問題如果改變價(jià)值向量和右端向量原最優(yōu)解/基是否仍是最優(yōu)解/基？如果不是，如何進(jìn)一步求 解？例：線性規(guī)劃max z 5x1 4x2x1 3x2902x1 x280x1x2 45x1, x20已知最優(yōu)表:x1x2x3x4乂5RHSz000-1-3-215乂30012-525x11001-135x2010-1210(1)確定x2的系數(shù)C2的變化范圍，使原最優(yōu)解保持最優(yōu);(2)若C2=6,求新的最優(yōu)計(jì)劃。解(1)將上表中的第0行重新計(jì)算檢驗(yàn)數(shù)，得到:XiX2X3X4X5RHSz5C20000X30012-525Xi1001-135X2010-1210z000C2 55

10、 2c2-175-10C2X30012-525Xi1001-135X2010-1210令 C25W0,52C2W0,解得 5/2 WC2W5,即當(dāng) C2在區(qū)間5/2 ,T5中變化時(shí)，最優(yōu)解 X= (35, 10, 25, 0, 0)保持不變(2)當(dāng)C2=6時(shí)，C25=1>0,原最優(yōu)解失去最優(yōu)性，在表中修改第0行后，用單純形法容易求得新的最優(yōu)表如下:X1X2X3X4X5RHSz0001-7-235X30012-525X11001-135X2010-1210z00-1/20-9/2-495/2X4001/21-5/225/2X110-1/203/245/2X2011/20-1/245/2故新

11、的最優(yōu)解為 x:=45/2, x；=45/2, X4*=25/2 , x；= x；=0,最優(yōu)值 z*=495/2 ,例 對于上例中的線性規(guī)劃作下列分析：(1) b3在什么范圍內(nèi)變化，原最優(yōu)基不變?(2)若h=55,求出新的最優(yōu)解解原最優(yōu)基為B= (P3, Pi, P2),由表2-6可得:12-5ET1=0 i 10-12901(1)由 B 1 80 = 0b302-511-1290250-5b380 = 80 b3>0b380 2b3解得40W b3<50,即當(dāng)b3640, 50時(shí)，最優(yōu)基B不變，最優(yōu)解為: *X3250-5b 3*x1 = 80 b3, X4=X5=0, z=5X

12、 (80b3)+4X (80+2b3)*x280 2b3=80+3b3(2)當(dāng) b3=55時(shí),250-5b 32580 b3= 25，以它代替表的b歹U,用對偶單純形法繼續(xù)求解80 2b330X1X2X3X4X5RHSz000-1-3-245X30012-5-25X11001-125X2010-1230z00-3/5-11/50-230X500-1/5-2/515Xi10-1/53/5030X2012/5-1/5020故新的最優(yōu)解為 Xi =30, X2 =20, X5 =5, X3 = X4 =0,最優(yōu)值 z =230。整數(shù)線性規(guī)劃0-1規(guī)劃如何建立整數(shù)線性規(guī)劃的數(shù)學(xué)模型？如何用圖解法求解兩

13、個(gè)變量的整數(shù)線性規(guī)劃問題？割平面方法的基本思想？如何用割平面方法求解整數(shù)線性規(guī)劃問題？分支定界方法的基本思想？如何用分支定界方法求解整數(shù)線性規(guī)劃問題？如何建立0-1 規(guī)劃問題的數(shù)學(xué)模型？如何用隱枚舉法求解0-1 規(guī)劃和匈牙利法求解指派問題？1、 如何建立整數(shù)線性規(guī)劃的數(shù)學(xué)模型？2、 如何用圖解法求解兩個(gè)變量的整數(shù)線性規(guī)劃問題？3、 割平面方法的基本思想？如何用割平面方法求解整數(shù)線性規(guī)劃問題？例考慮純整數(shù)規(guī)劃問題max z x1 x22x1 x2 6 4x1 5x220x10, x20且為整數(shù)解 先不考慮整數(shù)條件，求得其松弛問題的最優(yōu)單純形表為:x1x2x3x4RHSz00-1/6-1/6-13

14、/3x1105/6-1/65/3x201-2/31/38/3由第二行可以生成割平面： 1 x3 + 1 x4> = 1 333引入松弛變量S1后得：一）x3 x4 + S1 = - |333將此約束條件加到表中繼續(xù)求解如下：x1x2x3x4s1RHSz00-1/6-1/60-13/3x1105/6-1/605/3x201-2/31/308/3S100-1/3-1/31-2/3z0000-1/2-4xi100-15/20x20101-24x30011-32所以原問題的最優(yōu)解為：Xi =0, X2=4,最優(yōu)值z =4。4、 分支定界方法的基本思想？如何用分支定界方法求解整數(shù)線性規(guī)劃問題？例求

15、解下面整數(shù)規(guī)劃max z 3x1 2x22 x 1x 292 Xi3x214x10, x 20 且為整數(shù)值5、如何建立0-1規(guī)劃問題的數(shù)學(xué)模型?6、如何用隱枚舉法求解0-1規(guī)劃和匈牙利法求解指派問題?max z 5x1 4x2 3x3Xi3 x2 2X352x1 7x22x23x35x325x13x2 2x3xj 0 或 1 j=1,2,35x14x9 3x34I23(xi, x2, x3)滿 足 條 件？滿足所有 條件？z值(0, 0, 0)XX(0, 0, 1)XX(0, 1, 0)V4(0, 1, 1)VVVX(1, 0, 0)VVXX(1, 0, 1)VVVVVV8(1,1, 0)VV

16、VVVV9(1, 1, 1)VXX動(dòng)態(tài)規(guī)劃了解基本概念（如多階段決策問題、階段、策略） ；了解最優(yōu)性原理；如何用動(dòng)態(tài)規(guī)劃方法求解最短路問題？（圖上作業(yè)、公式求解）如何用動(dòng)態(tài)規(guī)劃方法求解旅行售貨員問題？如何求解多階段的資源分配問題？網(wǎng)絡(luò)分析了解圖的基本概念（如無向圖、有向圖、點(diǎn)、邊、關(guān)聯(lián)、鄰接、次、關(guān)聯(lián)矩陣、鄰接矩陣、握手定理）；樹，支撐樹，如何找最小樹？（破圈法、避圈法、反圈法；）最短路問題？（圖上標(biāo)號法、列表法）最大流問題？（找增廣路）1、 樹， 支撐樹， 如何找最小樹？（破圈法、避圈法、 反圈法； ） 例設(shè)樹有7條邊，則它有（8）個(gè)結(jié)點(diǎn)；例 一個(gè)由3個(gè)分支構(gòu)成的森林，如果有15個(gè)結(jié)點(diǎn)，則該

17、森林至少 有（12）條邊。例 一棵樹T有5個(gè)度為2的結(jié)點(diǎn)，3個(gè)度為3的結(jié)點(diǎn)，4個(gè)度為4 的結(jié)點(diǎn)，2個(gè)度為5的結(jié)點(diǎn)，其余均是度為1的結(jié)點(diǎn)，問T有幾個(gè)度 為1的結(jié)點(diǎn)？解設(shè)T有x個(gè)度為1的結(jié)點(diǎn)，則有5 2+3 3+4 4+2 5+x = 2mm = n - 15+3+4+2+x = n解以上三個(gè)方程得x = 19例：公園路徑系統(tǒng)見下圖，S為入口，T為出口，A、B、C、D E 為5個(gè)景點(diǎn)?，F(xiàn)安裝電話線連接各景點(diǎn)，則最小線路安裝是什么？ 如果某游客剛進(jìn)入入口就急需從出口離開， 那么該游客應(yīng)該如何走最 快？2、最短路問題？（圖上標(biāo)號法、列表法）3、最大流問題？（找增廣路）從甲地到乙地的公路網(wǎng)縱橫交錯(cuò)，每天

18、每條路上的通車量有上限.從 甲地到乙地的每天最多能通車多少輛 ？5（甲）A Q（乙）排隊(duì)論了解排隊(duì)論模型的基本概念和模型。決策分析了解決策分析的基本概念；（狀態(tài)集、決策集、報(bào)酬函數(shù)：基本要素；評價(jià)準(zhǔn)則）會(huì)建立決策分析問題的數(shù)學(xué)模型；（決策表、決策樹）如何求解不確定型決策分析問題；（樂觀法；悲觀法；樂觀系數(shù)法；后悔值法；等可能法）如何求解風(fēng)險(xiǎn)型決策分析問題；（最大可能法；期望值法）效用函數(shù)的概念；會(huì)用效用函數(shù)來進(jìn)行決策（期望效用值）；會(huì)計(jì)算信息的價(jià)值、完全信息的價(jià)值。對策論例 A 、 B 兩人分別有1 角、 5 分和1 分的硬幣各一枚。在雙方互不知道的情況下，各出一枚硬幣，并規(guī)定當(dāng)和為奇數(shù)時(shí)， A贏得B所出硬幣；當(dāng)和為偶數(shù)時(shí)，B贏得A所出硬幣。據(jù)此寫出對策