第4章最優(yōu)化方法運籌學ppt課件

1、第四章 最優(yōu)化方法(運籌學)第一節(jié) 線性(Linear Programing )規(guī)劃第二節(jié) 運輸問題和指派問題第三節(jié) 動態(tài)規(guī)劃問題？怎樣才是最漂亮的最帥？金字塔、巴特農(nóng)神殿、巴黎鐵塔等,在文藝復興時期也更有許多以黃金比例創(chuàng)造出來旳作品人從肚臍開始分,上半身到頭,下半身到腳,這個比例符合 1:1.168 是最美旳。 鼻子以及嘴巴旳寬度 = 1:1.618。 鼻子側(cè)面字型,鼻梁旳長度以及鼻尖高度旳比 = 1:1.618。從正面看來嘴巴長度以及嘴角到臉部輪廓邊旳長度比 = 1:1.618。 臉寬以及臉長各為眼睛長度旳 5 倍以及 8 倍,比 = 5:8。也相近于 1:1.618 歐洲的古代城堡為什么

2、建成圓形？案例：生產(chǎn)計劃問題例1. 某工廠在計劃期內(nèi)要安排、兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及A、B兩種原材料的消耗、資源的限制，如下表：v問題：工廠應(yīng)分別生產(chǎn)多少單位問題：工廠應(yīng)分別生產(chǎn)多少單位、產(chǎn)品才能產(chǎn)品才能使工廠獲利最多？使工廠獲利最多？第一節(jié) 線性規(guī)劃一、在管理中一些典型的線性規(guī)劃應(yīng)用二、線性規(guī)劃的一般模型三、線性規(guī)劃問題的計算機求解Excel，lingo）第一節(jié) 線性規(guī)劃一、在管理中一些典型的線性規(guī)劃應(yīng)用1、合理利用線材問題：如何在保證生產(chǎn)的條件下，下料最少2、配料問題：在原料供應(yīng)量的限制下如何獲取最大利潤3、投資問題：從投資項目中選取方案，使投資回報最大4、產(chǎn)品生產(chǎn)

3、計劃：合理利用人力、物力、財力等，使獲利最大5、勞動力安排：用最少的勞動力來滿足工作的需要6、運輸問題：如何制定調(diào)運方案，使總運費最小小知識茅于軾擇優(yōu)分配原理茅于軾通過引進帕累托最優(yōu)理論和帕累托改進理論，提出他的擇優(yōu)分配原理帕累托最優(yōu)Pareto Optimality是指資源分配的一種理想狀態(tài)：如果固有的一群人和可分配的資源，從一種分配狀態(tài)到另一種分配狀態(tài)的變化中，在沒有使任何人境況變壞的前提下，不會使任何一個人變得更好。帕累托改進Pareto improvement是指資源分配的一種改進狀態(tài)：如果固有的一群人和可分配的資源，從一種分配狀態(tài)到另一種分配狀態(tài)的變化中，在沒有使任何人境況變壞的前提

4、下，可以使其中至少一個人變得更好。帕累托改進是達到帕累托最優(yōu)的路徑和方法。由于從帕累托改進到帕累托最優(yōu)的核心精神是資源優(yōu)化配置，而西方經(jīng)濟學的本質(zhì)是配置經(jīng)濟學，“帕累托最優(yōu)”、“帕累托改進成了100多年來西方經(jīng)濟學的核心概念。第一節(jié) 線性規(guī)劃二、線性規(guī)劃的一般模型（一線性規(guī)劃的組成：目標函數(shù) Max F 或 Min F約束條件 s.t. (subject to) 滿足于決策變量 用符號來表示可控制的因素第一節(jié) 線性規(guī)劃（二建模過程1.理解要解決的問題，了解解題的目標和條件；2.定義決策變量（ x1 ，x2 ， ，xn ），每一組值表示一個方案；3.用決策變量的線性函數(shù)形式寫出目標函數(shù)，確定最大

