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

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

幾個(gè)術(shù)語(yǔ)1.階段過(guò)程的劃分，包括時(shí)間、空間的劃分，階段數(shù):n描述階段序號(hào)的變量稱為階段變量，用k表示，k=1,2,…..,n2.狀態(tài)每個(gè)階段開(kāi)始所處的自然狀況或客觀條件稱為狀態(tài)，是不可控因素。若給定了某階段狀態(tài)，則在這階段以后過(guò)程的發(fā)展不受這階段以前各階段狀態(tài)的影響（無(wú)后效性）。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.決策從一個(gè)階段的狀態(tài)到下一個(gè)階段狀態(tài)的選擇。描述決策的變量稱為決策變量，用u表示.uk=uk(sk)表示第k階段處于sk的決策變量；Dk=Dk(sk)表示第k階段處于Sk時(shí)決策變量的集合，uk

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

u2(B1)=C1

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

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

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

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

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

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

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