《运筹学课件第七章_动态规划》课件.ppt

* 运筹学 设xj 为第j 种物品的装件数（非负整数）则问题的数学模型如下： * 运筹学 例题：求下面背包问题的最优解 物品 1 2 3 重量（公斤） 3 2 5 使用价值 8 5 12 * 运筹学 用动态规划方法求解 阶段： 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 求解见板书 * 运筹学 练习：某厂生产三种产品，各种产品重量与利润的关系如表所示。现将此三种产品运往市场出售，运输能力总重量不超过 6 吨，问如何安排运输，使总利润最大？ 种类 1 2 3 重量（吨/公斤） 2 3 4 单件利润（元） 80 130 180 最优方案：X1 =（0.2.0）X2 =（1.0.1）Z=260 * 运筹学 四、复合系统工作可靠性问题 某种机器的工作系统由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,为提高成功率,可以给各组增加人员,现有三个人可以加入到研究工作中,问如何分配人手,使项目总成功率最大? 成功率 一 二 三 0 0.6 0.4 0.2 1 0.8 0.6 0.5 2 0.85 0.8 0.7 阶段： k=1，2，3,对应给第k个小组分配人手的过程 状态Sk:表示可供分配第k个到第3个小组的总人数 决策变量xk:表示分配给第k个小组的人数 状态转移方程: Sk+1 =Sk–xk 阶段指标函数:V k=Pk(xk) 基本方程: fk(Sk)=max{Vk· fk+1(Sk+1)}(k=3,2,1) f4(S4)=1 * 运筹学 阶段k 状态Sk 决策Uk 阶段指标Vk 状态转移Sk+1 fk+1(Sk+1) fk(Sk) 最优策略Uk* K=3 0 2 1 0 1 2 0.2 0.5 0.7 0 0 0 1 1 1 0.2 0.5 0.7 0 1 2 K=2 0 0 0.4 0 0.2 0.08 0 1 0 1 0.4 1 0.5 0.2 0.6 0 0.2 0.12 0 2 0 1 2 0.4 0.6 0.8 2 1 0.7 0.5 0.2 0.28 0.30 0.16 0 1 K=1 2 0 1 2 0.6 0.8 0.85 2 1 0 0.3 0.2 0.08 0.18 0.16 0.068 0 因此z*=0.18,X*=(0,1,1) 小组 人手 一 二 三 0 0.6 0.4 0.2 1 0.8 0.6 0.5 2 0.85 0.8 0.7 * * * * 运筹学 例:分割问题 阶段： k=1，2，…,n,对应给第k个变量赋值的过程 状态Sk:表示可供分配第k个到第n个变量赋值的总和 决策变量xk:表示给第k个变量赋的值 状态转移方程: Sk+1 =Sk–xk 阶段指标函数:V k=xk 基本方程: fk(Sk)=max