運籌學教材課件匯總完整版ppt全套課件最全教學教程整本書電子教案全書教案合集最新課件匯編

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

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

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

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

5、原理線性規(guī)劃的初始解解法實用舉例 某公司通過市場調研，決定生產(chǎn)高中檔新型拉桿箱。某分銷商決定買進該公司3個月內的全部產(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月內各部的最大生產(chǎn)時間為剪裁部630小時、縫合部600小時、定型部708小時、檢驗包裝部135小時。 通過市場調研部和會計部的調查核算得出結論：生產(chǎn)中檔拉桿箱的利潤是10元，高檔拉桿箱的利潤是9元

6、。公司應各生產(chǎn)多少中檔和高檔拉桿箱才能使公司利潤最大？實用舉例 某公司通過市場調研，決定生產(chǎn)高中檔新型拉桿箱。某分銷商決定買進該公司3個月內的全部產(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月內各部的最大生產(chǎn)時間為剪裁部630小時、縫合部600小時、定型部708小時、檢驗包裝部135小時。 通過市場調研部和會計部的調查核算得出結論：生產(chǎn)中檔拉桿箱的利潤是

7、10元，高檔拉桿箱的利潤是9元。公司應各生產(chǎn)多少中檔和高檔拉桿箱才能使公司利潤最大？可以通過線性規(guī)劃求解！線性規(guī)劃模型的建立 建立相應的線性規(guī)劃模型 ：其中的 稱為決策變量。目標函數(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ù)矩陣)一般線性規(guī)劃模型線性規(guī)劃模型的標準形式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ī)劃的標準型，即標準化原問題標準化方法目標

9、函數(shù)Max f(x)Max f(x)Min f(x)Max f(x)約束條件引入松弛變量和人工變量引入松弛變量, 不變變量 不變對某個對某個是任意的 線性規(guī)劃模型的標準化例:將如下線性規(guī)劃模型標準化：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取值無約束。 目標優(yōu)化標準化線性規(guī)劃模型的標準化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 決策變量的標準化: 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ī)劃模型的標準化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約束關系標準化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ī)劃問題的可行解。所有可行解的集合稱為可行域。基：設A是約束方程組的mn階系數(shù)矩陣，秩為m， 是A中階非奇異子矩陣（即 ），則稱是線性規(guī)劃問題的一個基矩陣，簡稱基。B中的列向量稱為基向量，與基向量對應的變量x稱為基變量，其它變量稱為非基變量。 基本解：令非基變量=0，則由Ax=b可求出一個解，這個解x稱為基本解?；究尚薪猓簼M足非負條件的基本解稱為基本可行解。最優(yōu)解：使目標函

13、數(shù)達到最優(yōu)值的可行解稱為最優(yōu)解。 線性規(guī)劃的解 可行解、基本解、基本可行解的關系可行解基本解基本可行解目 錄線性規(guī)劃實例與模型線性規(guī)劃的圖解法與基本性質單純形法原理線性規(guī)劃的初始解解法線性規(guī)劃的圖解法 當只有兩個決策變量時，可用圖解法求解！例：用圖解法求解以下線形規(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ī)劃的基本性質 X可行域內部的點 可行解? 是 最優(yōu)解? 不 若線性規(guī)劃有

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

15、規(guī)劃實例與模型線性規(guī)劃的圖解法與基本性質單純形法原理一、初始基本可行解的確定考慮如下形式的線性規(guī)劃問題max z=c1x1+c2x2+.+cnxn s.t. a11x1+a12x2+a1nxnb1 a21x1+a22x2+a2nxnb2 (2.17） . am1x1+am2x2+ +amnxnbm x1，x2，.，xn0 （2.18）對每個不等式約束引入一個非負松弛變量，得標準形式：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)解。單純形法求解步驟將所給問題化為標準形找出一個初始可行基,建立初始單純形表檢查所有檢驗數(shù)(若全為非負,則已得到最優(yōu)解,計算停止.否則繼續(xù)下一步)考察是否無解(若是,計算停止,否則繼續(xù)下一步)確定入基變量,出基變量對初始單純形表進行單純形變換單純形方法的一般步驟確定一個初始可行角點根據(jù)某種法則進行角點的最優(yōu)性判

17、斷不是最優(yōu)角點是最優(yōu)角點考察與當前角點相鄰的 “更好”的一個角點，并置為當前角點。根據(jù)某種法則進行LP的無界或不可行判斷無界或不可行還不能做出判斷求解結束單純形法舉例解：引進松馳變量x3, x4，化為標準形得： 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ù)，表明目標函數(shù)已達到最大值，上述表為最優(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法基本思想：在約束條件中增加人工變量，同時修改目標函數(shù)，對目標函數(shù)加上具有很大正系數(shù)M的懲罰項，為使人工變

19、量不影響目標函數(shù)取值，在迭代過程中，應把人工變量從基變量中退出，使其成為非基變量。 其中，M是很大的正數(shù)，同時增加兩個人工變量。 不容易找到初始可行解找初始可行解11-300MMbi/yibx1X2x3x4x5x6x70X4111-21100011MX6321-40-1103/2MX71(1)0-2000111-3M1-M-3+6M0M00 要求最后得到的基變量中不含人工變量X1進基，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)榉腔兞?，求出原問題的一個基本可行解。如果第一階段求解結果表明問題有可行解時，進行第二階段，就是從得到的基本可行解出發(fā)，用單純形方法求原問題的最優(yōu)解。兩階段法舉例例：第一階段：第二階段：用單純形法求得第一階段的解為： 用單純形法求解規(guī)劃問題得最優(yōu)解 目標函數(shù)的最優(yōu)解是 Excel Solver（規(guī)劃求解） Excel采用了電子表格的形式，幫助管理者提高數(shù)據(jù)管理的能力，因而得以廣泛應用。Solver插件專門用于求解帶約束的最優(yōu)化問題。 Solv

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

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

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

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

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

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

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

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

