（运筹学与控制论专业论文）双层规划中几个问题的研究.pdf

山东科技大学硕士学位论文 摘要 摘要 数学规划在决策中的应用，大多处理的问题要么仅有一个单一的目标，要么一系 列的目标同时达到最优，并且所有的目标都由唯一的决策者决定，同时它控制所有决 策变量。在许多实际问题中，需要考虑系统的层次性，即在整个系统中有不止一个决 策者，并且它们控制不同的决策变量和目标函数，多层规划是解决这类问题的一种有 效数学工具。多层规划解决了在递阶系统决策过程中的协调问题，它使得递阶系统某 层中的决策者有自己的可行集，这个可行集部分地由其它层决策变量决定，同时，它 的决策也影响其它层的决策行为。不像多目标数学规划，多层规划强调系统的非合作 性。 仅涉及两层的多层规划，称之为双层规j l j ( b i l e v e lp r o g r a m m i n g ) 。实际上，多层 规划可以看作是一系列双层规划的复合。 双层规划问题( b i l e v e l p r o g r a m m i n g p r o b l e m ) n t - 看作静态s t a c k e l b e r g 游戏，决策 是有序的且两者之间禁止合作，但上层的决策能影响下层的行为；而下层的反应可以 部分地影响上层的决定。 本文讨论了两类双层规划。一是线性双层规划( l i l l e a r b i l e v e l p r o g r a m m i n g ) ，即上、 下层目标函数及约束条件都是线性的，所有决策变量为连续的情况。本文在研究线性 双层规划的有关性质之后，给出一种极点方法能找到线性双层规划的全局最优解。二 是凸双层规划( c o n v e xb i l e v e lp r o g r a m m i n g ) ，即上层试图最小化一个非线性凸的目标 函数，而下层的目标函数是在一连续决策空间上的凸二次函数，所有约束是线性的情 况，本文提出一种分枝定界方法来找到它的全局最优解。 本文还对双层规划的最优解作了进步的研究，举例说明了双层规划的最优解一 般不是p a r e t o 最优，并给出5 种有效解的定义，指出所定义的有效解更有着重要的实 际意义。 关键词：双层规划，线性双层规划，凸双层规划，全局最优解，极点算法，分枝 定界，p a r e t o 最优，有效解 生查型茎查兰堡圭堂堡堡兰j 旦生 a b s t r a c t t h eu s eo fm a t h e m a t i c a lp r o g r a m m i n gi nd e c i s i o nm a k i n gi su s u a l l yt os o l v ep r o b l e m s w i t he i t h e ras i n g l eo v e r r i d i n go b j e c t i v e ，o rav a r i e t yo fo b j e c t i v e sd e a l tw i t hb ys t r i v i n g t o w a r da l lo f t h e ms i m u l t a n e o u s l y a l lo b j e c t i v e sa r ea s s u m e dt ob et h o s eo fs i n g l ed e c i s i o n m a k e rw h oh a sc o n t r o lo v e ra l ld e c i s i o nv a r i a b l e s i np r a c t i c e ，ah i e r a r c h i c a ld e c i s i o n p r o b l e mm a y h a sm o r et h a no n ed e c i s i o nm a k e r s ，w h i c hh a v et h e i ro w nd e c i s i o nv a r i a b l e s a n do b j e c t i v e s ，a n dt h e nt h em u l t i l e v e lm a t h e m a t i c a lp r o g r a m m i n gi sas a t i s f y i n gt o o lt o s o l v et h e s ep r o b l e m s m u l t i l e v e lm a t h e m a t i c a lp r o g r a m m i n gs o l v e st h ep r o b l e mo f c o o r d i n a t i n gt h ed e c i s i o nm a k i n gp r o c e s si n ad e c e n t r a l i z e ds y s t e m i nt h ed e f i n i t i o n m u l t i l e v e lm a t h e m a t i c a lp r o g r a m m i n g ，a so n el e v e lo ft h eh i e r a r c h y , ad e c i s i o nm a k e rh a s 1 1 i ss e to ff e a s i b l es o l u t i o n sd e t e r m i n e d ，i np a r t ，b yt h eu p p e rl e v e l s ；c o n v e r s e l y , t h e d e c i s i o ni n s t r t u n e n t sh ec o n t r o l sm a ya l l o wh i mt oi n f l u e n c et h eo p e r a t i o n so ft h el o w e r 1 e v e l s ac l a s so fm u l t i l e v e lm a t h e m a t i c a lp r o g r a m m i n gi n v o l v e so n l yt w ol e v e l s ，a n da r e c a l l e db i l e v e lp r o g r a m m i n g i nn a t u r e ，am u l t i l e v e lm a t h e m a t i c a lp r o g r a m m i n gm a yb e r e g a r d e da sac o m p o s i t eo f b i l e v e lp r o g r a m m i n g ab i l e v e lp r o g r a m m i n gp r o b l e mi sp r e s e n t e di nt h ef o r mo fs t a t i cs t a c k e l b e r gg a m e b y a s s u m p t i o n ，p l a yi ss e q u e n t i a la n du n c o o p e r a t i v e h o w e v e r ，t h el e a d e rc a l li n f l u e n c et h e a c t i o n so ft h ef o l l o w e r st h r o u g has e to fc o o r d i n a t i o nv a r i a b l e sw h i l et h ef o l l o w e r s r e s p o n s e sm a yp a r t l yd e t e r m i n et h el e a d sp a y o f f t h i sp a p e ri sd e v o t e dt oa n a l y s i n gt w oc l a s s e so fb i l e v e lp r o g r a m m i n gp r o b l e m s f i r s t l y , t h el i n e a rb i l e v e lp r o g r a m m i n g ，w h i c ha l lo b j e c t i v ef u n c t i o n sa n dc o n s t r a i n t sa r cl i n e a r , a n d t h ed e c i s i o nv a r i a b l e sa r cc o n t i n u o u s b a s e do nt h el i n e a rb i l e v e lp r o g r a m m i n g sp r o p e r t y , ae x t r e m ep o i n t sa l g o r i t h ma l g o r i t h mi sd e v e l o p e dt h a tf i n d sg l o b a lo p t i m a s e c o n d l y , w e e x a m i n eac l a s so fb i l e v e lp r o g r a r n m i n g sw h e r et h el e a d e rt r i e st om i n i m i z eac o n v e x n o n l i n e a ro b j e c t i v ef u n c t i o n t h ef o l l o w e r so b j e c t i v ef u n c t i o ni sac o n v e xq u a d r a t i ci na c o n t i n u o u sd e c i s i o ns p a c e a l lc o n s t r a i n sa r ea s s u m e dt ob el i n e a r ab r a n c ha n db o u n d a l g o r i t h mi sd e v e l o p e dt h a tf i n d sg l o b a lo p t i m a 山东科技大学硕士学位论文摘要 i nt h i sp a p e r , w eg i v ef u r t h e rr e s e a r c ho nt h eo p t i m ao fb i l e v e lp r o g r a m m i n gp r o b l e m ， a n dae x a m p l et oe x p l a i nt h a tt h eo p t i m ao fb i l e v e lp r o g r a m m i n gp r o b l e ma r en o tp a r e t o o p t i m a w eg i v eo u tf i v ed e f i n i t i o n so fe f f i c i e n ts o l u t i o n ，w h i c hh a v ei m p o r t a n ts e n s ei n p r a c t i c e k e yw o r d s ：b i l e v e lp r o g r a m m i n g ，l i n e a rb i l e v e lp r o g r a m m i n g ，c o n v e xb i l e v e l p r o g r a m m i n g ，g l o b a lo p t i m a ，e x t r e m ep o i n t sa l g o r i t h m ，b r a n c ha n db o u n d ，p a r e t oo p t i m u m ， e f f i c i e n ts o l u t i o n 声明 本人呈交给山东科技大学的这篇硕士学位论文，除了所列参考文献和世所 公认的文献外，全部是本人在导师指导下的研究成果。该论文资料尚没有呈交 于其它任何学术机关作鉴定。 硕士生签名：耋艉沦 日 期：埘，f 乎 a f f i r m a t i o n id e c l a r et h a tt h i sd i s s e r t a t i o n ，s u b m i t t e di nf u w f l l m e n to ft h er e q u i r e m e n t s f o rt h ea w a r do fd o c t o ro fp h i l o s o p h yi ns h a n d o n gu n i v e r s i t yo fs c i e n c ea n d t e c h n o l o g y , i sw h o l l ym yo w nw o r ku n l e s sr e f e r e n c e do fa c k n o w l e d g e t h e d o c u m e n th a sn o tb e e ns u b m i t t e df o rq u a l i f i c a t i o na ta n yo t h e ra c a d e m i c i n s t i t u t e s i g n a t u r e ：耋栉论 d a t e ： 懈s 一旨 山东科技大学硕士学位论文 第1 章绪论 1 1 双层规划产生的背景 阶层性是系统的特征之一，对于大系统和复杂系统，层次性更是主要特征。社会 的发展和经济全球化的扩展，实际问题的规模越来越大，层次越加明显，结构更加复 杂，使得层次性的研究具有非常重要的意义，多层规划正是为了研究系统层次性问题 而产生的。 2 0 世纪7 0 年代以来，在各种现实的层次分散系统优化决策问题的研究中，人们发 现用传统的标准优化方法不能解决这些实际问题，在寻找各种特定方法成功解决这些 问题的过程中，逐渐形成了多层规划的概念和方法。 多层规划0 v l u l t i l e v e l p r o g r a m m i n g ) 原意是一集嵌套着的数学规划问题，即在约束条 件中含有优化问题的数学规划，研究的是多个各具日标函数的决策者之间按非合作和 有序的方式进行的相互作用任何一方的决策行为影响其它方的策略选择和目标实现， 但任何一方又不能完全控制其它方的选择行为。 在多层规划的应用中以双层规划( b i l e v e l p r o g r a m m i n g ) 最为常见，这是因为现实中 的决策系统大都可以看作双层决策系统，并且任何一个多层决策系统是系列双层决 策系统的复合，如中央和地方，公司和子公司，学校与各院系等。 双层规划是在研究非平衡经济市场竞争时提出的。1 9 7 3 年在b r a c k e n 和m e g i l l l l l 的文章中，出现了双层规划数学模型。1 9 7 7 年，在c a n d l e r 和n o r t o n ( 2 的科学报告中正 式出现了双层规划和多层规划名词。从2 0 世纪8 0 年代开始，双层规划引起大家的注 意，一些国家的学者开始集中研究，使得双层规划理论和求解算法的研究取得了较大 发展，并正逐渐形成一个新的运筹学分支。 1 2 双屡规划定义及主要特点 双层规划问题可以看作静态s t a e k e l b e r g 游戏，决策是有序的且两者之间禁止合作， 但上层的决策能影响下层的行为；而下层的反应可以部分地影响上层的决定。双层规 划是= 层决策问题的数学模型，它是一种具有二层递阶结构的系统优化问题，上层问 划是= 层决策问题的数学模型，它是一种具有二层递阶结构的系统优化问题，上层问 山东科技大学硕士学位论文 题和下层问题都有各自的目标函数和约束条件。上层问题的目标函数和约束条件不仅 与下层决策变量有关，而且还依赖于下层问题的最优解，同时下层问题的最优解又受 到上层决策变量的影响。也就是说，这种决策机制使得上级部门对下级部门的管理和 领导仅仅靠影响下层的决策环境间接来引导下层作出有利于整个系统的决策，而不允 许上层的直接介入和命令。 双层规划主要研究的是两个各具目标函数的决策者之间按有序的和非合作的方式 进行的相互作用。上层决策者优先作出决策，下层决策者在上层决策信息下按自己的 利益做出反应。由于一方的行为影响另一方的选择行为和目标的实现，并且任何一方 又不能完全控制另一方的选择行为，因此上层决策者要根据下层的反应做出符合自身 利益的最终决策。 根据以上双层规划的定义，双层规划研究的问题主要有以下几大特点： 乱层次性：是指研究的系统是分层管理的，各层决策者依次做出决策，下层服从 上层。 b 独立性：即下层并不是完全无条件服从上层，它有自己的相当的自主权。 c 冲突性：各层决策者有各自不同的目标，这些目标往往是相互矛盾的。 d 优先性：是指上层决策者优先做出决策，而下层决策者在优化自己的目标而选 择决策时，不能违背上层的决策。 c 自主性：就是说各层决策者各自控制一部分决策变量，以优化各自的目标。 制约性：意味着下层的决策不但决定着自身目标的达成，而且也影响着上层目 标的达成。因此，上层在选择策略以优化自己的目标时，必须考虑到下层可能采取的 策略对自己的不利影响。 g 依赖性：是指各层决策者的容许策略集通常是不可分离的，它们往往形成一个 相互关联的整体。 1 3 双层规划数学模型 在双层规划模型中，不同的决策者控制着相应的决策变量，并优化各自的目标函 数。上层决策者首先做出决策，下层根据上层的决策进行反应，以优化个人的目标函 数。因为双方可供选择的策略集是相互依赖的，上层的决策会影响下层的决策和目标 的实现；反之亦然。 2 山东科技大学硕士学位论文 设上层决策者控制的变量为x = ( x i ，x 2 ，_ ) 7 jcr 4 ；下层决策者控制的变量为 y = ，y 2 ，) 7 ycr 4 ，双层规划数学模型可描述为： 鼍当俨( x - y ) ( 1 1 a ) s t g ( i ，y ) 0 ( 1 1 b ) 等当矿( x ，y ) ( 1 i c ) s t g ( x ，y ) 0 f 1 1 d ) 其中f , f x x y r 1 ，g j r ”r “斗r ，g ? 彤x r 4 - - - ) r 2 ，h f ，g ，g 为二级连续 可微函数。集合盖和集合y 包含了变量的其它约束，如变量的非负性或整数要求等。 例1 1 m i n f = 2 x + y i 2 y 2 s t 0 s 工1 ，其中y l ，m 解 血，y ly 2 s t x + m + y 2 = 1 弘，y 2 0 对上述问题，上层只有一个决策变量x ，下层控制两个决策变量y ，和y ：。当o x f ( x * y ) ，称( x * y + ) 为( l b p ) 的全局最优解，简称全局解。 由子( l b p ) 的上、下层约束都是线性的，所以( l b p ) 的约束域s 是r 8 “上的一个多 面体。对给定的上层允许决策xe t ，下层问题的合理反应集m ( x ) 定义了下层决策者 对上层决策的反应，雨( l b p ) 的诱导域d 给出了整个问题的可行解集合，即上层决策者 可以优化的空间。 根据线性规划一般理论可知，如果( l b p ) 的约束域s 无界时，上层允许决策集合， 也可能无界，从两( i 皿p ) 可能无有限解。另外由第l 章例1 1 可知，对给定的上层允许 决策x e t ，若下层最优解不唯一，即合理反应集m ( x ) 不是单值映射，则可能导致( u p ) 无确定的最优解。根据以上讨论，为保证( l b p ) 的全局最优解存在，以下两个假设是必 要的。 假设a ：( l b p ) 的约束域s 是非空有界的，即s 是非空紧凸集。 假设b ：任取x t ，下层问题在s ( x ) 上有最优解且难一，即合理反应集m ( x ) 是 单值映射。 假设a 要求( l b p ) 的约束域s 是异“上的一个多胞形，从而由线性规划性质可知， ( l b p ) 一定有全局最优解；假设b 确保( l b p ) 在可行解集合d 上能得到确定的最优解。 例2 1m i f = 一y s 7 x o ，其中y 解 m m f = y ， 5 j 一x 一2 y - 1 0 x 一2 y s 6 2 x y s 2 1 工+ 2 y 3 8 8 山东科技大学硕士学位论文 线性双层规划 一x + 2 y 1 8 v 0 例2 1 的上、下层各控制着变量工和y ，图2 1 给出了它的约束域根据图2 1 可知，上层允许决策集合t = 缸：0 x 1 6 ) 。对任意的x t ，下层问题的可行解集合 对应于过点z 垂直于横轴的直线被该多面体s 所截得的线段，由于下层目标函数是对y 求极小，所以整个合理反应集是垂直线段的最下端对应的点，即线段a b ，b c 和c d 上所有点都为问题的可行解。 f ( 0 ，9 ) a ( o 。5 ) x 图2 1 例2 1 的约束域和诱导域 例2 1 的全局最优解在点d ( 1 6 1 1 ) 上达到，即x * = 1 6 ，y * = l l ，+ = 一1 1 ，厂+ = 一1 1 。 在点e ( 1 0 ，1 4 ) 处，上层更优，但e 点不是可行点，如果上层决策者选x = 1 0 ，则下层决 策者的最优选择应为y = 2 ，此时下层目标函数更优但上层较差。点a ( 0 ，5 ) 是例2 1 的一 个局部最优解，但不是全局最优解。 根据例2 1 的几何意义，可以总结出线性双层规划有以下两个特点： 第一，可行解集合d 一般是非凸的； 第二，全局最优解可以在约束域s 的极点上找到。 山东科技大学硕士学位论文 线性双层规划 2 2 基本理论 定义2 3 设y c r 8 ，x 1 ，x 2 ，x “，五d r l f 一， = 1 ，如果4 x y 有x j y ( 1 f s ，) ，称】，对j 是弱凸的；如果丑x y ，且对丑 o 有x y ，称】， 对爿是严格弱凸的( 弱拟凸子集) 。 定义2 4 设k c 晨“是一个凸集，x o k ，如果x o 不能表示成足中其它两个顶点的 凸组合，称x o 是k 的一个极点。 定义2 5 设k c r ”是一个凸集，x o k ，p 是丘的一个凸子集，如果世中的任一 条闭线段只要有一个相对内点在p 中，这个线段的两个端点也在p 中，则称p 为世的 一个面。 根据以上定义可知，凸集k 的弱拟凸子集是由足的若干面的并组成。 为了求解线性双层规划，下面主要讨论( u p ) 解空间的几何意义。为了表示方便， 对( l b p ) 的一般形式( 2 1 ) ，可设c ：= 0 ，且假设a 和假设b 成立。 定理2 1 任取( x 1 ，y 1 ) ，( x ，y 7 ) 5 ， o ( 1s f r ) ，丑= l ，如果 i = l a ( x ，y ) d ，则对一切i = l ，2 ，有( x 7 ，y ) d 。 1 2 】 证明：假设( x 7 ，y 7 ) g d ，由d 的定义，存在y 使得( x 7 ，y ，) d ，且d ；歹 o ，所以乃d ：亨 d ；y 。 令( 簧，亨) = ( x ，y ) ，( ，y ) = 艺五( f ，y ) + t ( x ，矿) + 五( x ，y 7 ) 。由( 一，y ) ， 1 2 li = 1k j 1 ( x 卜1 ，y 川) ，( x ，y ) ，( x j + l , y “) ，( x ，y ) e s ，p o ( 1 f r ) ，宅 = 1 ，且s y od s 集， i = 1 得( 膏，歹) e s 。对固定的舅，有 1 0 山东科技大学硕士学位论文 线性双层规划 d r y = d 2 r ( ) k y l + + 1 y 。_ 1 + y 7 + “y p l + + 一y ) o ( 1 - i r ) ， = 1 ，使得( x ，y ) = 丑( x ，y ) 。由定理2 1 ，对一切 1s i r ，有 ，y ) d ，这与( x ，y ) 是d 的极点矛盾，所以推论成立。 推论2 1 2 若( x ，y ) 是s 的极点，且( x ，y ) e d ，则( x ，y ) 也是d 的极点。 证明：假设( x ，y ) 不是d 的极点，则存在扛1 ，y 1 ) ，( x l y 2 ) d ，0 五 o ，有( x ，y ) e d 。 山东科技大学硕士学位论文 线性双层规划 由于当r i g 时，( x 。，y ) 芒d ，所以当r i g 时，一定有丑= 0 ，即有 ( x ，y ) = ( x ，y ) ，丑0 ，丑= 1 。 记e = m i n f ( x 。, y m l i r ，由于s 是非空紧的，所以d 也是非空紧的，从而 线性函数f ( x ，y ) 在d 上有最优解。任取( x ，y ) d ，有 f ( x ，y ) = a ，( x i ，y ) 丑矗= 岛 i = if - l 若令r = m i n f ( x i , y ) ：1 i r ) = f ( x , y ) ，这说明f ( x ，y ) 在d 的极点( x ，y 7 ) 上达到 最小，所以定理成立。 推论2 2 1 在假设a 和假设b 保证下，( l b p ) 一定有最优解，且可在s 的极点上达 到。 证明：由定理2 2 和推论2 1 1 易证推论成立。 当上层给定某个允许决策x et 后，下层问题的最佳决策是解下列线性规划问题： n f i j n f ( x , y ) = d i y ( 2 2 8 ) s j b y b a x( 2 2 b ) y 0 ( 2 2 c ) 问题( 2 2 ) 的对偶规划为： m a x g ( u ，x ) = u r ( a x b )( 2 3 a ) s j 一u 7 b d j ( 2 3 b ) u 0 f 2 3 c ) 其中u r 9 ，记u = u r 9 ：一u r bs d ；，u o 为( 2 3 ) 的可行域。 定理2 3 ( x 弋y + ) 是( l b p ) 的全局最优解当且仅当存在1 1 u ，满足( x + ，y t u ，) 是下列 问题的最优解： m 。i ，n 。f ( x , y ) = c i x + d j y s t a x + b y b f 2 4 a ) r 2 4 b ) 山东科技大学硕士学位论文 线性双层规划 一u 7 b d ：( 2 4 c ) u 7 ( b a x b y ) = 0 ( 2 4 d ) ( u 7 b + d ；) y = 0( 2 4 e ) x o ，y 0 , u 0 ( 2 4 f ) 证明：对一对偶规划( 2 2 ) 和( 2 3 ) ，用k t 条件，易证定理成立。 定理2 3 中的问题( 2 4 ) 也称k t 模型，它是一个标准的数学规划，除非线性约束 条件( 2 4 d ) 和( 2 4 e ) 外，其它都是线性约束，应当容易求解，但实际上互补松弛项( 2 4 d ) 和( 2 4 e ) 非常难处理，需要有足够的技术来保证问题的可行性和全局收敛性。 2 3 线性双层规划求解算法介绍 自2 0 世纪7 0 年代以来，已提出了几十种求解线性双层规划的算法，主要有以下 几类不同的算法： 1 极点搜索法。利用推论2 2 1 和一般线性规划技术，在( l b p ) 约束域s 的极点上 寻找问题的全局最优解。c a n d l e r 和t o w n s l e y _ 【2 5 l 提出了第一个全局收敛算法，该算法通 过反复求解两个线性规划问题来获得( l b p ) 的全局最优解。b i a l a s 和k a r w a n 2 6 1 对约束域 s 的极点进行搜索，提出了“k 次最好”算法，该方法要用到凸多面体上的极点排序算 法，计算量和存储量一般较大。文 2 7 禾1 j 用约束域s 的极点与下层问题可行解集合上极 点之间的关系，也给出一种极点枚举法。 2 分支定界法( 或k - t 方法) 。根据定理2 3 ，该方法考虑k t 模型( 2 4 1 ，用分支 定界技术处理k - t 模型中的互补松弛项( 2 4 d ) 和( 2 4 e ) ，忽略或松弛这部分约束，得到 一个易于求解的标准线性规划，并用不同方法来保证最终满足互补松弛条件。文 3 】首 先提出一种分枝定界法，把问题转化为一个混合整数线性规划来求解，但效率不高。 b a r d 和m o o r e 【2 8 1 提出一种隐式满足互补松弛项的分枝定界方法，并证明效果比较好。 3 惩罚函数法。这类方法使用了非线性规划中的惩罚函数原理，将问题转化为带 有惩罚参数的非线性规划问题来求解。s h i m i z u 和l u 【2 9 利用外部惩罚法，构造了一个 全局收敛算法，贾富臣 3 0 】应用内点法，使( l b p ) 等价于一序列非线性规划问题，w l l i t e 和a n a n d a l i n g a m 3 1 在上层目标函数中添加下层问题的对偶间隙，将( l b p ) 转化为一个 山东科技大学硕士学位论文 线性双层规划 单层问题，提出了种全局收敛算法。 4 互补旋转法。b i a l a s 【3 2 l 等人第一个提出了一个互补旋转算法，该方法是将( l b p ) 转化成一个带参数的线性互补问题，然后用带参数的互补主元算法进行求解，但这种 算法不能确保全局收敛性，后来j u d i c 和f a u s t i n o 1 对其进行修正，提出连续线性互补 旋转算法，保证了算法的全局收敛性。 除以上四类主要算法外，还有其它一些求解线性双层规划的方法，不再一一介绍， 可参见文献【3 4 】【3 5 】【3 6 3 7 3 8 】【3 9 】【4 0 】。 2 4 算法与算例 求线性双层规划( l b p ) 约束域s = ( x ，y ) ：a x + b y b , x o ，y 0 的极点方法如下： 对a x + b ys b ，x 。，y 。，加入松弛变量z 。，有c a ，b ，e ， 封= b 。令 w 固删耻w 嘞，谢w 枷”m 嘲阶臁u 我们设w 的秩为“由于松弛变量的引进，睇p 为w p ( 。+ 。印) 的子阵，则显然有，= - p ) 。 记w = t w j ，w j ，u = ( u ： 7 ，其中w ，为r r 阶可逆矩阵。则等式约束w u = b 可以表 示成：w 。u ；+ w z u 。2 b ，u t = w ，b w w 2 u 2 ，我们令u 2 = o ，则u 。= w 1 b 。若u l = v v l 。b 0 ， 显然( w l b ，o ) 7 满足上述等式约束，此时我们称( w b ，0 ) 7 为等式约束w u = b 的基本 定理2 4 4 1 1 令k ： m y = p 。v o ，其中m 为m n 阶矩阵，m 的秩为，则k 的 这样求解约束域的极点，可归结为求等式约束w u = b 的基本可行解集。 山东科技大学硕士学位论文 线性双层规划 总结以上讨论，下面给出求解( l b p ) 全局最优解的一个极点算法，具体步骤描述如 第1 步引入松弛变量z 。，z ，将线性双层规划( 2 1 ) 的不等式约束，化为等式约 束c a ，b ，e ，匪 = b 。令w = c a ，b ，助，u = 习，约束可简记为 其中w 为p x ( n + m + p ) 阶矩阵，u 为月+ m + p 维向量。 第2 步求解问题( u ) o fw 的可行基矩阵，设有k 个，w 1 ，w 2 一，w k ，计算出基 可行解u 1 ，u 2 ，u 。去掉分量中的松弛变量分量部分，得线性双层规划( 2 1 ) 的不等式 约束的k 个基可行解( x ，y ) ，对它们按f ( x ，y ) 值的由小到大进行排序，可以没有差别地 记为x i ，y 1 ) ，( x ，y ) 。 鼍( 譬，y ) = d r y ( 2 5 a ) 第4 步若歹= y ，则( x i ，y 。) 为最优解，停止。若y 。y ，i = f + 1 ，转第2 步。 变量分量，得只含变量x , y 的基可行解，并按，( x ，y ) 值由小到大排序为：( 1 0 ，1 4 ) ，( 1 6 ，1 1 ) ， 山米科技大学硕士学位论文 图2 2 例2 1 的基可行矩阵 当面= 1 0 时，解( 2 5 a ) 一( 2 5 b ) 得歹= 王= 1 6 时，解( 2 5 a ) - - ( 2 5 b ) ，得歹= 1 1 ， f ( 0 ，9 ) a ( 0 ，5 ) 线性双层规划 0 。因为歹1 4 ，所以( 1 0 ，1 4 ) 不是最优解。当 所以( 1 6 ，1 1 ) 是最优解( 见图2 3 所示) 。 x 图2 3 算法解例2 1 的执行过程 所有求解线性双层规划问题的极点算法，关键是在于如何找出约束域s 的极点。 本算法通过解多个方程组找约束域s 的极点，是一种新的尝试。由于考虑了约束域所 有极点，算法最终能求得全局最优解。 1 6 o o o o 1 o l o o 0 1 0 0 o 0 吃七1 2 2 1 l q l l o 0 o o 1 o o o l o 1 o o o o 2 2 1 2 2 l 1 0 6 1 l o o o o l o o o 1 o o o 1 o o 吨屯1 0 0 1 1 2 1 1 o o o 1 o o 0 l o 0 o l o o o 1 0 o 0 0 屯屯1 2 2 o o 0 0 l o o o l o o 0 1 0 0 o l o o o 2 2 1 2 2 o o l o 0 0 1 o o o l 0 0 o 0 屯之1 0 01 2 1 山东科技大学硕士学位论文 凸双层规划 第3 章凸双层规划 3 1 引言 对于双层规划问题，即使上、下层问题中的目标函数和约束条件都是线性的，它 一般也是一个非凸问题，而且上层问题的目标函数对于上层决策变量不是处处可微。 双层规划问题的非凸性以及非处处可微给其数值求解带来了极大困难，特别是非线性 双层规划问题。因此，在现有的文献中，很多关于求解非线性双层规划问题的数值方 法研究，或者局限于具有某种特殊结构，或者局限于求局部最优解。 目前，人们已提出了一些求解非线性双层规划的算法，但比较成功的算法还不多。 解决这类问题常用方法，一是罚函数算法；二是分支定界算法；三是其它现代优化算 法等。 本文将讨论一种凸双层规划( c o n v e xb i l e v e lp r o g r a m m i n g ) ，即上层目标函数是凸函 数，下层目标函数是d s - - 次函数，约束条件均为线性的一类非线性双层规划。对这类 问题，在一定条件保证下，将原问题转化为一个单层的数学规划，通过对其对应的松 弛问题有关性质的讨论，给出恰当的定界规则和分支原则，隐含地考虑到互补松弛条 件的所有组合，利用分支定界技术给出一种求全局解的算法，并列举一个算例说明所 提算法的可行性和求解过程。 3 2 模型与定义 设上层决策变量x r ”，下层决策变量y r “，本章所讨论的凸双层规划( c b p ) 形 式为： 哑廿( x ，y ) ( 3 1 a ) s x 0 ，其中y 解 ( 3 1 b ) m i n f ( x ，y ) = c 7 x + d 7 y + x 7 q 1 y + = 1y 7 q 2 y( 3 1 c ) y 1 。 s a x + b y b ( 3 1 d ) 其中f 为r ”r ”斗r 1 上的凸函数，c r “，d r “，q 1 ，q 2 分别为n m 和m 删阶矩 山东科技大学硕士学位论文 凸双层规划 阵，b r ，a ，b 分别为p x n ，p x m 阶矩阵。类似第2 章中的有关定义t 问题( 3 1 ) 的可 行解和最优解定义如下。 定义3 1 a ( c b p ) 的约束域：s = ( x ，y ) ：a x + b y 兰b ，x 0 ) 。 b 上层允许决策集合：t = x ：( x ，y ) s 。 c 对每个固定的x t ，下层问题的可行域：s ( x ) = y ：( x ，y ) s ) 。 d ，对每个固定的x t ，下层问题的合理反应集： 。m ( x ) = y ：y a r g m i n f ( x ，y ) ：y s ( x ) ) e ( c b p ) 的可行解集合( 或诱导域) ：d = ( x ，y ) ：( x ，y ) s ，y m ( x ) ) 。 定义3 2 对任意( x ，y ) d ，若存在( 妒，y + ) d 满足f ( x ，y ) f ( x 气y 4 ) ，称( 妒y + ) 为( c b p ) 的全局最优解，简称全局解。 由于( c b p ) 的下层目标函数为严格d s - - - 次函数，且约束条件( 3 1 d ) 为线性约束，所 以对任意的x t ，下层问题都有唯一最优解。因此只要( c b p ) 的约束域s 非空有界( 即 s 是非空紧凸集1 ，贝i ( c b p ) - - 定有全局最优解。 不失一般性，设c = 0 ，利用k t 条件代替问题( 3 1 ) 的下层问题，则问题( 3 1 ) 可转 化为下列问题： m i n f 伍y )( 3 + 2 a ) x y , u s 1 a x + b y b f 3 2 b ) x r q l + y 7 q 2 + u 7 b = 一d 7 ( 3 2 c ) u j ( b a x b y ) f = 0 ( i = 1 ，2 ，。，p ) ( 3 2 d ) x 0 ，u 0 f 3 2 e ) 其中，u r ，为k - t 乘子向量。 因为下层目标函数氕x ，y ) 是关于y 的严格凸二次函数，下层问题的k t 条件必为充 分必要条件，所以问题( 3 1 ) 和( 3 2 ) 等价。在问题( 3 2 ) 中，除约束( 3 2 d ) 外，其余约束均 为线性约束，称非线性约束( 3 2 d ) 为互补松弛约束或互补松弛项。 1 r 山东科技大学硕士学位论文 凸双层规划 例3 1 r r d n f ( x ，y ) = 扛一5 ) 2 + ( 冷+ 1 ) 2 s x 0 ，其中y 解， l a t i n 厂o ，y ) = 一1 ) 2 1 珈 y s t 3 x - y 3 一x + 0 5 y - - 4 一x - y 一7 y 0 该例的约束域和诱导域如图3 1 所示： y b ( 5 2 ，9 2 ) 入 f ( 2 4 7 ，2 5 7 ) | 八 ( 1 6 9 ，7 3 ) 。 e 厂 s c ( 5 ，2 ) ；? j 1 l 迅之。 x 图3 i 例3 1 的约束域和诱导域 例3 1 的约束域s 为多边形a b c d ，而标记的折线部分为诱导域，且非凸。上层目 标求最优的过程，就是在折线a e ，e f 和f c 上的所有点中，找距p ( 5 ，一1 1 2 ) 最近的点。 此问题的最优解为a ( i ，0 ) ，即最优解矿) = ( 1 ，o ) ，最优目标函数值p = 1 7 。 3 3 理论与算法 根据上一节讨论，求解凸双层规划( 3 1 ) 等价于求解单层规划( 3 2 ) 但问题( 3 2 ) 是一 个非线性规划问题，由于互补松弛约束( 3 2 d ) 的存在，问题( 3 2 ) 是一个非凸规划问题， 在非线性规划中没有现有算法对其求解。 1 9 山东科技大学硕士学位论文 凸双层规划 如果将m n ( 3 2 ) 中的互补松弛约束( 3 2 d ) g a 女# 。n 1 a 7 n ( 3 2 ) 将简化为如下问题： m i n f ( x ，y ) ( 3 3 a ) y , u s t a x + b ys b ( 3 3 b ) x 7 q i + y 7 q 2 + u 7 b = 一d 7 x 0 ，u 0 f 3 3 e ) r 3 3 d ) 由于问题( 3 3 ) 的目标函数为凸函数，且所有约束为线性约束，所以问题( 3 3 ) 是一 个凸规划问题，已有很多成功的算法能对其进行求解。称问题( 3 3 ) 为问题( 3 2 ) 的松弛 问题。 记问题( 3 3 ) 的可行域为i ，由于原m n ( 3 1 ) 的约束域s 非空有界，g ( 3 3 ) 的目标函 数与u 无关，所以问题( 3 3 ) 要么无可行解，要么一定有最优解。设问题( 3 3 ) 有最优解 ( x o , y 0 , u o ) ，对应的最优目标函数值为p - 足x 0 ，y o ) ，则有以下结论成立。 定理3 1p 是原凸双层规划( 3 1 ) 的个下界。 证明：因为f g l n ( 3 - 3 ) 是问题( 3 2 ) 的