動態(tài)規(guī)劃Dynamicprogrammingppt課件

1、動 態(tài) 規(guī) 劃 (Dynamic programming)動態(tài)規(guī)劃的基本思想最短路徑問題資源分配問題背包問題生產(chǎn)計劃問題復合系統(tǒng)工作可靠性問題 動態(tài)規(guī)劃是用來解決多階段決策過程最優(yōu)化的一種數(shù)量方法。其特點在于，它可以把一個n 維決策問題變換為幾個一維最優(yōu)化問題，從而一個一個地去解決。 需指出：動態(tài)規(guī)劃是求解某類問題的一種方法，是考察問題的一種途徑，而不是一種算法。必須對具體問題進行具體分析，運用動態(tài)規(guī)劃的原理和方法，建立相應的模型，然后再用動態(tài)規(guī)劃方法去求解。即在系統(tǒng)發(fā)展的不同時刻（或階段）根據(jù)系統(tǒng)所處的狀態(tài)，不斷地做出決策；每個階段都要進行決策,目的是使整個過程的決策 達到最優(yōu)效果。動態(tài)決策

2、問題的特點：系統(tǒng)所處的狀態(tài)和時刻是進行決策的重要因素；找到不同時刻的最優(yōu)決策以及整個過程的最優(yōu)策略。多階段決策問題：在多階段決策過程中,系統(tǒng)的動態(tài)過程可以按照時間進程分為狀態(tài)相互聯(lián)系而又相互區(qū)別的各個階段；多階段決策問題的典型例子： 1 . 生產(chǎn)決策問題：企業(yè)在生產(chǎn)過程中，由于需求是隨時間變化的，因此企業(yè)為了獲得全年的最佳生產(chǎn)效益，就要在整個生產(chǎn)過程中逐月或逐季度地根據(jù)庫存和需求決定生產(chǎn)計劃。 2. 機器負荷分配問題：某種機器可以在高低兩種不同的負荷下進行生產(chǎn)。在高負荷下進行生產(chǎn)時，產(chǎn)品的年產(chǎn)量g和投入生產(chǎn)的機器數(shù)量u1的關(guān)系為g=g(u1)12n狀態(tài)決策狀態(tài)決策狀態(tài)狀態(tài)決策 這時，機器的年完

3、好率為a，即如果年初完好機器的數(shù)量為u，到年終完好的機器就為au, 0a1。 在低負荷下生產(chǎn)時，產(chǎn)品的年產(chǎn)量h和投入生產(chǎn)的機器數(shù)量u2的關(guān)系為 h=h(u2) 假定開始生產(chǎn)時完好的機器數(shù)量為s1。要求制定一個五年計劃，在每年開始時，決定如何重新分配完好的機器在兩種不同的負荷下生產(chǎn)的數(shù)量，使在五年內(nèi)產(chǎn)品的總產(chǎn)量達到最高。 相應的機器年完好率b, 0 b1。 3. 航天飛機飛行控制問題：由于航天飛機的運動的環(huán)境是不斷變化的，因此就要根據(jù)航天飛機飛行在不同環(huán)境中的情況，不斷地決定航天飛機的飛行方向和速度（狀態(tài)），使之能最省燃料和實現(xiàn)目的（如軟著落問題）。 4 .不包含時間因素的線性規(guī)劃、非線性規(guī)劃等

4、靜態(tài)決策問題（本質(zhì)上是一次決策問題）也可以適當?shù)匾腚A段的概念，作為多階段的決策問題用動態(tài)規(guī)劃方法來解決。 5 . 最短路問題：給定一個交通網(wǎng)絡圖如下，其中兩點之間的數(shù)字表示距離（或花費），試求從A點到G點的最短距離（總費用最?。?23456AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643 （一）、基本概念 1、階段： 把一個問題的過程，恰當?shù)胤譃槿舾蓚€相互聯(lián)系的階段，以便于按一定的次序去求解。 描述階段的變量稱為階段變量（k)。k=1,2 ,3, ，n階段的劃分，一般是根據(jù)時間和空間的自然特征來進行的，但要便于問題轉(zhuǎn)化

