第章动态规划ppt课件.ppt
《第章动态规划ppt课件.ppt》由会员分享,可在线阅读,更多相关《第章动态规划ppt课件.ppt(78页珍藏版)》请在三一文库上搜索。
1、第十章 动态规划,1 多阶段决策过程最优化问题举例 2 基本概念、基本方程与最优化原理 3 动态规划的应用(1) 4 动态规划的应用(2),1,1 多阶段决策过程最优化问题举例,例1 最短路径问题 下图表示从起点A到终点E之间各点的距离。求A到E的最 短路径。,2,B,C,B,D,B,C,D,E,C,4,1,2,3,1,2,3,1,2,3,2,2,1,6,4,7,2,4,8,3,8,6,7,5,6,1,10,6,3,7,5,1,1 多阶段决策过程最优化问题举例,用穷举法的计算量: 如果从A到E的站点有k个,除A、E之外每站有3个位置则 总共有3k-12条路径; 计算各路径长度总共要进行 (k+
2、1) 3k-12次加法以及 3k-12-1次比较。随着 k 的值增加时,需要进行的加法和比较的 次数将迅速增加; 例如当 k=20时,加法次数为 4.25508339662271015 次, 比较 1.37260754729771014 次。若用1亿次/秒的计算机计算 需要约508天。,3,1 多阶段决策过程最优化问题举例,讨论: 1、以上求从A到E的最短路径问题,可以转化为四个性质完全相 同,但规模较小的子问题,即分别从Di 、Ci、Bi、A到E的最短路径问题。 第四阶段:两个始点D1和D2,终点只有一个; 表10-1 分析得知:从D1和D2到E的最短路径唯一。,4,5,第三阶段:有三个始点
3、C1,C2,C3,终点有D1,D2,对始点 和终点进行分析和讨论分别求C1,C2,C3到D1,D2 的最短路 径问题: 表10-2 分析得知:如果经过C1,则最短路为C1-D2-E; 如果经过C2,则最短路为C2-D2-E; 如果经过C3,则最短路为C3-D1-E。,1 多阶段决策过程最优化问题举例,6,第二阶段:有4个始点B1,B2,B3,B4,终点有C1,C2,C3。对始点和终点进行分 析和讨论分别求B1,B2,B3,B4到C1,C2,C3 的最短路径问题: 表10-3 分析得知:如果经过B1,则走B1-C2-D2-E; 如果经过B2,则走B2-C3-D1-E; 如果经过B3,则走B3-C
4、3-D1-E; 如果经过B4,则走B4-C3-D1-E。,1 多阶段决策过程最优化问题举例,7,第一阶段:只有1个始点A,终点有B1,B2,B3,B4 。对始点和终 点进行分析和讨论分别求A到B1,B2,B3,B4的最短路径问题: 表10-4 最后,可以得到:从A到E的最短路径为A B4 C3 D1 E 距离为14.,1 多阶段决策过程最优化问题举例,8,以上计算过程及结果,可用图2表示,可以看到,以上方法不仅 得到了从A到D的最短路径,同时,也得到了从图中任一点到E的最 短路径。 以上过程,仅用了22次加法,计算效率远高于穷举法。,B,C,B,D,B,C,D,E,C,4,1,2,3,1,2,
5、3,1,2,3,3,2,1,6,4,7,2,4,8,3,8,6,7,5,1,6,10,6,0,10,6,12,11,11,12,13,14,14,12,7,5,1,2,1 多阶段决策过程最优化问题举例,9,一、基本概念: 1、阶段k:表示决策顺序的离散的量,阶段可以按时间或空间划分。 2、状态sk:能确定地表示决策过程当前特征的量。状态可以是数量,也可以是字符,数量状态可以是连续的,也可以是离散的。 3、决策xk:从某一状态向下一状态过渡时所做的选择。决策是所在状态的函数,记为xk(sk)。 决策允许集合Dk(sk):在状态sk下,允许采取决策的全体。 4、策略Pk,n(sk):从第k阶段开始
6、到最后第n阶段的决策序列,称k子策略。P1,n(s1)即为全过程策略。 5、状态转移方程 sk+1=Tk(sk, xk):某一状态以及该状态下的决策,与下一状态之间的函数关系。,2 基本概念、基本方程与最优化原理,10,6、阶段指标函数vk(sk, xk):从状态sk出发,选择决策xk所产生的第k阶段指标。 过程指标函数Vk,n(sk, xk, xk+1, xn):从状态sk出发,选择决策xk, xk+1, , xn所产生的过程指标。动态规划要求过程指标具有可分离 性,即 Vk,n(sk, xk, xk+1, , xn) = vk(sk, xk)+Vk+1(sk+1, xk+1, , xn)
7、称指标具有可加性,或 Vk,n(sk, xk, xk+1, , xn) = vk(sk, xk)Vk+1(sk+1, xk+1, , xn)称指标具有可乘性。 二、基本方程: 最优指标函数fk(sk):从状态sk出发,对所有的策略Pk,n,过程指 标Vk,n的最优值,即,2 基本概念、基本方程与最优化原理,11,对于可加性指标函数,上式可以写为 上式中“opt”表示“max”或“min”。对于可乘性指标函数,上式可以 写为 以上式子称为动态规划最优指标的递推方程,是动态规划的基本 方程。 终端条件:为了使以上的递推方程有递推的起点,必须要设定最 优指标的终端条件,一般最后一个状态n+1下最优指
8、标fn+1(sn+1) = 0。,2 基本概念、基本方程与最优化原理,12,三、最优化原理 作为整个过程的最优策略具有如下性质: 不管在此最优策略上的某个状态以前的状 态和决策如何,对该状态来说,以后的所有决 策必定构成最优子策略。就是说,最优策略的 任意子策略都是最优的。,2 基本概念、基本方程与最优化原理,13,一、资源分配问题 例2. 某公司拟将某种设备5台,分配给所属的甲、乙、丙三个工 厂。各工厂获得此设备后,预测可创造的利润如表10-5所示,问这 5台设备应如何分配给这3个工厂,使得所创造的总利润为最大? 表10-5,3 动态规划的应用(1),14,解:将问题按工厂分为三个阶段,甲、
9、乙、丙三个厂分别编号为1、2、3。设 sk= 分配给第k至第3个工厂的设备台数(k=1、2、 3)。 xk=分配给第k个工厂的设备台数。 已知s1=5, 并有 从 与 的定义,可知 以下我们从第三阶段开始计算。,3 动态规划的应用(1),15,第三阶段: 显然将 台设备都分配给第3工厂时, 也就是 时,第3阶段的指标值(即第3厂的盈利) 为最大,即 由于第3阶段是最后的阶段,故有 其中 可取值为0,1,2,3,4,5。其数值计算见表106。,3 动态规划的应用(1),16,表106,3 动态规划的应用(1),17,其中 表示取3子过程上最优指标值 时的 决策,例如在表10-6中可知当 =4时,
10、有 有 此时 ,即当 时,此时取 (把4台设备分配给第3厂)是最优决策,此时阶段指标值 (盈利)为12,最优3子过程最优指标值也为12。 第二阶段: 当把 台设备分配给第2工厂和第3工 厂时,则对每个 值,有一种最优分配方案,使最大盈利 即最优2子过程最优指标函数值为,3 动态规划的应用(1),18,因为 上式也可写成 其中x2可取值0,1,2,3,4,5,其数值计算如表107所示。 表107,3 动态规划的应用(1),19,其中在 的这一行里,当 时, 这里 从表105中可知,把1台设备交给乙厂所 得盈利数即可,知 ,这里 从表10-6 查 即可知 =11。同样可知当 时,可知 ; 当 时,
11、 ; 当 时, 当 时,,3 动态规划的应用(1),20,由于 ,不可能分2厂5台设备,故 时, 栏空着不填。从这些数值中取得最大即 得 ,即有 =16。在此行中我们在取最大值的 上面加一横以示区别,也可知这时 的最优决策为1或2。,3 动态规划的应用(1),21,第一阶段: 把 台设备分配给第1,第2,第3厂时,最大 盈利为 其中 可取值0,1,2,3,4,5. 数值计算见表108 表10-8 然后按计算表格的顺序推算,可知最优分配方案有两个: 1.由于 ,根据 ,查表107可 知 ,再由 ,求得 。即分配 给甲厂0台,乙厂2台,丙厂3台。 2.由于 ,根据 ,查表107可,3 动态规划的应
12、用(1),22,知 ,再由 ,求得 , 即分配给甲厂2台,乙厂2台,丙厂1台。 这两种分配方案都能得到最高的总盈利21万元。,3 动态规划的应用(1),23,二、背包问题 设有n种物品,每一种物品数量无限。第i种物品每件 重量为wi公斤,每件价值ci元。现有一只可装载重量为W 公斤的背包,求各种物品应各取多少件放入背包,使背 包中物品的价值最高。,3 动态规划的应用(1),24,下面用动态规划逆序解法求解它。设 阶段变量k:第k次装载第k种物品(k=1, 2, , n) 状态变量sk:第k次装载时背包还可以装载的重量; 决策变量uk = xk:第k次装载第k种物品的件数; 决策允许集合:Dk(
13、sk) = xk | 0 xksk/wk,xk为整数; 状态转移方程: sk+1 = sk wkxk; 阶段指标: vk = ckxk; 最优过程指标函数fk(sk):第k到n阶段容许装入物品的最大使 用价值; 递推方程: fk(sk) = max ckxk+fk+1(sk+1) = max ckxk+fk+1(sk wkxk); xDk(sk) 终端条件: fn+1(sn+1) = 0。,3 动态规划的应用(1),25,例3. 某咨询公司有10个工作日可以去处理四种类型的咨 询项目,每种类型的咨询项目中待处理的客户数量、处理每个 客户所需工作日数以及所获得的利润如表109所示。显然该公 司在
14、10天内不能处理完所有的客户,它可以自己挑选一些客 户,其余的请其他咨询公司去做,应如何选择客户使得在这10 个工作日中获利最大? 表109,3 动态规划的应用(1),26,解:用动态规划来求解此题。 我们把此问题分成四个阶段,第一阶段我们决策将 处理多少个第一种咨询项目类型中的客户,第二阶段决 策将处理多少个第二种咨询项目类型中的客户,第三阶 段、第四阶段我们也将作出类似的决策。我们设 分配给第k种咨询项目到第四种咨询项目的所 有客户的总工作日(第k阶段的状态变量)。 =在第k种咨询项目中处理客户的数量(第k阶段 的决策变量)。 已知 10 并有,3 动态规划的应用(1),27,并从 与 的
15、定义可知 从第四阶段开始计算: 显然将 个工作日 尽可能分配给第四 类咨询项目,即 时,第四阶段的指标值为最大, 其中, 表示取不大于 的最大整数,符号 为 取整符号,故有 由于第四阶段是最后的阶段,故有,3 动态规划的应用(1),28,因为 至多为10,所以x4的取值可为0和1,其数值计算见表1010。 表1010,3 动态规划的应用(1),29,第三阶段: 当把 个工作日分配给第四类和第 三类咨询项目时,则对每个 值,都有一种最优分配方 案,使其最大盈利即最优3子过程最优指标函数值为 因为 因为 至多为10,所以 的取值可为0,1,2。其数值计算 见表1011。,3 动态规划的应用(1),
16、30,表1011,3 动态规划的应用(1),31,第二阶段: 同样以每个 值都有一种最优分配方案,使其最大盈利即 最优2子过程最优指标函数值为: 因为 ,故有 因为 至多为10,所以 的取值为0,1,2,3。其数值计算 见表1012。,3 动态规划的应用(1),3 动态规划的应用(1),32,表10-12,33,第一阶段: 我们已知 ,又因为 ,同样有 因为 ,故 可取值为0,1,2, ,10。其数值计算 见表1013。 表1013,3 动态规划的应用(1),34,从表1013可知 , 从而得 10 010,在表1012的 的这一行可知 ,由 ,查表1011的 的这一行可知 ,最后由 ,查表1
17、0-10的 的这 一行得 ,综上所述得最优解为: 此时最大盈利为28。 现在我们不妨假设该咨询公司的工作计划有所改变,只有 8个工作日来处理这四类咨询项目,那么该咨询公司如何选择 客户使得获利最大呢?我们不必从头开始重做这个问题,而只 要在第一阶段上把 改成8,重新计算就可得到结果,如表10 14所示,这是动态规划的一个好处。,3 动态规划的应用(1),35,表1014 如上一样可从表1014,1012,1011,1010得到两组最优解 如下: 它们的最优解(即最大盈利)都为22。 一旦咨询的工作日不是减少而是增加,那么我们不仅要重新计 算第一阶段,而且要在第二、第三、第四阶段的计算表上补上增
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 章动 规划 ppt 课件
链接地址:https://www.31doc.com/p-2565474.html