补充:动态规划 Data, Model and decisions 数据、模型与决策 补充 动态规划 RuC Information School, Ye Xiang, 2007
补充：动态规划 RUC Information School，Ye Xiang，2007 Data， Model and Decisions 数据、模型与决策 补充 动态规划
本章内容 补充:动态规划 动态规划问题概述 动态规划在经济管理中的应用 本章的具体内容可以参见胡运权主编《运筹学教程》( 第二版)清华大学出版社,2004.2第七章动态规划 ,但它不是用 Excel求解,而是用动态规划方法手工求 解。这里想告诉大家,用 Excel求解动态规划问题非常 简单(如第三章P65案例:大沼泽地金色年代公司的现 金流问题)。 也就是说,本章介绍的是用 Excel来求解动态规划问题 ,但并没有介绍动态规划方法,有兴趣的同学可以参考 国内运筹学书籍中的“动态规划”章节 RuC Information School, Ye Xiang, 2007
补充：动态规划 RUC Information School，Ye Xiang，2007 本章内容 ➢ 动态规划问题概述 ➢ 动态规划在经济管理中的应用 本章的具体内容可以参见胡运权主编《运筹学教程》（ 第二版）清华大学出版社，2004.2 第七章 动态规划 ，但它不是用Excel求解，而是用动态规划方法手工求 解。这里想告诉大家，用Excel求解动态规划问题非常 简单（如第三章P65案例：大沼泽地金色年代公司的现 金流问题）。 也就是说，本章介绍的是用Excel来求解动态规划问题 ，但并没有介绍动态规划方法，有兴趣的同学可以参考 国内运筹学书籍中的“动态规划”章节
动态规划问题概述 补充:动态规划 动态规划是解决多阶段决策过程最优化问题的一种方法。该方法是 由美国数学家贝尔曼( R Bellman等人在20世纪50年代初提出的。 他们针对多阶段决策问题的特点,提出了解决这类问题的最优化原 理,并成功地解决了生产管理、工程技术等方面的许多实际问题, 从而建立了运筹学的一个新分枝,即动态规划。 动态规划是现代企业管理中的一个重要决策方法,可用于解决最优 路径问题、资源分配问题、生产计划与库存、投资、装载、排序等 问题及生产过程的最优控制等。由于它有独特的解题思路,在处理 某些优化问题时,比线性规划或非线性规划方法更有效。 多阶段决策过程:是指这样一类特殊的活动过程,它们可以按时间 顺序分解成若干互相联系的阶段,称为“时段”,在每一个时段都 要做出决策,全部过程的决策是一个决策序列,所以多阶段决策问 题属序惯决策问题。 多阶段决策过程最优化的目标是要达到整个活动过程的总体效果最 优。由于各阶段决策间有机地联系着,本段决策的执行将影响到下 段的决策,以至于影响总体效果,所以决策者在每段决策时不仅 考虑本阶段最优,还应考虑对最终目标的影响,从而做出对全局来 讲是最优的决策。 RuC Information School, Ye Xiang, 2007
补充：动态规划 RUC Information School，Ye Xiang，2007 动态规划问题概述 • 动态规划是解决多阶段决策过程最优化问题的一种方法。该方法是 由美国数学家贝尔曼(R Bellman)等人在20世纪50年代初提出的。 他们针对多阶段决策问题的特点，提出了解决这类问题的最优化原 理，并成功地解决了生产管理、工程技术等方面的许多实际问题， 从而建立了运筹学的一个新分枝，即动态规划。 • 动态规划是现代企业管理中的一个重要决策方法，可用于解决最优 路径问题、资源分配问题、生产计划与库存、投资、装载、排序等 问题及生产过程的最优控制等。由于它有独特的解题思路，在处理 某些优化问题时，比线性规划或非线性规划方法更有效。 • 多阶段决策过程：是指这样一类特殊的活动过程，它们可以按时间 顺序分解成若干互相联系的阶段，称为“时段”，在每一个时段都 要做出决策，全部过程的决策是一个决策序列，所以多阶段决策问 题属序惯决策问题。 • 多阶段决策过程最优化的目标是要达到整个活动过程的总体效果最 优。由于各阶段决策间有机地联系着，本段决策的执行将影响到下 一段的决策，以至于影响总体效果，所以决策者在每段决策时不仅 考虑本阶段最优，还应考虑对最终目标的影响，从而做出对全局来 讲是最优的决策
动态规划在经济管理中的应用补充:动态规划 动态规划在经济管理中的应用 ◇最短路线问题(例1和扩展)一工程线路 问题 ◆背包问题(例2和扩展) ☆生产经营问题(例3~例6) 营业资金管理(例7~例10) 资源分配问题(例11~例12) RuC Information School, Ye Xiang, 2007
补充：动态规划 RUC Information School，Ye Xiang，2007 动态规划在经济管理中的应用 ➢ 动态规划在经济管理中的应用 ❖ 最短路线问题（例1和扩展）－工程线路 问题 ❖ 背包问题（例2和扩展） ❖ 生产经营问题（例3～例6） ❖ 营业资金管理（例7～例10） ❖ 资源分配问题（例11～例12）
动态规划在经济管理中 的应用一最短路线间题 补充:动态规划 例1:最短路线问题一工程线路问题 给定一个线路网络图,要从A地向F地铺设一条输油管道,各 点间连线上的数字表示距离,问应选择什么路线,可使总距离 最短? ◇在Eκce中的解法:用第七章网络最优化问题的74节最短路问 题(P257,A节点为源,F节点为目的地) 最短赂题的扩展:货郎担问题和中国邮路问题(我 们已经讲过) ( B1 ( E1 A ()4 F B2)1C3)4 C4 RuC Information School, Ye Xiang, 2007
补充：动态规划 RUC Information School，Ye Xiang，2007 动态规划在经济管理中 的应用－最短路线问题 ➢ 例1：最短路线问题－工程线路问题 ❖ 给定一个线路网络图，要从A地向F地铺设一条输油管道，各 点间连线上的数字表示距离，问应选择什么路线，可使总距离 最短? ❖ 在Excel中的解法：用第七章网络最优化问题的7.4节最短路问 题（P257，A节点为源，F节点为目的地） ➢ 最短路线问题的扩展：货郎担问题和中国邮路问题（我 们已经讲过） 5 A B1 B2 C2 C3 C1 C4 D2 D3 D1 E1 E2 F 7 5 2 3 6 8 4 7 8 4 5 3 4 8 4 3 5 6 2 1 3 4 3