8.动态规划.ppt

第八章 动态规划 第八章 动态规划 第一节 多阶段决策过程及实例 通常的决策问题分为两大类： 静态决策 贪心算法 每一步都走最短的线路： A—B2—C4—D3—E2—F2—G，长度为21 最短的线路: A—B1—C2—D1—E2—F2—G，长度为18 枚举法 列出每条可能的路线，然后算出每条路的长度，从中选择最优路线。 缺点是线路太多，随点数增加很快。 例2 （机器负荷分配问题） 某企业拥有完好的机器y台，将它们按照高负荷和低负荷两种生产方式生产，已知收益函数分别是： g=g(x) 和 h=h(x) x为机器数量。设高负荷下生产时机器的年完好率为a，低负荷下生产时机器的年完好率为b（0≤a≤1，0≤b≤1） 问：对总数量为y的机器进行分配用于生产，试制定一个五年计划，应如何分配每年投入高负荷和低负荷的机器数量，才能使总收益最大？（n个阶段的决策问题） 例3（生产与存储问题） 某工厂生产并销售某种产品，已知今后四个月市场需求预测及每月生产j个单位产品的费用如下： 起始状态=终止状态=0； 每月产量不超过6单位； 月末库存不超过3单位； 满足每个月的市场需求。 最简单，按月需求生产—方案1：2 3 2 4 不按照月需求生产，如—方案2：2 5 0 4 .... 方案1的费用：(5+6+5+7)+0=23(万元) 方案2的费用：(5+8+0+7)+0.5*2=21(万元) ...... 第二节 动态规划的基本概念和基本方程 常见的指标函数有： 1)整个过程和它的任一子过程的指标函数是它所包含的各阶段的指标的和。 Vk,n（Sk，Uk ，Sk＋1 ，…,Sn+1）＝ Vk,n（Sk，Uk，Sk＋1，…,Sn+1） ＝vk(sk,uk)+ Vk+1,n（Sk+1，Uk+1 ，Sk＋2 ，…,Sn+1） 2)整个过程和它的任一子过程的指标函数是它所包含的各阶段的指标的乘积，即： Vk,n（Sk，Uk ，Sk＋1 ，…,Sn+1）＝ 指标函数的最优值称为最优值函数，记为fk(sk)。 表示从第k阶段的状态sk开始到第n阶段的终止状态的过程，采取最优策略所得到的指标函数值。如：f1(A)＝18，f2(B1)＝13。 即 fk(sk)＝ opt Vk,n(sk,uk,…,sn,un) （uk,…,un） 式中的“opt”（optimization）可根据具体问题而取min或max。 一般情况下，k阶段和k+1阶段之间的递推关系式可写成： fk(Sk)＝opt{ vk(Sk,Uk(Sk))+ fk+1(Sk+1) } k=n,n-1,…,2,1 或fk(Sk)＝opt{ vk(Sk,Uk(Sk))* fk+1(Sk+1) } k=n,n-1,…,2,1 生产与存储问题 某工厂生产并销售某种产品，已知今后四个月市场需求预测及每月生产j个单位产品的费用如下： (1)划分五个阶段，阶段变量k=1,2,…，5 如图给定一个线路网络，两点之间连线上的数字表示两点间的距离(或费用)。试求一条从A到G的铺管线路，使总距离最短(或总费用最小)。 从A点到G点可分成6个阶段。以A为起点，终点有两个B1、B2，有两个选择。若选择B2，则B2为第一阶段决策的结果。同时它又是第二阶段的开始状态。当每个阶段做出决策的结果，直接影响到后面的选择和决策的结果。 最短路线有一个重要特性： 如果从起点A经过C2点和D1点到达终点G是一条最短的路线，则由C2 点经过D1 点到达G点的这条子路线，是由C2 点出发到达G点所有路线中的最短路线。 寻找最短路线的方法，从最后一段开始，由后向前逐步推进，找出各点到G点的最短路线，最后就能确定一条从A点到G点的最短路线。 最短路线为A→B1→C2→D1→E2→F2→G 二、动态规划的建模条件 三、动态规划的基本方程 状态转移图 顺推解法 第三节 动态规划的最优性原理和最优性定理 二、最优性定理 证明： 若允许策略p*0, n-1是最优策略，对于任意一个k(0kn-1)， 它的子策略p*k,n-1对于以 为起点的k到n-1子过程来说，必是最优的。 第四节 动态规划的求解方法 第一节 一维资源分配问题 第三阶段：给第三市场分配 s3 有0－9种可能，第三阶段最优决策表如下： 第二阶段：给第二市场分配 s2 有0~9种可能，第二阶段最优决策表如下： 第一阶段：给第一市场分配 由边界条件s1=9，第一阶段最优决策表如下： 三、连续的一维资源分配问题 例3 机器负荷分配问题（P217－22