运筹学基础教程第二版PPT-(9)[122页]课件

1、运筹学基础教程（第二版）魏权龄 胡显佑 编著第5章 多目标规划*5.1多目标规划的一般形式和特点5.2什么是多目标规划的“最优解”-有效解5.3像 集*5.4 评价函数方法5.5福利最大化与多目标规划5.6福利经济学中的埃奇渥斯盒状图*5.7目标规划5.1多目标规划的一般形式和特点在前几章中讨论的规划问题都是单目标问题，也就是只通过一个性能指标的大小来衡量方案的好坏.然而，在实际生活中，确定一个问题的方案优劣，常常要考虑多个目标.例如，我们在制定生产计划时，既要求产量高，又要求质量好，还要求成本低.再如，在选择一个新工厂的厂址时，我们要考虑的有生产成本、运输费用、基建投资费用、国防条件、污染等

2、多种因素.特别是有些指标之间又往往不是那么协调，使得确定最优方案时决策者难以做出最后决断.例1（采购问题）设市场上有甲、乙、丙三种糖果，每斤的价格如表5-1所示：表5-1今要筹办一桩婚事，计划花掉（买糖果）的总钱数不得超过50元，总的糖果斤数不得少于12斤，甲种糖果的斤数不能少于7斤.问如何确定最佳的采购方案.对于该问题的约束条件是不难确定的.设x1,x2,x3分别为甲、乙、丙三种糖果的采购量.于是依题意，x1,x2,x3应满足条件当我们考虑以什么作为衡量“最佳方案”的标准时，会有以下几种目标：（1）花钱总数最小，即f1(x1, x2, x3)=3x1+2x2+x3min（2）买糖的总斤数量大

3、，即f2(x1, x2, x3)=x1+x2+x3max（3）甲种糖的斤数最大，即f3(x1, x2, x3)=x1max可见，该问题可以用多目标问题来描述.正像线性规划和非线性规划那样，我们可以假定每个目标都是以求最小值为目的.于是，多目标规划的一般形式可以写为：其中p=2，符号V-min表示对p个目标函数f1(x),f2(x),fp(x)求最小，以示区别于单目标时求最小.多目标规划有什么特点呢？可先看一下由图5-1给出的两个目标的例子.由图可以看出x1为单目标规划（即非线性规划）的最优解，但是它对于以f2(x)为目标的规划问题来说，却是最坏的可行解.另一方面，由图5-1也可看出x2是（P2

4、）的最优解，但是它对于问题（P1）来说却是最坏的可行解.这个例子说明多目标规划的目标之间可能不是一致的，甚至会是彼此矛盾的.我们再看一下图5-2及图5-3，其中图5-2是两个变量的例子，图5-3为单变量的例子.在这两个例子中，可行解 x 对两个目标来说都是最优解.我们称具有这样性质的 x 为绝对最优解，也即 x 对每个目标来说都是最优解.不难理解，多目标规划的绝对最优解往往是不存在的（例如图5-1）.图5-3多目标规划问题还有一个特点，即对于给定的两个方案（可行解），例如x1R,x2R,这两个方案谁优些、谁劣些，往往是不可比较的.实际上，对于x1来说，我们需要用p个目标值来衡量;对x2来说，也

5、同样需用p个目标值来衡量.比较x1与x2的优劣，则需要比较两个p维向量F1与F2.我们知道，两个向量往往是不能比较大小的.例如，这样两个向量就不能比较谁大谁小.总之，多目标规划问题中目标之间往往是不一致的，甚至是相互矛盾的；最理想的情况是：找到一个可行解，使其对每个目标都是最优的.但是，这样的可行解（即绝对最优解）往往是不存在的。最根本的问题是：可行解（即方案）之间用多个目标去判断优劣，由于是用多个目标值去比较，相当于比较两个向量的大小，而向量之间往往是不能进行比较的.5.2什么是多目标规划的最优解-有效解由以上的讨论可知，对多目标规划问题需要引进新的概念，在新概念之下定义多目标问题的解.为此

