4.2动态规划的 基本原理
对最短路问题: 来源于动态规划 最短路问题的特点: 的最优化原理 如果最短路线在第阶段通过s点,则由s点出发到 达终点的这段路线对于从s出发到达终点的所有可 能选择的不同路线来说,必是最短的 找最短路线的方法: 从最后一阶段开始,用由后向前的方法,求出各点到 终点的最短路线,最后求得由起点到终点的最短路线 最短路问题的基本方程: 由后向前迭代 min d(sy, u x)+sri))k=4.3,2,1 f(s)=0 递推公式
对最短路问题： 最短路问题的特点： 找最短路线的方法： 能选择的不同路线来说，必是最短的 达终点的这段路线对于从 出发到达终点的所有可 如果最短路线在第 阶段通过 点，则由 点出发到 s k s s 终点的最短路线，最后求得由起点到终点的最短路线 从最后一阶段开始，用由后向前的方法，求出各点到 来源于动态规划 的最优化原理 最短路问题的基本方程： min ( k , k )+ k+1 ( k+1 ) u d s u f s k f k (sk ) = k=4,3,2,1 f 5 (s5 ) = 0 由后向前迭代 递推公式
最优化原理: 个过程的最优策略具有这样的性质,即无论初始 状态及初始决策如何,对于先前决策所形成的状态 而言,其以后的所有决策必构成最优策略 对最短路问题: = 若C→D2→>E1→>F是C到F的最优策略(最短路) 则不论前面A如何到达B,B又如何到达C1 对状态C1来说,必有: D2→>E1→>F是D2到F的最优策略 E1→F是E1到F的最优策略
最优化原理： 一个过程的最优策略具有这样的性质，即无论初始 状态及初始决策如何，对于先前决策所形成的状态 而言，其以后的所有决策必构成最优策略 对最短路问题： 若C1 → D2 → E1 → F 是C1 到F的最优策略（最短路） 对状态C1 来说，必有： ○A ○B1 ○F ○B2 ○B3 ○C1 ○C2 ○ ○C3 D2 ○D1 ○E2 ○E1 则不论前面A如何到达B，B又如何到达C1 D2 → E1 → F是D2 到F的最优策略 E1 → F是E1 到F的最优策略
上堂课的主要内容: 动态规划的基本概念 1、阶段:指对整个过程的自然划分,用k表示 2、状态变量sk:第k阶段开始时所处的自然状况 Sk={s}—第k阶段的状态集合 3、决策变量: 当一个阶段的状态确定后,可以作出各种选 择从而演变到下一阶段的某个状态,这种选 择手段称为决策 lk(k)--第k阶段处于状态时的决策变量 UA(sk)--决策变量uk(sk)允许取值的范围
上堂课的主要内容： 一、动态规划的基本概念 1、阶段：指对整个过程的自然划分 ，用k表示 2、状态变量sk Sk ={sk} 第k阶段的状态集合 ：第k阶段开始时所处的自然状况 3、决策变量： 当一个阶段的状态确定后，可以作出各种选 择从而演变到下一阶段的某个状态，这种选 择手段称为决策 ( ) k k u s − − −第k阶段处于状态sk 时的决策变量 ( ) k k U s − −决策变量uk (sk )允许取值的范围
4、状态转移方程 sk—第k阶段的状态变量 lk()--表示第阶段处于状态时的决策变量 状态转移方程:SA1=T(SA2uk) 5、策略:由各阶段的决策组成的序列称为策略 原过程的策略pn(s1)---从第一阶段初始状态s开 始到第n阶段全过程的策略 p1n(s1)={1(s)a2(s2)…un(sn)} 后部子过程的策略pn(sA)--从第阶段状态S开 始到第n阶段的策略 即pn(sk)={x4(3)421(Sx)…un(sn) P={策略}允许策略集合
4、状态转移方程 sk 第k阶段的状态变量 ( ) k k u s − −表示第k阶段处于状态sk 时的决策变量 ( , ) k 1 k k uk s = T s 状态转移方程： + 5、策略：由各阶段的决策组成的序列称为策略 ( ) 始到第 阶段全过程的策略 原过程的策略 从第一阶段初始状态 开 n p s s 1,n 1 − − − 1 即p1,n (s1 ) = u1 (s1 ),u2 (s2 ), un (sn ) P = 策略——允许策略集合 ( ) 始到第 阶段的策略 后部子过程的策略 从第 阶段状态 开 n p s k s k ,n k − − − k 即pk ,n (sk ) = uk (sk ),uk+1 (sk+1 ), un (sn )
6、指标函数 用于衡量所选定的策略优劣的数量指标称为指标函数 V1n(s,p)-在初始状态为s时采用原过程策略p,所对应 的指标函数 kn(k,pn)--在第阶段状态为时采用后部子过程 策略p所对应的指标函数 最优策略pn;使指标函数n(,Pn)达到最优的策略 最优值函数f)止采用最优策略p*n时的指标函数值 从第k阶段状态S开始到过程终 ()=Vkn(,P*) *k opt Vknsk, pk Pk.n f(s)-初始状态为s时全过程采用最优策略p* 所对应的指标函数值
6、指标函数 用于衡量所选定的策略优劣的数量指标称为指标函数 ( ) 的指标函数 V1,n s1 , p1,n − −在初始状态为s1 时采用原过程策略p1,n 所对应 ( ) 策略 所对应的指标函数 在第 阶段状态为 时采用后部子过程 k n k n k k n k p V s p k s , , , , − − − 最优策略 p * k ,n ：使指标函数Vk,n (sk , pk,n )达到最优的策略 ( ) k k 最优值函数f s ( ) 所对应的指标函数值 初始状态为 时全过程采用最优策略p n f s s 1 1 − − 1 * 1, 止采用最优策略 时的指标函数值 从第 阶段状态 开始到过程终 k n k p k s * , − − − ( ) k k f s ( ) k n k k n p P opt V s p k n k n , , , , , ( ) = k n k p k n V s , * , =
最优化原理: 个过程的最优策略具有这样的性质,即无论初始 状态及初始决策如何,对于先前决策所形成的状态 而言,其以后的所有决策必构成最优策略 对最短路问题: = 若C→D2→>E1→>F是C到F的最优策略(最短路) 则不论前面A如何到达B,B又如何到达C1 对状态C1来说,必有: D2→>E1→>F是D2到F的最优策略 E1→F是E1到F的最优策略
二、最优化原理： 一个过程的最优策略具有这样的性质，即无论初始 状态及初始决策如何，对于先前决策所形成的状态 而言，其以后的所有决策必构成最优策略 对最短路问题： 若C1 → D2 → E1 → F 是C1 到F的最优策略（最短路） 对状态C1 来说，必有： ○A ○B1 ○F ○B2 ○B3 ○C1 ○C2 ○ ○C3 D2 ○D1 ○E2 ○E1 则不论前面A如何到达B，B又如何到达C1 D2 → E1 → F是D2 到F的最优策略 E1 → F是E1 到F的最优策略
①9 对最短路问题: 607 f()=从第阶段状态为到E点的最短距离,求/(4) 找最短路线的方法: 从最后一阶段开始,用由后向前的方法,求出各点到 终点的最短路线,最后求得由起点到终点的最短路线 最短路问题的基本方程: fu(k)=min d(sk, uk)+fk+(sk+1)k-4,3,2 (s3)=0
找最短路线的方法： 终点的最短路线，最后求得由起点到终点的最短路线 从最后一阶段开始，用由后向前的方法，求出各点到 ( ) k k f s = 从第k阶段状态为sk 到E点的最短距离 对最短路问题： f (A) 1 ,求 ○C1 ○A ○B1 ○E ○B2 ○B3 ○C2 ○ ○C3 D2 8 ○D1 4 5 9 8 6 6 1 10 9 6 7 7 3 8 4 2 3 最短路问题的基本方程： min ( k , k )+ k+1 ( k+1 ) u d s u f s k f k (sk ) = k=4,3,2,1 f 5 (s5 ) = 0
例3(生产与存储问题)某工厂生产并销售某种产品。已知今四 个月市场需求预测如下表,又每月生产个单位产品的费用为 4 c() g(需求|23 2 4 1,2,…6 每月库存个单位产品的费用E(i)=0.5千元),该厂最大库存容 量为3个单位,每月最大生产能力为6个单位,计划开始和计划 期末库存量都是零,试制定四个月的生产计划,在满足用户需 求条件下,使总费用最小 阶段k=1,2,3,4 状态变量s=第k个月月初的库存量 决策变量u(s)=第k月月初库存量为时产品的产量 状态转移方程:Sk1=lk+Sk-8(k 最优值函数f(S):第月月初库存为s时,从本月到 求f(0) 计划结束的最小总费用
例3（生产与存储问题）某工厂生产并销售某种产品。已知今四 个月市场需求预测如下表，又每月生产j个单位产品的费用为 每月库存i个单位产品的费用E(i)=0.5i(千元），该厂最大库存容 量为3个单位，每月最大生产能力为6个单位，计划开始和计划 期末库存量都是零，试制定四个月的生产计划，在满足用户需 求条件下，使总费用最小。 ( ) + = = = 3 1,2, 6 0 0 j j j c j 阶段k=1，2，3，4 状态变量sk=第k个月月初的库存量 i月 1 2 3 4 g(i)需求 2 3 2 4 决策变量uk (sk ) = 第k月月初库存量为sk 时产品的产量 状态转移方程： ( ) 1 s u s g k k+ = k + k − 计划结束的最小总费用 最优值函数f k (sk )：第k月月初库存为sk 时，从本月到 (0) 1 求f
最大生产能力为6个单位,最大库存容量为3个单位, 库存费E(i)=0.5i,计划开始和计划期末库存量为零 i月 生产费用 g0需求2324c( 3+J J=1,2. f(sk):第k月月初库存为s时,从本月到计划结束 的最小总费用 当k=4时,求f4(S4)S4=0,1,2,3 u(s)对应的总费用=生产费+库存费=cu4)+E(s4) S4S4)=min Cu4)+e(s4 0 2 ;(s:)765655 4 3
当k=4时， ( ) 4 4 求f s u4 (s4 )对应的总费用=生产费+库存费 s4 = 0,1,2,3 ( ) ( ) 4 4 = c u + E s 4 ( 4 ) min ( 4 ) ( 4 ) 4 f s c u E s u = + ( ) + = = = 3 1,2, 6 0 0 j j j c j i月 1 2 3 4 生产费用 g(i)需求 2 3 2 4 库存费E(i)=0.5i， 最大生产能力为6个单位，最大库存容量为3个单位， 计划开始和计划期末库存量为零 的最小总费用 f k (sk )：第k月月初库存为sk 时，从本月到计划结束 4 s 0 1 2 3 u4 4 ( ) 4 4 f s 7 u * 4 4 3 6.5 3 2 6 2 1 5.5 1