最優(yōu)化理論與方法 課件 12 動態(tài)規(guī)劃

動態(tài)規(guī)劃（DynamicProgramming）動態(tài)規(guī)劃是解決多階段決策過程最優(yōu)化的一種數(shù)學方法，主要用于以時間或地域劃分階段的動態(tài)過程的最優(yōu)化。應用：最優(yōu)調(diào)度、資源分配、最優(yōu)路徑、最優(yōu)控制、設(shè)備更新、庫存問題等。1例.某產(chǎn)品從A城運至E城，其間要經(jīng)過若干個城鎮(zhèn)和若干條道路，路線結(jié)構(gòu)如圖所示，圖中給出了每段道路的運費（單位：十元），試選擇一條合理的運輸路線，使總運費最??？23AB1B2C1C2C3D1D2E53234565238584

幾個術(shù)語1.階段過程的劃分，包括時間、空間的劃分，階段數(shù):n描述階段序號的變量稱為階段變量，用k表示，k=1,2,…..,n2.狀態(tài)每個階段開始所處的自然狀況或客觀條件稱為狀態(tài)，是不可控因素。若給定了某階段狀態(tài)，則在這階段以后過程的發(fā)展不受這階段以前各階段狀態(tài)的影響（無后效性）。4狀態(tài)變量：描述狀態(tài)的變量，用s表示。sk表示第k階段的狀態(tài)變量；Sk表示第k階段的狀態(tài)變量的集合；sk

Sk；例如：s1=A=S1,s2=B1

S2={B1,B2},S3={C1,C2,C3},S4={D1,D2},S5={E}=E.53.決策從一個階段的狀態(tài)到下一個階段狀態(tài)的選擇。描述決策的變量稱為決策變量，用u表示.uk=uk(sk)表示第k階段處于sk的決策變量；Dk=Dk(sk)表示第k階段處于Sk時決策變量的集合，uk

Dk(sk).如：D2(B1)={u2(B1)=C1,u2(B1)=C2}，

u2(B1)=C1

D2(B1).64.策略決策按順序構(gòu)成的序列稱為策略，用p表示。pk,n(sk):第k階段開始至第n階段止的策略；pk,n(sk)={uk(sk),uk+1(sk+1),…,un(sn)}.Pk,n(sk):可供選擇的策略有一定范圍，允許策略集合。當k=1時，p1,n(s1)為全過程策略，p1,n(s1)

P1,n(s1),使目標達到最優(yōu)的策略為最優(yōu)策略p*1,n(s1)。75.狀態(tài)轉(zhuǎn)移方程確定過程由一個狀態(tài)到另一個狀態(tài)變換的方程，Sk+1=Tk{Sk,uk},Tk為變換算子。6.指標函數(shù)衡量過程優(yōu)劣的數(shù)量指標，用Vk,n來表示。Vk,n=Vk,n(sk,pk,n),表示在第k階段狀態(tài)為sk采用策略pk,n時，后部子過程的指標函數(shù)值。指標函數(shù)取得最優(yōu)值時，相應的策略稱為最優(yōu)策略。8常見指標函數(shù)形式有以下兩種，vj

(sj,uj)是第j階段的階段指標。其中Pk,n

(sk)表示以sk為起始狀態(tài)的允許子策略集合，opt表示取最優(yōu)值。最優(yōu)指標函數(shù)記作fk

(sk),97.多階段過程12kn對于動態(tài)系統(tǒng)，設(shè)狀態(tài)為s1,s2,…,sn;T表示變換，則狀態(tài)變換過程為:s2=T(s1),s3=T(s2)=T(T(s1))=T(2)(s1)……sn+1=T(sn)=T(n)(s1)108.多階段決策過程多階段決策過程就是在各個階段都要進行決策。12kn11數(shù)學描述12動態(tài)規(guī)劃的基本方程最優(yōu)性原理作為整個過程的最優(yōu)策略，對前面決策所形成的狀態(tài)而言，余下的各個決策必須構(gòu)成最優(yōu)決策。簡言之，一個最優(yōu)策略的子策略也是最優(yōu)的。例如：最優(yōu)路線AB2C1E2F，

子路線C1E2F也是最優(yōu)的。13設(shè)指標函數(shù)為：根據(jù)最優(yōu)性原理，14根據(jù)以上分析，得到基本方程為：終端條件為：15逆推解法假設(shè)初始狀態(tài)為s1，狀態(tài)轉(zhuǎn)移方程sk+1=T(sk,uk)。逆推解法的計算步驟為：利用已知條件，從k=n開始由后向前推算，求得各階段的最優(yōu)決策和最優(yōu)指標函數(shù)，最后算出f1(s1)即得到最優(yōu)指標函數(shù)值。然后再從k=1開始，利用狀態(tài)轉(zhuǎn)移方程sk+1=T(sk,uk)確定最優(yōu)軌線s*1,s*2,…,s*n+1和最優(yōu)策略u*1,

…,u*n.16例：用逆推解法求解最短路線問題。假設(shè)有一個路網(wǎng)，其中圈號表示地址，連線上的數(shù)字表示兩地間的距離（或運費）。從A到E需經(jīng)過3個中間站，第1站在B1和B2中選擇一個，第2站在C1、C2、C3中選擇一個，第3站在D1和D2中選擇一個，試確定一條由A到E路程的最短路線。17AB1B2C1C2C3D1D2E5323456523858418順推解法設(shè)階段變量k和狀態(tài)變量sk的定義不變。順推解法中，從第一階段開始，利用狀態(tài)轉(zhuǎn)移方程由前向后推算。遞推方程為：最優(yōu)指標函數(shù)fk(sk+1)表示第k階段末的結(jié)束狀態(tài)為sk+1，從第1階段到第k階段的最優(yōu)值。19例：用順推解法求解最短路線問題。假設(shè)有一個路網(wǎng)，其中圈號表示地址，連線上的數(shù)字表示兩地間的距離（或運費）。從A到E需經(jīng)過3個中間站，第1站在B1和B2中選擇一個，第2站在C1、C2、C3中選擇一個，第3站在D1和D2中選擇一個，試確定一條由A到E路程的最短路線。2