1、 第二节 动态规划的基本方法 动态规划的基本解法： 1、网络图解法； 2、表格法； 3、迭代法。 三种方法的共同点： 都是用逆推计算方法，即由最后一个阶段往回推到最前的一个阶段实现最优。一、网络图解法 例1、如图给定一个线路网络，两点之间连线上的数字表示两点之间的距离（或费用），试求一条由 的铺管线路，使总距离最短（或费用最少）。A GAB1C1B2C2C3C4D1D3D2E1E2E3F1F2G531368766385338422123335526643437597681310912131618 31318 例2、某企业有5000万元的一笔投资款，拟投资三个项目，对每个项目的投资方案、投资金额
2、、投资效益（新增加收益）如表。问这笔资金应如何分配使用，使总收益最大？投资金额（万元）投资效益（万元）项目 项目 项目010002000300040000150026003500-0-280039004000013002500-ABCEDFGHI 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)0130025004100530028006400
3、6800二、表格法 例3 某公司欲将7万元的资金分配给下属三个企业，资金分配方案及 方案下 企业的 收益如表，公司 现有方案 ， 用 种 使公司的收益最 ？企业 分配方案及收益分配 收益 分配 收益 分配 收益1 0 0 0 0 0 02 1 5 1 3 2 73 2 8 3 9 3 114 3 10 5 11 4 13一、 定基本 及 推 1、 2、 态 方 3、 推 1 1k k ks S x+ += -方 企业 企业 企业K=3 K=2 K=11 11 1*0 0* *1 1 1 1 1*1 1 1 1 1( ) 0,( ) ( , ) ( ) ( , ) ( )maxmaxk Skk Skk k k k k k kxk k k k k kxf Sf S R S x f SR S x f S x+ + + + + + + + + + += += + -表一41374136413541343113272001000（万元）（万元）*1 1( )f S*1x1S表二表三