5、為多階段決策。2、狀態(tài)：表示每個階段開始所處的自然狀況或客觀條件。通常一個階段有若干個狀態(tài)，描述過程狀態(tài)的變量稱為狀態(tài)變量sk (表示第k階段的狀態(tài)變量 )。年、月、路段一個數(shù)、一組數(shù)、一個向量 狀態(tài)變量的取值有一定的允許集合或范圍，此集合稱為狀態(tài)允許集合S K =s1,s2, , s k ,。一、動態(tài)規(guī)劃的基本思想 3、決策：表示當過程處于某一階段的某個狀態(tài)時，可以作出不同的決定，從而確定下一階段的狀態(tài)，這種決定稱為決策。 描述決策的變量，稱為決策變量。 常用uk（sk）表示第k階段當狀態(tài)為sk時的決策變量。 決策變量是狀態(tài)變量的函數(shù)?？捎靡粋€數(shù)、一組數(shù)或一向量（多維情形）來描述。 在實際問

6、題中決策變量的取值往往在某一范圍之內(nèi)，此范圍稱為允許決策集合。 常用Dk（sk）表示第k階段從狀態(tài)sk出發(fā)的允許決策集合，顯然uk（sk）Dk（sk）。 4、多階段決策過程 可以在各個階段進行決策，去控制過程發(fā)展的多段過程；其發(fā)展是通過一系列的狀態(tài)轉(zhuǎn)移來實現(xiàn)的； 系統(tǒng)在某一階段的狀態(tài)轉(zhuǎn)移不但與系統(tǒng)的當前的狀態(tài)和決策有關(guān)，而且還與系統(tǒng)過去的歷史狀態(tài)和決策有關(guān)。圖示如下：狀態(tài)轉(zhuǎn)移方程是確定過程由一個狀態(tài)到另一個狀態(tài)的演變過程。如果第k階段狀態(tài)變量sk的值、該階段的決策變量一經(jīng)確定，第k+1階段狀態(tài)變量sk+1的值也就確定。其狀態(tài)轉(zhuǎn)移方程如下（一般形式）12ks1u1s2u2s3skuksk+1 能

7、用動態(tài)規(guī)劃方法求解的多階段決策過程是一類特殊的多階段決策過程，即具有無后效性的多階段決策過程。 如果狀態(tài)變量不能滿足無后效性的要求，應適當?shù)馗淖儬顟B(tài)的定義或規(guī)定方法。動態(tài)規(guī)劃中能處理的狀態(tài)轉(zhuǎn)移方程的形式。 狀態(tài)具有無后效性的多階段決策過程的狀態(tài)轉(zhuǎn)移方程如下無后效性(馬爾可夫性) 如果某階段狀態(tài)給定后，則在這個階段以后過程的發(fā)展不受這個階段以前各段狀態(tài)的影響； 過程的過去歷史只能通過當前的狀態(tài)去影響它未來的發(fā)展； 構(gòu)造動態(tài)規(guī)劃模型時，要充分注意是否滿足無后效性的要求；狀態(tài)變量要滿足無后效性的要求； 5、策略：相互連接的決策序列稱為一個策略。 從第k階段開始到第n階段結(jié)束稱為一個子策略。 Pk,n

