运筹学课件第七章-动态规划.ppt

运筹学 二、解题思路 三、应用范围 1、动态 2、静态 四、缺点 1、建模后，没有统一的方法 2、维数障碍 第二节 动态规划的基本概念 阶段指标与指标函数的关系有两种： 1）指标函数是它所含有的各阶段的阶段指标之和。 即Vkn(Sk,Pkn）= ∑ Vj(Sj, Uj),j=k,…n 那么有Vkn(Sk,Pkn）= Vk (Sk,Uk）+ Vk+1 n(Sk+1,Pk+1 n） 2）指标函数是它所含有的各阶段的阶段指标之积。 即Vkn(Sk,Pkn）= ∏Vj(Sj, Uj),j=k,…n 那么有Vkn(Sk,Pkn）= Vk (Sk,Uk）· Vk+1 n(Sk+1,Pk+1 n） 8、最优指标函数：指标函数的最优值，称为最优值函数。用fk(Sk)=optVkn(Sk,Pkn) opt表示最优化，常取max或min。 二、动态规划的基本思想和基本方程 第三节 动态规划应用举例一、最短路径问题 表上作业法 二、资源分配问题1、一维资源分配 三、背包问题 用动态规划方法求解 阶段： k=1，2，3,对应第k种物品的选择过程 状态Sk:表示可供分配第k种到第3种物品的重量 决策变量xk:表示分配给第k种物品的件数 状态转移方程: S1 =5,S2= S1 – 2x2, S3= S2 – 2x3 阶段指标函数:V 1= 8x1, V 2= 5x2 ,V 3= 12x3 基本方程: fk(Sk)=max{Vk +fk+1(Sk+1)}(k=3,2,1) f4(S4)=0 求解见板书 四、复合系统工作可靠性问题 某种机器的工作系统由n个部件串联组成，只要有一个部件失灵，整个系统就不能正常工作。为了提高系统工作的可靠性，在每个部件上均装有主要元件的备用件，并设计了备用元件自动投入装备，显然，备用元件越多，整个系统工作的可靠性就越大，但备用元件增多也会导致系统的成本、重量体积相应增大，工作精度降低，因此，在考虑上述限制条件下，如何选择各部件的备用元件数，使整个系统的工作可靠性最大？ 建模：设部件i装有xi个备用元件时，正常工作的概率为Pi(xi),那么整个系统正常工作的概率Z=∏ Pi(xi)（i=1，…,n）,设部件i的单位重量级wi,,那么总重量不超过w的情况下,如何配备备用件,使Z最大? 用动态规划方法求解 阶段： k=1，2，n,对应给第k个部件分配配件的过程 状态Sk:表示可供分配第k个到第n个部件的总重量 决策变量xk:表示分配给第k个部件配备的备用件数 状态转移方程: Sk+1 =Sk–wkxk 阶段指标函数:V k=Pk(xk) 基本方程: fk(Sk)=max{Vk· fk+1(Sk+1)}(k=n,…,2,1) fk+1(Sk+1)=1 例:三个科研小组分别对某一项目的一个部件研究,成功率分别为0.6,0.4,0.2,为提高成功率,可以给各组增加人员,现有三个人可以加入到研究工作中,问如何分配人手,使项目总成功率最大? 例:分割问题 Maxz=x1·x22·x3 x1+x2+x3=C xi≥0 五、生产与库存问题 某厂要对一种产品制订今后四个时期的生产计划,拒估计在今后四个时期内，市场对于该产品的需求量见表.假定该厂生产每批产品的固定成本为3千元,若不生产则为0,每单位产品成本为1千元,每个时期生产能力所允许的最大生产批量不超过6个单位,最大库存为3个单位,每个时期未出售的产品,每单位储存费需0.5千元/时期.假定在第一时期的初始库存量为0,第四个时期末库存量也为0.问该厂应如何安排各个时期的生产与库存,才能在满足市场需要的条件下,使成本为最小? 阶段:k=1,2,3,4 状态变量Sk：第k个月初的库存量 决策变量UK：第k个月的产量 状态转移方程：Sk+1=Sk+Uk-gk 指标函数：Vk＝0.5Sk＋3y＋UK fk(Sk)=min{Vk+fk(Sk+1)} 七：采购与销售问题 某商店在未来的4个月里，准备利用它的一个仓库来专门经销某种商品，仓库最大的容量为1000个单位。假定该商店每月只能卖出仓库现有的货，当商店在某月购买货物时，下月初才能到货，预测该商品未来4个月的买卖价格。假定商店在1月开始经销时，仓库贮存该商品500个单位，试问若不计库存费用，该商店应如何制定1－4月订购与销售计划，使获利为最大？ 阶段:k=1,2,3,4 状态变量Sk：第k个月初仓库中的存货 决策变量XK：第k个月的卖出的量 Yk：第k个月的订购的量 状态转移方程：Sk+1=Sk+Yk-Xk 指标函数：Vk＝PkXk-CkX