運(yùn)籌學(xué)教材課件匯總完整版ppt全套課件最全教學(xué)教程整本書電子教案全書教案合集最新課件匯編

1、第一章 緒論運(yùn) 籌 學(xué)（Operations Research） 運(yùn)籌學(xué)的產(chǎn)生和發(fā)展 運(yùn)籌學(xué)作為一門數(shù)學(xué)學(xué)科，用純數(shù)學(xué)的方法來解決最優(yōu)方法的選擇安排，卻是在二十世紀(jì)四十年代才開始興起。 運(yùn)籌學(xué)主要研究經(jīng)濟(jì)活動和軍事活動中能用數(shù)量來表達(dá)的有關(guān)策劃、管理方面的問題。隨著客觀實(shí)際的發(fā)展，運(yùn)籌學(xué)的許多內(nèi)容不但研究經(jīng)濟(jì)和軍事活動，有些已經(jīng)深入到我們的日常生活當(dāng)中去了。 運(yùn)籌學(xué)的研究方法有：（1）從現(xiàn)實(shí)生活中抽出本質(zhì)的要素來構(gòu)造數(shù)學(xué)模型，因而可尋求一個跟決策者的目標(biāo)有關(guān)的解；（2）探索求解的結(jié)構(gòu)并導(dǎo)出系統(tǒng)的求解過程；（3）從可行方案中尋求系統(tǒng)的最優(yōu)解法。運(yùn)籌學(xué)的主要內(nèi)容 數(shù)學(xué)規(guī)劃線性規(guī)劃非線性規(guī)劃整數(shù)規(guī)劃

2、參數(shù)規(guī)劃動態(tài)規(guī)劃目標(biāo)規(guī)劃 排隊論庫存論圖論博弈論運(yùn)籌學(xué)的主要內(nèi)容 數(shù)學(xué)規(guī)劃線性規(guī)劃 約束條件和目標(biāo)函數(shù)都是線性函數(shù)的數(shù)學(xué)規(guī)劃； 主要解法是：單純形法； 主要應(yīng)用于企業(yè)規(guī)劃和工農(nóng)業(yè)的管理決策等方面。 非線性規(guī)劃 它是線性規(guī)劃的進(jìn)一步發(fā)展和繼續(xù)。許多實(shí)際問題如設(shè)計問題、經(jīng)濟(jì)平衡問題都屬于非線性規(guī)劃的范疇。 整數(shù)規(guī)劃 整數(shù)規(guī)劃是研究決策變量取正整數(shù)或部分取整數(shù)的一類規(guī)劃問題。 運(yùn)籌學(xué)的主要內(nèi)容 數(shù)學(xué)規(guī)劃參數(shù)規(guī)劃 參數(shù)規(guī)劃是系數(shù)或常數(shù)項中帶有參數(shù)的規(guī)劃問題，主要研究問題的解法：當(dāng)參數(shù)在什么范圍變化時問題有解以及參數(shù)的變化對最優(yōu)解的影響。動態(tài)規(guī)劃 它是與時間有關(guān)的規(guī)劃問題，它是研究多階段決策過程最優(yōu)化問

3、題。目標(biāo)規(guī)劃 目標(biāo)規(guī)劃就是在給定的決策環(huán)境中，使決策結(jié)果與預(yù)定目標(biāo)的偏差達(dá)到最小的數(shù)學(xué)模型。 與線性規(guī)劃有很大的區(qū)別，主要表現(xiàn)在：在線性規(guī)劃中，要求單個目標(biāo)的優(yōu)化，而目標(biāo)規(guī)劃則強(qiáng)調(diào)使多個目標(biāo)得到滿意的解答。另一方面，線性規(guī)劃中，為得到一個可行解，必須滿足所有的約束條件。 運(yùn)籌學(xué)的主要內(nèi)容 排隊論 它是運(yùn)籌學(xué)的又一個分支，它也叫做隨機(jī)服務(wù)系統(tǒng)理論。它的研究目的是要回答如何改進(jìn)服務(wù)機(jī)構(gòu)或組織被服務(wù)的對象，使得某種指標(biāo)達(dá)到最優(yōu)的問題。 因為排隊現(xiàn)象是一個隨機(jī)現(xiàn)象，因此在研究排隊現(xiàn)象的時候，主要采用研究隨機(jī)現(xiàn)象的概率論作為主要工具。 庫存論 它是一種研究物資最優(yōu)存儲及存儲控制的理論。 圖論 圖論是研究

4、由節(jié)點(diǎn)和邊所組成的圖形的數(shù)學(xué)理論和方法 博弈論 博弈論是使用嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)模型研究沖突對抗條件下最優(yōu)決策問題的理論。 運(yùn)籌學(xué)在管理中的應(yīng)用 工程管理與優(yōu)化設(shè)計 生產(chǎn)計劃與管理 市場營銷管理 庫存管理 會計與財務(wù)分析及管理 人力資源管理 設(shè)備維修、更新和可靠性、項目選擇和評價等 物流管理與交通運(yùn)輸問題 教學(xué)要求：第二章 線性規(guī)劃和單純形法 掌握線性規(guī)劃的基本建模法和單純形法基本原理會在不同條件下運(yùn)用單純形法求解線性規(guī)劃問題了解線性規(guī)劃在經(jīng)濟(jì)和管理中的基本應(yīng)用方法目 錄線性規(guī)劃實(shí)例與模型線性規(guī)劃的圖解法與基本性質(zhì)單純形法原理線性規(guī)劃的初始解解法目 錄線性規(guī)劃實(shí)例與模型線性規(guī)劃的圖解法與基本性質(zhì)單純形法

5、原理線性規(guī)劃的初始解解法實(shí)用舉例 某公司通過市場調(diào)研，決定生產(chǎn)高中檔新型拉桿箱。某分銷商決定買進(jìn)該公司3個月內(nèi)的全部產(chǎn)品。拉桿箱生產(chǎn)需經(jīng)過原材料剪裁、縫合、定型、檢驗和包裝4過程。 通過分析生產(chǎn)過程，得出：生產(chǎn)中檔拉桿箱需要用7/10小時剪裁、5/10小時縫合、1小時定型、1/10小時檢驗包裝；生產(chǎn)高檔拉桿箱則需用1小時剪裁、5/6小時縫合、2/3小時定型、1/4小時檢驗包裝。由于公司生產(chǎn)能力有限，3月內(nèi)各部的最大生產(chǎn)時間為剪裁部630小時、縫合部600小時、定型部708小時、檢驗包裝部135小時。 通過市場調(diào)研部和會計部的調(diào)查核算得出結(jié)論：生產(chǎn)中檔拉桿箱的利潤是10元，高檔拉桿箱的利潤是9元

6、。公司應(yīng)各生產(chǎn)多少中檔和高檔拉桿箱才能使公司利潤最大？實(shí)用舉例 某公司通過市場調(diào)研，決定生產(chǎn)高中檔新型拉桿箱。某分銷商決定買進(jìn)該公司3個月內(nèi)的全部產(chǎn)品。拉桿箱生產(chǎn)需經(jīng)過原材料剪裁、縫合、定型、檢驗和包裝4過程。 通過分析生產(chǎn)過程，得出：生產(chǎn)中檔拉桿箱需要用7/10小時剪裁、5/10小時縫合、1小時定型、1/10小時檢驗包裝；生產(chǎn)高檔拉桿箱則需用1小時剪裁、5/6小時縫合、2/3小時定型、1/4小時檢驗包裝。由于公司生產(chǎn)能力有限，3月內(nèi)各部的最大生產(chǎn)時間為剪裁部630小時、縫合部600小時、定型部708小時、檢驗包裝部135小時。 通過市場調(diào)研部和會計部的調(diào)查核算得出結(jié)論：生產(chǎn)中檔拉桿箱的利潤是

