對只具有兩個決策變量的目標規(guī)劃的數(shù)學(xué)模型解析課件

對只具有兩個決策變量的目標規(guī)劃的數(shù)學(xué)模型，我們可以用圖解法來分析求解。通過圖解示例，可以看到目標規(guī)劃中優(yōu)先因子，正、負偏差變量及權(quán)系數(shù)等的幾何意義。圖解法的基本步驟1.令各偏差變量為0，作出所有的約束直線2.作圖表示偏差變量增加對約束直線的影響3.確定滿足第一優(yōu)先級目標集的最優(yōu)解空間（不考慮其他優(yōu)先級）4.轉(zhuǎn)到第k+1優(yōu)先級，求出其相應(yīng)的最優(yōu)解空間5.令k=k+1反復(fù)執(zhí)行步驟（4），直到所有的優(yōu)先級均求解完畢。上周內(nèi)容回顧對只具有兩個決策變量的目標規(guī)劃的數(shù)學(xué)模型，我們可1【例題】某電視機廠裝配黑白和彩色兩種電視機，每裝配一臺電視需占用裝配線1小時，裝配線每周計劃開動40小時，預(yù)計市場每周彩色電視機的銷量是24臺，每臺可獲利為80元，黑白電視機的銷量為30臺，每臺可獲利40元。該廠確定的目標為：第一優(yōu)先級：充分利用裝配線每周計劃開動40小時；第二優(yōu)先級：允許裝配線加班；但加班時間每周盡量不超過10小時；第三優(yōu)先級：裝配電視機的數(shù)量盡量滿足市場需要。因彩色電視機的利潤高，取其權(quán)系數(shù)為2。試建立該問題的目標規(guī)劃模型，并求解黑白電視機和彩色電視機的產(chǎn)量?！纠}】某電視機廠裝配黑白和彩色兩種電視機，每裝配一臺電視需2設(shè)x1,x2分別表示黑白和彩色電視機的產(chǎn)量，該問題的目標規(guī)劃模型為：用圖解法求解，見下圖。設(shè)x1,x2分別表示黑白和彩色電視機的產(chǎn)量，該3x1x205040302010

10203040501.令各偏差變量為0，作出所有的約束直線x1x205010204GHFEDCBAx1x205040302010

1020304050d4+d3-d2+d2-d1+d1-d4-d3+2.作圖表示偏差變量增加對約束直線的影響GHFEDCBAx1x20501025P1,P2的目標實現(xiàn)后，x1,x2的取值范圍為ABCD3.確定滿足第一優(yōu)先級目標集的最優(yōu)解空間（不考慮其他優(yōu)先級）4.轉(zhuǎn)到第k+1優(yōu)先級，求出其相應(yīng)的最優(yōu)解空間GHFEDCBAx1x205040302010

1020304050d4+d3-d2+d2-d1+d1-d4-d3+P1,P2的目標實現(xiàn)后，x1,x2的取值范圍為ABCD3.6P３目標要求，d3-權(quán)系數(shù)大于d4-,取d3-=0，

x1,x2的取值范圍為ABEF在ABEF中，只有

E點d4-取極小值。取E點為滿意解(24,26)5.令k=k+1反復(fù)執(zhí)行步驟（4），直到所有的優(yōu)先級均求解完畢。GHFEDCBAx1x205040302010

1020304050d4+d3-d2+d2-d1+d1-d4-d3+P３目標要求，d3-權(quán)系數(shù)大于d4-,取d3-=0，x17第10章動態(tài)規(guī)劃10.1多階段決策問題10.2多階段決策的有關(guān)概念10.3動態(tài)規(guī)劃的基本思想和基本方程10.4動態(tài)規(guī)劃模型的建立與求解10.5動態(tài)規(guī)劃應(yīng)用舉例

第10章動態(tài)規(guī)劃10.1多階段決策問題8

動態(tài)規(guī)劃所研究的對象是多階段決策問題。所謂多階段決策問題是指一類活動過程，它可以分為若干個相互聯(lián)系的階段，在每個階段都需要作出決策。這個決策不僅決定這一階段的效益，而且決定下一階段的初始狀態(tài)。每個階段的決策確定以后，就得到一個決策序列，稱為策略。多階段決策問題就是求一個策略，使各階段的效益的總和達到最優(yōu)。10.1多階段決策問題動態(tài)規(guī)劃所研究的對象是多階段決策問題。19在實際生產(chǎn)經(jīng)營活動中，存在著一類將過程劃分為若干個相互聯(lián)系的階段，而每個階段都需要做出決策，并且一個階段的決策確定后，常影響下一階段的決策，即多階段決策問題。在這類多階段決策問題中，整個問題的各個階段所確定的決策構(gòu)成一個決策序列，通稱為策略。對應(yīng)于一個策略，就有確定活動效果，且可用數(shù)量指標來衡量。因此多階段決策問題就需要在允許選擇的那些策略中選擇最優(yōu)策略，使在預(yù)定的標準下達到最好的效果。動態(tài)規(guī)劃是一種解決問題的思路，而不是一種算法。這一點與線性規(guī)劃不同，線性規(guī)劃是一種算法。在實際生產(chǎn)經(jīng)營活動中，存在著一類將過程劃分為10