8、 , 全策略 P1,n . 所有策略當中有最優(yōu)值的策略稱為最優(yōu)策略。 6、狀態(tài)轉(zhuǎn)移方程：是確定過程由一個狀態(tài)到另一個狀態(tài)的演變過程，描述了狀態(tài)轉(zhuǎn)移規(guī)律。 7、指標函數(shù)和最優(yōu)值函數(shù)：用來衡量所實現(xiàn)過程優(yōu)劣的一種數(shù)量指標，為指標函數(shù)。 階段指標函數(shù)： Vk (sk ,uk ) 表示第 k 階段位于sk 狀態(tài)、決策為 uk 的指標值。 策略指標函數(shù)：各決策序列指標值之和。（個別情況為乘積）指標函數(shù)的最優(yōu)值，稱為最優(yōu)值函數(shù)。在不同的問題中，指標函數(shù)的含義是不同的，它可能是距離、利潤、成本、產(chǎn)量或資源消耗等。 動態(tài)規(guī)劃模型的指標函數(shù)，應具有可分離性，并滿足遞推關(guān)系。小結(jié):方程 :狀態(tài)轉(zhuǎn)移方程概念 : 階

9、段變量k狀態(tài)變量sk決策變量uk;指標: 動態(tài)規(guī)劃本質(zhì)上是多階段決策過程; 效益指標函數(shù)形式: 和、積無后效性可遞推解多階段決策過程問題，求出 最優(yōu)策略，即最優(yōu)決策序列f1(s1) 最優(yōu)軌線，即執(zhí)行最優(yōu)策略時的狀態(tài)序列 最優(yōu)目標函數(shù)值從 k 到終點最優(yōu)策略子策略的最優(yōu)目標函數(shù)值 1、動態(tài)規(guī)劃方法的關(guān)鍵在于正確地寫出基本的遞推關(guān)系式和恰當?shù)倪吔鐥l件（簡稱基本方程）。要做到這一點，就必須將問題的過程分成幾個相互聯(lián)系的階段，恰當?shù)倪x取狀態(tài)變量和決策變量及定義最優(yōu)值函數(shù)，從而把一個大問題轉(zhuǎn)化成一組同類型的子問題，然后逐個求解。即從邊界條件開始，逐段遞推尋優(yōu)，在每一個子問題的求解中，均利用了它前面的子問

10、題的最優(yōu)化結(jié)果，依次進行，最后一個子問題所得的最優(yōu)解，就是整個問題的最優(yōu)解。（二）、動態(tài)規(guī)劃的基本思想 2、在多階段決策過程中，動態(tài)規(guī)劃方法是既把當前一段和未來一段分開，又把當前效益和未來效益結(jié)合起來考慮的一種最優(yōu)化方法。因此，每段決策的選取是從全局來考慮的，與該段的最優(yōu)選擇答案一般是不同的. 最優(yōu)化原理：作為整個過程的最優(yōu)策略具有這樣的性質(zhì)：無論過去的狀態(tài)和決策如何，相對于前面的決策所形成的狀態(tài)而言，余下的決策序列必然構(gòu)成最優(yōu)子策略?！币簿褪钦f，一個最優(yōu)策略的子策略也是最優(yōu)的。 3、在求整個問題的最優(yōu)策略時，由于初始狀態(tài)是已知的，而每段的決策都是該段狀態(tài)的函數(shù)，故最優(yōu)策略所經(jīng)過的各段狀態(tài)便可

11、逐段變換得到，從而確定了最優(yōu)路線。（三）、建立動態(tài)規(guī)劃模型的步驟 1、劃分階段k劃分階段是運用動態(tài)規(guī)劃求解多階段決策問題的第一步，在確定多階段特性后，按時間或空間先后順序，將過程劃分為若干相互聯(lián)系的階段。對于靜態(tài)問題要人為地賦予“時間”概念，以便劃分階段。 2、正確選擇狀態(tài)變量sk選擇變量既要能確切描述過程演變又要滿足無后效性，而且各階段狀態(tài)變量的取值能夠確定。一般地，狀態(tài)變量的選擇是從過程演變的特點中尋找。 3、確定決策變量uk(sk)及允許決策集合Dk(sk)通常選擇所求解問題的關(guān)鍵變量作為決策變量，同時要給出決策變量的取值范圍，即確定允許決策集合。 4、確定狀態(tài)轉(zhuǎn)移方程根據(jù)k 階段狀態(tài)變