7、10元，高檔拉桿箱的利潤是9元。公司應(yīng)各生產(chǎn)多少中檔和高檔拉桿箱才能使公司利潤最大？可以通過線性規(guī)劃求解！線性規(guī)劃模型的建立 建立相應(yīng)的線性規(guī)劃模型 ：其中的 稱為決策變量。目標(biāo)函數(shù)約束條件一般線性規(guī)劃模型Max z = c1x1 + c2x2 + + cnxns.t. a11x1+ a12x2 + + a1nxn = b1 ( 0) a21x1+ a22x2 + + a2nxn = b2 ( 0) : am1x1+ am2x2 + + amnxn= bm( 0) x1,x2 , ,xn 0s.t. 為約束限制（Subject to）的縮寫(LP)x1.xnb1.bma11 a1nam1 am

8、nx =b =A = c =其中c=(c1,c2,cn)，稱為價值系數(shù)向量；稱為資源限制向量 X=(x1,x2,xn)T 稱為決策變量向量稱為技術(shù)系數(shù)矩陣(也稱消耗系數(shù)矩陣)一般線性規(guī)劃模型線性規(guī)劃模型的標(biāo)準(zhǔn)形式Max Z = c1x1 + c2x2 + + cnxnSubject to (s.t.)a11x1 + a12x2 + + a1nxn = b1a21x1 + a22x2 + + a2nxn = b2 am1x1 + am2x2 + + amnxn= bmx1 0, x2 0, , xn 0為了討論方便，把最大化、等式約束型的線性規(guī)劃稱為線性規(guī)劃的標(biāo)準(zhǔn)型，即標(biāo)準(zhǔn)化原問題標(biāo)準(zhǔn)化方法目標(biāo)

9、函數(shù)Max f(x)Max f(x)Min f(x)Max f(x)約束條件引入松弛變量和人工變量引入松弛變量, 不變變量 不變對某個對某個是任意的 線性規(guī)劃模型的標(biāo)準(zhǔn)化例:將如下線性規(guī)劃模型標(biāo)準(zhǔn)化：min z= x1 + 5 x2 - 8 x3 - x4s.t. 2 x1 - 3 x2 + x3 + x4 20 x1+ 2 x2 + 3 x3 - x4 30 2x2 + 2 x3 +3 x4- 50 x1 , x3 , x4 0，x2取值無約束。 max z1=-x1-5 x2+8 x3 +x4s.t. 2 x1 - 3 x2 + x3 + x4 20 x1+ 2 x2 + 3 x3 - x

10、4 30 2x2 + 2 x3 +3 x4- 50 x1 , x3 , x4 0，x2取值無約束。 目標(biāo)優(yōu)化標(biāo)準(zhǔn)化線性規(guī)劃模型的標(biāo)準(zhǔn)化Max z2 =-x1-5y2+5y3+8x3+x4 s.t. 2 x1 - 3 y2+3y3 + x3 + x4 20 -x1- 2 y2 +2y3 - 3 x3 + x4 -30 -2y2 +2y3 - 2 x3 -3 x4 50 x1 , x3 , x4 ,y2,y3 0 決策變量的標(biāo)準(zhǔn)化: y2 - y3 = x2max z1=-x1-5 x2+8 x3 +x4s.t. 2 x1 - 3 x2 + x3 + x4 20 x1+ 2 x2 + 3 x3 -

11、 x4 30 2x2 + 2 x3 +3 x4- 50 x1 , x3 , x4 0，x2取值無約束 線性規(guī)劃模型的標(biāo)準(zhǔn)化Max z2 =-x1-5y2+5y3+8x3+x4 s.t. 2 x1 - 3 y2+3y3 + x3 + x4 +x5 =20 -x1- 2 y2 +2y3 - 3 x3 + x4 +x6 = -30 -2y2 +2y3 - 2 x3 -3 x4 +x7 = 50 x1 , x3 , x4 , x5, x6, x7, y2, y3 0約束關(guān)系標(biāo)準(zhǔn)化Max z2 =-x1-5y2+5y3+8x3+x4 s.t. 2 x1 - 3 y2+3y3 + x3 + x4 20 -

12、x1- 2 y2 +2y3 - 3 x3 + x4 -30 -2y2 +2y3 - 2 x3 -3 x4 50 x1 , x3 , x4 ,y2,y3 0 可行解:滿足所有約束條件的解x=（x1，x2，.，xn），稱為線性規(guī)劃問題的可行解。所有可行解的集合稱為可行域?；涸O(shè)A是約束方程組的mn階系數(shù)矩陣，秩為m， 是A中階非奇異子矩陣（即 ），則稱是線性規(guī)劃問題的一個基矩陣，簡稱基。B中的列向量稱為基向量，與基向量對應(yīng)的變量x稱為基變量，其它變量稱為非基變量。 基本解：令非基變量=0，則由Ax=b可求出一個解，這個解x稱為基本解?；究尚薪猓簼M足非負(fù)條件的基本解稱為基本可行解。最優(yōu)解：使目標(biāo)函

13、數(shù)達(dá)到最優(yōu)值的可行解稱為最優(yōu)解。 線性規(guī)劃的解 可行解、基本解、基本可行解的關(guān)系可行解基本解基本可行解目 錄線性規(guī)劃實(shí)例與模型線性規(guī)劃的圖解法與基本性質(zhì)單純形法原理線性規(guī)劃的初始解解法線性規(guī)劃的圖解法 當(dāng)只有兩個決策變量時，可用圖解法求解！例：用圖解法求解以下線形規(guī)劃問題。 max z=4x1+3x2 s.t. x16 2x28 2x1+3x218 x10，x20 x1 x2 L3：2x1+3x2=18可行域L1：x1=6L2：x2=4最優(yōu)解B4x1+3x2解的特殊情況多個最優(yōu)解解的特殊情況無可行解解的特殊情況無界解線性規(guī)劃的基本性質(zhì) X可行域內(nèi)部的點(diǎn) 可行解? 是 最優(yōu)解? 不 若線性規(guī)劃有

14、最優(yōu)解，則最優(yōu)解必在可行域的頂點(diǎn)上達(dá)到。凸集的概念 凸集是線性規(guī)劃中一個很重要的概念，凸集的一般定義為：如果在集合C中任意取兩個點(diǎn)x1，x2，其連線上的所有點(diǎn)也都在集合C中，則稱集合C為凸集合。用數(shù)學(xué)解析式表達(dá)為：對任意 ，均有 ，則稱C是凸集合。非凸集非凸集凸集線性規(guī)劃的基本性質(zhì) 定理2.1：線性規(guī)劃的可行域： 是凸集（凸多面體）。 引理2.1：線性規(guī)劃的可行解 為基本可行解的充分必要條件是x的正分量所對應(yīng)的系數(shù)列向量是線性無關(guān)的，即每個正分量都是一個基變量。 定理2.2：線性規(guī)劃問題的基本可行解x對應(yīng)于可行域的頂點(diǎn) 定理2.3：若線性規(guī)劃有最優(yōu)解，則最優(yōu)解必在可行域的頂點(diǎn)上達(dá)到。目 錄線性