【例10-1】生產(chǎn)與存儲問題某工廠每季度需供應(yīng)市場600，700，500和1200件產(chǎn)品，未銷售完的產(chǎn)品存入倉庫，存儲費為每件每季度1元，生產(chǎn)費用為件數(shù)的平方成正比，比例系數(shù)為0.005。現(xiàn)要制定生產(chǎn)計劃，在滿足市場需求的條件下，使一年的生產(chǎn)與存儲費用最少。按季度的順序分為4個階段，k=1,2,3,4設(shè)第k季生產(chǎn)的產(chǎn)品為uk件，

第k季初的庫存量為sk，

第k季的銷售量為qk

，則sk+1=sk+uk-qk假設(shè)年初和年底無存貨，即

s1=s5=0【例10-1】生產(chǎn)與存儲問題按季度的順序分為4個階段11全過程目標管理函數(shù)為：該問題是求最優(yōu)的生產(chǎn)決策序列，即全年中每季度的最優(yōu)生產(chǎn)量u1*,u2*,u3*,u4*，在滿足市場需求的條件下，使得一年的總費用最少。則該問題的數(shù)學(xué)模型為：全過程目標管理函數(shù)為：該問題是求最優(yōu)的生產(chǎn)決策序12【例10-2】最短路線問題。設(shè)有一輛汽車由A城到B城，中間可經(jīng)過v1到v8城市，各城市的交通路線及距離如圖所示，問應(yīng)選擇哪一條路線，可使總距離最短。Av285685547866924337131234v39v6Bv8v7v5v4v1【例10-2】最短路線問題。設(shè)有一輛汽車由A城到13這一問題看成是四個階段的決策問題，由A到(v1,v2,v3)中的點是第一階段；由(v1,v2,v3)中的點到(v4,v5,v6)中的點是第二階段；由(v4,v5,v6)中的點到(v7,v8)中的點是第二階段；由(v7,v8)中的一點到B是第四階段。要求在各個階段選取一個恰當(dāng)?shù)臎Q策，由這些決策組成的決策序列所決定的一條路線，其總路程最短。Av285685547866924337131234v39v6Bv8v7v5v4v1這一問題看成是四個階段的決策問題，由A到(v1,v2,v3)1410.2多階段決策的有關(guān)概念1.階段把所給問題的過程恰當(dāng)?shù)胤譃槿舾蓚€相互聯(lián)系的階段，以便按一定順序去求解。描述階段的變量稱為階段變量，用k表示。階段的劃分，一般是按時間和空間的自然特征來劃分?！纠?0-1】生產(chǎn)與存儲問題按自然時間分為4個階段（季度）K=1，2，3，4?！纠?0-2】最短路問題按空間的自然特征分為4個階段。年、月、路段10.2多階段決策的有關(guān)概念1.階段152.狀態(tài)狀態(tài)表示每個階段開始時所處的自然狀態(tài)或客觀條件，描述了問題過程的狀況，又稱為不可控因素。描述過程狀態(tài)的變量稱為狀態(tài)變量。用sk表示第k階段所處的狀態(tài)。狀態(tài)變量的取值有一定的允許集合或范圍，此集合稱為狀態(tài)允許集合?！纠?0-1】中狀態(tài)是每個階段開始時的庫存量，它既是前一階段決策的結(jié)果，又是后一階段決策的開始。通常一個階段有若干個狀態(tài)。構(gòu)成狀態(tài)集合。【例10-1】中s1=0，s5=0表示狀態(tài)變量s1，s5的值為0，而s2，s3，s4的取值可能有多種情況。2.狀態(tài)狀態(tài)表示每個階段開始時所處的自然16s1=A，s2=(v1,v2,v3)，s3=(v4,v5,v6)，s4=(v7,v8)狀態(tài)應(yīng)具有無后效性如果某階段狀態(tài)給定后，則在這個階段以后過程的發(fā)展不受這個階段以前各段狀態(tài)的影響；過程的過去歷史只能通過當(dāng)前的狀態(tài)去影響它未來的發(fā)展；構(gòu)造動態(tài)規(guī)劃模型時，要充分注意是否滿足無后效性的要求；如果狀態(tài)變量不能滿足無后效性的要求，應(yīng)適當(dāng)?shù)馗淖儬顟B(tài)的定義或規(guī)定方法。Av285685547866924337131234v39v6Bv8v7v5v4v1【例10-2】中s1=A，s2=(v1,v2,v3)，s3=(v4,v5,v17在實際問題中決策變量的取值往往在某一范圍之內(nèi)，此范圍稱為允許決策集合。常用Dk(sk)表示第k階段從狀態(tài)sk出發(fā)的允許決策集合。決策變量是狀態(tài)變量的函數(shù)。常用uk(sk)

表示第k階段當(dāng)狀態(tài)為sk時的決策變量。3.決策過程的某一階段、某個狀態(tài),可以做出不同的決定(選擇),決定下一階段的狀態(tài)，這種決定稱為決策。描述決策的變量，稱為決策變量?！纠?0-1】中，從第一階段的狀態(tài)s1=0出發(fā)，其允許決策集合為Dk(sk)={600，601，…，3000}【例10-2】中，從第二階段的狀態(tài)s2=v1出發(fā)，其允許決策集合為Dk(sk)={v4,v5,v6}。在實際問題中決策變量的取值往往在某一范圍之內(nèi)18

可供選擇的策略有一定范圍，此范圍稱為允許策略集合，用p表示。從允許策略集合中找出達到最優(yōu)效果的策略稱為最優(yōu)策略。

當(dāng)k=1時，此決策函數(shù)序列成為全過程的一個策略，簡稱策略，記為p1,n

(s1).即

4.策略按順序排列的決策組成的集合；

由第k

n(終止?fàn)顟B(tài))為止的過程，稱為原過程的后部子過程（k子過程）。

