大学精品课件：第七章 动态规划（第3-4节）.ppt

1、第第1页页 识别问题的多阶段特性，按时间或空间的先后顺识别问题的多阶段特性，按时间或空间的先后顺序适当地划分为满足递推关系的若干阶段，对非序适当地划分为满足递推关系的若干阶段，对非时序的静态问题要人为地赋予时序的静态问题要人为地赋予“时段时段”的概念。的概念。第第2页页正确选择状态变量，使其具备：正确选择状态变量，使其具备：各阶段的状态变量取值，能直接或间接地确定，各阶段的状态变量取值，能直接或间接地确定，且能够描述过程的演变。且能够描述过程的演变。状态变量要满足无后效性。状态变量要满足无后效性。第第3页页例如，著名的例如，著名的“货郎担问题货郎担问题”，有，有 N 个城镇，要求个城镇，要求一

2、个售货员从某城出发，到各城镇去售货，每个城一个售货员从某城出发，到各城镇去售货，每个城镇去且仅去一次，最后回到原来的出发城镇，求最镇去且仅去一次，最后回到原来的出发城镇，求最短路线。短路线。第第4页页这个问题如果象前面处理最短路问题一样，把城镇这个问题如果象前面处理最短路问题一样，把城镇位置作为状态变量，显然不满足无后效性；位置作为状态变量，显然不满足无后效性；如果把含该城镇在内及以前走过的全部城镇的集合如果把含该城镇在内及以前走过的全部城镇的集合定义为状态，则能实现无后效性。定义为状态，则能实现无后效性。第第5页页根据状态变量与决策变量的含义，正确写出状态根据状态变量与决策变量的含义，正确写

