4第四章動(dòng)態(tài)規(guī)劃

1、第四章 動(dòng)態(tài)規(guī)劃§ 1 引言1.1 動(dòng)態(tài)規(guī)劃的發(fā)展及研究?jī)?nèi)容動(dòng)態(tài)規(guī)劃 （ dynamic programming ） 是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過(guò)程（ decisionprocess） 最優(yōu)化的數(shù)學(xué)方法。20 世紀(jì) 50 年代初 R. E. Bellman 等人在研究多階段決策過(guò)程 （multistep decision process）的優(yōu)化問(wèn)題時(shí)，提出了著名的最優(yōu)性原理（principle ofoptimality ） ，把多階段過(guò)程轉(zhuǎn)化為一系列單階段問(wèn)題，逐個(gè)求解，創(chuàng)立了解決這類過(guò)程優(yōu)化問(wèn)題的新方法動(dòng)態(tài)規(guī)劃。1957 年出版了他的名著Dynamic Programming

2、，這是該領(lǐng)域的第一本著作。動(dòng)態(tài)規(guī)劃問(wèn)世以來(lái)，在經(jīng)濟(jì)管理、生產(chǎn)調(diào)度、工程技術(shù)和最優(yōu)控制等方面得到了廣泛的應(yīng)用。例如最短路線、庫(kù)存管理、資源分配、設(shè)備更新、排序、裝載等問(wèn)題，用動(dòng)態(tài)規(guī)劃方法比用其它方法求解更為方便。雖然動(dòng)態(tài)規(guī)劃主要用于求解以時(shí)間劃分階段的動(dòng)態(tài)過(guò)程的優(yōu)化問(wèn)題，但是一些與時(shí)間無(wú)關(guān)的靜態(tài)規(guī)劃（如線性規(guī)劃、非線性規(guī)劃），只要人為地引進(jìn)時(shí)間因素，把它視為多階段決策過(guò)程，也可以用動(dòng)態(tài)規(guī)劃方法方便地求解。應(yīng)指出，動(dòng)態(tài)規(guī)劃是求解某類問(wèn)題的一種方法，是考察問(wèn)題的一種途徑，而不是一種特殊算法（如線性規(guī)劃是一種算法）。因而，它不象線性規(guī)劃那樣有一個(gè)標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確定義的一組規(guī)則，而必須對(duì)具體問(wèn)題進(jìn)

3、行具體分析處理。因此， 在學(xué)習(xí)時(shí)， 除了要對(duì)基本概念和方法正確理解外，應(yīng)以豐富的想象力去建立模型，用創(chuàng)造性的技巧去求解。例 1 最短路線問(wèn)題下面是一個(gè)線路網(wǎng)，連線上的數(shù)字表示兩點(diǎn)之間的距離（或費(fèi)用）。 試尋求一條由A到 G 距離最短（或費(fèi)用最?。┑穆肪€。例 2 生產(chǎn)計(jì)劃問(wèn)題工廠生產(chǎn)某種產(chǎn)品，每單位（千件）的成本為1（千元），每次開(kāi)工的固定成本為3（千元） ，工廠每季度的最大生產(chǎn)能力為6（千件）。經(jīng)調(diào)查，市場(chǎng)對(duì)該產(chǎn)品的需求量第一、二、三、四季度分別為2， 3， 2， 4（千件）。如果工廠在第一、二季度將全年的需求都生產(chǎn)出來(lái)，自然可以降低成本（少付固定成本費(fèi)），但是對(duì)于第三、四季度才能上市的產(chǎn)品需

4、付存儲(chǔ)費(fèi)，每季每千件的存儲(chǔ)費(fèi)為0.5（千元）。 還規(guī)定年初和年末這種產(chǎn)品均無(wú)庫(kù)存。試制定一個(gè)生產(chǎn)計(jì)劃，即安排每個(gè)季度的產(chǎn)量，使一年的總費(fèi)用（生產(chǎn)成本和存儲(chǔ)費(fèi)）最少。1.2 決策過(guò)程的分類根據(jù)過(guò)程的時(shí)間變量是離散的還是連續(xù)的，分為離散時(shí)間決策過(guò)程（discrete-timedecision process）和連續(xù)時(shí)間決策過(guò)程（continuous-time decision process ） ；根據(jù)過(guò)程的演變是確定的還是隨機(jī)的，分為確定性決策過(guò)程（deterministic decision process）和隨-41-機(jī)性決策過(guò)程( stochastic decision process)