15、規(guī)劃實(shí)例與模型線性規(guī)劃的圖解法與基本性質(zhì)單純形法原理一、初始基本可行解的確定考慮如下形式的線性規(guī)劃問題max z=c1x1+c2x2+.+cnxn s.t. a11x1+a12x2+a1nxnb1 a21x1+a22x2+a2nxnb2 (2.17） . am1x1+am2x2+ +amnxnbm x1，x2，.，xn0 （2.18）對每個不等式約束引入一個非負(fù)松弛變量，得標(biāo)準(zhǔn)形式：max z=c1x1+c2x2+.+cn xns.t. a11x1+a1nxn+xn+1 =b1 a21x1+a2nxn +xn+2 =b2 （2.19） . am1x1+amn xn +xn+m =bm x1，x

16、2，.，xn，xn+1，xn+m0是線性規(guī)劃(2.19)的一個可行基。令 得由此得到一個初始基本可行解為二、最優(yōu)性檢驗 定理2.4： 在最大化問題中，對于某個基本可行解，如果所有 的 ，則這個基本可行解是最優(yōu)解。 在最小化問題中，對于某個基本可行解，如果所有 的 ，則這個基本可行解是最優(yōu)解。單純形法求解步驟將所給問題化為標(biāo)準(zhǔn)形找出一個初始可行基,建立初始單純形表檢查所有檢驗數(shù)(若全為非負(fù),則已得到最優(yōu)解,計算停止.否則繼續(xù)下一步)考察是否無解(若是,計算停止,否則繼續(xù)下一步)確定入基變量,出基變量對初始單純形表進(jìn)行單純形變換單純形方法的一般步驟確定一個初始可行角點(diǎn)根據(jù)某種法則進(jìn)行角點(diǎn)的最優(yōu)性判

17、斷不是最優(yōu)角點(diǎn)是最優(yōu)角點(diǎn)考察與當(dāng)前角點(diǎn)相鄰的 “更好”的一個角點(diǎn)，并置為當(dāng)前角點(diǎn)。根據(jù)某種法則進(jìn)行LP的無界或不可行判斷無界或不可行還不能做出判斷求解結(jié)束單純形法舉例解：引進(jìn)松馳變量x3, x4，化為標(biāo)準(zhǔn)形得： 4 3 0 0 CBXBb x1 x2 x3 x4 b/y00 x3x42426 2 3 1 0 24/2 3 2 0 1 26/3 0 4 3 0 04=4（03+02）；3=3（02+03） 4 3 0 0CBXBb x1 x2 x3 x4 b/y04x3x120/326/3 0 5/ 3 1 -2/3 1 2/3 0 1/3 -104/3 0 1/3 0 -4/3 4 3 0 0

18、CBXBb x1 x2 x3 x434x2x146 0 1 3/5 -2/5 1 0 -2/5 3/5 36 0 0 -1/5 -6/5表中最后一行的所有檢驗數(shù)均為非正數(shù)，表明目標(biāo)函數(shù)已達(dá)到最大值，上述表為最優(yōu)表。從表中可得到最優(yōu)解為X=（x1,x2,x3,x4）=（6，4，0，0），最優(yōu)值為Z=36 4 3 0 0CBXBb x1 x2 x3 x4 b/y04x3x120/326/3 0 5/ 3 1 -2/3 4 1 2/3 0 1/3 13 -104/3 0 1/3 0 -4/3大M法基本思想：在約束條件中增加人工變量，同時修改目標(biāo)函數(shù)，對目標(biāo)函數(shù)加上具有很大正系數(shù)M的懲罰項，為使人工變

19、量不影響目標(biāo)函數(shù)取值，在迭代過程中，應(yīng)把人工變量從基變量中退出，使其成為非基變量。 其中，M是很大的正數(shù)，同時增加兩個人工變量。 不容易找到初始可行解找初始可行解11-300MMbi/yibx1X2x3x4x5x6x70X4111-21100011MX6321-40-1103/2MX71(1)0-2000111-3M1-M-3+6M0M00 要求最后得到的基變量中不含人工變量X1進(jìn)基，x7出基11-300MMbi/yibx1x2x3x4x5x6x7-3X340011/3-2/32/3-5/31X210100-11-211X191002/3-4/34/3-7/30001/31/3M-1/3M-2

20、/3 可以從表中移去，然后繼續(xù)求解 經(jīng)過幾次變換，得到基變量為x1，x2，x3兩階段法原理兩階段法的第一階段是用單純形法 消去人工變量，即把人工變量都變?yōu)榉腔兞浚蟪鲈瓎栴}的一個基本可行解。如果第一階段求解結(jié)果表明問題有可行解時，進(jìn)行第二階段，就是從得到的基本可行解出發(fā)，用單純形方法求原問題的最優(yōu)解。兩階段法舉例例：第一階段：第二階段：用單純形法求得第一階段的解為： 用單純形法求解規(guī)劃問題得最優(yōu)解 目標(biāo)函數(shù)的最優(yōu)解是 Excel Solver（規(guī)劃求解） Excel采用了電子表格的形式，幫助管理者提高數(shù)據(jù)管理的能力，因而得以廣泛應(yīng)用。Solver插件專門用于求解帶約束的最優(yōu)化問題。 Solv

21、er“規(guī)劃求解”，可在Excel的工作表中根據(jù)對話框提示調(diào)用該項功能。加載 “規(guī)劃求解”如果在您的Excel中，沒有在“工具”菜單中發(fā)現(xiàn)“規(guī)劃求解”，請在下圖所示的界面中點(diǎn)擊“加載宏”。加載 “規(guī)劃求解”點(diǎn)擊“加載宏”后，顯示界面如下：如果列表中沒有 “規(guī)劃求解”，表明您還沒有安裝該插件。這時，您需要插入Microsoft Office安裝盤，選擇“添加安裝”后選擇該插件的安裝。第1步 導(dǎo)入已知數(shù)據(jù)可采用 復(fù)制粘貼 或 直接輸入 的方式導(dǎo)入數(shù)據(jù)。第2步 確定 可變單元格 可變單元格存放決策變量的取值，可變單元格數(shù)目等于決策變量個數(shù)圖中，規(guī)定B16、C16為可變單元格第3步 確定 目標(biāo)單元格 在

22、目標(biāo)單元格中，需要填入計算目標(biāo)函數(shù)值的公式。第4步 確定 約束單元格 在約束單元格中，需要填入計算約束函數(shù)值的公式。第5步 調(diào)用 規(guī)劃求解 模塊在上圖顯示的界面中，需要輸入目標(biāo)單元格、可變單元格，添加約束條件，另外還可能需要進(jìn)行選項設(shè)置。第6步 填寫目標(biāo)單元格和可變單元格第7步 添加約束第8步 “選項”設(shè)置選擇：采用線性模型，假定非負(fù)。 如果求解過程在找到結(jié)果之前即達(dá)到最長運(yùn)算時間或最大迭代 次數(shù)，則會彈出 “顯示中間結(jié)果” 對話框。第9步 保存求解結(jié)果顯示求解結(jié)果使用Excel求解例2.10掌握線性規(guī)劃對偶理論及其基本經(jīng)濟(jì)學(xué)意義；第三章 線性規(guī)劃對偶理論及其應(yīng)用教學(xué)要求：了解運(yùn)用對偶理論對線

23、性規(guī)劃最優(yōu)解進(jìn)行分析的基本方法；會運(yùn)用對偶理論對一些基本的管理問題進(jìn)行經(jīng)濟(jì)學(xué)分析。目 錄線性規(guī)劃的對偶問題對偶規(guī)劃的基本性質(zhì)對偶單純形法影子價格和靈敏度分析目 錄線性規(guī)劃的對偶問題對偶規(guī)劃的基本性質(zhì)對偶單純形法影子價格和靈敏度分析對偶問題的提出 某工廠甲生產(chǎn)A、B、C三種產(chǎn)品。這三種產(chǎn)品的單位利潤分別是60、30、20。生產(chǎn)這三種單位產(chǎn)品所占用M、N、P三種機(jī)器的時間已知，機(jī)器M、N、P每天可供使用的時間分別是48、20、8小時。這三種產(chǎn)品每天生產(chǎn)多少才能使工廠獲得最大效益?，F(xiàn)有另一工廠乙，因生產(chǎn)需要。擬向甲廠租用所有的機(jī)器，則乙廠希望租金越少越好，當(dāng)然必須保證甲廠的利潤。顯然，如果甲廠的利潤