12、量和決策變量，寫出k+1階段狀態(tài)變量，狀態(tài)轉(zhuǎn)移方程應當具有遞推關(guān)系。 sk+1 =Tk (sk ,uk ) Tk 函數(shù)關(guān)系 5、確定階段指標函數(shù)和最優(yōu)指標函數(shù)，建立動態(tài)規(guī)劃基本方程 階段指標函數(shù)是指第k 階段的收益，最優(yōu)指標函數(shù)是指從第k 階段狀態(tài)出發(fā)到第n 階段末所獲得收益的最優(yōu)值，最后寫出動態(tài)規(guī)劃基本方程。f k (sk ) = Opt Vk (sk ,uk ) + f k+1 (s k+1) fn+1 (s n+1 ) = 0 Opt 最優(yōu)化（max,min） 以上五步是建立動態(tài)規(guī)劃數(shù)學模型的一般步驟。由于動態(tài)規(guī)劃模型與線性規(guī)劃模型不同，動態(tài)規(guī)劃模型沒有統(tǒng)一的模式，建模時必須根據(jù)具體問題

13、具體分析，只有通過不斷實踐總結(jié)，才能較好掌握建模方法與技巧。 f1(s1) 是整個問題的最優(yōu)策略，最優(yōu)值。 f k(sk) 表示從第k階段（狀態(tài)sk）到終點的最優(yōu)指標值。（距離、利潤、成本等） 例一、從A 地到D 地要鋪設一條煤氣管道,其中需經(jīng)過兩級中間站，兩點之間的連線上的數(shù)字表示距離，如圖所示。問應該選擇什么路線，使總距離最短？ AB1B2C1C2C3D24333321114二、最短路徑問題 解：整個計算過程分三個階段，從最后一個階段開始。 第三階段（C D）： C 有三條路線到終點D 。 AB1B2C1C2C3D24333321114DC1C2C3顯然有 f3 (C1 ) = 1 ； f

14、3(C2 ) = 3 ； f3 (C3 ) = 4 d( B1,C1 ) + f3 (C1 ) 3+1 f2 ( B1 ) = min d( B1,C2 ) + f3 (C2 ) = min 3+3 d( B1,C3 ) + f3 (C3 ) 1+4 4 = min 6 = 4 5第二階段（B C）： B 到C 有六條路線。AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路線為B1C1 D) d( B2,C1 ) + f3 (C1 ) 2+1 f2 ( B2 ) = min d( B2,C2 ) + f3 (C2 ) = min 3+3 d( B2,C3 ) + f3

15、 (C3 ) 1+4 3 = min 6 = 3 5AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路線為B2C1 D)第一階段（ A B ）： A 到B 有二條路線。 f1(A)1 = d(A, B1 ) f2 ( B1 ) 246 f1 (A)2 = d(A, B2 ) f2 ( B2 ) 437 f1 (A) = min = min6,7=6d(A, B1 ) f2 ( B1 )d(A, B2 ) f2 ( B2 )(最短路線為AB1C1 D)AB1B2C1C2C3D24333321114DC1C2C3B1B2AAB1B2C1C2C3D24333321114DC

16、1C2C3B1B2A最短路線為 AB1C1 D 路長為 6三、非線性規(guī)劃問題【例7-4】 用動態(tài)規(guī)劃方法解下列非線性規(guī)劃問題 解： 解決這一類靜態(tài)規(guī)劃問題，需要人為地賦予時間概念，從而將該問題轉(zhuǎn)化為多階段決策過程。按問題的變量個數(shù)劃分階段，把它看作一個三階段決策問題，k=1，2，3設狀態(tài)變量為s1，s2，s3，s4并記s1c取問題中的變量x1，x2，x3為決策變量 狀態(tài)轉(zhuǎn)移方程為：s3=x3s3+x2=s2s2+x1=s1c允許決策集合為：x3=s30 x2s20 x1s1各階段指標函數(shù)為：v1（x1）=x1v2（x2）=x22v3（x3）=x3，各指標函數(shù)以乘積方式結(jié)合，最優(yōu)指標函數(shù)fk（s

