【正文】 1的指標(biāo)就是運(yùn)費(fèi) 。 (1)階段指標(biāo)函數(shù) （ 也稱階段效應(yīng) ） 。 用vk(sk,uk)表示第 k段處于 sk狀態(tài)且所作決策為uk(sk)時(shí)的指標(biāo) ， 則它就是第 k段指標(biāo)函數(shù) 。 (2)過程指標(biāo)函數(shù) （ 也稱目標(biāo)函數(shù) ） 。 不僅跟當(dāng)前狀態(tài) sk有關(guān) ， 還跟該子過程策略pk,n(sk)有關(guān) ， 表示為 : ,( ( ) )k n k n kV p s 適于用動(dòng)態(tài)規(guī)劃求解的問題的過程指標(biāo)函數(shù)（ 即目標(biāo)函數(shù) ） ， 必須具有關(guān)于階段指標(biāo)的可分離形式 ． 對(duì)于部子過程的指標(biāo)函數(shù)可以表示為： , , 1 , 1 , 1( ( ) ) ( , , ( ( ) ) )k n k n k k k k k n k n kV p s s u V p s? ? ? ?? (2) ,11 , 1 , 1( ( ) ( , )( , ) ( , )( , ) ( ( )nk n k n k i i iiknk k k i i iikk k k k n k n kV p s v s uv s u v s uv s u V p s???? ? ????????多階段決策問題中，常見的目標(biāo)函數(shù)形式之 一是取各階段效應(yīng)之和的形式，即 : (七 ) 最優(yōu)解 用 fk(sk)表示第 k子過程指標(biāo)函數(shù)在狀態(tài) sk下的最優(yōu)值 ,即 相應(yīng)的子策略稱為 sk狀態(tài)下的最優(yōu)子策略 ， 記 為 pk,n*(sk) ；而構(gòu)成該子策賂的各段決策稱為該 過程上的最優(yōu)決策 ， 記為 ； 有 , , , ,()( ) { ( ( ) ) } ( * ( ) ) ,1 , 2, ,k n k n kk k k n k n k k n k n kp P sf s o p t V p s V p skn????)(,),(),( 11 nnkkkk sususu ??? ?? ?,1{ , , , } , 1 , 2 , ,k n k k np u u u k n? ? ? ???? 最優(yōu)化原理 （ 貝爾曼最優(yōu)化原理 ） 作為一個(gè)全過程的最優(yōu)策略具有這樣的性質(zhì)：對(duì)于最優(yōu)策略過程中的任意狀態(tài)而言 ， 無論其過去的狀態(tài)和決策如何 ， 余下的諸決策必構(gòu)成一個(gè)最優(yōu)子策略 。 該原理的具體解釋是 ， 若某一全過程最優(yōu)策略為 ： 1 , 1 1 1 2 2( ) { ( ) , ( ) , , ( ) , ( ) }n k k n np s u s u s u s u s? ? ? ? ?? 則對(duì)上述策略中所隱含的任一狀態(tài)而言 ， 第 k子過程上對(duì)應(yīng)于該狀態(tài)的最優(yōu)策略必然 包含在上述全過程最優(yōu)策略 p1*中 ， 即為 , 1 1( ) { ( ) , ( ) , , ( ) }k n k k k k k n np s u s u s u s? ? ? ????(八 ) 動(dòng)態(tài)規(guī)劃的最優(yōu)性原理 (九 )動(dòng)態(tài)規(guī)劃的基本方程 基于上述原理，提出了一種逆序遞推法；該法的關(guān)鍵 在于給出一種遞推關(guān)系。一般把這種遞推關(guān)系稱為動(dòng) 態(tài)規(guī)劃的函數(shù)基本方程。 當(dāng)過程指標(biāo)函數(shù)為下列 “ 和 ” 的形式時(shí)，相應(yīng)的函數(shù)基本方程為 1111()( ) 0( ) { ( , ) ( ) } , , 1 , , 2, 1k k knnk k k k k k ku D sfsf s op t v s u f s k n n????????? ? ? ? ???（三）、建立動(dòng)態(tài)規(guī)劃模型的步驟 劃分階段 劃分階段是運(yùn)用動(dòng)態(tài)規(guī)劃求解多階段決策問題的第一步 ， 在確定多階段特性后 ， 按時(shí)間或空間先后順序 ，將過程劃分為若干相互聯(lián)系的階段 。 對(duì)于靜態(tài)問題要人為地賦予 “ 時(shí)間 ” 概念 ， 以便劃分階段 。 正確選擇狀態(tài)變量 選擇變量既要能確切描述過程演變又要滿足無后效性 ，而且各階段狀態(tài)變量的取值能夠確定 。 一般地 ， 狀態(tài)變量的選擇是從過程演變的特點(diǎn)中尋找 。 確定決策變量及允許決策集合 通常選擇所求解問題的關(guān)鍵變量作為決策變量 ， 同時(shí)要給出決策變量的取值范圍 ， 即確定允許決策集合 。 確定狀態(tài)轉(zhuǎn)移方程 根據(jù) k 階段狀態(tài)變量和決策變量，寫出 k+1階段狀態(tài)變量，狀態(tài)轉(zhuǎn)移方程應(yīng)當(dāng)具有遞推關(guān)系。 確定階段指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù)，建立動(dòng)態(tài)規(guī)劃基本方程 階段指標(biāo)函數(shù)是指第 k 階段的收益，最優(yōu)指標(biāo)函數(shù)是指從第 k 階段狀態(tài)出發(fā)到第 n 階段末所獲得收益的最優(yōu)值，最后寫出動(dòng)態(tài)規(guī)劃基本方程。 以上五步是建立動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型的一般步驟。由于動(dòng)態(tài)規(guī)劃模型與線性規(guī)劃模型不同，動(dòng)態(tài)規(guī)劃模型沒有統(tǒng)一的模式，建模時(shí)必須根據(jù)具體問題具體分析，只有通過不斷實(shí)踐總結(jié)，才能較好掌握建模方法與技巧。 例一、從 A 地到 D 地要鋪設(shè)一條煤氣管道 ,其中需經(jīng)過兩級(jí)中間站，兩點(diǎn)之間的連線上的數(shù)字表示距離，如圖所示。問應(yīng)該選擇什么路線，使總距離最短？ A B1 B2 C1 C2 C3 D 2 4 3 3 3 3 2 1 1 1 4 五、建模舉例：最短路徑問題 解：整個(gè)計(jì)算過程分三個(gè)階段，從最后一個(gè)階段開始。 第一階段（ C → D）： C 有三條路線到終點(diǎn) D 。 A B1 B2 C1 C2 C3 D 2 4 3 3 3 3 2 1 1 1 4 顯然有 f1 (C1 ) = 1 ； f1(C2 ) = 3 ； f1 (C3 ) = 4 d( B1,C1 ) + f1 (C1 ) 3+1 f2 ( B1 ) = min d( B1,C2 ) + f1 (C2 ) = min 3+3 d( B1,C3 ) + f1 (C3 ) 1+4 4 = min 6 = 4 5 第二階段（ B → C）： B 到 C 有六條路線。 A B1 B2 C1 C2 C3 D 2 4 3 3 3 3 2 1 1 1 4 (最短路線為 B1→ C1 → D) d( B2,C1 ) + f1 (C1 ) 2+1 f2 ( B2 ) = min d( B2,C2 ) + f1 (C2 ) = min 3+3 d( B2,C3 ) + f1 (C3 ) 1+4 3 = min 6 = 3 5 A B1 B2 C1 C2 C3 D 2 4 3 3 3 3 2 1 1 1 4 (最短路線為 B2→ C1 → D) 第三階段（ A → B ）： A 到 B 有二條路線。 f3(A)1 = d(A, B1 )＋ f2 ( B1 ) ＝ 2＋ 4＝ 6 f3 (A)2 = d(A, B2 )＋ f2 ( B2 ) ＝ 4＋ 3＝ 7 ∴ f3 (A) = min = min｛ 6,7｝ =6 d(A, B1 )＋ f2 ( B1 ) d(A, B2 )＋ f2 ( B2 ) (最短路線為 A→B 1→ C1 → D) A B1 B2 C1 C2 C3 D 2 4 3 3 3 3 2 1 1 1 4 A B1 B2 C1 C2 C3 D 2 4 3 3 3 3 2 1 1 1 4 最短路線為 A→B 1→ C1 → D 路長為 6 SETS: CITIES/1..7/:F。 ROADS(CITIES,CITIES)/ 1, 2 1, 3 2, 4 2, 5 2, 6 3, 4 3, 5 3, 6 4, 7 5, 7 6, 7/:D。 ENDSETS DATA: D=2 4 3 3 1 2 3 1 1 3 4。 ENDDATA F(@SIZE(CITIES))=0。 @FOR(CITIES(i)|iLT@SIZE(CITIES): F(i)=@MIN(ROADS(i,j):D(i,j)+F(j)) )。 END lINGO程序 Feasible solution found. Total solver iterations: 0 Variable Value F( 1) F( 2) F( 3) F( 4) F( 5) F( 6) F( 7) D( 1, 2) D( 1, 3) D( 2, 4) D( 2, 5) D( 2, 6) D( 3, 4) D( 3, 5) D( 3, 6) D( 4, 7)