3、出状态转移方程转移方程 。根据题意确定指标函数、最优指标函数根据题意确定指标函数、最优指标函数 fk(sk)、第、第 k 阶段的指标阶段的指标 的含义。的含义。正确列出最优指标函数的递推关系及边界条件，正确列出最优指标函数的递推关系及边界条件，即动态规划基本方程。即动态规划基本方程。),(1kkkkusTs ),(kkkusv第第6页页例：某公司有资金例：某公司有资金10万元，若投资于项目万元，若投资于项目 i（i=1,2,3）的投资额为）的投资额为 xi 时，其收益分别为时，其收益分别为 g1(x1)=4x1，g2(x2)=9x2，g3(x3)=2 ，问应如何分配投资额才，问应如何分配投资额

4、才能使总收益最大？能使总收益最大？23x第第7页页解：解：（1）建立问题的静态模型）建立问题的静态模型这是一个与时间无明显关系的静态最优化问题，可这是一个与时间无明显关系的静态最优化问题，可列出其静态模型：列出其静态模型：)3,2,1(010294max3212321ixxxxxxxzi第第8页页（2）将问题转化为多阶段决策过程）将问题转化为多阶段决策过程 为了应用动态规划方法求解，需要人为地赋予它为了应用动态规划方法求解，需要人为地赋予它“时段时段”：把问题划分为把问题划分为 3 个阶段，每个阶段只确定对一个项个阶段，每个阶段只确定对一个项目的投资金额，首先考虑对项目目的投资金额，首先考虑对

5、项目 1 投资，然后考虑投资，然后考虑对项目对项目 2 投资，最后考虑对项目投资，最后考虑对项目 3 投资。投资。这样问题就转化为一个这样问题就转化为一个 3 段决策过程。段决策过程。第第9页页（3）选择决策变量）选择决策变量 因为因为 xi 为每阶段的投资额，故第为每阶段的投资额，故第 k 阶段的决策变量阶段的决策变量定义为：定义为：uk=xk：表示第：表示第 k 阶段确定的投资额。阶段确定的投资额。uk=xk，k=1,2,3 第第10页页（4）选择状态变量）选择状态变量 状态变量一般为随递推过程变化的量，这里选取每状态变量一般为随递推过程变化的量，这里选取每阶段可供使用的资金数量，故第阶段

6、可供使用的资金数量，故第 k 阶段的状态变量阶段的状态变量定义为：定义为：sk：表示第：表示第 k 阶段到第阶段到第 3 阶段可供使用投资使用的阶段可供使用投资使用的资金数量。（满足无后效性）资金数量。（满足无后效性）第第11页页s1=10；s2=s1-u1；s3=s2-u2。即即 s1=10；s2=s1-x1；s3=s2-x2。第第12页页（5）状态转移方程）状态转移方程 kkkxss 1第第13页页（6）选择指数函数）选择指数函数 Vk,3：表示从第：表示从第 k 阶段的状态阶段的状态 sk 开始，到第开始，到第 3 阶段为阶段为止，采取投资策略（止，采取投资策略（xk，x3）时所创造的收

7、益。）时所创造的收益。Vk,3=，k=1,2,3（满足分离性和递推关系）（满足分离性和递推关系）3)(kiiixg第第14页页（7）选择最优指标函数）选择最优指标函数 fk(sk)：表示从第：表示从第 k 阶段的状态阶段的状态 sk 开始，到第开始，到第 3 阶段阶段为止，采取最优投资策略（为止，采取最优投资策略（xk，x3）时所创造）时所创造的收益。的收益。第第15页页（8）确定动态规划的基本方程）确定动态规划的基本方程 0)(1,2,3),()(max)(44110sfksfxgsfkkkksxkkkk第第16页页动态规划的求解有两种基本方法：动态规划的求解有两种基本方法：逆序解法（后向动

8、态规划方法）逆序解法（后向动态规划方法）顺序解法（前向动态规划方法）。顺序解法（前向动态规划方法）。第第17页页1.逆序解法（后向动态规划方法）逆序解法（后向动态规划方法）（1）定义）定义寻优的方向与多阶段决策过程的实际行进方向相寻优的方向与多阶段决策过程的实际行进方向相反；反；从最后一阶段开始计算，逐段前推；从最后一阶段开始计算，逐段前推；计算前一阶段要用到后一阶段的计算结果；计算前一阶段要用到后一阶段的计算结果；第一阶段的计算结果就是全过程的最优结果。第一阶段的计算结果就是全过程的最优结果。第第18页页（2）基本方程）基本方程 第第 k 阶段与阶段与 k+1 阶段的递推关系为：阶段的递推关

9、系为：0)(1,.,1,),()(,()(1111nnkkkkkkkksfnnksfsusvoptsf第第19页页（3）算）算 例例略略 第第20页页2.顺序解法（前向动态规划方法）顺序解法（前向动态规划方法）（1）定义）定义寻优的方向与多阶段决策过程的实际行进方向相寻优的方向与多阶段决策过程的实际行进方向相同；同；从第一阶段开始计算，逐段后推；从第一阶段开始计算，逐段后推；计算后一阶段要用到前一阶段的计算结果；计算后一阶段要用到前一阶段的计算结果；最后一阶段的计算结果就是全过程的最优结果。最后一阶段的计算结果就是全过程的最优结果。第第21页页（2）基本方程）基本方程第第 k 阶段与阶段与 k

10、+1 阶段的递推关系为：阶段的递推关系为：0)(,.,2,1),()(,()(101111sfnksfsusvoptsfkkkkkkkk第第22页页（3）算例）算例AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835358422123366253543第第23页页第一步：第一步：当当 k=0，S1=A f0(A)=0 第二步：第二步：当当 k=1，S2=B1,B2 s2=B1时：时：f1(B1)=B1 到到 A 最短距离为最短距离为 5，决策为决策为 u1(B1)=A，s1=A，线路为线路为B1A 505)(),(011 AfABd第第24页页s2=B2时：时：

11、f1(B2)=B2 到到 A 最短距离为最短距离为 3，u1(B2)=A，s1=A，线路为线路为B2A 303)(),(021 AfABd第第25页页第三步：第三步：当当 k=2，S3=C1,C2,C3,C4 s3=C1时：时：f2(C1)=C1到到 A 最短距离为最短距离为6，u2(C1)=B1，s2=B1，线路为线路为C1B1A651)(),(11112 BfBCd第第26页页s3=C2时：时：f2(C2)=C2 到到 A 最短距离为最短距离为8，u2(C2)=B1，s2=B1，线路为线路为C2 B1A 83853min)(),()(),(min2122211122 BfBCdBfBCd第

12、第27页页s3=C3时：时：f2(C3)=C3到到 A 最短距离为最短距离为10，u2(C3)=B2，s2=B2，线路为线路为C3B2A 103756min)(),()(),(min2123211132 BfBCdBfBCd第第28页页s3=C4 时：时：f2(C4)=C4 到到 A 最短距离为最短距离为 9，u2(C4)=B2，s2=B2，线路为线路为C4B2 A 936)(),(21242 BfBCd第第29页页第四步：第四步：当当 k=3，S4=D1,D2,D3 s4=D1时：时：f3(D1)=D1 到到 A 最短距离为最短距离为 11，u3(D1)=C2，s3=C2，线路为线路为D1C

13、2 B1A 118366min)(),()(),(min2221312113 CfCDdCfCDd第第30页页s4=D2时：时：f3(D2)=D2 到到 A 最短距离为最短距离为 13，u3(D2)=C2，s3=C2，线路为，线路为D2C2 B1A或或 u3(D2)=C3，s3=C3，线路为，线路为D2C3 B2A 13981038568min)(),()(),()(),()(),(min42423323232222312123 CfCDdCfCDdCfCDdCfCDd第第31页页s4=D3时：时：f3(D3)=D3到到 A 最短距离为最短距离为13，u3(D3)=C3，s3=C3，线路为，线

14、路为D3C3B2A或或 u3(D3)=C4，s3=C4，线路为，线路为D3C4B2A 1394103min)(),()(),(min4243332333 CfCDdCfCDd第第32页页第五步：第五步：当当 k=4，S5=E1,E2,E3 s5=E1时：时：f4(E1)=E1 到到 A 最短距离为最短距离为 13，u4(E1)=D1，s4=D1，线路为线路为E1D1C2 B1G 13112)(),(13114 DfDEd第第33页页s5=E2 时：时：f4(E2)=E2 到到 A 最短距离为最短距离为13，u4(E2)=D1，s4=D1，线路为线路为E2D1C2 B1G 13133131112

15、min)(),()(),()(),(min333242322413124 DfDEdDfDEdDfDEd第第34页页S5=E3时：时：f4(E3)=E3 到到 A 最短距离为最短距离为15，u4(E3)=D2，s4=D2，线路为线路为 E3D2D2C2 B1A 或或 E3D2C3 B2A 15133132min)(),()(),(min3333423234 DfDEdDfDEd第第35页页第六步：第六步：当当 k=5，S6=F1,F2 s6=F1 时：时：f5(F1)=F1 到到 A 最短距离为最短距离为16，u5(F1)=E1，s5=E1，线路为线路为 F1 E1 D1 C2 B1 G 16

16、156135133min)(),()(),()(),(min343152421514115 EfEFdEfEFdEfEFd第第36页页s6=F2时：时：f5(F2)=F2 到到 A 最短距离为最短距离为15，决策为决策为u5(F2)=E2，s5=E2，线路为线路为F2 E2 D1 C2 B1 G 15156132135min)(),()(),()(),(min343252422514125 EfEFdEfEFdEfEFd第第37页页第七步：第七步：当当 k=6，S7=G S7=G 时：时：f6(G)=G 到到 A 最短距离为最短距离为 18，决策为决策为u6(G)=F2，s6=F2，线路为线路

17、为 G F2 E2 D1 C2 B1 A 18153164min)(),()(),(min25261516 FfFGdFfFGd第第38页页结结 论论 最优决策最优决策=s1，u1，s2，u2，s3，u3，s4，u4，s5，u5，s6，u6，s7=s1=A，u1(A)=B1，s2=B1，u2(B1)=C2，s3=C2，u3(C2)=D1，s4=D1，u4(D1)=E2，s5=E2，u5(E2)=F2，s6=F2，u6(F2)=G，s7=G 第第39页页求解过程分析求解过程分析从上面的计算过程中可以看出，在求解的各个阶段，从上面的计算过程中可以看出，在求解的各个阶段，利用了利用了 k 阶段与阶段

18、与 k+1 阶段的递推关系：阶段的递推关系：0)(6,.,2,1),()(,(min)(101111sfksfsusvsfkkkkkkkk第第40页页3.顺序解法和逆序解法的关系顺序解法和逆序解法的关系 顺序解法和逆序解法本质上并无区别，一般来说：顺序解法和逆序解法本质上并无区别，一般来说：（1）当终止状态给定时：用顺序解法；）当终止状态给定时：用顺序解法；（2）当初始状态给定时：用逆序解法；）当初始状态给定时：用逆序解法；第第41页页（3）当定了一个初始状态与一个终止状态：两种方）当定了一个初始状态与一个终止状态：两种方法均可使用。法均可使用。（4）当终止状态为多个时：求出到达不同终止状态）

19、当终止状态为多个时：求出到达不同终止状态的最优指标函数值，选取最优指标函数值最优的终的最优指标函数值，选取最优指标函数值最优的终点状态。点状态。第第42页页（5）当初始状态为多个时：求出从不同初始状态）当初始状态为多个时：求出从不同初始状态出发的最优指标函数值，选取最优指标函数值最优出发的最优指标函数值，选取最优指标函数值最优的初始状态。的初始状态。针对问题的不同特点，灵活地选用两种方法之一，针对问题的不同特点，灵活地选用两种方法之一，可以使求解过程简化。可以使求解过程简化。第第43页页使用顺序法和逆序法为问题建立模型时，要注意以使用顺序法和逆序法为问题建立模型时，要注意以下区别：下区别：（1

20、）状态转移方式不同）状态转移方式不同逆序解法：逆序解法：第第 k 阶段的输入状态为阶段的输入状态为 sk，决策为，决策为uk 输出为状态输出为状态 sk+1第第44页页 状态转移方程为：状态转移方程为：sk+1=Tk(sk,uk)称为状态称为状态 sk 到到 sk+1 的顺序状态转移方程。的顺序状态转移方程。阶段指标为：阶段指标为：vk(sk,uk)kskuksk+1vk(sk,uk)1s1u1s2v1(s1,u1)nsnunsn+1vn(sn,un)第第45页页顺序解法：顺序解法：第第 k 阶段的输入状态为阶段的输入状态为 sk+1，决策为，决策为 uk 输出状态为输出状态为 sk 状态转移

21、方程为：状态转移方程为：sk=Tk(sk+1,uk)，称为状态称为状态 sk+1 到到 sk 的逆序状态转移方程的逆序状态转移方程第第46页页 阶段指标为：阶段指标为：vk(sk+1,uk)nsnunsn+1vn(sn+1,un)kskuksk+1vk(sk+1,uk)1s1u1s2v1(s2,u1)第第47页页（2）指标函数定义不同）指标函数定义不同 逆序解法：逆序解法：阶段指标阶段指标vk(sk,uk)表示第表示第 k 阶段的指标函数值。阶段的指标函数值。过程指标函数过程指标函数Vk,n 表示从第表示从第 k 阶段的状态阶段的状态 sk 开始，到第开始，到第 n 阶段为阶段为止，采取策略止

22、，采取策略 sk,uk,sk+1,uk+1,sn,un,sn+1 时时的数量指标值。的数量指标值。第第48页页当过程指标函数为阶段指标函数的和形式时：当过程指标函数为阶段指标函数的和形式时：当过程指标函数为阶段指标函数的积形式时：当过程指标函数为阶段指标函数的积形式时：nkjjjjnkusvV),(,nkjjjjnkusvV),(,第第49页页 最优指标函数最优指标函数 fk(sk)表示从第表示从第 k 阶段的状态阶段的状态 sk 开始，到最后一阶段开始，到最后一阶段为止，采取最优策略时的数量指标值。为止，采取最优策略时的数量指标值。f1(s1)为整体最优指标函数值。为整体最优指标函数值。nk

23、jjjjnkkkusvoptVoptsf),()(,第第50页页顺序解法：顺序解法：阶段指标阶段指标vk(sk+1,uk)表示第表示第 k 阶段的指标函数值。阶段的指标函数值。过程指标函数过程指标函数V1,k 表示从第表示从第 1 阶段开始到第阶段开始到第 k+1 阶段的状态阶段的状态 sk+1 为为止，采取策略止，采取策略 s0,s1,u1,s2,u2,sk,uk,sk+1 时时的数量指标值。的数量指标值。第第51页页当过程指标函数为阶段指标和形式时：当过程指标函数为阶段指标和形式时：当过程指标函数为阶段指标积形式时：当过程指标函数为阶段指标积形式时：kjjjjkusvV11,1),(kjj

24、jjkusvV11,1),(第第52页页 最优指标函数最优指标函数 fk(sk+1)表示从第表示从第 1 阶段开始到第阶段开始到第 k+1 阶段的状态阶段的状态 sk+1为止，采取最优策略时的数量指标值。为止，采取最优策略时的数量指标值。fn(sn+1)为整体最优指标函数值。为整体最优指标函数值。),()(11,11 kjjjjkkkusvoptVoptsf第第53页页（3）基本方程形式不同）基本方程形式不同 逆序解法：逆序解法：当过程指标函数为阶段指标函数的和形式当过程指标函数为阶段指标函数的和形式 时：时：nkjjjjnkusvV),(,0)(1,.,1,),(),()(1111nnkkk

25、kkkksfnnksfusvoptsf第第54页页当过程指标函数为阶段指标函数的积形式当过程指标函数为阶段指标函数的积形式 时：时：nkjjjjnkusvV),(,1)(1,.,1,),(),()(1111nnkkkkkkksfnnksfusvoptsf第第55页页顺序解法：顺序解法：当过程指标函数为阶段指标函数的和形式当过程指标函数为阶段指标函数的和形式 时：时：0)(,.,2,1),(),()(10111sfnksfusvoptsfkkkkkkk kjjjjkusvV11,1),(第第56页页当过程指标函数为阶段指标函数的积形式当过程指标函数为阶段指标函数的积形式 时：时：1)(,.,2,

26、1),(),()(10111sfnksfusvoptsfkkkkkkk kjjjjkusvV11,1),(第第57页页动态规划模型建立后，对基本方程分段求解，不像动态规划模型建立后，对基本方程分段求解，不像线性规划那样有固定的解法，必须根据具体问题的线性规划那样有固定的解法，必须根据具体问题的特点，结合数学技巧灵活求解，大体有以下几种方特点，结合数学技巧灵活求解，大体有以下几种方法。法。第第58页页动态规划模型中的状态变量与决策变量若被限定只动态规划模型中的状态变量与决策变量若被限定只能取离散值，则可采用分段穷举法。能取离散值，则可采用分段穷举法。前面的最短路问题的求解方法就是分段穷举算法，前

27、面的最短路问题的求解方法就是分段穷举算法，由于每段的状态变量和决策变量离散取值个数较少，由于每段的状态变量和决策变量离散取值个数较少，所以动态规划的穷举法要比一般的穷举法有效。用所以动态规划的穷举法要比一般的穷举法有效。用分段穷举法求最优指标函数值时，最重要的是正确分段穷举法求最优指标函数值时，最重要的是正确确定每段状态变量取值范围和允许决策集合范围。确定每段状态变量取值范围和允许决策集合范围。第第59页页例：某公司有资金例：某公司有资金10万元，若投资于项目万元，若投资于项目i（i=1,2,3）的投资额为的投资额为xi时，其收益分别为时，其收益分别为g1(x1)=4x1，g2(x2)=9x2

28、，g3(x3)=2x32，问应如何分配投资额才能，问应如何分配投资额才能使总收益最大？使总收益最大？第第60页页解：解：1.建立模型建立模型（1）选择决策变量）选择决策变量uk=xk：表示第：表示第 k 阶段确定的投资额。阶段确定的投资额。uk=xk，k=1,2,3 第第61页页（2）选择状态变量）选择状态变量 sk：表示第：表示第 k 阶段到第阶段到第 3 阶段可供用于投资使用的阶段可供用于投资使用的资金数量。（满足无后效性）资金数量。（满足无后效性）设状态变量为设状态变量为s1、s2、s3、s4：s1=10；s2=s1-x1；s3=s2-x2；s4=s3-x3 =0 、110sx 220s

29、x 330sx 第第62页页（3）状态转移方程）状态转移方程（4）选择指数函数）选择指数函数Vk,3：表示从第：表示从第 k 阶段的状态阶段的状态 sk 开始，到第开始，到第 3 阶段阶段为止，采取投资策略（为止，采取投资策略（xk，x3）时所创造的收）时所创造的收益。益。Vk,3=，k=1,2,3（满足分离性和递推关系）（满足分离性和递推关系）kkkxss 1 3)(kiiixg第第63页页（5）选择最优指标函数）选择最优指标函数 fk(sk)：表示从第：表示从第 k 阶段的状态阶段的状态 sk 开始，到第开始，到第 3 阶段阶段为止，采取最优投资策略（为止，采取最优投资策略（xk，x3）时

30、所创造）时所创造的收益。的收益。),.,(max)(33,xxVsfkkkk 第第64页页（6）确定动态规划的基本方程）确定动态规划的基本方程 0)(1,2,3),()(max)(44110sfksfxgsfkkkksxkkkk第第65页页2.逆序解法逆序解法 第一步：第一步：当当 k=4，S4=s4 f4(s4)=0第二步：第二步：当当 k=3，S3=s3 f3(s3)=u3(s3)=x3=s3 232302304433022max02max)()(max333333sxxsfxgsxsxsx 第第66页页第三步：第三步：当当 k=2，S2=s2 f2(s2)=29max)()(max232

31、0332202222sxsfxgsxsx 22222)(29)(maxxsxxZ )(29max2222022xsxsx 问题：问题：第第67页页490)(49022222 sxxsxZ04222 xZ4922 sx 又又不是极大值点，舍去。不是极大值点，舍去。第第68页页故极大值只能在故极大值只能在 x2=0 或或 x2=s2 处取得。处取得。x2=0 f2(s2)=；x2=s2 f2(s2)=9s2 222s（1）如果）如果x2=0为极大值点，即为极大值点，即 时：时：u2(s2)=x2=0 29922222 sss2222220222)(29max)(22sxsxsfsx 第第69页页（

32、2）如果）如果x2=s2为极大值点，即为极大值点，即 时：时：u2(s2)=x2=s2 29922222 sss222220229)(29max)(22sxsxsfsx 第第70页页第四步：第四步：当当k=1，S1=s1 f1(s1)=（1）f2(s2)=时：时：，u2(s2)=x2=0f1(s1)=问题：问题：)(4max)()(max2210221101111sfxsfxgsxsx 222s292 s21111)(24)(maxxsxxZ )(24max24max2111022101111xsxsxsxsx 第第71页页10)(44011111 sxxsxZ04212 xZ111 sx不是

33、极大值点，舍去。不是极大值点，舍去。又又 第第72页页故极大值只能在故极大值只能在 x1=0 或或 x1=s1 处取得。处取得。x1=0 f1(s1)=；x1=s1 f1(s1)=4 s1212s 如果如果 x1=0为极大值点，即为极大值点，即 ：u1(s1)=x1=0 2421121 sss2121110112)(24max)(11sxsxsfsx 第第73页页最优策略为：最优策略为：s1=10，x1=0，s2=10，x2=0，s3=10，x3=s3=10 第第74页页 如果如果x1=s1为极大值点，即为极大值点，即 时时：因为因为s1=10，故该情况不存在。，故该情况不存在。2421121

34、 sss第第75页页（2）f2(s2)=9s2 时：时：，u2(s2)=x2=s2 f1(s1)=u1(s1)=x1=0)(94max94max11102101111xsxsxsxsx 1110959max11sxssx 292 s第第76页页最优策略为：最优策略为：s1=10，x1=0，s2=10，x2=10，s3=0，x3=s3=0该策略中：该策略中：状态状态 s2=10 同同 矛盾，故该策略舍去。矛盾，故该策略舍去。292 s第第77页页例：用逆序解法求解例：用逆序解法求解 3,2,1,0max3213221ixcxxxxxxzi第第78页页解：令解：令g1(x1)=x1，g2(x2)=

35、，g3(x3)=x3 过程指标函数为阶段指标函数的积形式。过程指标函数为阶段指标函数的积形式。设状态变量为设状态变量为s1、s2、s3、s4：s1=c；s2=s1-x1；s3=s2-x2；s4=s3-x3 0 、22x110sx 220sx 330sx 第第79页页第一步：当第一步：当k=4，S4=s4 f4(s4)=1 第二步：当第二步：当k=3，S3=s3 f3(s3)=u3(s3)=x3=s3 3303044330333333max1max)()(maxsxxsfxgsxsxsx 第第80页页第三步：当第三步：当k=2，S2=s2 f2(s2)=问题：问题：)(maxmax)()(max

36、22220322033220222222xsxsxsfxgsxsxsx )()(max22222xsxxZ 第第81页页又又222222223200320sxxxxsxZ 或或2222262xsxZ 022222 sxZ当当x2=0 时：时：，不是极大值点，舍去。，不是极大值点，舍去。第第82页页当当 x2=时：时：，为极大值点。，为极大值点。x2=f3(s4)=u2(s2)=x2=232s022222 sxZ232s32274s232s第第83页页第四步：当第四步：当k=1，S1=s1 f1(s1)=问题：问题：)(274max274max)()(max3111032102211011111

37、1xsxsxsfxgsxsxsx 31111)(274)(maxxsxxZ 第第84页页又又当当 x1=s1 时：时：，不是极大值点，舍去。，不是极大值点，舍去。1111112111410)4()(2740sxsxxsxsxZ 或或)2)(981111212xsxsxZ 0212 xZ第第85页页x1=f1(s1)=u1(s1)=x1=141s41641scs41411 当当 x1=时：时：，为极大值点。，为极大值点。141s03121222 sxZ第第86页页 最优策略为：最优策略为：s1=c，x1=，s2=，x2=，s3=，x3=s3=，s4=0 最优解为：最优解为：x1=，x2=，x3=

38、c41c43232sc21c41c41c41c41c21第第87页页例：某公司有资金例：某公司有资金10万元，若投资于项目万元，若投资于项目i（i=1,2,3）的投资额为的投资额为xi时，其收益分别为时，其收益分别为g1(x1)=4x1，g2(x2)=9x2，g3(x3)=2x32，问应如何分配投资额才能，问应如何分配投资额才能使总收益最大？使总收益最大？第第88页页解：解：1.建立模型建立模型（1）选择决策变量）选择决策变量uk=xk：表示第：表示第 k 阶段确定的投资额。阶段确定的投资额。uk=xk，k=1,2,3 第第89页页（2）选择状态变量）选择状态变量 sk+1：表示第：表示第 1

39、 阶段到第阶段到第 k 阶段的总投资额。（满足阶段的总投资额。（满足无后效性）无后效性）设状态变量为设状态变量为s1、s2、s3、s4：s1=s2-x1；s2=s3-x2；s3=s4-x3；s4=10 、210sx 320sx 430sx 第第90页页（3）状态转移方程）状态转移方程（4）选择指数函数）选择指数函数V1,k：表示从第：表示从第 1 阶段到第阶段到第 k 阶段的总投资额为阶段的总投资额为 sk+1时，采取投资策略（时，采取投资策略（x1，xk）时所创造的收益。）时所创造的收益。V1,k=，k=1,2,3（满足分离性和递推（满足分离性和递推关系）关系）kkkxss 1 kiiixg

40、1)(第第91页页（5）选择最优指标函数）选择最优指标函数 fk(sk+1)：表示从第：表示从第 1 阶段到第阶段到第 k 阶段的总投资额为阶段的总投资额为sk+1 时，采取最优投资策略（时，采取最优投资策略（x1，xk）时所创造）时所创造的收益。的收益。),.,(max)(1,11kkkkxxVsf 第第92页页（6）确定动态规划的基本方程）确定动态规划的基本方程 0)(3,2,1),()(max)(101011sfksfxgsfkkkksxkkkk第第93页页2.顺序解法顺序解法 第一步：当第一步：当k=0，S1=s1 f0(s1)=0第二步：当第二步：当k=1，S2=s2 f1(s2)=

41、u1(s2)=x1=s2 210101011044max04max)()(max212121sxxsfxgsxsxsx 第第94页页第三步：当第三步：当k=2，S3=s3 f2(s3)=u2(s3)=x2=s3 49max)()(max220212203232sxsfxgsxsx 333230232095454max)(49max3232sssxsxsxsxsx 第第95页页第四步：当第四步：当k=3，S4=s4 f3(s4)=问题：问题：92max)()(max3230323304343sxsfxgsxsx )(92max3423043xsxsx )(92)(max34233xsxxZ 第第

42、96页页490940333 xxxZ04232 xZ493 x又又不是极大值点，舍去。不是极大值点，舍去。第第97页页故极大值只能在故极大值只能在 x3=0 或或 x3=s4 处取得。处取得。x3=0 f3(s4)=9s4；x3=s4 f3(s4)=242s第第98页页 如果如果x3=0为极大值点，即为极大值点，即 ：f3(s4)=u3(s4)=x3=029294244 sss4342309)(92max43sxsxsx 第第99页页最优策略为：最优策略为：s1=0，x1=s2=0，s2=0，x2=s3=10，s3=10，x3=0，s4=10 该策略中状态该策略中状态 s4=10 同同 矛盾，

43、故该策略舍矛盾，故该策略舍去。去。294 s第第100页页 如果如果x3=s4为极大值点，即为极大值点，即 ：f3(s4)=u3(s4)=x3=s429294244 sss24342302)(92max43sxsxsx 第第101页页最优策略为：最优策略为：s1=0，x1=s2=0，s2=0，x2=s3=0，s3=0，x3=s4=10，s4=10该策略中状态该策略中状态 s4=10 同同 不矛盾，为最优不矛盾，为最优策略。策略。294 s第第102页页例：用顺序解法求解例：用顺序解法求解 3,2,1,09231224max321232221ixxxxxxxzi第第103页页解：令解：令g1(x

44、1)=，g2(x2)=，g3(x3)=指标函数为阶段指标函数的和形式。指标函数为阶段指标函数的和形式。设状态变量为设状态变量为s1、s2、s3、s4：s1=s2-3x1=0；s2=s3-2x2；s3=s4-x3；s49 、214x22x 12223 x2130sx 3220sx 430sx 21310sx 32210sx 430sx 第第104页页第一步：当第一步：当k=0，S1=s1 f0(s1)=0 第二步：当第二步：当k=1，S2=s2 f1(s2)=u1(s2)=x1=231s2221310213101011310944max04max)()(max212121sxxsfxgsxsxs

45、x 第第105页页第三步：当第三步：当k=2，S3=s3 f2(s3)=问题：问题：94max)()(max222221021222103232sxsfxgsxsx 9169794max)2(94max2322230223222103232xsxsxsxsxsx 23222329169794)(max xsxsxZ 第第106页页又又 不是极大值点，舍去。不是极大值点，舍去。故极大值只能在故极大值只能在 x2=0 或或 处取得。处取得。323227809169140sxsxxZ 0914222 xZ3278sx 3221sx 第第107页页x2=0 f2(s3)=；f2(s3)=0 x2=0

46、为极大值点，为极大值点，f3(s4)=u2(s3)=x2=0 2394s2394s3221sx 2341s 第第108页页第四步：当第四步：当k=3，S4=s4 f3(s4)=问题：问题：94122max)()(max23230323304343sxsfxgsxsx )(94122max23423043xsxsx 234233)(94122)(max xsxxZ 第第109页页又又 不是极大值点，舍去。不是极大值点，舍去。故极大值只能在故极大值只能在 x3=0 或或 x3=s4 处取得。处取得。434331120989440sxsxxZ 0944232 xZ43112sx 第第110页页x3=

47、0 f3(s4)=x3=s4 f3(s4)=129424 s12224 s12212942424 ss x3=s4为极大值点，为极大值点，f3(s4)=u3(s4)=x3=s412224 s第第111页页问题：问题：当当 s4=9 时，时，f3(s4)达到最大值，达到最大值，f3(s4)=174所以可得：所以可得：u3(s4)=x3=s4=9 122)(max2443904 ss fs第第112页页最优策略为：最优策略为：s1=0，x1=0，s2=0，x2=0，s3=0，x3=s4=9，s4=9 最优解为：最优解为：x1=0，x2=0，x3=9 231s第第113页页 nixaxxgzinii

48、niii,.,2,1,0)(max11第第114页页 0)(1,.,1,),()(max)(11110nnkkkksxkksfnnksfxgsfkk其动态规划模型的基本方程为：其动态规划模型的基本方程为：第第115页页1.令令 sk=0,2,m，把区间，把区间 0,a 进行进行分割，分割，的大小可依据问题所要求的精度以及计算的大小可依据问题所要求的精度以及计算机的容量来定；机的容量来定；2.规定状态变量及决策变量只在离散点规定状态变量及决策变量只在离散点 0,2,m上取值，相应的指标函数上取值，相应的指标函数 fk(sk)就被定就被定义在这些离散值上，递推方程变为：义在这些离散值上，递推方程变

49、为：第第116页页 0)(1,2,3),()(max)(111,.,1,0nnkkkmpkksfkpsfpgsf3.按逆序方法，逐步递推求出按逆序方法，逐步递推求出 fn(sn),f1(s1)，最，最后求出最优方案。后求出最优方案。第第117页页例例 用连续变量的离散化方法求解下列问题。用连续变量的离散化方法求解下列问题。)3,2,1(010294max3212321ixxxxxxxzi第第118页页解：解：令令=2，将区间将区间 0,10 分割成分割成 0,2,4,6,8,10 六个点，六个点，即状态即状态 sk 集合为集合为 0,2,4,6,8,10 。允许决策集合为允许决策集合为 0 x

50、k sk，xk 与与 sk 均在分割点上均在分割点上取值。取值。第第119页页第一步：第一步：当当k=3，S3=0,2,4,6,8,10 f3(s3)=2max23033xsx s30246810 x30020240246024680246810g30080832083272083272083272032720246810128128 200f3(s3)*3x1282008第第120页页第二步：第二步：当当 k=2，S2=0,2,4,6,8,10 f2(s2)=)(9max2232022xsfxsx s20246810 x2002024024602468024 6810081832263672