運籌學基礎及應用第五版胡運權(quán)

1、18.1 多階段決策問題8.2 最優(yōu)化原理與動態(tài)規(guī)劃的數(shù)學模型8.3 離散確定性動態(tài)規(guī)劃模型的求解8.4 離散隨機性動態(tài)規(guī)劃模型的求解 8.5 一般數(shù)學規(guī)劃模型的動態(tài)規(guī)劃解法2 理解理解動態(tài)規(guī)劃基本概念、最優(yōu)化原理動態(tài)規(guī)劃基本概念、最優(yōu)化原理和基本方程，逆序法和順序解法，學習應和基本方程，逆序法和順序解法，學習應用動態(tài)規(guī)劃解決多階段決策問題。用動態(tài)規(guī)劃解決多階段決策問題。 重點重點 :掌握動態(tài)規(guī)劃掌握動態(tài)規(guī)劃模型結(jié)構(gòu)模型結(jié)構(gòu)、逆序、逆序法法算法原理、資源分配、設備更新、生產(chǎn)算法原理、資源分配、設備更新、生產(chǎn)與存貯與存貯等問題。等問題。學習要點：學習要點：3第一節(jié)第一節(jié) 多階段的決策問多階段的決

2、策問題題4動態(tài)規(guī)劃動態(tài)規(guī)劃（Dynamic Programming） R. Bellman50年代執(zhí)教于普林斯頓和斯坦福大學，年代執(zhí)教于普林斯頓和斯坦福大學，后進入蘭德（后進入蘭德（Rand）研究所。）研究所。1957年發(fā)表年發(fā)表“Dynamic Programming”一書，標識動態(tài)規(guī)劃的正式誕生。一書，標識動態(tài)規(guī)劃的正式誕生。 動態(tài)規(guī)劃的基本概念和定義動態(tài)規(guī)劃的基本概念和定義 動態(tài)規(guī)劃的研究對象和引例動態(tài)規(guī)劃的研究對象和引例 動態(tài)規(guī)劃是解決復雜系統(tǒng)優(yōu)化問題的一種方法。動態(tài)規(guī)劃是解決復雜系統(tǒng)優(yōu)化問題的一種方法。是解決是解決動態(tài)系統(tǒng)多階段決策動態(tài)系統(tǒng)多階段決策過程的基本方法之一過程的基本方法之

3、一。5 動態(tài)規(guī)劃：動態(tài)規(guī)劃：是解決是解決多階段決策多階段決策過程過程最優(yōu)最優(yōu)化問題的一種方法，無特定的數(shù)學模型。化問題的一種方法，無特定的數(shù)學模型?？山鉀Q可解決 與時間有關(guān)的動態(tài)問題與時間有關(guān)的動態(tài)問題 與時間無關(guān)的靜態(tài)問題與時間無關(guān)的靜態(tài)問題6多階段決策問題n 1）動態(tài)決策動態(tài)決策將將時間作為變量時間作為變量的決策問題稱的決策問題稱為動態(tài)決策。其基本特點是多次決策。為動態(tài)決策。其基本特點是多次決策。n 2）多階段多階段決策問題是一類特殊形式的動態(tài)決決策問題是一類特殊形式的動態(tài)決策問題。是指這樣一類活動過程：系統(tǒng)的動態(tài)策問題。是指這樣一類活動過程：系統(tǒng)的動態(tài)過程可以按照時間進程分為狀態(tài)過程可以

4、按照時間進程分為狀態(tài)互相聯(lián)系而又互相聯(lián)系而又互相區(qū)別互相區(qū)別的各個階段，而且在每個階段都要進的各個階段，而且在每個階段都要進行決策，當每一個階段的決策確定以后，就完行決策，當每一個階段的決策確定以后，就完全確定了一個過程的活動路線。全確定了一個過程的活動路線。712345引例引例1 最短路線問題最短路線問題25375632455114633334C1C3D1AB1B3B2D2EC28引例引例2 生產(chǎn)與存貯問題生產(chǎn)與存貯問題要求確定一個逐月的生產(chǎn)計劃，在滿足需求條件下，要求確定一個逐月的生產(chǎn)計劃，在滿足需求條件下，使一年的生產(chǎn)與存貯費用之和最??？使一年的生產(chǎn)與存貯費用之和最小？ 引例引例3 投資

