線性規(guī)劃方法課件

動態(tài)規(guī)劃

第一節(jié)動態(tài)規(guī)劃的基本原理一、動態(tài)規(guī)劃的基本概念二、遞推方程與最優(yōu)化原理第二節(jié)動態(tài)規(guī)劃的數(shù)學模型和求解方法一、動態(tài)規(guī)劃的數(shù)學模型二、動態(tài)規(guī)劃的求解方法第三節(jié)多維動態(tài)規(guī)劃簡介一、多維動態(tài)規(guī)劃問題的數(shù)學模型與求解方法的改進途徑二、動態(tài)規(guī)劃逐次漸近法三、離散微分動態(tài)規(guī)劃法四、系統(tǒng)方程的可逆性*/57動態(tài)規(guī)劃動態(tài)規(guī)劃（DynamicProgramming），縮寫為DP，是本世紀50年代初期由美國數(shù)學家貝爾曼（RichardE．Bellman）等人提出，逐漸發(fā)展起來的數(shù)學分支，它是一種解決多階段決策過程最優(yōu)化問題的數(shù)學規(guī)劃法。動態(tài)規(guī)劃的數(shù)學模型和求解方法比較靈活，對于系統(tǒng)是連續(xù)的或離散的，線性的或非線性的，確定性的或隨機性的，只要能構(gòu)成多階段決策過程，便可用動態(tài)規(guī)劃推求其最優(yōu)解。因而在自然科學、社會科學、工程技術(shù)等許多領(lǐng)域具有廣泛的用途，比線性規(guī)劃、非線性規(guī)劃更有成效，特別對于離散型問題，解析數(shù)學無法適用，動態(tài)規(guī)劃就成為非常有用的求解工具。它在廣泛應用中的主要障礙是“維數(shù)災”，即當問題中的變量個數(shù)（維數(shù)）太大時，由于計算機內(nèi)存貯量和計算速度限制，而無法求解。*/57第一節(jié)動態(tài)規(guī)劃的基本原理一、動態(tài)規(guī)劃的基本概念

（一）動態(tài)規(guī)劃的基本思路

在客觀事物中，存在著這樣一類問題:可以按照時間或空間特性將其劃分為若干個互相聯(lián)系的階段；在每個階段都需要做出決策，并且一個階段的決策將影響下階段的狀態(tài)；所有階段決策構(gòu)成一個決策序列，稱為策略；每個策略都對應一個效果。所選擇的策略應使整個過程獲得最優(yōu)效果。這類問題稱為多階段決策過程，動態(tài)規(guī)劃就是按照上述思路尋求問題最優(yōu)解的工具。*/57一、動態(tài)規(guī)劃的基本概念-（一）動態(tài)規(guī)劃的基本思路例如，以灌溉或發(fā)電為目標的年調(diào)節(jié)水庫調(diào)度問題，就是一個多階段決策過程。

一年可以按時間分成若干階段。在每個階段，以水庫蓄水量（或水位）為狀態(tài)變量，以放水量為決策變量，把灌溉效益或發(fā)電量最大化作為目標函數(shù)。在滿足約束條件下確定各時段放水量，即組成一個決策序列。如果所選定的各時段放水量能使全年灌溉或發(fā)電效益最大，這就是一個最優(yōu)策略，即最優(yōu)調(diào)度方案。由于各階段決策與時間進程有關(guān)，故稱為動態(tài)規(guī)劃。動態(tài)規(guī)劃不僅能解決與時間有關(guān)的優(yōu)化問題，而且也能解決與時間無關(guān)的靜態(tài)問題。

例如，資源分配問題、投資分配問題、最優(yōu)線路問題、結(jié)構(gòu)優(yōu)化問題等。只要能夠把問題分成多個階段或步驟進行決策，就可用動態(tài)規(guī)劃尋求最優(yōu)解。*/5752511214106104131112396581052C1C3D1AB1B3B2D2EC2也可稱為最短路徑問題：求從A到E的最短路徑一、動態(tài)規(guī)劃的基本概念-（一）動態(tài)規(guī)劃的基本思路下面以一個簡單的最優(yōu)輸水線路問題，說明動態(tài)規(guī)劃尋求最優(yōu)解的基本思路和方法。[例1]如下圖所示，現(xiàn)擬由水源A(起點站)，引水到用水地點E(終點站)。在輸水途中將經(jīng)過3級中轉(zhuǎn)站，第一級中轉(zhuǎn)站可以在地點B1、B2或B3中任選一點，第二級中轉(zhuǎn)站可以在地點C1、C2或C3中任選一點，第三級中轉(zhuǎn)站可以在地點D1或D2中任選一點，任何兩個地點之間的輸水費用已表示在圖中的聯(lián)結(jié)線上。問題是要選擇一條由水源A到用水地點E總輸水費用最小的路線。62511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=072511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=082511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=592511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=5102511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=8112511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=7122511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=8132511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=21142511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1)=21f2(B2)=14152511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21162511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)A（A，B2）B2172511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)A（A，B2）B2（B2，C1）C1182511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)A（A，B2）B2（B2，C1）C1（C1，D1）D1192511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)A（A，B2）B2（B2，C1）C1（C1，D1）D1（D1，E）E202511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)A（A，B2）B2（B2，C1）C1（C1，D1）D1（D1，E）E從A到E的最小費用（最短路徑）為19，路線為A→B2→C1→D1→E一、動態(tài)規(guī)劃的基本概念-（一）動態(tài)規(guī)劃的基本思路由本例可以看出，用動態(tài)規(guī)劃法求解的問題，必須具備以下特點：

①所研究的系統(tǒng)能劃分成若干階段(或步驟)；

②每個階段都能做出決策；

③

相鄰兩個階段的狀態(tài)能夠轉(zhuǎn)移，這種轉(zhuǎn)移是

通過使用某一決策而實現(xiàn)的。所以動態(tài)規(guī)劃是既把整個過程分為若干階段，又要考慮相鄰兩階段之間關(guān)系的一種方法。*/57一、動態(tài)規(guī)劃的基本概念-（二）多階段決策過程設(shè)某系統(tǒng)隨時間或空間變化，其演變過程可劃分為若干個階段，系統(tǒng)在各階段的狀態(tài)由狀態(tài)序列｛s1，s2，…，sn，sn+1，…，sN+1｝來表征。若n＋1階段的狀態(tài)sn+1是由n階段的狀態(tài)sn經(jīng)過轉(zhuǎn)移而形成，即sn+1=g(sn,dn)該式稱為狀態(tài)轉(zhuǎn)移方程。并且這種轉(zhuǎn)移是在一定約束下進行選擇的，則相應狀態(tài)轉(zhuǎn)移的選擇就是決策dn，轉(zhuǎn)移過程就是決策的結(jié)果。每個階段要做出一種決策，從而使整個過程獲得最優(yōu)效果。這一過程就稱為多階段決策過程，或稱為序列過程，如下圖所示（狀態(tài)轉(zhuǎn)移圖）。因此，多階段決策過程應看成是階段、狀態(tài)、決策以及和它們相關(guān)聯(lián)的效果的綜合體。*/57一、動態(tài)規(guī)劃的基本概念-（二）多階段決策過程1．階段在這里，階段可定義為所研究的事物在發(fā)展中所處的時段或步驟（或某一局部空間），有時稱為級，又稱步。以序列數(shù)字n＝l，2，…，N表示，常稱為階段變量或級變量，表示階段的次序或階段數(shù)。如果所研究的問題，其演變過程是離散的，則階段變量自然以上述自然數(shù)表示，如［例1]中我們將輸水路線編為n=1，2，3,4等4個階段。如果問題演變的過程是連續(xù)的，且為時間連續(xù)，則階段變量可用t表示，并定義在過程演變的整個時間區(qū)間，即t始≤t≤t終。但是在用動態(tài)規(guī)劃求解時，連續(xù)的階段變量t仍須按時間增量?t進行離散化。離散化的t值，可由離散序列n=1，2，…，N表示，相應于n的階段末t值為t=t始+n?t。*/57一、動態(tài)規(guī)劃的基本概念-（二）多階段決策過程2．狀態(tài)描述系統(tǒng)演變過程中各階段所處狀況的特征量稱為狀態(tài),常以s表示。在任一階段n可有若干個狀態(tài)，構(gòu)成該階段的狀態(tài)集合sn。