由每段的決策按順序排列組成的決策函數(shù)序列稱為k子過程策略，簡稱子策略，記為pk,n(sk)，即可供選擇的策略有一定范圍，此范圍稱為允許策略195.狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程是確定過程由一個狀態(tài)到另一個狀態(tài)的演變過程。本階段的狀態(tài)是上一階段狀態(tài)和上一階段決策的結(jié)果，對于本階段來講，狀態(tài)是已知的。如果給出第k階段狀態(tài)變量sk的值、該階段的決策變量uk一經(jīng)確定，第k+1階段狀態(tài)變量sk+1的值也就確定，其關(guān)系為：5.狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程是確定過程2012ks1u1s2u2s3skukSk+1能用動態(tài)規(guī)劃方法求解的多階段決策過程是一類特殊的多階段決策過程，即具有無后效性的多階段決策過程。圖示如下：【例10-1】中，狀態(tài)轉(zhuǎn)移方程為sk+1=sk+uk–qk其中k=1,2,3,4【例10-2】中，狀態(tài)轉(zhuǎn)移方程為sk+1=uk(sk)12ks1u1s2u2s3skukSk+121

6.指標函數(shù)和最優(yōu)值函數(shù)用來衡量所實現(xiàn)過程優(yōu)劣的一種數(shù)量指標，稱為指標函數(shù)；它分階段指標函數(shù)和過程指標函數(shù)。階段指標函數(shù)：僅是某一階段到下一階段的效益，用dk(sk,uk)表示，指在第k階段由狀態(tài)sk采取決策uk(sk)時的效益。Av285685547866924337131234v39v6Bv8v7v5v4v1【例10-2】中，d3(v4,v7)是指由v4出發(fā)，下一階段的決策是v7的兩點間的距離。即d3(v4,v7)

=3。6.指標函數(shù)和最優(yōu)值函數(shù)用來衡量22過程指標函數(shù)：它是定義在全過程和所有后部子過程上的數(shù)量函數(shù)，表示第k階段狀態(tài)為sk、采用策略pk,n(sk)時后部k子過程的效益值。動態(tài)規(guī)劃模型的指標函數(shù)，應(yīng)具有可分離性，并滿足遞推關(guān)系。

費用、成本、利潤、路長等。用Vk,n

表示之。即Vk,n可以表示為sk,uk,Vk+1,n的函數(shù)Vk,n=f(sk,uk,Vk+1,n)的函數(shù)。過程指標函數(shù)：它是定義在全過程和所有后部子過程上的數(shù)量函數(shù)23常見的指標函數(shù)的形式是：過程和它的任一子過程的指標是它所包含的各階段的指標和。即無后效性的結(jié)果。其中dj(sj

)

表示第

j階段的階段指標。這時上式可寫成過程和它的任一子過程的指標是它所包含的各階段的指標的乘積。即則可改寫成常見的指標函數(shù)的形式是：過程和它的任一子過程的指標是它所包含24

第k階段第n階段狀態(tài)sk

終止?fàn)顟B(tài)采取最優(yōu)策略所得到的指標函數(shù)值。最優(yōu)值函數(shù)：最優(yōu)指標函數(shù)是指從第k階段狀態(tài)采用最優(yōu)策略到過程終止時的最佳效益值，即指標函數(shù)的最優(yōu)值,記為fk(sk)可遞推即采取最優(yōu)策略所得到的指標函數(shù)值。最優(yōu)值函數(shù)：25