24、得不到保證，甲廠是不可能出租的。 原問題對偶問題當(dāng) 時，工廠的決策者認(rèn)為這兩種考慮有相同結(jié)果，都是最優(yōu)方案！ 對偶問題的一般形式 原線性規(guī)劃問題（LP） 原問題（LP）的對偶問題（LD）對偶問題的變量表示單位資源的價值。 在實(shí)際問題中，對偶問題的目標(biāo)函數(shù)表示可利用資源的數(shù)量。最小化問題的對偶問題的一般步驟對偶問題是最大化；當(dāng)原問題有n個決策變量，則對偶問題有n個約束條件。對偶問題的第一約束條件對應(yīng)的是原問題中的x1變量，對偶問題的第二個約束條件對應(yīng)的是原問題中的x2變量，依此類推。當(dāng)原問題有m個約束條件，則對偶問題有m個決策變量。對偶問題的u1變量對應(yīng)的是原問題中的第一約束條件，對偶問題的u2

25、變量對應(yīng)的是原問題中的第二約束條件，依此類推。原問題的約束條件的右側(cè)值成為對偶問題的目標(biāo)函數(shù)系數(shù)。原問題的目標(biāo)函數(shù)系數(shù)成為對偶問題中的約束條件的右側(cè)值。目標(biāo)函數(shù)中原問題第i個變量的系數(shù)成為對偶問題中第i個約束條件的常數(shù)項。 原問題與對偶問題線性規(guī)劃問題的對偶問題舉例寫出下列線性規(guī)劃問題的對偶問題：先化為最小化問題：最小化問題的對偶問題：也可把對偶問題化為最小化問題： 變成目標(biāo)函數(shù)的系數(shù)系數(shù)變成約束條件右側(cè)值變成第一個約束條件的系數(shù)目 錄線性規(guī)劃的對偶問題對偶規(guī)劃的基本性質(zhì)對偶單純形法影子價格和靈敏度分析對偶規(guī)劃的基本性質(zhì) 一、對稱性 對偶問題的對偶問題就是原問題。即對偶問題與原問題互為對偶問題

26、。二、弱對偶性如果x，u分別是原問題和對偶問題的可行解，則 。 三、最優(yōu)性 如果x，u分別是原問題和對偶問題的可行解,且 則 x，u分別是原問題和對偶問題的最優(yōu)解。四、強(qiáng)對偶性 若原問題有最優(yōu)解x，則對偶問題也有最優(yōu)解y，且目標(biāo)函數(shù)值相等，即 。 五、松馳性 設(shè) ， 分別是原問題和對偶問題的可行解，則 ， 是最優(yōu)解的充要條件是對所有的i和j，下列關(guān)系成立： 1如果 ，有 ； 2如果 ，有 ； 3如果 ，有 ； 4如果 ，有 。 其中pj是A的第j列，Ai是A的第i行。 對偶規(guī)劃的基本性質(zhì) 目 錄線性規(guī)劃的對偶問題對偶規(guī)劃的基本性質(zhì)對偶單純形法影子價格和靈敏度分析對偶單純形法的計算步驟 1給定一

27、個初始對偶可行的基本解，設(shè)相應(yīng)的基為B。2若 ，則停止計算，現(xiàn)行對偶可行的基本解為最優(yōu)解。否則令 ，則該行所對應(yīng)的變量 為換出基的變量； 3若對所有j， ，則停止計算，原問題無可行解。否則，令則 為換入基的變量；4以 為主元進(jìn)行主元消去，返回2。對偶單純形法舉例標(biāo)準(zhǔn)化乘以(-1)3100Bx1x2x3x40 x3-1-1-1100 x4-2-2-3013100初始對偶單純形表：出基進(jìn)基主元 直到B0，停止。對偶單純形法具有如下優(yōu)點(diǎn)：1 初始解可以是原問題的非可行解；2 對變量個數(shù)多于約束條件的線性規(guī)劃宜用對偶單純形法計算，因此當(dāng)變量數(shù)少于約束條件個數(shù)時，可先求其對偶規(guī)劃，然后用對偶單純形求解。

28、 用單純形法求解對偶問題（LD）（即 最大化問題）時，其最后一行的檢驗數(shù)行對應(yīng)原問題（LP）的一個基本解。并且在最終的單純形表中，對偶松弛變量對應(yīng)的檢驗數(shù)的負(fù)數(shù)就是原問題（LP）的最優(yōu)解。 例3.4：用對偶單純形法求解線性規(guī)劃解：在第2個約束方程的兩邊同乘以-1，然后引入變量x4,x5得：用對偶單純形法求解得最優(yōu)解 ： 最優(yōu)目標(biāo)函數(shù)值 ：單純形算法和對偶單純形算法之差別 目 錄線性規(guī)劃的對偶問題對偶規(guī)劃的基本性質(zhì)對偶單純形法影子價格和靈敏度分析影子價格和對偶價格 約束條件右側(cè)（即資源）改變1個單位時，目標(biāo)函數(shù)（即利潤）的變化量，它度量了約束條件對應(yīng)的那種資源的價值，經(jīng)濟(jì)學(xué)上稱為影子價格。對偶價

29、格：約束條件的右側(cè)值每增加一個單位導(dǎo)致最優(yōu)解的增加量。對偶價格只適用于約束條件右側(cè)值變化比較小的情況。當(dāng)資源越來越多時，約束條件右側(cè)的值也越來越大，其它的約束條件就有可能成為緊約束，限制目標(biāo)函數(shù)值的變大。決策變量、影子價格之間的對應(yīng)關(guān)系 例3.7：求下列原問題的最優(yōu)解及影子價格和對偶問題的最優(yōu)解及影子價格。 min z=4x1+7x2 +8x3 s.t. x1+ x2 3 x2 +2x3 1 （LP） x1+ x2 + x3 8 x10,x20,x30其對偶問題為： max w=3u1+u2 +8x3 s.t. U1 + u3 4 u1+u2 + u3 7 （LD） 2u2 + u3 8 u1

30、0,u20 ,u30求解（LP）得最優(yōu)解為x*=7.5, 0, 0.5；最優(yōu)值為34。 求解（LD）得最優(yōu)解為u*=0，2，4；最優(yōu)值為34。所以（LP）的影子價格是：0，2，4 ；（LD）的影子價格為7.5, 0, 0.5； 例3.8：A工廠計劃生產(chǎn)甲、乙兩種產(chǎn)品。每千克產(chǎn)品的銷售價格和能源消耗量、以及能源資源見表3-26，怎樣安排生產(chǎn)計劃才能使A工廠獲益最大？ 解：x1：產(chǎn)品甲的計劃生產(chǎn)量；x2：產(chǎn)品乙的計劃生產(chǎn)量，則有如下線性規(guī)劃問題： max z=7x1 + 12x2 (總銷售收入) s.t. 9x1 + 4x2 360 (煤資源限制) 4x1 + 5x2 200 (電資源限制) 3x

31、1 + 10 x2 300 (油資源限制) x1 0，x2 0 (非負(fù)條件)用單純形法求解得：x1=20，x2=24。其對偶問題是：min w = 360y1+200y2 +300y3 s.t. 9y1 + 4y2 + 3y3 7 4y1 + 5y2 + 10y3 12 y1 0，y2 0，y3 0用單純形法求解得：y1=0，y2 =1.36，y3=0.52。所以，煤、電、石油的影子價格分別為：0、1.36、0.52。直觀上，如果在一個生產(chǎn)計劃下，每一種資源都有所剩余，必然還可進(jìn)一步通過剩余資源的組合增加生產(chǎn)收入(例如，將x2增加到24)。這表明該生產(chǎn)計劃必定不是最優(yōu)的生產(chǎn)計劃。換言之，如果一

