6 多目标、动态优化

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,系统分析方法,Office: E414 Tel: 26035291(O),Mobile:,Email:,2006年3月,1,第6讲 多目标、动态优化,一 多目标优化,二 目标规划,三 动态优化,2,一 多目标优化,多目标优化模型,多目标优化解的性质,多目标优化技术简介,3,1.1 多目标优化模型,决策变量,X,（,x,1,，,x,2,，,x,n,）,目标函数,Z,F,(,x,1,，,x,2,，,x,n,),约束条件,g,1,(,x,1,，,x,2,，,x,n,),g,m,(,x,1,，,x,2,，,x,n,),系统优化模型一般形式,4,单目标优化与多目标优化,单,目标优化：,max(min),Z,=,f,(,x,1,，,x,2,，,x,n,),系统期望达到的目标可用一个函数来表达,多目标优化：,max(min),Z,1,=,f,1,(,x,1,，,x,2,，,x,n,),max(min),Z,2,=,f,2,(,x,1,，,x,2,，,x,n,),max(min),Z,m,=,f,m,(,x,1,，,x,2,，,x,n,),系统期望达到的,m,个目标应该分别用,m,个函数来表达,5,线性多目标优化,如果多目标优化问题的所有目标和约束条件都可用线性方程来表达，则为线性多目标问题，其目标函数可表达为：,6,1.2 多目标优化问题解的性质,单目标问题中，各种方案的目标函数值具有可比性，可以分出优劣，因此一般存在最优解,多目标问题中，对某个目标的,“优化”,可能导致其它目标的,“劣化”,，因此，一般不存在能够同时满足各个目标最优化的最优解,多目标优化问题的求解，除了要,“优化”,单个目标本身，还要,平衡,各个目标间的关系，因此，多目标优化问题的解是,经过各目标权衡后相对满意的方案,7,1.3 多目标规划求解技术简介,一般思路为：采取某种方式，,平衡,各个目标间的关系，将多目标规划问题转化为,单目标规划,问题去处理。,平衡,的技术有：,效用最优化模型,罚款模型,目标规划模型,约束模型,8,（1）效用最优化模型,按一定方式，将一系列的目标函数与效用函数建立相关关系，对各效用函数加权求和，以该和函数作为的单目标规划问题的目标函数,目标函数,f,i,(X),效用函数,i,(X),式中，是与各目标函数相关的效用函数的和函数；,权值,i,来反映原问题中各目标函数在总体目标中的权重，满足：,9,效用函数效益型,10,效用函数成本型,11,效用函数区间型,12,（2）罚款模型,如果对每一个目标函数，决策者都能提出一个,期望值,（或称满意值,）,f,*,i,，那么，可通过比较实际值与期望值,f,*,i,之间的偏差来构造单目标问题。,在上式中，,i,是与第i个目标函数相关的权重,13,（3）目标规划模型,目标规划模型与罚款模型类似，它也需要预先确定各个目标的期望值,f,*,i,14,（4）约束模型,如果规划问题的某一目标可以给出一个可供选择的范围，则该目标就可以作为约束条件而被排除出目标组，进入约束条件组中,假如，除了第一个目标外，其余目标都可以提出一个可供选的范围，则：,max(minZ)=,f,1,(x,1,x,2,x,n,),15,二 目标规划,目标规划由线性规划发展演变而来,处理多目标问题的简单实用的方法,目标规划与线性规划问题的对比,目标规划问题的数学模型,目标规划求解方法,案例分析,16,2.1 目标规划与线性规划问题的对比,线性规划,单,目标问题,目标值,待求,追求目标的,最优值,（最大或最小）,目标规划,单,或,多,目标问题,目标值（理想值、期望值）,已知,追求,尽可能接近,理想值的解满意解,17,例1,某厂生产甲、乙两种产品，已知单件生产所需工时、可用工时数、及单件收益,甲产品 乙产品 可用工时,金工工时 4 2 400,装配工时 2 4 500,收益/件 100 80,18,（1）从,线性规划,角度考虑,LP：,maxZ=100X,1,+,80X,2,2X,1,+4X,2,500,4X,1,+2X,2,400,X,1,X,2, 0,X* =(50,100) Z* =13000,目标：在现有资源条件下，追求最大收益,19,（2）从,目标规划,角度考虑,理想值,理想值（期望值）：去年总收益,9000,，期望增长,11.1%，,即希望今年总收益达到,10000,理想值已经确定,允许计算值（决策值）小于或大于理想值,希望计算值与理想值之间的（负）差别尽可能小,20,（2）从,目标规划,角度考虑,正、负偏差,计算值与理想值之间三种可能：,计算值理想值，超过，,d,-,=,0,计算值=理想值，相等，,d,+,=,d,-,=,0,因此：d,+,* d,-,=,0,d,+,，,d,-, 0,引入正、负偏差变量,d,+,、d,-,d,+,：,计算值,超过,理想值部分(正偏差变量),d,-,：,计算值,不足,理想值部分(负偏差变量),100X,1,+80X,2,-,d,+,+,d,-,=10000,21,（2）从,目标规划,角度考虑绝对约束与目标约束,绝对约束：,必须严格满足的条件，不能满足绝对约束的解即为非可行解,目标约束：,目标规划所特有的一种约束，以目标的,理想值作为约束方程右端常数项,，不必严格满足，允许发生正负偏差。,4X,1,+2X,2,400,2X,1,+4X,2,500,100X,1,+80X,2,-,d,+,+,d,-,=10000,22,（2）从,目标规划,角度考虑目标函数,因为希望：,100X,1,+80X,2,-,d,+,+,d,-,=10000,100X,1,+80X,2,10000,也就是希望：,d,-,0,目标函数为：,minZ=,d,-,23,（2）例1的目标规划模型,GP：,Min Z=,d,-,100X,1,+80X,2,-,d,+,+,d,-,=10000,4X,1,+2X,2,400,2X,1,+4X,2,500,X,1,X,2,d,-,d,+, 0,d,+,* d,-,=0,LP：,Max Z=100X,1,+,80X,2,2X,1,+4X,2,500,4X,1,+2X,2,400,X,1,X,2, 0,24,2.2 目标规划问题的数学模型,案例介绍,绝对约束与目标约束,目标函数,目标优先级,目标权因子,小节,25,例2,某工厂生产I、II两种产品，生产单位产品所需要的原材料及占用设备台时、每天拥有的设备台时、原材料最大供应量、单件产品可获利润。,I II,资源拥有量,原材料(公斤) 2 1 11,设备(小时) 1 2 10,利润(千元/件) 8 10,26,工厂在安排生产计划的考虑,原材料情况：计划使用原材料不能超过拥有量；,市场情况：产品,销售量有下降趋势，期望产品的产量不超过产品的产量。,期望充分利用设备，但不希望加班。,期望达到利润计划指标56千元。,2X,1,+X,2,11,X,1,-X,2,0,X,1,+2X,2,=,10,8X,1,+10X,2,56,27,（1）绝对约束与目标约束,2X,1,+X,2,11,X,1,-X,2,+d,1,-,-d,1,+,=0,X,1,+2X,2,+d,2,-,-d,2,+,=10,8X,1,+10X,2,+d,3,-,-d,3,+,=56,X,1,X,2,d,i,-,d,i,+, 0,d,i,-,.,d,i,+,=0,d,1,-,:,X,1,产量不足,X,2,部分,d,1,+,:,X,1,产量超过,X,2,部分,d,2,-,: 设备使用不足,10,部分,d,2,+,:设备使用超过,10,部分,d,3,-,: 利润不足,56,部分,d,3,+,:利润超过,56,部分,设,X,1,，,X,2,为产品,，产品产量。,28,（2）目标函数,市场情况：产品,销售量有下降趋势，期望产品的产量不超过产品的产量。,期望充分利用设备，但尽可能不加班。,期望达到利润计划指标56千元。,X,1,-X,2,0,X,1,+2X,2,=,10,8X,1,+10X,2,56,X,1,-X,2,+d,1,-,-d,1,+,=0,X,1,+2X,2,+d,2,-,-d,2,+,=10,8X,1,+10X,2,+d,3,-,-d,3,+,=56,min,Z,1,= d,1,+,min,Z,2,= d,2,-,+d,2,+,min,Z,3,= d,3,-,29,（3）优先级,在目标规划中，多个目标之间往往有主次、缓急之区别,凡要求首先达到的目标，赋予优先级,p,1,凡要求第二位达到的目标，赋予优先级,p,2,优化规则,只有完成了高级别的优化后，再考虑低级别的优化,再进行低级别的优化时，不能破坏高级别以达到的优化值,30,（4）权因子,在同一优先级中有几个不同的偏差变量要求极小，而这几个偏差变量之间重要性又有区别可用“权因子”来区分同一优先级中不同偏差变量重要性不同，如,p,2,（2,d,2,-,+ d,2,+,）,表示,d,2,-,的重要程度为,d,2,+,的两倍，,表明,“,充分利用设备”的愿望,“,不希望加班”的愿望,权因子的数值一般需要分析者与决策者商讨确定,31,例2的多目标规划模型,min,Z=P,1,d,1,+,+P,2,(2,d,2,-,+d,2,+,),+P,3,(,d,3,-,),2X,1,+X,2,11,X,1,-X,2,+d,1,-,-d,1,+,=0,X,1,+2X,2,+d,2,-,-d,2,+,=10,8X,1,+10X,2,+d,3,-,-d,3,+,=56,X,1,X,2,d,i,-,d,i,+, 0,32,小结,1）约束条件,硬约束(绝对约束),软约束 (目标约束)，引入,d,-,d,+,2）目标优先级与权因子,P,1,P,2,P,L,同一级中可以有若干个目标：,P,21,P,22,P,23,其重要程度用权重系数,W,21,W,22,W,23,表示,目标规划的基本思想是，给定若干目标以及实现这些目标的优先顺序，在有限的资源条件下，使总的偏离目标值的偏差最小,33,小结,期望,目标函数,f,i,(X),=g,i,恰好达到目标,min,Z= f,(,d,-,+d,+,),f,i,(X),=g,i,超过目标,min,Z= f,(,d,-,),f,i,(X),g,i,不超过目标,min,Z= f,(,d,+,),3）目标函数（准则函数）,对目标约束：,f,i,(X),+d,i,-,-d,i,+,=g,i,34,小结,目标函数的实质：,求一组决策变量的满意值，使决策结果与给定目标总偏差最小。,目标函数的特点：,目标函数中只有偏差变量,目标函数总是求偏差变量最小,目标函数值的含义,：,Z=0,：各级目标均已达到,Z0：,部分目标未达到,35,一般模型,36,2.3 目标规划的求解方法,序贯式算法,一种分解的算法，根据优先级的先后次序，将原多目标问题分解为一系列传统的单目标线性规划问题，然后依次求解。,37,（1）序贯式算法的思路,令,i,=1，,建立仅含,p,1,级目标的线性规划单目标模型：,min,Z,1,(,D,-,，,D,+,),；,利用单纯形法求解,p,i,级单目标规划，得到,min,Z,i,(,D,-,，,D,+,) = Z,*,i,令,i,=,i,+1，,建立仅含,p,i,级目标的线性规划单目标模型：,min,Z,i,=,Z,i,(,D,-,，,D,+,)；,同时考虑所有比,p,i,高级别目标相应的约束条件,；,还要增加约束条件：,Z,s,(,D,-,，,D,+,) = Z,*,s,s,= 1, 2, ,i,-1,转第2,步，直到考虑完所有级别目标,38,第1步：构造,P,1,级目标构成的单目标线性,min,Z= P,1,d,1,+,+P,2,(2,d,2,-,+d,2,+,),+P,3,(,d,3,-,),2X,1,+X,2,11,X,1,-X,2,+d,1,-,-d,1,+,=0,X,1,+2X,2,+d,2,-,-d,2,+,=10,8X,1,+10X,2,+d,3,-,-d,3,+,=56,X,1,X,2,d,i,-,d,i,+, 0,min,Z,1,=d,1,+,2X,1,+X,2,11,X,1,-X,2,+d,1,-,-d,1,+,=0,在,P,1,级只,包含,d,1,+,，,因此只取含有,d,1,+,的约束条件；,绝对约束,39,第2步,求解,P,1,级单目标规划,min,Z,1,=d,1,+,2X,1,+X,2,11,X,1,-X,2,+d,1,-,-d,1,+,=0,计算结果：Min,Z,1,(,D,-,，,D,+,) =,d,1,+,=0,40,第3步：构造,P,2,级目标构成的单目标线性,上一级目标所应满足的约束条件,本级目标所应满足的约束条件,为保证优化时,P,2,，不破坏,P,1,的最优值而增加的约束条件,min,Z= P,1,d,1,+,+P,2,(2,d,2,-,+d,2,+,),+P,3,(,d,3,-,),2X,1,+X,2,11,X,1,-X,2,+d,1,-,-d,1,+,=0,X,1,+2X,2,+d,2,-,-d,2,+,=10,8X,1,+10X,2,+d,3,-,-d,3,+,=56,X,1,X,2,d,i,-,d,i,+, 0,min,Z,2,=,2,d,2,-,+d,2,+,2X,1,+X,2,11,X,1,-X,2,+d,1,-,-d,1,+,=0,X,1,+2X,2,+d,2,-,-d,2,+,=10,d,1,+,=0,min,Z,2,=,2,d,2,-,+d,2,+,2X,1,+X,2,11,X,1,-X,2,+d,1,-,-d,1,+,=0,X,1,+2X,2,+d,2,-,-d,2,+,=10,d,1,+,=0,41,第4步：,求解,P,2,级单目标规划,min,Z,2,=,2,d,2,-,+d,2,+,2X,1,+X,2,11,X,1,-X,2,+d,1,-,-d,1,+,=0,X,1,+2X,2,+d,2,-,-d,2,+,=10,d,1,+,=0,计算结果： Min,Z,2,(,D,-,，,D,+,) =,2,d,2,-,+d,2,+,=0,42,第5步：构造,P,3,级目标构成的单目标线性,min,Z,3,= d,3,-,2X,1,+X,2,11,X,1,-X,2,+d,1,-,-d,1,+,=0,X,1,+2X,2,+d,2,-,-d,2,+,=10,8X,1,+10X,2,+d,3,-,-d,3,+,=56,d,1,+,=0,2,d,2,-,+d,2,+,=0,较低级目标所应满足的约束条件,本级目标所应满足的约束条件,为保证优化时,P,2,，不破坏,P,1,的最优值而增加的约束条件,min,Z= P,1,d,1,+,+P,2,(2,d,2,-,+d,2,+,),+P,3,(,d,3,-,),2X,1,+X,2,11,X,1,-X,2,+d,1,-,-d,1,+,=0,X,1,+2X,2,+d,2,-,-d,2,+,=10,8X,1,+10X,2,+d,3,-,-d,3,+,=56,X,1,X,2,d,i,-,d,i,+, 0,43,第6步：,求解,P,3,级单目标规划,min,Z,3,= d,3,-,2X,1,+X,2,11,X,1,-X,2,+d,1,-,-d,1,+,=0,X,1,+2X,2,+d,2,-,-d,2,+,=10,8X,1,+10X,2,+d,3,-,-d,3,+,=56,d,1,+,=0,2,d,2,-,+d,2,+,=0,计算结果： Min,Z,3,(,D,-,，,D,+,) =,0,44,例2结论,Variable Value,d,3,-,0.0,x,1,2.0,x,2,4.0,d,1,-,0.0,d,1,+,0.0,d,2,-,0.0,d,2,+,0.0,d,3,+,0.0,Min Z,1,(,D,-,，,D,+,) =,d,1,+,=0，,第1优先级：,期望产品的产量不超过产品的产量,，得到满足！,Min Z,2,(,D,-,，,D,+,) =,2,d,2,-,+d,2,+,=0，,第2优先级：期望充分利用设备，但尽可能不加班，得到满足！,Min,Z,3,(,D,-,，,D,+,),= d,3,-,= 0，,第3优先级：期望达到利润计划指标56千元,得到满足,min,Z,= P,1,d,1,+,+P,2,(2,d,2,-,+d,2,+,),+P,3,(,d,3,-,) = 0,45,三 动态规划,动态规划引论,动态规划的基本原理,动态规划的基本方程,举例,46,3.1,动态规划引论,从案例说起,多阶段决策问题与动态规划,47,最短路径问题,从,A,地到,D,地要铺设一条煤气管道,其中需经过两级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？,A,B,1,B,2,C,1,C,2,C,3,D,2,4,3,3,3,3,2,1,1,1,4,48,机器负荷问题,某种机器可以在高低两种不同的负荷下进行生产：,在高负荷下生产时,，机器的年完好率为70%，且，产品的年产量=8*投入生产的机器数量,在低负荷下生产时,，机器的年完好率为90%，且，产品的年产量=5*投入生产的机器数量,假定开始生产时完好的机器数量为1000,要求制定一个五年计划,在,每年开始时决定机器在两种不同负荷下生产的数量,，使五年内产品的总产量最高。,49,多阶段决策问题与动态规划,以上两个问题都可以划分为多个决策阶段。,多阶段决策问题：,系统运行过程中可划分为若干相继的“阶段”，每个阶段都要进行决策，并使整个过程达到最优的一类问题。,阶段：,阶段按时间、空间或其它特征划分，且各阶段相互联系，某阶段的结束是下一阶段起始,问题的特征,：某阶段的最优策略，而对下一阶段未必最有利。为使整个过程效果最优，必须将每阶段作为整个决策链的一环，从整体考虑。,动态规划：,用来多阶段决策过程优化的一种数量方法。,1,2,n,状态,决策,状态,决策,状态,状态,决策,50,3.2,动态规划的基本原理,上世纪50年代，美国数学家贝尔曼提出解决多阶段决策问题的“最优性原理”,假设采取了最优策略，得到某个系统运动的最优轨线，该最优轨线将s（起点）和t（终点）连接。若在最优轨线上取一点k，则子轨线k-s也是最优的。,最优策略的一部分也是最优的,51,最优性原理的应用,从,A,地到,D,地要铺设一条煤气管道,其中需经过两级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？,A,B,1,B,2,C,1,C,2,C,3,D,2,4,3,3,3,3,2,1,1,1,4,52,解：整个计算过程分三个阶段，从最后一个阶段开始。,第一阶段（,C,D,）：,C,有三条路线到终点,D,A,B,1,B,2,C,1,C,2,C,3,D,2,4,3,3,3,3,2,1,1,1,4,D,C,1,C,2,C,3,显然有,f,1,(,C,1,),= 1 ；,f,1,(,C,2,),= 3 ；,f,1,(,C,3,),= 4,第,k,阶段从,S,k,到终点最短距离,53,第二阶段（,B,1,C,）：,B,1,到,C,有三条路线。,d(,B,1,C,1,) +,f,1,(,C,1,),3+1,f,2,(,B,1,) = min d(,B,1,C,2,) +,f,1,(,C,2,),= min 3+3,d(,B,1,C,3,) +,f,1,(,C,3,) 1+4,4,= min 6 = 4,5,A,B,1,B,2,C,1,C,2,C,3,D,2,4,3,3,3,3,2,1,1,1,4,D,C,1,C,2,C,3,B,1,B,2,(最短路线为,B,1,C,1,D,),54,d(,B,2,C,1,) +,f,1,(,C,1,),2+1,f,2,(,B,2,) = min d(,B,2,C,2,) +,f,1,(,C,2,),= min 3+3,d(,B,2,C,3,) +,f,1,(,C,3,) 1+4,3,= min 6 = 3,5,第二阶段（,B,2,C,）：,B,2,到,C,有三条路线。,A,B,1,B,2,C,1,C,2,C,3,D,2,4,3,3,3,3,2,1,1,1,4,D,C,1,C,2,C,3,B,1,B,2,(最短路线为,B,2,C,1,D,),55,第三阶段（,A,B,）：,A,到,B,有二条路线。,f,3,(,A,),1,= d(,A,B,1,),f,2,(,B,1,) 246,f,3,(,A,),2,= d(,A,B,2,),f,2,(,B,2,) 437,f,3,(,A,),= min = min6,7=6,d(,A,B,1,),f,2,(,B,1,),d(,A,B,2,),f,2,(,B,2,),A,B,1,B,2,C,1,C,2,C,3,D,2,4,3,3,3,3,2,1,1,1,4,D,C,1,C,2,C,3,B,1,B,2,(最短路线为,AB,1,C,1,D,),56,3.3动态规划的基本方程,基本概念,动态规划基本方程,动态规划的步骤,57,3.2.1,基本概念,阶段,状态与状态变量,决策,策略,状态转移方程,指标函数和最优值函数,58,（1）,阶段,阶段（stage）把所研究的决策问题，按先后顺序划分为若干相互联系的决策步骤，以便按一定的次序进行求解。,描述阶段的变量称,阶段变量,，常用k表示。,A,B,1,B,2,C,1,C,2,C,3,D,2,4,3,3,3,3,2,1,1,1,4,D,C,1,C,2,C,3,59,（2）,状态与状态变量,状态（,state）,用,s,k,表示阶段,k,的起始状态（或输入状态）；用,s,k+1,表示阶段,k,的结束状态（或输出状态）,状态变量的取值有一定的允许集合或范围，此集合称为,状态允许集合,例如：最短路径问题中，第2阶段有二个输入状态，三个输出状态。,A,B,1,B,2,C,1,C,2,C,3,D,2,4,3,3,3,3,2,1,1,1,4,D,C,1,C,2,C,3,60,（3）,决策与决策变量,决策（,decision）,用,x,k,表示从第k阶段状态s,k,到第k+1阶段的状态,s,k+1,所采取的策略，它使活动过程从状态,s,k,转变为,s,k+1,。,决策变量的取值往往在某一范围之内，此范围称为,允许决策集合,，可用,D,K,(,s,K,),表示,。,A,B,1,B,2,C,1,C,2,C,3,D,2,4,3,3,3,3,2,1,1,1,4,C,1,C,2,C,3,决策：,x,2,(B,1,)=B,1,C,1,允许决策集合：,D,2,(B,1,)=B,1,C,1,，B,1,C,2,，B,1,C,3,61,（4）,策略,策略：,是一个按顺序排列的决策组成的集合。在实际问题中，可供选择的策略有一定的范围，称为,允许策略集合,。从允许策略集合中找出达到最优效果的策略称为,最优策略,。,1,2,k,s,1,x,1,s,2,x,2,s,3,s,k,x,k,s,k,+1,A,B,1,B,2,C,1,C,2,C,3,D,2,4,3,3,3,3,2,1,1,1,4,C,1,C,2,C,3,策略：,AB,1,C,1,D,62,（5）,状态转移方程,状态转移方程：,是确定过程由一个状态到另一个状态的方程，描述了状态转移规律。,1,2,k,s,1,x,1,s,2,x,2,s,3,s,k,x,k,s,k,+1,A,B,1,B,2,C,1,C,2,C,3,D,2,4,3,3,3,3,2,1,1,1,4,C,1,C,2,C,3,u,2,(B,1,)=B,1,C,1,s,3,=T,2,(B,1,u,2,)=C,1,63,讨论：状态的无后效性,一般而言，系统某阶段的状态转移不但与系统当前状态和决策有关，而且还与系统的历史状态和决策有关,特殊的，系统状态的转移都只仅与前一时刻的状态有关、而与过去的状态无关，称这样的状态具有“,无后效性,”,动态规划解决“,具有无后效性,”,的多阶段决策问题,64,（6）,指标函数和最优值函数,指标函数,又称目标函数，它,用来表示系统所要实现的目标，是衡量策略优劣的尺度。,指标函数的含义可能是距离、利润、成本、产量或资源消耗等,衡量从,k,阶段,n,阶段,决策过程总体效果的,确定数量函数：,V,k,n,衡量,第,k,阶段,决策效果的,指标：,d,k,(,s,k,x,k,),指标函数,V,k,n,最优值,最优值函数：,f,k,(,s,k,),65,最短路径问题中的指标函数,V,k,n,第,k,阶段从,S,k,到终点的距离,d,k,(,s,k,x,k,),从,S,k,到,x,k,决策所指节点的距离,f,k,(,s,k,),第,k,阶段从,S,k,到终点最短距离,d(,B,2,C,1,) +,f,1,(,C,1,),3,f,2,(,B,2,) = min d(,B,2,C,2,) +,f,1,(,C,2,),= min 6 =3,d(,B,2,C,3,) +,f,1,(,C,3,) 5,A,B,1,B,2,C,1,C,2,C,3,D,2,4,3,3,3,3,2,1,1,1,4,C,1,C,2,C,3,66,递推方程式,这样，就将原来的n阶段决策问题化为一系列单变量优化问题,f,k,(s,k,) opt ,d,k,(,s,k,x,k,),+f,k+1,(s,k+1,), opt ,d,k,(,s,k,x,k,),+f,k+1,(T(s,k,x,k,),0x,k,D,k,67,3.2.2,动态规划基本方程,递推方程式与状态转移方程式合称为动态规划基本方程,递推方程式：,f,k,(s,k,) opt ,d,k,(,s,k,x,k,),+f,k+1,(s,k+1,),0x,k,D,k,状态转移方程式：,s,k+1,=T(,s,k,x,k,),68,3.2.3 动态规划的步骤,(1)将所研究问题的过程划分为,n,个恰当的阶段,(2),正确地选择状态变量,S,k,，,并确定初始状态,S,1,的值,(3)确定决策变量x,k,以及各阶段的允许决策集,D,k,(S,k,),(4),给出状态转移方程；,(5) 给出满足要求的指标函数,V,k,n,及相应的最优值函,(6) 写出递推方程，建立基本方程；,(7) 按照基本方程递推求解,69,3.4,举例,：机器负荷问题,某种机器可以在高低两种不同的负荷下进行生产：,在高负荷下进行生产时，机器的年完好率为70%，且，产品的年产量=8*投入生产的机器数量,这时在低负荷下生产时，机器的年完好率为90%，且，产品的年产量=5*投入生产的机器数量,假定开始生产时完好的机器数量为1000,要求制定一个五年计划,在每年开始时决定机器在两种不同负荷下生产的数量，使五年内产品的总产量最高。,70,机器负荷问题,x,1,x,2,x,5,1,2,5,s,1,s,2,s,3,s,5,s,6,V,1,V,2,V,5,71,(1)按年数划分为5个阶段，k=1,2,3,4,5,(2)取第k年初完好的机器数s,k,为状态变量, s,1,=1000,(3)取第k年投入高负荷的机器数x,k,为决策变量, 0x,k,s,k,(4)状态转移方程为 s,k+1,=0.7x,k,+0.9(s,k,-x,k,)=0.9s,k,-0.2x,k,(5)指标函数为V,k,5,=8x,j,+5(s,j,-x,j,)=(5s,j,+3x,j,),解:,1,2,5,s,1,s,2,s,3,s,5,s,6,V,1,V,2,V,5,72,基本方程,(6)基本方程为,f,k,(s,k,) max ,5s,k,+3x,k,+f,k+1,(s,k+1,) k=5,4,3,2,1,0x,k,s,k,f,6,(s,6,)0,根据状态转移方程：,S,k+1,=0.9S,k,-0.2X,k,f,k,(s,k,) max ,5s,k,+3x,k,+f,k+1,(,0.9S,k,-0.2X,k,),因此基本方程,f,k,最终可转化为,S,k,和,X,k,的表达式。,73,当k=5时,基本方程为,f,k,(s,k,) max ,5s,j,+3x,j,+f,k+1,(s,k+1,),0x,k,s,k,f,6,(s,6,)0,当k=5时， 0x,5,s,5,f,5,(s,5,) max5s,5,+3x,5,+f,6,(s,6,), max5s,5,+3x,5, 8s,5,此时x,5,*=s,5,S,k+1,=0.9S,k,-0.2X,k,74,当k=4时,基本方程为,f,k,(s,k,) max ,5s,j,+3x,j,+f,k+1,(s,k+1,) k=5,4,3,2,1,0x,k,s,k,f,5,(s,5,),8s,5,当k=4时， 0x,4,s,4,f,4,(s,4,) max5s,4,+3x,4,+f,5,(s,5,), max5s,4,+3x,4,+8s,5, max5s,4,+3x,4,+8(0.9s,4,-0.2x,4,), max12.2s,4,+1.4x,4, 13.6s,4,此时x,4,*=s,4,75,当k=3时,基本方程为,f,k,(s,k,) max ,5s,j,+3x,j,+f,k+1,(s,k+1,) k=5,4,3,2,1,0x,k,s,k,f,4,(s,4,),13.6s,4,当k=3时， 0x,3,s,3,f,3,(s,3,) max5s,3,+3x,3,+f,4,(s,4,), max5s,3,+3x,3,+ 13.6s,4, max5s,3,+3x,3,+13.6(0.9s,3,-0.2x,3,), max17.24s,3,+0.28x,3, 17.5s,3,此时x,3,*=s,3,76,当k=2时,基本方程为,f,k,(s,k,) max ,5s,j,+3x,j,+f,k+1,(s,k+1,) k=5,4,3,2,1,0x,k,s,k,f,3,(s,3,),17.5s,3,当k=2时， 0x,2,s,2,f,2,(s,2,) max5s,2,+3x,2,+f,3,(s,3,), max5s,2,+3x,2,+ 17.5s,3, max5s,2,+3x,2,+ 17.5(0.9s,2,-0.2x,2,), max20.77s,2,-0.504x,2, 20.7s,2,此时x,2,*=0,77,当k=1时,基本方程为,f,k,(s,k,) max ,5s,j,+3x,j,+f,k+1,(s,k+1,) k=5,4,3,2,1,0x,k,s,k,f,2,(s,2,),20.7s,2,当k=1时， 0x,1,s,1,f,5,(s,5,) max5s,5,+3x,5,+f,6,(s,6,), max5s,5,+3x,5, 8s,5,此时x,5,*=s,5,f,1,(s,1,) max5s,1,+3x,+f,2,(s,2,), max5s,1,+3x,1,+ 20.7s,2, max5s,1,+3x,1,+ 20.7,(0.9s,1,-0.2x,1,), max23.7s,1,1.14x,1, 23.7s,1,此时x,1,*=0,78,结果,f,1,(1000)=23700,s,1,=1000, x,1,*=0，,s,2,=900, x,2,*=0,s,3,=810, x,3,*=810,s,5,=397, x,5,*=397,s,4,=576, x,4,*=576,79,小结,动态规划的最优策略具有这样的性质：,一个最优策略的子策略也是最优的,；,动态规划解决“,具有无后效性,”,的多阶段决策问题；,动态规划通过建立递推方程，,将原来的n阶段决策问题化为一系列单变量优化问题,动态规划是考察问题的一种途径，而不是一种算法；,动态规划模型没有统一的模式，建模时必须根据具体问题具体分析,80,