5.1動態(tài)規(guī)劃的基本概念

1、運運 籌籌 學學第五章 動態(tài)規(guī)劃第五章 動態(tài)規(guī)劃 動態(tài)規(guī)劃是運籌學的一個重要分支，它是從1951年開始，由美國人貝爾曼（R.Belman）為首的一個學派發(fā)展起來的。動態(tài)規(guī)劃在經(jīng)濟、管理、軍事、工程技術等方面都有廣泛的應用。 動態(tài)規(guī)劃是解決多階段決策過程的最優(yōu)化問題的一種方法。所謂多階段決策過程是指這樣一類決策過程：它可以把一個復雜問題按時間（或空間）分成若干個階段，每個階段都需要作出決策，以便得到過程的最優(yōu)結局。由于在每個階段采取的決策是與時間有關的而且前一階段采取的決策如何，不但與該階段的經(jīng)濟效果有關，還影響以后各階段的經(jīng)濟效果，可見這類多階段決策問題是一個動態(tài)的問題，因此，處理的方法稱為動

2、態(tài)規(guī)劃方法。然而，動態(tài)規(guī)劃也可以處理一些本來與時間沒有關系的靜態(tài)模型，這只要在靜態(tài)模型中人為地引入“時間”因素，分成時段，就可以把它看作是多階段的動態(tài)模型，用動態(tài)規(guī)劃方法去處理。 動態(tài)規(guī)劃對于解決多階段決策問題的效果是明顯的，但也有一定的局限性。首先，它沒有統(tǒng)一的處理方法，必須根據(jù)問題的各種性質(zhì)并結合一定的技巧來處理；另外當變量的維數(shù)增大時，總的計算量及存貯量急劇增大。由于計算機的存貯量及計算速度的限制，目前的計算機仍不能用動態(tài)規(guī)劃方法來解決較大規(guī)模的問題，這就是所謂“維數(shù)障礙”。 1 動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的基本概念n 1.1 多階段決策問題多階段決策問題 在研究社會經(jīng)濟、經(jīng)營管理和工程

3、技術領域內(nèi)的有關問題中，有一類特殊形式的動態(tài)決策問題多階段決策問題。在多階段決策過程中，系統(tǒng)的動態(tài)過程可以按照時間進程分為相互聯(lián)系而又相互區(qū)別的各個階段，在每個階段都要進行決策。系統(tǒng)在每個階段存在許多不同的狀態(tài)，在某個時點的狀態(tài)往往要依某種形式受到過去某些決策的影響，而系統(tǒng)的當前狀態(tài)和決策又會影響系統(tǒng)過程今后的發(fā)展。因而在尋求多階段決策問題的最優(yōu)解時，重要的是不能僅僅從眼前的局部利益出發(fā)進行決策，而需要從系統(tǒng)所經(jīng)過的整個期間的總效應出發(fā)，有預見性地進行動態(tài)決策，找到不同時點的最優(yōu)決策及整個過程的最優(yōu)策略。 下面舉例說明什么是多階段決策問題。 例1（最短路線問題）在線路網(wǎng)絡圖51中，從A至E有一

4、批貨物需要調(diào)運。圖上所標數(shù)字為各節(jié)點之間的運輸距離，為使總運費最少，必須找出一條由A至E總里程最短的路線。AB1B2EB3C2C3C1D2D3D14534443165887710296為了找到由A至E的最短線路，可以將該問題分成ABCDE 4個階段，在每個階段都需要作出決策，即在A點需決策下一步到B1還是到B2或B3；同樣，若到達第二階段某個狀態(tài)，比如B1 ，需決定走向C1還是C2 ；依次類推，可以看出：各個階段的決策不同，由A至E的路線就不同，當從某個階段的某個狀態(tài)出發(fā)作出一個決策，則這個決策不僅影響到下一個階段的距離，而且直接影響后面各階段的行進線路。所以這類問題要求在各個階段選擇一個恰當

5、的決策，使這些決策序列所決定的一條路線對應的總路程最短。圖圖51 例2（帶回收的資源分配問題）某廠新購某種機床125臺。據(jù)估計，這種設備5年后將被其它設備所代替。此機車如在高負荷狀態(tài)下工作，年損壞率為1/2，年利潤為10萬元；如在低負荷狀態(tài)下工作，年損壞率為1/5，年利潤為6萬元。問應如何安排這些機床的生產(chǎn)負荷，才能使5年內(nèi)獲得的利潤最大？ 本問題具有時間上的次序性，在五年計劃的每一年都要作出關于這些機床生產(chǎn)負荷的決策，并且一旦作出決策，不僅影響到本年利潤的多少，而且影響到下一年初完好機床數(shù)，從而影響以后各年的利潤。所以在每年初作決策時，必須將當年的利潤和以后各年利潤結合起來，統(tǒng)籌考慮。 與上