17、k）表示從第k階段初始狀態(tài)sk出發(fā)到第3階段所得到的最大值，則動態(tài)規(guī)劃基本方程為： 用逆序解法由后向前依次求解：k=3時，x3*=s3 k=2時，令h2（s2，x2）=x22（s2x2）用經(jīng)典解析法求極值點：解得： x2=0（舍） 所以 是極大值點。 k=1時， 令解得：x1=s1（舍） 所以 是極大值點。 由于s1未知，所以對s1再求極值，顯然s1=c時，f1（s1）取得最大值 反向追蹤得各階段最優(yōu)決策及最優(yōu)值： s1=c所以最優(yōu)解為： 一般地，如果階段指標函數(shù)vk（sk，uk）是線性函數(shù)或凸函數(shù)時，最優(yōu)指標函數(shù)fk（sk）的表達式比較容易得到，但是當vk（sk，uk）不具備上述特性時，最優(yōu)

18、指標函數(shù)fk（sk）的表達式不易得到，就需要采用數(shù)值法，即對連續(xù)變量進行離散化處理，再分散求解。例如靜態(tài)規(guī)劃模型其動態(tài)規(guī)劃基本方程為：狀態(tài)轉(zhuǎn)移方程為sk+1=skxks1=a狀態(tài)變量sk及決策變量xk都是連續(xù)變量，對其進行離散化處理，具體做法是：1. 對區(qū)間0，a進行分割，分割數(shù)m= ，其中是分割后的小區(qū)間的長度，其大小可以根據(jù)所求解問題要求的精度及計算機運算能力而定，分割點為0，2，m= a。2. 規(guī)定狀態(tài)變量sk及決策變量xk僅在離散點0，2，m處取值，最優(yōu)指標函數(shù)fk（sk）也定義在這些離散點上。動態(tài)規(guī)劃基本方程可以寫為：其中sk=q，xk=p。3. 由后向前逐段遞推，直至求出整個過程最

19、優(yōu)解。 【例7-5】解 按變量個數(shù)將原問題分為三個階段，階段變量k=1，2，3；選擇xk為決策變量；狀態(tài)變量sk表示第k階段至第3階段決策變量之和；取小區(qū)間長度=1，小區(qū)間數(shù)目m=6/1=6，狀態(tài)變量sk的取值點為：狀態(tài)轉(zhuǎn)移方程：sk+1=skxk；允許決策集合：Dk（sk）=xk|0 xkskk=1，2，3xk，sk均在分割點上取值； 階段指標函數(shù)分別為：g1（x1）=x12g2（x2）=x2g3（x3）=x33，最優(yōu)指標函數(shù)fk（sk）表示從第k階段狀態(tài)sk出發(fā)到第3階段所得到的最大值，動態(tài)規(guī)劃的基本方程為： k=3時， s3及x3取值點較多，計算結(jié)果以表格形式給出，見表7-1所示。 表7

20、1取值k=2時，計算結(jié)果見表7-2 k=1時，其中s1=6，計算結(jié)果見表7-3所示。由表7-3知，x1*=2，s1=6，則s2= s1x1*=62=4，查表7-2得：x2*=1，則s3= s2x2*=41=3，查表7-1得：x3*=3，所以最優(yōu)解為：x1*=2，x2*=1，x3*=3，f1(s1)=108。本例也可用經(jīng)典解析法求得各段的極值，讀者可自行求解，二者結(jié)論完全相同。需要指出的是當連續(xù)變量離散化處理以后，由于狀態(tài)變量和決策變量只在給定的離散點上取值，故有可能漏掉最優(yōu)解，因此需要慎重選擇參數(shù)m與。 資源分配問題就是將一定數(shù)量的一種或若干種資源（原材料、資金、設備等）合理分配給若干使用者，

