动态规划的基本方法

第二节动态规划的基本方法•动态规划的基本解法：•1、网络图解法；•2、表格法；•3、迭代法。•三种方法的共同点：•都是用逆推计算方法，即由最后一个阶段往回推到最前的一个阶段实现最优。一、网络图解法•例1、如图给定一个线路网络，两点之间连线上的数字表示两点之间的距离（或费用），试求一条由•的铺管线路，使总距离最短（或费用最少）。AGAB1C1B2C2C3C4D1D3D2E1E2E3F1F2G5313687663853384221233355266434Ⅰ37597681310912131618ⅡⅢⅣⅤⅥ35691318•例2、某企业有5000万元的一笔投资款，拟投资三个项目，对每个项目的投资方案、投资金额、投资效益（新增加收益）如表。问这笔资金应如何分配使用，使总收益最大？投资金额（万元）投资效益（万元）项目Ⅰ项目Ⅱ项目Ⅲ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)01300250041005300280064006800250064006800680068006800二、表格法•例3某公司欲将7万元的资金分配给下属三个企业，资金分配方案及在此方案下各企业的预期收益如表，公司在现有方案中，采用哪种组合才使公司的预期收益最高？企业ⅠⅡⅢ分配方案及收益分配收益分配收益分配收益10000002151327328393114310511413一、确定基本要素及递推关系•1、•2、状态转移方程•3、递推关系式11kkksSx过程进行方向企业Ⅰ企业Ⅱ企业ⅢK=3K=2K=11111*00**11111*11111()0,(){(,)()}{(,)()}maxmaxkSkkSkkkkkkkkxkkkkkkxfSfSRSxfSRSxfSx表一*11()fS*1x1S（万元）（万元）00010027231134134513461347134表二表三三、连续型动态规划的函数迭代法三、函数迭代法求解动态规划的步骤