5、決策問題投資決策問題某公司現(xiàn)有資金某公司現(xiàn)有資金Q萬元，在今后萬元，在今后5年內(nèi)考慮給年內(nèi)考慮給A，B，C，D 4個項目投資？個項目投資？引例引例4 設備更新問題設備更新問題現(xiàn)企業(yè)要決定一臺設備未來現(xiàn)企業(yè)要決定一臺設備未來8年的更新計劃，問應在年的更新計劃，問應在哪些年更新設備可使總費用最??？哪些年更新設備可使總費用最小？ 9 動態(tài)規(guī)劃方法的特點n 優(yōu)點：1）許多問題用動態(tài)規(guī)劃求解比線性規(guī)劃、非線許多問題用動態(tài)規(guī)劃求解比線性規(guī)劃、非線性規(guī)劃更有效，特別是離散性問題，解析數(shù)學性規(guī)劃更有效，特別是離散性問題，解析數(shù)學無用武之地，而動態(tài)規(guī)劃成為得力工具。無用武之地，而動態(tài)規(guī)劃成為得力工具。2）某些情

6、況下，用動態(tài)規(guī)劃處理不僅能作定性某些情況下，用動態(tài)規(guī)劃處理不僅能作定性描述分析，且可利用計算機給出求其數(shù)值解的描述分析，且可利用計算機給出求其數(shù)值解的方法。方法。10動態(tài)規(guī)劃方法的特點缺點：缺點：n1）沒有統(tǒng)一的處理方法，求解時要根據(jù)問題）沒有統(tǒng)一的處理方法，求解時要根據(jù)問題的性質(zhì)，結(jié)合多種數(shù)學技巧。因此，實踐經(jīng)驗的性質(zhì)，結(jié)合多種數(shù)學技巧。因此，實踐經(jīng)驗及創(chuàng)造性思維將起重要作用。及創(chuàng)造性思維將起重要作用。n2）“維數(shù)障礙維數(shù)障礙”：當變量個數(shù)太多時，由于：當變量個數(shù)太多時，由于計算機內(nèi)存和速度的限制導致問題無法解決。計算機內(nèi)存和速度的限制導致問題無法解決。有些問題由于涉及的函數(shù)沒有理想的性質(zhì)使

7、問有些問題由于涉及的函數(shù)沒有理想的性質(zhì)使問題只能用動態(tài)規(guī)劃描述，而不能用動態(tài)規(guī)劃方題只能用動態(tài)規(guī)劃描述，而不能用動態(tài)規(guī)劃方法求解。法求解。11第二節(jié)第二節(jié) 最優(yōu)化原理與動態(tài)規(guī)劃的數(shù)學模型最優(yōu)化原理與動態(tài)規(guī)劃的數(shù)學模型一一 最短路線問題求解最短路線問題求解25375632455114633334C1C3D1AB1B3B2D2EC2f(E)=012考慮一個階段的最優(yōu)選擇考慮一個階段的最優(yōu)選擇C1C3D1AB1B3B2D2EC2f(D1)=3f(E)=02537563245511463333413C1C3D1AB1B3B2D2EC2f(D2)=4f(E)=0f(D1)=325375632455114

8、633334考慮一個階段的最優(yōu)選擇考慮一個階段的最優(yōu)選擇14C1C3D1AB1B3B2D2EC2f(D2)=4f(E)=0f(C1)=4f(D1)=325375632455114633334考慮二個階段的最優(yōu)選擇考慮二個階段的最優(yōu)選擇15C1C3D1AB1B3B2D2EC2f(D2)=4f(E)=0f(C2)=7f(D1)=3f(C1)=437563245511463332534考慮二個階段的最優(yōu)選擇考慮二個階段的最優(yōu)選擇16C1C3D1AB1B3B2D2EC2f(D2)=4f(E)=0f(C3)=6f(D1)=3f(C1)=4f(C2)=725375632455114633334考慮二個階段

9、的最優(yōu)選擇考慮二個階段的最優(yōu)選擇17C1C3D1AB1B3B2D2EC2f(D2)=4f(E)=0f(C3)=6f(D1)=3f(B1)=11f(C2)=7f(C1)=425375632455114633334考慮三個階段的最優(yōu)選擇考慮三個階段的最優(yōu)選擇18C1C3D1AB1B3B2D2EC2f (D2)=4f (E)=0f(C3)=6f (D1)=3f(B2)=7f(C2)=7f(C1)=4f(B1)=1125375632455114633334考慮三個階段的最優(yōu)選擇考慮三個階段的最優(yōu)選擇19C1C3D1AB1B3B2D2EC2f(D2)=4f(E)=0f(C3)=6f(D1)=3f(B3)