5、化或最小化目標；4.用一組決策變量的等式或不等式表示解決問題過程中必須遵循的約束條件第一節(jié) 線性規(guī)劃（三線性規(guī)劃模型的一般形式目標函數(shù)： Max （Min） z = c1 x1 + c2 x2 + + cn xn 約束條件：s.t. a11 x1 + a12 x2 + + a1n xn （ =, ）b1 a21 x1 + a22 x2 + + a2n xn （ =, ）b2 am1 x1 + am2 x2 + + amn xn （ =, ）bm x1 ，x2 ， ，xn 0 例題分析1：生產(chǎn)計劃問題例1. 某工廠在計劃期內(nèi)要安排、兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及A、B兩種原材料

6、的消耗、資源的限制，如下表：問：工廠應(yīng)分別生產(chǎn)多少單位問：工廠應(yīng)分別生產(chǎn)多少單位、產(chǎn)品才能使工產(chǎn)品才能使工廠獲利最多？廠獲利最多？例題分析1：生產(chǎn)計劃問題解：工廠應(yīng)分別生產(chǎn)、產(chǎn)品x1、x2單位，則所求的線性規(guī)劃模型為：Max z = 50 x1 + 100 x2 s.t. x1 + x2 300 2 x1 + x2 400 x2 250 x1 , x2 0例題分析2：食譜問題例1 已知某人每周所需的營養(yǎng)成分、所食用的食品及單位食品所含營養(yǎng)如下表所示：營養(yǎng)成分營養(yǎng)成分 大米大米 白菜白菜 雞蛋雞蛋 豬肉豬肉 營養(yǎng)成分的需要量（周）營養(yǎng)成分的需要量（周）蛋白質(zhì)蛋白質(zhì)某維生素某維生素某礦物質(zhì)某礦物質(zhì)

7、 a11 a12 a13 a14 a21 a22 a23 a24 a31 a32 a33 a34 b1 b2 b3單價（元）單價（元） c1 c2 c3 c4 問這個人每周應(yīng)食用大米、白菜、雞蛋和豬肉各多問這個人每周應(yīng)食用大米、白菜、雞蛋和豬肉各多少，能使生活費用最省？少，能使生活費用最省？例題分析2：食譜問題解：設(shè)這個人每周應(yīng)食用大米、白菜、雞蛋、豬肉各為x1、x2、x3、x4，則所求的線性規(guī)劃模型為：minZ = c1x1+c2x2+c3x3+c4x4s.t. a11x1+a12x2 +a13x3+a14x4b1 a21x1+a22x2+a23x3+a24x4 b2 a31x1+a32x2

8、+a33x3+a34x4 b3 x1,x2,x3,x4 0小知識明尼蘇達大學建立食物營養(yǎng)價值評估數(shù)據(jù)庫，可對每天需要的營養(yǎng)與食物作最優(yōu)化選擇作業(yè)：建立自己的小營養(yǎng)優(yōu)化選擇例題分析3：人力資源分配問題例2某晝夜服務(wù)的公交線路每天各時間段內(nèi)所需司機和乘務(wù)人員數(shù)如下： 設(shè)司機和乘務(wù)人員分別在各時間段一開始時上班，并連設(shè)司機和乘務(wù)人員分別在各時間段一開始時上班，并連續(xù)工作八小時續(xù)工作八小時(注意每班次才注意每班次才4小時小時)，問該公交線路怎樣安排，問該公交線路怎樣安排司機和乘務(wù)人員，既能滿足工作需要，又配備最少司機和乘司機和乘務(wù)人員，既能滿足工作需要，又配備最少司機和乘務(wù)人員務(wù)人員?例題分析3：人力

9、資源分配問題解：設(shè) xi 表示從第i班次開始上班的司機和乘務(wù)人員數(shù)(i=1,2,3,4,5,6),這樣我們建立如下的數(shù)學模型。 Min Z = x1 + x2 + x3 + x4 + x5 + x6 s.t. x1 + x6 60 x1 + x2 70 x2 + x3 60 x3 + x4 50 x4 + x5 20 x5 + x6 30 x1,x2,x3,x4,x5,x6 0例題分析4：合理下料問題例4 假定現(xiàn)有一批某種型號的圓鋼長8米，需要裁取長2.5米的毛坯100根、長1.3米的毛坯200根，問應(yīng)該怎樣選擇下料方式才能既滿足需要，又使總的用料最??？解：各種可能的裁剪方案如下表所示：型號型