Av285685547866924337131234v39v6Bv8v7v5v4v1【例10-2】中，f3*(v4)是指從v4到B的最短距離。整個問題即為f1*(A)是指從A到B的最短距離。具有可分離性Av28568554786692433713123426解多階段決策過程問題，求出

最優(yōu)策略，即最優(yōu)決策序列f1(s1)

最優(yōu)軌線，即執(zhí)行最優(yōu)策略時的狀態(tài)序列

最優(yōu)目標函數(shù)值從k到終點最優(yōu)策略子策略的最優(yōu)目標函數(shù)值解多階段決策過程問題，求出最優(yōu)策略，即最優(yōu)決策序列27步步走近路，距離為：5+7+3+4=19。問題：是否一定最優(yōu)？Av285685547866924337131234v39v6Bv8v7v5v4v110.3動態(tài)規(guī)劃的基本思想和基本方程【例10-2】步步走近路步步走近路，距離為：5+7+3+4=19。Av285685528最優(yōu)化定理作為整個過程的最優(yōu)策略具有如下性質(zhì)：不管在此最優(yōu)策略上的某個狀態(tài)以前的狀態(tài)和決策如何，對該狀態(tài)而言，以后所有的決策必定構(gòu)成最優(yōu)子策略。就是說，最優(yōu)策略的任意子策略都是最優(yōu)的。

對最短路問題而言,從最短路上任一點到終點的部分道路（最短路上的子路）也一定是從該點到終點的最短路。

動態(tài)規(guī)劃的基本思想：逐段分析，逐點考慮并優(yōu)化后，逐步擴大范圍，直到找到最優(yōu)解。最優(yōu)化定理動態(tài)規(guī)劃的基本思想29如果一個問題的最短路在某階段通過Qs，則由點Qs出發(fā)到達終點的這條路線，對于從Qs出發(fā)到達終點的所有可能選擇的不同路線來說，必定是最短路線。QsAB要找到最短路，只要從最后一段開始，用逐步逆推的方法，求出各點到終點的最短路線，最后求得由起點到終點的最短路線。如果一個問題的最短路在某階段通過Qs，則由點30【例10-3】按照動態(tài)規(guī)劃的基本思想求解【例10-2】中最短路問題。Av285685547866924337131234v39v6Bv8v7v5v4v1【例10-3】按照動態(tài)規(guī)劃的基本思想求解【例10-2】中最短31具體計算前，先引進幾個符號：K——階段變量sk——狀態(tài)變量，表示第k階段所處的位置uk——決策變量，表示當(dāng)狀態(tài)為sk時，可選擇的下一狀態(tài)(這里有uk=Sk+l)dk(sk,uk)

——從sk到sk+1＝uk的距離fk*

(sk)——由sk到終點的最短距離。求解此問題的過程，是從最后一個階段開始計算，逐步倒退直到第一階段為止，即用逐步逆推的方法，該問題就是求f1*

(s1)。具體計算前，先引進幾個符號：32Av285685547866924337131234v39v6Bv8v7v5v4v1（1）在第四階段：

當(dāng)k=4時，只要再走一步即到終點B地。目前的狀態(tài)集s4={v7,v8}，可選擇的下一狀態(tài)u4是B。v7Bf4*(v7)=4v8B

