第五章多目标规划.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2020年5月29日星期五,#,11 十一月 2026,第五章多目标规划,多目标规划的例子(1),产 品,A,B,C,条件,利润（万元/吨）,9,4,1,目标函数，最大化,耗用原料（吨/吨）,4,2,5,耗用原料不超过38吨,排放污染（m,3,/吨）,2,1,3,排放污染不超过25m,3,销售价格（万元/吨）,30,10,20,销售总额不低于100万元,产量（吨）,1,1,1,总产量不低于12吨,利润最大化的线性规划模型为：,max z=9x1+4x2+x3,s.t.4x,1,+2x,2,+5x,3,38耗用原料约束,2x,1,+x,2,+3x,3,25排放污染约束,30 x,1,+10 x,2,+20 x,3,100销售总额约束,x,1,+x,2,+x,3,12产量约束,x,1,x,2,x,3,0,最优解如下表：,产 品,条件,最优解,利润（万元/吨）,目标函数，最大化,总利润83万元,耗用原料（吨/吨）,耗用原料不超过38吨,耗用原料38吨,排放污染（m,3,/吨）,排放污染不超过25m,3,排放污染19m,3,销售价格（万元/吨）,销售总额不低于100万元,销售总额260万元,产量（吨）,总产量不低于12吨,总产量12吨,如果允许排放的污染量从25立方米逐步减少，最优解也将发生变化。变化情况如下表：,多目标规划的例子(2),允许排放的,污染(m,3,),产品A产量,（吨）,产品B产量,（吨）,产品C产量,（吨）,最大利润,（万元）,25,7,5,0,83,19,7,5,0,83,18,6,6,0,78,17,5,7,0,73,16,4,8,0,68,15,3,9,0,63,14,2,10,0,58,13,1,11,0,53,12,0,12,0,48,11,没有可行解,多目标规划的例子(3),25 24 23 22 21 19 18 17 16 15 14 13 12,允许排放的污染（m,3,）,83,78,73,68,63,58,53,48,最大利润（万元）,允许排放的污染和最大利润之间的关系,排放污染最小和利润最大两个目标可以同时实现的区域,利润最大化和排放污染最小化双目标问题的图示,两个目标的规划问题的劣解和非劣解,第一个目标,第一个目标,z,1A,z,1B,z,2A,z,2B,N,M,P,P,A,B,劣解,劣解,非劣解(Pareto解),非劣解(Pareto解),非劣解集(Pareto解集),两个目标都可能实现的区域,第一个目标取定一个值z,1A,，作为约束条件，优化第二个目标，得到第二个目标的最优值Z,2A,，得到A点。用同样的方法得到B点。依次进行，得到两个目标之间关系的曲线AB和相应的区域。,区域内部的点N和M称为“劣解”，劣解的两个目标同时可以改进。曲线AB上的点称为“非劣解”或“Pareto”解，非劣解的两个目标不可能同时改进。,设多目标规划的可行域为,，设其中的一个可行解,X*，它的K个目标值分别,f,1,(X*)，f,2,(X*)，f,k,(X*),如果对于任意的可行解X ，都至少有一个目标i，使得,f,i,(X)f,i,(X*),则称X*为这个多目标规划的一个Pareto解（也称为非劣解、有效解）。,如果一个多目标规划问题有一个以上的Pareto解，这些Pareto解组成的集合称为Pareto解集。,多目标规划问题的非劣解和非劣解集,f,1,(X),f,2,(X),f(x),x,Pareto 集,x,1,x,2,x,4,x,5,x,3,图中x,1,、x,5,为劣解，x,2,、x,3,、x,4,为Pareto解,劣解,劣解,Pareto解集的图解,多目标线性规划的Pareto解集(1),设两个目标的线性规划为,min z,1,=c,11,x,1,+c,12,x,2,min z,2,=c,21,x,1,+c,22,x,2,s.t.,a,11,x,1,+a,12,x,2,b,1,a,21,x,1,+a,22,x,2,b,2,x,1,x,2,0,设以z,1,为单目标的线性规划最优解为B，以z,2,为单目标的线性规划最优解为D。可行域内部（不包括边界）的可行解都是劣解。,O,A,B,E,D,C,z,1,z,2,F,z,1,z,2,O,A,B,E,D,C,z,1,z,2,z,1,F,对于多目标规划可行域中的点，根据两个目标函数的法线方向，可以确定两个目标同时可以改进的方向。这是一个锥体，锥体内的方向称为多目标规划的优化方向集合。,目标函数z,1,改善的方向,目标函数z,1,和z,2,同时改善的方向,z,2,目标函数z,2,改善的方向,O,A,B,E,D,C,F,当一个可行解的优化方向集合和可行域的交集为非空时，两个目标z,1,，z,2,可以同时改善，即这样的可行解是劣解。优化方向集合和可行域的交集为空集时，两个目标函数不可能同时改善。这样的可行解是多目标规划的Pareto解。图中的可行解B,C,D是多目标规划的Pareto解。Pareto解集为折线BCD。,多目标线性规划的Pareto解集(2),用单纯形表求解多目标线性规划Pareto解集,双目标线性规划问题为,max z,1,=3x,1,+2x,2,max z,2,=-x,1,+2x,2,s.t.x,1,+x,2,6,2x,1,+x,2,10,x,1,+2x,2,10,x,1,，x,2,0,标准化问题为,min z,1,=-3x,1,-2x,2,min z,2,=x,1,-2x,2,s.t.x,1,+x,2,+x,3,=6,2x,1,+x,2,+x,4,=10,x,1,+2x,2,+x,5,=10,x,1,x,2,x,3,x,4,x,5,0,多目标线性规划问题的图解。,6,5,4,3,2,1,0123456,z,2,z,1,O,A,B,C,D,多目标规划的图形,目标z,1,的最优解,目标z,2,的最优解,多目标规划的Pareto解集,x,3,=0,x,4,=0,x,5,=0,x,2,=0,x,1,=0,max z,1,=3x,1,+2x,2,max z,2,=-x,1,+2x,2,s.t.x,1,+x,2,6,2x,1,+x,2,10,x,1,+2x,2,10,x,1,，x,2,0,10,10,6,0,0,RHS,1,0,0,2,1,0,0,x,5,0,1,0,1,2,0,0,x,4,0,0,1,1,1,0,0,x,3,0,0,0,2,-1,1,0,z,2,0,0,0,2,3,0,1,z,1,x,5,x,4,x,3,x,2,x,1,z,2,z,1,多目标线性规划单纯形表(1),如果非基变量在两个目标中的检验数都大于0，当前的基础可行解是劣解。这个非基变量进基，两个目标都会改善。,如果任何一个非基变量在两个目标中的检验数不同时大于0，这个基础可行解是Pareto解，任何一个非基变量进基，一个目标将会改善，而另一个目标将会变差。,10,10,6,0,0,RHS,1,0,0,2,1,0,0,x,5,0,1,0,1,2,0,0,x,4,0,0,1,1,1,0,0,x,3,0,0,0,2,-1,1,0,z,2,0,0,0,2,3,0,1,z,1,x,5,x,4,x,3,x,2,x,1,z,2,z,1,当前的解(x,1,x,2,x,3,x,4,x,5,)=(0,0,6,10,10),z,1,=0,z,2,=0是劣解，对应于图中的O点。,x,1,进基，x,4,离基，z,1,会改善，z,2,将会变差，进到劣解A。,x,2,进基，x,5,离基，z,1,，z,2,可以同时改善，进到Pareto解D。,多目标线性规划单纯形表(2),5,5,1,5,-15,RHS,1,-1/2,0,3/2,0,0,0,x,5,0,1/2,0,1/2,1,0,0,x,1,0,-1/2,1,1/2,0,0,0,x,3,0,1/2,0,5/2,0,1,0,z,2,0,-3/2,0,1/2,0,0,1,z,1,x,5,x,4,x,3,x,2,x,1,z,2,z,1,当前的解(x,1,x,2,x,3,x,4,x,5,)=(5,0,1,0,5),z,1,=15,z,2,=-5是劣解。对应于A点。,x,2,进基，x,3,离基，z,1,，z,2,同时改善，进到Pareto解B。,x,4,进基，x,1,离基，z,1,会变差，z,2,会改善，回到劣解O。,多目标线性规划单纯形表(3),2,4,2,0,-16,RHS,1,1,-3,0,0,0,0,x,5,0,1,-1,0,1,0,0,x,1,0,-1,2,1,0,0,0,x,2,0,3,-5,0,0,1,0,z,2,0,-1,-1,0,0,0,1,z,1,x,5,x,4,x,3,x,2,x,1,z,2,z,1,当前的解(x,1,x,2,x,3,x,4,x,5,)=(2,4,0,0,2),z,1,=16,z,2,=0是Pareto解。对应于B点。,x,3,进基，x,2,离基，两个目标同时会变差，回到劣解A。,x,4,进基，x,5,离基，z,1,会变差，z,2,会改善，进到Pareto解C。,多目标线性规划单纯形表(4),2,2,4,-6,-14,RHS,1,1,-3,0,0,0,0,x,4,-1,0,2,0,1,0,0,x,1,1,0,-1,1,0,0,0,x,2,-3,0,4,0,0,1,0,z,2,1,0,-4,0,0,0,1,z,1,x,5,x,4,x,3,x,2,x,1,z,2,z,1,当前的解(x,1,x,2,x,3,x,4,x,5,)=(2,4,0,2,0),z,1,=14,z,2,=6是Pareto解。对应于C点。,x,3,进基，x,1,离基，z,1,会变差，z,2,会改善，进到Pareto解D。,x,5,进基，x,4,离基，z,1,会改善，z,2,会变差，回到Pareto解B。,多目标线性规划单纯形表(5),5,1,5,-8,-10,RHS,-1/2,1,0,0,3/2,0,0,x,4,-1/2,0,1,0,1/2,0,0,x,3,1/2,0,0,1,1/2,0,0,x,2,-1,0,0,0,-2,1,0,z,2,-1,0,0,0,2,0,1,z,1,x,5,x,4,x,3,x,2,x,1,z,2,z,1,当前的解(x,1,x,2,x,3,x,4,x,5,)=(0,5,1,5,0),z,1,=10,z,2,=8是Pareto解。对应于D点。,x,1,进基，x,3,离基，z,1,会改善，z,2,会变差，回到Pareto解C。,x,5,进基，x,2,离基，z,1,会变差，z,2,会变差，将回到劣解O。,已搜索到这个多目标规划的所有Pareto解B点，C点，D点。,多目标线性规划单纯形表(6),max z,1,=3x,1,+2x,2,max z,2,=-x,1,+2x,2,s.t.x,1,+x,2,6,2x,1,+x,2,10,x,1,+2x,2,10,x,1,，x,2,0,目标函数线性加权：,z=,1,z,1,+,2,z,2,0,1,2,1,1,+,2,1,由图解可以看出，加权以后的单目标问题的最优解必定是多目标规划的一个Pareto解。,5,4,3,2,1,012345,z,2,z,1,1,z,1,+,2,z,2,求解多目标线性规划的线性加权法,多目标的线性加权转化为单目标规划问题,一、多目标规划转化为单目标规划问题,1、评价函数法,F(X)=Uf,1,(X)，f,2,(X)，f,K,(X),将多目标规划问题转化为单目标规划问题。最简单的评价函数是线性加权。,线性加权法,F(X)=,1,f,1,(X)+,2,f,2,(X)+,K,f,K,(X),其中0,1,，,2,，,，,K,1，称为目标权重。,面积(m,2,）,单价（元/m,2,）,朝向,地段,楼层,住房A,200,4800,南,丙,四层,住房B,180,5500,西,甲,七层,住房C,150,4000,东,乙,三层,例1：住房选择（决策空间是离散的）,确定各目标最理想和最不理想的值，将各目标进行归一化处理。最理想的值为1，最不理想的值为0，将各决策方案的实际目标值转化为01之间的值。,面积（m,2,）,单价（元/m,2,）,朝向,地段,楼层,最好,200(1.0),3000(1.0),南(1.0),甲(1.0),三层(1.0),最差,75(0.0),6000(0.0),北(0.0),丁(0.0),一层(0.0),实际指标,A,200,4800,南,丙,四层,B,180,5500,西,甲,七层,C,150,4000,东,乙,三层,归一化,A,1.0,0.400,1.0,0.4,0.9,B,0.84,0.167,0.4,1.0,0.6,C,0.60,0.667,0.7,0.7,1.0,确定各目标的权重,设目标重要性由大到小依次为：单价面积地段朝向楼层确定目标权重,1,+,2,+,3,+,4,+,5,=1，1 ,1,2,3,4,5,0,计算各方案的评价指标F(X)=,4,f,i,(X)，评价指标最高的为最优决策。,例如，设五个目标的权重分别为：,面积（m,2,）,单价（元/m,2,）,朝向,地段,楼层,目标权重,0.25,0.3,0.15,0.2,0.1,面积（m,2,）,单价（元/m,2,）,朝向,地段,楼层,评价值,目标权重,0.25,0.3,0.15,0.2,0.1,住房A,1.0,0.400,1.0,0.4,0.9,0.690,住房B,0.84,0.167,0.4,1.0,0.6,0.580,住房C,0.60,0.667,0.7,0.7,1.0,0.695*,住房A,200,4800,南,丙,四层,住房B,180,5500,西,甲,七层,住房C,150,4000,东,乙,三层,根据评价值，选择住房C是最优决策。线性加权法的缺点是各目标的权重完全由主观确定，而权重的选取对决策结果起着十分关键的作用。,优点,方便直观，简单易行,可以利用丰富的单目标决策方法和软件,缺点,权重的确定完全靠决策者主观判断,对不同量纲的目标，合成以后的目标实际意义不明,线性加权法的优缺点,层次分析法（AHP）,层次分析法是由T.L.Saaty提出的一种确定多目标决策中各目标的权重的方法，不仅在多目标决策中有重要作用，在管理以外的其它学科也有许多应用。,在多目标决策中，各目标的权重对分析结果具有重要影响，但权重的确定比较困难。层次分析法的基础是目标的分层和对同一层次的各目标的重要性进行两两比较，使确定各目标的权重的任务具有可操作性。,矩阵的特征向量和特征根,设A是nn非奇异的矩阵，如果存在一个实数,0和一个n1的非零向量V，满足 AV=V，则称V为矩阵A的特征向量，为矩阵A的一个特征根。,由线性代数可知，方程组 AV=,V 即 (A-I)V=0有非零解的条件是系数行列式|A-I|=0。其中 I 为单位矩阵。,例如,展开行列式,(-4-)(3-)+10=0，,2,20,求解二次方程，得到矩阵的特征根,1,1，,2,2,对于高阶矩阵，用行列式计算特征根需要求解高次方程，计算比较复杂，可以采用叠代法。,矩阵特征根的计算,判断矩阵特征向量和特征根的叠代算法,任取一个初始n1向量,计算,已经收敛。因此判断矩阵的特征向量,并且,max,=1,特征向量为,求特征向量和特征根的近似方法,将每一列相加，得到：,特征向量为,归一化,层次分析法原理,显然，n个物体归一化重量之和等于1。,如果已知这n个物体总量两两比较的值，能否求出它们（归一化）的重量？,设n个物体，重量分别为w,1,，w,2,，w,n,，总重量为,将每一个物体的重量除以n个物体的总重量称为这个物体的“归一化”重量。,设n个物体重量的两两比较矩阵如下,例如，四个物体的重量为 w,1,=2,w,2,=1,w,3,=3,w,4,=4（公斤）,它们的总重量W=10公斤,四个物体两两比较的判断矩阵为,这个矩阵具有以下特点：,对角线上的元素,a,ii,=1（i=1,2,n）,以对角线对称的元素互为倒数,a,ij,=1/a,ji,（i,j=1,2,n）,各物体之间的相对重量比值是一致的,a,ij,=a,ik,/a,jk,（i,j=1,2,n）,n个物体归一化的重量组成的向量是判断矩阵的一个特征向量，对应的最大特征根,max,=n。,因此，只要给出判断矩阵，就可以求出n个物体的归一化重量。,同样，在多目标决策中，如果能给出各目标重要性两两比较的判断矩阵，就可以求出这些目标（归一化）的相对重要性。,设目标C由n个元素A,1,，A,2,，A,n,组成，对这n个元素相对于目标C的重要性作两两比较，构成以下判断矩阵：,C,A,1,A,2,A,n,A,1,a,11,a,12,a,1n,A,2,a,21,a,22,a,2n,A,n,a,n1,a,n2,a,nn,a,ij,含义,1,元素 i 和元素 j 同等重要,3,元素 i 比元素 j 稍微重要,5,元素 i 比元素 j 明显重要,7,元素 i 比元素 j 强烈重要,9,元素 i 比元素 j 绝对重要,其中a,ij,=1,2,3,4,5,6,7,8,9以及1/2，1/3，1/4，1/5，1/6，1/7，1/8，1/9。这些数字的含义为：,数值2、4、6、8的意义介于以上表格相邻两行的含义之间,与物体的重量之比不同，目标的重要性判断矩阵可能是不一致（Inconsistency）的。即可能出现A,1,比A,2,重要，A,2,比A,3,重要，A,3,又比A,1,重要这样的判断。如果不一致性在一定的范围以内，判断矩阵还是有效的，不一致性超出一定的范围，判断矩阵的有效性就有问题。,线性代数可以证明，判断矩阵的不一致性可以由矩阵的最大特征根,max,表示，当判断矩阵完全一致时，,max,n，不完全一致时，,max,n，,max,越大说明不一致性越严重。,单层次分析法的步骤：,构造组成目标各元素的重要性两两比较判断矩阵,求解判断矩阵的最大特征根和相应的特征向量,判断矩阵的一致性检验（Consistency Test）,如果通过一致性检验，得到的特征向量就是各元素的权重,n,1,2,3,4,5,6,7,8,9,10,R.I.,0,0,0.52,0.89,1.12,1.26,1.36,1.41,1.46,1.49,n,11,12,13,14,15,R.I.,1.52,1.54,1.56,1.58,1.59,层次分析法步骤,2、计算平均随机一致性指标R.I.（Random Index）。这个指标是随机产生的不同维数的判断矩阵的特征根的平均值,1、计算一致性指标C.I.（Consistency Index）,3、计算一致性比例C.R.（Consistency Ratio）,当C.R.0.1时，认为判断矩阵的一致性是可以接受的。,理想的住房,A,单价,C,1,面积,C,2,楼层,C,3,地段,C,4,朝向,C,5,舒适,B,2,经济,B,1,便利,B,3,建立目标的层次结构,对目标A,经济,B,1,舒适,B,2,便利,B,3,经济,B,1,1,3,7,舒适,B,2,1/3,1,3,便利,B,3,1/7,1/3,1,单层分析：层次B对目标A的两两判断矩阵,理想的住房,A,舒适,B,2,经济,B,1,便利,B,3,计算B-A判断矩阵的特征向量和特征根,一致性检验,层次C对目标B,1,的两两判断矩阵,经济,B,1,单价,C,1,面积,C,2,楼层,C,3,地段,C,4,朝向,C,5,经济,单价,面积,楼层,地段,朝向,单价,1,1,5,1,7,面积,1,1,5,1,7,楼层,1/5,1/5,1,1/5,3,地段,1,1,5,1,9,朝向,1/7,1/7,1/3,1/9,1,max,=5.1212,C.I.=0.0303,R.I.=1.12,C.R.=0.020.1,层次C对目标B,3,的两两判断矩阵,便利,B,3,单价,C,1,面积,C,2,楼层,C,3,地段,C,4,朝向,C,5,便利,单价,面积,楼层,地段,朝向,单价,1,1,1/3,1/7,1,面积,1,1,1/3,1/7,1,楼层,3,3,1,1/5,3,地段,7,7,5,1,7,朝向,1,1,1/3,1/7,1,max,=5.087,C.I.=0.022,R.I.=1.12,C.R.=0.0190.1,理想的住房,A,舒适,B,2,经济,B,1,便利,B,3,单价,C,1,面积,C,2,楼层,C,3,地段,C,4,朝向,C,5,0.654,0.258,0.088,0.281,0.281,0.073,0.567,.,.,.,每一层因素对上一层因素的权重,B对A,的权重,经济(B,1,),舒适(B,2,),便利(B,3,),C对A的,总权重,权重,排序,0.654,0.258,0.088,C,对,B,的权重,单价(C,1,),0.281,0.040,0.073,0.201,三,面积(C,2,),0.281,0.379,0.073,0.288,二,楼层(C,3,),0.086,0.190,0.214,0.124,四,地段(C,4,),0.318,0.299,0.567,0.335,一,朝向(C,5,),0.032,0.092,0.073,0.051,五,计算各底层因素对总目标的权重,项目,总权重,楼房A,楼房B,楼房C,单价C1,0.201,0.4,0.167,0.667,面积C2,0.288,1.0,0.84,0.6,楼层C3,0.124,0.9,0.6,1.0,地段C4,0.335,0.4,0.1,0.7,朝向C5,0.051,1.0,0.4,0.7,总评分,0.665,0.404,0.701,计算各决策方案的评分,目标规划（Goal Programming）,线性规划是一种应用非常广泛的优化模型，但它也有以下明显的缺点：,1、只能求解,单目标,问题；,2、把,约束条件和目标函数,作为完全不同的概念来处理，而在实际问题中，目标函数和约束条件往往是可以互换的，并没有严格的区别。,3、,约束条件,是,刚性,的,，即可行解必须在可行域中。在一些实际问题中，约束条件是可以突破的，约束条件的右边常数并不是变量上限或下限，而是一个希望能够最接近的目标。,4、如果,约束条件互不相容,，则线性规划无可行解。,针对线性规划的以上缺陷，A.Charnes和W.Cooper提出了目标规划（Goal Programming），这是一种求解多目标线性规划的方法。,目标规划分为,无优先级的目标规划,和,有优先级的目标规划,。,目标规划的图解,设线性规划问题为,max z=2x,1,+3x,2,s.t.x,1,-x,2,1,x,1,+x,2,2,x,2,3,x,1,，x,2,0,01234,3,2,1,-1,由图解可知，线性规划的最优解为：,x,1,=4，x,2,=3,max z=17,min z=n,1,+p,1,+n,2,+p,2,+n,3,+p,3,+n,4,+p,4,s.t.2x,1,+3x,2,+n,1,-p,1,=12 (1),x,1,-x,2,+n,2,-p,2,=1 (2),x,1,+x,2,+n,3,-p,3,=2 (3),x,2,+n,4,-p,4,=3 (4),x,1,x,2,n,1,p,1，,n,2,p,2,n,3,p,3,n,4,p,4,0,相应的目标规划问题为,其中p,1,、p,2,、p,3,、p,4,称为正偏差变量，n,1,、n,2,、n,3,、n,4,称为负偏差变量。,一般形式表示为：,01234,4,3,2,1,-1,p,3,=3,n,4,=1,2x,1,+3x,2,=12 (1),x,2,=3 (4),x,1,-x,2,=1 (2),x,1,+x,2,=2 (3),n,1,=4,n,2,=2,p,3,=1,n,4,=1,用LINDO求解以上问题，得到目标规划的最优解为：,x,1,=3，x,2,=2,p,1,=0,p,2,=0,p,3,=3,p,4,=0,n,1,=0,n,2,=0,n,3,=0,n,4,=1,min z=4,min z=n,1,+p,1,+n,2,+p,2,+n,3,+p,3,+n,4,+p,4,s.t.2x,1,+3x,2,+n,1,-p,1,=12 (1),x,1,-x,2,+n,2,-p,2,=1 (2),x,1,+x,2,+n,3,-p,3,=2 (3),x,2,+n,4,-p,4,=3 (4),x,1,x,2,n,i,p,i,0,产品A,产品B,产品C,条件,利润（万元/吨）,9,4,1,总利润最大化,耗用原料（吨/吨）,4,2,5,耗用原料总量不超过38吨,排放污染（m,3,/吨）,2,1,3,排放污染总量不超过26m,3,销售价格（万元/吨）,30,10,20,销售总额不低于100万元,总产量（吨）,1,1,1,总产量不低于18吨,如果以利润为目标函数，线性规划模型为：,max z=9x,1,+4x,2,+x,3,s.t.4x,1,+2x,2,+5x,3,38（1）原料总量约束,2x,1,+x,2,+3x,3,26（2）排放污染约束,30 x,1,+10 x,2,+20 x,3,100（3）销售总额约束,x,1,+x,2,+x,3,18（4）总产量约束,x,1,x,2,x,3,0,目 标,产品,A,产品,B,产品,C,目标的,理想值,正偏差,变量,负偏差,变量,利润（万元/吨）,9,4,1,77,p,1,n,1,耗用原料（吨/吨）,4,2,5,38,p,2,n,2,排放污染（m,3,/吨）,2,1,3,26,p,3,n,3,销售价格（万元/吨）,30,10,20,100,p,4,n,4,总产量（吨）,1,1,1,18,p,5,n,5,如果将利润、耗用原料等五个因素作为目标，确定各目标的理想值以及偏差变量如下：,如果目标大于理想值，正偏差变量大于0，小于理想值，负偏差变量大于0。因此，对第i个目标，有,如果各目标无优先级，要使所有的目标总偏差最小，即,目标规划的模型为：,对于每一个目标，正偏差变量和负偏差变量在系数矩阵中的列向量是两个相同的单位向量，是线性相关的，不可能同时出现在基矩阵中，因此，以上问题的任何一个基础可行解，同一个目标的正负偏差变量，不可能两个同时大于0。这一结果的实际意义也是很清楚的：任何一个目标，不可能既大于理想值，又小于理想值。,产品A,产品B,产品C,目标的,理想值,正偏差,变量,负偏差,变量,产量（吨）,0,10,0,RHS,p,i,n,i,达 到 的 目 标 值,利润（万元）,40,77,0,37,耗用原料（吨）,30,38,0,18,排放污染（m,3,）,10,26,0,16,销售价格（万元）,100,100,0,0,总产量（吨）,10,18,0,8,用单纯形法，得到目标规划的最优解、各目标的值以及偏差变量的值,最优解,目标值,偏差变量,目标规划的特点,可以求解多目标问题。克服了线性规划只能求解单目标的缺点。,用目标（Goal）的概念取代了线性规划中的“约束条件”，用偏离各目标的总偏差最小取代了线性规划中的目标函数，消除了线性规划中目标函数和约束条件的对立。,各目标值既可以正偏差，也可以负偏差，克服了线性规划约束条件的刚性。,目标规划总是有可行解的。克服了线性规划无解的问题。,目标有优先级的目标规划,在上面的例子中，利润、耗用原料、排放污染、销售额、总产量等五个目标是一视同仁的，最优解是使偏离五个目标的总偏差之和最小。在实际问题中，这些目标往往是有轻重缓急的。,产品A,产品B,产品C,目标的,理想值,正偏差,变量,负偏差,变量,产量（吨）,0,10,0,RHS,p,i,n,i,达 到 的 目 标 值,利润（万元）,40,77,0,37,耗用原料（吨）,30,38,0,18,排放污染（m,3,）,10,26,0,16,销售价格（万元）,100,100,0,0,总产量（吨）,10,18,0,8,确定五个目标的优先级Pi（Pi=1，2，3，4，5），数字越小优先级越高,目 标,产品,A,产品,B,产品,C,优先级,Pi,目标的,理想值,正偏差,变量,负偏差,变量,利润（万元/吨）,9,4,1,1,77,p,1,n,1,耗用原料（吨/吨）,4,2,5,5,38,p,2,n,2,排放污染（m,3,/吨）,2,1,3,3,26,p,3,n,3,销售价格（万元/吨）,30,10,20,2,100,p,4,n,4,总产量（吨）,1,1,1,4,18,p,5,n,5,目标有优先级的目标规划解法有：,加权法,字典序法,目 标,产品A,产品B,产品C,优先级,权重,理想值,正偏差,负偏差,利润（万元/吨）,9,4,1,1,10000,77,p,1,n,1,耗用原料（吨/吨）,4,2,5,5,1,38,p,2,n,2,排放污染（m,3,/吨）,2,1,3,3,100,26,p,3,n,3,销售价格（万元/吨）,30,10,20,2,1000,100,p,4,n,4,总产量（吨）,1,1,1,4,10,18,p,5,n,5,目标具有优先级的目标规划解法加权法,产品A,产品B,产品C,理想值,正偏差,负偏差,产量（吨）,0,10,0,RHS,p,i,n,i,无 优 先 级,利润（万元）,40,77,0,37,耗用原料（吨）,30,38,0,18,排放污染（m,3,）,10,26,0,16,销售价格（万元）,100,100,0,0,总产量（吨）,10,18,0,8,产品A,产品B,产品C,理想值,正偏差,负偏差,产量（吨）,1,19.25,0,RHS,p,i,n,i,有 优 先 级,1,利润（万元）,77,77,0,0,5,耗用原料（吨）,38,38,0,0,3,排放污染（m,3,）,19.25,26,0,6.75,2,销售价格（万元）,192.5,100,92.5,0,4,总产量（吨）,19.25,18,1.25,0,字典序优化（Lexico-optimization）,字典序法的原则是：,首先不顾其它目标，对优先级最高的目标进行优化，得到使第一级目标最优的决策变量的值以及第一级目标函数的值；,然后在不使第一级目标变差的前提下，优化第二级目标；,用同样的原则，按优先级从高到低，依次优化各级目标，直至所有目标都优化完毕。,min(n,1,+p,1,)，(n,2,+p,2,)，(n,3,+p,3,)，(n,4,+p,4,),s.t.2x,1,+2x,2,+n,1,-p,1,=20优先级1,x,1,+x,2,+n,2,-p,2,=20 优先级2,x,1,+n,3,-p,3,=5 优先级3,x,2,+n,4,-p,4,=3 优先级4,x,1,，x,2,，n,1,，n,2,，n,3,，n,4,，p,1,，p,2,，p,3,，p,4,0,字典序优化的图解法,min(n,1,+p,1,),(n,2,+p,2,),(n,3,+p,3,),(n,4,+p,4,),s.t.2x,1,+2x,2,+n,1,-p,1,=16(1),x,1,+x,2,+n,2,-p,2,=4(2),x,1,+n,3,-p,3,=2(3),x,2,+n,4,-p,4,=3(4),x,1,，x,2,，n,i,，p,i,0,02468,8,6,4,2,x,1,x,2,2x,1,+2x,2,=16,x,1,+x,2,=4,x,1,=2,x,2,=3,p,1,n,1,p,2,n,2,p,3,n,3,p,4,n,4,第一优先级最优解,第二优先级最优解,第三优先级最优解,第四优先级最优解,min(n,1,+p,1,),(n,2,+p,2,),(n,3,+p,3,),(n,4,+p,4,),s.t.2x,1,+2x,2,+n,1,-p,1,=16优先级P1,x,1,+x,2,+n,2,-p,2,=4优先级P2,x,1,+n,3,-p,3,=2优先级P3,x,2,+n,4,-p,4,=3优先级P4,x,1,，x,2,，n,i,，p,i,0,具有目标优先级的目标规划单纯形表,3,2,4,16,0,0,0,0,RHS,-1,1,1,0,n,4,-1,1,0,1,n,3,-1,1,1,1,n,2,-1,1,2,2,n,1,-1,-1,P,4,-1,-1,P,3,-1,-1,P,2,-1,-1,P,1,p,4,n,4,p,3,n,3,p,2,n,2,p,1,n,1,x,2,x,1,3,2,4,16,3,2,4,16,RHS,-1,1,1,0,n,4,-1,1,0,1,n,3,-1,1,1,1,n,2,-1,1,2,2,n,1,-2,0,1,0,P,4,-2,0,0,1,P,3,-2,0,1,1,P,2,-2,0,2,2,P,1,p,4,n,4,p,3,n,3,p,2,n,2,p,1,n,1,x,2,x,1,消去基变量n,1,n,2,n,3,n,4,在目标函数中的系数,对第一优先级目标P,1,优化。x,1,进基，n,3,离基，1为主元。消去主元所在列的其它元素,3,2,2,12,3,0,2,12,RHS,-1,1,1,0,n,4,-1,1,0,1,x,1,1,-1,-1,1,1,0,n,2,2,-2,-1,1,2,0,n,1,-2,0,1,0,P,4,-1,-1,0,0,P,3,1,-1,-2,0,1,0,P,2,2,-2,-2,0,2,0,P,1,p,4,n,4,p,3,n,3,p,2,n,2,p,1,n,1,x,2,x,1,第一优先级目标P,1,未达到最优解。x,2,进基，n,2,离基，1为主元。消去主元所在列的其它元素,1,2,2,8,1,0,0,8,RHS,-1,1,-1,1,1,-1,0,0,n,4,-1,1,0,1,x,1,1,-1,-1,1,1,0,x,2,0,0,2,-2,-1,1,0,0,n,1,-2,0,-1,1,1,-1,0,0,P,4,-1,-1,0,0,P,3,0,0,-1,-1,0,0,P,2,0,0,2,-2,-2,0,0,0,P,1,p,4,n,4,p,3,n,3,p,2,n,2,p,1,n,1,x,2,x,1,第一优先级目标P,1,未达到最优解。p,2,进基，n,4,离基，1为主元。消去主元所在列的其它元素,1,2,3,6,0,0,1,6,RHS,-1,1,-1,1,1,-1,0,0,p,2,-1,1,0,1,x,1,-1,1,0,0,0,2,1,0,x,2,2,-2,2,-2,0,0,-1,1,0,0,n,1,-1,-1,0,0,0,0,0,0,P,4,-1,-1,0,0,P,3,-1,1,-1,1,0,-2,0,0,P,2,2,-2,2,-2,0,0,-2,0,0,0,P,1,p,4,n,4,p,3,n,3,p,2,n,2,p,1,n,1,x,2,x,1,第一优先级目标P,1,未达到最优解。p,3,进基，n,1,离基，2为主元。消去主元所在列的其它元素,4,5,3,3,0,3,4,0,RHS,0,0,0,0,1,-1,-1/2,1/2,0,0,p,2,1,-1,0,0,-1/2,1/2,0,1,x,1,-1,1,0,0,0,2,1,0,x,2,1,-1,1,-1,0,0,-1/2,1/2,0,0,p,3,-1,-1,0,0,0,0,0,0,P,4,1,-1,0,-2,-1/2,1/2,0,0,P,3,0,0,0,0,0,-2,-1/2,1/2,0,0,P,2,0,0,0,0,0,0,-1,-1,0,0,P,1,p,4,n,4,p,3,n,3,p,2,n,2,p,1,n,1,x,2,x,1,第一级目标P,1,已达到最优解。,对第二级目标优化。n,1,进基可以减小P,2,的值，但由于n,1,在P,1,中的检验数为负数，n,1,进基将使P,1,增加，n,1,不进基。第二级优化终止。,4,5,3,3,0,3,4,0,RHS,0,0,0,0,1,-1,-1/2,1/2,0,0,p,2,1,-1,0,0,-1/2,1/2,0,1,x,1,-1,1,0,0,0,2,1,0,x,2,1,-1,1,-1,0,0,-1/2,1/2,0,0,p,3,-1,-1,0,0,0,0,0,0,P,4,1,-1,0,-2,1/2,-1/2,0,0,P,3,0,0,0,0,0,-2,-1/2,1/2,0,0,P,2,0,0,0,0,0,0,-1,-1,0,0,P,1,