21、使得資源分配后總結(jié)果最優(yōu)。一種資源的分配問題稱為一維資源分配問題，兩種資源的分配問題稱為二維資源分配問題。 四、資源分配問題假設有一種資源，數(shù)量為a，將其分配給n個使用者，分配給第i個使用者數(shù)量xi時，相應的收益為gi（xi），問如何分配使得總收入最大？這就是一維資源分配問題，該問題的數(shù)學模型為：這是一個靜態(tài)規(guī)劃問題，應用動態(tài)規(guī)劃方法求解時人為賦予時間概念，將其看作是一個多階段決策問題。 按變量個數(shù)劃分階段，k=1，2，n；設決策變量uk=xk，表示分配給第k個使用者的資源數(shù)量；設狀態(tài)變量為sk，表示分配給第k個至第n個使用者的總資源數(shù)量；狀態(tài)轉(zhuǎn)移方程：sk+1=skxk，其中s1=a；允許決

22、策集合：Dk（sk）=xk|0 xksk階段指標函數(shù)：vk（sk，uk）=gk（xk）表示分配給第k個使用者數(shù)量xk時的收益；最優(yōu)指標函數(shù)fk（sk）表示以數(shù)量sk的資源分配給第k個至第n個使用者所得到的最大收益，則動態(tài)規(guī)劃基本方程為：由后向前逐段遞推，f1（a）即為所求問題的最大收益?！纠?-6】 某公司打算在3個不同的地區(qū)設置4個銷售點，根據(jù)市場部門估計，在不同地區(qū)設置不同數(shù)量的銷售點每月可得到的利潤如表7-4所示。試問在各地區(qū)如何設置銷售點可使每月總利潤最大。表7-4 解 如前所述，建立動態(tài)規(guī)劃數(shù)學模型：將問題分為3個階段，k=1，2，3；決策變量xk表示分配給第k個地區(qū)的銷售點數(shù)；狀態(tài)

23、變量為sk表示分配給第k個至第3個地區(qū)的銷售點總數(shù)；狀態(tài)轉(zhuǎn)移方程：sk+1=skxk，其中s1=4；允許決策集合：Dk（sk）=xk|0 xksk階段指標函數(shù)：gk（xk）表示xk個銷售點分配給第k個地區(qū)所獲得的利潤；最優(yōu)指標函數(shù)fk（sk）表示將數(shù)量為sk的銷售點分配給第k個至第3個地區(qū)所得到的最大利潤，動態(tài)規(guī)劃基本方程為： k=3時，數(shù)值計算如下表7-5表7-5 k=2時，計算結(jié)果見下表7-6表7-6 k=1時，k=1時，只有s1=4的情況。計算結(jié)果如表7-7所示。所以最優(yōu)解為：x1*=2，x2*=1，x3*=1，f1(4)=47，即在第1個地區(qū)設置2個銷售點，第2個地區(qū)設置1個銷售點，第

24、3個地區(qū)設置1個銷售點，每月可獲利潤47。表7-7 【例7-7】機器負荷問題某工廠有100臺機器，擬分四期使用，每一期都可在高、低兩種不同負荷下進行生產(chǎn)。若把x臺機器投入高負荷下進行生產(chǎn)，則在本期結(jié)束時將有1/3x臺機器損壞報廢；余下的機器全部投入低負荷下進行生產(chǎn)，則在期末有1/10的機器報廢。如果高負荷下生產(chǎn)時每臺機器可獲利潤為10，低負荷下生產(chǎn)時每臺機器可獲利潤為7，問怎樣分配機器使四期的總利潤最大？解 將問題按周期分為4個階段，k=1，2，3，4；狀態(tài)變量sk表示第k階段初完好的機器數(shù)，s1=100，0sk100；決策變量xk表示第k階段投入高負荷下生產(chǎn)的機器數(shù)，則skxk表示第k階段投

