多目标动态优化

第6讲多目标、动态优化一多目标优化二目标规划三动态优化一多目标优化多目标优化模型多目标优化解的性质多目标优化技术简介1.1多目标优化模型决策变量X（x1，x2，…xn）目标函数Z＝F(x1，x2，…xn)约束条件g1(x1，x2，…xn)…gm(x1，x2，…xn)),...,,()(21nXXXFZMinMaxmnmnnbXXXgbXXXgbXXXg或或或,,),...,,(...............,,),...,,(,,),...,,(2122121211系统优化模型一般形式单目标优化与多目标优化单目标优化：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个函数来表达线性多目标优化如果多目标优化问题的所有目标和约束条件都可用线性方程来表达，则为线性多目标问题，其目标函数可表达为：nnmmmmnnnnxcxcxcXfxcxcxcXfxcxcxcXf22112222121212121111)(max(min))(max(min))(max(min)1.2多目标优化问题解的性质单目标问题中，各种方案的目标函数值具有可比性，可以分出优劣，因此一般存在最优解多目标问题中，对某个目标的“优化”可能导致其它目标的“劣化”，因此，一般不存在能够同时满足各个目标最优化的最优解多目标优化问题的求解，除了要“优化”单个目标本身，还要平衡各个目标间的关系，因此，多目标优化问题的解是经过各目标权衡后相对满意的方案1.3多目标规划求解技术简介一般思路为：采取某种方式，平衡各个目标间的关系，将多目标规划问题转化为单目标规划问题去处理。平衡的技术有：效用最优化模型罚款模型目标规划模型约束模型……（1）效用最优化模型按一定方式，将一系列的目标函数与效用函数建立相关关系，对各效用函数加权求和，以该和函数作为的单目标规划问题的目标函数目标函数fi(X)效用函数ψi(X)kiii1max式中，ψ是与各目标函数相关的效用函数的和函数；权值λi来反映原问题中各目标函数在总体目标中的权重，满足：kii11效用函数——效益型minmaxminiiiiffffi指标的最大和最小值分别为iiifffniminmax,,,2,1效用函数——成本型minmaxmaxjjjjffffj指标的最大和最小值分别为jjjfffnjminmax,,,2,1效用函数——区间型2},max{211},max{,1],[1,12maxmin122maxmin11jfffjjfffjfffjjjjjj为指标的最佳稳定区间指标的最大和最小值分别为],[,,,2,121minmaxjjjfffnj（2）罚款模型如果对每一个目标函数，决策者都能提出一个期望值（或称满意值）f*i，那么，可通过比较实际值与期望值f*i之间的偏差来构造单目标问题。在上式中，αi是与第i个目标函数相关的权重（3）目标规划模型目标规划模型与罚款模型类似，它也需要预先确定各个目标的期望值f*i（4）约束模型如果规划问题的某一目标可以给出一个可供选择的范围，则该目标就可以作为约束条件而被排除出目标组，进入约束条件组中假如，除了第一个目标外，其余目标都可以提出一个可供选的范围，则：max(minZ)=f1(x1,x2,…,xn)二目标规划目标规划由线性规划发展演变而来处理多目标问题的简单实用的方法目标规划与线性规划问题的对比目标规划问题的数学模型目标规划求解方法案例分析2.1目标规划与线性规划问题的对比线性规划单目标问题目标值待求追求目标的最优值（最大或最小）目标规划单或多目标问题目标值（理想值、期望值）已知追求尽可能接近理想值的解——满意解例1某厂生产甲、乙两种产品，已知单件生产所需工时、可用工时数、及单件收益甲产品乙产品可用工时金工工时42400装配工时24500收益/件10080（1）从线性规划角度考虑LP：maxZ=100X1+80X22X1+4X25004X1+2X2400X1,X20X*=(50,100)Z*=13000目标：在现有资源条件下，追求最大收益（2）从目标规划角度考虑——理想值理想值（期望值）：去年总收益9000，期望增长11.1%，即希望今年总收益达到10000理想值已经确定允许计算值（决策值）小于或大于理想值希望计算值与理想值之间的（负）差别尽可能小（2）从目标规划角度考虑——正、负偏差计算值与理想值之间三种可能：计算值理想值，不足，d+=0计算值理想值，超过，d-=0计算值=理想值，相等，d+=d-=0因此：d+*d-=0d+，d-0引入正、负偏差变量d+、d-d+：计算值超过理想值部分(正偏差变量)d-：计算值不足理想值部分(负偏差变量)100X1+80X2-d++d-=10000（2）从目标规划角度考虑——绝对约束与目标约束绝对约束：必须严格满足的条件，不能满足绝对约束的解即为非可行解目标约束：目标规划所特有的一种约束，以目标的理想值作为约束方程右端常数项，不必严格满足，允许发生正负偏差。4X1+2X24002X1+4X2500100X1+80X2-d++d-=10000（2）从目标规划角度考虑——目标函数因为希望：100X1+80X2-d++d-=10000100X1+80X210000也就是希望：d-0目标函数为：minZ=d-（2）例1的目标规划模型GP：MinZ=d-100X1+80X2-d++d-=100004X1+2X24002X1+4X2500X1,X2,d-,d+0d+*d-=0LP：MaxZ=100X1+80X22X1+4X25004X1+2X2400X1,X202.2目标规划问题的数学模型案例介绍绝对约束与目标约束目标函数目标优先级目标权因子小节例2某工厂生产I、II两种产品，生产单位产品所需要的原材料及占用设备台时、每天拥有的设备台时、原材料最大供应量、单件产品可获利润。III资源拥有量原材料(公斤)2111设备(小时)1210利润(千元/件)810工厂在安排生产计划的考虑原材料情况：计划使用原材料不能超过拥有量；市场情况：产品Ⅰ销售量有下降趋势，期望产品Ⅰ的产量不超过产品Ⅱ的产量。期望充分利用设备，但不希望加班。期望达到利润计划指标——56千元。2X1+X211X1-X20X1+2X2=108X1+10X256（1）绝对约束与目标约束2X1+X211X1-X2+d1--d1+=0X1+2X2+d2--d2+=108X1+10X2+d3--d3+=56X1,X2,di-,di+0di-.di+=0d1-:X1产量不足X2部分d1+:X1产量超过X2部分d2-:设备使用不足10部分d2+:设备使用超过10部分d3-:利润不足56部分d3+:利润超过56部分设X1，X2为产品Ⅰ，产品Ⅱ产量。（2）目标函数市场情况：产品Ⅰ销售量有下降趋势，期望产品Ⅰ的产量不超过产品Ⅱ的产量。期望充分利用设备，但尽可能不加班。期望达到利润计划指标——56千元。X1-X20X1+2X2=108X1+10X256X1-X2+d1--d1+=0X1+2X2+d2--d2+=108X1+10X2+d3--d3+=56minZ1=d1+minZ2=d2-+d2+minZ3=d3-（3）优先级在目标规划中，多个目标之间往往有主次、缓急之区别凡要求首先达到的目标，赋予优先级p1凡要求第二位达到的目标，赋予优先级p2…优化规则只有完成了高级别的优化后，再考虑低级别的优化再进行低级别的优化时，不能破坏高级别以达到的优化值（4）权因子在同一优先级中有几个不同的偏差变量要求极小，而这几个偏差变量之间重要性又有区别——可用“权因子”来区分同一优先级中不同偏差变量重要性不同，如p2（2d2-+d2+）表示d2-的重要程度为d2+的两倍，表明“充分利用设备”的愿望“不希望加班”的愿望权因子的数值一般需要分析者与决策者商讨确定例2的多目标规划模型minZ=P1d1++P2(2d2-+d2+)+P3(d3-)2X1+X211X1-X2+d1--d1+=0X1+2X2+d2--d2+=108X1+10X2+d3--d3+=56X1,X2,di-,di+0小结1）约束条件硬约束(绝对约束)软约束(目标约束)，引入d-,d+2）目标优先级与权因子P1P2…PL同一级中可以有若干个目标：P21,P22,P23…其重要程度用权重系数W21,W22,W23…表示目标规划的基本思想是，给定若干目标以及实现这些目标的优先顺序，在有限的资源条件下，使总的偏离目标值的偏差最小小结期望目标函数fi(X)=gi恰好达到目标minZ=f(d-+d+)fi(X)=gi超过目标minZ=f(d-)fi(X)gi不超过目标minZ=f(d+)3）目标函数（准则函数）对目标约束：fi(X)+di--di+=gi小结目标函数的实质：求一组决策变量的满意值，使决策结果与给定目标总偏差最小。目标函数的特点：目标函数中只有偏差变量目标函数总是求偏差变量最小目标函数值的含义：Z=0：各级目标均已达到Z0：部分目标未达到一般模型KkddnjxKkqddxCkmibxadwdwPdwdwPZkkjnjkkkjjnjijijkkkLkkLkLkkkkkk10,1011,min11111112.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+X211X1-X2+d1--d1+=0X1+2X2+d2--d2+=108X1+10X2+d3--d3+=56X1,X2,di-,di+0minZ1=d1+2X1+X211X1-X2+d1--d1+=0在P1级只包含d1+，因此只取含有d1+的约束条件；绝对约束第2步求解P1级单目标规划minZ1=d1+2X1+X211X1-X2+d1--d1+=0计算结果：MinZ1(D-，D+)=d1+=0第3步：构造P2级目标构成的单目标线性上一级目标所应满足的约束条件本级目标所应满足的约束条件为保证优化时P2，不破坏P1的最优值而增加的约束条件minZ=P1d1++P2(2d2-+d2+)+P3(d3-)2X1+X211X1-X2+d1--d1+=0X1+2X2+d2--d2+=108X1+10X2+d3--d3+=56X1,X2,di-,di+0minZ2=2d2-+d2+2X1+X211X1-X2+d1--d1+=0X1+2X2+d2--d2+=10d1+=0minZ2=2d2-+d2+2X1+X211X1-X2+d1--d1+