资源描述：
《《运筹学动态规划》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、管理运筹学教程第三章动态规划清华大学出版社图3-1清华大学出版社名词解释阶段，用k表示。状态、状态变量，用Sk表示，通常是集合决策、决策变量，通常用uk或xk表示。状态转移及其方程：过程与子过程策略与子策略：指标函数与最优值函数：清华大学出版社二、最优化原理与动态规划的基本方法Bellman原理动态规划的基本方法逆向顺序法前向顺序法清华大学出版社Bellman原理示意图清华大学出版社逆向顺序法求解例3-2清华大学出版社第二节动态规划建模与求解步骤建立动态规划模型的基本要求动态规划的求解步骤清华大学出版社一、建立动态规划模型的基本要求将问题划分成若干阶段。有的问题的阶段性很明显，有的则不
2、明显，需要分析后人为假设。确定各阶段的状态变量，并给出状态转移方程，状态转移方程的形式应当与递推顺序一致。状态变量应当满足无后效性要求。明确指标函数，给出最优函数递推方程，递推方程的形式应当与递推顺序一致。清华大学出版社二、动态规划的求解步骤正确划分阶段。确定状态变量和决策变量，并给出状态变量和决策变量的可行集合。确定求解的递推顺序，给出状态转移方程。确定阶段、子过程(子策略)的指标函数，确定最优值函数的递推方程和边界条件。递推求解。与递推过程反向求出最优策略(最优决策变量值系列)和最优状态变化路线。清华大学出版社第三节动态规划的应用举例定价问题资源分配问题生产存储问题清华大学出版社一
3、、定价问题某公司考虑为某新产品定价，该产品的单价拟从每件5元、6元、7元和8元这四个中选取一个，每年允许价格有1元幅度的变动，该产品预计畅销五年，据预测不同价格下各年的利润如表3-1所示。清华大学出版社表3-2每年预计利润额单价第一年第二年第三年第四年第五年5元6元7元8元1012141612131415151616152020181425241814清华大学出版社建立数学模型按年划分阶段，k=1,2,...,5每阶段的状态变量为本年(上一年已确定)的价格，状态变量的可行集合Sk=(5,6,7,8)。决策变量为每年依据当年价格为下一年度决定价格，根据题意决策变量的可行集合是：采用逆序算
4、法，因此状态转移方程是最优值函数递推方程为清华大学出版社进行各阶段的计算采用逆序法，设当k=5时，S5=(5,6,7,8)，由表3-1得到当k=4时，S4=(5,6,7,8)，由递推方程得清华大学出版社继续求解清华大学出版社反推得最优路线按照与求最优值函数方向相反的顺序求最优状态路线：最优决策变量。即从第一年单价应为8元开始，向后推算。得第二年定价8元，第三年定价7元，第四年定价6元，第五年定价5元。最大利润值为92万元。清华大学出版社用决策图求解清华大学出版社二、资源分配问题某公司将5台加工中心分配给甲、乙、丙、丁四个工厂，各工厂或设备后可产生如表3-2所示的利润，应怎么分配设备可使
5、公司总利润最大？清华大学出版社工厂设备数甲乙丙丁012345067101215037912130510111111046111212清华大学出版社建立数学模型按工厂次序划分阶段，k=1，2，3，4状态变量为各阶段可用于分配的设备总台数决策变量是分配给第k工厂的设备数采用逆序算法，状态转移方程最优值函数递推方程清华大学出版社第4阶段的最优解当k=4时，S4=(0,1,2,3,4,5)012345012345046111212046111212012345清华大学出版社第3阶段的最优解当k=3时，S3=(0,1,2)000000010105404551201205106406910102清
6、华大学出版社第3阶段的最优解（续）当k=3时，S3=3301230510111164011111411142清华大学出版社第3阶段的最优解（续）当k=3时，S3=44012340510111112116401216161511161，2清华大学出版社第3阶段的最优解（续）当k=3时，S3=550123450510111111121211640121721171511212清华大学出版社第2阶段的最优解当k=2时，S2=(0,1,2)000000010103505350201203710501087100清华大学出版社第2阶段的最优解（续）当k=2时，S2=330123037914105
7、01413129140清华大学出版社第2阶段的最优解（续）当k=2时，S2=4401234037912161410501617171412171，2清华大学出版社第2阶段的最优解（续）当k=2时，S2=55012345037912132116141050211921191715210，2清华大学出版社第1阶段的最优解（续）当k=1时，S1=550123450671012152117141050212321201715231清华大学出版社第4阶段