10、=8f(C2)=7f(C1)=4f(B1)=11f(B2)=725375632455114633334考慮三個階段的最優(yōu)選擇考慮三個階段的最優(yōu)選擇2010C1C3D1AB1B3B2D2EC2f(D2)=4f(E)=0f(C3)=6f(D1)=3f(B3)=8f(C2)=7f(C1)=4f(A)=11f(B2)=7f(B1)=1125375632455114633334四個階段聯(lián)合考慮從四個階段聯(lián)合考慮從A點到點到E點的最優(yōu)選擇點的最優(yōu)選擇216C1C3D1AB1B3B2D2EC2f(D2)=4f(E)=0f(C3)=6f(D1)=3f(B3)=8f(C2)=7f(C1)=4f(A)=11f(B

11、2)=7f(B1)=11狀態(tài)狀態(tài) 最優(yōu)決策最優(yōu)決策 狀態(tài)狀態(tài) 最優(yōu)決策最優(yōu)決策 狀態(tài)狀態(tài) 最優(yōu)決策最優(yōu)決策 狀態(tài)狀態(tài) 最優(yōu)決策最優(yōu)決策 狀態(tài)狀態(tài)A （ A，B3） B37532455125314633334226C1C3D1AB1B3B2D2EC2f(D2)=4f(E)=0f(C3)=6f(D1)=3f(B3)=8f(C2)=7f(C1)=4f(A)=11f(B2)=7f(B1)=11狀態(tài)狀態(tài) 最優(yōu)決策最優(yōu)決策 狀態(tài)狀態(tài) 最優(yōu)決策最優(yōu)決策 狀態(tài)狀態(tài) 最優(yōu)決策最優(yōu)決策 狀態(tài)狀態(tài) 最優(yōu)決策最優(yōu)決策 狀態(tài)狀態(tài)A （ A，B3） B3 （ B3， C2 ） C275324551253146333342

12、36C1C3D1AB1B3B2D2EC2f(D2)=4f(E)=0f(C3)=6f(D1)=3f(B3)=8f(C2)=7f(C1)=4f(A)=11f(B2)=7f(B1)=11狀態(tài)狀態(tài) 最優(yōu)決策最優(yōu)決策 狀態(tài)狀態(tài) 最優(yōu)決策最優(yōu)決策 狀態(tài)狀態(tài) 最優(yōu)決策最優(yōu)決策 狀態(tài)狀態(tài) 最優(yōu)決策最優(yōu)決策 狀態(tài)狀態(tài)A （ A，B3） B3 （ B3， C2 ） C2 （ C2， D2 ） D2 7532455125314633334246C1C3D1AB1B3B2D2EC2f(D2)=4f(E)=0f(C3)=6f(D1)=3f(B3)=8f(C2)=7f(C1)=4f(A)=11f(B2)=7f(B1)=1

13、1狀態(tài)狀態(tài) 最優(yōu)決策最優(yōu)決策 狀態(tài)狀態(tài) 最優(yōu)決策最優(yōu)決策 狀態(tài)狀態(tài) 最優(yōu)決策最優(yōu)決策 狀態(tài)狀態(tài) 最優(yōu)決策最優(yōu)決策 狀態(tài)狀態(tài)A （ A，B3） B3 （ B3， C2 ） C2 （ C2， D2 ） D2 （ D2， E） E7532455125314633334從從A到到E的最短路徑為的最短路徑為11，路線為，路線為AB3C2 D2 E25通過上例的討論，可以看到多級決策過程具有以下特點：（1）把整個過程看成（或認為地分成）把整個過程看成（或認為地分成）n個具有個具有遞推關(guān)系的單級過程。遞推關(guān)系的單級過程。（2）采取逐級分析的方法，一般由最后一級開）采取逐級分析的方法，一般由最后一級開始倒向進

14、行。始倒向進行。（3）在每一級決策時，不只考慮本級的性能指）在每一級決策時，不只考慮本級的性能指標的最優(yōu)，而且同時考慮本級及以后的總性能標的最優(yōu)，而且同時考慮本級及以后的總性能指標最優(yōu)，因此它是根據(jù)指標最優(yōu)，因此它是根據(jù)“全局全局”最優(yōu)作出本最優(yōu)作出本級決策的。級決策的。26動態(tài)規(guī)劃法較之窮舉法的優(yōu)點動態(tài)規(guī)劃法較之窮舉法的優(yōu)點:(1) 容易計算出結(jié)果；容易計算出結(jié)果；(2) 動態(tài)規(guī)劃的計算結(jié)果不僅得到了從起始點動態(tài)規(guī)劃的計算結(jié)果不僅得到了從起始點到最終點的最短路線，而且得到了中間段任一到最終點的最短路線，而且得到了中間段任一點到最終點的最短路線點到最終點的最短路線 。27動態(tài)規(guī)劃方法的基本思想