f4*(v8)=3從v7和v8到B的最短路徑唯一從v7和v8到B的最短路徑為：Av285685547866924337131234v39v33（2）在第三階段：k=3,s3={v4,v5,v6}說明v4到B的最短距離為7，其最短路線為v4→v7→B,u3(v4)=v7Av285685547866924337131234v39v6Bv8v7v5v4v1u3(v4)=v7v4v7B（2）在第三階段：k=3,s3={v4,v5,v6}說明v434u3(v5)=v8v5v8Bu3(v6)=v7v6v7BAv285685547866924337131234v39v6Bv8v7v5v4v1u3(v5)=v8u3(v6)=v7Av285685547835Av285685547866924337131234v39v6Bv8v7v5v4v1（3）在第二階段：k=2,s2={v1,v2,v3}說明從v1到B的最短距離為9，其最短路線為v1→v5→v8→B，相應(yīng)決策為u2(v1)=v5Av285685547866924337131234v39v36說明從v2到B的最短距離為11，其最短路線為v2→v6→v7→B，相應(yīng)決策為u2(v2)=v6Av285685547866924337131234v39v6Bv8v7v5v4v1說明從v2到B的最短距離為11，其最短路線為v2→v6→v737說明從v3到B的最短距離為13，其最短路線為v3→v5→v8→B，相應(yīng)決策為u2(v3)=v8Av285685547866924337131234v39v6Bv8v7v5v4v1說明從v3到B的最短距離為13，其最短路線為v3→v5→v838從A到B的最短距離為17，其最短路線為A→v1→v5→v8→B，相應(yīng)決策為u1(A)=v1（4）在第一階段：k=1,s1={A}Av285685547866924337131234v39v6Bv8v7v5v4v1步步走近路，不一定是最優(yōu)從A到B的最短距離為17，其最短路線為A→v1→v5→v8→39對一個實際問題，建立動態(tài)規(guī)劃模型的步驟:ⅰ是定義在全過程和所有后部子過程上的數(shù)量函數(shù);ⅱ要具有可分離性，并滿足遞推關(guān)系。即ⅲ函數(shù)k（sk，uk，Vk+1,n）對于變量Vk+1，n要嚴格單調(diào)。1.將問題的過程劃分成恰當(dāng)?shù)碾A段；2.選擇狀態(tài)變量sk,既能描述過程的變化又滿足無后效性；3.確定決策變量uk及每一階段的允許決策集合Dk(sk)；4.正確寫出狀態(tài)轉(zhuǎn)移方程；5.正確寫出指標函數(shù)Vk,n，它應(yīng)滿足下面三個性質(zhì)：對一個實際問題，建立動態(tài)規(guī)劃模型的步驟:ⅰ是定義在全過程和40由上述性質(zhì)，針對實際問題，構(gòu)造動態(tài)規(guī)劃基本方程步驟：確定階段指標函數(shù)vk(sk,uk);確定狀態(tài)轉(zhuǎn)移方程sk+1=Tk(sk,uk)確定動態(tài)規(guī)劃基本方程。動態(tài)規(guī)劃基本方程的一般形式為：邊界條件為或運算+或×是sk的函數(shù)由上述性質(zhì)，針對實際問題，構(gòu)造動態(tài)規(guī)劃基本方41對只具有兩個決策變量的目標規(guī)劃的數(shù)學(xué)模型，我們可以用圖解法來分析求解。通過圖解示例，可以看到目標規(guī)劃中優(yōu)先因子，正、負偏差變量及權(quán)系數(shù)等的幾何意義。圖解法的基本步驟1.令各偏差變量為0，作出所有的約束直線2.作圖表示偏差變量增加對約束直線的影響3.確定滿足第一優(yōu)先級目標集的最優(yōu)解空間（不考慮其他優(yōu)先級）4.轉(zhuǎn)到第k+1優(yōu)先級，求出其相應(yīng)的最優(yōu)解空間5.令k=k+1反復(fù)執(zhí)行步驟（4），直到所有的優(yōu)先級均求解完畢。上周內(nèi)容回顧對只具有兩個決策變量的目標規(guī)劃的數(shù)學(xué)模型，我們可42【例題】某電視機廠裝配黑白和彩色兩種電視機，每裝配一臺電視需占用裝配線1小時，裝配線每周計劃開動40小時，預(yù)計市場每周彩色電視機的銷量是24臺，每臺可獲利為80元，黑白電視機的銷量為30臺，每臺可獲利40元。該廠確定的目標為：第一優(yōu)先級：充分利用裝配線每周計劃開動40小時；第二優(yōu)先級：允許裝配線加班；但加班時間每周盡量不超過10小時；第三優(yōu)先級：裝配電視機的數(shù)量盡量滿足市場需要。因彩色電視機的利潤高，取其權(quán)系數(shù)為2。試建立該問題的目標規(guī)劃模型，并求解黑白電視機和彩色電視機的產(chǎn)量?！纠}】某電視機廠裝配黑白和彩色兩種電視機，每裝配一臺電視需43設(shè)x1,x2分別表示黑白和彩色電視機的產(chǎn)量，該問題的目標規(guī)劃模型為：用圖解法求解，見下圖。設(shè)x1,x2分別表示黑白和彩色電視機的產(chǎn)量，該44x1x205040302010

10203040501.令各偏差變量為0，作出所有的約束直線x1x2050102045GHFEDCBAx1x205040302010

1020304050d4+d3-d2+d2-d1+d1-d4-d3+2.作圖表示偏差變量增加對約束直線的影響GHFEDCBAx1x205010246P1,P2的目標實現(xiàn)后，x1,x2的取值范圍為ABCD3.確定滿足第一優(yōu)先級目標集的最優(yōu)解空間（不考慮其他優(yōu)先級）4.轉(zhuǎn)到第k+1優(yōu)先級，求出其相應(yīng)的最優(yōu)解空間GHFEDCBAx1x205040302010

1020304050d4+d3-d2+d2-d1+d1-d4-d3+P1,P2的目標實現(xiàn)后，x1,x2的取值范圍為ABCD3.47P３目標要求，d3-權(quán)系數(shù)大于d4-,取d3-=0，

x1,x2的取值范圍為ABEF在ABEF中，只有