10、號方案方案1 方案方案2 方案方案3 方案方案4需要根數(shù)需要根數(shù)2.5米米1.3米米 3 2 1 0 0 2 4 6 100 200余料余料(米米) 0.5 0.4 0.3 0.2 例題分析4：合理下料問題設(shè) x1,x2,x3,x4 分別為上面4種方案下料的原材料根數(shù)。這樣我們建立如下的數(shù)學模型。Min f = x1 + x2 + x3 + x4s.t. 3x1 + 2x2 + x3 100 2x2 + 4x3 + 6x4 200 x1,x2,x3,x4 0例題分析5：投資問題例5 某部門現(xiàn)有資金200萬元，今后五年內(nèi)考慮給以下的項目投資。知：項目A：從第一年到第五年每年年初都可投資，當年末能

11、收回本利110%；項目B：從第一年到第四年每年年初都可投資，次年末能收回本利125%，但規(guī)定每年最大投資額不能超過30萬元；項目C：需在第三年年初投資，第五年末能收回本利140%，但規(guī)定最大投資額不能超過80萬元；項目D：需在第二年年初投資，第五年末能收回本利155%，但規(guī)定最大投資額不能超過100萬元。 問應(yīng)如何確定這些項目的每年投資額，使得第五年年末擁有資金的本利金額為最大？例題分析4：投資問題解：設(shè) xij ( i = 15，j = 14)表示第 i 年初投資于A(j=1)、B(j=2)、C(j=3)、D(j=4)項目的金額。這樣我們建立如下的決策變量： 1 2 3 4 5 A x11