5、， 其中應(yīng)用最廣的是確定性多階段決策過(guò)程。§ 2 基本概念、基本方程和計(jì)算方法2.1 動(dòng)態(tài)規(guī)劃的基本概念和基本方程一個(gè)多階段決策過(guò)程最優(yōu)化問(wèn)題的動(dòng)態(tài)規(guī)劃模型通常包含以下要素。2.1.1 階段階段(step)是對(duì)整個(gè)過(guò)程的自然劃分。通常根據(jù)時(shí)間順序或空間順序特征來(lái)劃分階段， 以便按階段的次序解優(yōu)化問(wèn)題。階段變量一般用k 1,2, ,n表示。 在例 1 中由 A出發(fā)為 k 1 ，由Bi (i 1,2) 出發(fā)為 k 2 ，依此下去從Fi (i 1,2) 出發(fā)為 k 6，共n 6個(gè)階段。在例2 中按照第一、二、三、四季度分為k 1,2,3,4，共四個(gè)階段。2.1.2 狀態(tài)狀態(tài)(state)表

6、示每個(gè)階段開(kāi)始時(shí)過(guò)程所處的自然狀況。它應(yīng)能描述過(guò)程的特征并且無(wú)后效性，即當(dāng)某階段的狀態(tài)變量給定時(shí)，這個(gè)階段以后過(guò)程的演變與該階段以前各階段的狀態(tài)無(wú)關(guān)。通常還要求狀態(tài)是直接或間接可以觀測(cè)的。描述狀態(tài)的變量稱狀態(tài)變量( state variable) 。 變量允許取值的范圍稱允許狀態(tài)集合(set of admissible states)。用xk 表示第k 階段的狀態(tài)變量，它可以是一個(gè)數(shù)或一個(gè)向量。用 X k 表示第 k 階段的允許狀態(tài)集合。在例1 中x2 可取B1, B2 ，或?qū)?Bi 定義為i(i 1,2)，則x21 或 2，而X21,2。n 個(gè)階段的決策過(guò)程有n 1 個(gè)狀態(tài)變量，xn 1 表

7、示xn 演變的結(jié)果。在例 1 中 x7 取G ，或定義為1 ，即x71 。根據(jù)過(guò)程演變的具體情況，狀態(tài)變量可以是離散的或連續(xù)的。為了計(jì)算的方便有時(shí)將連續(xù)變量離散化；為了分析的方便有時(shí)又將離散變量視為連續(xù)的。狀態(tài)變量簡(jiǎn)稱為狀態(tài)。2.1.3 決策當(dāng)一個(gè)階段的狀態(tài)確定后，可以作出各種選擇從而演變到下一階段的某個(gè)狀態(tài)，這種選擇手段稱為決策(decision) ，在最優(yōu)控制問(wèn)題中也稱為控制(control ) 。描述決策的變量稱決策變量(decision variable) ，變量允許取值的范圍稱允許決策集合( set of admissible decisions) 。用uk(xk) 表示第k 階段處

8、于狀態(tài)xk 時(shí)的決策變量，它是xk 的函數(shù)，用 Uk(xk) 表示xk的允許決策集合。在例 1 中u2(B1) 可取C1,C2 或C3，可記作 u2(1)1,2,3，而U2(1) 1,2,3。決策變量簡(jiǎn)稱決策。2.1.4 策略決策組成的序列稱為策略(policy ) 。由初始狀態(tài)x1 開(kāi)始的全過(guò)程的策略記作p1n(x1)，即p1n(x1) u1(x1),u2(x2),un(xn) .由第 k 階段的狀態(tài)xk 開(kāi)始到終止?fàn)顟B(tài)的后部子過(guò)程的策略記作pkn(xk) ，即pkn(xk)uk(xk), ,un(xn)， k 1,2, ,n 1.類似地，由第k 到第 j 階段的子過(guò)程的策略記作pkj(xk

9、) uk(xk), ,uj (xj) .可供選擇的策略有一定的范圍，稱為允許策略集合(set of admissible policies) ，用-41-P1n(x1),Pkn(xk),Pkj(xk)表示。2.1.5 . 狀態(tài)轉(zhuǎn)移方程在確定性過(guò)程中，一旦某階段的狀態(tài)和決策為已知，下階段的狀態(tài)便完全確定。用狀態(tài)轉(zhuǎn)移方程(equation of state transition)表示這種演變規(guī)律，寫(xiě)作xk 1Tk(xk,uk),k 1,2,n.( 1)在例 1 中狀態(tài)轉(zhuǎn)移方程為xk 1uk(xk) 。2.1.6 . 指標(biāo)函數(shù)和最優(yōu)值函數(shù)指標(biāo)函數(shù)(objective function) 是衡量過(guò)程優(yōu)