32、個生產(chǎn)計劃是最優(yōu)的，則該計劃必然會耗盡某些資源。在一個最優(yōu)生產(chǎn)計劃下，被耗盡的資源對于A工廠來說就是所謂的稀缺資源。如果追加這些稀缺資源的量，則可進(jìn)一步提高產(chǎn)量以增加生產(chǎn)收入。于是，提出了這樣一個實(shí)際問題：如果在一個最優(yōu)生產(chǎn)計劃下，出現(xiàn)多種稀缺資源，那么，哪些稀缺資源最值得追加？或者說，如果A工廠始終按照最優(yōu)化的計劃組織生產(chǎn)，哪些資源對其最為緊缺？另外，根據(jù)稀缺資源對提高整個生產(chǎn)收入的貢獻(xiàn)，A工廠甚至可考慮以高于市場價格的采購策略追加這些資源。這類實(shí)際問題，可通過影子價格得以解答。 影子價格是對現(xiàn)有資源實(shí)現(xiàn)最大效益時的一種估價 企業(yè)可以根據(jù)現(xiàn)有資源的影子價格，對資源的使用有兩種考慮： 第一，是

33、否將設(shè)備用于外加工或出租，若租費(fèi)高于某設(shè)備的影子價格，可考慮出租該設(shè)備，否則不宜出租。 第二，是否將投資用于購買設(shè)備，以擴(kuò)大生產(chǎn)能力，若市價低于某設(shè)備的影子價格，可考慮買進(jìn)該設(shè)備，否則不宜買進(jìn)。影子價格的經(jīng)濟(jì)含義 在報告列表框中選擇“敏感性報告”影子價格Max z = 7x1 + 12x2 s.t. 9x1 + 4x2 360 4x1 + 5x2 200 3x1 + 10 x2 300 x1 0，x2 0Min g = 360y1 + 200y2 + 300y3 s.t. 9y1 + 4y2 + 3y3 7 4y1 + 5y2 + 10y3 12 y1 0，y2 0，y3 0根據(jù)影子價格確定某

34、種資源的追加價值。 例如：煤、電、石油的影子價格分別為0、1.36、0.52，則可確定應(yīng)首先增加電資源，因為相比之下它能導(dǎo)致更多的生產(chǎn)收入。 又如：每增加1度電能使生產(chǎn)收入增加1.36 ，如果1度電的價格高于1.36 就不劃算了；反之，如果1度電的價格低于1.36 ，則購買電資源是有利可圖的。根據(jù)影子價格制定新產(chǎn)品的價格。 例如，A工廠要生產(chǎn)一種新產(chǎn)品，如果每單位新產(chǎn)品需耗用煤、電、石油分別為5、10、3單位，則新產(chǎn)品的價格必須大于 50+101.36+30.52 = 15.19才可能增加生產(chǎn)收入。如果售價低于15.19，生產(chǎn)該新產(chǎn)品是不劃算的。 根據(jù)影子價格分析生產(chǎn)工藝的改變對資源節(jié)約所帶來

35、的收益。 例如，如果A工廠經(jīng)過工藝改造后使石油節(jié)約了2%，則帶來的經(jīng)濟(jì)收益為 3002%0.52=3.12在線性規(guī)劃中，我們假定模型的系數(shù)都是已知常數(shù)。而在實(shí)際中，各種條件都是動態(tài)變化的，因此這種假定很難成立。靈敏度分析將回答：最優(yōu)解對線性規(guī)劃模型中各種系數(shù)變化的敏感性靈敏度分析靈敏度分析目標(biāo)函數(shù)系數(shù)的變化 Max Z = 40 x + 50y利潤s.t.1x + 2y 40時間約束4x + 3y 120人力約束x, y 0非負(fù)約束目標(biāo)函數(shù)系數(shù)在什么范圍變化時，目標(biāo)函數(shù)的最優(yōu)解不會發(fā)生變化？ 圖像表示x240403020 x1 最優(yōu)解變化圖像表示x240403020 x1 最優(yōu)解變化 約束條件

36、右邊值的變化 右側(cè)值在什么范圍變化時，目標(biāo)函數(shù)的最優(yōu)解不會發(fā)生變化？Max Z = 40 x + 50y利潤s.t.1x + 2y 40時間約束4x + 3y 120人力約束x, y 0非負(fù)約束x240403020 x1最優(yōu)解變化最優(yōu)解變化 圖像描述 用圖解法對例2.1進(jìn)行靈敏度分析 利用計算機(jī)管理軟件進(jìn)行靈敏度分析 當(dāng)Excel已經(jīng)找出了線形規(guī)劃問題的最優(yōu)解時，屏幕上就會出現(xiàn)一個“規(guī)劃求解結(jié)果”的對話框（圖3-3）。如果這個解就是你所要的，在“報告”一欄里選擇“敏感性報告”，單擊“確定”，有關(guān)靈敏度分析的報告就會保存在同一個Excel工作簿的另外一張工作表上。對于球袋公司，我們得到最優(yōu)解所在

37、的工作表如圖2-7和敏感性分析所在的工作表如圖3-4。圖 3-3圖 2-7利用計算機(jī)管理軟件進(jìn)行靈敏度分析圖 3-4此報告中將包含縮減成本、影子價格、目標(biāo)系數(shù)(允許有小量增幅)以及右側(cè)約束區(qū)域。 注：必須選擇 “假定線性模型” 才能提供完整的敏感性報告接受求解結(jié)果，并將其輸入可變單元格中。用Excel對例3.8的敏感性報告在不改變最優(yōu)解結(jié)構(gòu)的前提下，單個目標(biāo)系數(shù)的可變上下限。如果其中有0出現(xiàn)，表明存在多個最優(yōu)解。僅當(dāng)資源增幅在允許的范圍內(nèi)，才能利用影子價格進(jìn)行分析。即產(chǎn)品的邊際收入與按影子價格折算的邊際成本之差。當(dāng)遞減成本小于零時，表示不應(yīng)該安排該產(chǎn)品的生產(chǎn)。列出目標(biāo)單元格和可變單元格以及它們

38、的初始值、最終結(jié)果、有關(guān)約束條件的信息。運(yùn)算結(jié)果報告列出目標(biāo)單元格和可變單元及其數(shù)值、在滿足約束條件和保持其它可變單元格數(shù)值不變情況下的上下限和目標(biāo)值。極限值報告教學(xué)要求：第五章目標(biāo)規(guī)劃了解目標(biāo)規(guī)劃在多目標(biāo)決策中的作用 掌握目標(biāo)規(guī)劃的建模方法和線性目標(biāo)規(guī)劃基本求解方法 了解目標(biāo)規(guī)劃在經(jīng)濟(jì)和管理中的基本應(yīng)用方法 目標(biāo)規(guī)劃60年代初，查恩斯（Charnes）和庫伯（Cooper）提出了一種用于求解多于一個目標(biāo)的線性決策模型的方法，并提出了目標(biāo)規(guī)劃的概念。與線性規(guī)劃的區(qū)別在線性規(guī)劃中，要求單個目標(biāo)的優(yōu)化，而目標(biāo)規(guī)劃則強(qiáng)調(diào)使多個目標(biāo)得到滿意的解答 線性規(guī)劃中，為得到一個可行解，必須滿足所有的約束條件。