25、入低負荷下生產(chǎn)的機器數(shù)；允許決策集合：Dk（sk）=xk|0 xksk狀態(tài)轉(zhuǎn)移方程：sk+1=Tk（sk，xk），即第k+1階段初擁有的完好機器數(shù)sk+1為： 階段指標函數(shù)：vk（sk，xk）=10 xk+7（skxk）表示第k階段所獲得的利潤；最優(yōu)指標函數(shù)fk（sk）表示從第k階段初完好機器數(shù)為sk至第四階段的最大利潤，動態(tài)規(guī)劃基本方程為： k=4時， x4*=s4 k=3時， x3*=s3 k=2時， x2*=0 k=1時， x1*=0因為s1=100，所以f1（100）=2680，逆向追蹤得：s1=100，x1*=0 x2*=0 x3*=s3=81 x4*=s4=54即，第1，2期把全部

26、完好機器投入低負荷下生產(chǎn)，第3，4期把全部完好機器投入高負荷下生產(chǎn)所得利潤最大。 五、生產(chǎn)計劃問題 在企業(yè)生產(chǎn)經(jīng)營活動中，經(jīng)常會遇到如何合理安排生產(chǎn)、庫存及銷售計劃，使總效益最高的問題，這一類問題統(tǒng)稱為生產(chǎn)計劃問題。 【例7-8】 （生產(chǎn)庫存問題）某工廠要對一種產(chǎn)品制定今后四個時期的生產(chǎn)計劃，據(jù)估計在今后四個時期內(nèi)，市場對該產(chǎn)品的需求量分別為2，3，2，4單位，假設每批產(chǎn)品固定成本為3千元，若不生產(chǎn)為0，每單位產(chǎn)品成本為1千元，每個時期最大生產(chǎn)能力不超過6個單位，每期期末未出售產(chǎn)品，每單位需付存貯費0.5千元，假定第1期初和第4期末庫存量均為0，問該廠如何安排生產(chǎn)與庫存，可在滿足市場需求的前提

27、下總成本最小。解 以每個時期作為一個階段，該問題分為4個階段，k=1，2，3，4； 決策變量xk表示第k階段生產(chǎn)的產(chǎn)品數(shù)； 狀態(tài)變量sk表示第k階段初的庫存量； 以dk表示第k階段的需求，則狀態(tài)轉(zhuǎn)移方程：sk+1=sk+xkdk k=4，3，2，1 由于期初及期末庫存為0，所以s1=0，s5=0； 允許決策集合Dk（sk）的確定： 當skdk時，xk可以為0，當skdk時，至少應生產(chǎn)dksk，故xk的下限為max（0，dksk）；每期最大生產(chǎn)能力為6，xk最大不超過6，由于期末庫存為0，xk還應小于本期至4期需求之和減去本期的庫存量 ，所以xk的上限為min（ ，6），故有：Dk（sk）=xk

28、| max（0,dksk）xkmin（ ,6） 階段指標函數(shù)rk（sk，xk）表示第k期的生產(chǎn)費用與存貯費用之和：最優(yōu)指標函數(shù)fk（sk）表示第k期庫存為sk到第4期末的生產(chǎn)與存貯最低費用，動態(tài)規(guī)劃基本方程為：先求出各狀態(tài)允許狀態(tài)集合及允許決策集合，如表7-8所示。表7-8k=4時，計算結(jié)果見表7-9所示。表7-9 k=3時，計算結(jié)果如下表：k=2時，計算結(jié)果如下表k=1時，計算結(jié)果見表7-12所示 逆向追蹤可得：x1*=5，s2=3，x2*=0，s3=0，x3*=6，s4=4，x4*=0，即第1時期生產(chǎn)5個單位，第3時期生產(chǎn)6個單位，第2，4時期不生產(chǎn)，可使總費用最小，最小費用為20.5千元