15、：動態(tài)規(guī)劃方法的基本思想： (1)將多階段決策過程劃分階段，恰當?shù)剡x取狀態(tài)變將多階段決策過程劃分階段，恰當?shù)剡x取狀態(tài)變量、決策變量及定義最優(yōu)指標函數(shù)從而把問題化成一量、決策變量及定義最優(yōu)指標函數(shù)從而把問題化成一族同類型的子問題，然后逐個求解。族同類型的子問題，然后逐個求解。 (2)求解時從邊界條件開始，逆求解時從邊界條件開始，逆(或順或順)過程行進方向，過程行進方向，逐段遞推尋優(yōu)。在每一個子問題求解時，都要使用它前逐段遞推尋優(yōu)。在每一個子問題求解時，都要使用它前面已求出的子問題的最優(yōu)結(jié)果，最后一個子問題的最優(yōu)面已求出的子問題的最優(yōu)結(jié)果，最后一個子問題的最優(yōu)解，就是整個問題的最優(yōu)解。解，就是整個

16、問題的最優(yōu)解。 (3)動態(tài)規(guī)劃方法是既把當前一段與未來各段分開，動態(tài)規(guī)劃方法是既把當前一段與未來各段分開，又把當前效益和未來效益結(jié)合起來考慮的一種最優(yōu)化方又把當前效益和未來效益結(jié)合起來考慮的一種最優(yōu)化方法，因此每段的最優(yōu)決策選取是從全局考慮的，與該段法，因此每段的最優(yōu)決策選取是從全局考慮的，與該段的最優(yōu)選擇一般是不同的。的最優(yōu)選擇一般是不同的。28二、基本概念和基本原理二、基本概念和基本原理動態(tài)規(guī)劃模型要用到的概念：動態(tài)規(guī)劃模型要用到的概念：n (1)階段階段; (2)狀態(tài)狀態(tài); (3)決策和策略決策和策略; (4)狀態(tài)狀態(tài)轉(zhuǎn)移律轉(zhuǎn)移律; (5)指標函數(shù)。指標函數(shù)。1、階段：、階段：將將所給問

17、題的過程，按時間或空間特征分解所給問題的過程，按時間或空間特征分解成若干互相聯(lián)系的階段，以便按次序去求每階段的解，常用成若干互相聯(lián)系的階段，以便按次序去求每階段的解，常用字母字母k表示階段變量。表示階段變量。292、狀態(tài)：、狀態(tài)：各階段開始時的客觀條件叫做狀態(tài)。各階段開始時的客觀條件叫做狀態(tài)。狀態(tài)變量狀態(tài)變量：描述各階段狀態(tài)的變量，用描述各階段狀態(tài)的變量，用sk表示第表示第k階段階段的狀態(tài)變量。的狀態(tài)變量。狀態(tài)集合：狀態(tài)集合：狀態(tài)變量的取值集合，用狀態(tài)變量的取值集合，用Sk表示。表示。一階段：S1A二階段：S2B1,B2,B3三階段：S3C1,C2,C3四階段：S4D1,D2一階段：一階段：S

18、1A二階段：二階段：S2B1,B2,B3三階段：三階段：S3C1,C2,C3四階段：四階段：S4D1,D2二、基本概念和基本原理二、基本概念和基本原理30二、基本概念和基本原理二、基本概念和基本原理二、基本概念和基本原理二、基本概念和基本原理3、決策：、決策：當各段的狀態(tài)取定以后，就可以作出不同當各段的狀態(tài)取定以后，就可以作出不同的決定（或選擇），從而確定下一階段的狀態(tài)，這種決的決定（或選擇），從而確定下一階段的狀態(tài)，這種決定稱為決策。定稱為決策。決策變量：決策變量：表示決策的變量，稱為決策變量，常用表示決策的變量，稱為決策變量，常用xk(sk)表示第表示第k階段當狀態(tài)為階段當狀態(tài)為sk時的決

19、策變量。時的決策變量。允許決策集合：允許決策集合：決策變量的取值往往限制在一定范圍決策變量的取值往往限制在一定范圍內(nèi)，我們稱此范圍為允許決策集合，用內(nèi)，我們稱此范圍為允許決策集合，用Dk(sk)表示第表示第k階階段從狀態(tài)段從狀態(tài)sk出發(fā)的允許決策集合。出發(fā)的允許決策集合。D2( B1)=C1,C2 D2( B2)=C1,C2,C3如狀態(tài)為B1時選擇C2，可表示為：u2(B1)=C2D2( B1)=C1,C2 D2( B2)=C1,C2,C3如狀態(tài)為如狀態(tài)為B1時選擇時選擇C2，可表示為：，可表示為：x2(B1)=C231二、基本概念和基本原理二、基本概念和基本原理4 策略：策略：各段決策確定后

