第八章动态规划.ppt

文档介绍：动态规划
(Dynamic programming)
动态规划的基本思想
最短路径问题
投资分配问题
背包问题
动态规划是解决多阶段决策过程最优化问题的一种方法。由美国数学家贝尔曼(Ballman)等人在20世纪50年代提出。他们针对多阶段决策问题的特点,提出了解决这类问题的“最优化原理”,并成功地解决了生产管理、工程技术等方面的许多实际问题。
动态规划是现代企业管理中的一种重要决策方法,可用于最优路径问题、资源分配问题、生产计划和库存问题、投资问题、装载问题、排序问题及生产过程的最优控制等。
动态规划模型的分类:
以“时间”角度可分成:
离散型和连续型。
从信息确定与否可分成:
确定型和随机型。
从目标函数的个数可分成:
单目标型和多目标型。
7-1 动态规划的基本原理
多阶段决策过程最优化
多阶段决策过程是指这样一类特殊的活动过程,他们可以按时间顺序分解成若干相互联系的阶段,在每个阶段都要做出决策,全部过程的决策是一个决策序列,所以多阶段决策问题也称为序贯决策问题。
例7-1 生产与存储问题
某工厂每月需供应市场一定数量的产品。供应需求所剩余产品应存入仓库,一般地说,某月适当增加产量可降低生产成本,但超产部分存入仓库会增加库存费用,要确定一个每月的生产计划,在满足需求条件下,使一年的生产与存储费用之和最小。
例7-2 投资决策问题
某公司现有资金Q亿元,在今后5年内考虑给A、B、C、D四个项目投资,这些项目的投资期限、回报率均不相同,问应如何确定这些项目每年的投资额,使到第五年末拥有资金的本利总额最大。
例7-3 设备更新问题
企业在使用设备时都要考虑设备的更新问题,因为设备越陈旧所需的维修费用越多,但购买新设备则要一次性支出较大的费用。
现在某企业要决定一台设备未来8年的更新计划,已预测到第j年购买设备的价格为Kj,Gj为设备经过j年后的残值,Cj为设备连续使用j-1年后在第j年的维修费用(j=1,2…8),问应在哪年更新设备可使总费用最小。
动态规划的基本概念
阶段;
状态;
决策和策略;
状态转移;
指标函数。