29、。 【例7-9】 （庫存銷售問題） 設某公司計劃在1至4月份從事某種商品經(jīng)營。已知倉庫最多可存儲600件這種商品，已知1月初存貨200件，根據(jù)預測知1至4月份各月的單位購貨成本及銷售價格如表7-13所示，每月只能銷售本月初的庫存，當月進貨供以后各月銷售，問如何安排進貨量和銷售量，使該公司四個月獲得利潤最大（假設四月底庫存為零）。表7-13 解 按月份劃分階段，k=1，2，3，4；狀態(tài)變量sk表示第k月初的庫存量，s1=200，s5=0；決策變量 xk表示第k月售出的貨物數(shù)量，yk表示第k月購進的貨物數(shù)量；狀態(tài)轉(zhuǎn)移方程：sk+1=sk+ykxk；允許決策集合：0 xksk，0yk600（skxk

30、）；階段指標函數(shù)為：pkxkckyk表示k月份的利潤，其中pk為第k月份的單位銷售價格，ck為第k月份的單位購貨成本；最優(yōu)指標函數(shù)fk（sk）表示第k月初庫存為sk時從第k月至第4月末的最大利潤，則動態(tài)規(guī)劃基本方程為： k=4時，x4*=s4y4*=0k=3時， 為求出使44s35x3+4y3最大的x3，y3，須求解線性規(guī)劃問題： 只有兩個變量x3，y3，可用圖解法也可用單純形法求解，圖解法求解示意圖如圖7-5所示：在A點處取得最優(yōu)解，x3*=0，y3*=600s3，f3（s3）=40s3+2400 As3600y3x30600s3圖7-5k=2時，類似地求得：x2*=s2，y2*=600，f

31、2（s2）=42s2+3600k=1時，類似地求得：x1*=s1，y1*=600， f1（s1）=45s1+4800=13800 逆向追蹤得各月最優(yōu)購貨量及銷售量：x1*=s1=200y1*=600；x2*=s2=s1+ y1*x1*=600y2*=600；x3*=0y3*=600s3=600（s2+ y2*x2*）=0 x4*=s4=（s3+ y3*x3*）=600y4*=0即1月份銷售200件，進貨600件，2月份銷售600件，進貨600件，3月份銷售量及進貨量均為0，4月份銷售600件，不進貨，可獲得最大總利潤13800。 六、背包問題 有人攜帶背包上山，其可攜帶物品的重量限度為a公斤，

32、現(xiàn)有n種物品可供選擇，設第i種物品的單件重量為ai公斤，其在上山過程中的價值是攜帶數(shù)量xi的函數(shù)ci（xi），問應如何安排攜帶各種物品的數(shù)量，使總價值最大。這就是背包問題，類似的貨物裝載問題，下料問題都等同于背包問題。背包問題的數(shù)學模型為：下面用動態(tài)規(guī)劃方法求解：按照裝入物品的種類劃分階段，k=1，2，n；狀態(tài)變量sk表示裝入第k種至第n種物品的總重量；決策變量xk表示裝入第k種物品的件數(shù)；狀態(tài)轉(zhuǎn)移方程為：sk+1=skakxk允許決策集合為：其中表示不超過的最大整數(shù)； 階段指標函數(shù)ck（xk）表示第k階段裝入第k種商品xk件時的價值；最優(yōu)指標函數(shù)fk（sk）表示第k階段裝入物品總重量為sk時的最大價值，動態(tài)規(guī)劃基本方程為：【例7-10】 某工廠生產(chǎn)三種產(chǎn)品，各產(chǎn)品重量與利潤關(guān)系如表7-14所示，現(xiàn)將此三種產(chǎn)品運往市場銷售，運輸能力總重量不超過6噸，問如何安排運輸使總利潤最大？表7-14種類123單位重量（噸）234單位利潤（元）80130180解 設xi為裝載第i種貨物的件數(shù)，i=1，2，3，該問題數(shù)學模型為：按前述方法建立動態(tài)規(guī)劃模型；k=3時，計算結(jié)果如表7-15所示。k=2時，計算結(jié)果如表7-16所示。表7-16k=1時，計算結(jié)果如表7-17所示。表7-17反向追蹤得最優(yōu)方案：