补充:动态规划 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
动态规划在经济管理中 的应用一背包问题 补充:动态规划 例2:背包问题 位旅行者携带背包去登山,已知他所能承受的背包重量限度为a千 克,现有n种物品可供他选择装入背包,第种物品的单件重量为a1千 克,其价值(可以是表明本物品对登山的重要性的数量指标)是携 带数量x的函数c;x;(i=1,2,…,n),问旅行者应该如何选择携带 各种物品的件数,以使总价值最大?(背包问题等同于车、船、人造 卫星等工具的最优装载等,有广泛的实际意义) 代数模型(一维背包问题): 设x1为第i物品装入的件数,则整数规划模型: 目标(总价值最大):MaxP=Σcr1 总重量约束:∑a1x;≤a 非负约束:x1≥0且为整数(i=1,2,…,n) 在 Excel中的解法:用本书9.1节的一般整数规划 >背包问题的扩展 当x仅表示装入(取1)和不装(取0)第种物品,则本模型就是0-1背包 问题。 多维背包问题:当约束条件不止一个时,如多总体积的限制等 RuC Information School, Ye Xiang, 2007
补充：动态规划 RUC Information School，Ye Xiang，2007 动态规划在经济管理中 的应用－背包问题 ➢ 例2：背包问题 ❖ 一位旅行者携带背包去登山，已知他所能承受的背包重量限度为a千 克，现有n种物品可供他选择装入背包，第i种物品的单件重量为ai千 克，其价值（可以是表明本物品对登山的重要性的数量指标）是携 带数量xi的函数cixi（i=1，2，…，n），问旅行者应该如何选择携带 各种物品的件数，以使总价值最大？(背包问题等同于车、船、人造 卫星等工具的最优装载等，有广泛的实际意义) 代数模型（一维背包问题）： 设xi为第i种物品装入的件数，则整数规划模型： 目标(总价值最大)：Max P=cixi 总重量约束： aixi a 非负约束：xi 0 且为整数（i=1，2，…，n） 在Excel中的解法：用本书9.1节的一般整数规划 ➢ 背包问题的扩展 ➢ 当xi仅表示装入(取1)和不装(取0)第i种物品，则本模型就是0-1背包 问题。 ➢ 多维背包问题：当约束条件不止一个时，如多总体积的限制等
动态规划在经济管理中 的应用一0-1背包问题 补充:动态规划 >背包问题的扩展:0-1背包问题 某人准备外出旅游,行装中有A、B、C、D、E共5件备 选物品,其重量和价值如表所示,假定行李总重不得 超过13Kg,求总价值最大的行李构成方案。 物品 ABCDE 数学模型: 重量Kg7543 设x为第i种物品是否装入(1-是,0- 价值百元94320.5 否),则0-1整数规划模型: 目标(总价值最大): MaxP=9x1+4x2+3x3+2x4+0.5x5 重量约束:7x1+5x2+4x3+3x4+x≤13 0-1约束:x为0或1(=1,2,3,4,5) RuC Information School, Ye Xiang, 2007
补充：动态规划 RUC Information School，Ye Xiang，2007 动态规划在经济管理中 的应用－0-1背包问题 ➢ 背包问题的扩展：0-1背包问题 某人准备外出旅游，行装中有A、B、C、D、E共5件备 选物品，其重量和价值如表所示，假定行李总重不得 超过13Kg，求总价值最大的行李构成方案。 物品 A B C D E 重量/Kg 7 5 4 3 1 价值/百元 9 4 3 2 0.5 数学模型： 设xi为第i种物品是否装入（1-是，0- 否），则0-1整数规划模型： 目标(总价值最大)： Max P=9x1+4x2+3x3+2x4+0.5x5 重量约束：7x1+5x2+4x3 +3x4+x513 0-1约束：xi为0或1（i=1,2,3,4,5）
动态规划在经济管理中 的应用一多维背包间题 补充:动态规划 >背包问题的扩展:多维背包问题 现有一辆载重w=5t,最大装载体积v=8m3卡车作为运输 工具,可装载三种货物,已知每种货物各8件,其他有 关信息如表所示,求携带货物价值最大的装载方案。 货物品单件货单件货单件货 数学模型: 种k 物重量物体积物价值 设x为第k种物品装入的件数,则整 Wtwm3|p/万元 数规划模型: 2 30 目标(总价值最大) MaxP=30x1+75x2+60x3 2 3 4 75 重量约束:x1+3x2+2x3S5 3 2 3 体积约束:2x1+4x2+3x3≤8 货物件数:x≤8(k=1,2,3 非负约束:xk≥0且为整数(k=1,2,3) RuC Information School, Ye Xiang, 2007
补充：动态规划 RUC Information School，Ye Xiang，2007 动态规划在经济管理中 的应用－多维背包问题 ➢ 背包问题的扩展：多维背包问题 现有一辆载重w=5t，最大装载体积v=8m3卡车作为运输 工具，可装载三种货物，已知每种货物各8件，其他有 关信息如表所示，求携带货物价值最大的装载方案。 货物品 种k 单件货 物重量 wk /t 单件货 物体积 vk /m3 单件货 物价值 pk /万元 1 1 2 30 2 3 4 75 3 2 3 60 数学模型： 设xk为第k种物品装入的件数，则整 数规划模型： 目标(总价值最大)： Max P=30x1+75x2+60x3 重量约束：x1+3x2+2x3 5 体积约束：2x1+4x2+3x3 8 货物件数：xk 8 (k=1,2,3) 非负约束：xk 0 且为整数(k=1,2,3)
动态规划在经济管理中的 应用一生产经营问题 补充:动态规划 在生产和经营中,经常遇到如何合理安排 生产计划、采购计划以及仓库的存货计划 和销售计划,使总效益最大的问题。以下 是几个例子 口例3:P206生产进度安排(动态规划方法) 口例4:生产与库存问题(动态规划的另外 种写法:网络最优化中的最小费用流问题) 例5:P87习题3.3(多种解法) 例6:采购与销售问题 RuC Information School, Ye Xiang, 2007
补充：动态规划 RUC Information School，Ye Xiang，2007 动态规划在经济管理中的 应用－生产经营问题 • 在生产和经营中，经常遇到如何合理安排 生产计划、采购计划以及仓库的存货计划 和销售计划，使总效益最大的问题。以下 是几个例子 例3：P206 生产进度安排（动态规划方法） 例4：生产与库存问题（动态规划的另外一 种写法：网络最优化中的最小费用流问题） 例5：P87 习题3.3（多种解法） 例6：采购与销售问题
动态规划在经济管理中的应用补充:动态规划 生产经营问题(续) 例3:P206生产进度安排(动态规划方法) 在Exce中的解法,主要利用: 本月剩余量R=上月剩余量R1+ 本月生产量(x+y1) 本月计划安装量N 具体见本章的“补充一动态规划问题”的 Exce文件 RuC Information School, Ye Xiang, 2007
补充：动态规划 RUC Information School，Ye Xiang，2007 动态规划在经济管理中的应用 －生产经营问题（续） 例3： P206 生产进度安排（动态规划方法） 在Excel中的解法，主要利用： 本月剩余量Ri=上月剩余量Ri -1＋ 本月生产量（xi+yi）－ 本月计划安装量Ni 具体见本章的“补充－动态规划问题”的 Excel文件