E點d4-取極小值。取E點為滿意解(24,26)5.令k=k+1反復(fù)執(zhí)行步驟（4），直到所有的優(yōu)先級均求解完畢。GHFEDCBAx1x205040302010

1020304050d4+d3-d2+d2-d1+d1-d4-d3+P３目標要求，d3-權(quán)系數(shù)大于d4-,取d3-=0，x148第10章動態(tài)規(guī)劃10.1多階段決策問題10.2多階段決策的有關(guān)概念10.3動態(tài)規(guī)劃的基本思想和基本方程10.4動態(tài)規(guī)劃模型的建立與求解10.5動態(tài)規(guī)劃應(yīng)用舉例

第10章動態(tài)規(guī)劃10.1多階段決策問題49

動態(tài)規(guī)劃所研究的對象是多階段決策問題。所謂多階段決策問題是指一類活動過程，它可以分為若干個相互聯(lián)系的階段，在每個階段都需要作出決策。這個決策不僅決定這一階段的效益，而且決定下一階段的初始狀態(tài)。每個階段的決策確定以后，就得到一個決策序列，稱為策略。多階段決策問題就是求一個策略，使各階段的效益的總和達到最優(yōu)。10.1多階段決策問題動態(tài)規(guī)劃所研究的對象是多階段決策問題。150在實際生產(chǎn)經(jīng)營活動中，存在著一類將過程劃分為若干個相互聯(lián)系的階段，而每個階段都需要做出決策，并且一個階段的決策確定后，常影響下一階段的決策，即多階段決策問題。在這類多階段決策問題中，整個問題的各個階段所確定的決策構(gòu)成一個決策序列，通稱為策略。對應(yīng)于一個策略，就有確定活動效果，且可用數(shù)量指標來衡量。因此多階段決策問題就需要在允許選擇的那些策略中選擇最優(yōu)策略，使在預(yù)定的標準下達到最好的效果。動態(tài)規(guī)劃是一種解決問題的思路，而不是一種算法。這一點與線性規(guī)劃不同，線性規(guī)劃是一種算法。在實際生產(chǎn)經(jīng)營活動中，存在著一類將過程劃分為51

【例10-1】生產(chǎn)與存儲問題某工廠每季度需供應(yīng)市場600，700，500和1200件產(chǎn)品，未銷售完的產(chǎn)品存入倉庫，存儲費為每件每季度1元，生產(chǎn)費用為件數(shù)的平方成正比，比例系數(shù)為0.005。現(xiàn)要制定生產(chǎn)計劃，在滿足市場需求的條件下，使一年的生產(chǎn)與存儲費用最少。按季度的順序分為4個階段，k=1,2,3,4設(shè)第k季生產(chǎn)的產(chǎn)品為uk件，

第k季初的庫存量為sk，

第k季的銷售量為qk

，則sk+1=sk+uk-qk假設(shè)年初和年底無存貨，即