39、在目標(biāo)規(guī)劃中，并不認(rèn)為所有約束都是絕對的，因此對于非絕對的約束，目標(biāo)規(guī)劃并不要求絕對滿足，而是設(shè)法使各目標(biāo)離原先設(shè)定的意向指標(biāo)值的偏差盡可能的小。 目 錄目標(biāo)規(guī)劃實(shí)例與模型目標(biāo)規(guī)劃求解方法目標(biāo)規(guī)劃的靈敏度分析用Excel求解目標(biāo)規(guī)劃的解目 錄目標(biāo)規(guī)劃實(shí)例與模型目標(biāo)規(guī)劃求解方法目標(biāo)規(guī)劃的靈敏度分析用Excel求解目標(biāo)規(guī)劃的解實(shí) 例 設(shè)某公司生產(chǎn)兩種型號的電扇，一種為普通型，裝配一個需要1小時，另一種為豪華型，裝配一個需要2小時。正常的裝配時間每周限定為40小時。市場調(diào)查表明每周銷售普通型不超過30件，豪華型不超過15件。普通型每件的凈利潤為8元，豪華型為每件12元。公司經(jīng)理提出如下優(yōu)先次序的要求

40、： 1總利潤最大2裝配線盡可能少加班3銷售盡可能多的電扇（這同盡可能獲取最大利潤一致）。 4根據(jù)市場調(diào)研要求每周生產(chǎn)的產(chǎn)品數(shù)不能多于銷售的數(shù)量，即普通型電扇為30件，豪華型電扇為15件。該問題的決策目標(biāo)是：（1）總利潤最大；（2）盡可能少加工；（3）盡可能多銷售電扇；（4）生產(chǎn)數(shù)量不能超過預(yù)銷售數(shù)量。（5）絕對目標(biāo)約束。所謂絕對目標(biāo)約束就是必須要嚴(yán)格滿足的約束。絕對目標(biāo)約束是最高優(yōu)先級，在考慮較低優(yōu)先級的目標(biāo)之前它們必須首先得到滿足。實(shí) 例模型建立第一優(yōu)先級決策目標(biāo) 正偏差：決策值超過目標(biāo)值的偏差部分 負(fù)偏差：決策值小于目標(biāo)值的偏差部分 指標(biāo)偏離函數(shù) 約束條件決策變量建立目標(biāo)規(guī)劃模型的步驟 第

41、一步：定義決策變量和有關(guān)的常量 建立模型的第一步就是定義決策變量和決策目標(biāo)約束等式右邊的常數(shù)。等式右邊的常數(shù)是可利用的資源或是決策者特定的目標(biāo)值。第二步：建立決策目標(biāo)約束 通過分析決策變量之間的關(guān)系以及決策變量與目標(biāo)值之間的關(guān)系，建立一組目標(biāo)約束。并從所有的決策目標(biāo)中，找出絕對決策目標(biāo)（即，如果不滿足將導(dǎo)致最終結(jié)果無法實(shí)現(xiàn)的目標(biāo)），將這些目標(biāo)作為第一優(yōu)先級。而后再確定其余目標(biāo)的優(yōu)先級。第三步：建立指標(biāo)偏差函數(shù)目標(biāo)規(guī)劃的一般模型為：其中xj（ ）為決策變量；Pk（ ）為第k級優(yōu)先因子； 分別為第l個目標(biāo)約束的正負(fù)偏差變量的權(quán)系數(shù)，在同一等級的目標(biāo)中，根據(jù)對各因子考慮的先后次序的不同，賦予不同權(quán)系

42、數(shù)。 （ ）為目標(biāo)的預(yù)期目標(biāo)值；bj 為系統(tǒng)的資源量。 這里 僅表示目標(biāo)的優(yōu)先等級， 后的函數(shù)表示該等級內(nèi)的目標(biāo)函數(shù)。在這里，我們規(guī)定 優(yōu)先于 ，等等。記為：在對目標(biāo)規(guī)劃問題求解時，只有在盡量滿足 等級內(nèi)的目標(biāo)函數(shù)前提下，才能考慮實(shí)現(xiàn) 等級內(nèi)的目標(biāo)。在這里 不是一個具體的數(shù)，而只表示各等級間的從屬關(guān)系。所以，我們稱 為優(yōu)先權(quán)因子。 稱為目標(biāo)規(guī)劃的目標(biāo)函數(shù)。目 錄目標(biāo)規(guī)劃實(shí)例與模型目標(biāo)規(guī)劃求解方法目標(biāo)規(guī)劃的靈敏度分析用Excel求解目標(biāo)規(guī)劃的解 再滿足P4 ,使 , 極小化，由于 是 的1.5倍，先考慮先滿足P1 =0, =0圖解法再滿足P2使 =0再滿足P3使 極小化單純形方法問題 單純形方法

43、解決 ciP15P33P3P4P2ziVBx1x2d1 -d2-d3-d11-d1+d11+P1d1 -80111-15P3d2-70113P3d3 -4511d11 -1011-1P40-1P348553P20-1P18011-1 在選擇最優(yōu)列時，先從檢驗數(shù)欄中最優(yōu)等級 行開始尋找最大正檢驗數(shù)。如 行內(nèi)有最大正檢驗數(shù)，就確定它為最優(yōu)列，進(jìn)行迭代。直到 行內(nèi)檢驗數(shù)沒有正值為止，再轉(zhuǎn)入 行尋找最大檢驗數(shù)。如此繼續(xù)下去，直到所有檢驗數(shù)全部檢查完畢。檢驗數(shù)的計算：以 列為例，此時， ， 所以， 。故在檢驗數(shù)欄中的 行和 行與 列的交叉點(diǎn)處的數(shù)分別為1和5。 目 錄目標(biāo)規(guī)劃實(shí)例與模型目標(biāo)規(guī)劃求解方法目

44、標(biāo)規(guī)劃的靈敏度分析用Excel求解目標(biāo)規(guī)劃的解 目標(biāo)規(guī)劃的靈敏度分析 優(yōu)先權(quán)因子( )的變化 1對應(yīng)最優(yōu)解的非基變量的 的變化:改變它們的優(yōu)先等級，并不影響最優(yōu)解的值,進(jìn)改變他們的系數(shù)。2對應(yīng)基變量的組合或基變量與非基變量組合的 的變化 ：重新寫出初始單純形表，計算最有解。目標(biāo)值（ ）的變化 計算最終的單純形表中的B-1b，看所得結(jié)果；如果所有分量都大于零，則解不變；如果存在分量小于零，則用對偶單純形方法求新的最有解。目 錄目標(biāo)規(guī)劃實(shí)例與模型目標(biāo)規(guī)劃求解方法目標(biāo)規(guī)劃的靈敏度分析用Excel求解目標(biāo)規(guī)劃的解 用Excel求解目標(biāo)規(guī)劃問題例5.3 將目標(biāo)規(guī)劃化為如下形式 建立電子表格模型如下：通過

45、規(guī)劃求解，得到如下的結(jié)果121了解整數(shù)規(guī)劃在經(jīng)濟(jì)和管理中的基本應(yīng)用方法。 第六章 整數(shù)規(guī)劃 教學(xué)要求：掌握線性整數(shù)規(guī)劃的建模方法，特別是0-1變量的運(yùn)用；掌握分支定界求解方法的基本原理；了解割平面求解方法的基本原理；122目 錄整數(shù)規(guī)劃實(shí)例與模型01整數(shù)規(guī)劃的建模方法分支定界法割平面法指派問題應(yīng)用舉例和Excel求解123目 錄整數(shù)規(guī)劃實(shí)例與模型01整數(shù)規(guī)劃的建模方法分支定界法割平面法指派問題應(yīng)用舉例和Excel求解124應(yīng)用與實(shí)例 在現(xiàn)實(shí)生活中，經(jīng)常遇到一些需要變量取整數(shù)才有實(shí)際意義的問題，例如制定計劃、規(guī)劃時需要確定工人的人數(shù)，設(shè)備的臺數(shù)等。許多有名的最優(yōu)化問題，如旅行商問題、背包問題、下

