系统工程---多目标决策

多目标决策第十六章制作人赵小君2002年3月22日第一节引言在生产、经济、科学和工程活动中经常需要对多个目标（指标）的方案、计划、设计进行好坏的判断，例如设计一个导弹，既要其射程远，又要耗燃料少，还要命中率高等；又如选择新厂址，除了要考虑运费、造价燃料供应费等经济指标外，还要考虑对环境的污染等社会因素。只有对各种因素的指标进行综合衡量后，才能作出合理的决策。例由n种成分组成一个橡胶配方，可用表示。对于每一个配方要同时考察几个指标，如强度，硬度，伸长率，变形度等。假定有m个指标。它们都与配方方案有关，它们与的关系为,,,。当m很多时，要比较两方案的优劣时，就往往很难下决断了。于是有人把这问题用数学规划来处理。先以某指标作为主要指标，如以强度为主要指标，并且越大越好。而其它指标只要落在一定规格内就可以。这就把这问题nxxx,,,21Tnxxxx,,,211f2f3f4fxxxf1xf2xfm这里A表示对本身的一个限制，表示第i个指标的上、下限。化为求xfRx1maxAxmifxfxfxRiii,,,2,|'x',iiff第二节基本概念在考虑单目标最优化问题时，只要比较任意两个解对应的目标函数值后，就能确定谁优谁劣（目标值相等时除外）。在多目标的情况下就不能这样比较了。例如，有两个目标都有要求实现最大化，这样的决策问题，若能列出十个方案，各方案能实现的不同的目标值如图所示。由图可见，对于第一个目标来说方案1优于2；而对于第二个目标方案则方案2优于1。因此无法确定谁优谁劣；但是它们都比方案3，5劣。方案3，5之间又无法比较。在图中10个方案，除方案3、4、5外，其它方案都比它们中的某一个劣。因而称1、2、6、7、8、9、10为劣解，而3、4、5之间又无法比较谁优谁劣；但又不存在一个比它们中任一个还好的方案，故称此三个方案为非劣解（或称为有效解）。假定m个目标，，，。同时要考察，并要求都越大越好。在不考虑其它目标时，记第I个目标的最优值为xf1xf2xfmxffiRximax)0(相应的最优解记为，；其中R是解的约束集合。ixmi,,2,10|xgxRTlxgxgxg,,1当这此都相同时，就以这共同解作为多目标的共同最优解。一般不会全相同，例如时，这两个解就难比优劣，但是它们一定都是非劣解。为了与单目标最优化的记号有所区别，今后用ix21xxxFVRxmaxxFVxgmax0)(或表示在约束集合R内求多目标问题的最优（亦称求向量最优）；其中若各目标都要求越小越好，就用表示。为了简易起见，本节一般只考虑n维欧氏空间，即实际上当是最优解时，即表示有当是非劣解时，即不存在有TmxfxfxF,,1xFVRxminnE.,,,,,21mnTnExFERRxxxx0x,Rx*0xFxF0x,Rx0xFxF以后用“”表示，但，即至少有一个分量，有“”才成立，即严格大于。相应的在目标函数空间中称为非劣点或有效点。有的还进一步引入弱非劣解，即当是弱非劣解，基不存在有0xFxF0xFxF0xF0x,Rx0xFxF为直观起见，举几个数值例子。1例213210,2221xxxxxfxxxf设xFVRRxmax,2,0求解先对单个目标分别求出其最优解，显然第一个目标的最优解。这时11xxfxffRx11)0(1max1第二个目标的最优解是，这时12xxfxffRx22)0(2max1因为121xx故取作为这多目标问1*x题的最优解。下面用变量空间和目标函数空间分别来描述各种情况，见图16-2。图中两个和解彼此无法比较，但都劣于。1*x图16-2ff*xf1f2f例2求设,2,0,2,2221RxfxxxfxFVRxmax解容易求得这时多目标问题没有共同最优解。从图16-3可见，两个解无法比较，但是容易找到，仍无法比较优劣，但还可找到。解却不存在可以比它优，这时为非劣解。本例中时都是非劣解。,2,121xx和优比'与'优比''2,1x2f2f1f1ff'ff'图16-3例3,2,0,15361281,22221Rxxxfxxxf设求xFVRxmax解易求得，这时多目标问题无最优解，而都是非劣解，见图16-4。,5.1,121xx5.1,1x图`16-42f2f1f1f例4,2,23212211xxxfxxxf设00010201832:212121xxxxxxR求xFVRxmax解易求得因而多目标问题最优解即图16-5所示的之间无法比较，但都劣于A。,6,0,6,021xx和图`16-51x2x2f1f'A'B'C在单目标时任何两个解都可以比较其优劣，因此是完全有序的。可是在多目标时任何两个解不一定都可以比出其优劣的，因此只能是半有序的。假定所有x是属于全空间∑中某一个约束集合R，即,在∑上对任一个解x可以定义一个半序：，（ab表示a优于b），可把∑分成三个子集：1）所有比x优的解集合；2）所有比x劣或相等的解集合；3）所有与x无法比较的解集合。显然按照这些子集的划分，Zadeh给出“非劣”和“最优”的定义。Rxxx~定义1解叫作在R内“非劣”，如果。定义2解叫作在R内最优，如果。推论：若是最优解，则必为非劣解。反之不然。Rx0Rx0)(0xR0x第三节化多为少的方法要求若干目标同时都实现最优往往是很难的。经常是有所失才能有所得，那么问题的失得在何时最好。各种不同的思路可能引出各种合理处理得失的方法。以下介绍化多为少的方法。3.1主要目标法解决主要问题，并适当兼顾其它要求。1.优选法。在实际问题中通过分析讨论，抓住其中一两个主要目标，让它们尽可能地好，而其它指标只要满足一定要求即可。通过若干次实验以达到最佳。2.数学规划法设有m个目标，，，要考察，其中一两个方案变量（约束集合），若以某目标为主要目标，如要求实现最优（最大），而对其它目标只滞一定规格要求即可，如xf1xf2xfm,Rxxf1mifxffiii,,2''iiff或其中当就变成单边限制，这样问题就可化成下述非线性规划问题：RRmifxffxRxfiii,,,2,|max''1Rx3.2线性加权和法若有m个目标，分别给以权系数（i=1,2,,m),然后作新的目标函数（也称效用函数）xfii这种方法的难点是如何找到合理的权系数，使多个目标用同一尺度统一起来。同时的找到的最优解又是向量极值的好的非劣解。在多目标最优化问题中不论用何方法，至少应找到一个非劣解（或近似非劣解）。其次，因非劣解可能有很多，如何从中挑出较好的解，这个解有时就要用到另一个目标。下面介绍几种选择特权系数的方法。miiixfxU1（1）--法先以两个目标为例，假设一个目标是要求劳动量消耗为最小，另一个目标是收益为最高。它们都是线性函数，都以元为单位。R也为线性约束，即xf1xf2bAxxR|A为矩阵，b为列向量。作为新目标函数由下述方程组来确定和其中211122xfxfxU0201*2*1*101120201*2*1*202111121*12220212*2111011022*111*22011:,0,max,min--ffffffcffffffcccxffxfxffxffxfxffcffcffRxRx这方程组可解得可为任意的常数kffffffffffffffffffffffff01*1*2022101*1*20201*1201*1*202*202101*1*2020201*2*1121c,1易见从而有即可得到若规定212,11122Rx01*1*2021*202201*1112221k,)()(maxmax,U,一簇平行线其斜率为取不同数时相当则若作目标值空间可表示为当要求实现最大时作出的新目标函数为由这样定义的xUffxfxfxUffffxfffxfffxfxfxRx请注意点与的联线的斜率为与新目标函数的平行经簇的斜率是一致的，见图16-7。U取最大值时，正好是此平行线簇中与c点相交。01*1202011,ffMffM01*1*202ffffxU1M2MUUmax01f2f01f*1f02f*2f图16-7对于有m个目标，，的情况，不妨设其中，，要最小化，而，，要求最大化，这时可构成下述新目标函数。xf1xfmxf1xfkxfk1xfmmkixfxfMaxffkixfxfMinffmicffxfxfMaxxUiiiRxiiiiiiRxiiikjmkjijjijjjmkjjjkjjjRx,,1,,,1,,,1,Max0011111Rx其中满足下方程组其中mjixffijij,,2,1,,例1设有,4211Minxxxf,23212Maxxxxf,,0,,3,42|2212121xxxxxxxxR试用--法求解。解先分别对求得其最优解，它们是xf1xf272,100,0022222011111fxfMaxfxffxfMinfxfRxRx60:21*112*2xffxff然后求出13153,051013113613761313767721212211201*1*202*2021UxUMaxxxxfxfxfxfxUffffffRx易求得由此可得(2)当m个目标都要求实现最大时，可用下述加权和效用函数，即法xfMaxffxfxUiRxiiiimiii001,1取其中3.3平均和加权法设有m个规定值要求m个函数分别与规定的值相差尽量小，若对其中不同值的相差又可不完全一样，即有的要求重一些，有的轻一些，这时可采用下述评判函数：.,12*给出可按要求相差程度分别其中要求iRxmiiiixUMinfxfxU,,,**1mff,,,1xfxfm3.4理想点法有m个目标每个目标分别有其最优值,,,1xfxfmmixfxfMaxfiiiRxi,,2,1,0若所有都相同，设为。则令时，对每个目标都能达到其各自的最优点。可惜一般做不到，因此对向量函数mixi,,2,10x0xx.,,,),,(00101即一般达不到它只是一个理想点向量来说TmTmffFxfxfxF理想点法，其中心思想是定义了一定的模，在这个模意义下找一个点尽量接近理想点，即让模对于不同的模，可以找到不同意义下的最优点，这个模也可看作评判函数，一般定义的p-模是：00FxFMinFxF