（应用数学专业论文）非线性二层规划的平衡点算法研究.pdf

。一 厂一1ffjmifjiffjf： 福建师范大学硕士学位论文y 18 0 7 0 6 5 自= = = = = = = = ；= ；= = = = = = 目自= = = 自= ；= = = = 昌= = = = = = = = = = = = = = = = = = = 昌= = = = = = = = = = = = = = = = = = = = = = = = = = = = ；= ；= = = = = t e = = = = = = = = 一 a b s t r a c t t h i sp a p e rd i s c u s s e st h et w ot y p e so fs p e c i a ln o n l i n e a rb i l e v e lp r o g r a m m i n g p r o b l e m sa n dt h e i ra l g o r i t h m s i ti sm a i n l yc o m p o s e do ft h r e ep a r t s i nt h ef i r s tp a r t ，w ei n t r o d u c em a n o e lc a m p e l o sa l g o r i t h m sf o rt h el i n e a rb i l e v e l p r o g r a m m i n gw i t ho n l yn o n - n e g a t i v ei nt h eu p p e rl e v e l ，w h i c hf i n dt h ee q u i l i b r i u m p o i n tf o rt h i sl i n e a rb i l e v e lp r o g r a m m i n gb ym e a n so ft h es i m p l e xm e t h o d i nt h es e c o n dp a r t ，w ec o n s i d e rt h en o n l i n e a r l yb i l e v e lp r o g r a m m i n ga n dg i v e i t sa l g o r i t h mb ym e a n so fm a n e o l sa l g o r i t h mf o rt h ee q u i l i b r i u mp o i n t f i n a l l y , w e p r e s e n ts o m en u m e r i c a le x a m p l e st od e m o n s t r a t et h ec o n c r e t es t e p so ft h ea l g o r i t h m i nt h et h i r dp a r t ，i n s p i r e db ym a n e o l sw o r kf o rt h el i n e a rb i l e v e lp r o g r a m m i n g ， w ec o n s i d e rt h eb i l e v e lp r o g r a m m i n gw h i c hi so b t a i n e db yr e p l a c i n gt h eu p p e ro b - j e c t i v ef u n c t i o ni nt h eo r i g i n a lm a n e o l sm o d e lw i t haq u a d r a t i cc o n c a v ef u n c t i o n ， a n dg i v ei t sa l g o r i t h mb ym e a n so ft h es i m p l e xm e t h o df o rl i n e a rp r o g r a m m i n ga n d l e m k ea l g o r i t h mf o rt h eq u a d r a t i cp r o g r a m m i n gw i t hl i n e a rc o n s t r a i n t s ，a n ds h o w i t sl o c a lo p t i m a l i t y f i n a l l y , w ep r e s e n ts o m en u m e r i c a le x a m p l e st od e m o n s t r a t e t h ec o n c r e t es t e p so ft h ea l g o r i t h m k e y w o r d s n o n l i n e a r l yb i l e v e lp r o g r a m ，e q u i l i b r i u mp o i n t s ，t h es i m p l e xm e t h o d ， t r u s t r e g i o nm e t h o d ，l e m k ea l g o r i t h m i i - 。_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 。_ _ 。“。 福建师范大学硕士学位论文 中文文摘 本文主要探讨两类特殊的非线性二层规划问题的求解算法文章的结构安排如 下 第一章分为三个小节第一节概括了目前国内外关于二层规划问题的研究情况 和主要成果，指出了二层规划的数学模型有着广泛的实际应用背景和重要的理论意 义第二节引出了一类特殊线性二层规划的数学模型： m a x f l ( z ，y ) = c t x + 彦耖 s t x 0 ys 1 帆戥 、(lbp) m a xy 2 ( z ，y ) = d r y s t a l x + a 2 y 口； y 0 其中z r m ，y r m ，c 1 r m ，c 2 ，d r m ，a l r m x n l ，a 2 r e l , x n 2 详细介绍 了mc a m p e l o 关于这类特殊线性二层规划的平衡点算法，这是本文研究的主要理 论依据第三节指出了本文所做的主要工作 第二章我们考虑下列二层规划模型： m a xf l ( x ，y ) = 1 ( z ) + 2 ( ) s t x 0 ys o l v e s ：( n l b p l ) m a x 厶( ) s t g j ( x ，y ) = g j i l ( x ) + g j 2 ( y ) o ，j = 1 ，2 ，价 y 0 其中 l ( z ) ，q j l ( z ) ，y 1 2 ( y ) ，止( 耖) ，g j 2 ( y ) 分别是关于x 舻，和y r n ：的二阶连 续可微函数，j = 1 ，2 ，仇我们在每个迭代点上利用了t a y l o r 展式的线性逼近 的方法构造线性二层规划，再用m c a m p e l o 的平衡点算法解这个线性二层规划， 得到新的迭代点由此通过在小范围内对每个非线性函数进行t a y l o r 展开并用线 i i i l 爿 llllil，ll一-_-一 福建师范大学硕士学位论文 性部分逼近来实现了从非线性到线性的转化，我们在迭代点附近可将( n l b p l ) 转 化为下列线性二层规划： mm m a x c 1 1x + c 2 1y s t z 0 可s 。1 w 8 ：( l b p l ) m a xd r y 8 t a k x + 4 l 可扩 y 0 我们给出了非线性二层规划( n l b p l ) 的平衡点算法( 算法1 ) ： 1 取初始点z 1 = ( x 1 ，y 1 ) q 分别取定x 和y 的步长限制7 1 = ( r ，1 。) 0 和s 1 = ( s i ，s n l ：) 0 ，令k = 1 ，取收缩系数0 0 这样，线性二层规划( l b p ) 便可转化为： m a x c t x + c y m ( 肛t u + i t y ) s t a l x + a 2 y + u = a x 0 ，y 0 ，0( 尸( m ) ) 4 多一= d 肛0 ，0 其中u 胛，弘胪，彤。在p ( m ) 中，我们记 名= ( 重) ，c = ( 喜) ，s = ( 三) ， a = ( a a 2i ) ，d = ( o 一，a t ) 这样( p ( m ) ) 便可表示为： m a x 砌( z ，8 ) = c t z m s t z s t z z ，s s 其中z = _ z 舻：a z = a ，z 0 ) ，s = s 舻：d s = d ，s o ) 点( 牙，吾) 称为p ( m ) 的平衡点，如果存在一m 0 ，对任意m 丽，总成立着 m a x f m ( 5 ，8 ) ：8 s ) = f m ( 孑，可) = m a x f m ( z ，互) ：z z ) 很显然，由于m 可以取任意大的数，函数砌( z ，s ) 的极大值只能在某个平衡点处 取到 在( p ( m ) ) 中，如果z 和s 中有一个是已知的，那么这个规划便是线性规划 了，这两种情况分别为： m a x 砌( 牙，s ) = ，牙一m s t 牙 ( 尸( m ，牙) ) s t s s 、。“ 4 l 一 一 0 f 0 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - 。 _ _ _ _ _ _ _ _ _ 。- 。1 。 氐 q 福建师范大学硕士学位论文 m a x f m ( z ，吾) = c t z m , s t z s t z z 显然，我们可以用单纯形法【5 8 】来求解上述两个线性规划 这里给出平衡点的概念，定义点( 牙，琴) 是平衡点当且仅当牙和；分别是线性 规划( p ( m ，可) ) 和( 尸( m ，乏) ) 的解由于线性规划的最优解总在顶点处达到，故 ( 乏，吾) 乙，其中乙和分别是z 和s 的顶点集 令( 乏，吾) 乙& ，j = 【1 ，2 ，佗) bcj 是线性规划( p ( m ，蚕) ) 的基变量 的一个下标集，n = j b a b 和a n 分别表示线性规划( 尸( m ，可) ) 的一个基矩 阵和一个非基矩阵下面我们可以列出求解( p ( m ，吾) ) 的初始和最优表格形式 瑶商 a ba n 0 m 一霸一露 0 c 丢c 罨 0 瑶z 焉 ia n = a b - 1 a n - 2 b = a b - l a mo 器= 露a 一襄0 = 露 2 b 0 磊= c 焉一c 丢么 - - c t - z b 设e i 表示第i 个分量为1 其余分量为0 的几维列向量，a 表示矩阵a 的 第i 列，a k i 表示矩阵4 的( k ，i ) 位置的元素令s ( z ) = s s ：z t $ = o ) - ， z ( s ) = z z ：z t s = o 令五i = a b l a t ，磊= 岛一c 暑a ，g i = ln 。l ，i e i ，+ = n ：磊 o ) ，n + o = i n + ：西 0 ，| s s ( 牙) ，s t 8 t g i = o ) 对 于i n ，称g i 是退化的，若i n f k s z k a k i ：a 航 o ) = 0 称集合+ 0 是关于基 矩阵a b 是完全退化的，若n + o 0 且对于任意i n + 0 ，g i 都是退化的 令( 牙，否) 磊x & ，j = 1 ，2 ，佗) ecj 是线性规划( p ( m ，牙) ) 的基变量 的一个下标集，r = j e d e 和d r 分别表示线性规划( p ( m ，牙) ) 的一个基矩 5 福建师范大学硕士学位论文 阵和一个非基矩阵下面我们可以列出求解( p ( m ，牙) ) 的初始和最优表格形式 s 荟s 丢 d ed n d m 一露一霸 0 s 荟s 夏 l 西r = d e - 1 d rd e - l d m0 一绉= 一绉+ z 刍2 r0 = 诌昆 设e j 表示第j 个分量为1 其余分量为0 的礼维列向量d j 表示矩阵d 的 第j 列，d k j 表示矩阵d 的( 尼，j ) 位置的元素令z ( s ) = z z ：z t 8 = o ) ， s ( z ) ： 5 s ：z t $ ：o ) 令岛：d e l d j ，h j ：f d j1 ，歹冗，础：d 冗： 苟= o ) ，r 0 0 = d r o ：弓= o ) 这里，我们需要作如下假设： 假设：若s s ( 牙) ，则对所有i n ，有s t g t 0 显然，当孑是个非退化顶点时该假设成立，在这种情况下a b 是唯一的基矩 阵由于牙是m i n s r z ：z z ) 的一个解，最优下降值s 丁g i = s 罨一s t a b l a 非 负 这时，m c a m p e l o 的平衡点算法可归结如下： m c a m p e l o 算法： 1 若zxs = 仍，则( l b p ) 不可行否则，取z o z ，令k = 1 2 用单纯形法解( p ( m ，z o ) ) ，得到g k 乱 3 用单纯形法解( 尸( m ，驴) ) ，若无界，则l b p 无界否则，得到砂玩，这样， ( 砂，砂) 是一个平衡点 4 在平衡点( 2 k ，g k ) 处确定+ 0 6 f 0 ， k 福建师范大学硕士学位论文 5 若n 十o = 谚，则驴是( l b p ) 的一个局部最优解 若n + o 仍且完全退化，这时算法失败，即无法保证平衡点给出( l b p ) 的一个局部极小点 若n + o 仍且不完全退化，则存在i + o 使得q 是非退化的 6 取孑七+ 1 a r g m i ng 歹s ：s s ( 砂) ) 令k 圭k + 1 ，转3 0 3 本文主要工作 本文主要探讨两类特殊的非线性二层规划问题的求解算法 ( 1 ) 考虑将原模型中上下层目标及下层约束用二阶连续可微凸函数来替代， 得到第一类特殊非线性二层规划问题，即 m a x ( z ，y ) = 1 ( z ) + 2 ( y ) s t x 0 妒0 1 啷：，、( n l b p l ) n l & x 如( 可) s t g j ( x ，y ) = g 歹l ( x ) + g j 2 ( y ) o ，j = 1 ，2 ，m y 0 其中 l ( z ) ，缈l ( 刀) ， 2 ( 可) ，2 ( 可) ，g j 2 ( y ) 分别是关于x r n l 和y r n z 的二阶连 续可微凸函数，j = 1 ，2 ，m 这里给出了这种情况下的平衡点算法，并通过典 型算例来展示了算法的具体步骤 ( 2 ) 考虑了将线性二层规划中上层目标函数用一个二次凹函数来替代，得到 第二类特殊的非线性二层规划问题，即 m a xf ( x ，y ) = z r 盈+ z t 两+ r 动+ d r z + e t y s t x 0 s。lves：(nlbp2) m a xd r y s t a l x + a 2 o ； y 0 7 r ，； 福建师范大学硕士学位论文 其中f ( x ，y ) 是二次凹函数二这里，在m a n e o l 的平衡点算法基础上，构造求解二层 规划问题( n l b p 2 ) 的算法，并给出理论证明最后也通过了算例来展示了算法的 具体步骤 8 第1 章非线性的二层规划的平衡点算法 第1 章非线性的二层规划的平衡点算法 本章我们考虑下列二层规划模型： m a xf l ( x ，y ) = f l l ( x ) + f 1 2 ( y ) s t z 0 炉o l v e s ：p ，、( n l b p l ) m a x 厶( y ) s t 缈( z ，y ) = g i , ( x ) + g j 2 ( y ) o ，j = 1 ，2 ，m y 0 其中 1 ( z ) ，缈1 ( z ) ， 2 ( ) ，2 ( ) ，g j 2 ( y ) 分别是关于x r , u 和y 舻。的二阶连 续可微凸函数，j = 1 ，2 ，价本章我们在每个迭代点上利用了t a y l o r 展式的线 性逼近的方法构造线性二层规划，再用m c a m p e l o 的平衡点算法解这个线性二层 规划，得到新的迭代点由此通过在小范围内对二次函数缈( z ，y ) 进行t a y l o r 展开 逼近来实现了从非线性到线性的转化，给出了非线性二层规划( n l b p l ) 的平衡点 算法最后，我们通过算例来展示了算法的具体步骤 1 1 非线性到线性的转化 考虑下列二层规划模型： m a x ( z ，y ) = 1 ( z ) + 2 ( ) s t x 0 ys o l v e s ： m a xf 2 ( u ) s t 绑( 彩，y ) = g j l ( x ) + g j 2 ( y ) o ，j = 1 ，2 ，m y 0 其中 1 ( z ) ，缈1 ( z ) ， 2 ( ) 尼( ) ，g j 2 ( y ) 分别是关于x r n l 和y 舻2 的二阶连 续可微凸函数，j = 1 ，2 ，m 令 q = ( z ，y ) i g j ( z ，y ) = g 歹l ( x ) + g j 2 ( y ) o ，j i = 1 ，2 ，m ，。0 ，y o ) 9 r r 给定( 扩，y 七) q ，将 1 ( z ) ，缈l ( z ) ， 2 ( ) ，2 ( 秒) ，乃2 ( 可) 分别在扩和y k 展为t a y l o r 级数，并取线性近似，得到线性二层规划问题： m a x f l l ( x 詹) + v 1 ( 扩) ? ( z z 七) + 2 ( 扩) + v 2 ( 七) t ( 一扩) s t z 0 m d , x 如( 七) + v s ：( u 后) t ( 可一可惫) s t g i l ( x ) + v g 了l ( x 七) t ( z x k ) + 彩2 ( 秒七) + v 缈2 ( 詹) t ( 一y k ) 0 ， j = 1 ，2 ，m y 0 ( 1 1 2 ) 由于用线性函数逼近非线性函数时，一般只在展开点附近近似程度较好，因此， 我们要对变量的取值范围加以限制我们取步长限制0 哆r ，0 s q k r 使得 i 一露i 咭p = 1 ，2 ，n 1 ) 和i 纨一鳝i s ：( g = 1 ，2 ，礼2 ) 则我们有下列 线性二层规划： 令 m a x f 1 1 ( x 七) 十v 1 ( z 七) 丁( z x k ) + 2 ( 可七) + v 2 ( 扩) r ( 秒一y k ) s t 1 昂一露i 咭，p = l ，2 ，n 1 刀0 m a x 尼( 耖彪) + v 厶( 局) t ( 耖一y 詹) s t 夕j l ( x 知) + v 彩1 ( z 七) ? ( 彩一彩七) + 仍2 ( y 七) + x t g j 2 ( 可七) 丁( y 一耖七) 0 ， j = 1 ，2 ，m l 蜘一站i s q k ，口= 1 ，2 ，死2 y 0 ( 1 1 3 ) ( 前) 丁 ( 避) t e l = v f l l ( x 后) ，c 2 = v 2 ( 可后) ，d = v ，2 ( ) ， ( v q n ( x ) ，v q 2 1 ( x 庇) ，v 9 m 1 ( 扩) ) ， ( v 9 1 2 ( y 七) ，v 眈2 ( 犷) ，v 夕m 2 ( 秒七) ) ， 口屉=一 1 0 ( 1 1 4 ) 矿扩 勺 ? t 州 嗲嗲 扩 “ 2 2 们 她勉 耽仇。 v 一 一 一 ) ) n ， 扪，肌， 产 扩驴 ，憎u“：钛 引引 屹 仇仍 纸 + + ；+ 后 k 舭舭 冰 p p p 时驴 拙 ，l，i 1 1 l 仇陇 h 耽耽 一 一 一 q q ， 妙 仇眈 m 则我们有下列线性二层规划问题： 令 1 m m a x e 1 1x 上c 2 1y s t x 0 ys o l v e s ： m a x d r y s t 五i z + a l 口詹 i 一硝l 哆，p = 1 ，2 ，n l i 蜘一鳝i s ：，q = 1 ，2 ，几2 y 0 a：厂霉。、，a5：厂曼：、， 扛 个t m a x c 1 1z + c 2 。y s t x 0 ys o l v e s ： m a xd r y s t a k x + a 5 可a 詹 y 0 1 1 ( 1 1 5 ) ( 1 1 6 ) ( 1 1 7 ) ( 1 1 8 ) 福建师范大学硕士学位论文 1 2 扩展平衡点算法 下面我们给出求非线性二层规划( n l b p l ) 的扩展平衡点算法： 算法l ： 1 取初始点z 1 = ( x 1 , y 1 ) q 分别取定x 和y 的步长限制7 1 = ( r ，1 。) 0 和s 1 = ( s ，s n l 。) 0 ，令k = 1 ，取收缩系数0 0 接着，对于规划( 1 3 2 ) ，我们可作以下转化： ( 1 3 2 ) 1 引入松弛变量w 1 ，w 2 ，u 3 ，w 4 ，0 - ) 5 ，把下层问题中的不等式约束转化为等式约束 2 把下层问题用它的k k t 条件进行取代 3 利用罚函数法把k k t 条件中的互补约束写进目标函数里，罚参数取为m 0 4 令 c2z2s2 0 工， p 1 2 p 3 4 5 g 斟w 砌 枷似 似 峦 9 w a a a o 盖 o o 0 l 0 0 o 重o a 0 韭0 a 0 丑o 0 0 0 l o l o l丑。靴o，fj-i_-_-_-_-、 = 0 凰 福建师范大学硕士学位论文 即 d o = ( o 一1 1o1 o 一1 ) ，d = 1 这样，问题( 1 3 2 ) 便可化为： m a xf m ( z ，s ) = c t z m s t z s t z z = z ：b o z = b o ，z o ) ， s s = 5 r 3 ：d o s = d ，s o ) ( 尸( m ，z ，s ) ) m a x x + y m ( # l w l + # 2 w 2 + 肛3 u 3 + p 4 龇+ # 5 w 5 + u y ) s t z + y + w 1 = 萼 x + w 2 = y + w 3 = x 一龇= ； ( 1 3 3 ) y w 52 著 p 1 + 肛3 一p 5 一= 1 x 0 ，y 0 ，w 1 0 ，w 2 0 ，w 3 0 ，w 4 0 ，w 5 0 ， 1 0 ，肛2 0 ，p 3 0 ，p 4 0 ，肛5 0 ，2 0 取z 2 = ( 互1 ，互1 ，互1 ，虿1 ，虿1 ，百1 ， ) ，将z ? 代入( 1 3 3 ) 得到线性规划： m a x1 一m ( ；p 1 + p 2 + p 3 + 肛4 + 肛5 + 1 1 ) s t a 1 + a 3 一5 一2 = 1 p 1 0 ，肛2 0 ， a 3 0 ，p 4 0 ，弘5 0 ，j 0 用单纯形法解( p ( m ，z o ，s ) ) 得到s = ( 0 ，0 ，0 ，0 ，1 ，0 ，o ) 丁，事实上， 肛1p 2p 3肛4p 5 1101011 三三三三三三 o 228888 1 4 ( 尸( m ，哿，s ) ) 肛1p 2 p 3 p 45 1101011 1 8i虿80 百8石848 ， 第1 章非线性的二层规划的平衡点算法 将s 代入( 1 3 3 ) 得到线性规划： m a xx + y m w 3 s t x + y + w 1 = 萼， x + w 2 = y + w 3 = z w 42 毒 y w 52 蓄 x 0 ，y 0 ，w 1 0 ，w 2 0 ， 忱0 ，w 4 0 ，w 5 0 用单纯形法解( 尸( m ，z ，s i ) ) 得到最优解 ( 尸( m ，z ，s ) ) z t = ( ；，；， ，0 ，0 ， ， ) 丁，事实上， z yw 1w 2w 3w 4w 5 11l0000 3 2 10010 00 o 8 0 1001oo 5 8 一1000010 3 8 0100001 3 8 1 一l00m000 z yw 1 w 2w 3 w 4w 5 1 110000 3 2 1001000 5 8 0 100100 5 8 1000o10 3 8 010000 1 3 8 1 1 一m 00000一m 石 1 5 福建师范大学硕士学位论文 令j = 1 ，2 ，3 ，4 ，5 ，6 ，7 ) 从上式得，基变量和非基变量的下标集分别为b = 氨 zyw 1w 2 w 30 3 4w 5 1010100 7 8 10 01000 5 8 01001o0 5 8 1000010 3 8 0 000 1 0 1 2 8 1000m + 100 5 8 彩u 1w 2w 3 w 4 w 5 001 1 100 1 4 10 01000 5 8 01 00100 5 8 0 00 1010 2 8 0 00 0101 2 8 0001m + 10 0 5 4 、l 0 0 1 0 0 ，。一 = a 、llilllii， 1 o l o o 1 1 o o o ，i-ii_li_li-_-_il_iii、 = b a 酌卟到 0 0 1 旷0 0 l 0 0 0 l i 1 0 o 0 0 和 1 o 1 o o l ” 1 1 o o o 文 卫 = 上 0 q a z 2 + y 2 在z 1 点展开并取一次近似，取r 1 = 一= 吾，s 1 = s 。= ，计算得到z 2 不属于可行域q ，故返回z 1 取7 1 = o = 去，s 1 = p s o = 而1 ，我们有下列二层规划 类似( 1 3 2 ) ，我们有 m s & x z 十秒 s t z 0 ys l o v e s ： m a xy s t z + y 丽5 7 z 1 1 1 6 y 丽1 1 z 杀 y 杀 0 m a x x + y m ( # 1 w 1 + # 2 w 2 - i - # 3 w 3 - i - p 4 龇+ p 5 + v y ) s t z + y + w 1 = 嚣 z + w 2 。丽1 1 y + w 3 = 丽1 1 0 z 一龇2 素 0 秒一w 52 素 p 1 + 肛3 一肛5 一= l z 0 ，y 0 ，w 1 0 ，c d 2 0 ，w 3 0 ，w 4 0 ，u 5 0 ， p 1 0 ，肛2 0 ，p 3 0 ，肛4 0 ，p 5 0 ，2 0 将霹= ( ；，百5 ，而7 ，丽1 ，丽1 ，丽1 ，去) t 代入( 1 3 5 ) 并求解得s i = ( o ，0 ，0 ，0 ，1 ，0 ，o ) r 1 7 ( 1 3 4 ) ( 1 3 5 ) 福建师范大学硕士学位论文 将s ! = ( 0 ，0 ，0 ，0 ，1 ，0 ，o ) t 代入( 1 3 5 ) ，有下列