s1=s5=0【例10-1】生產(chǎn)與存儲問題按季度的順序分為4個階段52全過程目標管理函數(shù)為：該問題是求最優(yōu)的生產(chǎn)決策序列，即全年中每季度的最優(yōu)生產(chǎn)量u1*,u2*,u3*,u4*，在滿足市場需求的條件下，使得一年的總費用最少。則該問題的數(shù)學(xué)模型為：全過程目標管理函數(shù)為：該問題是求最優(yōu)的生產(chǎn)決策序53【例10-2】最短路線問題。設(shè)有一輛汽車由A城到B城，中間可經(jīng)過v1到v8城市，各城市的交通路線及距離如圖所示，問應(yīng)選擇哪一條路線，可使總距離最短。Av285685547866924337131234v39v6Bv8v7v5v4v1【例10-2】最短路線問題。設(shè)有一輛汽車由A城到54這一問題看成是四個階段的決策問題，由A到(v1,v2,v3)中的點是第一階段；由(v1,v2,v3)中的點到(v4,v5,v6)中的點是第二階段；由(v4,v5,v6)中的點到(v7,v8)中的點是第二階段；由(v7,v8)中的一點到B是第四階段。要求在各個階段選取一個恰當(dāng)?shù)臎Q策，由這些決策組成的決策序列所決定的一條路線，其總路程最短。Av285685547866924337131234v39v6Bv8v7v5v4v1這一問題看成是四個階段的決策問題，由A到(v1,v2,v3)5510.2多階段決策的有關(guān)概念1.階段把所給問題的過程恰當(dāng)?shù)胤譃槿舾蓚€相互聯(lián)系的階段，以便按一定順序去求解。描述階段的變量稱為階段變量，用k表示。階段的劃分，一般是按時間和空間的自然特征來劃分?！纠?0-1】生產(chǎn)與存儲問題按自然時間分為4個階段（季度）K=1，2，3，4。【例10-2】最短路問題按空間的自然特征分為4個階段。年、月、路段10.2多階段決策的有關(guān)概念1.階段562.狀態(tài)狀態(tài)表示每個階段開始時所處的自然狀態(tài)或客觀條件，描述了問題過程的狀況，又稱為不可控因素。描述過程狀態(tài)的變量稱為狀態(tài)變量。用sk表示第k階段所處的狀態(tài)。狀態(tài)變量的取值有一定的允許集合或范圍，此集合稱為狀態(tài)允許集合。【例10-1】中狀態(tài)是每個階段開始時的庫存量，它既是前一階段決策的結(jié)果，又是后一階段決策的開始。通常一個階段有若干個狀態(tài)。構(gòu)成狀態(tài)集合?！纠?0-1】中s1=0，s5=0表示狀態(tài)變量s1，s5的值為0，而s2，s3，s4的取值可能有多種情況。2.狀態(tài)狀態(tài)表示每個階段開始時所處的自然57s1=A，s2=(v1,v2,v3)，s3=(v4,v5,v6)，s4=(v7,v8)狀態(tài)應(yīng)具有無后效性如果某階段狀態(tài)給定后，則在這個階段以后過程的發(fā)展不受這個階段以前各段狀態(tài)的影響；過程的過去歷史只能通過當(dāng)前的狀態(tài)去影響它未來的發(fā)展；構(gòu)造動態(tài)規(guī)劃模型時，要充分注意是否滿足無后效性的要求；如果狀態(tài)變量不能滿足無后效性的要求，應(yīng)適當(dāng)?shù)馗淖儬顟B(tài)的定義或規(guī)定方法。Av285685547866924337131234v39v6Bv8v7v5v4v1【例10-2】中s1=A，s2=(v1,v2,v3)，s3=(v4,v5,v58在實際問題中決策變量的取值往往在某一范圍之內(nèi)，此范圍稱為允許決策集合。常用Dk(sk)表示第k階段從狀態(tài)sk出發(fā)的允許決策集合。決策變量是狀態(tài)變量的函數(shù)。常用uk(sk)

表示第k階段當(dāng)狀態(tài)為sk時的決策變量。3.決策過程的某一階段、某個狀態(tài),可以做出不同的決定(選擇),決定下一階段的狀態(tài)，這種決定稱為決策。描述決策的變量，稱為決策變量?！纠?0-1】中，從第一階段的狀態(tài)s1=0出發(fā)，其允許決策集合為Dk(sk)={600，601，…，3000}【例10-2】中，從第二階段的狀態(tài)s2=v1出發(fā)，其允許決策集合為Dk(sk)={v4,v5,v6}。在實際問題中決策變量的取值往往在某一范圍之內(nèi)59

可供選擇的策略有一定范圍，此范圍稱為允許策略集合，用p表示。從允許策略集合中找出達到最優(yōu)效果的策略稱為最優(yōu)策略。

當(dāng)k=1時，此決策函數(shù)序列成為全過程的一個策略，簡稱策略，記為p1,n

(s1).即

4.策略按順序排列的決策組成的集合；

由第k

n(終止?fàn)顟B(tài))為止的過程，稱為原過程的后部子過程（k子過程）。

由每段的決策按順序排列組成的決策函數(shù)序列稱為k子過程策略，簡稱子策略，記為pk,n(sk)，即可供選擇的策略有一定范圍，此范圍稱為允許策略605.狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程是確定過程由一個狀態(tài)到另一個狀態(tài)的演變過程。本階段的狀態(tài)是上一階段狀態(tài)和上一階段決策的結(jié)果，對于本階段來講，狀態(tài)是已知的。如果給出第k階段狀態(tài)變量sk的值、該階段的決策變量uk一經(jīng)確定，第k+1階段狀態(tài)變量sk+1的值也就確定，其關(guān)系為：5.狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程是確定過程6112ks1u1s2u2s3skukSk+1能用動態(tài)規(guī)劃方法求解的多階段決策過程是一類特殊的多階段決策過程，即具有無后效性的多階段決策過程。圖示如下：【例10-1】中，狀態(tài)轉(zhuǎn)移方程為sk+1=sk+uk–qk其中k=1,2,3,4【例10-2】中，狀態(tài)轉(zhuǎn)移方程為sk+1=uk(sk)12ks1u1s2u2s3skukSk+162

6.指標函數(shù)和最優(yōu)值函數(shù)用來衡量所實現(xiàn)過程優(yōu)劣的一種數(shù)量指標，稱為指標函數(shù)；它分階段指標函數(shù)和過程指標函數(shù)。階段指標函數(shù)：僅是某一階段到下一階段的效益，用dk(sk,uk)表示，指在第k階段由狀態(tài)sk采取決策uk(sk)時的效益。Av285685547866924337131234v39v6Bv8v7v5v4v1【例10-2】中，d3(v4,v7)是指由v4出發(fā)，下一階段的決策是v7的兩點間的距離。即d3(v4,v7)

