4-3动态规划应用() 建模练习
4-3 动 态 规 划 应用(一) 建 模 练 习
工程路线问题 (也称最短路或最长路问题) 工程路线问题的一般提法: 从某地出发,途径若干个中间点 最后到达目的地,试求距离最短或 费用最省的路线。 具体有两种情况:
一、工程路线问题 （也称最短路或最长路问题） 工程路线问题的一般提法： 从某地出发，途径若干个中间点 最后到达目的地，试求距离最短或 费用最省的路线。 具体有两种情况：
1.从出发点到目的地的每条路线均由n条 边(弧)组成,因此问题可以化为n个 阶段的多阶段决策过程。由于可以明确 地划分出固定的阶段数,所以称为定步 数问题,亦称定期的多阶段决策过程。 2.阶段数不固定则称为不定步数问题,或 不定期的多阶段决策过程。 建模过程如表4-1
1. 从出发点到目的地的每条路线均由n条 边（弧）组成，因此问题可以化为n个 阶段的多阶段决策过程。由于可以明确 地划分出固定的阶段数，所以称为定步 数问题，亦称定期的多阶段决策过程。 2. 阶段数不固定则称为不定步数问题，或 不定期的多阶段决策过程。 建模过程如表4-1
表4工程路线的建模过程 10=m 基本方 k=n,n-1,…,2,1 1(n+!)=0 最短路问题 最长路问题 阶段:k=1,2,…,n 「状态变量:各阶段初始位置x∈或(∈x)√ 决策变量:各阶段终止位置∈U或k∈UA)√ 状态转移方程:xk+1=uk(xk)或ik+1=jk(k) 阶段效益(x2)=C0(xk→4=x的费用)√ R=∑ Cu(xk,uk) 目标函数: KoK 基本方[(k)=mnA(kJ)++(k) ∫(4)=mxCA()+() fm+1(n+1)=0 k=n,n-1,……2,l fn+1(n+1)=0 k =n,n-1,…2,1 (4)=mxA()+() fn+1(n+1)=0 k= 1,…2,1 或简化为 f(=min Cu+&+o)) f2(=max Cu+k+Oj 或 fn+1(n+1)=0k=n,n-1,…,1 n. n
表4-1 工程路线的建模过程 基 本 方 程 , 1, ,2,1 ( !) 0 ( ) min ( ) 1 1 = − + = = + + + k n n f n f i C f j n i j k j k 最 短 路 问 题 最 长 路 问 题 阶段：k = 1,2,, n √ 状态变量：各阶段初始位置 ( ) k k k X k x X 或 i √ 决策变量：各阶段终止位置 ( ) k k k U k u U 或 j √ 状态转移方程： ( ) ( ) k 1 k k k 1 k k x = u x i = j i + 或 + √ 阶段效益 ( , ) ( ) rk xk uk = Ci j xk → uk = xk+1的费用 √ 目标函数： k k k k n k i j n k k i j R r C x u = = = = ( , ) 1 1 √ 基本方程： = = − = + + + + ( ) 0 1 2 1 ( ) min ( . ) ( ) 1 1 1 f j k n，n ， ， f i C i j f j n n k k k k k j k k k = = − = + + + + ( ) 0 1 2 1 ( ) max ( . ) ( ) 1 1 1 f j k n，n ， ， f i C i j f j n n k k k k k j k k k = = − = + + + + ( ) 0 1 2 1 ( ) max ( . ) ( ) 1 1 1 f j k n，n ， ， f i C i j f j n n k k k k k j k k k 或简化为 = = − = + + + + ( ) 0 , 1, ,1 ( ) min ( ) 1 1 1 f i k n n f i C f j n n i j k j k 或 = = − = + + + + ( ) 0 , 1, ,1 ( ) max ( ) 1 1 1 f i k n n f i C f j n n i j k j k
若是不定步数问题,则基本方 程呈函数方程的形式: f(i=min cu+fof
若是不定步数问题，则基本方 程呈函数方程的形式： f (i) min cij f ( j) j = +