第10章多目标规划简介.doc

《第10章多目标规划简介.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第10章多目标规划简介§10.1基本概念与术语10.1.1模型举例例1(物资调运优化):假设物资调度部门计划将某种物资从若干个储存仓库，调运到若干个销售网点。考虑到物资的时效性和销售效益，调度部门希望物资在运输过程中尽可能快地到达目的地；考虑到运输的成本，调度部门还希望物资的总运输费用最小。假设个仓库的物资库存量为，…，（单位：t)；个销售网点预计销售量为，…，（单位：t)。仓库i与销售网点j之间的路程为(单位：km)，单位物资的运费为（元）。用物资吨公里总数来衡量物资的运输品质，吨公里总数最小意味着有适量的物资尽可能快地到达目的地。记从仓库i到销售网点j运送的物资量为。目标

2、函数：（1）物资在运输过程中的吨公里总数为（2）物资运输费用总和为约束条件为产销平衡条件：优化问题模型：多目标规划（MOP）问题描述:称为向量值目标函数。变量可行域记为S的像集称为目标可行域，Z中的元素称为目标向量。如果不指明约束函数的具体形式，多目标规划问题可以简记为若每个目标函数都是凸函数，并且可行域S是凸集，则（MOP）称为多目标凸规划问题。10.1.2向量集的有效点与弱有效解在讨论向量集的有效点之前，约定如下记号：对于任意两个向量令（1）（2）（3）（4）（5）定义1：给定一个向量集，对于点，若，有，则称是X的绝对最小点（即绝对最小向量）。若不存在，使得（），则称是X

3、的有效点（弱有效点）。集合X的所有绝对最小点、有效点和弱有效点的集合分别记为，和。例2：考虑椭圆。从几何上看，表示椭圆的左下部（包括端点）。约定：非负锥：正锥：定理1：给定，考虑下面条件：（1）对某，函数（）在处取到最小值；（2）对某个，，函数（）在处取到严格最小值；（3）对某个，，函数（）在处取到最小值。若条件（1）或（2）成立，则是X的有效点。若条件（3）成立，则是X的弱有效点。10.1.3多目标规划的解及其性质考虑形如式（1）-（3）的多目标规划问题，变量可行域，目标可行域。定义2：给定一可行点，若，有，则称为问题(MOP）的绝对最优解（绝对最小解）。若不存在，使得()

4、,则称为问题（MOP）的有效解（弱有效解）。问题（MOP）有效解也称Pareto最优解。将问题（MOP）绝对最优解、有效解、弱有效解集合分别记为，和。多目标规划的（弱）有效解与其目标可行域的（弱）有效点之间有紧密的联系，概括为如下定理：定理2：对于问题（MOP)，令表示目标函数在定义域S上的值域（目标可行域）,Z的有效点集和弱有效点集分别记为和，则（MOP）的有效解集和弱有效解集，由下面式子给出：（1）（2）解集合，和之间的关系，有如下定理：定理3：对多目标规划问题（MOP)，必有（1）（2）当时，（3）若可行域S为凸集，f是S上严格凸的向量值函数，则。如果记单目标优化问题的

5、最小点的集合为，那么多目标规划问题的绝对最优解的集合此外，容易证明成立。根据定理3，有如下结论：例3：求解两目标优化问题其中。记目标,。单目标优化问题的最优解集，,故绝对最优解集。该问题的目标可行域为根据Z的（弱）有效点定义以及定理2，该问题的有效解集与弱有效解集相等。特别地，。例4：求解两目标优化问题其中。记目标,.单目标优化问题最优解集，,故绝对最优解集。根据定理3中结论(3)，该问题的有效解集与弱有效解集相等.另外，该问题的目标可行域Z为根据Z的（弱）有效点定义，可以知道利用定理2，有。§10.2多目标规划的解法10.2.1多目标规划的直接解法多目标规划问题（MOP）的

6、本质在于：各个子目标有可能是相互矛盾的，一个子目标的改善有可能引起另一个子目标的恶化，同时使所有子目标都达到最优值一般是不可能的，只能是在这多个子目标之间进行协调和权衡，使各个子目标尽可能地达到理想值。多目标规划问题的直接解法，就是寻找它的整个最优解集（Pareto有效解集）。除了特殊的情形，计算所有的最优解是比较困难的，因为确定整个有效解集的问题是NP-hard的。目前对直接解法的研究结果还比较少，主要采用间接解法。直接解法的最新进展——多目标遗传算法（MOGA）。多目标规划Pareto最优解一般是一个集合。由于GA是对整个群体所进行的进化运算操作，它处理的是个体的集合，这

7、种相似性使得GA可以作为求解多目标规划问题的Pareto最优解集的一个有效手段。注1：间接解法的共同特点：将多目标规划问题转化为一个或多个单目标优化问题。通过求解单目标优化问题得到（MOP）的一个或多个最优解。一般并不要求间接解法给出问题的所有最优解。10.2.2基于一个单目标问题的方法基本思想：首先将原来的多目标规划问题（MOP）转化成一个单目标优化问题；然后利用非线性优化算法求解该单目标问题，把所求得的最优解作为问题(MOP）的最优解．—线性加权和法—主要目标法—理想点法—极小化极大法这类方法的核心