sn={sn1,sn2,…,snr}

式中，r——階段n的狀態(tài)點數(shù)。如［例1]中某階段n的某個中轉(zhuǎn)點就是該階段的一個狀態(tài)；而階段n的所有中轉(zhuǎn)點，就構(gòu)成該階段的狀態(tài)集合。描述過程狀態(tài)（或稱系統(tǒng)狀態(tài)）的變量，稱為狀態(tài)變量。它可以是一維變量，也可以是多維變量。例如包括4個水庫的水資源系統(tǒng)，若以各水庫時段初蓄水量為狀態(tài)變量，則該系統(tǒng)的狀態(tài)變量即為四維向量。推而廣之，對于一個給定系統(tǒng)，若選用m個狀態(tài)變量，記為s1，s2，…，sm，則這些狀態(tài)變量構(gòu)成一個m維狀態(tài)向量S。

S=[s1s2

…sm]T*/57一、動態(tài)規(guī)劃的基本概念-（二）多階段決策過程為了建立數(shù)學模型，必須正確地選擇狀態(tài)變量s。動態(tài)規(guī)劃中的狀態(tài)變量應當具有下列性質(zhì)：①能夠逐階段轉(zhuǎn)移，用以描述受控過程的演變特征；②各狀態(tài)變量的值，可以直接或間接地獲知；③要求滿足無后效性。即當某階段的狀態(tài)一旦確定，則此后過程的演變不再受此前各狀態(tài)和決策的影響，或者說“未來與過去無關(guān)”。即由狀態(tài)sn出發(fā)的后部子過程可以看成一個以sn為初始狀態(tài)的獨立過程.*/57一、動態(tài)規(guī)劃的基本概念-（二）多階段決策過程例如上圖所示最優(yōu)輸水路徑問題中，由中轉(zhuǎn)點C1到下一階段（未來）中轉(zhuǎn)點D1或D2這一過程，與前一階段（過去）中轉(zhuǎn)點B1或B2、B3到達中轉(zhuǎn)點C1是無關(guān)的；同時各階段上所有中轉(zhuǎn)點都是給定確知的，而且描述了過程的演變，所以可作為狀態(tài)變量。*/572511214106104131112396581052C1C3D1AB1B3B2D2EC2一、動態(tài)規(guī)劃的基本概念-（二）多階段決策過程3．決策

某階段狀態(tài)給定后，從該狀態(tài)演變到下一階段某個狀態(tài)的選擇稱為決策，常以d表示。在多階段決策過程的任一階段中，當階段的狀態(tài)sn給定后，如果做出某一決策dn，則階段初的狀態(tài)就轉(zhuǎn)移到一個相應的下一階段狀態(tài)sn+1。如[例1]中，在第3階段狀態(tài)C1，做出決策C1→D2，便轉(zhuǎn)移到第4階段狀態(tài)D2。*/572511214106104131112396581052C1C3D1AB1B3B2D2EC2一、動態(tài)規(guī)劃的基本概念-（二）多階段決策過程決策隨階段n和狀態(tài)sn而變化，在一個狀態(tài)sn下，可有若干個決策dn，但其取值應被限制在某一范圍內(nèi)，即dn

