文档介绍：第八章动态规划
教学内容:
动态规划问题实例
动态规划的基本概念与原理
动态规划应用举例
引言
动态规划是解决多阶段决策过程最优化的一种方法。
该方法是由美国数学家贝尔曼(R. E. Bellman)等人在20世纪50年代初提出的。他们针对多阶段决策问题的特点,提出了解决这类问题的“最优化原理”,并成功地解决了生产管理、工程技术等方面的许多问题,从而建立了运筹学的一个新的分支,即动态规划。
Bellman在1957年出版了《Dynamic Programming》一书,是动态规划领域中的第一本著作。
第一节动态规划问题及实例
动态规划是解决多阶段决策问题的一种方法,是现代企业管理中的一种重要决策方法,可用于最优路径问题、资源分配问题、生产计划和库存问题、投资问题、装载问题、排序问题及生产过程的最优控制等。
动态规划模型的分类:
以“时间”角度可分成:离散型和连续型。
从信息确定与否可分成:确定型和随机型。
从目标函数的个数可分成:单目标型和多目标型。
第一节动态规划问题及实例
一、多阶段决策过程
多阶段决策过程是指这样一类特殊的活动过程,他们可以按时间顺序分解成若干相互联系的阶段,在每个阶段都要做出决策,全部过程的决策是一个决策序列,所以多阶段决策过程也称为序贯决策过程。这种问题就称为多阶段决策问题。
二、多阶段决策问题的特点
过程可分为若干个相互联系的阶段;每一阶段都对应着一组可供选择的决策;每一决策的选定即依赖于当前面临的状态,又影响以后总体的效果。
第一节动态规划问题及实例
三、具体实例
1、最短路线问题
给定一个线路网络,
要从A向F铺设一条输油管道,各点间连
线上的数字表示距离,问应选择什么路线,可使总距离最短?
第一节动态规划问题及实例
2、生产与存储问题:
某工厂每月需供应市场一定数量的产品。供应需求所剩余产品应存入仓库,一般地说,某月适当增加产量可降低生产成本,但超产部分存入仓库会增加库存费用,要确定一个每月的生产计划,在满足需求条件下,使一年的生产与存储费用之和最小。
第一节动态规划问题及实例
3、投资决策问题
某公司现有资金Q亿元,在今后5年内考虑给A、B、C、D四个项目投资,这些项目的投资期限、回报率均不相同,问应如何确定这些项目每年的投资额,使到第五年末拥有资金的本利总额最大。
第一节动态规划问题及实例
4、设备更新问题
企业在使用设备时都要考虑设备的更新问题,因为设备越陈旧所需的维修费用越多,但购买新设备则要一次性支出较大的费用。
现在某企业要决定一台设备未来8年的更新计划,已预测到第j年购买设备的价格为Kj,Gj为设备经过j年后的残值,Cj为设备连续使用j-1年后在第j年的维修费用(j=1,2…8),问应在哪年更新设备可使总费用最小。
第二节动态规划的基本概念与原理
动态规划的基本概念
阶段;
状态;
决策和策略;
状态转移方程;
指标函数。
第二节动态规划的基本概念与原理
一。基本概念
阶段:是指问题需要做出决策的步数。阶段总数常记为n,相
应的是n个阶段的决策问题。阶段的序号常记为k,称为阶段
变量,k=1,2, …,n. k即可以是顺序编号也可以是逆序编号,
常用顺序编号。
状态:各阶段开始时的客观条件,第k阶段的状态常用状态
变量表示,状态变量取值的集合成为状态集合,用
表示。
例如,案例1中,