动态规划应用举例ppt课件

1、第二节 动态规划应用举例 本节将通过动态规划的三种应用类型资源分配问题、复合系统可靠性问题、设备更新问题，进一步介绍动态规划的特点和处理方法。一、资源分配问题1. 问题的一般提法 设有某种资源，总数量为a，用于生产n种产品；若分配数量xi用于生产第i种产品，其收益为gi(xi)。问应如何分配，可使总收益最大？2. 数学规划模型xi种产品的资源数量为设分配给第决策变量： niiixgMaxz1)( 目标函数：nixaxinii,1,0 1约束条件：模型的特点变量分离。3.用动态规划方法求解阶段k状态sk决策xk=1,n表示把资源分配给第k种产品的过程；表示在给第k种产品分配之前还剩有的资源量；表

2、示分配给第k种产品的资源量；状态转移sk+1= sk- xk ；阶段指标vk指标函数vkn ；nkiiikkxgxg)()(,1,0,11nkffvMaxfnkkxkk基本方程12S1=ax1x2g1(x1)g2(x2) nxnsngn(xn)s2s3.例3 某公司拟将某种高效设备5台分配给所属甲、乙、丙3厂。各厂获此设备后可产生的效益如下表。问应如何分配，可使所产生的总效益最大？效益厂设备台数甲 乙 丙0 0 0 01 3 5 42 7 10 63 9 11 114 12 11 125 13 11 12解：阶段k状态sk决策xk=1,2,3依次表示把设备分配给甲、乙、丙厂的过程；表示在第k阶

3、段初还剩有的可分台数；表示第k阶段分配的设备台数；状态转移sk+1= sk- xk ；阶段指标vk指标函数vk3 ；阶段分配后产生的效益表示第3k)(iiixvk,1,0,1234kffvMaxfkkxkk基本方程问题：本问题是属于离散型还是属于连续型？怎样解？离散型，用表格的方式求解。效益厂设备台数甲 乙 丙0 0 0 01 3 5 42 7 10 63 9 11 114 12 11 125 13 11 12k Sk xk vk vk+fk+1 fkknP3012345012345 0 4 6111212 0+0 4+0 6+011+012+012+0 0 4 6111212012345k

4、Sk xk vk vk+fk+1 fkknP0123452 0 0 0+0 0 0-0 0 0 0+4 1 5 5+0 5 1-0 0 0 0+6 1 5 5+4 2 10 10+010 2-0 0 0 0+11 1 5 5+6 2 10 10+4 3 11 11+014 2-1 0 0 0+12 1 5 5+11 2 10 10+6 3 11 11+4 4 11 11+016 1-3 2-2 0 0 0+12 1 5 5+12 2 10 10+11 3 11 11+6 4 11 11+4 5 11 11+021 2-3k Sk xk vk vk+fk+1 fkknP15012345 0 3

5、7 912130+21 3+167+149+1012+513+021 0-2-3 2-2-1最优策略：P*13 为0-2-3或2-2-1， 即分给甲厂0台、分给乙厂2台、分给丙厂3台， 或分给甲厂2台、分给乙厂2台、分给丙厂1台。最优值： f1=21。可见，最优解可以是不唯一的，但最优值是唯一的。资源分配问题的应用很广泛，例如： 1.某学生正在备考4门功课，还剩7天时间，每门功课至少复习1天。若他已估计出各门功课的复习天数与能提高的分数之间的关系，问他应怎样安排复习时间可使总的分数提高最多？ 2.背包问题：旅行者携带的背包中能装的物品重量为a，现他要从n种物品中挑选若干数量装入背包，问他应如何

6、挑选可使所带的物品总价值最大？一九九九年硕士研究生入学试题一九九九年硕士研究生入学试题某大学生正在计划如何安排在7天时间里复习完4门考试课程。他要求每天只能安排一门课程复习，每门课程至少需要复习1天，据他估计各门课程的复习时间与所能带来的成绩提高关系如下表。用动态规划法求出使其总成绩提高最多的复习天数安排计划资源分配问题）解：阶段k：将7天分配给甲乙丙丁四门课程，划分四个阶段，k=1，2，3，4状态sk： 分配给第k门课程的天数，k=1,2,3,4 1XkSk状态转移: S k+1=Sk-Xk第k阶段初还剩的天数。状态集：S1=7,S2=3,4,5,6,S3=2,3,4,5,S4=1,2,3,

7、4决策Xk：阶段指标Vk: 第k阶段分配后提高的分数指标函数： Vk4=Vi递推方程：k=4,3,2,1f 5(S5)=0fk(Sk)=max vk(Sk,Xk)+f k+1(S k+1)1 xk SkK=4, S4=1,2,3,4, 1X4S4, S5=S4-X4 ,f5(S5)=0K=3, S3=2,3,4,5, 1X3S3, S4=S3-X3K=2, S2=3,4,5,6, 1X2S2, S3=S2-X2S2X2V2(S2)S3f3(S3)V2(x2)+f3(S3)f2(S2)X2*313273+7=1010113393+9=1225275+7=12134123+12=1525395+9

8、=1436276+7=13135133+13=16254125+12=1736396+9=1547277+7=1461724121(2)5151K=1, S1=7, 1X1S1, S2=S1-X1S1X1V1(S1)S2f2(S2)V1(x1)+f2(S2)f1(S1)X1*146174+17=21245154+15=19354125+12=17483108+10=187211最优解为:S1=7X1*=1第1门复习1天S2=S1-X1*=7-1=6X2*=2第2门复习2天S3=S2-X2*=6-2=4X3*=1第3门复习1天S4=S3-X3*=4-1=3X4*=3第4门复习3天最优值为:f1(

9、S1)=21总成绩最多提高21分背包问题1.一般提法： 旅行者携带的背包中能装的物品重量为a，现他要从n种物品中挑选若干数量装入背包，已知第i种物品的单件重量为ai，其价格是cixi），问他应如何挑选可使所带的物品的总价值最大？2.模型：决策变量xi表示第i种物品装入的件数i=1n）模型为：Maxz=Vixi）wixi）wxi 0 且为整数i=1n）具有变量分离的静态模型3.用动态规划法求解：阶段k：将可装入物品按1,2,.,n排序,每段装一种物品,共划分为n个阶段。即k=1，2，. ，n状态sk：背包中装入第kn种物品的总重量（第k阶段还能装入物品的量）S1=a决策xk：装入第k种物品的件数

10、状态转移：S k+1=sk-wkxk0 xk（sk/wk）基本方程：k=n，n-1，.，3，2，1f n+1s n+1）=0 xkfksk）=max Vkxk）+f k+1s k+1）由背包问题模型可求解静态问题模型：如求解线性规划问题Maxz=5x1+2x2+x3x1+2x2+x3 12x1，x2，x3 0由动态规划法：阶段：k=1，2，3 表示给xk赋值的过程状态sk：第k个阶段初可赋给xk到x3的值（约束右端项的剩余值）决策xk： Xk的取值0 x1s1状态转移： S 1=120 x2s2/20 x3s3 S 2=s1-x1 S 3=s2-2x2阶段指数：V1=5x1基本方程：f 4s

11、4）=0k=3，2，1xkfksk）=max vk+f k+1sk+1）V2=2x2 V3=x3Xk为连续型；用求极值方法求最大值二、复合系统工作可靠性问题1. 问题的一般提法 设某工作系统由n个部件串接而成，为提高系统的可靠性，在每个部件上装有备用件。已知部件i上装有xi个备用件时，其正常工作的概率为pi(xi)；每个部件i的备用件重量为wi，系统要求总重量不超过W。问应如何安排备用件可使系统可靠性最高？串接:122. 数学规划模型个备用件个部件安排设给第决策变量：ixi )( 1iinixpMaxz目标函数：为非负整数约束条件：iniiixWxw1 模型的特点变量分离。3.用动态规划方法求

12、解12S1=Wx1x2p1(x1)p2(x2) nxnsnpn(xn)s2s3.阶段k状态sk决策xk=1,n表示安排第k个部件备用件的过程；表示在给第k个部件安排之前还剩有的容许重量；表示第k个部件上安排的备用件数量；状态转移sk+1= sk- wkxk ；阶段指标vk指标函数vkn ；的可靠性；部件安排备用件后产生表示第)(niikixpk,1,1n1nkffvMaxfkkxkk1基本方程由可靠性问题模型可求解静态模型如：求解非线性规划问题：Maxz=xixi=cxi 0由动态规划方法：阶段k=1，.，n：给xk赋值的过程状态sk：第k到n阶段赋值和决策xk：Xk的取值阶段指标： Vk=xk转移： S k+1=sk-