20、，整個問題的決策序列就構(gòu)成各段決策確定后，整個問題的決策序列就構(gòu)成一個策略，用一個策略，用p1,nx1(s1),x2(s2),.xn(sn)表示。表示。允許策略集合：允許策略集合：對每個實際問題，可供選擇的策略有一對每個實際問題，可供選擇的策略有一定范圍，稱為允許策略集合，記作定范圍，稱為允許策略集合，記作P1,n，使整個問題達到最，使整個問題達到最優(yōu)效果的策略就是最優(yōu)策略。優(yōu)效果的策略就是最優(yōu)策略。32二、基本概念和基本原理二、基本概念和基本原理 5、狀態(tài)轉(zhuǎn)移方程、狀態(tài)轉(zhuǎn)移方程：動態(tài)規(guī)劃中本階段的狀態(tài)往往是上一階動態(tài)規(guī)劃中本階段的狀態(tài)往往是上一階段狀態(tài)和上一階段的決策結(jié)果。段狀態(tài)和上一階段的

21、決策結(jié)果。第第k段的狀態(tài)段的狀態(tài)sk，本階段決策為，本階段決策為xk(sk)，則第，則第k+1段的狀態(tài)段的狀態(tài)sk+1也就完全確定，它們的關(guān)系可用公式表示：也就完全確定，它們的關(guān)系可用公式表示：sk+1=Tk(sk,xk)33 6、指標函數(shù)：、指標函數(shù)：用于衡量所選定策略優(yōu)劣的數(shù)量指標。用于衡量所選定策略優(yōu)劣的數(shù)量指標。 它分為它分為階段指標函數(shù)階段指標函數(shù)和和過程指標函數(shù)過程指標函數(shù)。 階段指標函數(shù)階段指標函數(shù)是指第是指第k段，從狀態(tài)段，從狀態(tài)sk出發(fā)，采取決策出發(fā)，采取決策xk時的效益，用時的效益，用Vk(sk,uk)表示。表示。 過程指標函數(shù)過程指標函數(shù)記為記為fk(sk)：表示從第：表

22、示從第k段狀態(tài)段狀態(tài)sk按預定指按預定指標到過程終止時的效益值。標到過程終止時的效益值。二、基本概念和基本原理二、基本概念和基本原理34最簡單的方法最簡單的方法窮舉法。共有多少條窮舉法。共有多少條路徑，依次計算并比較。路徑，依次計算并比較。動態(tài)規(guī)劃方法動態(tài)規(guī)劃方法本方法是從過程的最本方法是從過程的最后一段開始，用逆序遞推方法求解，逐步求后一段開始，用逆序遞推方法求解，逐步求出各段各點到終點的最短路線，最后求得起出各段各點到終點的最短路線，最后求得起始點到終點的最短路線始點到終點的最短路線。三、三、最優(yōu)化原理與動態(tài)規(guī)劃的數(shù)學模型最優(yōu)化原理與動態(tài)規(guī)劃的數(shù)學模型35最優(yōu)化原理Optimization

23、 Principle 作為整個過程的最優(yōu)策略具有這樣的性質(zhì)：n無論過去的狀態(tài)和決策如何，對先前決策所形成的狀態(tài)而言，余下的諸決策必構(gòu)成最優(yōu)策略。 若若M是從是從A到到B的最優(yōu)路線上的一點，則的最優(yōu)路線上的一點，則從從M到到B的路線也是最優(yōu)的的路線也是最優(yōu)的。ABM36動態(tài)規(guī)劃的基本方程（最優(yōu)化原理的應用）n根據(jù)最優(yōu)化原理得到的計算動態(tài)規(guī)劃問題的遞（逆）推關(guān)系式：, ( ,) nk niiii KVv s x當時，11()() ( ,)()kkkkkkkkkkxDsf soptv s xfsn,i k ( ,) k nkiiVv s x當時11()( ) ( ,)()kkkkkkkkkkxDsf

24、 soptv s xfs邊界條件：k=n時，fn+1(sn+1)=0邊界條件： k=n時， fn+1(sn+1)=1Opt: optimization, max or min vk: k階段的指標函數(shù) fk+1:k+1階段的最優(yōu)指標函數(shù)值 fk:k階段的最優(yōu)指標函數(shù)值37構(gòu)成動態(tài)規(guī)劃模型的條件構(gòu)成動態(tài)規(guī)劃模型的條件-1n根據(jù)時間或空間的自然特征，實際問題能恰根據(jù)時間或空間的自然特征，實際問題能恰當?shù)貏澐譃楫數(shù)貏澐譃槿舾呻A段若干階段，形成，形成多階段決策多階段決策的過的過程程38構(gòu)成動態(tài)規(guī)劃模型的條件構(gòu)成動態(tài)規(guī)劃模型的條件-2 -2n正確的選擇狀態(tài)變量正確的選擇狀態(tài)變量S 動態(tài)規(guī)劃的狀態(tài)應具有三

