多目标、动态优化

.,系统分析方法,秦华鹏北京大学深圳研究生院环境与城市学院Office:E414Tel:26035291(O)Mobilemail:qinhuapeng2006年3月,.,第6讲多目标、动态优化,一多目标优化二目标规划三动态优化,.,一多目标优化,多目标优化模型多目标优化解的性质多目标优化技术简介,.,1.1多目标优化模型,决策变量X（x1，x2，xn）目标函数ZF(x1，x2，xn)约束条件g1(x1，x2，xn)gm(x1，x2，xn),系统优化模型一般形式,.,单目标优化与多目标优化,单目标优化：max(min)Z=f(x1，x2，xn)系统期望达到的目标可用一个函数来表达,多目标优化：max(min)Z1=f1(x1，x2，xn)max(min)Z2=f2(x1，x2，xn)max(min)Zm=fm(x1，x2，xn)系统期望达到的m个目标应该分别用m个函数来表达,.,线性多目标优化,如果多目标优化问题的所有目标和约束条件都可用线性方程来表达，则为线性多目标问题，其目标函数可表达为：,.,1.2多目标优化问题解的性质,单目标问题中，各种方案的目标函数值具有可比性，可以分出优劣，因此一般存在最优解多目标问题中，对某个目标的“优化”可能导致其它目标的“劣化”，因此，一般不存在能够同时满足各个目标最优化的最优解多目标优化问题的求解，除了要“优化”单个目标本身，还要平衡各个目标间的关系，因此，多目标优化问题的解是经过各目标权衡后相对满意的方案,.,1.3多目标规划求解技术简介,一般思路为：采取某种方式，平衡各个目标间的关系，将多目标规划问题转化为单目标规划问题去处理。平衡的技术有：效用最优化模型罚款模型目标规划模型约束模型,.,（1）效用最优化模型,按一定方式，将一系列的目标函数与效用函数建立相关关系，对各效用函数加权求和，以该和函数作为的单目标规划问题的目标函数,目标函数fi(X),效用函数i(X),式中，是与各目标函数相关的效用函数的和函数；权值i来反映原问题中各目标函数在总体目标中的权重，满足：,.,效用函数效益型,.,效用函数成本型,.,效用函数区间型,.,（2）罚款模型,如果对每一个目标函数，决策者都能提出一个期望值（或称满意值）f*i，那么，可通过比较实际值与期望值f*i之间的偏差来构造单目标问题。,在上式中，i是与第i个目标函数相关的权重,.,（3）目标规划模型,目标规划模型与罚款模型类似，它也需要预先确定各个目标的期望值f*i,.,（4）约束模型,如果规划问题的某一目标可以给出一个可供选择的范围，则该目标就可以作为约束条件而被排除出目标组，进入约束条件组中假如，除了第一个目标外，其余目标都可以提出一个可供选的范围，则：,max(minZ)=f1(x1,x2,xn),.,二目标规划,目标规划由线性规划发展演变而来处理多目标问题的简单实用的方法目标规划与线性规划问题的对比目标规划问题的数学模型目标规划求解方法案例分析,.,2.1目标规划与线性规划问题的对比,线性规划单目标问题目标值待求追求目标的最优值（最大或最小）目标规划单或多目标问题目标值（理想值、期望值）已知追求尽可能接近理想值的解满意解,.,例1,某厂生产甲、乙两种产品，已知单件生产所需工时、可用工时数、及单件收益,.,（1）从线性规划角度考虑,LP：maxZ=100X1+80X2,X*=(50,100)Z*=13000,目标：在现有资源条件下，追求最大收益,.,（2）从目标规划角度考虑理想值,理想值（期望值）：去年总收益9000，期望增长11.1%，即希望今年总收益达到10000理想值已经确定允许计算值（决策值）小于或大于理想值希望计算值与理想值之间的（负）差别尽可能小,.,（2）从目标规划角度考虑正、负偏差,计算值与理想值之间三种可能：计算值理想值，超过，d-=0计算值=理想值，相等，d+=d-=0,因此：d+*d-=0d+，d-0,引入正、负偏差变量d+、d-d+：计算值超过理想值部分(正偏差变量)d-：计算值不足理想值部分(负偏差变量),100X1+80X2-d+d-=10000,.,（2）从目标规划角度考虑绝对约束与目标约束,绝对约束：必须严格满足的条件，不能满足绝对约束的解即为非可行解,目标约束：目标规划所特有的一种约束，以目标的理想值作为约束方程右端常数项，不必严格满足，允许发生正负偏差。,100X1+80X2-d+d-=10000,.,（2）从目标规划角度考虑目标函数,因为希望：,100X1+80X2-d+d-=10000,100X1+80X210000,也就是希望：,d-0,目标函数为：,minZ=d-,.,（2）例1的目标规划模型,GP：MinZ=d-100X1+80X2-d+d-=100004X1+2X24002X1+4X2500X1,X2,d-,d+0d+*d-=0,LP：MaxZ=100X1+80X22X1+4X25004X1+2X2400X1,X20,.,2.2目标规划问题的数学模型,案例介绍绝对约束与目标约束目标函数目标优先级目标权因子小节,.,例2,某工厂生产I、II两种产品，生产单位产品所需要的原材料及占用设备台时、每天拥有的设备台时、原材料最大供应量、单件产品可获利润。,.,工厂在安排生产计划的考虑,原材料情况：计划使用原材料不能超过拥有量；市场情况：产品销售量有下降趋势，期望产品的产量不超过产品的产量。期望充分利用设备，但不希望加班。期望达到利润计划指标56千元。,2X1+X211,X1-X20,X1+2X2=10,8X1+10X256,.,（1）绝对约束与目标约束,d1-:X1产量不足X2部分d1+:X1产量超过X2部分d2-:设备使用不足10部分d2+:设备使用超过10部分d3-:利润不足56部分d3+:利润超过56部分,设X1，X2为产品，产品产量。,.,（2）目标函数,市场情况：产品销售量有下降趋势，期望产品的产量不超过产品的产量。期望充分利用设备，但尽可能不加班。期望达到利润计划指标56千元。,X1-X20,X1+2X2=10,8X1+10X256,X1-X2+d1-d1+=0,X1+2X2+d2-d2+=10,8X1+10X2+d3-d3+=56,minZ1=d1+,minZ2=d2-+d2+,minZ3=d3-,.,（3）优先级,在目标规划中，多个目标之间往往有主次、缓急之区别凡要求首先达到的目标，赋予优先级p1凡要求第二位达到的目标，赋予优先级p2优化规则只有完成了高级别的优化后，再考虑低级别的优化再进行低级别的优化时，不能破坏高级别以达到的优化值,.,（4）权因子,在同一优先级中有几个不同的偏差变量要求极小，而这几个偏差变量之间重要性又有区别可用“权因子”来区分同一优先级中不同偏差变量重要性不同，如p2（2d2-+d2+）表示d2-的重要程度为d2+的两倍，表明“充分利用设备”的愿望“不希望加班”的愿望权因子的数值一般需要分析者与决策者商讨确定,.,例2的多目标规划模型,minZ=P1d1+P2(2d2-+d2+)+P3(d3-),2X1+X211X1-X2+d1-d1+=0X1+2X2+d2-d2+=108X1+10X2+d3-d3+=56X1,X2,di-,di+0,.,小结,1）约束条件硬约束(绝对约束)软约束(目标约束)，引入d-,d+2）目标优先级与权因子P1P2PL同一级中可以有若干个目标：P21,P22,P23其重要程度用权重系数W21,W22,W23表示,目标规划的基本思想是，给定若干目标以及实现这些目标的优先顺序，在有限的资源条件下，使总的偏离目标值的偏差最小,.,小结,3）目标函数（准则函数）对目标约束：fi(X)+di-di+=gi,.,小结,目标函数的实质：求一组决策变量的满意值，使决策结果与给定目标总偏差最小。目标函数的特点：目标函数中只有偏差变量目标函数总是求偏差变量最小目标函数值的含义：Z=0：各级目标均已达到Z0：部分目标未达到,.,一般模型,.,2.3目标规划的求解方法,序贯式算法一种分解的算法，根据优先级的先后次序，将原多目标问题分解为一系列传统的单目标线性规划问题，然后依次求解。,.,（1）序贯式算法的思路,令i=1，建立仅含p1级目标的线性规划单目标模型：minZ1(D-，D+)；,利用单纯形法求解pi级单目标规划，得到minZi(D-，D+)=Z*i,令i=i+1，建立仅含pi级目标的线性规划单目标模型：minZi=Zi(D-，D+)；同时考虑所有比pi高级别目标相应的约束条件；还要增加约束条件：Zs(D-，D+)=Z*ss=1,2,i-1,转第2步，直到考虑完所有级别目标,.,第1步：构造P1级目标构成的单目标线性,minZ=P1d1+P2(2d2-+d2+)+P3(d3-)2X1+X211X1-X2+d1-d1+=0X1+2X2+d2-d2+=108X1+10X2+d3-d3+=56X1,X2,di-,di+0,minZ1=d1+2X1+X211X1-X2+d1-d1+=0,在P1级只包含d1+，因此只取含有d1+的约束条件；,绝对约束,.,第2步求解P1级单目标规划,minZ1=d1+2X1+X211X1-X2+d1-d1+=0,计算结果：MinZ1(D-，D+)=d1+=0,.,第3步：构造P2级目标构成的单目标线性,上一级目标所应满足的约束条件,本级目标所应满足的约束条件,为保证优化时P2，不破坏P1的最优值而增加的约束条件,minZ=P1d1+P2(2d2-+d2+)+P3(d3-)2X1+X211X1-X2+d1-d1+=0X1+2X2+d2-d2+=108X1+10X2+d3-d3+=56X1,X2,di-,di+0,minZ2=2d2-+d2+2X1+X211X1-X2+d1-d1+=0X1+2X2+d2-d2+=10d1+=0,minZ2=2d2-+d2+2X1+X211X1-X2+d1-d1+=0X1+2X2+d2-d2+=10d1+=0,.,第4步：求解P2级单目标规划,minZ2=2d2-+d2+2X1+X211X1-X2+d1-d1+=0X1+2X2+d2-d2+=10d1+=0,计算结果：MinZ2(D-，D+)=2d2-+d2+=0,.,第5步：构造P3级目标构成的单目标线性,minZ3=d3-2X1+X211X1-X2+d1-d1+=0X1+2X2+d2-d2+=108X1+10X2+d3-d3+=56d1+=02d2-+d2+=0,较低级目标所应满足的约束条件,本级目标所应满足的约束条件,为保证优化时P2，不破坏P1的最优值而增加的约束条件,minZ=P1d1+P2(2d2-+d2+)+P3(d3-)2X1+X211X1-X2+d1-d1+=0X1+2X2+d2-d2+=108X1+10X2+d3-d3+=56X1,X2,di-,di+0,.,第6步：求解P3级单目标规划,minZ3=d3-2X1+X211X1-X2+d1-d1+=0X1+2X2+d2-d2+=108X1+10X2+d3-d3+=56d1+=02d2-+d2+=0,计算结果：MinZ3(D-，D+)=0,.,例2结论,VariableValued3-0.0 x12.0 x24.0d1-0.0d1+0.0d2-0.0d2+0.0d3+0.0,MinZ1(D-，D+)=d1+=0，第1优先级：期望产品的产量不超过产品的产量，得到满足！,MinZ2(D-，D+)=2d2-+d2+=0，第2优先级：期望充分利用设备，但尽可能不加班，得到满足！,MinZ3(D-，D+)=d3-=0，第3优先级：期望达到利润计划指标56千元,得到满足,minZ=P1d1+P2(2d2-+d2+)+P3(d3-)=0,.,三动态规划,动态规划引论动态规划的基本原理动态规划的基本方程举例,.,3.1动态规划引论,从案例说起多阶段决策问题与动态规划,.,最短路径问题,从A地到D地要铺设一条煤气管道,其中需经过两级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,.,机器负荷问题,某种机器可以在高低两种不同的负荷下进行生产：在高负荷下生产时，机器的年完好率为70%，且，产品的年产量=8*投入生产的机器数量在低负荷下生产时，机器的年完好率为90%，且，产品的年产量=5*投入生产的机器数量假定开始生产时完好的机器数量为1000要求制定一个五年计划,在每年开始时决定机器在两种不同负荷下生产的数量，使五年内产品的总产量最高。,.,多阶段决策问题与动态规划,以上两个问题都可以划分为多个决策阶段。多阶段决策问题：系统运行过程中可划分为若干相继的“阶段”，每个阶段都要进行决策，并使整个过程达到最优的一类问题。阶段：阶段按时间、空间或其它特征划分，且各阶段相互联系，某阶段的结束是下一阶段起始问题的特征：某阶段的最优策略，而对下一阶段未必最有利。为使整个过程效果最优，必须将每阶段作为整个决策链的一环，从整体考虑。动态规划：用来多阶段决策过程优化的一种数量方法。,.,3.2动态规划的基本原理,上世纪50年代，美国数学家贝尔曼提出解决多阶段决策问题的“最优性原理”假设采取了最优策略，得到某个系统运动的最优轨线，该最优轨线将s（起点）和t（终点）连接。若在最优轨线上取一点k，则子轨线k-s也是最优的。最优策略的一部分也是最优的,.,最优性原理的应用,从A地到D地要铺设一条煤气管道,其中需经过两级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,.,解：整个计算过程分三个阶段，从最后一个阶段开始。,第一阶段（CD）：C有三条路线到终点D,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,D,C1,C2,C3,显然有f1(C1)=1；f1(C2)=3；f1(C3)=4,第k阶段从Sk到终点最短距离,.,第二阶段（B1C）：B1到C有三条路线。,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,D,C1,C2,C3,B1,B2,.,第二阶段（B2C）：B2到C有三条路线。,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,D,C1,C2,C3,B1,B2,.,第三阶段（AB）：A到B有二条路线。,f3(A)1=d(A,B1)f2(B1)246f3(A)2=d(A,B2)f2(B2)437,f3(A)=min=min6,7=6,d(A,B1)f2(B1)d(A,B2)f2(B2),A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,D,C1,C2,C3,B1,B2,.,3.3动态规划的基本方程,基本概念动态规划基本方程动态规划的步骤,.,3.2.1基本概念,阶段状态与状态变量决策策略状态转移方程指标函数和最优值函数,.,（1）阶段,阶段（stage）把所研究的决策问题，按先后顺序划分为若干相互联系的决策步骤，以便按一定的次序进行求解。描述阶段的变量称阶段变量，常用k表示。,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,D,C1,C2,C3,.,（2）状态与状态变量,状态（state）用sk表示阶段k的起始状态（或输入状态）；用sk+1表示阶段k的结束状态（或输出状态）状态变量的取值有一定的允许集合或范围，此集合称为状态允许集合例如：最短路径问题中，第2阶段有二个输入状态，三个输出状态。,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,D,C1,C2,C3,.,（3）决策与决策变量,决策（decision）用xk表示从第k阶段状态sk到第k+1阶段的状态sk+1所采取的策略，它使活动过程从状态sk转变为sk+1。决策变量的取值往往在某一范围之内，此范围称为允许决策集合，可用DK(sK)表示。,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,C1,C2,C3,决策：x2(B1)=B1C1,允许决策集合：D2(B1)=B1C1，B1C2，B1C3,.,（4）策略,策略：是一个按顺序排列的决策组成的集合。在实际问题中，可供选择的策略有一定的范围，称为允许策略集合。从允许策略集合中找出达到最优效果的策略称为最优策略。,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,C1,C2,C3,策略：AB1C1D,.,（5）状态转移方程,状态转移方程：是确定过程由一个状态到另一个状态的方程，描述了状态转移规律。,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,C1,C2,C3,u2(B1)=B1C1s3=T2(B1,u2)=C1,.,讨论：状态的无后效性,一般而言，系统某阶段的状态转移不但与系统当前状态和决策有关，而且还与系统的历史状态和决策有关特殊的，系统状态的转移都只仅与前一时刻的状态有关、而与过去的状态无关，称这样的状态具有“无后效性”动态规划解决“具有无后效性”的多阶段决策问题,.,（6）指标函数和最优值函数,指标函数又称目标函数，它用来表示系统所要实现的目标，是衡量策略优劣的尺度。指标函数的含义可能是距离、利润、成本、产量或资源消耗等衡量从k阶段n阶段决策过程总体效果的确定数量函数：Vk,n衡量第k阶段决策效果的指标：dk(sk,xk)指标函数Vk,n最优值最优值函数：fk(sk),.,最短路径问题中的指标函数,Vk,n第k阶段从Sk到终点的距离dk(sk,xk)从Sk到xk决策所指节点的距离fk(sk)第k阶段从Sk到终点最短距离,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,C1,C2,C3,.,递推方程式,这样，就将原来的n阶段决策问题化为一系列单变量优化问题,fk(sk)optdk(sk,xk)+fk+1(sk+1)optdk(sk,xk)+fk+1(T(sk,xk)0xkDk,.,3.2.2动态规划基本方程,递推方程式与状态转移方程式合称为动态规划基本方程,递推方程式：fk(sk)optdk(sk,xk)+fk+1(sk+1)0xkDk状态转移方程式：sk+1=T(sk,xk),.,3.2.3动态规划的步骤,(1)将所研究问题的过程划分为n个恰当的阶段(2)正确地选择状态变量Sk，并确定初始状态S1的值(3)确定决策变量xk以及各阶段的允许决策集Dk(Sk)(4)给出状态转移方程；(5)给出满足要求的指标函数Vk,n及相应的最优值函(6)写出递推方程，建立基本方程；(7)按照基本方程递推求解,.,3.4举例：机器负荷问题,某种机器可以在高低两种不同的负荷下进行生产：在高负荷下进行生产时，机器的年完好率为70%，且，产品的年产量=8*投入生产的机器数量这时在低负荷下生产时，机器的年完好率为90%，且，产品的年产量=5*投入生产的机器数量假定开始生产时完好的机器数量为1000要求制定一个五年计划,在每年开始时决定机器在两种不同负荷下生产的数量，使五年内产品的总产量最高。,.,机器负荷问题,x1,x2,x5,.,(1)按年数划分为5个阶段，k=1,2,3,4,5,(2)取第k年初完好的机器数sk为状态变量,s1=1000,(3)取第k年投入高负荷的机器数xk为决策变量,0xksk,(4)状态转移方程为sk+1=0.7xk+0.9(sk-xk)=0.9sk-0.2xk,(5)指标函数为Vk,5=8xj+5(sj-xj)=(5sj+3xj),解:,.,基本方程,(6)基本方程为fk(sk)max5sk+3xk+fk+1(sk+1)k=5,4,3,2,10xkskf6(s6)0根据状态转移方程：Sk+1=0.9Sk-0.2Xkfk(sk)max5sk+3xk+fk+1(0.9Sk-0.2Xk)因此基本方程fk最终可转化为Sk和Xk的表达式。,.,当k=5时,基本方程为fk(sk)max5sj+3xj+fk+1(sk+1)0xkskf6(s6)0,当k=5时，0x5s5,f5(s5)max5s5+3x5+f6(s6)max5s5+3x58s5此时x5*=s5,.,当k=4时,基本方程为fk(sk)max5sj+3xj+fk+1(sk+1)k=5,4,3,2,