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

第 10 章 多目标规划简介 10.1 基本概念与术语 10.1.1 模型举例 例 1( 物资调运优化 ): 假设物资调度部门计划将某种物资从若干个储存仓库， 调运到若 干个销售网点。 考虑到物资的时效性和销售效益， 调度部门希望物资在运输过程中尽可能快地到达目的地；考虑到运输的成本，调度部门还希望物资的总运输费用最小。 假设 m 个仓库的物资库存量为 a ， ，a （单位：t) ； 个销售网点预计销售量为 b ， ， 1 m n 1 bn （单位： t) 。 仓库 i 与销售网点 j 之间的路程为 dij ( 单位： km)，单位物资的运费为 cij （元）。 用物资吨公里总数来衡量物资的运输品质， 吨公里总数最小意味着有适量的物资尽可能快地到达目的地。 记从仓库 i 到销售网点 j 运送的物资量为 xij 。 目标函数： （1）物资在运输过程中的吨公里总数为 dij xij i j （2）物资运输费用总和为 cij xij i j 约束条件为产销平衡条件： xijai xijbj j i 优化问题模型： dij xij min i j cij xij i j s.t. j xij ai , i 1, ,m i xij bj , j 1, ,n xij 0, i 1, , m, j 1, , n 多目标规划（ MOP）问题描述 : 142 min f (x) ( f1( x), f2 ( x), , f p (x))T (1) s.t. gi ( x) 0, i I ( 2) hj ( x) 0, j E (3) ( x) 称为向量值目标函数。变量可行域记为 S { x Rn | x满足（2）（3）} S 的像集 Z f (S) 称为目标可行域， Z 中的元素 z f (x) 称为目标向量。 如果不指明约束函数的具体形式，多目标规划问题可以简记为 (MOP ) V min f ( x) x S 若每个目标函数 fi (x) 都是凸函数，并且可行域 S 是凸集，则（ MOP）称为多目标凸规划 问题。 10.1.2 向量集的有效点与弱有效解 在讨论向量集的有效点之前，约定如下记号：对于任意两个向量 x (x1, x2 , , xn )T y ( y1 , y2, , yn )T 令 （1） x y xi yi , i 1,2, , n （2） x y xi yi , i 1,2, , n,但存在某个 j，使得 x j y j （3） x y y x 0 （4） x y xi yi , i 1,2, ,n （5） x y xi yi , i 1,2, ,n 定义 1：给定一个向量集 X Rn ，对于点 x0 X ，若 x X ，有 x0 x ，则称 x0 是 X 的绝对最小点（即绝对最小向量）。若不存在x X ，使得 x x0 （ x x0 ），则称 x0 是 X 的有效点（弱有效点）。 集合 X 的所有绝对最小点、有效点和弱有效点的集合分别记为 Ea ， Ep 和 Ewp 。 143 例 2：考虑椭圆 X {( x1 , x2 ) | ( x1 0.5)2 (2x2 ) 2 4} 。 Ea Ep Ewp { x X | x1 0.5, x2 0} 从几何上看， E p 表示椭圆的左下部（包括端点）。 约定： 非负锥： Rn { x Rn | x 0} 正锥： Rn { x Rn | x 0} 定理 1：给定 x0 X Rn ，考虑下面条件： （ 1）对某 Rn ，函数 T x i xi （ x X ）在 x0 处取到最小值； i （ 2）对某个 Rn ， 0 ，函数 T x （ x X ）在 x0 处取到严格最小值； （ 3）对某个 Rn ， 0 ，函数 T x （ x X ）在 x0 处取到最小值。 0 若条件（ 1）或（ 2）成立，则 x 是 X 的有效点。 0 若条件（ 3）成立，则 x 是 X 的弱有效点。 10.1.3 多目标规划的解及其性质 考虑形如式（ 1）（- 3）的多目标规划问题， 变量可行域 S { x Rn | x满足式（ 2）（3）} ， 目标可行域 Z f ( S) 。 定义 2：给定一可行点 x* S ，若 x S，有 f ( x * ) f x * 为问题 (MOP）的 ( )，则称 绝对最优解（绝对最小解）。若不存在 x S ，使得 f (x) f ( x* ) ( f ( x) f ( x* ) ) , 则 称 x* 为问题（ MOP）的有效解（弱有效解）。 问题（ MOP）有效解也称 Pareto 最优解。将问题（ MOP）绝对最优解、有效解、弱有效解 集合分别记为 Sa ，