多目标规划.

第八章多目标规划概述什么是多目标规划问题在前面所述的最优化问题，无论是线性规划、整数规划还是非线性规划，其目标函数都只有一个。但在实际问题中，衡量一个设计方案的好坏往往不止一个标准，常常要考虑多个目标。例如研究生产过程时，人们既要提高生产效率，同时还要考虑产品质量，又要考虑成本以降低生产费用，可能还希望生产过程中的环保问题，即废渣、废水、废气造成的污染小。在设计导弹的过程中，既要射程远，又要燃料省，还要重量轻且打击精度高。在进行投资决策时，既希望回报高的同时又希望降低投资风险，如此等等。这就向我们提出了一个多指标最优化问题。我们把在这样的背景下建立起来的最优化称之为多目标规划问题。多目标规划问题的发展多目标规划法（GoalProgramming，简称GP）也是最优化理论和方法中的一个重要分支，它是在线性规划的基础上，为解决多目标决策问题而发展起来的一种数学方法。其概念和数学模型是由A.Charnes和W.W.Cooper在1961年提出的，经过Ijiri,Sang.M.Lee等人的改进，并逐步发展和成熟，它在经济管理与规划、人力资源管理、政府管理、大型工程的最优化等重要问题上都有广泛的应用。多目标规划问题的典型实例例1木梁设计问题用直径为1（单位长）的圆木制成截面为矩形的梁。为使重量最轻面强度最大，问截面的宽和高应取何尺寸？假设矩形截面的宽和高分别为1x和2x，那么根据几何知识可得：22121xx且此时木梁的截面面积为12xx。同时根据材料力学的知识，木梁的强度取决于截面矩量21216xx，故若要使得重量最轻，实际上目标即为横截面积最小，又要强度最大，故目标为截面矩量最大，于是容易列出如下数学模型：1122212221212min1max61,0fxxfxxxxxxxx多目标规划问题的典型实例例2工厂采购问题某工厂需要采购某种生产原料，该原料市场上有A和B两种，单价分别为2元/kg和1.5元/kg。现要求所花的总费用不超过300元，购得的原料总重量不少于120kg，其中A原料不得少于60kg。间如何确定最佳采购方案，花最少的钱，采购最多数量的原料。设A、B两种原料分别采购1x、2xkg，那么总的花费为：11221.5fxxx购得的原料总量为：212fxxx那么我们求解的目标即是使得花最少的钱买最多的原料，即最小化1fx的同时极大化2fx。多目标规划问题的典型实例同时要满足所花的总费用不得超过300元，原料的总重量不得少于120kg，A原料不得少于60kg，于是得到约束条件如下：12120xx1221.5300xx160x又考虑到购买的数量必须要满足非负的条件，由于对1x已经有相应的约束条件，故只需添加对2x的非负约束即可。综合以上分析，得到最优化数学模型如下：112212121212min21.5max12021.5300600fxxfxxxxxxxxxx多目标规划问题的典型实例例3生产计划问题某工厂生产A1、A2和A3三种产品以满足市场的需要，该厂每周生产的时间为40h，且规定每周的能耗都不得超过20t标准煤，其数据表如表8-1所示。现在的问题时，每周生产三种产品各多少小时，才能使得该厂的利润最多，而能源消耗最少？产品生产销售数据表产品生产效率（m/h）利润（元/m）最大销量（m/周）能耗（t/1000m）A12050070024A22540080026A31560050028多目标规划问题的典型实例假设该厂每周生产三种产品的小时数分别为123,,xxx，则我们根据各种产品的单位利润得到其总利润1fx为：1123500400600fxxxx根据各个产品的生产效率，可得生产A1、A2和A3的生产数量分别为：12312320,25,15AAAqxqxqx故在生产过程中产生的能耗可以表达为：33321231232410202610252810150.480.650.42fxxxxxxx那么根据最优化问题的目标，我们需要使得才利润最多且能耗最少，即在极大化1fx的同时极小化2fx。多目标规划问题的典型实例再由约束条件，该厂每周的生产时间为40h，故：12340xxx且需要满足能耗不得超过20t标准煤：1230.480.650.4220xxx上面是对生产过程的约束，再考虑销售过程，由于数据表中给出了三种产品每周的最大销量，故我们必须限制生产数量小于最大销量才能使得成本最低，即满足下述约束条件：12312320700;25800;15500AAAqxqxqx同时考虑到生产时间的非负性，总结得到该问题的数学模型为：11232123123123123123max500400600min0.480.650.42s.t.400.480.650.4220207002580015500,,0fxxxfxxxxxxxxxxxxxxxxx多目标规划问题的数学模型上述问题可以归结为标准形式：V-mins.t.0(1,2,...,)0(1,2,...,)iigimhilFxxx其中：12Tnxxxx；12,2pfffpFxxxx令|0,1,2,...,iRgimxx，则称R为问题的可行域，V-minFx指的是对向量形式的p个目标函数求最小，且目标函数Fx和约束函数igx、ihx可以是线性函数也可以是非线性函数。多目标规划问题域线性规划和非线性规划问题的主要区别就在于，它所追求的目标不止一个，而是多个。多目标规划问题的数学模型目标规范化由于许多实际问题中，各个目标的量纲一般都是不同的，所以有必要将每个目标事先进行规范化，例如，对第j个带量纲的目标jFx，我们可令：jjjFfFxx其中：minjjxRFFx|0,1,2,...,;0,1,2,...,iiRgimhilxxx这样jfx就是规范化的目标了，在以后的叙述中，不妨假设多目标规划问题中的目标均已规范化。多目标规划的解集直观理解对单目标规划来说，给定任意两个可行解12,Rxx，通过比较它们的目标函数值12,ffxx就可以确定哪个更优。但对于多目标规划而言，给定任意两个可行解12,Rxx，因为目标函数12,FxFx均为向量，故可能不存在12,FxFx之间的大小关系，既无大于等于关系，也无小于等于关系。例如我们首先直观的看一个多目标规划的图解实例。假设问题的目标为求函数1f和2f的极小值如图所示。就方案1A和2A来说，有：1112fAfA且2122fAfA，故无法确定优劣。而对于方案2A和3A而言，有：1213fAfA且2223fAfA；所以显然2A比3A好。对于方案1A和2A，由于无法确定其优劣，而且又没有比它们更好的其他方案，所以它们就被称之为多目标规划问题的有效解（或者非劣解），其余方案都称为劣解。所有非劣解构成的集合称为非劣解集。1A2A3A4A5A6A7AO2f1f多目标规划的解集绝对最优解设*Rx，如果对于Rx均有*FxFx，则称*x为多目标规划问题的绝对最优解。多目标规划问题的绝对最优解的全体可以记为*abR，其含义为：该最优解与任意一个可行解都是可以进行比较的。下图为当1,2np时绝对最优解的示意图。1fx2fxOxfx*x1fx2fxOxfx*,abRabbaab多目标规划问题的的绝对最优解一般情况下是不存在的。事实上，如果把多目标规划中的每个目标函数看成是单目标规划问题的目标函数，即我们分别考虑p个单目标规划问题：min,,1,2,...,ifRinxx，那么这p个单目标规划问题的公共最优解才是多目标规划问题的的绝对最优解。如果这p个单目标规划问题没有公共的最优解，则多目标规划问题就没有绝对最优解。多目标规划的解集有效解与弱有效解设*Rx，如果不存在Rx使得*FxFx成立，则称*x为多目标规划问题的有效解。多目标规划问题的有效解的全体记作*eR，有效解的含义是：在所有的可行解中找不到比它好的可行解，当1,2np时有效解的直观几何意义如图(a)所示，其有效解的集合*,eRab设*Rx，如果不存在Rx使得*FxFx成立，则称*x为多目标规划问题的弱有效解。多目标规划问题的弱有效解的全体记作*weR，弱有效解的含义是：在所有的可行解中找不到比它严格好的可行解。当1,2np时弱有效解的直观几何意义如图(b)所示，*,weRab，*,eRcd1fx2fxOxfx1fx2fxOxfxbaabab*,eRabcd多目标规划的解集解集之间的关系(1)若*1piiR，则**1pabiiRR(2)**eweRRR(3)**(1,2,...,)iweRRip(4)**abeRR(5)若*abR，则**1piweiRR，***1pieabiRRR(6)若Fx中每个ifx都是严格凸函数，R是凸集，则**eweRR多目标规划的象集考虑多目标规划问题：V-mins.t.0(1,2,...,)igimFxx(8-3)则其可行域为：|0,1,2,...,iRgimxx则根据上述模型，我们任意给定一个可行解Rx，则其对应的目标函数值Fx是一个p维的向量。即有nRRx，12[]TppfffRFxxxx。设RF表示可行域R中所有x对应的p维向量Fx的全体，即：|RRFFxx，如果把Fx看作是由约束集合R到pR的映射，则RF称为象集或者目标空间，R称为原象或策略空间。对Rx，必有RFxF，反之对RFF，必Rx使得FxF，即象集RF中的每一个象点，至少有一个R中的与之对应，但这种对应不一定是“一对一”的。多目标规划的象集有效点和弱有效点。设RFF，如果不存在RFF使得FF成立，则称F为象集RF的有效点，有效点的全体记作*eF设RFF，如果不存在RFF使得FF成立，则称F为象集RF的弱有效点，弱有效点的全体记作*weF根据上述定义显然有：**eweFF多目标规划的象集研究象集的作用在于：(1)求出RF中的有效点和弱有效点，就可确定有效解和弱有效解；(2)对象集RF的研究可以提供—些解多目标规划的方法；(3)可以从几何上（例如2p时）对一些常用的解法加以解释。有效解和有效点、弱有效解和弱有效点之间有如下的关系：若已知象集RF的有效点集*eF，则多目标规划问题的有效解集*eR可以表示为：**|,eeRRFFxFxFx若已知象集RF的有弱效点集*weF，则多目标规划问题的弱有效解集*weR可以表示为：**|,weweRRFFxFxFx这两个定理说明，RF的有效点和弱有效点的原象分别为多目标规划问题的有效解和弱有效解。处理多目标规划的方法约束法评价函数法功效系数法约束法原理约束法又称主要目标法，它根据问题的实际情况．确定一个目标为主要目标，而把其余目标作为次要目标，并根据决策者的经验给次要的目标选取—定的界限值，这样就可以把次要目标作为约束来处理，从而就将原有多目标规划问题转化为一个在新的约束下，求主要目标的单目标最优化问题。假设在p个目标中，1fx为主要目标，而对应于其余1p个目标函数ifx均可以确定其允许的边界值：,2,3,...,iiiafbipx。这样我们