46、料問題、工序安排問題等，也都可以歸結(jié)為整數(shù)規(guī)劃問題。125應(yīng)用與實(shí)例 具體實(shí)例 現(xiàn)有一位于城市B5的工廠，其年生產(chǎn)量是30000件，產(chǎn)品被運(yùn)往A1，A2，A3三個城市的銷售中心。經(jīng)預(yù)測該廠產(chǎn)品的需求量將會增長，工廠決定將在B1，B2，B3，B4四個城市中的一個或多個城市中新建工廠以增加生產(chǎn)力(如有圖）。綜合考慮在這四個城市中新建工廠的年固定成本和生產(chǎn)能力，以及每件產(chǎn)品從每個工廠送到每個銷售中心的運(yùn)費(fèi)。問如何選擇新的廠址，才能使該工廠每年的總成本最小。B1B2B3B4B5A3A2A1126 首先做如下假設(shè)： 如果在B1建新廠，y1=1；否則，y1=0。 如果在B2建新廠，y2=1；否則，y2=0

47、。 如果在B3建新廠，y3=1；否則，y3=0。 如果在B4建新廠，y4=1；否則，y4=0。 xij：表示從工廠i 到銷售中心j的運(yùn)輸量；i=1,5；j=1,2,3。 利用已知的數(shù)據(jù)，年運(yùn)輸成本為： TC1=5x11+2x12+3x13+4x21+3x22+4x23+9x31+7x32 +5x33+10 x41+4x42+2x43+8x51+4x52+3x53127TC2=175y1+300y2+375y3+500y4；總成本為：TC=TC1+TC2；生產(chǎn)能力的約束條件為：從新工廠B1運(yùn)到A1，A2，A3三個城市銷售中心的總量應(yīng)小于等于B1的生產(chǎn)能力，所以約束條件為： x11+x12+x13

48、10y1 B1的生產(chǎn)能力；同理可得：x21+x22+x2320y2 B2的生產(chǎn)能力；x31+x32+x3330y3 B3的生產(chǎn)能力；x41+x42+x4340y4 B4的生產(chǎn)能力；x51+x52+x5330 B5的生產(chǎn)能力；三個銷售中心的需求量為：x11+x21+x31+x41+x51=30 A1的需求量；x12+x22+x32+x42+x52=20 A2的需求量；x13+x23+x33+x43+x53=20 A3的需求量；建新工廠的年固定成本為：128所以選址模型為：min TC= TC1+TC2s.tx11+x12+x1310y1； x21+x22+x2320y2； x31+x32+x33

49、30y3； x41+x42+x4340y4； x51+x52+x5330； x11+x21+x31+x41+x51=30； x12+x22+x32+x42+x52=20； x13+x23+x33+x43+x53=20； xij0，對所有的i，j； y1，y2，y3，y4=0，1 129整數(shù)規(guī)劃的一般模型130目 錄整數(shù)規(guī)劃實(shí)例與模型01整數(shù)規(guī)劃的建模方法分支定界法割平面法指派問題應(yīng)用舉例和Excel求解131實(shí)例分析 某電冰箱廠正在考慮隨后4年內(nèi)有不同資金要求的投資方案。面對每年有限的資金，工廠領(lǐng)導(dǎo)需要選擇最好的方案，使資金預(yù)算方案的當(dāng)前估算凈值最大化。每種方案的現(xiàn)金估算凈值（現(xiàn)金估算凈值為第

50、一年開始時的凈現(xiàn)金流的值）、資金需求和4年內(nèi)擁有的資金見下表：132實(shí)例分析 x1表示擴(kuò)建工廠的變量，=1表示擴(kuò)建工廠，0表示不擴(kuò)建 同理，變量x2,x3,x4依次表示擴(kuò)建倉庫、更新機(jī)器、新產(chǎn)品研制。變 量第1年的可用資金為40千元，所以相應(yīng)的約束條件為：同理得到后三年的約束條件。約束條件當(dāng)前估算凈值最大，即max 目標(biāo)函數(shù)13301整數(shù)規(guī)劃的標(biāo)準(zhǔn)型和解法必須 必須大于等于0 解法 全枚舉法（不展開論述） 隱枚舉法（重點(diǎn)講述）標(biāo)準(zhǔn)型134隱枚舉法求解步驟（一）（1）令全部都是自由變量且取0值，檢驗解是否可行。若可行，已得最優(yōu)解；若不可行，進(jìn)行步驟（2）。（2）將某一變量轉(zhuǎn)為固定變量，令其取值為

51、1或0，使問題分成兩個子域。令一個子域中的自由變量都取0值，加上固定變量取值，組成此子域的解。（3）計算此解的目標(biāo)函數(shù)值，與已求出的可行解最小目標(biāo)函數(shù)值比較。如果前者大，則不必檢驗其是否可行而停止分枝，若子域都檢驗過，轉(zhuǎn)步驟（7），否則轉(zhuǎn)步驟（6）。因繼續(xù)分枝即使得到可行解，其目標(biāo)函數(shù)值也較大，不會是最優(yōu)解；如前者小，進(jìn)行步驟（4）。對第一次算出的目標(biāo)函數(shù)值，不必進(jìn)行比較，直接轉(zhuǎn)到步驟（4）。（4）檢驗解是否可行。如可行，已得一個可行解，計算并記下它的z值，并停止分枝，若子域都檢驗過，轉(zhuǎn)步驟（7），否則轉(zhuǎn)步驟（6）。因繼續(xù)分枝，即使得到可行解，目標(biāo)函數(shù)值也比記下的z值大，不會是最優(yōu)解；如不可行

52、，進(jìn)行步驟（5）。135隱枚舉法求解步驟（二）（5）將子域固定變量的值代入第一個不等式約束條件方程，并令不等式左端的自由變量當(dāng)系數(shù)為負(fù)時取值為1，系數(shù)為正時取值為0，這就是左端所能取得最小值。若此最小值大于右端值，則稱此子域為不可行子域，不再往下分枝，若子域都檢驗過，轉(zhuǎn)步驟（7），否則，轉(zhuǎn)步驟（6）；若此最小值小于右端值，則依次檢驗下一個不等式約束方程，直至所有的不等式約束方程都通過，若子域都檢驗過，轉(zhuǎn)步驟（7），否則，轉(zhuǎn)步驟（6）。（6）定出尚未檢驗過的另一個子域的解，執(zhí)行步驟（3）（5），若所有子域都停止分枝，計算停止，目標(biāo)函數(shù)值最小的可行解就是最優(yōu)解；否則，轉(zhuǎn)（7）。（7）檢查有無自由變

53、量。若有，轉(zhuǎn)（2）；如沒有，計算停止。目標(biāo)函數(shù)值最小的可行解就是最優(yōu)解。136隱枚舉法舉例(0,0,0,0,0)(0,1,0,0,0)(0,1,0,1,0)(0,1,0,0,0)(0,1,1,0,0)(0,0,0,0,0)(0,1,0,0,0)(0,0,0,0,0)(1,0,0,0,0)說明： 彩色字體為固定變量。Z1=8，可行，停止分支。Z2=0 Z1 ，不可行；可行子域，分支。Z3=2 Z1 ，不可行，可行子域，分支。Z4=0 Z1 ，不可行，不可行子域，停止分支。Z5=6 Z1 ，可行，停止分支。Z6=2 Z5 ，停止分支。Z8=20時，c(x)=3+2x。每月最多生產(chǎn)4個單位，每月的需

54、求是隨機(jī)的，或為1或為2單位。如果生產(chǎn)的數(shù)量大于需求，就出現(xiàn)庫存。每個月末檢查庫存，1個單位的庫存費(fèi)用是1元。因為庫存能力有限，每月末的庫存量不能超過3單位。但同時要求必須及時滿足需求。在第3個月末要把現(xiàn)有的庫存以每單位2元的價格售出。在第1月的月初，公司有1單位的庫存。如何制定生產(chǎn)策略使三個月內(nèi)的期望費(fèi)用最小。 劃分階段 將三個月分為三個階段，每個月為一個階段 狀態(tài)變量 sk表示第k個月初的庫存數(shù) 決策變量 xk表示第k月生產(chǎn)的單位數(shù) 建立狀態(tài)轉(zhuǎn)移方程 ，其中 為一隨機(jī)需求量或為1或為2 最優(yōu)指標(biāo)函數(shù) fk(sk)表示第k個月初的庫存是時，第k個月至第3個月內(nèi)的最小期望費(fèi)用。設(shè)備更新問題 在

55、企業(yè)中，經(jīng)常遇到設(shè)備陳舊或部分損壞需要更新的問題。從經(jīng)濟(jì)上分析，一種設(shè)備應(yīng)該使用多少年后進(jìn)行更新最合算。這就是要研究的問題。一般來說，一臺新設(shè)備出故障少，維護(hù)費(fèi)用低，帶來的經(jīng)濟(jì)效益就高；隨著使用年限的增加，新設(shè)備逐漸變舊，維護(hù)費(fèi)用增加，效用降低。在適當(dāng)?shù)臅r候，就要賣掉舊設(shè)備，購買新設(shè)備。當(dāng)然，設(shè)備越舊越不值錢，購買新設(shè)備又需要一定數(shù)額的購買費(fèi)，這就是設(shè)備的更新決策問題。 rk(t)：在第k年設(shè)備已使用過t年，再使用1年的效益 uk(t)：在第k年設(shè)備已使用過t年，再使用1年的維修費(fèi)用 ck(t)：在第k年賣掉一臺已使用過t年的設(shè)備，買進(jìn)一臺新設(shè)備的更新費(fèi)用 a：折扣因子，表示一年以后的單位收入