6、面例1、例2類似的多階段決策問題還有資源分配、生產(chǎn)存貯、可靠性、背包、設備更新問題等等。 1.2 動態(tài)規(guī)劃的基本概念 1.階段階段 動態(tài)規(guī)劃問題通常都具有時間或空間上的次序性，因此求解這類問題時，首先要將問題按一定的次序劃分成若干相互聯(lián)系的階段，以便能按一定次序去求解。如例1，可以按空間次序劃分為ABCDE 4個階段，而例2，按照時間次序可分成5個階段。 2.狀態(tài)狀態(tài) 在多階段決策過程中，每階段都需要作出決策，而決策是根據(jù)系統(tǒng)所處情況決定的。狀態(tài)是描述系統(tǒng)情況所必需的信息。如例1中每階段的出發(fā)點位置就是狀態(tài)，例2中每年初擁有的完好機床數(shù)是作出機床負荷安排的根據(jù)，所以年初完好機床數(shù)是狀態(tài)。一般地

7、，狀態(tài)可以用一個變量來描述，稱為狀態(tài)變量。記第k 階段的狀態(tài)變量為xk,k=1,2, ,n. 3.決策決策 多階段決策過程的發(fā)展是用各階段的狀態(tài)演變來描述的，階段決策就是決策者從本階段某狀態(tài)出發(fā)對下一階段狀態(tài)所作出的選擇。描述決策的變量稱為決策變量，當?shù)趉 階段的狀態(tài)確定之后，可能作出的決策要受到這一狀態(tài)的影響。這就是說決策變量uk還是狀態(tài)變量xk 的函數(shù)，因此，又可將第k階段xk狀態(tài)下的決策變量記為uk(xk)。 在實際問題中，決策變量的取值往往限制在某一范圍之內(nèi)，此范圍稱為允許決策變量集合，記作Dk(uk)。如例2中取高負荷運行的機床數(shù)uk為決策變量，則0ukxk（xk是k階段初完好機床數(shù)

8、）為允許決策變量集合。 4.狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程 在多階段決策過程中，如果給定了k 階段的狀態(tài)變量xk和決策變量uk，則第k+1階段的狀態(tài)變量xk+1也會隨之而確定。也就是說xk+1是xk和uk函數(shù)，這種關系可記為 xk+1=T(xk, uk)稱之為狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程。 5.策略策略 在一個多階段決策過程中，如果各個階段的決策變量uk(xk) （k=1，2，n）都已確定，則整個過程也就完全確定。稱決策序列u1(x1), u2(x2), , un(xn)為該過程的一個策策略略，從階段k到階段n的決策序列稱為子策略子策略，表示成uk(xk), uk+1(xk+1), , un(xn) 。

9、如例1中，選取一路線AB1C2D2E 就是一個策略： u1(A)= B1, u2(B1)= C2, u3(C2)= D2, u4(D2)=E 由于每一階段都有若干個可能的狀態(tài)和多種不同的決策，因而一個多階段決策的實際問題存在許多策略可供選擇，稱其中能夠滿足預期目標的策略為最優(yōu)策略最優(yōu)策略。例1中存在12條不同路線，其中AB2C1D2E是最短線路。 6.指標函數(shù)指標函數(shù) 用來衡量過程優(yōu)劣的數(shù)量指標，稱為指標函數(shù)指標函數(shù)。在階段k的xk狀態(tài)下執(zhí)行決策uk，不僅帶來系統(tǒng)狀態(tài)的轉(zhuǎn)移，而且也必然對目標函數(shù)給予影響，階段效應就是執(zhí)行階段決策時給目標函數(shù)的影響。 多階段決策過程關于目標函數(shù)的總效應是各階段的階段效應累積形成的。常見的全過程目標函數(shù)有以下兩種形式：n （1）全過程的目標函數(shù)等于各階段目標函數(shù)的和，即： R=r1 (x1, u1) +r2 (x2, u2) +rn(xn, un)n （2）全過程的目標函數(shù)等于各階段目標函數(shù)