第二节 动态规划的基本方法.pptVIP

第二节 动态规划的基本方法 动态规划的基本解法： 1、网络图解法； 2、表格法； 3、迭代法。 三种方法的共同点： 都是用逆推计算方法，即由最后一个阶段往回推到最前的一个阶段实现最优。 一、网络图解法 例1、如图给定一个线路网络，两点之间连线上的数字表示两点之间的距离（或费用），试求一条由 的铺管线路，使总距离最短（或费用最少）。 例2、某企业有5000万元的一笔投资款，拟投资三个项目，对每个项目的投资方案、投资金额、投资效益（新增加收益）如表。问这笔资金应如何分配使用，使总收益最大？ 二、表格法 例3 某公司欲将7万元的资金分配给下属三个企业，资金分配方案及在此方案下各企业的预期收益如表，公司在现有方案中，采用哪种组合才使公司的预期收益最高？ 一、确定基本要素及递推关系 1、 2、状态转移方程 3、递推关系式 表一 表二 表三 三、连续型动态规划的函数迭代法 三、函数迭代法求解动态规划的步骤 * A B1 C1 B2 C2 C3 C4 D1 D3 D2 E1 E2 E3 F1 F2 G 5 3 1 3 6 8 7 6 6 3 8 5 3 3 8 4 2 2 1 2 3 3 3 5 5 2 6 6 4 3 4 Ⅰ 3 7 5 9 7 6 8 13 10 9 12 13 16 18 Ⅱ Ⅲ Ⅳ Ⅴ Ⅵ 3 5 6 9 13 18 0 1300 2500 ---- ---- 0 ---- 2800 3900 4000 0 1500 2600 3500 ---- 0 1000 2000 3000 4000 项目Ⅲ 项目Ⅱ 项目Ⅰ 投资效益（万元） 投资金额（万元） A B C E D F G H I Ⅰ Ⅱ Ⅲ 1000(1300) 200(2500) 2000(2500) 0(0) 3000(3900) 2000(2800) 4000(4200) 2000(2800) 3000(3900) 2000(2800) 4000(4000) 0(0) 3000(3900) 2000(2600) 1000(1500) 3000(3500) 0(0) 0 1300 2500 4100 5300 2800 6400 6800 2500 6400 6800 6800 6800 6800 分配方案 及收益 13 4 11 5 10 3 4 11 3 9 3 8 2 3 7 2 3 1 5 1 2 0 0 0 0 0 0 1 收益 分配 收益 分配 收益 分配 Ⅲ Ⅱ Ⅰ 企业 过程进行方向 企业Ⅰ 企业Ⅱ 企业Ⅲ K=3 K=2 K=1 4 13 7 4 13 6 4 13 5 4 13 4 3 11 3 2 7 2 0 0 1 0 0 0 （万元） （万元） * * *