多階段決策過(guò)程最優(yōu)化問(wèn)題

1、多階段決策過(guò)程最優(yōu)化問(wèn)題動(dòng)態(tài)規(guī)劃的基本模型在現(xiàn)實(shí)生活中，有一類活動(dòng)的過(guò)程，由于它的特殊性，可將過(guò)程分成若干個(gè)互相聯(lián)系 的階段，在它的每一階段都需要作出決策，從而使整個(gè)過(guò)程達(dá)到最好的活動(dòng)效果。因此各 個(gè)階段決策的選取不能任意確定，它依賴于當(dāng)前面臨的狀態(tài)，又影響以后的發(fā)展。當(dāng)各個(gè) 階段決策確定后，就組成一個(gè)決策序列，因而也就確定了整個(gè)過(guò)程的一條活動(dòng)路線。這種 把一個(gè)問(wèn)題看做是一個(gè)前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過(guò)程就稱為多階段決策過(guò)程，這種 問(wèn)題稱為多階段決策最優(yōu)化問(wèn)題?！纠}1】最短路徑問(wèn)題。圖中給出了一個(gè)地圖，地圖中每個(gè)頂點(diǎn)代表一個(gè)城市，兩個(gè)城市間的連線代表道路，連線上的數(shù)值代表道路的長(zhǎng)度?，F(xiàn)在，

2、想從城市A到達(dá)城市E，怎樣走路程最短，最短路程的長(zhǎng)度是多少？【分析】把從 A到E的全過(guò)程分成四個(gè)階段，用 k表示階段變量，第1階段有一個(gè)初 始狀態(tài)A，兩條可供選擇的支路 ABI、AB2 ;第2階段有兩個(gè)初始狀態(tài) B1、B2，B1有三 條可供選擇的支路，B2有兩條可供選擇的支路。 用dk(Xk, Xk+i)表示在第k階段由初始 狀態(tài)Xk到下階段的初始狀態(tài) Xk+i的路徑距離，F(xiàn)k(Xk)表示從第k階段的Xk到終點(diǎn)E的最短 距離，利用倒推方法求解 A到E的最短距離。具體計(jì)算過(guò)程如下：S1 : K=4，有：F4(D1)=3 , F4(D2)=4 , F4(D3)=3S2: K=3，有:F3(C1)=

3、mind3(C1,D1)+F4(D1),d3(C1,D2)+F4(d2)=min8,10=8F3(C3)=d3(C3,D3)+f4(D3)=8+3=11F3(C4)=d3(C4,D3)+f4(D3)=3+3=6S2: K=2，有F2(B1)=mi nd2(B1,C1)+F3(C1),d2(B1,C2)+f3(C2),d2(B1,C3)+F3(C3)=mi n9,12,14=9F2(m)=mi nd2(B2,c2)+f3(C2),d2(B2,C4)+F3(C4)=mi n16,10=10S4 : k=1，有:F1(A)=mind1(A,B1)+F2(B1),d1(A,B2)+F2(B2)=min

4、13,13=13因此由A點(diǎn)到E點(diǎn)的全過(guò)程的最短路徑為A>B2 一 >C4 >D3 >E。最短路程長(zhǎng)度為13。從以上過(guò)程可以看出，每個(gè)階段中，都求出本階段的各個(gè)初始狀態(tài)到過(guò)程終點(diǎn)E的最短路徑和最短距離，當(dāng)逆序倒推到過(guò)程起點(diǎn)A時(shí)，便得到了全過(guò)程的最短路徑及最短距離，同時(shí)附帶得到了一組最優(yōu)結(jié)果(即各階段的各狀態(tài)到終點(diǎn)E的最優(yōu)結(jié)果)。在上例的多階段決策問(wèn)題中，各個(gè)階段采取的決策，一般來(lái)說(shuō)是與時(shí)間有關(guān)的，決策依賴于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移，一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來(lái)的，故有“動(dòng)態(tài)”的含義，稱這種解決多階段決策最優(yōu)化問(wèn)題的方法為動(dòng)態(tài)規(guī)劃方法。根據(jù)上例分析和動(dòng)態(tài)規(guī)劃的基本概念，可以得到動(dòng)態(tài)規(guī)劃的基本模型如下：(1) 確定問(wèn)題的決策對(duì)象。(2) 對(duì)決策過(guò)程劃分階段。(3) 對(duì)各階段確定狀態(tài)變量。(4) 根據(jù)狀態(tài)變量確定費(fèi)用函數(shù)和目標(biāo)函數(shù)。建立各階段狀態(tài)變量的轉(zhuǎn)移過(guò)程，確定狀態(tài)轉(zhuǎn)移方程。思考與練習(xí):1、寫出本節(jié)例題的算法及PASCAL程序。2、若城市路徑示意圖如下圖所示,231 Zb1223234541232214