21.8递归方程 如下方程称为递归方程 fn(xn1)=0或l f4(x)=opt{v4(xk,u)②f+(xk+1)},k=n…,1 (2) ak∈Uk(x) 在上述方程中,当②为加法时取fn1(xn)=0;当⑧为乘法时,取fn(xn1)=1。动 态规划递归方程是动态規划的最优性原理的基础,即:最优策略的子策略,构成最优子 策略。用状态转移方程(1)和递归方程(2)求解动态规划的过程,是由k=η+1逆 推至k=1,故这种解法称为逆序解法。当然,对某些动态规划问题,也可采用顺序解 法。这时,状态转移方程和递归方程分别为: xk=Tk(xkl, uk),k=l, f(x1)=0或1 f(xk+)=opt{v(xk+12uk)⑧f-(xk),k=1…,n 例3用 lingo求解例1最短路线问题。 model Title Dynamic Programming; vertex/A, Bl, B2, C1, C2, C3, C4, D1, D2, D3, El, E2, E3, Fl, F2, G/: L; road(vertex, vertex)/A Bl, A b2, b1 Cl, Bl C2, B1 c3, B2 C2, B2 C3, B2 C4 C1 D1, Cl D2, C2 Dl, C2 D2, C3 D2, C3 D3, C4 D2,C4 D3 D1E1,D1E2,D2E2,D2E3,D3E2,D3E3, E1 Fl, El F2, E2 Fl, E2 F2, E3 F1, E3 F2, F1 G, F2 G/: D; endset data D=53136876 3336 221233 35526643; L=0,,;,;;;; @for(vertex(i)li#GT#1: L(i)=@min(road(, i): L(3)+D(, i)))i end 纵上所述,如果一个问题能用动态规划方法求解,那么,我们可以按下列步骤,首 先建立起动态规划的数学模型: (i)将过程划分成恰当的阶段。 (ⅱi〕正确选择状态变量x,使它既能描述过程的状态,又满足无后效性,同时确 定允许状态集合x (ⅲi)选择决策变量,确定允许决策集合U4(xk)。 (ⅳv)写出状态转移方程。 (ⅴ)确定阶段指标v(xk,lk)及指标函数Vn的形式(阶段指标之和,阶段指标之 积,阶段指标之极大或极小等)。 (ⅵi)写出基本方程即最优值函数满足的递归方程,以及端点条件 §3逆序解法的计算框图-59- 2.1.8 递归方程 如下方程称为递归方程 ⎪⎩ ⎪ ⎨ ⎧ = ⊗ = = + + ∈ + + ( ) opt { ( , ) ( )}, , ,1 ( ) 0 1 1 1 ( ) 1 1 f x v x u f x k n L f x k k k k k u U x k k n n k k k 或 （2） 在上述方程中，当⊗ 为加法时取 fn+1(xn+1) = 0 ；当⊗ 为乘法时，取 fn+1(xn+1) =1。动 态规划递归方程是动态规划的最优性原理的基础，即：最优策略的子策略，构成最优子 策略。用状态转移方程（1）和递归方程（2）求解动态规划的过程，是由 k = n +1逆 推至 k = 1，故这种解法称为逆序解法。当然，对某些动态规划问题，也可采用顺序解 法。这时，状态转移方程和递归方程分别为： x T xk uk k n r k k ( , ), 1, , = +1 = L ， ⎪⎩ ⎪ ⎨ ⎧ = ⊗ = = + − ∈ + + + f x v x u f x k n f x k k k k k u U x k k k r k k ( ) opt { ( , ) ( )}, 1, , ( 0 1 1 1 ( ) 1 0 1 1 1 L ） 或 例 3 用 lingo 求解例 1 最短路线问题。 model: Title Dynamic Programming; sets: vertex/A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,E3,F1,F2,G/:L; road(vertex,vertex)/A B1,A B2,B1 C1,B1 C2,B1 c3,B2 C2,B2 C3,B2 C4, C1 D1,C1 D2,C2 D1,C2 D2,C3 D2,C3 D3,C4 D2,C4 D3, D1 E1,D1 E2,D2 E2,D2 E3,D3 E2,D3 E3, E1 F1,E1 F2,E2 F1,E2 F2,E3 F1,E3 F2,F1 G,F2 G/:D; endsets data: D=5 3 1 3 6 8 7 6 6 8 3 5 3 3 8 4 2 2 1 2 3 3 3 5 5 2 6 6 4 3; L=0,,,,,,,,,,,,,,,; enddata @for(vertex(i)|i#GT#1:L(i)=@min(road(j,i):L(j)+D(j,i))); end 纵上所述，如果一个问题能用动态规划方法求解，那么，我们可以按下列步骤，首 先建立起动态规划的数学模型： （i）将过程划分成恰当的阶段。 （ii）正确选择状态变量 k x ，使它既能描述过程的状态，又满足无后效性，同时确 定允许状态集合 Xk 。 （iii）选择决策变量uk ，确定允许决策集合 ( ) k k U x 。 （iv）写出状态转移方程。 （v）确定阶段指标 ( , ) k k uk v x 及指标函数Vkn 的形式（阶段指标之和，阶段指标之 积，阶段指标之极大或极小等）。 （vi）写出基本方程即最优值函数满足的递归方程，以及端点条件。 §3 逆序解法的计算框图