56、價值相當(dāng)于現(xiàn)在的a單位 fk(t)：已使用了t年的舊設(shè)備，從第k年開始在以后繼續(xù)使用到規(guī)定的第n年未知幾年內(nèi)的總回收額設(shè)備更新問題 劃分階段 k表示計劃使用該設(shè)備的年限數(shù) 狀態(tài)變量 sk表示第k年初，設(shè)備已使用過的年數(shù) 決策變量 xk表示第k年初更新，還是繼續(xù)使用舊設(shè)備，分別用R和K表示。 建立狀態(tài)轉(zhuǎn)移方程 動態(tài)規(guī)劃的基本方程資源分配問題 將一種或多種有限的資源，分配給若干個使用者，而使目標(biāo)達(dá)到最優(yōu)設(shè)有一原料，總量為a，用于生產(chǎn)n種產(chǎn)品。若分配數(shù)量xi用于生產(chǎn)第i種產(chǎn)品，其產(chǎn)生的效益為ri(xi)。問如何分配，才能使生產(chǎn)n種產(chǎn)品的總收入最大？ 。 劃分階段 將n種產(chǎn)品按1,2,n的序號排列,每

57、種產(chǎn)品為一個階段,分為n個階段,k=1,2,n. 狀態(tài)變量 sk表示分配給第k個產(chǎn)品至第n 種產(chǎn)品的資源數(shù)。 決策變量 xk表示分配給第k個產(chǎn)品的資源數(shù)。 建立狀態(tài)轉(zhuǎn)移方程 sk+1=sk-xk 最優(yōu)指標(biāo)函數(shù) fk(sk)表示在擁有資源sk，分配給第k種產(chǎn)品至第n 種產(chǎn)品所得到的最大總收入。 基本方程 確定邊界條件 因為在第1階段時的資源為總資源，到第n+1階段時資源已分配完畢，所以 so=a，sn+1=0,fn+1(sn+1)=0.復(fù)合系統(tǒng)可靠性問題 若某種機(jī)器的工作系統(tǒng)有N個部件組成，只要有一個部件失靈，整個系統(tǒng)就不能正常工作。這些部件的正常工作關(guān)系為串接關(guān)系，為提高系統(tǒng)工作的可靠性，在每

58、一個部件上均裝有主要元件的備用件，并且設(shè)計了備用件自動投入裝置。顯然，備用元件越多，整個系統(tǒng)正常工作的可靠性越大。但備用元件多了，整個系統(tǒng)的成本、重量、體積均相應(yīng)加大，工作精度也降低。因此，最優(yōu)化問題是在考慮上述限制條件下，應(yīng)如何選擇各部件的備用元件數(shù)，使整個系統(tǒng)的工作可靠性最大？設(shè)部件i上裝有zi個備用遠(yuǎn)見時，它正常工作的概率是pi(zi)。因此，整個系統(tǒng)正常工作的可靠性，可以用它的正常工作的概率來衡量。即設(shè)部件i的一個備用元件的費(fèi)用為ci，重量為wi，要求整個系統(tǒng)所裝備用元件的總費(fèi)用不超過C，總重量不超過W Xk表示由第k個到第n個部件所容許使用的總費(fèi)用 Yk表示由第k個到第n個部件所容許

59、使用的總重量 Xk+1=xk-zkck Yk+1=yk-zkwk 允許決策集合 動態(tài)規(guī)劃基本方程復(fù)合系統(tǒng)可靠性問題 教學(xué)要求：第八章 馬爾可夫鏈和馬爾可夫決策過程 掌握掌握馬爾可夫分析的基本原理和方法 會運(yùn)用馬爾可夫決策過程解決一些基本問題 了解馬爾可夫決策過程的建模和求解方法 目 錄馬爾可夫鏈 n步轉(zhuǎn)移概率 馬爾可夫鏈中狀態(tài)的分類 穩(wěn)態(tài)概率 馬爾可夫決策規(guī)劃 目 錄馬爾可夫鏈 n步轉(zhuǎn)移概率 馬爾可夫鏈中狀態(tài)的分類 穩(wěn)態(tài)概率 馬爾可夫決策規(guī)劃 定義離散時間隨機(jī)過程 ：假設(shè)我們觀測一個系統(tǒng)在離散時間點(diǎn)上某個特性的情況，令 為此系統(tǒng)特性在時刻t的值。離散時間的隨機(jī)過程就是關(guān)于隨機(jī)變量 之間關(guān)系的描

60、述。 馬爾可夫鏈 ：稱一個離散時間隨機(jī)過程為馬爾可夫鏈，如果對于所有的 和狀態(tài)，成立 稱概率規(guī)則在時間上是平穩(wěn)的鏈為平穩(wěn)馬爾可夫鏈。轉(zhuǎn)移概率 ：在馬爾可夫鏈中，對于所有的狀態(tài)i和j，以及所有的時刻t，有 ，稱 為馬爾可夫鏈的轉(zhuǎn)移概率。對于平穩(wěn)馬爾可夫鏈，轉(zhuǎn)移概率可以用一個轉(zhuǎn)移概率矩陣P表示。 例題賭徒問題 考慮一賭徒，在時刻0擁有賭金2元，在時刻 進(jìn)行賭局。在每賭博中，贏一元的概率是 ，輸一元的概率是 。賭徒的目標(biāo)是賭金增加到4元，所以當(dāng)賭金增加到4元或輸光時賭博結(jié)束。 請描述此離散時間隨機(jī)過程 ，并判斷其是否為一個平穩(wěn)馬爾可夫鏈？若是，請寫出其概率轉(zhuǎn)移矩陣。解答 我們定義 為賭徒在第t場賭局