6、，引进一个符号“ “.设a与b为两个p维向量，即设向量a与向量b具有关系：a b这意味着向量a的每个分量都要小于或等于向量b的对应分量，并且a至少有一个分量要严格地小于向量b对应的分量.用数学符号表示，即有（1）对于i=1,2,p均有ai bi;（2）至少存在某i0（1 i0 p），有ai0bi0.现在，利用符号“ ”来考察方案 的优劣.若存在另一个方案 满足则方案 比方案 劣.这是因为方案 的p个目标值都不比方案 的对应目标值差（即对所有的i=1,2,p均有fi( ) fi( ) ）,并且至少有一个目标值要好（即至少存在某个i0，有fi0（ ）fi0 ( )）.此时，我们称 为劣解.显然，若

7、不存在 R，满足式（5.1），则方案 不为劣解，于是可得如下的定义.定义1 设 R，若不存在xR满足则称 为多目标规划问题（VP）的非劣解（或称有效解，也称Pareto解）.多目标规划（VP）的有效解全体记为R*pa.例2 求多目标规划的有效解集合R*pa，其中解：对问题（VP）可以画出图形，见图5-4.当0 x1时，由图形可知即也有因此，当0 x1时，x为劣解；当x3时，有即也有因此，当x3时，x为劣解；当1 x 3时，我们找不到一个 0，使得因此x为有效解，即R*pa=x1 x 3例3 求多目标规划的有效解集R*pa，其中解:对问题(VP)画出图形,见图5-5.当0 x1时，由图可知f1(

8、1)f1(x)f2(1)f2(x)即也有因此，当0 x1时，x为劣解；当1 x 2时，我们找不到一个 0，2，使得因此x为有效解，即R*pa=x1 x 2例4 考虑由图5-6给出的两个目标的问题，其中x=（x1,x2）T.从图中不难看出， R*pa，这是因为我们找不到另一个可行解，满足下面再给出一个比有效解更弱的、被称为弱有效解的定义.定义2 设 R，若不存在 R，满足则称 为多目标问题（VP）的弱有效解（或称弱Pareto解）.多目标问题（VP）的弱有效解全体记为R*wp.不难看出有 例5 考虑由图5-7给出的具有两个目标、一个变量的例子，xE1.不难看出，此时5.3像 集*对于多目标规划问

9、题，有别于单目标问题的是需要研究像集.像集的研究有助于找出（VP）的有效解集合和弱有效解集合(特别是对于两个目标的情况,即p=2);也会对处理多目标规划问题的办法给出几何解释;更会对像集的研究提供一些处理多目标问题的办法.记可以看出：若x0R，F0=F（x0），则F0F（R）；反之，若F0F（R），则至少存在某x0R，有F0=F（x0）.由此可以定义一个由R到F（R）的映象F：（在数学上，称满足上述性质的映象F是映上（或称满射）的，但不是一对一的）.我们称F（R）为多目标规划（VP）的像集.例6 考虑问题(n=1，p=2)其中f1(x)=(x-2)x,f2(x)=-x记f1=(x-2)x,f2

10、=-x求出像集，也就是需要求出当x0,2时，f1与f2之间的函数关系.当我们将x看做参数时，上式可看做以x为参数时的f1与f2之间的函数关系.由f2=-x，得出x=-f2,代入f1=(x-2)x，得到f1=f2(f2+2)并且由知并且多目标规划（VP）的几何图形及像集分别由图5-8和图5-9给出.对于像集F（R），也可以定义绝对最优点、有效点和弱有效点，在像空间中，我们考虑如下的多目标问题有如下的定义3和定义4.定义3 设F（R）.若不存在FF（R）有F ，则称为（ ）的有效点，（ ）的有效点的集合记为E*pa.定义4设F（R）.若不存在FF（R）有F ，则称为（ ）的弱有效点，（ ）的弱有效

