数学建模(动态规划)

(76页)

'数学建模(动态规划)'
动态规划 教学内容: ?动态规划问题实例 ?动态规划的基本概念与原理?动态规划的基本概念与原理 ?动态规划应用举例 引 言 动态规划是解决多阶段决策过程最优化的一种方法。 该方法是由美国数学家贝尔曼(R. E. Bellman)等人在20世该方法是由美国数学家贝尔曼( e)等人在 0世 纪50年代初提出的。他们针对多阶段决策问题的特点,提出 了解决这类问题的“最优化原理”,并成功地解决了生产管 理、工程技术等方面的许多问题,从而建立了运筹学的一个 新的分支,即动态规划。 Bellman在1957年出版了《Dynamic Programming》一书, 是动态规划领域中的第一本著作。 动态规划问题及实例 动态规划是解决多阶段决策问题的一种方法,是现代企 业管理中的一种重要决策方法,可用于最优路径问题、资源 分配问题生产计划和库存问题投资问题装载问题排分配问题、生产计划和库存问题、投资问题、装载问题、排 序问题及生产过程的最优控制等。 动态规划模型的分类动态规划模型的分类: 以“时间”角度可分成:离散型和连续型。 从信息确定与否可分成:确定型和随机型。 从目标函数的个数可分成单目标型和多目标型从目标函数的个数可分成:单目标型和多目标型。 动态规划问题及实例动态规划问题及实例 一、多阶段决策过程 多阶段决策过程是指这样一类特殊的活动过程,他们可以 按时间顺序分解成若干相互联系的阶段,在每个阶段都要做 出决策,全部过程的决策是一个决策序列,所以多阶段决策 过程也称为序贯决策过程。这种问题就称为多阶段决策问题。 二、多阶段决策问题的特点 过程可分为若干个相互联系的阶段;每一阶段都对应过程可分为若干个相互联系的阶段;每阶段都对应 着一组可供选择的决策;每一决策的选定即依赖于当前 面临的状态,又影响以后总体的效果。 动态规划问题及实例 三具体实例三、具体实例 1、最短路线问题 给定一个线路网络,要从A向F铺设一条输油管道,各点间连 线上的数字表示距离问应选择什么路线可使总距离最短?线上的数字表示距离,问应选择什么路线,可使总距离最短? 动态规划问题及实例 2生产与存储问题:2、生产与存储问题: 某工厂每月需供应市场一定数量的产品。供应需求所某厂每月需供应市场定数量的产品供应需求所 剩余产品应存入仓库,一般地说,某月适当增加产量可 降低生产成本但超产部分存入仓库会增加库存费用降低生产成本,但超产部分存入仓库会增加库存费用, 要确定一个每月的生产计划,在满足需求条件下,使一 年的生产与存储费用之和最小。 动态规划的基本概念与原理 动态规划的基本概念动态规划的基本概念 阶段;阶段; 状态;状态; 决策和策略;决策和策略; 状态转移方程;状态转移方程; 指标数指标数指标指标函函数数。。 动态规划的基本概念与原理动态规划的基本概念与原理 一基本概念。基本概念 阶段:是指问题需要做出决策的步数。阶段总数常记为n,相 应的是n个阶段的决策问题。阶段的序号常记为k,称为阶段 变量,k=1 2nk即可以是顺序编号也可以是逆序编号,变量,k=1,2, …,n. k即可以是顺序编号也可以是逆序编号, 常用顺序编号。 状态:各阶段开始时的客观条件,第k阶段的状态常用状态 变量表示,状态变量取值的集合成为状态集合,用 k s k S 变量表示,状态变量取值的集合成为状态集合,用 表示。 k k 例如案例1中}{}{BBSAS例如,案例1中,}.,{},{ 2121 BBSAS== 状状 状状 状状状 态 状 态 状 态 状 态 状 态 状 态 C1 2 5 B1 C2 D1 E1 4 2 3 6 8 4 5 3 5 6 4 A B2 C3 D2 D E2 F 5 8 7 3 4 8 6 2 1 3 B2 C4 D3 7 4 3 第1阶段第2阶段第3阶段第4阶段第5阶段 决策是指从某阶段的某个状态出发在若干个不同方案中决策:是指从某阶段的某个状态出发,在若干个不同方案中 做出的选择。表示决策的变量,称为决策变量,用表示。)( kk su 表示第k阶段当状态处于sk时的决策变量。 kk )( kk su 例如:表示走到C阶段,当处于C2 路口时,下一 步到D 123 )(DCu= 步到D1. 决策变量允许的取值范围称为允许决策集合,第k阶段状态为 时的允许决策集合记为,例如: )( kk sD},,{)( 32112 CCCBD= k s 策略:一个按顺序排列的决策组成的集合。由每段的决策 按顺序排列组成的决策函数序列 称为k子过程策略。简称子策略,记为。即 当k=1时,此决策函数序列成为全过程的一个策略,简称 策略记为策略,记为: 在实际问题中,可供选择的策略有一定的范围,此范围称 状态转移方程:是从上一阶段的某一状态值转变为下一阶段 为允许策略集合,用P表示。 某一状态值的转移规律,用 )(usTs= 表示 ),( 1kkkk usTs= +表示。 指标函数:分阶段指标函数和过程指标函数。阶段指标函数指标函数:分阶段指标函数和过程指标函数。阶段指标函数 是指第k阶段从状态出发,采取决策时的效益,用 k s k u ),( kkk usv 表示。而过程指标函数是从第k阶段的某状态出发, 采取子策略采取子策略 效益之和 时所得到的阶段 效益之和: 最优指标函数:表示从第k阶段状态为时采用最佳策略 k s 到过程终止时的最佳效益记为到过程终止时的最佳效益。记为 其中 opt 可根据具体情况取max 或min其中 opt 可根据具体情况取max 或min。 基本方程:此为逐段递推求和的依据,一般为: 1 () ( )opt { ( ,( ))(( ))},1,,2,1 ()0 kkk kkkkkkkkk uDs f sv s u sfu skn n f + ∈ ?=+=? ? ? ? ? ? ? ? 式中opt 可根据题意取 max 或 min. 11 ()0 nn fs ++ ? =? ? ? p 例如,案例1的基本方程为: 1 () ()min {(,())(())}5,4,3,2,1 kkk kkkkkkkkk uDs fsds usfusk + ∈ ?=+= ? ? ? ? ? 66 ()0fs ? =? ? ? 最优性原理:最优策略的子策略必为最优不管过去的状态最优性原理:最优策略的子策略必为最优。不管过去的状态 和决策如何,从眼下直到最后的诸决策必构成最优子策略。 动态规划的优点: ?可把一个N维优化问题化成N个一维优化问题求解。 ?函数方程中附加某些约束条件,可使求解更加容易。函数方程中附加某些约束条件,可使求解更加容易 ?求得最优解以后,可得所有子问题的最优解。 动态规划的缺点动态规划的缺点: ?“一个”问题,“一个”模型,“一个”求解方法。且 求解技巧要求比较高,没有统一处理方法。 动态规划动态规划应用举例应用举例动态规划动态规划应用举例应用举例 例最短路线问题例1 最短路线问题 基本思想如果起点 经过而到终点则由出基本思想:如果起点A经过B1,C1,D1,E1而到终点F,则由C1出 发经D1,E1到F点这条子路线,是从C1到F的最短路线。所以, 寻找最短路线应该从最后一段开始找然后往前递推寻找最短路线,应该从最后
关 键 词:
数学 建模 动态 规划
 天天文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
关于本文
本文标题:数学建模(动态规划)
链接地址: https://www.wenku365.com/p-42269482.html
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服点击这里,给天天文库发消息,QQ:1290478887 - 联系我们

本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有【成交的100%(原创)】。本站是网络服务平台方,若您的权利被侵害,侵权客服QQ:1290478887 欢迎举报。

1290478887@qq.com 2017-2027 https://www.wenku365.com 网站版权所有

粤ICP备19057495号 

收起
展开