10、劣的數(shù)量指標(biāo)，它是定義在全過(guò)程和所有后部子過(guò)程上的數(shù)量函數(shù)，用Vk,n(xk ,uk, xk 1 , ,xn 1) 表示， k 1,2, ,n 。指標(biāo)函數(shù)應(yīng)具有可分離性，即Vk 可表為xk,uk ,Vk 1 的函數(shù)，記為k,nk k k 1,nVk,n (xk ,uk , xk 1 , ,xn 1 )k (xk ,uk ,Vk 1,n (xk 1,u k 1 ,xn 1 ) 并且函數(shù)k 對(duì)于變量 Vk 1, n是嚴(yán)格單調(diào)的。過(guò)程在第j 階段的階段指標(biāo)取決于狀態(tài)xj 和決策uj ，用vj (xj,uj) 表示。指標(biāo)函數(shù)由 vj ( j 1,2, ,n) 組成，常見(jiàn)的形式有：階段指標(biāo)之和，即nVk

11、,n(xk,uk, xk 1,xn 1)vj (xj ,uj)，jk階段指標(biāo)之積，即nVk,n (xk ,uk , xk 1,xn 1 )vj (xj ,u j ) ，jk階段指標(biāo)之極大(或極小)，即Vk,n(xk,uk, xk 1, ,xn 1) max(min)vj(xj,uj). kjn這些形式下第k 到第 j 階段子過(guò)程的指標(biāo)函數(shù)為Vk,j (xk,uk, xj 1)。根據(jù)狀態(tài)轉(zhuǎn)移方程指標(biāo)函數(shù)Vk ,n 還可以表示為狀態(tài)xk 和策略pkn 的函數(shù)，即Vk,n(xk , pkn)。 在 xk 給定時(shí)指標(biāo)函數(shù)Vk,n對(duì)pkn的最優(yōu)值稱為最優(yōu)值函數(shù)( optimal valuefunctio

12、n ) ，記為fk (xk ) ，即fk (xk) opt Vk,n(xk, pkn)，p kn Pkn (xk )其中 opt可根據(jù)具體情況取max或 min 。2.1.7 最優(yōu)策略和最優(yōu)軌線使指標(biāo)函數(shù)Vk, n達(dá)到最優(yōu)值的策略是從k 開(kāi)始的后部子過(guò)程的最優(yōu)策略，記作*pknuk, , un 。 p1n是全過(guò)程的最優(yōu)策略，簡(jiǎn)稱最優(yōu)策略(optimal policy ) 。從初始狀 態(tài)x1 ( x1 ) 出 發(fā) ， 過(guò) 程 按 照p1n 和 狀 態(tài) 轉(zhuǎn) 移 方 程 演 變 所 經(jīng) 歷 的 狀 態(tài) 序 列*x1 ,x2,xn 1 稱最優(yōu)軌線(optimal trajectory ) 。2.1.8

13、 遞歸方程如下方程稱為遞歸方程fn 1(xn 1) 0或 1fk(xk )opt vk(xk,uk )fk 1(xk 1), k n, ,1( 2)uk Uk(xk)在上述方程中，當(dāng)為加法時(shí)取fn 1(xk 1) 0；當(dāng) 為乘法時(shí)，取fn 1(xk 1) 1 。動(dòng)態(tài)規(guī)劃遞歸方程是動(dòng)態(tài)規(guī)劃的最優(yōu)性原理的基礎(chǔ)，即： 最優(yōu)策略的子策略，構(gòu)成最優(yōu)子策略。用狀態(tài)轉(zhuǎn)移方程( 1)和遞歸方程(2)求解動(dòng)態(tài)規(guī)劃的過(guò)程，是由k n 1 逆推至 k 1，故這種解法稱為逆序解法。當(dāng)然，對(duì)某些動(dòng)態(tài)規(guī)劃問(wèn)題，也可采用順序解法。這時(shí)，狀態(tài)轉(zhuǎn)移方程和遞歸方程分別為：xkTkr(xk 1,uk), k 1, ,nf0(x1)

14、0或 1fk(xk 1)opt vk(xk 1,uk) fk 1(xk), k 1, ,nu k U kr 1 ( xk 1 )縱上所述，如果一個(gè)問(wèn)題能用動(dòng)態(tài)規(guī)劃方法求解，那么，我們可以按下列步驟，首先建立起動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型：(i )將過(guò)程劃分成恰當(dāng)?shù)碾A段。(ii)正確選擇狀態(tài)變量xk ，使它既能描述過(guò)程的狀態(tài)，又滿足無(wú)后效性，同時(shí)確定允許狀態(tài)集合Xk。( iii )選擇決策變量uk ，確定允許決策集合Uk(xk) 。( iv)寫(xiě)出狀態(tài)轉(zhuǎn)移方程。( v)確定階段指標(biāo)vk(xk,uk) 及指標(biāo)函數(shù)Vkn 的形式 (階段指標(biāo)之和，階段指標(biāo)之積，階段指標(biāo)之極大或極小等)。( vi )寫(xiě)出基本方程即