11、点的集合记为E*wp.正如5.2讨论的那样，可以完全类似地证明如下的关系式成立：例7 设由图5-10可见现在用几个简单的例子说明在多目标问题中研究像集的目的.（）研究像集的目的之一（特别是对于两个目标的情况，即p=2）：能够找出（VP）的有效解集R*pa和弱有效解集R*wp.如果我们已经求得像集F（R），对于多目标问题（VP），找出有效点和弱有效点比较容易.从有效点和弱有效点出发，它们的原像（在R中映射到有效点和弱有效点的那些可行解的集合）即为（VP）的有效解和弱有效解.我们仍以本节的例1为例加以说明（图5-11和图5-12）.在图5-12中，像集F（R）为弧AC.因为在弧AB（不包括端点B）

12、上的任何一点F，向其左下方移动时，总可以在弧BC段上找到另外一点 F（R），有 F，因此弧AB（不包括端点B）上的点不是弱有效点，即F E*wp.再由E*paE*wp，知F E*pa.然而，在弧BC（包括端点B和C）上的任何一点 ，在其左下方都找不到像集F（R）中的点，因此BC段（包括端点B和C）为有效点（因此也为弱有效点）. 我们再观察一下弧BC的原像.由于（B和C在图5-11中）进而可知，在图5-11中的区间B，C的像是图5-12中的弧BC，即因此，是弧BC的原像，区间B，C正是（VP）的有效解集（正如图5-11所示）.例8 考虑线性多目标问题由图5-13，有而故像集见图5-14，在像空间

13、中，有效点为：AD和DC，类似于例6中的分析（见图5-11和图5-12），可知AD的原像AD和DC的原像DC为Pareto解.（）研究像集的目的之二：对一些处理多目标问题的办法给出几何解释.我们考虑下面具有两个目标的问题，xj（j=1，n）为第j种产品的数量，并且总投资额最小： 为成本总收益最大： 为收益以乘除法作为处理多目标问题的一种办法，是考虑利率最大为目的，即从像空间来看，对应的是其几何意义由图5-15所示，图中 为（P）的最优点， 的原像 ( 满足： R,F( ) = )为（P）的最优解.（）研究像集的目的之三（也是最主要的目的）：可以提供一些处理多目标问题的办法，我们以下例来说明.例

