第五章_多目标规划

第五章多目标规划多目标线性规划问题多目标规划问题的非劣解和非劣解集求解多目标规划的目标线性加权法层次分析法目标规划多目标规划的例子(1)产品ABC条件利润（万元/吨）941目标函数，最大化耗用原料（吨/吨）425耗用原料不超过38吨排放污染（m3/吨）213排放污染不超过25m3销售价格（万元/吨）301020销售总额不低于100万元产量（吨）111总产量不低于12吨利润最大化的线性规划模型为：maxz=9x1+4x2+x3s.t.4x1+2x2+5x3≤38耗用原料约束2x1+x2+3x3≤25排放污染约束30x1+10x2+20x3≥100销售总额约束x1+x2+x3≥12产量约束x1,x2,x3≥0最优解如下表：产品条件最优解利润（万元/吨）目标函数，最大化总利润83万元耗用原料（吨/吨）耗用原料不超过38吨耗用原料38吨排放污染（m3/吨）排放污染不超过25m3排放污染19m3销售价格（万元/吨）销售总额不低于100万元销售总额260万元产量（吨）总产量不低于12吨总产量12吨如果允许排放的污染量从25立方米逐步减少，最优解也将发生变化。变化情况如下表：：多目标规划的例子(2)允许排放的污染(m3)产品A产量（吨）产品B产量（吨）产品C产量（吨）最大利润（万元）25750831975083186607817570731648068153906314210058131110531201204811没有可行解多目标规划的例子(3)25242322211918171615141312允许排放的污染（m3）8378736863585348最大利润（万元）允许排放的污染和最大利润之间的关系排放污染最小和利润最大两个目标可以同时实现的区域利润最大化和排放污染最小化双目标问题的图示两个目标的规划问题的劣解和非劣解第一个目标第一个目标z1Az1Bz2Az2BNMPP’AB劣解劣解非劣解(Pareto解)非劣解(Pareto解)非劣解集(Pareto解集)两个目标都可能实现的区域第一个目标取定一个值z1A，作为约束条件，优化第二个目标，得到第二个目标的最优值Z2A，得到A点。……用同样的方法得到B点。依次进行，得到两个目标之间关系的曲线AB和相应的区域。区域内部的点N和M称为“劣解”，劣解的两个目标同时可以改进。曲线AB上的点称为“非劣解”或“Pareto”解，非劣解的两个目标不可能同时改进。设多目标规划的可行域为，设其中的一个可行解X*∈，它的K个目标值分别f1(X*)，f2(X*)，……，fk(X*)如果对于任意的可行解X∈，都至少有一个目标i，使得fi(X)fi(X*)则称X*为这个多目标规划的一个Pareto解（也称为非劣解、有效解）。如果一个多目标规划问题有一个以上的Pareto解，这些Pareto解组成的集合称为Pareto解集。多目标规划问题的非劣解和非劣解集f1(X)f2(X)f(x)xPareto集x1x2x4x5x3图中x1、x5为劣解，x2、x3、x4为Pareto解劣解劣解Pareto解集的图解多目标线性规划的Pareto解集(1)设两个目标的线性规划为minz1=c11x1+c12x2minz2=c21x1+c22x2s.t.a11x1+a12x2≤b1a21x1+a22x2≤b2x1,x2≥0设以z1为单目标的线性规划最优解为B，以z2为单目标的线性规划最优解为D。可行域内部（不包括边界）的可行解都是劣解。OABEDCz1z2Fz1z2OABEDCz1z2z1F对于多目标规划可行域中的点，根据两个目标函数的法线方向，可以确定两个目标同时可以改进的方向。这是一个锥体，锥体内的方向称为多目标规划的优化方向集合。目标函数z1改善的方向目标函数z1和z2同时改善的方向z2目标函数z2改善的方向OABEDCF当一个可行解的优化方向集合和可行域的交集为非空时，两个目标z1，z2可以同时改善，即这样的可行解是劣解。优化方向集合和可行域的交集为空集时，两个目标函数不可能同时改善。这样的可行解是多目标规划的Pareto解。图中的可行解B,C,D是多目标规划的Pareto解。Pareto解集为折线BCD。多目标线性规划的Pareto解集(2)用单纯形表求解多目标线性规划Pareto解集双目标线性规划问题为maxz1=3x1+2x2maxz2=-x1+2x2s.t.x1+x2≤62x1+x2≤10x1+2x2≤10x1，x2≥0标准化问题为minz1=-3x1-2x2minz2=x1-2x2s.t.x1+x2+x3=62x1+x2+x4=10x1+2x2+x5=10x1,x2,x3,x4,x5≥0多目标线性规划问题的图解。6543210123456z2z1OABCD多目标规划的图形目标z1的最优解目标z2的最优解多目标规划的Pareto解集x3=0x4=0x5=0x2=0x1=0maxz1=3x1+2x2maxz2=-x1+2x2s.t.x1+x2≤62x1+x2≤10x1+2x2≤10x1，x2≥01010600RHS1002100x50101200x40011100x30002-110z20002301z1x5x4x3x2x1z2z1多目标线性规划单纯形表(1)如果非基变量在两个目标中的检验数都大于0，当前的基础可行解是劣解。这个非基变量进基，两个目标都会改善。如果任何一个非基变量在两个目标中的检验数不同时大于0，这个基础可行解是Pareto解，任何一个非基变量进基，一个目标将会改善，而另一个目标将会变差。1010600RHS1002100x50101200x40011100x30002-110z20002301z1x5x4x3x2x1z2z1当前的解(x1,x2,x3,x4,x5)=(0,0,6,10,10),z1=0,z2=0是劣解，对应于图中的O点。x1进基，x4离基，z1会改善，z2将会变差，进到劣解A。x2进基，x5离基，z1，z2可以同时改善，进到Pareto解D。多目标线性规划单纯形表(2)5515-15RHS1-1/203/2000x501/201/2100x10-1/211/2000x301/205/2010z20-3/201/2001z1x5x4x3x2x1z2z1当前的解(x1,x2,x3,x4,x5)=(5,0,1,0,5),z1=15,z2=-5是劣解。对应于A点。x2进基，x3离基，z1，z2同时改善，进到Pareto解B。x4进基，x1离基，z1会变差，z2会改善，回到劣解O。多目标线性规划单纯形表(3)2420-16RHS11-30000x501-10100x10-121000x203-50010z20-1-10001z1x5x4x3x2x1z2z1当前的解(x1,x2,x3,x4,x5)=(2,4,0,0,2),z1=16,z2=0是Pareto解。对应于B点。x3进基，x2离基，两个目标同时会变差，回到劣解A。x4进基，x5离基，z1会变差，z2会改善，进到Pareto解C。多目标线性规划单纯形表(4)224-6-14RHS11-30000x4-1020100x110-11000x2-3040010z210-40001z1x5x4x3x2x1z2z1当前的解(x1,x2,x3,x4,x5)=(2,4,0,2,0),z1=14,z2=6是Pareto解。对应于C点。x3进基，x1离基，z1会变差，z2会改善，进到Pareto解D。x5进基，x4离基，z1会改善，z2会变差，回到Pareto解B。多目标线性规划单纯形表(5)515-8-10RHS-1/21003/200x4-1/20101/200x31/20011/200x2-1000-210z2-1000201z1x5x4x3x2x1z2z1当前的解(x1,x2,x3,x4,x5)=(0,5,1,5,0),z1=10,z2=8是Pareto解。对应于D点。x1进基，x3离基，z1会改善，z2会变差，回到Pareto解C。x5进基，x2离基，z1会变差，z2会变差，将回到劣解O。已搜索到这个多目标规划的所有Pareto解B点，C点，D点。多目标线性规划单纯形表(6)maxz1=3x1+2x2maxz2=-x1+2x2s.t.x1+x2≤62x1+x2≤10x1+2x2≤10x1，x2≥0目标函数线性加权：z=1z1+2z20≤1,2≤11+2＝1由图解可以看出，加权以后的单目标问题的最优解必定是多目标规划的一个Pareto解。54321012345z2z11z1+2z2求解多目标线性规划的线性加权法多目标的线性加权转化为单目标规划问题一、多目标规划转化为单目标规划问题1、评价函数法F(X)=U{f1(X)，f2(X)，…，fK(X)}将多目标规划问题转化为单目标规划问题。最简单的评价函数是线性加权。线性加权法F(X)=1f1(X)+2f2(X)+……+KfK(X)其中0≤1，2，…，K≤1，称为目标权重。面积(m2）单价（元/m2）朝向地段楼层住房A2004800南丙四层住房B1805500西甲七层住房C1504000东乙三层例1：住房选择（决策空间是离散的）确定各目标最理想和最不理想的值，将各目标进行归一化处理。最理想的值为1，最不理想的值为0，将各决策方案的实际目标值转化为0～1之间的值。面积（m2）单价（元/m2）朝向地段楼层最好200(1.0)3000(1.0)南(1.0)甲(1.0)三层(1.0)最差75(0.0)6000(0.0)北(0.0)丁(0.0)一层(0.0)实际指标A2004800南丙四层B1805500西甲七层C1504000东乙三层归一化A1.00.4001.00.40.9B0.840.1670.41.00.6C0.600.6670.70.71.0确定各目标的权重设目标重要性由大到小依次为：单价—面积—地段—朝向—楼层确定目标权重1+2+3+4+5=1，1123450计算各方案的评价指标F(X)=4fi(X)，评价指标最高的为最优决策。例如，设五个目标的权重分别为：面积（m2）单价（元/m2）朝向地段楼层目标权重0.250.30.150.20.1面积（m2）单价（元/m2）朝向地段楼层评价值目标权重0.250.30.150.20.1住房A1.00.4001.00.40.90.690住房B0.840.1670.41.00.60.580住房C0.600.6670.70.71.00.695*住房A2004800南丙四层住房B1805500西甲七层住房C1504000东乙三层根据评价值，选择住房C是最优决策。线性加权法的缺点是各目标的权重完全由主观确定，而权重的选取对决策结果起着十分关键的作用。优点方便直观，简单易行可以利用丰富的单目标决策方法和软件缺点权重的确定完全靠决策者主观判断对不同量纲的目标，合成以后的目标实际意义不明线性加权法的优缺点层次分析法（AHP）层次分析法是由T.L.Saaty提出的一种确定多目标决策中各目标的权重的方法，不仅在多目标决策中有重要作用，在管理以外的其它学科也有许多应用。在多目标决策中，各目标的权重对分析结果具有重要影响，但权重的确定比较困难。层次分析法的基础是目标的分层和对同一层次的各目标的重要性进行两两比较，使确定各目标的权重的任务具有可操作性。矩阵的特征向量和特征根设A是n×n非奇异的矩阵，如果存在一个实数0和一个n×1的非零向量V，满足AV=V，则称V为矩阵A的特征向量，为矩阵A的一个特征根。3254A的特征根。是矩阵的特征向量是矩阵A21A25V11V2121111V11111113254AV25V11V21对于向量112V252410253254AV