第6章 动态规划 运筹学ppt.pptVIP

一、引例 动态：相对于静态：只考虑一个计划期。 动态规划：考虑多个计划期，多个阶段的优化问题。 研究对象：多阶段决策问题 例1（时间阶段）某种设备可在高低两种不同的负荷下进行生产，设在高负荷下投入生产的设备数量为x，产量为g=10x，设备年完好率为a=0.75；在低负荷下投入生产的设备数量为y，产量为h=8y,年完好率为b=0.9。假定开始生产时完好的设备数量s1=1000台。 制定一个5年计划，确定每年投入高、低两种负荷下生产的设备数量，使5年内产品的总数量达到最大。 二、动态规划的基本思想 3、确定决策变量 uk 及决策集合 Dk（sk）。 4、写出状态转移方程 sk+1 = Tk（sk，uk）。 5、定义阶段指标值（函数） vk（sk，uk）。 6、定义第 k至 n 阶段（后部子过程）的最优指标（目标）函数 fk（sk）。 7、作出动态规划结构图： 8、建立动态规划基本方程：（逆序递推方程） （一）最短路径问题 (二) 资源分配问题 例1（连续）：某公司有资金10万元，若投资于项目i（i = 1，2，3）的投资额为 时，其收益分别为 问题：如何分配投资数额才能使总收益最大？ 动态规划模型的建立 阶段k：按项目为3个阶段，k=1，2，3。 状态变量 ：第k阶段初拥有的可以分配给第k到第3个项目的资金和。 决策变量 ：决定给第k阶段（项目）的资金。 状态转移方程： 阶段指标函数： 过程指标函数： 例2（离散） 某公司新引进了 6 台高效率生产设备，该设备可用于生产 4 种不同的产品，当生产每种产品所投入的设备数量不同时所带来的利润也不相同。其详细资料如下： 该公司这 6 台设备在 4 种产品的生产中能够发挥最大的效益，应该如何分配这 6 台设备，才能获得最大的总利润？ 分析、建模 此决策问题如按 4 种产品的一种顺序（可以任意排列，不妨按产品的自然顺序），将产品 1 分配的设备数量作为第一阶段需作出的决策，将产品 2 分配的设备数量作为第二阶段需作出的决策，将产品 3 分配的设备数量作为第三阶段需作出的决策，将产品 4 分配的设备数量作为第四阶段需作出的决策，这显然就是一个多阶段决策问题。因此有： 1、阶段 k ：第 k 种产品，k=1，2，3，4 2、状态变量 sk ：当按顺序用于第 k 种产品分配设备时所余有的设备总量。 3、决策变量 uk ：分配给第 k 种产品的设备数量。 Dk（sk）= { uk | uk =0，1，2，…， sk } 4、状态转移方程： sk+1 = sk - uk 5、定义阶段指标值（函数） vk（sk，uk）= vk（ uk ）：即分配给第 k 种产品的设备数量为 uk 时，第 k 种产品所创造的利润（如利润表）。 6、定义 fk（sk）：第 k 种产品分配设备时所余有的设备数量为 sk ，第 k 种产品至第四种产品所创造的利润总和 。（第 k 种产品至第四种产品按某种设备分配策略所创造的最大总利润 。 7、作出动态规划结构图： 8、建立动态规划基本方程：（逆序递推方程） k= 4 时，状态集合 —— S4={ 0，1，2，3，4，5，6 } f4（s4）= max [ v4（ u4）＋0] k= 3 时，状态集合 —— S3={ 0，1，2，3，4，5，6 } f3（s3）= max [ v3（ u3）+ f4（s4）] k= 2 时，状态集合 —— S2={ 0，1，2，3，4，5，6 } f2（s2）= max [ v2（ u2）+ f3(s3）] k= 1 时，状态集合 —— S1={ 6 } f1（s1）= max [ v1（ u1）+ f2（s2）] 该公司设备分配的所有最优方案： 例3（离散）背包问题 动态规划模型的建立 例5 机器负荷分配问题 某种机器可在两种负荷下进行生产。在高负荷下生产的产量函数为 g = 8 u1 （ u1 为投入的机器数量），年完好率为 a = 0.7 ；在低高负荷下生产的产量函数为 h = 5y （y 为投入的机器数量），年完好率为 b = 0.9 。开始生产时完好机器数量 s1 = 1000台，问每年如何分配机器在两种负荷下进行生产，使五年内生产的产品总产量最高。 建立动态规划模型： 1