29、格：約束條件的右側值每增加一個單位導致最優(yōu)解的增加量。對偶價格只適用于約束條件右側值變化比較小的情況。當資源越來越多時，約束條件右側的值也越來越大，其它的約束條件就有可能成為緊約束，限制目標函數(shù)值的變大。決策變量、影子價格之間的對應關系 例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 (非負條件)用單純形法求解得：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)計劃下，每一種資源都有所剩余，必然還可進一步通過剩余資源的組合增加生產(chǎn)收入(例如，將x2增加到24)。這表明該生產(chǎn)計劃必定不是最優(yōu)的生產(chǎn)計劃。換言之，如果一

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

33、否將設備用于外加工或出租，若租費高于某設備的影子價格，可考慮出租該設備，否則不宜出租。 第二，是否將投資用于購買設備，以擴大生產(chǎn)能力，若市價低于某設備的影子價格，可考慮買進該設備，否則不宜買進。影子價格的經(jīng)濟含義 在報告列表框中選擇“敏感性報告”影子價格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，則可確定應首先增加電資源，因為相比之下它能導致更多的生產(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)濟收益為 3002%0.52=3.12在線性規(guī)劃中，我們假定模型的系數(shù)都是已知常數(shù)。而在實際中，各種條件都是動態(tài)變化的，因此這種假定很難成立。靈敏度分析將回答：最優(yōu)解對線性規(guī)劃模型中各種系數(shù)變化的敏感性靈敏度分析靈敏度分析目標函數(shù)系數(shù)的變化 Max Z = 40 x + 50y利潤s.t.1x + 2y 40時間約束4x + 3y 120人力約束x, y 0非負約束目標函數(shù)系數(shù)在什么范圍變化時，目標函數(shù)的最優(yōu)解不會發(fā)生變化？ 圖像表示x240403020 x1 最優(yōu)解變化圖像表示x240403020 x1 最優(yōu)解變化 約束條件

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

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

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

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

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

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

42、數(shù)。 （ ）為目標的預期目標值；bj 為系統(tǒng)的資源量。 這里 僅表示目標的優(yōu)先等級， 后的函數(shù)表示該等級內的目標函數(shù)。在這里，我們規(guī)定 優(yōu)先于 ，等等。記為：在對目標規(guī)劃問題求解時，只有在盡量滿足 等級內的目標函數(shù)前提下，才能考慮實現(xiàn) 等級內的目標。在這里 不是一個具體的數(shù)，而只表示各等級間的從屬關系。所以，我們稱 為優(yōu)先權因子。 稱為目標規(guī)劃的目標函數(shù)。目 錄目標規(guī)劃實例與模型目標規(guī)劃求解方法目標規(guī)劃的靈敏度分析用Excel求解目標規(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ù)。如 行內有最大正檢驗數(shù)，就確定它為最優(yōu)列，進行迭代。直到 行內檢驗數(shù)沒有正值為止，再轉入 行尋找最大檢驗數(shù)。如此繼續(xù)下去，直到所有檢驗數(shù)全部檢查完畢。檢驗數(shù)的計算：以 列為例，此時， ， 所以， 。故在檢驗數(shù)欄中的 行和 行與 列的交叉點處的數(shù)分別為1和5。 目 錄目標規(guī)劃實例與模型目標規(guī)劃求解方法目

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

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

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

47、。 如果在B3建新廠，y3=1；否則，y3=0。 如果在B4建新廠，y4=1；否則，y4=0。 xij：表示從工廠i 到銷售中心j的運輸量；i=1,5；j=1,2,3。 利用已知的數(shù)據(jù)，年運輸成本為： 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運到A1，A2，A3三個城市銷售中心的總量應小于等于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ī)劃實例與模型01整數(shù)規(guī)劃的建模方法分支定界法割平面法指派問題應用舉例和Excel求解131實例分析 某電冰箱廠正在考慮隨后4年內有不同資金要求的投資方案。面對每年有限的資金，工廠領導需要選擇最好的方案，使資金預算方案的當前估算凈值最大化。每種方案的現(xiàn)金估算凈值（現(xiàn)金估算凈值為第

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

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

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

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

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

56、價值相當于現(xiàn)在的a單位 fk(t)：已使用了t年的舊設備，從第k年開始在以后繼續(xù)使用到規(guī)定的第n年未知幾年內的總回收額設備更新問題 劃分階段 k表示計劃使用該設備的年限數(shù) 狀態(tài)變量 sk表示第k年初，設備已使用過的年數(shù) 決策變量 xk表示第k年初更新，還是繼續(xù)使用舊設備，分別用R和K表示。 建立狀態(tài)轉移方程 動態(tài)規(guī)劃的基本方程資源分配問題 將一種或多種有限的資源，分配給若干個使用者，而使目標達到最優(yōu)設有一原料，總量為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)轉移方程 sk+1=sk-xk 最優(yōu)指標函數(shù) fk(sk)表示在擁有資源sk，分配給第k種產(chǎn)品至第n 種產(chǎn)品所得到的最大總收入。 基本方程 確定邊界條件 因為在第1階段時的資源為總資源，到第n+1階段時資源已分配完畢，所以 so=a，sn+1=0,fn+1(sn+1)=0.復合系統(tǒng)可靠性問題 若某種機器的工作系統(tǒng)有N個部件組成，只要有一個部件失靈，整個系統(tǒng)就不能正常工作。這些部件的正常工作關系為串接關系，為提高系統(tǒng)工作的可靠性，在每

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

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

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