15、最優(yōu)值函數(shù)滿足的遞歸方程，以及端點(diǎn)條件。§ 3 逆序解法的計(jì)算框圖以自由終端、固定始端、指標(biāo)函數(shù)取和的形式的逆序解法為例給出計(jì)算框圖，其它情況容易在這個(gè)基礎(chǔ)上修改得到。一般化的自由終端條件為fn1(xn1,i)(xn 1,i), i 1,2,nn1(3)其中 為已知。固定始端條件可表示為X1 x1x1* 。如果狀態(tài)xk 和決策 uk 是連續(xù)變量，用數(shù)值方法求解時(shí)需按照精度要求進(jìn)行離散化。設(shè)狀態(tài)xk 的允許集合為Xk xki|i1,2,nk, i 1,2, ,nk,k1,2, ,n.決策uki (xki ) 的允許集合為Uki uk(ij)| j1,2,nki,i 1,2, ,nk,k

16、1,2,n.狀態(tài)轉(zhuǎn)移方程和階段指標(biāo)應(yīng)對(duì)xk 的每個(gè)取值xki 和 uki 的每個(gè)取值u(kij) 計(jì)算，即TkTk(xki,uk(ij)，vkv(xki,uk(ij) 。 最優(yōu)值函數(shù)應(yīng)對(duì)xk 的每個(gè)取值xki計(jì)算。 基本方程可以表為fk(j)(xki)vk(xki ,uk(ij) fk 1(Tk(xki ,uk(ij),fk(xki)opt fk(j)(xki ),( 4)j 1,2,nki,i 1,2, ,nk, k n, ,2,1.按照(3) ， ( 4)逆向計(jì)算出f1(x1* )，為全過(guò)程的最優(yōu)值。記狀態(tài)xki 的最優(yōu)決策為uk*i (xki ) ， 由 x1*和 uk*i (xki )

17、 按照狀態(tài)轉(zhuǎn)移方程計(jì)算出最優(yōu)狀態(tài)，記作xk* 。 并得到相應(yīng)的最優(yōu)決策，記作u*k(xk* ) 。于是最優(yōu)策略為u1 (x1 ),u2 (x2 ),un (xn ) 。算法程序的框圖如下。圖的左邊部分是函數(shù)序列的遞推計(jì)算，可輸出全過(guò)程最優(yōu)值f1(x1* )，如果需要還可以輸出后部子過(guò)程最優(yōu)值函數(shù)序列fk(xki ) 和最優(yōu)決策序列u*k(xki )。計(jì)算過(guò)程中存fk(xki ) 是備計(jì)算fk1 之用， 在fk1 算完后可用fk1 將fk替換掉；存uk(xki) 是備右邊部分讀uk(xk) 之用。圖的右邊部分是最優(yōu)狀態(tài)和最優(yōu)決策序列的正向計(jì)算，可輸出最優(yōu)策略*u1 (x1),u2(x2), ,u

18、n(xn) 和最優(yōu)軌線x1 ,x2,xn 。4 動(dòng)態(tài)規(guī)劃與靜態(tài)規(guī)劃的關(guān)系動(dòng)態(tài)規(guī)劃與靜態(tài)規(guī)劃(線性和非線性規(guī)劃等)研究的對(duì)象本質(zhì)上都是在若干約束條 件下的函數(shù)極值問(wèn)題。兩種規(guī)劃在很多情況下原則上可以相互轉(zhuǎn)換。動(dòng)態(tài)規(guī)劃可以看作求決策u1 ,u2, ,un 使指標(biāo)函數(shù)V1n(x1,u1， u2, ,un) 達(dá)到最優(yōu)(最大或最小)的極值問(wèn)題，狀態(tài)轉(zhuǎn)移方程、端點(diǎn)條件以及允許狀態(tài)集、允許決策集等是約束條件，原則上可以用非線性規(guī)劃方法求解。一些靜態(tài)規(guī)劃只要適當(dāng)引入階段變量、狀態(tài)、決策等就可以用動(dòng)態(tài)規(guī)劃方法求解。下面用例子說(shuō)明。例 3 用動(dòng)態(tài)規(guī)劃解下列非線性規(guī)劃nm axgk(uk)；k1ns.t. uk a

19、, uk 0 . k1其中 gk (uk )為任意的已知函數(shù)。解 按變量uk 的序號(hào)劃分階段，看作n 段決策過(guò)程。設(shè)狀態(tài)為x1 ,x2 , , xn 1 ，取問(wèn)題中的變量u1,u2,un 為決策。狀態(tài)轉(zhuǎn)移方程為x1 a,xk 1xk uk ,k 1,2, ,n.取 gk (uk )為階段指標(biāo)，最優(yōu)值函數(shù)的基本方程為(注意到xn 10)fk(xk)max gk(xk) fk 1(xk 1) ；0 uk xk0 xka, k n,n 1, ,2,1；fn 1(0) 0.*按照逆序解法求出對(duì)應(yīng)于xk 每個(gè)取值的最優(yōu)決策uk*(xk)，計(jì)算至f1(a)后即可利用狀態(tài)轉(zhuǎn)移方程得到最優(yōu)狀態(tài)序列x*k 和最

20、優(yōu)決策序列uk* (x*k) 。與靜態(tài)規(guī)劃相比，動(dòng)態(tài)規(guī)劃的優(yōu)越性在于：( i )能夠得到全局最優(yōu)解。由于約束條件確定的約束集合往往很復(fù)雜，即使指標(biāo)函數(shù)較簡(jiǎn)單，用非線性規(guī)劃方法也很難求出全局最優(yōu)解。而動(dòng)態(tài)規(guī)劃方法把全過(guò)程化為一系列結(jié)構(gòu)相似的子問(wèn)題，每個(gè)子問(wèn)題的變量個(gè)數(shù)大大減少，約束集合也簡(jiǎn)單得多，易于得到全局最優(yōu)解。特別是對(duì)于約束集合、狀態(tài)轉(zhuǎn)移和指標(biāo)函數(shù)不能用分析形式給出的優(yōu)化問(wèn)題，可以對(duì)每個(gè)子過(guò)程用枚舉法求解，而約束條件越多，決策的搜索范圍越小，求解也越容易。對(duì)于這類問(wèn)題，動(dòng)態(tài)規(guī)劃通常是求全局最優(yōu)解的唯一方法。( ii)可以得到一族最優(yōu)解。與非線性規(guī)劃只能得到全過(guò)程的一個(gè)最優(yōu)解不同，動(dòng)態(tài)規(guī)劃得

21、到的是全過(guò)程及所有后部子過(guò)程的各個(gè)狀態(tài)的一族最優(yōu)解。有些實(shí)際問(wèn)題需要這樣的解族，即使不需要，它們?cè)诜治鲎顑?yōu)策略和最優(yōu)值對(duì)于狀態(tài)的穩(wěn)定性時(shí)也是很有用的。當(dāng)最優(yōu)策略由于某些原因不能實(shí)現(xiàn)時(shí)，這樣的解族可以用來(lái)尋找次優(yōu)策略。( iii )能夠利用經(jīng)驗(yàn)提高求解效率。如果實(shí)際問(wèn)題本身就是動(dòng)態(tài)的，由于動(dòng)態(tài)規(guī)劃方法反映了過(guò)程逐段演變的前后聯(lián)系和動(dòng)態(tài)特征，在計(jì)算中可以利用實(shí)際知識(shí)和經(jīng)驗(yàn)提高求解效率。如在策略迭代法中，實(shí)際經(jīng)驗(yàn)?zāi)軌驇椭x擇較好的初始策略，提高收斂速度。動(dòng)態(tài)規(guī)劃的主要缺點(diǎn)是：( i )沒(méi)有統(tǒng)一的標(biāo)準(zhǔn)模型，也沒(méi)有構(gòu)造模型的通用方法，甚至還沒(méi)有判斷一個(gè)問(wèn)題能否構(gòu)造動(dòng)態(tài)規(guī)劃模型的準(zhǔn)則。這樣就只能對(duì)每類問(wèn)題

22、進(jìn)行具體分析，構(gòu)造具體的模型。 對(duì)于較復(fù)雜的問(wèn)題在選擇狀態(tài)、決策、 確定狀態(tài)轉(zhuǎn)移規(guī)律等方面需要豐富的想象力和靈活的技巧性，這就帶來(lái)了應(yīng)用上的局限性。( ii ) 用數(shù)值方法求解時(shí)存在維數(shù)災(zāi)( curse of dimensionality ) 。 若一維狀態(tài)變量有m個(gè)取值，那么對(duì)于n 維問(wèn)題，狀態(tài)xk 就有mn個(gè)值，對(duì)于每個(gè)狀態(tài)值都要計(jì)算、存儲(chǔ)函數(shù) fk(xk) ，對(duì)于 n 稍大(即使n 3)的實(shí)際問(wèn)題的計(jì)算往往是不現(xiàn)實(shí)的。目前還沒(méi)有克服維數(shù)災(zāi)的有效的一般方法。§ 5 若干典型問(wèn)題的動(dòng)態(tài)規(guī)劃模型5.1 最短路線問(wèn)題對(duì)于例 1 一類最短路線問(wèn)題(shortest Path Proble

23、m ) ，階段按過(guò)程的演變劃分，狀態(tài)由各段的初始位置確定，決策為從各個(gè)狀態(tài)出發(fā)的走向，即有xk 1uk(xk )，階段指標(biāo)為相鄰兩段狀態(tài)間的距離dk(xk ,uk (xk)， 指標(biāo)函數(shù)為階段指標(biāo)之和，最優(yōu)值函數(shù)fk(xk )是由xk出發(fā)到終點(diǎn)的最短距離(或最小費(fèi)用)，基本方程為fk(xk )min dk(xk,uk(xk )fk 1(xk 1 ), k n, ,1;uk (xk )fn 1 (xn 1 ) 0.利用這個(gè)模型可以算出例l 的最短路線為AB1C2D1E2F2G，相應(yīng)的最短距離為18。5.2 生產(chǎn)計(jì)劃問(wèn)題對(duì)于例 2 一類生產(chǎn)計(jì)劃問(wèn)題(Production planning probl

24、em ) ，階段按計(jì)劃時(shí)間自然劃分，狀態(tài)定義為每階段開(kāi)始時(shí)的儲(chǔ)存量xk ，決策為每個(gè)階段的產(chǎn)量uk ，記每個(gè)階段的需求量(已知量)為dk ，則狀態(tài)轉(zhuǎn)移方程為xk 1 xk uk dk,xk0,k 1,2,n.(5)設(shè)每階段開(kāi)工的固定成本費(fèi)為a ， 生產(chǎn)單位數(shù)量產(chǎn)品的成本費(fèi)為b ， 每階段單位數(shù)量產(chǎn)品的儲(chǔ)存費(fèi)為c，階段指標(biāo)為階段的生產(chǎn)成本和儲(chǔ)存費(fèi)之和，即a buk, uk0vk(xk,uk)cxk0(6)指標(biāo)函數(shù)Vkn 為 vk 之和。最優(yōu)值函數(shù)fk(xk) 為從第 k 段的狀態(tài)xk 出發(fā)到過(guò)程終結(jié)的最小費(fèi)用，滿足fk(xk)umiUnvk(xk,uk)fk 1(xk 1), k n, ,1.其

25、中允許決策集合U k 由每階段的最大生產(chǎn)能力決定。若設(shè)過(guò)程終結(jié)時(shí)允許存儲(chǔ)量為xn0 1，則終端條件是fn 1 (x0n 1)0.( 7)5 5) ( 7)構(gòu)成該問(wèn)題的動(dòng)態(tài)規(guī)劃模型。6 .3 資源分配問(wèn)題一種或幾種資源(包括資金)分配給若干用戶，或投資于幾家企業(yè)，以獲得最大的效益。資源分配問(wèn)題(resource allocating Problem)可以是多階段決策過(guò)程，也可以是靜態(tài)規(guī)劃問(wèn)題，都能構(gòu)造動(dòng)態(tài)規(guī)劃模型求解。下面舉例說(shuō)明。例 4 機(jī)器可以在高、低兩種負(fù)荷下生產(chǎn)。u 臺(tái)機(jī)器在高負(fù)荷下的年產(chǎn)量是g(u) ，在 低 負(fù) 荷 下 的 年 產(chǎn) 量 是 h(u) ， 高 、 低 負(fù) 荷 下 機(jī) 器

26、 的 年 損 耗 率 分 別 是a1 和 b1( 0 b1a1 1 ) 。 現(xiàn)有 m 臺(tái)機(jī)器， 要安排一個(gè)n年的負(fù)荷分配計(jì)劃，即 每年初決定多少臺(tái)機(jī)器投入高、低負(fù)荷運(yùn)行，使n年的總產(chǎn)量最大。如果進(jìn)一步假設(shè)g(u) u ，h(u) u (0) ，即高、低負(fù)荷下每臺(tái)機(jī)器的年產(chǎn)量分別為和 ，結(jié)果將有什么特點(diǎn)。解 年度為階段變量k 1,2, n 。狀態(tài)xk 為第k 年初完好的機(jī)器數(shù)，決策uk 為第 k 年投入高負(fù)荷運(yùn)行的臺(tái)數(shù)。當(dāng)xk 或 uk不是整數(shù)時(shí)，將小數(shù)部分理解為一年中正常工作時(shí)間或投入高負(fù)荷運(yùn)行時(shí)間的比例。機(jī)器在高、低負(fù)荷下的年完好率分別記為a 和 b ，則 a 1 a1 ， b 1 b1 ，

27、有a b 。因?yàn)榈趉 年投入低負(fù)荷運(yùn)行的機(jī)器臺(tái)數(shù)為xk uk ，所以狀態(tài)轉(zhuǎn)移方程是xk 1 auk b(xk uk )( 8)階段指標(biāo)vk 是第k 年的產(chǎn)量，有vk (xk ,uk ) g(uk ) h(xk uk )( 9)指標(biāo)函數(shù)是階段指標(biāo)之和，最優(yōu)值函數(shù)fk(xk) 滿足fk(xk) max vk(xk,uk)fk 1(xk 1),0 uk xk(10)0 xkm, k n, ,2,1.及自由終端條件fn 1(xn 1) 0, 0 xn 1 m.( 11)當(dāng) vk 中的 g, h 用較簡(jiǎn)單的函數(shù)表達(dá)式給出時(shí)，對(duì)于每個(gè)k 可以用解析方法求解極值問(wèn)題。 特別， 若 g(u) u ， h(u)

28、 u ， ( 10) 中的vk(xk ,uk)fk 1(xk) 將是uk的線性函數(shù)，最大值點(diǎn)必在區(qū)間0 ukxk 的左端點(diǎn)uk0或右端點(diǎn)ukxk 取得，即每年初將完好的機(jī)器全部投入低負(fù)荷或高負(fù)荷運(yùn)行。§ 6 具體的應(yīng)用實(shí)例例 5 設(shè)某工廠有1000 臺(tái)機(jī)器，生產(chǎn)兩種產(chǎn)品A、 B ，若投入y臺(tái)機(jī)器生產(chǎn)A產(chǎn)品， 則純收入為5y， 若投入 y臺(tái)機(jī)器生產(chǎn)B 種產(chǎn)品， 則純收入為4y， 又知： 生產(chǎn) A種產(chǎn)品機(jī)器的年折損率為20%，生產(chǎn)B 產(chǎn)品機(jī)器的年折損率為10%，問(wèn)在5年內(nèi)如何安排各年度的生產(chǎn)計(jì)劃，才能使總收入最高？解 年度為階段變量k 1,2,3,4,5。令 xk 表示第k 年初完好機(jī)器

29、數(shù)，uk 表示第 k 年安排生產(chǎn)A種產(chǎn)品的機(jī)器數(shù)，則xkuk為第k 年安排生產(chǎn)B 種產(chǎn)品的機(jī)器數(shù)，且0 ukxk。則第 k 1 年初完好的機(jī)器數(shù)xk 1 (1 0.2)uk (1 0.1)(xkuk) 0.9xk 0.1uk( 12)令 vk(xk ,uk)表示第k 年的純收入，fk(xk)表示第 k 年初往后各年的最大利潤(rùn)之和。顯然f6(x6) 0( 13)fk(xk)maxvk(xk,uk) fk 1(xk 1)0 uk xkmax5uk 4(xk uk) fk 1(xk 1) maxuk 4xk fk 1(xk 1) ( 14)0 u k xk0 u k xk1 ) k 5 時(shí)，由(13

30、) 、 ( 14)式得f5 (x5)0mu5axx5u5 4x5u5 4x5關(guān)于u5求導(dǎo)，知其導(dǎo)數(shù)大于零，所以u(píng)5 4x5在 u5等于x5處取得最大值，即 u5x5 時(shí)，f5 (x5 ) 5x5 。2) 2) k 4時(shí)，由(12) 、 ( 14)式得f4 (x4) max u4 4x4 5x50 u4 x4maxu4 4x4 5(0.9x 4 0.1u 4) max0.5u4 8.5x4 0 u 4 x40 u4 x4當(dāng) u4 x4時(shí)，f4(x4 ) 9x43) 3) k 3時(shí)，f3(x3)max u3 4x3 9x40 u3 x3max u3 4x3 9(0.9 x 3 0.1u3)max