D(n,sn)，D(n,sn)為在階段n狀態(tài)sn下的可行決策集合。描述決策的變量稱為決策變量。應具備的性質(zhì)：① 能夠被控制；② 能通過狀態(tài)變量而影響過程的演變，即能有效地控制系統(tǒng)。一個問題的決策變量可以是一個或多個。*/57一、動態(tài)規(guī)劃的基本概念-（二）多階段決策過程4．策略由第1階段開始直到終點為止的過程稱為問題的全過程。由每個階段的決策dn（n=l，…，N）所組成的決策序列，稱為全過程策略，簡稱策略，記為P1,N，即P1,N=｛d1，d2，…，dN｝由第k階段開始到終點為止的過程，為原問題的后部子過程，又稱為k子過程或余留過程。其決策序列｛dk，dk+1，…，dN｝稱為k子過程策略，簡稱子策略，即Pk,N=｛dk，dk+1，…，dN｝在實際問題中，可供選擇的策略有很多個，其中能使全過程獲得最優(yōu)效果的策略稱為最優(yōu)策略。而與最優(yōu)策略相應的狀態(tài)序列，則稱為最優(yōu)軌跡。*/57一、動態(tài)規(guī)劃的基本概念-（二）多階段決策過程現(xiàn)以上圖表示N階段決策過程狀態(tài)轉(zhuǎn)移的全貌。圖中，n=1，2，…，N為階段變量，｛sn｝=｛s1，s2，…，sN+1｝為狀態(tài)序列，｛dn｝=｛d1，d2，…，dN｝為決策序列，｛rn｝={r1，r2，…，rN｝為各階段效益或費用。從上圖和上述分析可以看出，多階段決策過程具有如下性質(zhì)：在多階段決策過程中，任一階段都是以若干狀態(tài)來表征，其中任一狀態(tài)的變化，都將使該階段決策發(fā)生變化。在每一階段，都可對每個狀態(tài)選擇一種決策，決策的結(jié)果就是狀態(tài)的轉(zhuǎn)移。階段n+l的狀態(tài)sn+1是由階段n的狀態(tài)sn和決策dn所決定，而與n以前的各階段狀態(tài)sn-1，sn-2，…，s1無關(guān)。這表明，多階段決策過程存在著馬爾可夫單鏈性質(zhì)，這是無后效性的重要特性。過程的決策序列可能有多個，但只有使目標函數(shù)獲得最優(yōu)值的策略才是要選擇的最優(yōu)策略。*/57二、遞推方程與最優(yōu)化原理-（一）遞推方程遞推方程是動態(tài)規(guī)劃的基本方程，該方程可由下述一般的數(shù)學推導求得。設(shè)多階段決策過程如下圖所示，階段變量、狀態(tài)變量和決策變量分別以n、s和d表示；系統(tǒng)的實際運動方向為1→N+l，階段的編碼次序與實際運動方向一致，即1→N，遞推計算時采用的系統(tǒng)狀態(tài)轉(zhuǎn)移方向亦與實際運動方向一致，如下圖中箭頭所示；目標函數(shù)為最小化總費用。*/57二、遞推方程與最優(yōu)化原理-

（一）遞推方程首先，設(shè)最小費用函數(shù)為

fn*(sn)表示對由任一階段（級）n上的任一可行狀態(tài)sn開始的后部子過程（余留過程），使用可行決策序列dj，j=n，…，N，所得到的最小總費用。第一步：將上式中大括號內(nèi)的總費用分為兩部分，即第n階段費用和（n＋1）～N階段的總費用，寫成*/57二、遞推方程與最優(yōu)化原理-（一）遞推方程第二步：把決策序列也分為兩部分，即在dn上的最小化和在dn＋l，dn+2，…，dN上的最小化?？梢钥闯?，上式中大括號內(nèi)第1項僅僅決定于dn，而與dn+1,…,dN無關(guān)，因此，di，j＞n上的最小化對這一項沒有影響。上式中第2項看起來似乎與dn無關(guān)，但實際上dn通過系統(tǒng)方程

sn+1＝g（sn，dn）

確定狀態(tài)sn+1。因此，上式可寫成根據(jù)最小費用函數(shù)定義，上式中第2項可寫為

第三步：將上式代入前式得遞推方程

上式就是動態(tài)規(guī)劃的遞推方程，也叫迭代函數(shù)方程。*/57二、遞推方程與最優(yōu)化原理-（一）遞推方程應當指出，上式是在前圖所示條件下推導出來的，即階段變量按順序編碼，且階段號碼與階段初編號一致，系統(tǒng)狀態(tài)轉(zhuǎn)移方向與實際運動方向一致，而遞推計算次序與實際運動方向相反，即由系統(tǒng)實際的終端向始端遞推，故稱這種計算為逆序遞推，又稱向后計算法。實際上，許多問題可以令系統(tǒng)狀態(tài)轉(zhuǎn)移方向與系統(tǒng)實際運動方向相反，這時實際的始端變成了計算用的終端，遞推計算要從這個終端開始，這樣遞推計算次序便與實際運動方向一致，稱之為順序遞推，又叫向前計算法。下圖為順序遞推示意圖，設(shè)階段變量按順序編碼，且階段號碼與階段末編號一致，用上述同樣方法可推導出順序遞推的遞椎方程為：*/57二、遞推方程與最優(yōu)化原理-（一）遞推方程總之，用動態(tài)規(guī)劃求解問題時，要首先選定系統(tǒng)狀態(tài)轉(zhuǎn)移方向，該方向可以與系統(tǒng)實際運動方向一致，也可以相反。然后逆著選定的系統(tǒng)狀態(tài)轉(zhuǎn)移方向，使用遞推方程由計算用的終端向始端進行遞推計算，逐階段找出最優(yōu)決策。這種規(guī)劃過程稱為“逆序”決策過程。也就是說，無論是順序遞推，還是逆序選推，其遞推計算次序必須與計算選用的狀態(tài)轉(zhuǎn)移方向相反，這是動態(tài)規(guī)劃計算的基本特性。由此也可看出，逆序遞推和逆序決策過程是兩個不同的概念。*/57二、遞推方程與最優(yōu)化原理-（二）最優(yōu)化原理最優(yōu)化原理是貝爾曼提出的動態(tài)規(guī)劃的基本原理，其表述如后：“一個過程的最優(yōu)策略具有這樣的性質(zhì)，即不論初始狀態(tài)和初始決策如何，對于初始決策所構(gòu)成的下一個狀態(tài)來說，其余留的所有決策，必須構(gòu)成一個最優(yōu)策略”。現(xiàn)仍以[例l］加以說明。如果從水源A到用水地點E的最小輸水費用路線A→B2→

C1→D1→E通過中轉(zhuǎn)點C1，那末從中轉(zhuǎn)點5到用水地點E也必定是最優(yōu)的，即從中轉(zhuǎn)點C1到用水地點E的最小費用路線是C1→D1→E

，而不能是C1→D2→E

。*/572511214106104131112396581052C1C3D1AB1B3B2D2EC2二、遞推方程與最優(yōu)化原理-（二）最優(yōu)化原理最優(yōu)化原理也可由前述遞椎方程的推導過程加以證明。由遞椎方程可知，其右端第1項L（sn，dn）的值僅取決于sn和dn，而sn和dn是n階段以后遞推過程的初始狀態(tài)和初始決策。遞椎方程右端第2項fn+1*（sn+1）表示由初始決策dn所形成的下一階段狀態(tài)sn+1開始的n＋1，…，N階段的最小總費用，與這個最小總費用相應的n＋1子過程（n＋1，…，N階段）的子策略｛dn+1，…，dN｝*，也應是最優(yōu)策略，故在n階段計算時，要求事先已知fn+1*（sn+1）。因此n＋1階段擇優(yōu)計算必須先于n階段進行，這就是逆序決策過程的基本原理。綜上所述，遞推方程實際上就是最優(yōu)化原理的數(shù)學表達，而最優(yōu)化原理也可以說是遞推方程的文字描述。這個直觀而簡單的原理，就是動態(tài)規(guī)劃的理論基礎(chǔ)。*/57二、遞推方程與最優(yōu)化原理-（二）最優(yōu)化原理由最優(yōu)化原理和遞推方程可以看出動態(tài)規(guī)劃具有如下基本性質(zhì)：(1)動態(tài)規(guī)劃的基本內(nèi)容，實際上是把原問題分成許多相互聯(lián)系的子問題，而每個子問題是一個比原問題簡單得多的優(yōu)化問題，且在每一個子問題的求解中，均利用它的一個后部子問題（余留過程）的最優(yōu)化結(jié)果，依次進行，最后一個子問題所得的最優(yōu)解，即為原問題的最優(yōu)解。動態(tài)規(guī)劃就是將一個決策序列問題轉(zhuǎn)化為多個階段求單階段決策問題；每一個單階段決策問題可看成原問題的一個子問題?，F(xiàn)以一個簡單情況為例說明，如果原問題劃分為N個階段，并且每個階段只有一個決策變量，則動態(tài)規(guī)劃就將一個N維決策的原問題轉(zhuǎn)化成只有一維決策的N個子問題。*/57二、遞推方程與最優(yōu)化原理-（二）最優(yōu)化原理由最優(yōu)化原理和遞推方程可以看出動態(tài)規(guī)劃具有如下基本性質(zhì)（續(xù)）：(2)從遞推方程fn*(sn)=min{L(sn,dn)+fn+1*(sn+1)}中看出，在任一階段n選用一個決策dn后，它有兩方面的影響：其一

它直接影響面臨階段的費用L(sn,dn)；其二

它也影響其后n+1子過程的初始狀態(tài)sn+1，因而影響到后邊N-n個階段的最小總費用fn+1*(sn+1)。全過程最優(yōu)策略的選擇是根據(jù)兩者統(tǒng)一考慮的結(jié)果確定的.所以，在多階段決策過程中，動態(tài)規(guī)劃法是既把面臨階段與未來階段分開，又把當前費用和未來費用結(jié)合起來考慮的一種最優(yōu)化方法。*/57二、遞推方程與最優(yōu)化原理-（二）最優(yōu)化原理由最優(yōu)化原理和遞推方程可以看出動態(tài)規(guī)劃具有如下基本性質(zhì)（續(xù)）：(3)由于用動態(tài)規(guī)劃求解問題只需考慮相鄰兩個階段，就使得動態(tài)規(guī)劃的計算量遠遠小于枚舉法的計算量。對于一個N階段問題，如果始端狀態(tài)只有一個，其他各階段狀態(tài)點數(shù)有T個，每個狀態(tài)下有T個決策，則枚舉法需計算TN個方案，而動態(tài)規(guī)劃法只需計算T+(N-l)T2個方案。(4)

對系統(tǒng)方程、目標函數(shù)、約束條件的函數(shù)性質(zhì)無嚴格要求，線性、非線性均可，甚至用表格表示某些變量之間關(guān)系，都可用動態(tài)規(guī)劃求解，它也不要求決策空間為凸的，故動態(tài)規(guī)劃是一種相當靈活的方法。*/57第二節(jié)動態(tài)規(guī)劃的數(shù)學模型和求解方法一、動態(tài)規(guī)劃的數(shù)學模型

動態(tài)規(guī)劃的數(shù)學模型一般由系統(tǒng)方程、目標函數(shù)、約束條件和邊界條件等幾部分組成。在建立模型時，首先將研究的問題根據(jù)其時間或空間特點劃分階段，形成多階段決策過程，并相應地選取階段變量、狀態(tài)變量和決策變量。1．系統(tǒng)方程

系統(tǒng)方程即上面所說的狀態(tài)轉(zhuǎn)移方程，它是包括階段變量、狀態(tài)變量和決策變量三種變量的一組關(guān)系式。對于具有一個狀態(tài)變量、一個決策變量的一維多階段決策過程，系統(tǒng)方程可寫成

sn+1＝g（sn，dn）n＝1，2，…，N式中，sn——階段n的狀態(tài)變量；

dn——階段n的決策變量；

g（sn，dn）——狀態(tài)轉(zhuǎn)移函數(shù)。*/57一、動態(tài)規(guī)劃的數(shù)學模型例如，［例1]中的系統(tǒng)方程為

sn+1＝dn單一水庫優(yōu)化調(diào)度問題的系統(tǒng)方程為

Sn+1=Sn+In-dn-Wn式中，sn，sn+1——n時段和n＋1時段初水庫蓄水量；

In,dn,Wn——n時段內(nèi)水庫來水量、放水量和蒸發(fā)滲漏損失量。對于具有m維狀態(tài)向量、q維決策向量的系統(tǒng)方程可寫成這可以用4個水庫聯(lián)合運行為例加以說明。4個水庫具有4個狀態(tài)變量，故為4維(m=4)問題。由于每一個水庫時段末的狀態(tài)不僅和它自己時段初的狀態(tài)、本時段的決策有關(guān)，而且與所有其他3個水庫時段初狀態(tài)和本時段決策有關(guān)。*/57一、動態(tài)規(guī)劃的數(shù)學模型2．目標函數(shù)動態(tài)規(guī)劃和其他數(shù)學規(guī)劃方法一樣，其數(shù)學模型同樣要包括目標函數(shù)。目標函數(shù)的最優(yōu)準則可以是效益最大化，也可以是費用最小化或其他指標。目標函數(shù)值決定于系統(tǒng)中的狀態(tài)變量和決策變量，設(shè)以F表示目標函數(shù)，則式中，L——每一階段的費用（或效益）； F——系統(tǒng)總費用（或總效益）。若為最小化目標函數(shù)，則寫作*/57一、動態(tài)規(guī)劃的數(shù)學模型3．約束條件

對狀態(tài)變量和決策變量的約束可以根據(jù)實際的限制條件給出。（1）第n階段的狀態(tài)向量sn約束于集合Sn，記為sn

Sn式中，Sn——第n階段的可行狀態(tài)集合。（2）在第n階段狀態(tài)sn時所采用的決策向量dn約束于集合Dn(sn)，記為dn(sn)Dn(sn)式中，Dn(sn)——在第n階段狀態(tài)sn的可行決策集合。*/57一、動態(tài)規(guī)劃的數(shù)學模型4．邊界條件指初始狀態(tài) s1＝C1

或終末狀態(tài) sn＝CN式中C1，CN——已知常數(shù)。凡問題的初始狀態(tài)已知，則稱為初值問題；而終末狀態(tài)已知的問題則稱終值問題；如初始和終末狀態(tài)均已知，則稱邊值問題。動態(tài)規(guī)劃就是要在系統(tǒng)方程、約束條件、邊界條件約束下，尋求目標函數(shù)最優(yōu)值和相應的最優(yōu)決策序列。*/57二、動態(tài)規(guī)劃的求解方法求解動態(tài)規(guī)劃數(shù)學模型，主要是反復使用速推方程進行擇優(yōu)計算，并由給定的初始狀態(tài)開始反演，以確定最優(yōu)策略。若實際問題中的階段變量、狀態(tài)變量和決策變量是離散的，就按原離散值計算；

若這些變量是連續(xù)的，則可在其可行域內(nèi)離散為有限個數(shù)值。設(shè)階段變量離散為n=l，2，…，N；任一階段n的狀態(tài)sn離散為T1個點，記為sni，i=1，…，T1；狀態(tài)sn上的決策dn離散為T2個值，記為dnj，j=1，…，T2。1．由最后階段開始逐階段進行遞推計算在每個階段n（n=1，…，N），對每一個離散狀態(tài)sni

(i=1，…，T1），都要使用所有的可行決策dnj（j=1，…，T2）。對任何一個指定的離散狀態(tài)sni，都須進行下列工作，以便選定最優(yōu)決策。*/57二、動態(tài)規(guī)劃的求解方法（1）由給定的sni和dnj

，求得相應的L（sni，dnj）。（2）由該sni和dnj，用系統(tǒng)方程計算sn+1j，并求出由該狀態(tài)sn+1j開始的n+l余留過程的最小總費用fn+1*(sn+1j)。應當指出:

若sn+1j在給定的離散狀態(tài)點上，則fn+1*(sn+1j)可以由n+1階段計算結(jié)果直接查到；

若sn+1j不在離散狀態(tài)點上，則fn+1*(sn+1j)須進行內(nèi)插。*/57二、動態(tài)規(guī)劃的求解方法（3）由遞推方程計算使用dnj時的余留過程總費用fn(sni,dnj)=L(sni,dnj)+fn+1*(sn+1j)當T2個決策都使用之后，將所有的fn(sni,dnj)進行比較，取其中最小者為該指定狀態(tài)sni開始的余留過程的最小總費用fn*(sni)，其相應的dnj為最優(yōu)決策dn*。將fn*(sni)記入計算機內(nèi)存，供n-l階段計算使用；同時存貯dn*，供決策反演時使用。至此，便結(jié)束這個離散化狀態(tài)sni的計算。一個指定的sni算完后．接著依次進行其他離散狀態(tài)點的計算。所有的sni（i=1，…，T1）都算完之后，n階段計算結(jié)束，隨即轉(zhuǎn)入(n-1)階段計算。*/57二、動態(tài)規(guī)劃的求解方法2．由給定的初始狀態(tài)開始進行決策反演，追尋最優(yōu)策略當遞推計算至第1階段后，由給定的初始狀態(tài)s1開始，按系統(tǒng)方程和各狀態(tài)下的最優(yōu)決策進行反演，直到最后階段N，以得到最優(yōu)策略{d1,d2,…,dN}*、最優(yōu)軌跡{s1,s2,…,sN+1}*和相應的最優(yōu)目標函數(shù)值F*。若初始狀態(tài)非唯一，則將推算的幾個不同的初始狀態(tài)的最小總費用進行比較，取其中最小者為最優(yōu)目標函數(shù)值F*；并由它對應的初始狀態(tài)開始反演求得最優(yōu)策略和最優(yōu)軌跡。一般講來，當初始狀態(tài)已知時，逆序遞推較方便；當終末狀態(tài)已知時，順序遞推較方便。*/57二、動態(tài)規(guī)劃的求解方法下面以灌溉水資源最優(yōu)分配為例，具體說明動態(tài)規(guī)劃數(shù)學模型建立與求解過程。[例2]

某灌區(qū)內(nèi)有N種作物，自水庫引水灌溉，在中等干旱年，水庫可提供水量為Q萬m3，如以水量xn供給第n種作物，所得的凈效益（以產(chǎn)值計）為rn（xn）。問水資源Q在N種作物間如何分配，才能使總的凈效益最大。這是個具有N個決策變量的最優(yōu)分配問題，本來可以用線性規(guī)劃法或非線性規(guī)劃法求解。但是由于灌溉水量與其所產(chǎn)生的效益之間的非線性關(guān)系較為復雜，有時甚至只能用離散的表格形式表示效益函數(shù)，因而在某些情況下用線性規(guī)劃或非線性規(guī)劃求解并不簡便。如把原問題轉(zhuǎn)化為一個動態(tài)的多階段決策過程問題，即把同時對各種作物進行水資源最優(yōu)分配問題看做分階段依次對各種作物進行水資源分配的問題，這樣便可使用動態(tài)規(guī)劃法求解。（一）建立數(shù)學模型1．階段變量

每種作物為一個用水單位，可看做一個階段，共有N個階段，階段變量n=l,2,…,N。2．狀態(tài)變量和決策變量

狀態(tài)變量為各階段可用于分配的有效水量，以q表示；決策變量為供給每種作物的水量，即各階段的供水量，以xn表示。3．系統(tǒng)方程

根據(jù)狀態(tài)變量和決策變量之間關(guān)系推得該問題的系統(tǒng)方程（即狀態(tài)轉(zhuǎn)移方程）為qn+1=qn-xn*/57二、動態(tài)規(guī)劃的求解方法4.目標函數(shù)

設(shè)F*(Q)以水資源Q分配給N種作物而獲得的最大總凈效益，則5．約束條件(1)供給各種作物水量之和不超過水資源總量Q(2)供給第n種作物的水量xn不能超過在第n階段可用于分配的有效水量qn，而且非負數(shù) 0≤xn≤qn n=1，2，…,N（3）qn不能超過水資源總量Q，也是非負數(shù)

0≤qn≤Q

n=1，2，…,N+16.初始條件

q1＝Q采用逆序遞推求解上述數(shù)學模型，其追推方程為（二）計算過程

（見Excell文件）*/57二、動態(tài)規(guī)劃的求解方法由動態(tài)規(guī)劃的解算方法可以看出，為進行遞推計算，在高速存貯（內(nèi)存）中至少須存貯相鄰兩個階段所有可行狀態(tài)(sn與sn+1）的后部子過程的最小總費用（或最大總效益）fn*(sn)和fn+1*(sn+1)，其中一個階段所需內(nèi)存量為Tn，則兩個階段內(nèi)存需要量為2Tn。

式中， Ti——第i狀態(tài)變量的離散點數(shù); m——狀態(tài)向量維數(shù)，即狀態(tài)變量數(shù)； ∏——連乘符號。若各狀態(tài)變量之離散點數(shù)均為Ti，則Tn＝Tim設(shè)Ti=100，當m=4時，Tn=108，這個數(shù)目已超過現(xiàn)有計算機的內(nèi)存能力。由此可見，盡管動態(tài)規(guī)劃同枚舉法相比，在計算量上有顯著節(jié)省，但由于它需要的存貯量和計算時間隨狀態(tài)向量的維數(shù)(m)呈指數(shù)增長，當維數(shù)高于4或5時，它需要的計算機存貯量可能會超出現(xiàn)有計算機的存貯能力；而且需花費大量的計算時間。這就是動態(tài)規(guī)劃廣泛應用的主要障礙——維數(shù)災。*/57第三節(jié)多維動態(tài)規(guī)劃簡介在動態(tài)規(guī)劃數(shù)學模型中，如有兩個或兩個以上狀態(tài)變量，或者在每一階段需要選擇兩個或兩個以上決策變量時，便構(gòu)成多維動態(tài)規(guī)劃問題。多維問題原則上可以用第二節(jié)所述方法求解，但由于計算機存貯量和計算量隨狀態(tài)向量維數(shù)增加呈指數(shù)增長，使得動態(tài)規(guī)劃廣泛應用受到限制。自動態(tài)規(guī)劃問世以來，為解決“維數(shù)災”問題，R．E．貝爾曼及其他學者提出了一些改進方法，這些方法可以歸納為幾種途徑。本節(jié)首先介紹多維動態(tài)規(guī)劃問題的一般數(shù)學表達和求解方法的改進途徑，然后介紹應用較為普遍的具有代表性的兩種求解方法：動態(tài)規(guī)劃逐次漸近法（DynamicprogrammingSuccessiveApproximation，縮寫為DPSA）和離散微分動態(tài)規(guī)劃法（DiscreteDifferentialDynamicProgramming，縮寫為DDDP）*/57一、多維動態(tài)規(guī)劃問題的數(shù)學模型與求解方法的改進途徑（一）數(shù)學模型

考慮一個時間離散的動態(tài)系統(tǒng),階段變量順序編號,且階段號碼與階段初一致。系統(tǒng)方程

s(n+1)＝g[s(n),d(n)]n=0,1,2,…,N-1

式中，n——階段序號；

S(n)——第n階段的m維狀態(tài)向量，s(n)=(s1(n),s2(n),…sm(n))T；

d(n)——第n階段的q維決策向量，d(n)=(d1(n),d2(n),…dq(n))T；

g——m維向量函數(shù)，即狀態(tài)轉(zhuǎn)移函數(shù)。目標函數(shù)設(shè)為費用最小化，即

式中，F(xiàn)——系統(tǒng)總費用；

L[s(n),d(n)]——系統(tǒng)在s(n)狀態(tài)下，由決策d(n)所產(chǎn)生的第n階段費用。約束條件

s（n）

S（n），n=0，1，…，N

d（n）

D（s，n），n＝0，1，…，N－1

式中，S（n）——階段n的可行狀態(tài)集合；

D（s，n）——階段n上狀態(tài)s的可行決策集合。邊界條件已知系統(tǒng)始端或終端的m維狀態(tài)向量如下

s（0）＝C（0） s（N）＝C（N）*/57一、多維動態(tài)規(guī)劃問題的數(shù)學模型與求解方法的改進途徑以動態(tài)規(guī)劃的向后計算法（逆序遞推）為代表，寫出其遞推方程式中，fn*[s(n)]——由狀態(tài)s(n)開始直到終端的后部子過程最小總 費用；fn+1*[s(n+1)]——由狀態(tài)s(n+1)開始直到終端的后部子過程最小總費用,當s(n+1)不在具有已知最小總費用fn+1*[s(n+1)]的離散狀態(tài)點上時，上式右端第2項須內(nèi)插求得；Ln[s(n),d(n)]——意義同前；

[s(N)]——僅與終端狀態(tài)S(N)有關(guān)的邊值函數(shù)。*/57一、多維動態(tài)規(guī)劃問題的數(shù)學模型與求解方法的改進途徑（二）求解方法的改進途徑前已述及，使用常規(guī)動態(tài)規(guī)劃求解多維問題，需要的內(nèi)存量Tn和計算量隨問題維數(shù)的增加呈指數(shù)增長，即

Tn=Tim維數(shù)很高時，會超過計算機的存貯能力，或使運算費用昂貴。故在貝爾曼提出動態(tài)規(guī)劃后，一些學者又提出了各種改進方法，用來求解多維問題。這些方法大多是通過下列3種途徑來減少存貯量和計算量。（1）降低維數(shù)m。如動態(tài)規(guī)劃逐次漸近法（DPSA）、聚合分解法（AD）等。（2）減少每次計算的離散狀態(tài)點數(shù)Ti。如離散微分動態(tài)規(guī)劃法（DDDP）、雙狀態(tài)動態(tài)規(guī)劃法（BSDP）等。（3）狀態(tài)變量不離散。如微分動態(tài)規(guī)劃法（DDP）、漸近優(yōu)化算法（POA）等。本節(jié)僅以動態(tài)規(guī)劃逐次漸近法和離散微分動態(tài)規(guī)劃法為代表，介紹多維問題的求解方法。*/57二、動態(tài)規(guī)劃逐次漸近法（DPSA）簡介（一）基本思路該法由貝爾曼提出，其基本思想是把包含若干決策變量的問題，變?yōu)閮H僅包含一個決策變量的若干子問題，每個子問題比原來的問題具有較少的狀態(tài)變量，因而可減少高速存貯量，所以它是一種降維方法。當狀態(tài)變量數(shù)和決策變量數(shù)相等（m=q）時，每個子問題只有一個狀態(tài)變量。為了便于說明這個方法，下面就以這種情況為例進行介紹。數(shù)學模型如“數(shù)學模型”部分所表達，且m=q。*/57二、動態(tài)規(guī)劃逐次漸近法（DPSA）（二）求解方法首先假設(shè)一個由s（0）=C（0）開始的虛擬狀態(tài)序列（稱為虛擬軌跡）{si0(n)},n=0,1,…,N;i=1,2,…,m。相應的決策序列（即策略）為{di0(n)},n=0,1,…,N-1;i=1,2,…,m。其中s和d的右上角數(shù)字表示迭代次數(shù)；右下角i表示狀態(tài)變量或決策變量的序號。從m個狀態(tài)變量中挑選一個如s1（s1表示第1個狀態(tài)變量）為狀態(tài)變量，而所有其他狀態(tài)序列｛si0(n)｝，i≠1，假設(shè)固定不變，則這個問題在任一階段n只有一個狀態(tài)變量s1(n)。決策向量d(n)仍有m個分量，但由于（m-1）維狀態(tài)必須保持固定不變，可以通過系統(tǒng)方程，將決策向量d(n)用相鄰兩個階段的狀態(tài)向量s(n)和s(n+1)表示，使各階段已知的（m-1）維狀態(tài)構(gòu)成對d(n)的(m-1)個附加約束，所以真正起作用的決策變量也只有一個。這樣就把原來的m維問題簡化成一維問題。對于這個一維問題用動態(tài)規(guī)劃（DP）求解，得到一個新的決策序列{d’(n)}和新的狀態(tài)序列{s’(n)}。然后，另選一個狀態(tài)變量，如s2，重復以上最優(yōu)化過程，直到每個狀態(tài)變量對于這個最優(yōu)化過程至少被選了一次；并且當針對任一狀態(tài)變量進行最優(yōu)化都得到相同的決策序列和狀態(tài)序列時，便結(jié)束計算。*/57二、動態(tài)規(guī)劃逐次漸近法（DPSA）這一方法大大節(jié)省了計算機存貯量和計算時間，但不能保證在所有情況下都收斂到真正的最優(yōu)解。貝爾曼曾建議若干方法增加尋找真正最優(yōu)解的可能性，例如由一些不同的虛擬軌跡開始等。事實上，如果虛擬軌跡充分接近最優(yōu)軌跡，就會收斂到這個最優(yōu)軌跡。上述基本原理同樣適用于決策向量維數(shù)q不等于狀態(tài)向量維數(shù)m的問題。對于q小’于m的問題，可把原問題分成q個子問題，每個子問題包含一個決策變量和少于m個的狀態(tài)變量。對于q大于m的問題，也是按決策變量劃分子問題，在很多情況下，每個子問題中只包含一個決策變量和一個狀態(tài)變量，可按一維問題求解。*/57三、離散微分動態(tài)規(guī)劃法（DDDP）簡介（一）基本思路DDDP法系由黑達利（Heidari）、周文德等人在微分動態(tài)規(guī)劃（DDP）的理論基礎(chǔ)上提出的一種迭代方法。它是由一個滿足給定的約束條件和邊界條件的初始試驗軌跡開始，并在這個試驗軌跡的某個鄰域內(nèi)將狀態(tài)離散化；然后使用動態(tài)規(guī)劃的遞推方程，在各離散狀態(tài)間尋找一個改善軌跡；并以此作為下次迭代的試驗軌跡，重復進行，直到尋找出最優(yōu)軌跡為止。由于每次選代計算中各階段的離散狀態(tài)點數(shù)很少，從而大大減小了存貯量和計算時間。DDDP法的數(shù)學模型見“數(shù)學模型”部分。*/57三、離散微分動態(tài)規(guī)劃法（DDDP）（二）DDDP的求解方法（1）首先假設(shè)一個滿足約束條件的初始試驗策略

｛d0（n）｝，n=0，l，…，N-1，并根據(jù)該初始試驗策略由系統(tǒng)方程確定各階段的狀態(tài)向量，該狀態(tài)向量序列稱做初始試驗軌跡，以｛s0（n）｝，n=0,1,…,N表示，它必須滿足約束和邊界條件。由｛s0（n）｝和｛d0（n）｝求得系統(tǒng)總費用F0。并將{s0(n)}和{d0(n)}作為第1次迭代的試驗軌跡{sk(n)}和試驗策略｛dk（n）｝(k為迭代次數(shù)，第1次迭代k=1）。若系統(tǒng)方程可逆，也可先假設(shè)初始試驗軌跡｛s0（n）｝，再由過系統(tǒng)方程求得相應的初始試驗策略｛d0（n）｝。*/57三、離散微分動態(tài)規(guī)劃法（DDDP）（2）若每個狀態(tài)變量離散為T個狀態(tài)點，則m維狀態(tài)向量共有Tm個離散狀態(tài)點，因而在任一階段n須選擇Tm個狀態(tài)增量?sj（n），j=1，…，Tm。在試驗軌跡的周圍，用｛sk（n）+?sj（n）}

{S(n)}形成Tm個離散狀態(tài)點，這些狀態(tài)點便構(gòu)成本次迭代的狀態(tài)域。如果所研究的動態(tài)系統(tǒng)具有m個狀態(tài)變量（m維狀態(tài)向量），則每個增量上?sj（n）都是一個m維向量，即*/57式中，n——階段序號；

j——第n階段所建立的狀態(tài)點序號，下頁圖(a)、(b)分別表示m=1、T=3和m=2、T=3時狀態(tài)域內(nèi)網(wǎng)點分布；

i——第n階段第j個狀態(tài)點之增量向量中的分量序號，與狀態(tài)變量編號一致。一般初始增量選得較大，以后逐漸縮小，據(jù)經(jīng)驗，每個狀態(tài)變量離散點數(shù)T=3～7個即可。將?sj(n)加到階段n的試驗軌跡上，就形成了階段n的m維狀態(tài)子域C(n):{?sk(n)+?sj(n)}

S(n)

，圖(b)表示一個M維問題n=1和n=2時的子域C(1)和C(2)。階段1～N的狀態(tài)子域總體即狀態(tài)域C，常稱C為廊道。三、離散議分動態(tài)規(guī)劃法（DDDP）*/57三、離散微分動態(tài)規(guī)劃法（DDDP）（3）在廊道C中，使用常規(guī)動態(tài)規(guī)劃法尋求最小費用Fk，并進行反演求得最優(yōu)軌跡{sk(n)}*和最優(yōu)策略{dk(n)}*。由于不是在整個可行域內(nèi)尋優(yōu)，這個{sk(n)}*和{dk(n)}*還不是真正的最優(yōu)解，僅僅是改善軌跡和改善策略。上述包括廊道的形成，針對廊道內(nèi)狀態(tài)的優(yōu)化，以及為了獲得整個系統(tǒng)的改善軌跡而進行反演的過程叫做一次迭代。（4）以本次（第k次）迭代求得的{sk(n)}*和{dk(n)}*作為下次（第k＋1次）迭代之試驗軌跡和試驗策略，即

{sk+1(n)}=

{sk(n)}*

n=0，l，2，…，N

{dk+1(n)}=

{dk(n)}*

n=0，l，2，…，N-1并將本次選代與前次迭代求得之最小總費用進行比較:a.

當其相對誤差小于預先規(guī)定的允許誤差

1，即

|Fk-Fk-1|／Fk-1≤

1

時，便減小增量?sj(n)，在新的試驗軌跡周圍建立起較小的廊道；b.否則，仍采用原來的增量在新試驗軌跡周圍建立廊道。無論是否減小增量，都重復第（2）、（3）、（4）步，進行下一次迭代。*/57三、離散微分動態(tài)規(guī)劃法（DDDP）（5）如此迭代下去，并再三地減小整個系統(tǒng)的?sj(n)，直到?sj(n)小于一個規(guī)定值?；并且前后兩次選代最小總費用之相對誤差也小于允許誤差

2（

2≤

1），便結(jié)束這個初始試驗策略｛d0（n）｝和初始試驗軌跡｛s0（n）｝的迭代。最后一次選代所得最優(yōu)解就是原問題的最優(yōu)解，包括最優(yōu)策略｛d（n）｝*、最優(yōu)軌跡｛s（n）｝*和最優(yōu)目標函數(shù)值F*。（6）由于動態(tài)規(guī)劃求解的問題不一定是凸規(guī)劃問題，只從一個初始試驗策略開始求得的最優(yōu)解不能保證是全局最優(yōu)解。因此須假設(shè)幾個不同的初始試驗策略和相應的初始試驗軌跡，進行上述（1）～（5）步計算，求得幾個相應的最優(yōu)解。一般選擇其中總費用最小者為采用的最優(yōu)解；當然，也可以根據(jù)社會、政治和經(jīng)濟等各方面因素，選擇其中某一個為采用的最優(yōu)解。由DDDP法的解算步驟可以看出，它不需要在狀態(tài)變量的整個可行域內(nèi)擇優(yōu)，而只要在試驗軌跡的某個鄰域（即廊道C）內(nèi)很少的幾個離散狀態(tài)點上擇優(yōu)，因而可大大節(jié)省存貯量和計算時間，為求解多維問題提供了條件。*/57四、系統(tǒng)方程的可逆性前已述及，當用系統(tǒng)方程轉(zhuǎn)移到的s(n+1)不在事先離散的狀態(tài)點上時，遞推方程右端第2項要進行內(nèi)插，對高維系統(tǒng)而言，這種內(nèi)插常產(chǎn)生不精確的結(jié)果，并且需要大量的計算時間。而可逆系統(tǒng)可以避免這種內(nèi)插。1．可逆系統(tǒng)方程如果一個動態(tài)系統(tǒng)方程組的反函數(shù)存在且唯一，則可根據(jù)狀態(tài)向量與決策向量的函數(shù)關(guān)系，從由決策向量表達的系統(tǒng)方程中解出決策向量，這樣的系統(tǒng)方程稱為可逆的系統(tǒng)方程。根據(jù)方程組的反函數(shù)存在定理可以推得：若一個系統(tǒng)的狀態(tài)向量維數(shù)等于決策向量維數(shù)（即m=q），并且對任一階段n，系統(tǒng)方程s1(n+1)=g1[s(n),d(n)]

s2(n+1)=g2[s(n),d(n)]

……

si(n+1)=gi[s(n),d(n)]

……

sm(n+1)=gm[s(n),d(n)]的(i,j=1,…,m)所形成的矩陣都是非奇異陣，則該系統(tǒng)方程是可逆的，因而能通過狀態(tài)向量解出決策向量*/57四、系統(tǒng)方程的可逆性 d1(n)=

1[s(n),s(n+1)]

d2(n)=

2[s(n),s(n+1)]

……

di(n)=

i[s(n),s(n+1)]

……

dm(n)=

m[s(n),s(n+1)]對于可逆的系統(tǒng)方程，可以對指定的離散狀態(tài)s(n)和s(n+1)，用上式(5－66)去計算第n階段的各個決策。然后檢查這些決策，看它們是否符合給定的約束條件。如果一個階段有Tm個狀態(tài)點，對每個指定狀態(tài)s(n)的擇優(yōu)計算，要考慮所有的狀態(tài)s(n＋1)，那么根據(jù)系統(tǒng)方程的可逆性，一個狀態(tài)有Tm個可能決策。前圖給出一個m=2、T=3的系統(tǒng)的可能決策（共9個）。當這Tm個決策應用于遞推方程時，由于s(n+1)是指定的離散狀態(tài)，其相應的最小費用fn+1*[s(n+1)]已在（n＋1）階段擇優(yōu)計算中求得，不須插補fn+1*[s(n+1)]項，而可直接計算fn*[s(n)]。這樣就消除了由插補所產(chǎn)生的誤差，并減少了計算時間。對多維系統(tǒng)來說，其精確度和計算速度遠遠超過帶有插補的那些方法。*/57s1(n+1)=g1[s(n),d(n)]

s2(n+1)=g2[s(n),d(n)]

……

si(n+1)=gi[s(n),d(n)]

……

sm(n+1)=gm[s(n),d(n)]四、系統(tǒng)方程的可逆性*/57四、系統(tǒng)方程的可逆性2．灌溉水庫群系統(tǒng)中系統(tǒng)方程的可逆性

以灌溉水庫群為代表的灌溉水資源系統(tǒng)中之系統(tǒng)方程一般是可逆的。這是由于系統(tǒng)方程中第i個分量可以寫成

si(n+1)=si(n)+yi(n)-di(n)-ui(n)i=1，2，…，m

式中，i——水庫序號，i=1，2，…，m；

si（n）——第i水庫第n階段初蓄水量，為狀態(tài)變量；

di（n）——第i水庫第n階段的放水量，為決策變量；

yi（n）——第i水庫第n階段的入庫徑流量；

ui（n）——第i水庫第n階段的蒸發(fā)和滲漏損失量。上式代表由m個分量組成的系統(tǒng)方程，當i=j=1，2，…，m時，其

由所形成的矩陣為非奇異陣，所以系統(tǒng)方程是可逆的。若損失忽略不計，就可將上式中d(n)表示為

di(n)=si(n)-si(n+1)+yi(n)=

i[si(n),si(n+1),yi(n)]這樣，在對第n階段狀態(tài)si(n)選擇最優(yōu)決策時，就可指定具有fn+1*[s(n+1)]的狀態(tài)si(n+1)，由上式求出di(n)，遞推方程右端第2項fn+1*[s(n+1)]就不需內(nèi)插了。*/57動態(tài)規(guī)劃第一節(jié)動態(tài)規(guī)劃的基本原理一、動態(tài)規(guī)劃的基本概念二、遞推方程與最優(yōu)化原理第二節(jié)動態(tài)規(guī)劃的數(shù)學模型和求解方法一、動態(tài)規(guī)劃的數(shù)學模型二、動態(tài)規(guī)劃的求解方法第三節(jié)多維動態(tài)規(guī)劃簡介一、多維動態(tài)規(guī)劃問題的數(shù)學模型與求解方法的改進途徑二、動態(tài)規(guī)劃逐次漸近法三、離散微分動態(tài)規(guī)劃法四、系統(tǒng)方程的可逆性*/57*/57THANKYOU謝謝多目標規(guī)劃方法

多目標規(guī)劃及其求解技術(shù)簡介目標規(guī)劃方法

§1多目標規(guī)劃及其求解技術(shù)簡介

一、多目標規(guī)劃及其非劣解二、多目標規(guī)劃求解技術(shù)簡介一、多目標規(guī)劃及其非劣解

(1)多目標規(guī)劃數(shù)學模型其數(shù)學模型可以描寫為為規(guī)劃決策變量向量是K維函數(shù)；是m維函數(shù)向量；G是m維的常數(shù)向量，m是約束條件個數(shù)?？梢赃M一步寫作:A為k*n矩陣，B為m*n矩陣，b為m維向量，X為n維決策變量向量.（2）多目標規(guī)劃的非劣解

對于上述多目標規(guī)劃問題，求解就意味著需要做出如下的復合選擇：▲每一個目標函數(shù)取什么值，原問題可以得到最滿意的解決？▲每一個決策變量取什么值，原問題可以得到最滿意的解決？多目標規(guī)劃問題的求解不能只追求一個目標的最優(yōu)化（最大或最小），而不顧其它目標。非劣解：可以用圖5.1.1說明。圖5.1.1多目標規(guī)劃的劣解與非劣解非劣解是指這樣的方案(記作A),在可行解集中我們再也找不到另一方案B,方案B的各目標函數(shù)值(屬性值)都不劣于方案A的相應目標值，而且B至少有一個目標比方案A優(yōu)。多目標規(guī)劃的解之間無法確定優(yōu)劣，但沒有比它們更好的其他方案，所以它們就被稱之為多目標規(guī)劃問題的非劣解或有效解,其余方案都稱為劣解。所有非劣解構(gòu)成的集合稱為非劣解集。二、多目標規(guī)劃求解技術(shù)簡介

多目標規(guī)劃問題的求解，就是要在非劣解集中尋求一個最為滿意的規(guī)劃方案。解決這一問題，常常需要將多目標規(guī)劃問題轉(zhuǎn)化為單目標規(guī)劃問題去處理。實現(xiàn)這種轉(zhuǎn)化，有如下幾種建模方法。效用最優(yōu)化模型建摸依據(jù)：規(guī)劃問題的各個目標函數(shù)可以通過一定的方式進行求和運算。這種方法將一系列的目標函數(shù)與效用函數(shù)建立相關(guān)關(guān)系，各目標之間通過效用函數(shù)協(xié)調(diào)，使多目標規(guī)劃問題轉(zhuǎn)化為傳統(tǒng)的單目標規(guī)劃問題：

maxZ=(X)

(X)≤G

是與各目標函數(shù)相關(guān)的效用函數(shù)的和函數(shù)。在用效用函數(shù)作為規(guī)劃目標時，需要確定一組權(quán)值

i來反映原問題中各目標函數(shù)在總體目標中的權(quán)重，即：式中，諸

i應滿足：若采用向量與矩陣 max

=

T

(X)≤G罰款模型

規(guī)劃決策者對每一個目標函數(shù)都能提出所期望的值（或稱滿意值）fi*通過比較實際值fi與期望值fi*之間的偏差來選擇問題的解，其數(shù)學表達式如下：或?qū)懗删仃囆问剑簃inZ=(F-F*)TA(F-F*) (X)≤G在上式中，ai是與第i個目標函數(shù)相關(guān)的權(quán)重；A是由ai(i=1,2,...,k)諸組成的m×m對角矩陣。目標規(guī)劃模型

也需要預先確定各個目標的期望值fi*。目標規(guī)劃模型的數(shù)學形式為：在上式中，fi+和fi-分別表示與fi相應的、與fi*相比的目標超過值和不足值。采用矩陣形式可記為 minZ=T(F++F-) (X)≤G F+F--F+=F*

表示各元素均為1的k維列向量。約束模型

理論依據(jù)：若規(guī)劃問題的某一目標可以給出一個可供選擇的范圍，則該目標就可以作為約束條件而被排除出目標組，進入約束條件組中。假如，除第一個目標外，其余目標都可以提出一個可供選擇的范圍，則該多目標規(guī)劃問題就可以轉(zhuǎn)化為單目標規(guī)劃問題：

采用矩陣可記為：§2

目標規(guī)劃方法一、目標規(guī)劃模型

二、求解目標規(guī)劃的單純形方法一、目標規(guī)劃模型

基本思想：給定若干目標以及實現(xiàn)這些目標的優(yōu)先順序，在有限的資源條件下，使總的偏離目標值的偏差最小。下面通過例子來介紹目標規(guī)劃的有關(guān)概念及數(shù)學模型。例1：某一個企業(yè)利用某種原材料和現(xiàn)有設(shè)備可生產(chǎn)甲、乙兩種產(chǎn)品，其中，甲、乙兩種產(chǎn)品的單價分別為8元和10元；生產(chǎn)單位甲、乙兩種產(chǎn)品需要消耗的原材料分別為2個單位和1個單位，需要占用的設(shè)備分別為1臺時和2臺時；原材料擁有量為11個單位；可利用的設(shè)備總臺時為10臺時。試問：如何確定其生產(chǎn)方案？解：如果決策者所追求的唯一目標是使總產(chǎn)值達到最大，則這個企業(yè)的生產(chǎn)方案可以由如下的線性規(guī)劃模型給出：求x1，x2使

maxZ=8x1+10x2

且滿足： 2x1+x2≤11 x1+2x2≤10 x1,x2≥0則可用單純形法求得最佳方案x1*=4,x2*=3,Z*=62但是，在實際決策時，企業(yè)領(lǐng)導者必須考慮市場等一系列其它條件，如：根據(jù)市場信息，甲種產(chǎn)品的需求量有下降的趨勢，因此甲種產(chǎn)品的產(chǎn)量不應大于乙種產(chǎn)品的產(chǎn)量。超過計劃供應的原材料，需用高價采購，這就會使生產(chǎn)成本增加。應盡可能地充分利用設(shè)備的有效臺時，但不希望加班。應盡可能達到并超過計劃產(chǎn)值指標56元。這樣，該企業(yè)生產(chǎn)方案的確定，便成為一個多目標決策問題，這一問題可以運用目標規(guī)劃方法進行求解。偏差變量

在目標規(guī)劃數(shù)學模型中，除了決策變量外，還需要引入正、負偏差變量d+、d-。正偏差變量d+表示決策值超過目標值的部分;負偏差變量d-表示決策值未達到目標值的部分。因為決策值不可能既超過目標值同時又未達到目標值，故恒有d+×d-＝0成立。目標規(guī)劃模型的有關(guān)概念絕對約束和目標約束絕對約束，是指必須嚴格滿足的等式約束和不等式約束，譬如，線性規(guī)劃問題的所有約束條件都是絕對約束，不能滿足這些約束條件的解稱為非可行解,所以它們是硬約束。目標約束是目標規(guī)劃所特有的，我們可以將約束方程右端項看作是追求的目標值，在達到此目標值時允許發(fā)生正或負偏差，因此在這些約束條件中加入正、負偏差變量，它們是軟約束。線性規(guī)劃問題的目標函數(shù)，在給定目標值和加入正、負偏差變量后可變換為目標約束，也可以根據(jù)問題的需要將絕對約束變換為目標約束。譬如，上例線性問題中的目標函數(shù)Z=8x1+10x2可變換為目標約束8x1+10x2+d1--d1+=56，絕對約束2x1+x2≤11可變換為2x1+x2+d2--d2+=11。優(yōu)先因子（優(yōu)先等級）與權(quán)系數(shù)：決策者對各個目標的考慮,有主次或輕重緩急。凡要求第一位達到的目標賦予優(yōu)先因子P1，次位的目標賦予優(yōu)先因子P2,...,并規(guī)定Pk>>Pk+1(k=1,2,...,K)表示Pk比Pk+1有更大的優(yōu)先權(quán)。若要區(qū)別具有相同優(yōu)先因子Pk的目標的差別，就可以分別賦予它們不同的權(quán)系數(shù):目標函數(shù)目標規(guī)劃的目標函數(shù)（準則函數(shù)）是按照各目標約束的正、負偏差變量和賦予相應的優(yōu)先因子而構(gòu)造的。當每一目標確定后，盡可能縮小與目標值的偏離。因此，目標規(guī)劃的目標函數(shù)只能是：

minZ=f(d+,d-)其基本形式有三種：①要求恰好達到目標值，就是正、負偏差變量都要盡可能小,即

minZ=f(d+＋d-)②要求不超過目標值，即允許達不到目標值，就是正偏差變量要盡可能小，即

minZ=f(d+)③要求超過目標值，也就是超過量不限，但負偏差變量要盡可能小，即

minZ=f(d-)例2：在例1中，如果決策者在原材料供應受嚴格控制的基礎(chǔ)上考慮：首先是甲種產(chǎn)品的產(chǎn)量不超過乙種產(chǎn)品的產(chǎn)量；其次是充分利用設(shè)備的有限臺時，不加班；再次是產(chǎn)值不小于56元。并分別賦予這三個目標優(yōu)先因子P1,P2,P3。試建立該問題的目標規(guī)劃模型。解：根據(jù)題意，這一決策問題的目標規(guī)劃模型是maxZ=8x1+10x22x1+x2≤11x1+2x2≤10x1,x2≥0假定有L個目標，K個優(yōu)先級(K≤L)，n個變量。在同一優(yōu)先級中不同目標的正、負偏差變量的權(quán)系數(shù)分別為、，則多目標規(guī)劃問題可以表示為：目標規(guī)劃模型的一般形式目標函數(shù)目標約束絕對約束非負約束非負約束二、求解目標規(guī)劃的單純形方法

目標規(guī)劃模型仍可以用單純形方法求解，在求解時作以下規(guī)定：①因為目標函數(shù)都是求最小值，所以，最優(yōu)判別檢驗數(shù)為：②因為非基變量的檢驗數(shù)中含有不同等級的優(yōu)先因子，所以檢驗數(shù)的正、負首先決定于P1的系數(shù)a1j的正、負，若a1j=0，則檢驗數(shù)的正、負就決定于P2的系數(shù)a2j的正、負，下面可依此類推。

計算步驟：①建立初始單純形表，在表中將檢驗數(shù)行按優(yōu)先因子個數(shù)分別排成K行，置K=1。

②檢查該行中是否存在負數(shù)，且對應的前K-1行的系數(shù)是零。若有，取其中最小者對應的變量為換入變量，轉(zhuǎn)③。若無負數(shù)，則轉(zhuǎn)⑤。③按最小比值規(guī)則（

規(guī)則）確定換出變量，當存在兩個和兩個以上相同的最小比值時，選取具有較高優(yōu)先級別的變量為換出變量。④按單純形法進行基變換運算，建立新的計算表，返回②。⑤當k=K時，計算結(jié)束，表中的解即為滿意解。否則置k=K+1，返回②

。例3：試用單純形法求解例2所描述的目標規(guī)劃問題解：首先將這一問題化為如下標準形式：

①取x3,d1-,d2-,d3-為初始基變量，列出初始單純形表1②取K=1，檢查檢驗數(shù)的行P1，因該行無負檢驗數(shù)，故轉(zhuǎn)⑤。⑤因為K=1<K=3，置K=K+1=2，返回②。②檢查檢驗數(shù)P2行中有-1，-2，因為有m