动态规划.pptx

2019/11/28管理运筹学课程组ftp://:理解:动态规划基本概念、最优化原理和基本方程,通过资源分配和生产与存储等问题,学习应用动态规划解决多阶段决策问题。重点:掌握动态规划模型结构、逆序法算法原理、资源分配、设备更新、生产于存贮等问题。难点:为动态规划中状态变量等的确定。2019/11/28管理运筹学课程组ftp://://:生产与存贮问题某工厂生产并销售某种产品,已知今后4个月市场需求预测如表2-1所示,每月生产单位产品的费用为其中为生产的固定费用,为可变生产费率,为生产能力。供应需求所剩余产品应存入仓库,每月库存单位产品的费用为(千元)2019/11/28管理运筹学课程组ftp://。试制定4个月的生产计划,在满足用户需求的条件下使总费用最小。i1234需求23242019/11/28管理运筹学课程组ftp://。系统在某个时刻的状态,往往要依某种形式受过去某些决策的影响;将时间作为决策变量之一的决策问题称为动态决策问题。如经济系统,生产系统等。动态系统:线性系统、非线性系统。动态系统的特点:动态决策问题:而系统的当前状态和决策又会影响系统今后的发展。动态规划的研究对象:2019/11/28管理运筹学课程组ftp://(或阶段)根据系统所处的状态,不断地做出决策;每个阶段都要进行决策,目的是使整个过程的决策达到最优效果。动态决策问题的特点:系统所处的状态和时刻是进行决策的重要因素;找到不同时刻的最优决策以及整个过程的最优策略。多阶段决策问题:是动态决策问题的一种特殊形式;在多阶段决策过程中,系统的动态过程可以按照时间进程分为状态相互联系而又相互区别的各个阶段;2019/11/28管理运筹学课程组ftp://::企业在生产过程中,由于需求是随时间变化的,因此企业为了获得全年的最佳生产效益,就要在整个生产过程中逐月或逐季度地根据库存和需求决定生产计划。:某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时,产品的年产量g和投入生产的机器数量u1的关系为g=g(u1)12n状态决策状态决策状态状态决策2019/11/28管理运筹学课程组ftp://,机器的年完好率为a,即如果年初完好机器的数量为u,到年终完好的机器就为au,0<a<1。在低负荷下生产时,产品的年产量h和投入生产的机器数量u2的关系为h=h(u2)假定开始生产时完好的机器数量为s1。要求制定一个五年计划,在每年开始时,决定如何重新分配完好的机器在两种不同的负荷下生产的数量,使在五年内产品的总产量达到最高。相应的机器年完好率b,0<b<1。2019/11/28管理运筹学课程组ftp://:由于航天飞机的运动的环境是不断变化的,因此就要根据航天飞机飞行在不同环境中的情况,不断地决定航天飞机的飞行方向和速度(状态),使之能最省燃料和实现目的(如软着落问题)。不包含时间因素的静态决策问题(本质上是一次决策问题)也可以适当地引入阶段的概念,作为多阶段的决策问题用动态规划方法来解决。、非线性规划等静态的规划问题也可以通过适当地引入阶段的概念,应用动态规划方法加以解决,后面将详细介绍。2019/11/28管理运筹学课程组ftp://:给定一个交通网络图如下,其中两点之间的数字表示距离(或花费),试求从A点到E点的最短距离(总费用最小)。