《运筹》教学课件动态规划 8.4离散动态规划建模与求解.ppt

《《运筹》教学课件动态规划 8.4离散动态规划建模与求解.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、8.4离散动态规划建模与求解例1设从甘肃要铺一条煤气管道到北京，途中须经过三个省：陕西、山西、河北，每省设一个中间站。各省建站可供选择的地点及各段距离如下图，现要求选择一条甘肃到北京的铺管线路，使总距离最短。8.4.1离散例子○A○B○C○D○E○F○G○H○I○J北京河北山西陕西甘肃8458961610967738423例2（生产与存储问题）某工厂生产并销售某种产品。已知今四个月市场需求预测如下表，又每月生产j个单位产品的费用为每月库存i个单位产品的费用E(i)=0.5i(千元），该厂最大库存容量为3

2、个单位，每月最大生产能力为6个单位，计划开始和计划期末库存量都是零，试制定四个月的生产计划，在满足用户需求条件下，使总费用最小。i月1234di需求23248.4.1离散动态规划的建模举例8.3.2离散动态规划建模及求解8.4.2离散动态规划建模及求解8.4.2离散动态规划建模及求解8.4.3离散动态规划的举例—正向求解例1设从甘肃要铺一条煤气管道到北京，途中须经过三个省：陕西、山西、河北，每省设一个中间站。各省建站可供选择的地点及各段距离如下图，现要求选择一条甘肃到北京的铺管线路，使总距离最短。○A○

3、B○C○D○E○F○G○H○I○J北京河北山西陕西甘肃84589616109677384238.4.3离散动态规划举例—正向求解○A○B○C○D○E○F○G○H○I○J北京河北山西陕西甘肃84589616109677384238.4.3离散动态规划举例—正向求解○A○B○C○D○E○F○G○H○I○J北京河北山西陕西甘肃84589616109677384238.4.3离散动态规划举例—正向求解第二步求解○A○B○C○D○E○F○G○H○I○J北京河北山西陕西甘肃84589616109677384238.

4、4.3离散动态规划举例—正向求解第二步求解○B○C○D○E○F○G山西陕西109677388.4.3离散动态规划举例—正向求解第二步求解○B○C○D○E○F○G山西陕西109677388.4.3离散动态规划举例—正向求解第二步求解○B○C○D○E○F○G山西陕西109677388.4.3离散动态规划举例—正向求解第二步求解○E河北○F○G○H○I山西5896168.3.3离散动态规划举例—正向求解第二步求解○E○F○G○H○I河北山西5896168.4.3离散动态规划的举例—正向求解第二步求解○H○I○

5、J北京河北848.4.3离散动态规划的举例—正向求解结论：○A○B○C○D○E○F○G○H○I○J北京河北山西陕西甘肃8458961610967738423例2（生产与存储问题）某工厂生产并销售某种产品。已知今四个月市场需求预测如下表，又每月生产j个单位产品的费用为每月库存i个单位产品的费用E(i)=0.5i(千元），该厂最大库存容量为3个单位，每月最大生产能力为6个单位，计划开始和计划期末库存量都是零，试制定四个月的生产计划，在满足用户需求条件下，使总费用最小。i月1234di需求23248.4.3离

6、散动态规划的举例——反向求解8.4.3离散动态规划的举例——反向求解8.4.3离散动态规划的举例——反向求解8.4.3离散动态规划的举例——反向求解第一步过程描述8.4.3离散动态规划的举例—反向求解第二步求解i月1234di23248.4.3离散动态规划的举例—反向求解第二步求解s40123f4(s4)76.565.58.4.3离散动态规划的举例—反向求解第二步求解s40123f4(s4)76.565.58.4.3离散动态规划的举例—反向求解第二步求解s40123f4(s4)76.565.58.4.3

7、离散动态规划的举例—反向求解第二步求解s40123f4(s4)76.565.58.4.3离散动态规划的举例—反向求解第二步求解s30123f3(s3)1211.5888.4.3离散动态规划的举例—反向求解第二步求解s30123f3(s3)1211.5888.4.3离散动态规划的举例—反向求解第二步求解s30123f3(s3)1211.5888.4.3离散动态规划的举例—反向求解第二步求解s30123f3(s3)1211.5888.4.3离散动态规划的举例—反向求解第二步求解s20123f2(s2)161

8、5.51513.58.4.3离散动态规划的举例—反向求解结论：动态规划模型的求解总结解法离散型连续型：分段穷举法：利用解析方法没有固定的方法具体模型具体分析要求：经验、技巧、灵活难！