=3。6.指標函數(shù)和最優(yōu)值函數(shù)用來衡量63過程指標函數(shù)：它是定義在全過程和所有后部子過程上的數(shù)量函數(shù)，表示第k階段狀態(tài)為sk、采用策略pk,n(sk)時后部k子過程的效益值。動態(tài)規(guī)劃模型的指標函數(shù)，應(yīng)具有可分離性，并滿足遞推關(guān)系。

費用、成本、利潤、路長等。用Vk,n

表示之。即Vk,n可以表示為sk,uk,Vk+1,n的函數(shù)Vk,n=f(sk,uk,Vk+1,n)的函數(shù)。過程指標函數(shù)：它是定義在全過程和所有后部子過程上的數(shù)量函數(shù)64常見的指標函數(shù)的形式是：過程和它的任一子過程的指標是它所包含的各階段的指標和。即無后效性的結(jié)果。其中dj(sj

)

表示第

j階段的階段指標。這時上式可寫成過程和它的任一子過程的指標是它所包含的各階段的指標的乘積。即則可改寫成常見的指標函數(shù)的形式是：過程和它的任一子過程的指標是它所包含65

第k階段第n階段狀態(tài)sk

終止?fàn)顟B(tài)采取最優(yōu)策略所得到的指標函數(shù)值。最優(yōu)值函數(shù)：最優(yōu)指標函數(shù)是指從第k階段狀態(tài)采用最優(yōu)策略到過程終止時的最佳效益值，即指標函數(shù)的最優(yōu)值,記為fk(sk)可遞推即采取最優(yōu)策略所得到的指標函數(shù)值。最優(yōu)值函數(shù)：66

Av285685547866924337131234v39v6Bv8v7v5v4v1【例10-2】中，f3*(v4)是指從v4到B的最短距離。整個問題即為f1*(A)是指從A到B的最短距離。具有可分離性Av28568554786692433713123467解多階段決策過程問題，求出

最優(yōu)策略，即最優(yōu)決策序列f1(s1)

最優(yōu)軌線，即執(zhí)行最優(yōu)策略時的狀態(tài)序列

最優(yōu)目標函數(shù)值從k到終點最優(yōu)策略子策略的最優(yōu)目標函數(shù)值解多階段決策過程問題，求出最優(yōu)策略，即最優(yōu)決策序列68步步走近路，距離為：5+7+3+4=19。問題：是否一定最優(yōu)？Av285685547866924337131234v39v6Bv8v7v5v4v110.3動態(tài)規(guī)劃的基本思想和基本方程【例10-2】步步走近路步步走近路，距離為：5+7+3+4=19。Av285685569最優(yōu)化定理作為整個過程的最優(yōu)策略具有如下性質(zhì)：不管在此最優(yōu)策略上的某個狀態(tài)以前的狀態(tài)和決策如何，對該狀態(tài)而言，以后所有的決策必定構(gòu)成最優(yōu)子策略。就是說，最優(yōu)策略的任意子策略都是最優(yōu)的。

對最短路問題而言,從最短路上任一點到終點的部分道路（最短路上的子路）也一定是從該點到終點的最短路。

動態(tài)規(guī)劃的基本思想：逐段分析，逐點考慮并優(yōu)化后，逐步擴大范圍，直到找到最優(yōu)解。最優(yōu)化定理動態(tài)規(guī)劃的基本思想70如果一個問題的最短路在某階段通過Qs，則由點Qs出發(fā)到達終點的這條路線，對于從Qs出發(fā)到達終點的所有可能選擇的不同路線來說，必定是最短路線。QsAB要找到最短路，只要從最后一段開始，用逐步逆推的方法，求出各點到終點的最短路線，最后求得由起點到終點的最短路線。如果一個問題的最短路在某階段通過Qs，則由點71【例10-3】按照動態(tài)規(guī)劃的基本思想求解【例10-2】中最短路問題。Av285685547866924337131234v39v6Bv8v7v5v4v1【例10-3】按照動態(tài)規(guī)劃的基本思想求解【例10-2】中最短72具體計算前，先引進幾個符號：K——階段變量sk——狀態(tài)變量，表示第k階段所處的位置uk——決策變量，表示當(dāng)狀態(tài)為sk時，可選擇的下一狀態(tài)(這里有uk=Sk+l)dk(sk,uk)

——從sk到sk+1＝uk的距離fk*

(sk)——由sk到終點的最短距離。求解此問題的過程，是從最后一個階段開始計算，逐步倒退直到第一階段為止，即用逐步逆推的方法，該問題就是求f1*

(s1)。具體計算前，先引進幾個符號：73Av285685547866924337131234v39v6B