25、個特征：動態(tài)規(guī)劃的狀態(tài)應具有三個特征： 能夠用來描述受控過程的能夠用來描述受控過程的演變特征演變特征；n滿足無后效性：滿足無后效性：如果某階段狀態(tài)給定，則在這階如果某階段狀態(tài)給定，則在這階段以后過程的發(fā)展只與當前的狀態(tài)有關(guān)，而與過去的段以后過程的發(fā)展只與當前的狀態(tài)有關(guān)，而與過去的歷史無關(guān)?；虍斍暗臓顟B(tài)是過去歷史發(fā)展的一個總結(jié)，歷史無關(guān)。或當前的狀態(tài)是過去歷史發(fā)展的一個總結(jié)，過程的過去歷史只能通過當前的狀態(tài)影響未來的發(fā)展。過程的過去歷史只能通過當前的狀態(tài)影響未來的發(fā)展。n可知性：可知性：各階段狀態(tài)變量的值，直接或間各階段狀態(tài)變量的值，直接或間接地都是可以知道的。接地都是可以知道的。39構(gòu)成動態(tài)規(guī)

26、劃模型的條件構(gòu)成動態(tài)規(guī)劃模型的條件 - - 3n確定決策變量確定決策變量sk的含義及每階段的的含義及每階段的允許決策集合允許決策集合Dk(sK)()(kkkksDsx40構(gòu)成動態(tài)規(guī)劃模型的條件構(gòu)成動態(tài)規(guī)劃模型的條件-4 -4正確寫出狀態(tài)轉(zhuǎn)移方程正確寫出狀態(tài)轉(zhuǎn)移方程 sk+1=T(sk,xk(sk) 或或 sk+1=T(sk,xk) 41構(gòu)成動態(tài)規(guī)劃模型的條件構(gòu)成動態(tài)規(guī)劃模型的條件-5 -5明確指標函數(shù)明確指標函數(shù)Vk,n的關(guān)系的關(guān)系一般有兩種形式一般有兩種形式n和式n積式11()() ( ,)()kkkkkkkkkkxDsf soptv s xfs11()( ) ( ,)()kkkkkkkkk

27、kxDsf soptv s xfs42四四 逆序解法與順序解法逆序解法與順序解法如果尋優(yōu)的方向與多階段決策過程的實際行進方如果尋優(yōu)的方向與多階段決策過程的實際行進方向相反，從最后一段開始計算逐段前推，求得全過程向相反，從最后一段開始計算逐段前推，求得全過程的最優(yōu)策略，稱為逆序解法。的最優(yōu)策略，稱為逆序解法。順序解法的尋優(yōu)方向同于過程的行進方向，計算順序解法的尋優(yōu)方向同于過程的行進方向，計算時從第一段開始逐段向后遞推，計算后一階段要用到時從第一段開始逐段向后遞推，計算后一階段要用到前一階段的求優(yōu)結(jié)果，最后一段計算的結(jié)果就是全過前一階段的求優(yōu)結(jié)果，最后一段計算的結(jié)果就是全過程的最優(yōu)結(jié)果。程的最優(yōu)結(jié)

28、果。43第一步：k=0狀態(tài)：s1Af0(A)0求解步驟求解步驟順序解法求解順序解法求解44第二步：k=1 狀態(tài)：B1 B2 x1*(B1)=Ax1*(B2)=Af1(B1)4f1(B2)5(4)(5)45第三步：k=2 狀態(tài)：C1 C2 C3 C4u2*(C1)=B1x2*(C2)=B1x2*(C3)=B1f2(C1)6f2(C2)7f2(C3)10 x2*(C4)=B2f2(C4)12(4)(5)(6)(7)(10)(12)x2*(C1)=B146(4)(5)(6)(7)(10)(12)第四步：k=3 狀態(tài)：D1 D2 D3x3*(D1)=C1或C2x3*(D2)=C2x3*(D3)=C3f

29、3(D1)11f3(D2)12f3(D3)14(11)(12)(14)47第五步：k=4 狀態(tài)：E1 E2 x4*(E1)=D1x4*(E2)=D2f4(E1)14f4(E2)14(4)(5)(6)(7)(10)(12)(11)(12)(14)(14)(14)48第六步：k=5 狀態(tài)：F u5*(F)=E2f5(F)17(6)(4)(5)(7)(10)(12)(11)(12)(14)(14)(14)(17)即從A到F的最短距離為17。最優(yōu)路線為：AB1C2D2E2F49逆序解法與順序解法建模的不同點逆序解法與順序解法建模的不同點1狀態(tài)轉(zhuǎn)移方式不同狀態(tài)轉(zhuǎn)移方式不同sk+1=Tk(sk,xk) s

30、k=Tk(sk+1,xk) 1狀態(tài)s1決策x1效益v1(s1,x1)s2kskxkvk(sk,xk)Sk+1nsnxnvn(sn,xn)Sn+11狀態(tài)s1決策x1效益v1(s2,x1)s2kskxkvk(sk+1,xk)Sk+1nsnxnvn(sn+1,xn)Sn+1502指標函數(shù)的定義不同指標函數(shù)的定義不同 逆序解法中，我們定義最優(yōu)指標函數(shù)逆序解法中，我們定義最優(yōu)指標函數(shù)fk(sk)表示第表示第k段從狀態(tài)段從狀態(tài)sk出發(fā)，到終點后部子過程最優(yōu)效益值，出發(fā)，到終點后部子過程最優(yōu)效益值，f1(s1)是整體最優(yōu)函數(shù)值。是整體最優(yōu)函數(shù)值。 順序解法中，定義最優(yōu)指標函數(shù)順序解法中，定義最優(yōu)指標函數(shù)fk

31、(sk+1)表示第表示第k段段時從起點到狀態(tài)時從起點到狀態(tài)sk+1的前部子過程最優(yōu)效益值。的前部子過程最優(yōu)效益值。fn(sn+1)是是整體最優(yōu)函數(shù)值。整體最優(yōu)函數(shù)值。513. 基本方程形式不同基本方程形式不同(1)當指標函數(shù)為階段指標和形式逆序解法則基本方程為：則基本方程為：順序解法, (,)nk njjjjkVvsx=1,11 (,)kkjjjjVv sx+=1111()(,)(),1,.,2,1()0kkkkkkkkkuDnnfsopt v sxfskn nfs+=+=-= 11101()(,)()1,2,.,( )0kkkkkkkkkuDfsopt v sxfsknfs+-=+= 52(

32、2)當指標函數(shù)為階段指標積形式當指標函數(shù)為階段指標積形式逆序解法逆序解法基本方程為：基本方程為：基本方程為：基本方程為：順序解法順序解法nkjjjjnkusvV),( ,kjjjjkusvV11, 1),( 1111()(,)(),1,.,2,1()1kkkkkkkkkuDnnfsopt v s ufskn nfs1)(,.,2 , 1)(),()(10111sfnksfusvoptsfkkkkkDukkkk53第第3 3節(jié)節(jié) 離散確定型動態(tài)規(guī)劃 模型求解Solution of Discrete Certain DP Model54例4n某一警衛(wèi)部門共有某一警衛(wèi)部門共有12支巡邏隊，負責支巡邏

33、隊，負責4個要害個要害部位部位A、B、C、D的警衛(wèi)巡邏。的警衛(wèi)巡邏。n對每個部位可分別派出對每個部位可分別派出2-4支巡邏隊，并且由支巡邏隊，并且由于派出巡邏隊數(shù)的不同，各部位預期在一段于派出巡邏隊數(shù)的不同，各部位預期在一段時期內(nèi)可能造成的損失有差別，具體數(shù)字見時期內(nèi)可能造成的損失有差別，具體數(shù)字見表表8-1。n問該警衛(wèi)部門應往各部位分別派多少支巡邏問該警衛(wèi)部門應往各部位分別派多少支巡邏隊，使總的預期損失為最小隊，使總的預期損失為最小。 ABCD218382434314352231410312125巡邏隊數(shù)巡邏部位預期損失55解-1n階段變量階段變量k ：把12支巡邏隊往4個部位派遣看成依次分

34、四個階段(k=1，2，3，4)。n狀態(tài)變量狀態(tài)變量sk：表示每個階段初擁有的可派遣的巡邏隊數(shù)是前面階段決策的結(jié)果，也是本階段決策的依據(jù)n決策變量決策變量xk：表示各階段對各部位派出的巡邏隊數(shù)，n各階段允許的決策集合決策集合Dk(sk)為：nDk(sk)=xk|2xk4| (k=1,2,3,4)56解解-2n狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程：sk+1=sk-xk (k=1,2,3,4)n每階段初擁有可派遣的巡邏隊數(shù)量等于上階段初擁有的數(shù)量減去上階段派出的數(shù)量n過程函數(shù)為階段指標函數(shù)之和：過程函數(shù)為階段指標函數(shù)之和：n階段指標函數(shù)階段指標函數(shù)vk(xk)表示表示k階段派出的巡邏隊數(shù)階段派出的巡邏隊數(shù)為為

35、xk時，該階段的部位的預期損失值時，該階段的部位的預期損失值44,41,41( )()( )()kiikkiikkki ki kVv xv xv xv xV 57解-3nfk(sk)：表示從：表示從k階段狀態(tài)為階段狀態(tài)為sk出發(fā)，采用最優(yōu)出發(fā)，采用最優(yōu)子策略到過程結(jié)束時的預期損失值，有子策略到過程結(jié)束時的預期損失值，有n先考慮給先考慮給D部位派巡邏隊，即部位派巡邏隊，即k=4，上式可寫，上式可寫為為 n邊界條件邊界條件f5(s5)=0 ，所以，所以 11()()min ()()kkkkkkkkkxDsfsv xfs444444455()()min ()( )xDsf sv xf s444444

36、4()( )min ()xDsf sv x58解-4 x4s4v4(x4)f4(s4)x4*23423434233431313434312525453431252546343125254因因D4（s4）=2，3，4，又，又s4的可能值是的可能值是2s46，故，故由表由表8-1的數(shù)據(jù)，可得下表的結(jié)果的數(shù)據(jù)，可得下表的結(jié)果 4444444()()min ()xDsf sv x總共總共12支巡邏隊，每部位支巡邏隊，每部位24支巡邏隊。支巡邏隊。59解-5n聯(lián)合考慮對聯(lián)合考慮對C、D兩個部位派巡邏隊，兩個部位派巡邏隊，k=3，有：，有：n因因D3(s3)=2,3,4，4s38，可得如下結(jié)果，可得如下結(jié)

37、果333333344()( )min ()( )xDsf sv xf s x3s3v3(x3)+f4(s3-x3)f3(s3)x3*234424+34582524+3122+34552624+2522+3121+34492724+2522+2521+31473824+2522+2521+2546460解-6n考慮對考慮對B、C、D三個部位派巡邏隊，三個部位派巡邏隊，k=2，有，有由由D2(s2)=2,3,4，8s210，可得如下結(jié)果可得如下結(jié)果 222222233()()min ()( )xDsf sv xf s x2s2v2(x2)+f3(s2-x2)f2(s2)x2*234838+4935

38、+5531+58872938+4735+4931+558431038+4635+4731+4980461解-7n考慮對考慮對A、B、C、D四個部隊派巡邏隊，即四個部隊派巡邏隊，即k=1時，有時，有n因因s1=12, D1(s1)=2,3,4,可得如下結(jié)果可得如下結(jié)果 111111122()( )min ( )( )xDsf sv xf s x1s1v1(x1)+f2(s1-x1)f1(s1)x1*2341218+8014+8410+8797462解-8 x3s3v3(x3)+f4(s3-x3)f3(s3)x3*234424+34582524+31 22+34552624+25 22+3121+

39、34492724+25 22+2521+31473824+25 22+2521+25464x4s4v4(x4)f4(s4)x4*23423434233431313434312525453431252546343125254 x2s2v2(x2)+f3(s2-x2)f2(s2)x2*234838+49 35+55 31+58872938+47 35+49 31+558431038+46 35+47 31+49804l最優(yōu)策略最優(yōu)策略為：lA部位部位4支，支，B部位部位2支，支，C部位部位2支，支，D部位部位4支，總預期損失為支，總預期損失為97單位。單位。x1s1v1(x1)+f2(s1-x1)

40、f1(s1)x1*2341218+80 14+84 10+8797463第四節(jié)第四節(jié) 離散隨機型動態(tài)規(guī)劃離散隨機型動態(tài)規(guī)劃 模型求解模型求解Solution of Discrete Stochastic DP Model64隨機型的動態(tài)規(guī)劃n指狀態(tài)的轉(zhuǎn)移律是不確定的，即對給定的狀態(tài)和決策，下一階段的到達狀態(tài)是具有確定概率分布的隨機變量，這個概率分布由本階段的狀態(tài)和決策完全確定第第k+1階段可階段可能的狀態(tài)數(shù)能的狀態(tài)數(shù)給定狀態(tài)給定狀態(tài)xk和決策和決策uk的情況下，下一個可的情況下，下一個可能到達的狀態(tài)的概率能到達的狀態(tài)的概率從從k階段狀態(tài)階段狀態(tài)sk轉(zhuǎn)移到轉(zhuǎn)移到k+1階段階段狀態(tài)為狀態(tài)為i時的指時的指標函數(shù)值標函數(shù)值 隨機性動態(tài)規(guī)劃的基本結(jié)構(gòu)圖skxkSk+165指標函數(shù)為和函數(shù)的轉(zhuǎn)換方程n在隨機性的動態(tài)規(guī)劃問題下，由于下一階段到達的狀態(tài)和階段的效益值不確定，只能根據(jù)各階段的期望效益值進行優(yōu)化。n因此隨機性的動態(tài)規(guī)劃問題中，當指標函數(shù)值為各階段效益和的情況下，基本方程應寫為 )(),(max)(11)(kkkksDxkksfxsgEsfkkk期望值期望值66665 5一般數(shù)學規(guī)劃模型的動態(tài)規(guī)劃解法一般數(shù)學規(guī)劃模型的動態(tài)規(guī)劃解法用動態(tài)規(guī)劃的方法求解一般數(shù)學規(guī)劃模型思想：用動態(tài)規(guī)劃的方法求解一般數(shù)學規(guī)劃模型思想：將取定每個變量的值作為一個階段，則有將取定每個變量的值作