12、x21 x31 x41 x51 B x12 x22 x32 x42 C x33 D x24例題分析5：投資問題Max z = 1.1x51+ 1.25x42+ 1.4x33 + 1.55x24 s.t. x11+ x12 = 200 x21 + x22+ x24 = 1.1x11(第二年的投資與第一年投資回收的本利金相等) x31 + x32+ x33 = 1.1x21+ 1.25x12 x41 + x42 = 1.1x31+ 1.25x22 x51 = 1.1x41+ 1.25x32 xi2 30 ( i =1、2、3、4 ) x33 80 x24 100 xij 0 ( i = 1、2、3

13、、4、5；j = 1、2、3、4） 線性規(guī)劃解法圖解法）F變量：x表示A的臺數(shù)，y表示B的臺數(shù)F目標函數(shù)：利潤最大Fmax f(x,y)=x6y7F約束條件：2x+3y=24F 2x+y=0 圖作業(yè)法0510 xY10502x+y=162x+3y=603x+2y=405x+y=35x=0y=0線性規(guī)劃的圖解法P97 例4：Max S(x,y)=7x+12y9x+4y=3604x+5y=2003x+10y=126x+2y=122x+2y=82x+2y=84x+12y=244x+12y=240=x=70=x=7，0=y=70=y=72 4 6 776426x+2y=122x+2y=84x+12y=

14、24y=7x=7E(0,7)D(0,6)(0,4)(0,2) (0,0)(2,0) (4,0) A(6,0)G(7,0)F(7,7)C(1,3)B(3,1)圓圈表示可行域的邊界圓圈表示可行域的邊界最優(yōu)解在圓圈所在的點取得把這些點分別代入目標把這些點分別代入目標函數(shù)，求得函數(shù)，求得S值分別為：值分別為：A1200，B760，C680，D960，E1120，F(xiàn)2520，G1400，所以，所以C為最優(yōu)為最優(yōu)點。點。例:求以下最優(yōu)解Max Z(x,y)=2x+3yS.T.x+y=4x=0y=0線性規(guī)劃求解結(jié)論線性規(guī)劃求解結(jié)論若線性規(guī)劃有可行解，則可行域是個凸多邊形，或是凸集集中任兩點線段仍在集中）若線

15、性規(guī)劃有最優(yōu)解，則最優(yōu)解可能是唯一，也可能是無窮。如唯一一定在凸多邊形的某頂點上；如是無窮則一定充滿凸多邊形的一條邊界上如有可行解，但沒有有限最優(yōu)解，這時凸多邊形是無界的，反之不一定成立如上例）沒有可行解，即可行解集是空集用EXCEL進行線性規(guī)劃例：學校準備為學生添加營養(yǎng)餐，每個學生每月至少要補充60單位碳水傾到物，40單位蛋白質(zhì)和35單位脂肪。已知A、B兩種營養(yǎng)品的含量價格如下表，問A、B分別 要多少單位既滿足學生需要又價格最??？A AB B碳水化合物52蛋白質(zhì)32脂肪51單價1.5元/斤0.7元/斤第一步：描述問題并建立問題模型Min S(x,y)=1.5x+0.7yS.T.5x+2y=6

16、03x+2y=405x+y=35X,y=0第二步 利用規(guī)劃求解工具注意如沒有，需要另外加載）目標單元格是必須可計算公式注意是求解最大還是最小值可變單元格是最優(yōu)解約束條件根據(jù)需要添加操作實驗 ：對課堂上的線性規(guī)劃例子用Excel求解實例1某企業(yè)生產(chǎn)混合飼料，規(guī)定：蛋白質(zhì)至少有15%，脂肪至少4.5%，淀粉至少30%，纖維素不得超過10%。所提供的原材料有：花生餅，每噸單價500元，含25%蛋白質(zhì)、2%脂肪、10%淀粉、2%纖維素花生秧，每噸50元，含 8%蛋白質(zhì)、1%脂肪、5%淀粉、40%纖維素骨粉，每噸350元，20%蛋白質(zhì)、8%脂肪、1%淀粉、0.5%纖維素玉米，每噸450元，7%蛋白質(zhì)、5

17、%脂肪、40%淀粉、6%纖維素滿足營養(yǎng)成分前提下，配合費用最低建模決策變量：四種原料，各自需要為X1、X2、X3、X4目標函數(shù)：max=500X1+50X2+350X3+450X4約束條件：25%x1+8%x2+20%x3+7%x415% 2%x1+1%x2+8%x3+5%x44.5% 10%x1+5%x2+1%x3+40%x430% 2%x1+40%x2+0.5%x3+6%x410% X1,X2,X3,X4 0 X1+X2+X3+X4=1(歸一條件)發(fā)現(xiàn)問題總量沒有為1而是1.17所以要增加約束條件，決策總量單元格G6=1計算后發(fā)現(xiàn)無解,需要重新調(diào)整原料和降低營養(yǎng)成份對偶問題與影子價格在經(jīng)濟

18、活動中可以追求最大利潤，也可以追求最低成本，這是一個問題兩種不同表現(xiàn)形式。反映在數(shù)學上，就是互為對偶的線性規(guī)劃問題表達，而且這兩個問題可以同時實現(xiàn)。對偶問題變換規(guī)則原問題原問題對偶問題對偶問題目標函數(shù)max目標函數(shù)min約束條件=約束條件=約束條件=對偶變量=對偶變量=對偶變量=約束條件=自由變量 自由變量約束條件=例題分析1：生產(chǎn)計劃問題對偶問題例1. 某工廠在計劃期內(nèi)要安排、兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及A、B兩種原材料的消耗、資源的限制，如下表：問：工廠應(yīng)分別生產(chǎn)多少單位問：工廠應(yīng)分別生產(chǎn)多少單位、產(chǎn)品才能使工產(chǎn)品才能使工廠獲利最多？廠獲利最多？對偶問題設(shè)備x1,原料A

19、x2，原料Bx3目標函數(shù)minZ=300*x1+400*x2+250*x3S.TX1+2*x2=50X1+x2+x3=100X1、X2、X3=0習題：食品營養(yǎng)例中的對偶問題Min S(x,y)=1.5x+0.7yS.T.5x+2y=603x+2y=405x+y=35X,y=0對偶Max S(Z1,Z2,Z)=60*Z1+40*z2+35*z3S.T.5*z1+3*z2+5*z3=1.52*z1+2*z2+z3=0敏感性分析注意線性模型與假定非負勾選上敏感性分析作用低于陰影價格購買或應(yīng)用該約束條件是好的決策可以分析哪個約束條件比較敏感，對此部分條件因素要變化時要慎重決策第二節(jié) 運輸問題和指派問題

20、特殊的線性規(guī)劃問題）一、運輸問題二、指派問題案例：產(chǎn)銷平衡問題例1 某公司從兩個產(chǎn)地A1、A2將物品運往三個銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如下表所示，問：應(yīng)如何調(diào)運可使總運輸費用最??？案例：產(chǎn)銷平衡問題解：產(chǎn)銷平衡問題： 總產(chǎn)量 = 總銷量 設(shè) xij 為從產(chǎn)地Ai運往銷地Bj的運輸量，得到下列運輸量表：Min f = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23 s.t. x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150

21、x13 + x23 = 200 xij 0 ( i = 1、2；j = 1、2、3）EXCEL求解過程1.建立決策變量區(qū)域2.用函數(shù) sumproduct建立決策目標公式3.決策區(qū)域中，分別對供銷，用sum函數(shù)進行合計計算4.點擊目標公式區(qū)域，用線性規(guī)劃選擇目標和變量區(qū)域約束條件設(shè)置很重要變量區(qū)域0，sum函數(shù)統(tǒng)計的區(qū)域要與常數(shù)區(qū)域數(shù)值相等）求解完成注意：如某產(chǎn)銷條件不平衡時，只需要在條件上根據(jù)情況修改第二節(jié) 運輸問題和指派問題一、運輸問題及其模型A1、 A2、 Am 表示某物資的m個產(chǎn)地； B1、B2、Bn 表示某物質(zhì)的n個銷地；si 表示產(chǎn)地Ai的產(chǎn)量； dj 表示銷地Bj 的銷量； ci

22、j 表示把物資從產(chǎn)地Ai運往銷地Bj的單位運價設(shè) xij 為從產(chǎn)地Ai運往銷地Bj的運輸量，得到下列一般運輸量問題的模型： （一產(chǎn)銷平衡問題 m n Min f = cij xij i = 1 j = 1 n s.t. xij = si i = 1,2,m j = 1 m xij = dj j = 1,2,n i = 1 xij 0 (i = 1,2,m ; j = 1,2,n) 第二節(jié) 運輸問題和指派問題（二產(chǎn)大于銷問題 m n Min f = cij xij i = 1 j = 1 n s.t. xij si i = 1,2,m j = 1 m xij = dj j = 1,2,n i =

23、 1 xij 0 (i = 1,2,m ; j = 1,2,n) 第二節(jié) 運輸問題和指派問題（三銷大于產(chǎn)問題 m n Min f = cij xij i = 1 j = 1 n s.t. xij = si i = 1,2,m j = 1 m xij dj j = 1,2,n i = 1 xij 0 (i = 1,2,m ; j = 1,2,n)注：產(chǎn)銷不平衡時，可加入假想的產(chǎn)地銷大于產(chǎn)時注：產(chǎn)銷不平衡時，可加入假想的產(chǎn)地銷大于產(chǎn)時或銷地產(chǎn)大于銷時），把它化為產(chǎn)銷平衡問題?；蜾N地產(chǎn)大于銷時），把它化為產(chǎn)銷平衡問題。例題分析2：產(chǎn)大于銷問題（四運輸問題的計算機求解例2、某公司從兩個產(chǎn)地A1、A2將

24、物品運往三個銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如下表所示，問：應(yīng)如何調(diào)運可使總運輸費用最??？例題分析2：產(chǎn)大于銷問題解：增加一個虛設(shè)的銷地運輸費用為0例題分析3：銷大于產(chǎn)問題例3、某公司從兩個產(chǎn)地A1、A2將物品運往三個銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如下表所示，問：應(yīng)如何調(diào)運可使總運輸費用最??？ B1 B2 B3 產(chǎn)產(chǎn)量量 A1 6 4 6 200 A2 6 5 5 300 銷銷量量 250 200 200 500 650 例題分析3：銷大于產(chǎn)問題解：增加一個虛設(shè)的產(chǎn)地運輸費用為0 B1 B2 B3

25、 產(chǎn)量產(chǎn)量 A1 6 4 6 200 A2 6 5 5 300 A3 0 0 0 150 銷量銷量 250 200 200 650 650 習題From/toFrom/toE EF FG GH HFactory Factory supplysupplyA A25253535363660601515B B55553030454538386 6C C40405050262665651414D D60604040666627271111Destination Destination requirementrequirement1010121215159 94646第二節(jié) 運輸問題和指派問題二、指派問

26、題特殊的運輸問題）（一任務(wù)數(shù)=人數(shù)產(chǎn)銷平衡的運輸問題）任務(wù)數(shù)與人數(shù)相等的指派問題實質(zhì)上就是產(chǎn)銷平衡的運輸問題，且每行、每列的產(chǎn)量或銷量都等于1。 m n Min f = cij xij i = 1 j = 1 n s.t. xij = 1 i = 1,2,m j = 1 m xij = 1 j = 1,2,n i = 1 xij 0 (i = 1,2,m ; j = 1,2,n) 例題分析4：指派問題例13 有一份說明書，要分別譯成英、日、德、俄四種文字，因各人專長不同，他們完成翻譯不同文字所需的時間見下表：解法：匈牙利法匈牙利法是求解及小型優(yōu)化方向為極小指派問題的一種方法，這種方法最初由w.

27、w.kuhn提出，后經(jīng)改進而形成，解法基于匈牙利數(shù)學家D.Knig給出的一個定理而得名。理論基礎(chǔ):（1若從效率矩陣(cij)的行或列的各元素中分別減去該行或列的最小元素后得到一個新矩陣bij）,則以bij為效率矩陣的指派問題與原問題有相同的最優(yōu)解。經(jīng)過上述變換后，（bij中的每行和每列都至少含有一個0元素，稱位于不同行不同列的0元素為獨立的0元素。 （2假設(shè)bij有n個獨立的0元素，由此可得一個解矩陣，方法為在X中令對應(yīng)于bij的0元素位置的元素為1，其它位置的元素為0，則X為指派問題的最優(yōu)解。 （3D.Knig定理：矩陣中獨立0元素的最多個數(shù)等于能覆蓋所有0元素的最少直線數(shù)。 匈牙利法步驟第

28、一步 變換效率矩陣Cij），使變換后效率矩陣bij的每行每列至少出現(xiàn)一個0元素，同時不出現(xiàn)負元素。（對效率矩陣每行每列減去該行該列最小元素）2 210109 97 715154 414148 813131414161611114 4151513139 9Cij-2-4-11-40 08 87 75 511110 010104 42 23 35 50 00 011119 95 5-50 08 82 25 511110 05 54 42 23 30 00 00 011114 45 5第二步 畫出包含所有0的直線，并使畫出直線條數(shù)最少。如果直線條數(shù)與表中的行或列相等，則獲最優(yōu)解。否則第三步注意不能畫

29、斜線）（例中3條直線0，特別注意要在選項中，將“線性模型和“假定非負鉤選上第二節(jié) 運輸問題和指派問題（二任務(wù)數(shù)人數(shù)產(chǎn)銷不平衡的運輸問題）1、若任務(wù)數(shù)人數(shù)，就增加假想人，就可以化為產(chǎn)銷平衡問題。2、若任務(wù)數(shù) 人數(shù)，就增加假想工作，就可以化為產(chǎn)銷平衡問題。習題項目領(lǐng)導者項目領(lǐng)導者1 12 23 3terryterry101015159 9CandyCandy9 918185 5TomTom6 614143 3第三節(jié) 動態(tài)規(guī)劃一、動態(tài)規(guī)劃的基本概念和方法二、動態(tài)規(guī)劃模型的建立與求解步驟三、動態(tài)規(guī)劃的應(yīng)用案例：最短路問題例16 位于城市A的某公司要把一批貨物送到位于城市E的銷售門市部，途中可能經(jīng)過的城

30、市有B1,B2,B3;C1,C2,C3;D1,D2等8個城市，問如何走，能使路線最短？BACBDBCDEC41231231296487689356231435第三節(jié) 動態(tài)規(guī)劃一、基本概念和方法：（一基本概念1、階段k：表示決策順序的離散的量，階段可以按時間或空間劃分。2、狀態(tài)sk：在各階段開始時的客觀條件稱為各階段的狀態(tài)。狀態(tài)可以是數(shù)量，也可以是字符。3、決策uk：從某一狀態(tài)向下一狀態(tài)過渡時所做的選擇。決策是所在狀態(tài)的函數(shù)，記為uk(sk)。 決策允許集合Dk(sk)：在狀態(tài)sk下，允許采取決策的全體。4、狀態(tài)轉(zhuǎn)移方程 sk+1=Tk(sk, uk)：某一狀態(tài)以及該狀態(tài)下的決策，與下一狀態(tài)之間

31、的函數(shù)關(guān)系。 5、策略Pk,n(sk)：從第k階段開始到最后第n階段的決策序列，稱k子策略。P1,n(s1)即為全過程策略。第三節(jié) 動態(tài)規(guī)劃6、階段指標函數(shù)dk(sk, uk)：從狀態(tài)sk出發(fā)，選擇決策uk所產(chǎn)生的第k階段指標。 過程指標函數(shù)Vk,n(sk, uk, uk+1, un)：從狀態(tài)sk出發(fā)，選擇決策uk,uk+1, , un所產(chǎn)生的過程指標。動態(tài)規(guī)劃要求過程指標具有可分離性，即 Vk,n(sk, uk, uk+1, , un) = vk(sk, uk)+Vk+1(sk+1, uk+1, , un)稱指標具有可加性，或 Vk,n(sk, uk, uk+1, , un) = vk(sk

32、, uk)Vk+1(sk+1,uk+1, , un)稱指標具有可乘性。最優(yōu)指標函數(shù)fk(sk)：從狀態(tài)sk出發(fā)，對所有的策略Pk,n，過程指標Vk,n的最優(yōu)值，即),()(,)(nkknksDxkkPsVsfoptkkk第三節(jié) 動態(tài)規(guī)劃（二基本方法1、最優(yōu)化原理不管在此最優(yōu)策略上的某個狀態(tài)以前的狀態(tài)和決策如何，對該狀態(tài)來說，以后的所有決策必定構(gòu)成最優(yōu)子策略。就是說，最優(yōu)策略的任意子策略都是最優(yōu)的。2、基本方法從最后一個階段的優(yōu)化開始，按逆向順序逐步向前一階段擴展，并將后一階段的優(yōu)化結(jié)果帶到擴展后的階段中去，以此逐步向前推進，直到得到全過程的優(yōu)化結(jié)果。3、遞推方程nksfusdsfkkkkksD

33、xkkoptkkk, 2 , 1)(),()(11)(第三節(jié) 動態(tài)規(guī)劃二、動態(tài)規(guī)劃模型的建立與求解步驟（一建立動態(tài)規(guī)劃模型的基本要求1.所研究的問題必須能夠分成幾個相互聯(lián)系的階段，而且在每一個都具有需要決策的問題.2.在每一階段都必須有若干個與該階段相關(guān)的狀態(tài)。（二動態(tài)規(guī)劃的求解步驟1.列出本階段的所有可能狀態(tài)變量sk。2.對每一狀態(tài)sk列出所有可能的決策變量uk(sk)。第三節(jié) 動態(tài)規(guī)劃3.對每一階段sk,uk(sk)計算本階段的指標值dk(sk,uk)。4.確定狀態(tài)轉(zhuǎn)移方程sk+1=T(sk,uk)，對于每對sk,uk求出sk+1的值。5.對于每一對sk,uk，計算相應(yīng)的指標值dk(sk,

34、uk)+fk+1(sk+1)。6.比較各個指標值，取最優(yōu)者最大值或最小值作為本階段sk狀態(tài)開始的后部子過程的最優(yōu)指標值fk(sk),相應(yīng)的決策uk即是本階段以sk為起始狀態(tài)的最優(yōu)決策u*k。7.在第一階段的最優(yōu)策略確定后，再從第一階段開始，根據(jù)狀態(tài)轉(zhuǎn)移方程確定各階段的最優(yōu)策略u*k。例題分析1：定價問題例17 考慮為某新產(chǎn)品定價，該產(chǎn)品的單價從5元、6元、7元、8元這四種價格中選取其中之一來定價，每年年初允許價格變動，但幅度不能超過1元。該公司預計該產(chǎn)品暢銷只有5年，5年后將被淘汰，另據(jù)銷售情況預測，在價格不同的情況下年度的預計利潤入下表所示，問如何定價，能使利潤最大？單價單價 第一年第一年

35、第二年第二年 第三年第三年 第四年第四年 第五年第五年5元元 10 12 15 20 256元元 12 13 16 20 247元元 14 14 16 18 188元元 16 15 15 14 14例題分析1：定價問題解：（1該問題按年度分為5個階段進行，即k=5。（2狀態(tài)變量sk:第k年初的價格k=1,2,3,4,5）（3決策變量uk:第k+1年初的價格,即sk+1=uk （k=1,2,3,4,5）（4狀態(tài)轉(zhuǎn)移方程：sk+1=uk=sk-1,sk,sk+1, （k=1,2,3,4,5）（5最優(yōu)指標函數(shù)的遞推公式： fk(sk)=maxdk(sk,uk)+fk+1(sk+1)= maxdk(s

36、k,uk)+fk+1(uk), f6(s6)=0, （k=1,2,3,4,5）以下我們從第五階段開始計算例題分析1：定價問題u5s5d5(s5,u5)+f6(s6) 5 6 7 8 f5(s5) U*55 25 2556 24 2467 18 1878 14 148第五階段：第五階段：s5=u5例題分析1：定價問題第四階段:s5=u4=s4-1,s4,s4+1u4s4d4(s4,u4)+f5(s5)= d4(s4,u4)+f5(u4) 5 6 7 8f4(s4) U*45 20+25 20+24 4556 20+25 20+24 20+18 4557 18+24 18+18 18+14 426

37、8 14+18 14+14 327例題分析1：定價問題第三階段:s4=u3=s3-1,s3,s3-1u3s3d3(s3,u3)+f4(s4)= d3(s3,u3)+f4(u3) 5 6 7 8 f3(s3) U*3515+45 15+45 605,6616+45 16+45 16+42 615,67 16+45 16+42 16+326168 15+42 15+32 577例題分析1：定價問題第二階段:s3=u2=s2-1,s2,s2+1u2s2d2(s2,u2)+f3(s3)= d2(s2,u2)+f3(u2) 5 6 7 8 f2(s2) U*25 12+60 12+61 7366 13+

38、60 13+6113+61 746,77 14+61 14+61 14+57756,78 15+61 15+57 767例題分析1：定價問題第一階段:s2=u1=s1-1,s1,s1+1u1s1d1(s1,u1)+f2(s2)= d1(s1,u1)+f2(u1) 5 6 7 8 f1(s1) U*1510+73 10+74 846612+73 12+74 12+75 8777 14+74 14+75 14+769088 16+75 16+76 928 由第一階段分析知道由第一階段分析知道s1=8,故故s2=u*1=8得得u*2=8,故故s3=u*2=8得得u*3=7,故故s4=u*3=7得得u*4=6,故故s5=u*4=6得得u*5=5。即當?shù)谝荒甓▋r即當?shù)谝荒甓▋r8元，第二年定價元，第二年定價8元，第三年定價元，第三年定價7元，第四元，第四年定價年定價6元，第五年定價元，第五年定價5元時，利潤最大，最大利潤為元時，利潤最大，最大利潤為92萬萬元。元。例題分析2：資源分配問題例18