第章 多目标规划简介.docVIP

第10章 多目标规划简介 §10.1 基本概念与术语 10.1.1 模型举例 例1(物资调运优化): 假设物资调度部门计划将某种物资从若干个储存仓库，调运到若干个销售网点。考虑到物资的时效性和销售效益，调度部门希望物资在运输过程中尽可能快地到达目的地；考虑到运输的成本，调度部门还希望物资的总运输费用最小。 假设个仓库的物资库存量为，…，（单位：t)；个销售网点预计销售量为，…，（单位：t)。 仓库i与销售网点j之间的路程为(单位：km)，单位物资的运费为（元）。 用物资吨公里总数来衡量物资的运输品质，吨公里总数最小意味着有适量的物资尽可能快地到达目的地。 记从仓库i到销售网点j运送的物资量为。 目标函数： （1）物资在运输过程中的吨公里总数为 （2）物资运输费用总和为 约束条件为产销平衡条件： 优化问题模型： 多目标规划（MOP）问题描述: 称为向量值目标函数。变量可行域记为 S的像集称为目标可行域，Z中的元素称为目标向量。 如果不指明约束函数的具体形式，多目标规划问题可以简记为 若每个目标函数都是凸函数，并且可行域S是凸集，则（MOP）称为多目标凸规划问题。 10.1.2 向量集的有效点与弱有效解 在讨论向量集的有效点之前，约定如下记号：对于任意两个向量 令 （1） （2） （3） （4） （5） 定义1：给定一个向量集，对于点，若，有，则称是X的绝对最小点（即绝对最小向量）。若不存在 ，使得（），则称是X的有效点（弱有效点）。 集合X的所有绝对最小点、有效点和弱有效点的集合分别记为，和。 例2：考虑椭圆。 从几何上看，表示椭圆的左下部（包括端点）。 约定： 非负锥： 正锥： 定理1：给定，考虑下面条件： （1）对某，函数（）在处取到最小值； （2）对某个，，函数（）在处取到严格最小值； （3）对某个，，函数（）在处取到最小值。 若条件（1）或（2）成立，则是X的有效点。 若条件（3）成立，则是X的弱有效点。 10.1.3 多目标规划的解及其性质 考虑形如式（1）-（3）的多目标规划问题，变量可行域，目标可行域。 定义2：给定一可行点，若，有，则称为问题(MOP）的绝对最优解（绝对最小解）。若不存在，使得 () , 则称为问题（MOP）的有效解（弱有效解）。 问题（MOP）有效解也称Pareto最优解。将问题（MOP）绝对最优解、有效解、弱有效解集合分别记为，和。 多目标规划的（弱）有效解与其目标可行域的（弱）有效点之间有紧密的联系，概括为如下定理： 定理2：对于问题（MOP)，令表示目标函数在定义域S上的值域（目标可行域）,Z的有效点集和弱有效点集分别记为和，则（MOP）的有效解集和弱有效解集，由下面式子给出： （1） （2） 解集合，和之间的关系，有如下定理： 定理3：对多目标规划问题（MOP)，必有 （1） （2）当时， （3）若可行域S为凸集，f是S上严格凸的向量值函数，则。 如果记单目标优化问题 的最小点的集合为，那么多目标规划问题的绝对最优解的集合 此外，容易证明成立。 根据定理3，有如下结论： 例3：求解两目标优化问题 其中。 记目标, 。 单目标优化问题的最优解集，,故绝对最优解集。该问题的目标可行域为 根据Z的（弱）有效点定义以及定理2，该问题的有效解集与弱有效解集相等。特别地，。 例4：求解两目标优化问题 其中。 记目标, . 单目标优化问题最优解集，,故绝对最优解集。 根据定理3中结论(3)，该问题的有效解集与弱有效解集相等.另外，该问题的目标可行域Z为 根据Z的（弱）有效点定义，可以知道 利用定理2，有。 §10.2 多目标规划的解法 10.2.1 多目标规划的直接解法 多目标规划问题（MOP）的本质在于：各个子目标有可能是相互矛盾的，一个子目标的改善有可能引起另一个子目标的恶化，同时使所有子目标都达到最优值一般是不可能的，只能是在这多个子目标之间进行协调和权衡，使各个子目标尽可能地达到理想值。 多目标规划问题的直接解法，就是寻找它的整个最优解集（Pareto有效解集）。除了特殊的情形，计算所有的最优解是比较困难的，因为确定整个有效解集的问题是NP-hard的。 目前对直接解法的研究结果还比较少，主要采用间接解法。 直接解法的必威体育精装版进展——多目标遗传算法（MOGA）。 多目标规划Pareto最优解一般是一个集合。由于GA是对整个群体所进行的进化运算操作，它处理的是个体的集合，这种相似性使得GA可以作为求解多目标规划问题的Pareto最优解集的一个有效手段。 注1：间接解法的共同特点： 将多目标规划问题转化为一个或多个单目标优化问题。 通过求解单目标优化问题得到（MOP）的一个或多个最优解。 一般并不要求间