多目标规划培训课程.ppt

《多目标规划培训课程.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第五章多目标规划多目标线性规划问题多目标规划问题的非劣解和非劣解集求解多目标规划的目标线性加权法层次分析法目标规划多目标规划的例子(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产量约束

2、x1,x2,x3≥0最优解如下表：产品条件最优解利润（万元/吨）目标函数，最大化总利润83万元耗用原料（吨/吨）耗用原料不超过38吨耗用原料38吨排放污染（m3/吨）排放污染不超过25m3排放污染19m3销售价格（万元/吨）销售总额不低于100万元销售总额260万元产量（吨）总产量不低于12吨总产量12吨如果允许排放的污染量从25立方米逐步减少，最优解也将发生变化。变化情况如下表：：多目标规划的例子(2)允许排放的污染(m3)产品A产量（吨）产品B产量（吨）产品C产量（吨）最大利润（万元）2575083197508318660781757073164806815390631421005

3、8131110531201204811没有可行解多目标规划的例子(3)25242322211918171615141312允许排放的污染（m3）8378736863585348最大利润（万元）允许排放的污染和最大利润之间的关系排放污染最小和利润最大两个目标可以同时实现的区域利润最大化和排放污染最小化双目标问题的图示两个目标的规划问题的劣解和非劣解第一个目标第一个目标z1Az1Bz2Az2BNMPP’AB劣解劣解非劣解(Pareto解)非劣解(Pareto解)非劣解集(Pareto解集)两个目标都可能实现的区域第一个目标取定一个值z1A，作为约束条件，优化第二个目标，得到第二个目标的最优

4、值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解组成的集合称为Pa

5、reto解集。多目标规划问题的非劣解和非劣解集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对于多目标规划可行域

6、中的点，根据两个目标函数的法线方向，可以确定两个目标同时可以改进的方向。这是一个锥体，锥体内的方向称为多目标规划的优化方向集合。目标函数z1改善的方向目标函数z1和z2同时改善的方向z2目标函数z2改善的方向OABEDCF当一个可行解的优化方向集合和可行域的交集为非空时，两个目标z1，z2可以同时改善，即这样的可行解是劣解。优化方向集合和可行域的交集为空集时，两个目标函数不可能同时改善。这样的可行解是多目标规划的Pareto解。图中的可行解B,C,D是多目标规划的Pareto解。Pareto解集为折线BCD。多目标线性规划的Pareto解集(2)用单纯形表求解多目标线性规划Pareto

7、解集双目标线性规划问题为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的最优解多目标规划