（运筹学与控制论专业论文）不等式约束的一种修改的罚函数方法.pdf

摘要 摘要 本文提出并分析一种解决不等式约束最优化问题的修改的罚函数法，这 一方法综合利用修改的罚函数和拉格朗日法修改的罚函数法所用的罚函数 消除了经典罚函数的主要缺点，修改的罚函数存在解，且在解的邻域内保持目 标函数和约束函数的光滑性修改的罚函数法首先最小化修改的罚函数，进而 校正拉格朗日乘子，这一方法避免了函数m 。z ho 的不可微性，且对于足够 大的罚参数，修改的罚函数法在二阶最优性条件满足的条件下线性收敛，在每 次校正拉格朗日乘子后增加罚参数能达到超线性收敛 本文是按如下方式组织的第一章为绪论部分，第二章介绍本文收敛性理 论所需要的一般非线性规划问题的最优性条件和基本的假设条件，第三章给 出修改的罚函数的定义，修改的罚函数法，以及第步迭代所用的信赖域算 法，第四章讨论修改的罚函数法的收敛理论，数值实验和由修改的罚函数法得 出的一些结论 关键词：最优化，不等式约束，收敛，修改的罚函数 北京工业大学理学硕士学位论文 a b s t r a c t w e p r e s e n ta n da n a l y z eam o d 谕e dp e n a l t yf u n c t i o n s ( m p f ) m e t h o df o r s o l v i n gc o n s t r a i n e do p t i m i z a t i o np r o b l e m sw i t hi n e q u a l i t yc o n s t r a i n t st h i s m e t h o dc o m b i n e st h em o d 洒e dp e n a l t ya n dt h el a g r a n g i a nm e t h o d s i ti s b a s e do nm p f ，w h i c ht r e a t si n e q u a l i t yc o n s t r a i n t sw i t ham o d i f i e dp e n a l t y t e r m t h em p fm e t h o da l t e r n a t i v e l ym i n i m i z e st h em p fa n du p d a t e st h e l a g r a n g em u l t i p l i e r s t h em p fm e t h o da v o i d st h ei n d i f f e r e n t i a b i l i t yo ft h e m n z z ，o ) f o r a l a r g ee n o u g hp e n a l t yp a r a m e t e rt h em p f m e t h o di ss h o w n t oc o n v e r g el i n e a r l yu n d e rt h es t a n d a r ds e c o n do r d e ro p t i m a l i t yc o n d i t i o n s s u p e r l i n e a rc o n v e r g e n c ec a nb ea c h i e v e db yi n c r e a s i n gt h ep e n a l t yp a r a m e t e r a f t e re a c hl a g r a n g em u l t i p l i e ru p d a t e t h i sp a p e ri s o r g a n i z e da s f 0 u o w s i nc h a p t e r1 ，t h eb a c k g r o u n da n d t h em a i nr e s u l t so ft h i sp a p e ra r eg i v e n t h eg e n e r a ln o n l i n e a rp r o g r a m m i n g p r o b l e ma n dt h eb a s i ca s s u m p t i o n su n d e rw h i c ho u rc o n v e r g e n c er e s u l t sh 0 1 d a r ei n t r o d u c e di nc h a p t e r2 i nc h a p t e r 3 ，w eg i v et h ed e 丘n i t i o no ft h em p f w h i c ho u rm e t h o di sb a s e do n ，t h em p fm e t h o da n dt h et r u s tr e g i o na l g o - r i t h m t h e c o n v e r g e n c er e s u l t sf o rt h em p fm e t h o d ，s o m ea s p e c t sc o n c e r n i n g t h ep r a c t i c a l i m p l e m e n t a t i o na n ds o m ec o n c l u d e dr e m a r k so ft h em e t h o da r e d i s c u s s e di nc h a p t e r4 i ( e y 、v o r d s ：o p t i m i z a t i o n ，i n e q u a l i t yc o n s t r a i n t s ，c o n v e r g e n c e ，m o d i 矗e dp e n a l t y f u n c t i o n ( m p f ) i i 第1 章绪论 第l 章绪论 1 1 背景与主要结果 本文提出一种新的解决不等式约束最优化问题的方法，即求解问题 ( i q ) ”机m ) ( 1 1 ) s t g ( z ) 0 的修改的罚函数方法，这里，( ) ：r ”_ 兄是一连续可微函数， g ( z ) = ( c l ( z ) ，c r 。( z ) ) r ：r “r m 一般来说，对于问题( 1 1 ) 的罚函数是利用目标函数，( z ) 和约束函数g ( 。) 所构造的具有“罚性质”的函数 p ( z ) = 户( ，( z ) ，g ( z ) ) ( 1 2 ) 所谓罚性质，即要求对( 1 1 ) 所有的可行点g x 均有p ( z ) = ，( 。) ，其中x 为问题( 1 1 ) 的可行域，而且当约束条件破坏很大时有p ( z ) 远大于，( z ) - 罚函 数方法将约束规划问题的求解，转化为一系列无约束极值问题，因而也称这 种方法为序列无约束最小化方法( s u m t ) ，典型的s u m t 方法就是f i a c o 和 m c m o r m i c k 算法 罚函数一般可表示为目标函数，( z ) 和一项与g ( z ) 有关的“罚项”之和， 即 p ( z ) = ，( z ) + ( d + ) ( z ) ) ( 1 3 ) 北京工业大学理学硕士学位论文 罚项 ( g ( + ) ( z ) ) 是定义在r ”上的函数它满足 ( 0 ) = 0 ， m ( g ) = + ， l i g | | _ + 。4 其中 g ( + ( z ) = ( c ( 十( z ) ，c # ( 。) ) 丁， c l + ( z ) = m o z o ，q ( z ) ) ，t = 1 ，- 一，m 我们称e ( + ) ( z ) 为约束违反度函数 最早的罚函数是c o u r a n t 罚函数，它定义如下 p ( z ) = ，( z ) + 盯| | c ( + ( z ) l l ； ( 1 4 ) 其中a o 是一正常数，它称为罚因子显然( 1 4 ) 是( 1 3 ) 的特殊情形，由此 我们可得出一类罚函数的定义如下 尸( z ) = ，( z ) + 盯| | g ( + ) ( z ) | i 。 ( 1 5 ) 其中a o 是罚因子，o o 以及”l i 是r ”中的某一范数罚函数( 1 5 ) 的 另两个特殊情形是 p l ( z ) = ，( z ) + 口i i g ( + ) ( z ) i | 1 尸( 茁) = ，( z ) + 盯| | e ( + ) ( z ) 0 它们分别称为l l ，l o 。罚函数 如果罚函数在可行域的边界上取值为无穷，则称为内点罚函数内点罚 函数法是利用内点罚函数求解问题( 1 1 ) 的方法由于它利用内点罚函数，它 第1 章绪论 产生的点列都在可行域的内部内点罚函数一般可表示为以下形式 只( z ) = ，( z ) 十一_ 1 ( c 。( 。) ) ， ( i 6 ) t = 1 其中o o 是罚因子， ( g ) 是定义在( o ，+ 。) 的实值函数两个常见的内点 罚函数是倒数罚函数 p ( - ，扛卜口。1 蚤南 和对数罚函数 p ( z ) = ，扛) + a 一1 f 叩( 一q ( z ) ) 2 = 1 从几何上看，内点罚函数在可行域的边界上形成一堵很高的“障碍墙”，所以 内点罚函数也常称为障碍罚函数 1 2 函数p ( z ，n ) 的性质 在文献 2 】中，c h e n 用函数p ( 。，o ) 近似加函数m o 。 z ，o ) ，也就是 其中 这是因为 其中 ，z1 m 。 z ，o ) 兰p ( z ，a ) 2 _ 。s ( ，a ) 妇= z + 言2 叩( 1 + e ”。)，一 u 出，a ) = 再三，。 o m o z z ，o = a ( ) 咖 ，z j o 。 f1z o 盯( z ) = 【o z o 一3 一 北京工业大学理学硕士学位论文 并且 出，n ) = 再，a o 与函数矿( z ) 非常近似 下面给出函数p 扛，a ) ，a o 的性质( 见文献【2 ) j 函数p ( 。，n ) 对任意正整数k 一阶连续可微，并且p ，( 孔d ) = t 干 面， f ( z ，n ) = 禹 2 函数p ( z ，a ) 严格凸且在r 上严格递增 3 对任：意$ r ，p ( $ ，a ) z + 4 搿旷刊帅) = 警， 量l i m 妇( 。，o ) 一。+ ) = o ，任意a o l z l o 。 6 撬p ( z ，a ) = 正+ ，任意z r zp ( z ，a ) ( o ，) ，其中z r ，任意。 o ，且反函数p 一1 在z ( o ，o o ) 上有定义 占p ( z ，a ) p ( 。，卢) ，其中a o v d d c 舻 第2 章基本假设和最优性条件 其中 d = d ：矿v q ( z ) = o ，江l ，r ) ( 2 2 ) c 3 对于不等式约束的严格松弛互补条件成立，即 2 2 本章小结 w q ( 矿) = o = 1 ，m ， n 0 l _ 1 ，r ， ( 2 3 ) q ( 矿) o ，且b d = o = 争( a d ，d ) 卢( d ，d ) ， o ， 则存在一d o o 对任意o o ，在z + 的邻域内求得严格凸光滑函数f ( z ，a ，n ) 的最小点 我们又知，如果拉格朗日乘子向量 r 足够近似于”，则 岔= 岔( a ，a ) = o ”g m 礼 f ( z ，a ，a ) i 。r “) 北京工业大学理学硕士学位论文 是z + 的一个好的近似故而得出，对于足够大的定值参数a o ，最小点岔 能改进a 近似于”选择一足够大的罚参数n ，从任意初始点( z ，a ) 开始，其 中a 冠，通过最小化函数f ( z ，a ，a ) 和校正拉格朗日乘子a 就可解决问题 ( 1 1 ) 让我们来具体的考虑假设无约束最小点壬= 畲( a ，a ) 存在，我们有 v 洲蛐= v m ) + 萎熹v 嘶) = o ( 3 2 ) i = l 通过公式 定：_ f ：1 ，m ， ( 3 3 ) 2 n i ：；丽 ”1 ”、“。 定义新的拉格朗日乘子，可重写( 3 2 ) 为 v 她扣) _ v m ) + 吾武v 嘶 ( 3 4 ) = v 。工( 童，支) = 0 因此，函数f ( 。，a ，a ) 的最小点岔是经典拉格朗日函数l ( z ，天) 的稳定点 圣是拉格朗日函数在凸集上的最小点 令i ( a ，n ) = 天，则，首先，对任意固定的a o ，支( ”，a ) = ”，即” 是映射a - + i ( a ，a ) 上的固定点，其次 | | 支一a + 0s ，yl i a a + 0 ( 3 5 ) fj 雪一。+ j js 7j j a a + j j ( 3 6 ) 其中o o 获得任意小的距离 上面所述就是我们为什么称之为修改的罚函数法下一节，我们将给出 其迭代算法 3 3 迭代算法 算法3 1 ： 步o ：给出a o ，锄， o ，女：= o ； 步l ：计算问题亦f ( 。，舻，a 女) 求出。+ 1 ，计算a 抖1 ，矿机，其中 。蚪1 = n r 肿讯 f ( z ，妒，a 女) f z r ”) ， 矿1 = 而尝两，m ， ( 3 7 ) n 女+ 1 = j 钒，2 是一迭代常数 k ：= 十1 转步2 ； 步2 ：如果j j v 。l ( 一，a ) j j ，j j g ( + ) ( 矿) j j e ，则停，否则转步1 关于问题：啄f ( z ， ，钒) ，我们可用求解无约束最优化问题的任意方法 本文，我们应用信赖域算法，这样可保证收敛更有效 3 4 无约束最优化问题的信赖域算法 在第k 步迭代，我们通过求解问题 m 伽机( d ) = 鳍d + j 护仇8 ( 3 8 ) 8 t 1 l d 女， 北京工业大学理学硕士学位论文 来计算试探步，其中弧= v 。f ( 矿，妒，a 女) ，凤是函数f ( z ，妒，o 女) 在矿处的海 森阵，女为信赖域半径，j i 表示无穷范数 在信赖域算法中，通过计算试探步吼来决定其是否可被接受本文，我 们应用修改的罚函数f ( z ， ，a ) ( 3 1 ) 作为价值函数如果价值函数f ( z ，a ，a ) 下降足够大，我们接受呶，并且令z + 1 ：= + 驴，否则，拒绝d 七为计算 下降量，我们记d 七为问题( 3 8 ) 的解，且通过 a r e 出：= f ( z ，a 七，o * ) 一f ( z + 1 ，妒，o 女) 算出价值函数的实际下降量，然后算出预测下降量 p r e 靠：= 机( o ) 一九( 如) 令n = 缶爱，o 0 ， c r o o ，s 0 ， 1 1 2 0 ，o 卢l 如 o 获得较快的收敛速度 下一章，我们将证明当二阶最优性条件满足并且a t o 足够大时，带 有固定罚参数a 的修改罚函数法的线性收敛性当_ 矿时，海森阵 v ：。f ( z ， ，a ) 的病态性会更小，这对于通过每步迭代增大a 女获得超线性收敛 性是有用的 1 3 北京工业大学理学硕士学位论文 第4 章修改的罚函数法的收敛理论 4 1 定理及其证明 在给出修改罚函数法的收敛结论之前，我们先做一些关于问题( 1 1 ) 的假 设我们假设下面的条件成立： j k 。：m “ 。蛩篓l q ( 刮i z x ) = k ( 4 - 1 ) 其中x 是问题( 1 1 ) 的可行域另外，梯度v q ( 矿) ，f _ 1 ，r 线性独立，且 定义下列集和； r l k ：丸，i 凡一a ：i d a ，o a o = 1 ，r d i ( ) = d i ( r ，q 6 ，) = l 扎：o 沁墨d a ，a a o ) i = r + 1 ，m 其中j o 是一足够小的数，o o 和足够小的数j o 使得对任意 o o 和t s ( o ，6 ) ，向量函数h ( ，t ，足够光滑，且 ( 茁+ ，0 ，a ) ；o 兄”，v 。_ l ( z + ，0 ，a ) = = d “。“ 考虑函数西。( z ，天( r ) ，t ，n ) ：肝+ r + 叶r “+ r 其中( 1 + e a q r ) ( 。) ) 一1 = 【d i o g ( 1 + e 一。“( 。) ) 一1 ：= 1 1 6 - ，v “ ( 矿，o ，a ) = d “ ，即 叭 、 回 m 屯 卜 嘞 + + 锄 肌 托 ) ，：i水 + q ) n 一e w h 一 撕 ，。，。一 = 入z 第4 章修改的罚函数法的收敛理论 令 由条件c 3 和 ( 矿，o ，a ) = 0 可得 西a 扛+ ，a h ，o ，a ) = o ，va o v 。已“蚝( z + ，a 0 ) ，o ，a ) ，磁。工= v ：。三( 矿，a + ) ，v ) = v ) ( ) a 0 ) = d f 凹等k l ：口一口，碍 o ，待1 ，r 因为v z ( z + ，o ，a ) = 。“，v i ( ，) ( z + ，o ，a ) = 伊”，所以 砜，吲一嘞，o ，加( 菇，斟 - v 式，吲一嘞，o ，出( 巍，斟 l l v 圣：1 l | sp 所以由第二隐函数定理和西a ( 矿，入轴，o ，q ) = o ，c ( z ) g 2 ，i = 1 ，m 可得屯( 。+ ，a ：r ) ，t ，a ) = o 存在向量函数。( t ，口) ，天( ，) ( t ，a ) 使得z ( o ，a ) = 。+ ，1 p ) ( o ，o ) = a 0 ) ，并且在s ( o ，= t ：f 岛fs 以= l ，一，m 辱畹内，当口2 n o 屯( z ( t ，a ) ，天( r ) ( 亡t q ) ，t ，a ) 三o ( 4 4 ) 1 7 北京工业大学理学硕士学位论文 因此，由。( ) ；z ( t ，n ) 和式( 4 4 ) 的前n 个方程可得 m v 。f ( z ( ) ，i ( ) ，- ) = v ，( z ( ) ) + 丸( - ) v q 扛( ) ) = o ( 4 5 ) t = l 也就是，z ( ) 是修改的罚函数的一个稳定点 另外，证明z ( ) 是修改的罚函数的局部极小点需用式( 3 5 ) 和( 3 6 ) 的估 计，这将在定理4 2 中给出证明对于函数f ( z ，a ，a ) 的严格凸性将在定理4 3 和4 4 中给以证明证毕 定理42假设条件j 成立，则对于岔和i = i ( a ，a ) = 再岛，当n 足够 大时， 壬一z | | s r1 1 a a 4 ( 4 6 ) 成立，其中百南= 胁。9 ( 1 + e 一。t 动) 一1 罂l ，o o ，当m n z 1 1 z ( t ，。) 一z + i i ，1 | i ( ，) ( t ，。) 一a + l i ) 墨印时 和 成立 面。( z ( t ，a ) ， ( ，) ( t ，o ) ，t ，n ) ；垂。 ( ) ，i ( ，) ( - ) ，) i o ( 4 7 ) v 。工f ，、壬。( 卫( t ，n ) ，天( ，) ( t ，a ) ，t ，a ) i j 2 p ，v t s ( o ，占) a q o 1 8 第4 章修改的罚函数法的收敛理论 并且 令 a = ，景装。 q ( 矿) ) o ， 天( z ( o ，a ) ，o ，a ) = a ：= o ， = r + 1 ，- ，m ， q 扛( 0 ，a ) ) = q ( 矿) 盯 0 ，i = r + l ，m ， d ，( o ，n ) = 2 ，研= 4 ，d 0 ( 。一，) ) f t ( m 一，) = o = d ( ”一) 。( ”一7 ) d ( q 。一r ) ( 矿) ) = 陋叼c ( $ + ) 】罂r + ls d ，” 2 0 d 二，( ( o ，a ) )= 2 q 【战0 9 ( 1 + e 一。c ( 。) ) 一1 銎，+ 1 2 a e ”p 。一 2 2 北京工业大学理学硕士学位论文 成立，其中i v q 。一，】( 。+ ) | | + l 三同时，可得 ( 慧h 纛赫，) = j 苫v 圣二1 ( z ( 下t ，q ) ，天( ，) ( 下t ，a ) ) r ( z ( 下t ，a ) ，( 丁t ，a ) ) 弘】d r 因此，考虑式( 4 1 5 ) 和( 4 1 6 ) 又可得 令 m 叩m ( ，a ) 一z ( t ，a ) 一a + 吣铷三e 4 喇i = 4 p 乩e 4 。a 。1 忪一” 则有 成立 岔( a ，n ) = z ( 3 亏竽，o ) ，i ( a ，o ) = ( 天( r ) ( 盖看生，口) ，天( 。一，) ( 墨专竖，a ) ) g = m 。 2 a e 扣，4 舢三e ”) ， m 。z l l z ( a ，a ) 一z + 扎i i i p ) ( a ，n ) 一a + i i ) s g a 一1 | | a a + | | = m 口。 2 e 4 。，4 面矿。) 1 i 一 1 ls 7 1 1 一 + 因为口 o ，所以当o - o o 时， 2 e 口。一0 ，4 p l e ”_ o ， 所以存在一足够大的数口o ，对任意n c r o ，o ，r 都成立证毕 由定理4 2 可知，当a 充分大时，修改的罚函数法可达到线性收敛在随 后两个定理中，我们将证明是函数f ( 。，a ，a ) 的全局极小点 一2 4 第4 章修改的罚函数法的收敛理论 v t 天( m 一，) ( o ，a ) = 0 ( m 一) 。，2 a d 二l ，( 。( o ，o ) = o ( ”一7 ) 。，2 0 出口9 ( 1 + e o q ( 2 + ) ) 一1 罂，+ 1 o 和任意s ( o ，6 ) ，口a o ，o 冬r s1 ，不等式 v 圣二1 ( z ( r t ，n ) ，天( ，) ( r t ，a ) ) r ( 。( r t ，a ) ，( r t ，a ) ) i | 2 p ( 2 a e 4 。0 v q m r ) ( z ) | l + 1 ) 4 阳l e ” ( 4 1 5 ) 一2 3 第4 章修改的罚函数法的收敛理论 定理4 3假设条件j 成立，则函数f ( z ，a ，a ) 在的邻域内严格凸 证明：由等式( 4 8 ) ( 4 1 0 ) 可知童= 圣( ，o ) 对函数f ( z ，i ，a ) 满足最优性必要 条件因此可证明矩阵v ：。f ( 童，a ，a ) 正定 我们知道 并且 v 删，加v m ) + 薹去v 如) v ( 川= v 绷卅薹高v 鞠z ) + 薹篇v 帅耕 因此，由丸= 天( a ，a ) 可得 v 恐f ( 圣，a ，a ) = v m ) + 圣天v 飘动+ 要，尚v 缄岔) i = i日十i + n 妻百；拿i ；舞v q ( ) v q ( 壬) 7 + a i = r + l v c i ( ) v q ( 士) t v ( a ，o ) d ( a + ，a o ，d ，) 由式( 4 6 ) 知，对足够大的数a o ，我们有在( a ，a ) d ( ”，o o ，最e ) 时，岔( a ，a ，) 一致接近，并且i ( a ，a ，) 也一致接近”因此由_ 矿和天_ ”可得 v k ，( 量) + i v 乞c i 忙) _ v 孙二扛+ ，a + ) ， n 耋簿兰舞v 柙耕一+ 哪r ) ( t v 啪+ ) 2 5 并且 北京工业大学理学硕士学位论文 q ( ) _ q + ) 盯 o ，使得f ( 童，a ，a ) f ( ，a ，a ) 一豇，则 由式( 4 1 7 ) 可知 即a n ) m 圭2 凡警咱 ( 4 1 8 ) 其中 f ，a ，n ) = ，( 孟) + 2 k q 忙) + ：j 凹( 1 + e 一。“2 ) f n1 令l ( 量) = i ：c t ( i ) o ，都有 n ， 三o ，a ) f 。r 2 ) = 一。o 现在我们考虑修改的罚函数法，其相应的修改罚函数为 f 扫，a ，口) = 。 一墨；+ 2 a 1 0 一1 f o g ( 1 + e 。( 。2 2 ) + 2 a 2 0 一1 z p g ( 1 + e 一。5 2 ) v ：。f + ，a + ，a ，= ( ；一：二：。) 所以对任意a 1 ，v ：。f ( 矿，”，a ) 都正定，并且有 = ( o ，2 ) = d r g m 伽 f o ，a + ，。) 。r 2 ) 与经典拉格朗日函数相比，修改的罚函数法有许多好的性质例如，在 函数的解处有定义，在可行域内保持原有函数的光滑性，并且其二阶海森阵正 定，也就是，即使对非凸规划问题，修改的罚函数在解的邻域内也严格凸 北京工业大学理学硕士学位论文 结论 本文提供了一种解决不等式约束问题的修改的罚函数方法，与经典拉格 朗日函数相比，修改的罚函数法有许多好的性质，修改的罚函数存在解，且在 解的邻域内保持目标函数和约束函数的光滑性在二阶最优性条件满足的情 况下，当罚参数足够大时，对于不等式约束的任何正的拉格朗日乘子，修改的 罚函数总存在全局最小值这一方法避免了函数m o z 霸o ) 的不可微性，且对 于足够大的罚参数，修改的罚函数法在二阶最优性条件满足的条件下线性收 敛，在每次校正拉格朗日乘子后增加罚参数能达到超线性收敛 本文提出的修改的罚函数方法在第七步迭代用信赖域算法求解，目的是 用信赖域算法的优点来加快收敛速度，以达到预期的结果 3 6 参考文献 参考文献 1g d p i l l oa n ds l u s i d i - b i g g s ，a 礼口叼m e n t e d 三叼m 凹f d n 加n c “帆叫i 地 妇r 啦m 口e de 。口c 打l e s sp 7 d p e 九e e s ，s i a mj o u r a lo no p t i m i z a t i o n ，1 2 ( 2 0 0 1 ) 3 7 6 4 0 6 2c c h e a d0 lm a n g a s a r i a n ，胁沈伽gm e 纳d d ，。rc d n e z 伽e 弘8 f 撕e s a 住d “n e 8 rc o 竹巾f e m e n t 8 掣p r d 6 f e m s ，1 9 9 4 3a r c o n n ，n i mg o u l da n dp l 7 工b i n t ，a9 f d 6 口坳c d 竹 e 憎e 疵工凹m n g i 口n 6 仃e ro 冶d t i 纳m ，d rd p 胁7 l i z b “d 仃叫i 晓9 e 仃e r 口“仃叼u 口? 甜yc 口n s 舌r - 口讯拈口仃d s i 巾f e6 d t n 出，m a t h e m a t i c so fc o m p u t a t i o n ，6 6 ( 1 9 9 7 ) 2 6 1 2 8 8 4a l d o n t c l l e va n dw w h a g e r ，三印c i 拓f d ns t d 6 删掣，d r s t 口t ec d n s t m 讥甜 n o n “n e o r 印“m 凸lc o n t r d l ，s i a mj o u m a l o nc o t r o la n do p t i l i z a t i o n ( 1 9 9 8 ) 6 9 8 7 1 8 5m c p i a ra j l ds a z e n i o s ，0 ns m o d 饥伽g 口c tp e 竹d f 坷如n c “d n s ，d r c d n u c o n s t r a 讯甜d p t l m l z 口t 如n ，s i a mj o u r n a l o no p t i m i z a t i o n ，4 ( 1 9 9 4 ) 4 8 6 5 1 1 6k m a d s e na n dh b n i e l s e n ，a 鼻n 乱e5 m d d t h 锄gn 幻d n t h m ，d r “礼e 8 rf l e s t i l o t i d n ，s i a mj o u r n a lo n0 p t i m i z a t i o n ，3 ( 1 9 9 3 ) 2 2 3 2 3 5 7o l m a n g a s a r i a n ，ac d 仃出t i d nn u m 6 e r ，d r 绒睁他n t i 0 6 f ec d n 讯e 口u 口 倒e 5 ，m a t h e m a t i c so fo p e r a t i o nr e s e a r c h ，1 0 ( 1 9 8 5 ) 1 7 5 1 7 9 3 7 _ 北京工业大学理学硕士学位论文 8d g o l d f a r