《多目标参数线性规划_赵建中》由会员分享，可在线阅读，更多相关《多目标参数线性规划_赵建中（10页珍藏版）》请在金锄头文库上搜索。
1、运筹与管理 1夕好 年第 了一4期 多目标参数线性规划 赵建中 已二海机械学院) 提要本文主要 讨论利用一组爹数变量 求解多 标线性 规划的方法 , 使得所有口标函数的凸线性组合 最大 , 确定多目标规划非劣解的参数约束空 间 。 如 何利川参数空间.飞勺约束法 确 定 多 目标线性规划中目标函数 的系数知阵 , 以及如何利用参 数空间分解法求多目标的作劣解 报后 , 义中附实例说明如何应用此方法来 解 决多目标线性规划的问题 引 在 现实世界的生 活中 , 人们经 常碰到多个目标 或多指标决 策的问题 。 这 些目标很难用 统一的单个指标来衡量 , 有 些目标是互相矛盾 , 互相冲突 的 ,
2、 甚 至会出现 互相对立的目标 。 看来仅仅用传统的线性规划理论和方法 , 是 满足不了多目标规划或决 策间题的需 要 。 为了 解 决上 述 出现 的矛盾 , 近二 十多年 来人们越 来越重视多目标决策或多 目标规划 的 问题 。 多目标规划是 现代运筹学 中一 个 主要的分支 , 其历 史根源可以追 朔 到 K u h n 和T u c ke 1 4 以及 K o op m a n s的早期 (1 95 1年 )的工作 。 直到 1972 年在 美国S。川11 C a r olin a召 开第一次 国际性多目标决策会议以来 , 多目标规划 才被实际承认是一 个可 以独立 的专业 2, 。
3、由于它 对现实世界 中 的决策很 有帮助 , 因此它是 一个已经引起 多方面兴 趣和注 意 的应用 和研究领 域 。 国内许多专家教授 2,4, 。 也发 表了许多论文 , 对多目标规划的理 沦和应用进行探讨研 究 。 目前 , 多目标决策和规划的方法是众 多的 5, , 很难 用统一 的准则 来综 合 。 据国内有关多 目标决策 的介绍 , 多目标决策大体可分为下述几个大 类 : 1 、 化多目标为 单目标方法 。 2 、 分层序 列方 法 。 3 、 引进次序方 法 。 4 、 多目标线性规划 方法 。 5 、 目标规划方 法 。 6 、 其它方 法 。 (上接第月 页) 然后求出所有检
4、验数 : 气一( s , + t i ) ;a i j二马+ ( s j+ t j ) , 其结果全列 于表 6中 。 从表 6中看出 , 内) 几 。 ) 0 ( i = 1 , 2 , 3 . 4;j=工 , 2 , 3 , 4 ) , 故知 , 扩展运输问题已达 最 优 解其最优费用 为247 , 比传统最 优费用节约2个单位 。 15 上 述各方法 的具体理论与算法 , 使用过程可参考文献 36 。 二 、 多目标参数线性规划的一般表达式 多目标线性规划讨沦两个以上目标函数的优化 问题 , 它和传统的单目标优化问题仅有目 标函数表达式上的差异 。 对于一个 有 n 个 决策变量 , m
5、个 限制条件的单目标优化问题 , 其数学表 达式如下 : Ma x 5 .T. F( x )二f (x 1,xZ,“ ,x (1) , m n 善 a 。荞( b k, 长) 0 , k=1 ,2, 二 j= I ,2, ” 一般具有 n 个 决策变量 , m个限制条件 , 1个目标函数的多目标优化问题 , 其数学表达式 如下 : V 一Max F( x)=云 ( x) , 几( x) , ,五 ( x ) (2) S T 善 a。bk , 荞) 0 , 其中目标函数 k=l ,2, ” , m j= l , 2 , ” ,n 荞茂 行 J Z j CC n 艺 同 一 一 ( x 扩 n 艺
6、 洲 一一( x 犷卜 荞c t j n 艺 洲 一一 ( x rL飞 因此 , 上述多目标函数表达式 可写为: n 若( x ) 一F( x 丫 一 ( x ), 一暑 C入 , 一, 2 , ” , l 子( x ) 表示目标向量 F( x )的转置 向量 , 即 F( x )=F( x丫= 甄( x ) ,几( x ) . . ,双 ( x ) T 。 上述多目标线性规划优化 问题也可用 向量 形式表 示 : M aX S T. F( x ) =C X AX毛B X)0 (3) 其中 : X二( x :,从 、 、 1 1/ J / ,xn 丫 C一2 c l l 勺 / 了 .| 、
7、、 、 一 一 C l6 _ _ _ 一- - 一一一- - - - - - - - b . 、 l!1 11/ : 一 玩b m / 了护11 一 一 B a耐a心 ” a咖 、 、 IJ .I z 产 /l |1 、 、 . 一一 A 下面通过引进一种多参数规划的方法 来解决多 目标线性规划的问题 。 令A是 所有参数又的集合 , 即A 二又 , 寿 二 , 研 , 这里!表示1维目标空间 , 其定 义如下 : A= 川 又 E l , 又 ;) 0 , 艺又 、= l , i=l ,2, ,l ) 其中E l表示 在1维空间 中参数可行解 的集合 。 为清楚地 表示上述 定义 , 利 用
8、三维空间坐标图象 表示(见 图1) 。 然后 , 通过引进参数义来构成多目标参数线性规划的一般表达式 。 已知又 eA , 令 P( A , x ) = 艺凡 F( x )= 艺从( x ) , 其中 F( x)表示目标函数值的 向量 , 是 x 的线性函数表 达式 。 P( k , x )是 又与 x 的双 线性函数表 达式 。 多 目 标参数线性规划数学模型如下 : M ax p(又 , x)= 艺 义 j ( x)( 4 ) i,百 xR xR 又 任A 又任A R= x j xR ” X)0 , Ax簇B A= x I胆E , 艺 几 、司, 兄 却图 1 (注 : 在又O时可用图 1
9、中人表示 . A空间也可 以减少到斜影的两维坐标 , ) 三 、 确定多目标参数规划的系数 在 多 目标参数线性规划中 , 如何确定合理的目标函数系数是解决 多目标参数规划 的前 提 。 本文通过参数空 间降阶 的方法 , 减少目标空间的维数 , 来确 定多 目标函数的系数 。 参数空间降阶法 的证明如下 二 P以沐)= 艺凡( ( x )二 n 一“ 馨 q j x j + 各 “ 善 、 x j 气 。 工 川1几 l 艺 同 艺 、 ; =l , 即入+ 艺 义 i= l 义 := 1一艺凡 17 钊-一 - . - - - .月一,-一.目目-目- - . - -一一一- 一-一 -
10、- - - 一一 l . . P ( A , x , 一,一戴 协 、客 喀 q j x j 一言 卜 蒸 纸 一 外 我们可以将(5 )式改写为如下 的一般表达式 : ( 5 ) P份 ,x )一善、+ 答暮 “ i佩一 、) x j (6) 目口 一善 气、+“ 1一 善 幻 伙一厂马) x , +“ 1 一 善 偏一厂、) x j + O +“ 属 ( c . j 一 0 j ) x 其中马表示第 i个目标函数中第j个 决策变 量的系数 , 这 些系数均 为已知 的 常数 。 然 后 , 利 用(6 )式参数空间的分解方法 , 将原来参数空间 1维降阶到l一1维 , 从而得到 一组目标
11、函数的系数 。 四 、 利用参数 空 间分解法求非劣解 1一l 显然在( 5 )式中c l j 十馨“ i( c j 一, 的值是“的函数 所以设 : 、(“)一、+ 善 “ i( c j 一、 , 这样 , (5 ) 式可变为 : P扭, x,一善、以)、 ( 7) 可见 P (凡x )是R与A域中的 一个双线性函数 。 若已知又 *A, 我们可找 出一个线性函数 p扭* ,x )并使得 P扭 * , x ) = 艺马扭 * ) x j Ma x (8) xR ,只* 人 n R 一 x x 眼 。; 蓦 a x j b“ 多O 在(8 )式的基础上 , 设法 在 义 *A 与 x 任R 的
12、 范困 中找 出一 点又 , 并使得下式成立 : 即 P(又 * , 幻) p(又 * ,x ) 式中 ) 符号表示 至少有 一个目标函数值存在 着严格的大于 。 此时求得的又称为 多目标线 性规划的非劣解 。 为了较清楚地表达上述求非 劣解 的过程 , 本文利用单纯形 迭代过程 来说明一下 多目标 参数线性规划的算法过程 。 在表 1中共有 n 个决策变量中 , m个 限制条件 (k ) , l个目标函数(i ) 。 整个表格中共有 m ( n + m ) 个元素 , 其中在变 量 x , 一 x 。 下面 的基本元素 a, : 一 am n 为限制条件中的常 系数 。 在松驰变量 x 。+
13、: 一 x 。* I n 下面 的元素 a. n十: 一 a。 。十。 之中 , 其主对角线为 1 , 故将 x n +: 一 x 。+ 。 列人基本变量By的一列 中 。 b 、 为限制条件的右端项 。 l8 . . . . . . . . . . . . . . . . 表 1 c c clJ* * *el一* eln* 00 0 0 马马 * * * 气 * 气 * 00 0 0 气气* * *B V V V xz “ x,、 气 +一 ” 凡 +m m m b 、 0 0 00 0 0凡 + 1 1 1 a一 “ a一 :一 aIn +1 aln +m m m b l l l 0 0
14、00 0 0凡 +m m m am一 “ a而、a:n n卜l ” am n+m m m b m m m z z zlj*=zl j*一只j * * * 一el一* 一e一 n* 0 二 0 0 0B 一* * * 孔孔 * = 犷 一马* * *一q产 一气* O 。二 0 0 0 B 一* * * 表格中凡是带有 * 号的变量 (如 : 气 * , 孔 * 等)表示 : 在 固定又忙A的范围之内 , 求 1一I D P ( A , x ) 一属 q j x j + 蒸 凡 嘱 ( 0 j 一 0 j ) x j 一 Ma x xCR , 又 *A 的极大值 。 前面我们已经知道 马( 幻
15、凡( c j 一马) 在 沪A时 , 设马 * 二气 , 马 * 二气一q j , 所以 _ 匕式 可改为 二 、以 , )一、 , + 答 凡 、 (9) 表 l中 z。* = 艺 e. k*a、j 、 一凰 q ka 。 j一 ”n +m ) 其一般数学表 达式如下 : 。, 一凰q ,a 。, i=l ,2, ,l; j= l , 2 , ,n +m 表中B .* 玖 * 表示P (沪 , x )中各目标参数规划的解 , 并非原目标函数F ( x)中各目标f ( x) 的解 . B ,* = 艺 e. k*bk l9 - - 一 - 一- - - - - - B ,* = 艺q k* b
16、 k 其一般表达式为 : B i* 一艺q k* b , , i=l , 2 , ,l 或 在求目标函数极大值时 , 必 须使所有的孔*都大于等于零 , 即 目标的优化条件 。 多目标参数线性规划的优化条件如下 : 几 * 二几*一马*) 0 i=1 ,2, , l; j= 1 、2, ,n + m (10) 凰 、 k, a。一、, ) o 在满足上述条件的基础上 , 求出一组 解又 , 并使得 P(护 , 幻) P以* ,x ) 成 立 。 如果又是 唯 一 解 , 并且在 又*。A和 凡 * 0 ( i 二1 ,2, , 1 )的条件下 , 则称又为多目标参数线性规划的最优解 。 五 、 如
