第10章多目标规划简介

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

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

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

4、）。问题（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是对整个群体所进行的进化运算操作，它处理的是个体的集合，这种相似性使得GA可以作为求解多目标规划问题的Pareto最优解集的一个有效手段。注1：间接

7、解法的共同特点：将多目标规划问题转化为一个或多个单目标优化问题。通过求解单目标优化问题得到（MOP）的一个或多个最优解。一般并不要求间接解法给出问题的所有最优解。10.2.2 基于一个单目标问题的方法基本思想：首先将原来的多目标规划问题（MOP）转化成一个单目标优化问题；然后利用非线性优化算法求解该单目标问题，把所求得的最优解作为问题(MOP）的最优解 线性加权和法 主要目标法 理想点法 极小化极大法这类方法的核心：保证所构造的单目标问题的最优解是（MOP）的有效解或者弱有效解线性加权和法：根据个目标函数的重要程度，分别赋予一定的权系数，然后将所有的目标函数加权求和作为新的目标函数，在（MOP

8、）的可行域S上求出新目标函数的最优值。 问题转化为如下单目标优化问题：（） 其中。f, g, h为向量值函数。主要目标法：根据实际情况，首先确定一个目标函数为主要目标，不妨假设为主要目标，而把其余的个目标函数作为次要目标。然后借助于决策者的经验，通过选定一定的界限值（），把次要目标转化为约束条件，通过求解如下的单目标优化问题获得问题（MOP）的最优解：（） 10.2.3 基于多个单目标问题的方法基本思想：根据某种规则，首先将（MOP）问题转化为有一定次序的多个单目标优化问题；然后，依次分别求解这些单目标优化问题，并且把最后一个单目标优化问题的最优解作为原问题的最优解。 分层排序法 重点目标法

9、分组排序法这类方法的核心：保证最后一个单目标优化问题的最优解是（MOP）的有效解或者弱有效解。分层排序法：根据目标的重要程度将它们一一排序；然后分别在前一个目标的最优解集中，寻找后一个目标的最优解集，并把最后一个目标的最优解集作为问题（MOP）的最优解。首先，通过求解单目标问题得到的最优解集。然后对于，依次求解单目标优化问题得到的最优解集。最后，将中的点作为（MOP）的最优解。重点目标法：在p个目标函数中，首先确定最重要的目标，比如，并且在S上求出的最优解集；然后，在上求解其余个目标对应的多目标规划问题把（MOP）的有效解或弱有效解作为（MOP）的最优解在求解问题（MOP）时，可以利用前面介绍的方法，将（MOP）转化为一个单目标优化问题求解。分组排序法：根据某种规则，首先将（MOP）的目标分成若干个组，使得在每个组内的目标的重要程度相差不多，此时，每组目标实际上对应着一个新的多目标规划问题；然后，依次在前一组目标对应问题的最优解集中，寻找后一组目标对应问题的最优解集，并把最后一组目标对应问题的最优解作为（MOP）的最优解注2：分组排序法实际上是分层排序法的推广形式。分层排序法是针对