14、9 （“理想点法”）为了简单，我们只讨论两个目标的情况（更一般的情况详见下节）：令其中先考虑一种最理想的情况，如图5-16所示，此时F*F（R）并且满足记 F*=（f*1,f*2）T由于F*F（R），故存在x*R，有F(x*)=(f1(x*),f2(x*)T=F*并且对任意xR，记 F=（f1，f2）T=F（x）=（f1(x),f2(x)）T则 (f1,f2)TF（R）因此有 即对任意xR有F（x）F（x*）可见，x*R*ab，因此我们在像空间称F*为理想点(即（VP）的绝对最优解对应的点).一般来说，多目标规划（VP）的绝对最优解不一定存在，正如图5-17所示，F* F（R）.由图5-17可

15、以看出，像集F（R）中与理想点F*最近的点似乎是可取的，即求如下问题的解F：如图5-17所示.现在，借助上面的分析求出的原像.考虑规划问题这里，（P）与（ P ）的不同在于：在（ P ）中，令f1=f1(x)，f2=f2(x),并且将在（ P ）中变量F限制在F（R）中求最小，变为在（P）中变量x限制在R中求最小.问题（P）是一个非线性规划，它的几何解释如图5-18所示，有如下定理（证明略）.定理1 设像空间中的问题（P）的最优解为 ，其中并且 R,有与(P)相对应的非线性规划问题为：设其最优解为 ，并且 ，则如下结论成立：（） 为（P）的最优解；（） 为（ ）的最优解.5.4 评价函数方法在

16、本节中将对多目标规划问题给出一些处理的方法.这些方法都是基于某种评价意义，把多目标规划问题化为单目标规划问题去求解.这里只给出五种处理方法.（一）线性加权和方法事先我们对p个目标f1（x），f2(x),fp(x)的重要性，通过邀请一批对这个问题有经验、有专门研究的老手（如专家、教授、技术人员、干部、工人等）发表意见，最终确定出一组权系数并且满足令评价函数为：求规划问题的最优解 .可以证明：当10，20,p0时， 为（VP）的有效解，即 x R*pa（二）平方和加权法先对每一个目标估计一个尽量好的希望值，例如对于第i个目标fi(x)给出一个估计值f0i，它满足条件： 再对p个目标f1(x),f2

17、(x),fi(x),fp(x)给出一组权系数：1,2,i,，p其中令评价函数为：求非线性规划问题的最优解 .可以证明： 为（VP）的有效解，即 R*pa平方和加权法体现了通常所说的自报公议的原则.即让那些强调目标fi(x)重要者预先给出最优值 的一个尽可能好的估计f0i,然后，通过公议（例如请老手评议）给出一组表明各目标重要性的权系数1,2, p.（三）理想点法先求p个单目标规划的最优值，记这样，我们得到了一个点它是各目标的理想值的点，称为理想点（因为多目标规划的绝对最优解往往是不存在的，可见，F*只不过是理想值而已）.令评价函数为：其中而为欧氏模（距离），即求非线性规划问题的最优解 .可以证

18、明： 为（VP）的有效解，即 x R*pa（四）“min-max”法（“最小-最大”法）在对策论的研究中，选取最优策略的一种思想是在最不利的情况下选取最有利的策略，即所谓最小-最大的原则.借用这一思想，我们可得到评价函数再求规划问题的最优解 .这里， 是变量x的函数，当n=1时如图5-19所示.对于问题（P），可以用增加一个变量xn+1和p个约束条件的方法，将它化为一个等价的通常形式的数学规划：问题（P）和（P）之间的关系是：若 及 为（P）的最优解，则 为（P）的最优解；反之，若 x 为（P）的最优解，令则 及 为（P）的最优解（证明是初等的）.五）乘除法考虑具有p个目标的多目标问题，其中x

19、R,并且 在上述p个目标当中，有一些目标希望越小越好，另一些目标希望越大越好.不失一般，设 要求越小越好；而目标要求越大越好.此时令评价函数为：再求规划问题的最优解至此，我们给出了五种评价函数方法.所谓评价函数方法，实际上是根据决策者的偏好去确定函数h(F)的形式，然后用复合函数的办法，将多目标规划中的目标函数F（x）=（f1(x),f2(x),fp(x)）T代入h(F)中，化为由单一目标函数 h(F(x)=h(f1(x),f2(x),fp(x)来评价和求最优解 .由5.2我们知道，那些非有效解显然是不可取的（非弱有效解就更不可取了），因为总可以找到另一个可行解，其每个目标都不会比原来的差，并

20、且至少有一个目标明显更好（对于非弱有效解来说，我们会找到另一个可行解，其每个目标都要比原来的好）.现在的问题是：用上述一些评价函数得到的规划问题的最优解 ，是否可保证是多目标的有效解（或至少保证为弱有效解）.下面将指出，当评价函数h（F）具有某种“单调性”时，可以保证规划问题的最优解 为有效解或弱有效解.为此，先给出两个定义，再由定理2和定理3给出所希望的结果.定义5 设h(F)是定义在 上的函数，若对于任意满足F1F2的F1F（R），F2F（R），均有则称h(F)为单调增函数.定义6 设h(F)是定义在 上的函数，若对于任意满足F1F2的F1F（R），F2F（R），均有则称h(F)为严格单调

21、增函数.由定义5和定义6可以看出：严格单调增函数也是单调增函数.有如下定理.定理2 若h(F)是定义在 上的严格单调增函数， 为规划问题的最优解，则证：用反证法证明之，若 ,则存在 ,有 . , ,以及h(F)为严格单调增函数，故有此与 为（P）的最优解相矛盾.因此必有 .得证.定理3 若h(F)是定义在 上的单调增函数， 为规划问题的最优解，则 .证：证明方法与定理2雷同，不另证.得证.根据定理2和定理3，可以检验本节给出的一些评价函数方法得到的 是否为有效解或弱有效解，也就是只需验证相应的评价函数是否为严格单调增函数或单调增函数.本节给出的一些评价函数的严格单调增函数性质或单调增函数性质都

22、可以用初等方法证明.我们不一一给出验证，只给出相应的结论.（一）线性加权和方法评价函数为：（1）当=(1,2,p)T0时，h(F)为严格单调增函数，故 R*pa.（2）当=(1,2,p)T0，且0时，h(F)为单调增函数，故 R*wp.(二)平方和加权法评价函数为:（1）当=(1,2,p)T0时，h(F)为严格单调增函数，故 R*pa.（2）当=(1,2,p)T0，且0时，h(F)为单调增函数，故 R*wp.(三)理想点法评价函数为严格单调增函数，故 R*pa.(四)“min-max”法（“最小-最大”法）当评价函数为(这里 )此时h(F)都为单调增函数，故 R*wp.（五）乘除法评价函数为：

23、此时可证为（f1,f2,fs）及（fs+1,fp）的严格增-减函数，即若则有可以类似于定理2的证明，知规划问题的最优解 为下面多目标问题的有效解(即 R*pa)在结束本节的讨论之前,我们以两个目标的情况为例(p=2的情况),简单地介绍一下如何在评价函数中有目的地调节参数,以求得更加令人满意的解.这种通过调节参数、重复计算求解的过程，有人称其为对话式方法（或交互型方法）.然而，我们在这里给出的方法只不过是最简单的对话式方法而已.在处理多目标的过程中，可认为有分析者和决策者.分析者的任务是向决策者提供有效解（非有效解显然是不可取的）；决策者的任务是向分析者提出对方案的偏好信息，以便使分析者提供令决

24、策者更满意的有效解.当然，最终决定采用哪个方案，要由决策者来决定.他们之间的关系由图5-20给出.考虑两个目标的规划问题（p=2）线性加权和法先给定一组权求解规划问题设其最优解为x1，相应的目标函数值为： f1(x1) f2(x1)如果“决策者”认为第一个目标函数值f1(x1)还不够理想，即希望求一新的解，其相应的f1(x)的值要比f1(x1)好，那么“分析者”可以增大对应于目标f1(x)的权系数，令相应的有其中再求规划问题（此工作也由分析者借用计算机完成）的最优解，设其为x2.可以证明这个性质说明，当我们增大对应于目标f1(x)的权系数时，可能会改进f1(x)的值，但是，对另一个目标f2(x

25、)来说则需要做些让步.如果决策者对解x2还不满（或认为f1(x2)偏大，或认为f2(x2)过小)，则可用类似的原则改变相应的权系数，而后重新求解.5.5福利最大化与多目标规划西方经济学可以分为实证经济学（positive economics）和规范经济学（normative economics）.实证经济学回答“是什么”的问题；规范经济学回答应当是什么的问题.可见，规范经济学的研究将涉及道德规范和价值判断.福利经济学是经济学的一个重要分支，它是研究整个经济的资源配置与社会成员福利的关系，于是不可避免地要涉及应当是什么，即价值判断.假设有p个社会成员，我们称为社会经济人，每个社会经济人都有一个表

26、明其偏好程度的效用函数（其数值越大，表示满意程度越高），设为u1(x),u2(x),up(x)其中，x=(x1,x2,xn)TR，R为“政策集”，xR称为一种“政策”，例如工资分配政策、税收政策等；R表示对政策的一种“规定”.于是可以用如下的多目标规划问题描述（由于效用值越大，满意程度越高，故相应的多目标问题与前几节不同之处是取最大，即V-max）设 R，若存在xR，有称对“政策” 存在Pareto改进.存在Pareto改进，是说存在另一种政策x，它可以使p个“社会经济人”中的部分人境况好转，而又不损害其他人的利益.显然，存在Pareto改进是何乐而不为的事.现在，若不存在xR,使得在经济学中

27、，称 为Pareto最优，即多目标问题中的Pareto解.可见，Pareto最优是不会存在Pareto改进的一种状态.设 R，若存在xR，使得称政策 存在弱Pareto改进.这就是说存在另一种政策x，它可以使所有的社会经济人的境况都要好，这是皆大欢喜的事.现在，若不存xR，使得在经济学中，称 为弱Pareto最优，即多目标问题中的弱Pareto解，可见，弱Pareto最优是不会存在弱Pareto改进的一种状态.当xR，并且记在福利经济学中，称集合为福利空间中的效用可能性集合（即多目标问题中的像集）.可以证明：当R为凸集，Uj（x）（j=1，p）为凹函数时，集合为凸集.例10 企业最优工资比例分

28、配问题某企业的工资分配针对两种人群：一般员工和管理层员工，工资的分配比例分别为x1和x2，其效用函数分别为：效用函数u1(x1)，u2（x2）表示董事会对两类人员获得工资比例分别为x1和x2时的认可程度的一种描述，u1(x1)=x1，表明董事会认为对一般员工来说，所占份额（工资比例）越大越好；u2(x2)=x2(1-x2)，表明董事会认为对管理层员工来说，按有关规定，所占份额太大或太小都不好.见图5-21和图5-22.“政策集”为：如果写为多目标问题为：以下求效用可能性集合.由x2=1-x1得u2=x2(1-x2)=(1-x1)x1=(1-u1)(u1)故（见图5-23和图5-24）福利经济学

29、家关心的另一个问题是研究如何由“社会经济人”的效用函数Ui（x）（i=1,p）得出“社会福利函数”，进而研究福利最大化问题.社会福利函数是各个社会经济人的效用函数的函数，即W(u1(x),u2(x),up(x)实际上，它就是多目标问题中的评价函数.福利最大化问题为：一般要求W(u1,u2,up)是变量U=（u1,u2,up）的严格单调增函数（或增函数），这将保证（P）的最优解 为Pareto最优（或弱Pareto最优），见上一节的定理2和定理3.例11 福利最大化的配置问题设有p个消费者，他们分配m种商品，已知m种商品的数量分别为a1,a2，am.令xij（i=1,m;j=1,p）为第j个消费

30、者获有第i种商品的数量，这样，求社会福利最大化的问题为：其中，xj=（x1j,x2j,xmj）T，j=1，p.当具有两个消费者（p=2）、一种商品（m=1）时，（P）化为式中，x1为消费者1的商品数量；x2为消费者2的商品数量.在福利空间中，当p=2时，福利最大化问题的几何解释是：福利空间中相应于（P）的问题为：在图5-25中，U（R）为效用可能性集合，W(u1,u2)为常数，为福利曲线（即相应于W（u1,u2）的等高线）， =（1，2）T为（P）的最优解.图5-25不难证明，（P）的最优解（即社会福利最大化的配置）为：通常，社会福利函数可取做各社会经济人的效用函数总和（有时被称为古典效用主义

31、或边沁福利函数）上述社会福利函数的一个推广，是加权的效用和福利函数其中 ,被称为权重，表示每个“社会经济人”的效用在整个社会福利中的重要性.可以看出，加权的效用福利函数，即为多目标问题的线性加权和评价函数.由于函数为严格单调增函数，故（P）的最优解为Pareto最优.当p=2时，在福利空间中，（P）为类似于图5-25，此时相应的几何图形如图5-26所示.图5-26 在应用社会福利函数寻求福利最大化时，可取另一种有意义的最小-最大社会福利函数（有时也被称为罗尔斯社会福利函数）这一社会福利函数表明社会福利由境况最差的“社会经济人”的福利决定；相应的福利最大化问题（P）是在境况最差的福利函数值中寻求

32、最大化，即min-max .于是有由于函数为单调增函数，故（P）的最优解为弱Pareto最优（见上一节的定理3）.5.6福利经济学中的埃奇渥斯盒状图*本节中，我们给出福利经济学中论述Pareto最优的一个范例-埃奇渥斯盒状图.福利经济学中，用埃奇渥斯盒状图研究两种既定数量的产品在两个消费者之间的分配问题，然后推广到一般，给出交换的Pareto最优条件.同样的方法可以研究两种既定的生产要素（例如劳动、资金）在两个生产者之间的分配情况，即所谓生产的Pareto最优条件.交换的Pareto最优条件和生产的Pareto最优条件的研究方法几乎是平行的.以下，我们仅以两人两种商品的交换为背景讨论交换过程中

33、的Pareto最优条件.假设有两个人，他们都拥有一定数量的两种商品，如表5-2所示.其中aij=第j个人拥有第i种商品的数量，i=1，2；j=1，2 ai=ai1+ai2=第i种商品的总量，i=1,2两个商品交换者的商品交换必须在双方都有利或者至少不被损害的情况下才能够进行.这就需要有一个体现商品交换者对于两种不同数量的商品，表明自己满足程度的数与其对应.这里用效用函数表示不同的商品量对商品交换者来说的满足程度.令U1（x1,x2）,U2(x1,x2)分别为商品交换者1和商品交换者2的效用函数，其中x1表示第一种商品的数量，x2表示第二种商品的数量.如果从多目标规划的角度看，显然有如下的多目标

34、问题其中由U1(x11,x21)和U2（x12,x22）可得到它们的等效用曲线（即f1(x11,x21)和f2(x12,x22)的等高线），由图5-27和图5-28给出.图中，愈偏离原点O1（或O2）的等效用曲线效用值愈大.埃奇渥斯盒状图是将上述两个图画在一个盒子当中，其中盒子长为a11+a12,盒子宽为a21+a22（即两个商品交换者具有商品1的总和a1为盒子的长；具有商品2的总和a2为盒子的宽）.于是，盒子中的每一个点，都表示商品交换者1和2拥有两种商品的数量，而该点所在的等效用线的数值分别表示两个商品交换者的效用函数值.图5-29中的点W表示商品交换者所具有的商品1和商品2的数量.Par

35、eto给出了以下原则进行交换（即Pareto最优条件）：如果每个人都不能在不损害他人利益的前提下增加自己的利益，那么就认为他们已处于最优状态.由图5-29可知，当前的状态（即点W）并不是最优状态.实际上，图5-29中斜线构成的梭形区域中的任意一个点，都可能使商品交换者的效用值增大，也就是比当前的状态有所改进.我们称该梭形区域为互利区，即多目标规划（VP）的约束集合确定的区域.下面我们讨论Pareto的有效配置问题，即按照交换的Pareto最优条件，确定有效配置的点.当商品交换者之一确定了他的效用值c后，我们去确定另一个商品交换者所可能达到的最大的效用值的点，即如下的单目标规划所描述的：由上述单

36、目标问题确定的点如图5-30所示，其中点M即为所求，称点M为契约点.在埃奇渥斯盒子中，所有可能的契约点构成了一条曲线O1O2，称为契约曲线.可以看出，契约曲线上的任意一个点都满足交换的Pareto最优条件.由5.2知，契约曲线上的任意一个点都是多目标规划（VP）的Pareto解.在上述的两个人、两种商品的交换问题中，当两个商品交换者拥有的商品数量确定之后，就在埃奇渥斯盒子中对应了一个点W，以及相应的梭形区域（见图5-30）.5.7目标规划在这一节中将讨论另一类多目标问题-（线性）目标规划.先看一个例子（请注意目标函数的形式）.例12 某家具厂只生产两种产品：桌子和椅子.售出一张桌子的利润为3元

37、，售出一把椅子的利润为4元.又知桌子和椅子需经过两个加工工段：装配工段和精整工段，其中每个桌子和椅子所需工时，以及各工段的生产能力由表5-3给出.如果要求利润最大，这是在第2章中讨论过的线性规划问题的模型，不难写出，有由图解法得到最优解（见图5-31）：相应的最优值为26.现在根据三种不同要求建立三种模型.（1）要求一天的利润达到20元，两种产品各应生产多少？除了假设桌子的生产数量为x1，椅子的生产数量为x2之外，还设d-=利润不足20元时的差额值（简称为负偏差）d+=利润超过20元时的超出值（简称为正偏差）建立目标规划模型为：在这个问题中的目标函数为：其原因是负偏差及正偏差都为非负变量，因此

38、，目标值（d-+d+）0，如果能求得最优解使得目标值min （d-+d+）=0，这只有正偏差及负偏差都为0，于是就能实现我们希望利润达到20元的目的.（2）要求一天内的利润值不少于20元（允许超过20元，但尽可能不要少于20元），问两种产品应各生产多少？我们可以建立这样的目标规划模型：其中x1,x2,d-,d+的意义与问题（P1）相同.在问题(P2)中的目标函数为：min d-其原因是变量（负偏差）d-为非负变量，我们希望目标的最优值min d-=0,因为若（P2）的最优解 ， ， ， 中的 =0,则因为正偏差 ，故利润值为：即利润值不少于目的值20元.（3）要求一天的利润不少于23元，装配车

39、间的总工时不超过28工时（允许少于28个工时，但尽可能不要超过28个工时），问两种产品应各生产多少？建立的目标规划模型为：其中x1,x2的意义与前面的几个问题相同，即x1为生产的桌子数，x2为生产的椅子数，但是d-，d+与前面的问题都不同，在这里d-=装配车间工时不足28时的差额值（负偏差）d+=装配车间工时超过28时的超出值（正偏差）问题（P3）的目标函数为：min d+其原因是变量d+（正偏差）为非负变量，我们希望目标的最优值min d+=0，因为若（P2）的最优解 ， ， , ，有 =0，则因为负偏差 ，故得到装配车间的工时为：即工作时间少于28.从上面的例子可以看出目标规划的一个特点，

40、就是把原来的目标函数（性能指标）通过引进正偏差与负偏差转化为约束条件，而用正偏差及负偏差的不同组合形式作为目标规划的目标函数.一般地，假设有一个性能指标为：它的一个给定的目的值为f0，则令d-=指标f(x)不足f0时的差额值(负偏差)， d+=指标f(x)超过f0时的超出值（正偏差）， 有如下的约束条件：目标规划可以有以下五种目标函数的形式：1.要求性能指标f(x)尽量达到目的值f0(即不足f0不好，超过f0也不好)，此时目标规划的目标为：min (d-+d+)2.要求性能指标f(x)的值不少于目的值f0(即允许超过f0，但尽可能不要少于f0)，此时目标规划的目标为：min d-3.要求性能指

41、标f(x)的值不超过目的值f0（即允许少于f0，但尽可能不要超过f0），此时目标规划的目标为：min d+以下两种情况4与5是我们前面几章中研究过的普通规划问题的提法，这里只不过是用目标规划的语言做了统一处理.4.要求性能指标f(x)的值越大越好，此时目标规划的目标为：min （d-d+）（实际上，由f(x)=f0-(d-d+)可知,要求max f(x)等价于min(d-d+）.5.要求性能指标f(x)的值越小越好，此时目标规划的目标为：min (d+-d-)（实际上，由f(x)=f0+(d+-d-)可知,要求min f(x)等价于min (d+-d-)）.以上是为了便于说明目标规划的性质，所以暂时借用单个目标来讨论.现在根据对单个目标的目标规划的五种形式来讨论多目标的情况.例13 在例12中，有如下两个要求：第一，要求一天内的利润达到20元；第二，在利润尽可能达到20元的前提下，装配车间剩余的工时越多越好（即在完