31、0.1u3 12.1x 30 u 3 x30 u 3 x3u3x3時(shí)，f3(x3) 12.2x34) k 2 時(shí)，f2 (x2)max u2 4x2 12.2x3max 0.22u2 14.98x20 u2 x20 u 2 x2u20時(shí)，f2(x2) 14.98x2。5) k 1 時(shí)，f1(x1 ) maxu1 4x1 14.98x2max 0.498u1 17.482 x1當(dāng) u10時(shí)，f1(x1) 17.482x1。因?yàn)閤11000(臺(tái))所以由(12)式，進(jìn)行回代得x20.9x1 0.1u1 900(臺(tái))x30.9x2 0.1u2 810(臺(tái))x40.9x3 0.1u3648(臺(tái))x50.9x4 0.1u4 518.4(臺(tái))注：x5518.4臺(tái)中的 0.4臺(tái)應(yīng)理解為有一臺(tái)機(jī)器只能使用0.4 年將報(bào)廢。例 6 求解下面問(wèn)題2max z u1u2u3u1u2 u3 c (c 0)ui0 i 1,2,3解： 按問(wèn)題的變量個(gè)數(shù)劃分階段，把它看作為一個(gè)三階段決策問(wèn)題。設(shè)狀態(tài)變量為 x1 ,x2,x3,x4， 并記x1 c； 取問(wèn)題中的變量u1,u2,u3 為決策變量；各階段指標(biāo)函數(shù)按乘積方式結(jié)合。令最優(yōu)值函數(shù)fk(xk)表示第k 階段的初始狀態(tài)為xk，從k 階段到 3階段所得到的最大值。設(shè) x3 u3 ，x3u 2x2 ，x2u1x1