（运筹学与控制论专业论文）几类线性多层规划的理论与算法研究.pdf

北京科技大学硕士学位论文 摘要 随着科学技术的发展和实际应用范围的扩展，人们研究的对象逐步由描述简单系统 优化问题的数学规划模型转向了描述复杂系统优化模型。多层规划正是近年来发展起来 的复杂优化模型。本文主要讨论的是线性多层规划的性质与算法。 本文主要工作分为以下几部分： 1 通过理论分析，提出了一种求解带上层约束的线性双层规划模型的算法，数值试 验表明该算法有效；本文提出的算法同样适用于求解不带上层约束的线性双层规划，并 与赵茂先在2 0 0 5 年提出的一种针对不带上层约束的线性双层规划的算法进行了比较， 数值例子表明本文算法减少了计算量。 2 在原有的下层多人无关联线性双层规划模型的基础上，通过放宽下层约束条件， 建立了一类下层多人且关联的线性双层规划模型( b l m f p ) ；并将原有模型的一些理论性 质推广到( b l m f p ) 模型，证明了( b l m f p ) 问题的可行域的某些性质，推导出了( b l m f p ) 问题的最优解的几何特性，这些理论性质为解决( b l m f p ) 问题打下了良好的基础；最后 将k 次最好法应用于解决( b l m f p ) 问题，并通过算例说明了算法的实施过程。 3 在已有的一类线性多层规划模型的基础上，提出了一类具有广泛典型代表性且更 加接近实际问题的线性多层规划模型( m l p ) ；给出了( m l p ) 问题的可行解的定义，证明 了可行解的等价定义，对( m l p ) i o 题的可行域的几何性质进行了理论分析，推广了原有 模型的一些理论性质。 关键词：线性双层规划，线性多层规划，极点，k 次最好法 一1 一 北京科技大学硕士学位论文 t h e o r y a n da l g o r i t h ms t u d yo fs o m ek i n d so fm u l t i l e v e l l i n e a rp r o g r a m m i n g a l o n gw i t ht h ed e v e l o p m e n to fs c i e n c e ，t h eo b j e c t sp e o p l es t u d yj u s tc h a n g ef r o m m a t h e m a t i c a lp r o g r a m m i n gd e s c r b i n gs i m p l es y s t e mt om a t h e m a t i c a lp r o g r a m m i n gd e s c r b i n g c o m p l e xs y s t e m i ti st h em u l t i l e v e lp r o g r a m m i n gt h a tm a t h e m a t i c a lp r o g r a m m i n gd e s c r b i n g c o m p l e xs y s t e mh a v ed e v e l o p p e dr e c e n ty e a r s i nt h i sp a p e r ，w ed i s c u s st h ep r o p e r t i e sa n d a l g o r i t h mo f t h em u l t i l e v e ll i n e a rp r o g r a m m i n gp r o b l e m i nt h i sp a p e r , t h em a i nr e s u l t sa r ea sf o l l o w s ： 1 a c c o r d i n gt h e o r e t i ca n a l y s i s ，an e wa l g o r i t h mw a sp r o p o s e df o rt h eb i l e v e ll i n e a r p r o g r a m m i n gw i t hu p p e rl e v e lc o n s t r a i n t s t h en u m e r i c a lr e s u l t sp r o v et h a tt h ea l g o r i t h mi s e f f e c t i v e t h i sa l g o r i t h ms t i l la p p l yt ot h em o d e lo fb i l e v e ll i n e a rp r o g r a m m i n gw i t hn ou p p e r l e v e lc o n s t r a i n t s t h i sa l g o r i t h mi sc o m p a r e dw i t ht h ea l g o r i t h mf o rs o l v i n gb i l e v e ll i n e a r p r o g r a m m i n gw i t hn ou p p e rl e v e lc o n s t r a i n t sp r o p o s e db yz h a om a o x i a ni n2 0 0 5 t h r o u g h s o m ee x a m p l e s , i tc a nb es e e nt h a tt h ea m o u n to fc o m p u t u t i o nc a nb el e s s e n e db yt h i sa l g o r i t h m 2 b a s e do nt h em o d e lo fb i l e v e ll i n e a rm u l t i f o l l o w e rp r o g r a m m i n gi nw h i c ht h e r ei sn o s h a r i n gi n f o r m a t i o na m o n gf o l l o w e r s ，w ee x t e n dt h el o w e r l e v e lc o n s t r a i n t s ，t h e nw ee s t a b l i s ha m o d e lo fb i l e v e ll i n e a rp r o g r a m m i n gw i t hm u l t i i n t e r c o n n e c t e d - p e r s o nl o w e rl e v e l ( b l m f p ) s o m ee x i s t i n gp r o p e r t i e sa n dt h e o r i e sa r ee x t e n d e d s o m ep r o p e r t i e so ff e a s i b l er e g i o na r e p r o v e d g e o m e t r i cp r o p e r t i e so fo p t i m a ls o l u t i o na r er e d u c e d a tl a s t ，t h ek t h - b e s ta l g o r i t h mi s u s e df o rs o l v i n g ( b u 订f dp r o b l e m t h ee x p e r i m e n ts h o w st h ep r o c e s so ft h ea l g o r i t h m 3 b a s e do nt h em o d e lo fak i n do fm u l t i l e v e ll i n e a rp r o g r a m m i n g , i ti sp r o p o s e dac l a s so f m u l t i l e v e ll i n e a rp r o g r a m m i n gm o d e l s ( m l p ) ，w h i c hc a ne x t e n s i v e l yr e p r e s e n tac l a s so f m u l t i l e v e lm a n a g e m e n t a ls y s t e m s i na d d i t i o n , d e f i n i t i o no ff e a s i b l es o l u t i o ni sg i v e na n da l l e q u i v a l e n c ed e f i n i t i o nf o r ( m l p ) i sp r o v e d s o m eg e o m e t r i cp r o p e r t i e so ff e a s i b l er e g i o na r e p r o v e d s o m ee x i s t i n gp r o p e r t i e sa n dt h e o r i e sa r ee x t e n d e d k e yw o r d s ：b i l e v e ll i n e a rp r o g r a m m i n g ，m u l t i l e v e ll i n e a rp r o g r a m m i n g ，e x t r e m e p o i n t , k t h - b e s ta p p r o a c h 2 一 独创性说明 本人郑重声明：所呈交的论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 北京科技大学或其他教育机构的学位或证书所使用过的材料。与我一同 工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表 示了谢意。 签名：盛已塑日期：丝! 生三丑堡旦 关于论文使用授权的说明 本人完全了解北京科技大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公 布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论 文。 ( 保密的论文在解密后应遵循此规定) 签名：垒! 奎董导师签名： 北京科技大学硕士学位论文 引言 决策问题贯穿于人类社会生活的各个方面，决策优化是人们研究决策问题的焦点。 随着人类社会的不断发展，人们所研究实际问题的规模越来越大、层次结构日趋复杂， 这就需要在不同层次上的决策者根据自己的实际情况做出各自的决策。在较大规模的管 理系统中，上一级决策者自上而下地对下一级决策者进行控制，从全局上进行决策；下 一级决策者在上一级决策者指导下，在自己的管理范围内行使决策权。在此背景之下， 多层规划理论与方法就成了管理及决策研究中一个重要的研究领域，它是近二十年来规 划论中比较受关注的一个研究领域。 在多层规划的研究中，以二层规划最为常见，这是因为现实的决策系统大都可以看 成二层决策，近年不断有文章研究双层规划在社会各个具体领域中的应用。显然，双层 规划广泛的应用范围和美好的应用前景是非常诱人的，但是，机遇总是与挑战并存的。 双层规划问题是一类本质非凸非光滑问题，研究起来较复杂。对于双层规划问题，研究 最早和最多的是线性双层规划，研究发现，即使是基本的线性双层规划问题都是n p - h a r d 问题，增加了其研究难度。 虽然对于线性双层规划的研究有一定难度，但由于其中所包含函数的特殊性，它也 具有某些特殊的性质，这些性质为其算法的研究提供了强有力的基础。线性双层规划问 题的理论研究及其算法求解引起了大家的广泛重视和兴趣。 目前学者们对于线性多层规划的研究，大都集中在研究线性双层规划，大部分的算 法都是把线性双层规划问题转化为单层规划，然后进行求解。线性双层规划问题可以分 为很多类。 本文主要研究了下层单人的线性双层规划模型的求解算法，并与他人提出的算法作 了比较，理论分析和数值例子都证明了本文算法在减少计算量上有优势；并研究了下层 多人且关联的两层线性规划以及多层线性规划的一些理论性质。 - l 一 北京科技大学硕士学位论文 1 线性多层规划基本理论综述 1 1 选题的意义与背景 阶层性是系统的六大层次，随着人类社会的发展，经济全球化的加剧，实际问题的 规模越来越大，层次性愈加明显，结构越来越复杂，因此，层次性的研究就具有非常重 要的意义，多层规划正是为了研究系统层次性问题而产生的。 多层规划问题是一种具有多级递阶结构的系统优化问题，而对这类问题的研究已经 有了很久的历史。 2 0 世纪5 0 年代提出来的s t a c k e l b e r g 对策，是一种多人非零的对策，其中局中人有 上下关系并且各自有不同的目标，而各自的策略集通常是彼此分离的。多层规划问题与 这类对策有些共同点，但各个层次的决策者必须依次做出决策，各自的策略集不必再是 分离的。 加世纪6 0 年代，d a n t z i g 和w o l f e 提出了大规模线性规划的分解算法，相当于有 一个核心决策者，他的目标是高于一切的，其他各层次的决策者实现自己的目标只不过 是为实现核心决策者的目标的一种分工，他们的目标须与核心决策者的目标完全一致， 没有自己独立的利益。多层规划承认有最高决策者，但不是绝对的，他容许下层决策者 有各自不同的利益。 2 0 世纪7 0 年代发展起来的多目标舰划通常是寻求一个决策者的相互矛盾的多个目 标的折中解，有些技术，如分层优化技术，也可用来求解层次问题，但下层的决策不影 响上层的目标，因而可以逐层独立求解。而多层规划正是要强调下层决策对上层目标的 影响，因此多层规划问题通常不能逐层独立求解。 2 0 世纪7 0 年代以来，人们在各种现实的层次分散系统优化决策问题的研究中，遇 到用上述方法不能解决的实际问题，因而人们寻找各种特定的方法并成功地解决了这些 问题，并逐渐形成了多层规划的概念和方法。如：c a s s i d y ( 1 9 7 1 ) 的政府决策效力分析， k y l a n d ( 1 9 7 5 ) 的经济层次分析，b r a c k e n 等人( 1 9 7 3 1 9 7 7 ) 的战略武器配置研究，c a n d l e r 和n o r t o n ( 1 9 7 7 ) 的奶制品工业模型和墨西哥农业模型等。多层规划一词就是c a n d l e r 和 n o r t o n 在上述论文中首先提出来的，它的原意是一集嵌套着的数学规划问题，即在约束 条件中含有优化问题的数学规划。 2 一 北京科技大学硕士学位论文 1 2 国内外研究现状及复杂度 多层规划的发展可追朔到三个问题：一是运筹学中约束条件含优化问题的数学规划 问题。b r a c k e n 等首次给出两层规划的形式【1 】，并在一系列文献中讨论此类问题的性质 和求解，同时将其应用到军事防御和竞争环境下生产与市场决策等闷题中。二是f a r o 2 深入研究的线性m i l l - m a x 问题，它是两层规划的特殊形式，该问题的讨论为两层线性 规划几何性质的研究和算法设计提供了理论基础。三是德国经济学家s t a c k e l b e r g 在3 0 年代提出的寡头市场模型s t a c k e l b e r g 模型。它是三个经典的寡头市场模型之一【3 】， 在该模型中，决策是贯序的，主导产业先走一步，因而占有优势。 在多层决策问题中，以双层决策问题最为常见，任何多层决策系统都是一系列双层 决策系统的复合。七十年代末，c a n d l e r 等首次使用双层规划这一术语，直到八十年代 初才引起人们的广泛关注【禾7 】。从此入们致力于双层规划理论的探讨，算法设计和实 际应用等课题的研究。九十年代，随着双层规划横向与纵向的拓广，对其研究也随之更 加深入，下层有多个子问题的双层规划、多层规划、多层混合整数规划、下层以最优值 反应上层的双层规划、双层多目标规划及有平衡约束的数学规划等都纳入多层规划的研 究范畴，取得许多成果。 1 9 7 7 年c a n d l e r 和n o r t o n 在科技报告1 8 】中，正式提出了双层规划和多层规划这个 名词。本文主要研究线性多层规划问题，而对线性多层规划的研究中以研究线性双层规 划最为普遍，关于线性双层规划问题的算法主要有以下几种： ( 1 ) 极点算法：其基本思路是，线性双层规划问题的任何解都出现在下层规划的约 束集合的极点处，首先可以利用各种方法来寻找约束空间的极点，然后从中再找出双层 规划问题的局部最优解或全局最优解。但是随着问题规模的增大，极点的增多，计算量 也迅速增大，对较大规模的问题难以求解。c a n d l e r 9 提出了通过枚举约束集的极点来 计算线性双层规划问题的全局最优解。b i a l a s ，c h e w 1 0 1 提出了一种“k 次最好法”极 点算法，此算法对线性双层规划约束集的极点按上层规划目标函数值由大到小依次进行 枚举，并判断其是否为线性双层规划的可行解。刘红英、刘三阳【1 1 1 针对带上层约束的 线性双层规划问题，提出一种基于两阶段单纯形法及修正单纯形算法的“k 次最好”算 法，在此基础上又给出了一种双层广义线性规划的“k 次最好”算法。v i c e n t e 1 2 】引入 了“诱导域极点”和“诱导域集值方向”的概念，提出了一种根据上层目标函数的性质 来计算局部极小点的极点算法。 ( 2 ) 分枝定界法：其基本思路是，根据事先选定的分枝准则，将所求解的问题分成 一系列子问题，并从中选取一个子问题进行检验，决定其取舍。分枝定界法计算量很 3 北京科技大学硕士学位论文 大，但它能求解全局最优解。b a r d ，f a l k 1 3 等人提出了线性情况下的分枝定界算法。 e d m u n d s ，b a r d 1 4 】提出了求解双层整数二次规划的分枝定界算法。倪放明【1 5 】引入代理 约束，通过构造一个计算简单的定界函数，给出了一个混合整数线性双层规划的分枝定 界算法。沈厚才【1 6 】等人针对上层o 1 变量、下层多目标的二次线性双层规划问题提 出了一种有效的分枝定界算法。 ( 3 ) k - t 法：其基本思路是，将双层规划问题中的下层规划问题用它的k u h n t u c k e r 条件代替，将双层规划问题化为单层非线性规划问题求解，最初用于求解双层 线性资源控制问题。这种算法仅对线性约束的上层和凸二次规划的下层这种特殊情况有 效。 ( 4 ) 模糊数学算法：其基本思路是，充分利用模糊集理论中隶属函数及模糊算子的 概念和性质，分别建立上层决策变量的隶属函数和上、下层决策者目标函数的偏好隶属 函数，双层决策问题转化为单层优化问题，分别对各单层规划的解进行讨论，最终把双 层线性规划转化为求解一个单层线性规划问题，求得两层决策问题的满意解。裴峥、黄 天民【1 7 】针对上层有约束条件、下层有n 个独立的决策单元的线性双层规划问题，提出 了一种模糊数学解法。刘新旺、达庆利 1 8 1 针对多人递阶资源分配问题提出了对决策者 模糊满意度进行两步折衷的求解算法。腾春贤、李皓白 1 9 1 给出了多人多目标的双层规 划问题的模糊目标规划算法。 双层规划的几何性质比熟知的单层数学规划复杂得多，主要表现在：约束的嵌套 本性。在双层规划中，因为下层问题的介入，由其隐含的互补条件决定了约束的嵌套本 性。可行集一般不具备凸性和闭性，有上层约束时还可能不连通。b i a l a s 和k s t w a l l 以实例论证了上层问题的非凸性【2 0 】。内在的非光滑性。计算复杂度。b e n - a y e d 和 b l a i r 通过将背包问题构造为线性双层规划问题，从而证明了这是一类n p h a r d 的问题 【2 1 】。 对多层规划的研究大多数局限于双层规划。研究下层有多个子问题的双层规划的很 少 2 2 ，2 3 1 、三层以上多层规划的研究仅限于多层线性规划 2 4 ，2 5 ，2 6 、双层混合整数规划 的研究也仅限于线性情况 2 7 , 2 8 ，2 9 ，下层以最优值反应上层的双层规划研究比较成熟 3 0 ，3 1 1 ，但面很窄。 矗一 北京科技大学硕士学位论文 2 预备知识 2 1 多层规划模型与内涵 在社会经济、工程技术、管理部门及军事领域中，具有层次递阶关系的系统比比皆 是，如管理机构中的上下级关系、经济活动中的供销关系、军事系统中的防御与反防御 关系、企业中的公司与分公司关系，工程设计中的控制变量和状态变量的关系等。在这 些具有递阶结构的系统中，上层是领导，总揽全局，起协调、主导作用，目标是使整个 系统效益达到最优；下层是随从，在上层的决策限制下独立决策使子系统效益最优。其 决策机制是：首先上层向下层宣布它的决策，该决策直接影响下层的可行集和目标函 数，下层在该限制下将自己的最优决策反应给上层，下层的决策也影响上层的目标函数 和可行性，上层再调整它的决策，直到上层的目标函数值最优为止。这种决策机制使得 上级部1 3 x i j - 下级的管理和领导仅仅靠影响下层的决策环境间接来引导下层作出有利于整 个系统的决策，而不允许上层的直接介入或命令，故属于“民主”的而非“独裁”的决 策方式，更为科学和合理。 对上述系统的决策和管理进行数学建模使整个系统发挥最大效益，即是多层规划， 它包含一个上层问题和若干个下层子问题，上层问题和下层子问题都有各自的目标函数 和约束条件。上层问题的目标函数和约束条件不仅与上层决策变量有关，而且还依赖于 下层问题的最优解；而下层问题的目标函数和约束条件又受到上层决策变量的影昀；下 层问题针对给定的上层决策变量，求出自己的最优解并将该最优解反馈给其上层决策 者，多层规划问题的一般形式为f 3 2 】： m i n 厂1 0 1 ，一) s l 工一( z 1 ，x 。) e x l 且( 工2 , x 3 ，z ) 解 r a i n 厂2 1 ，x 。) 墨x e x2 且( 工3 ，工4 ，工7 ) 解( o m l e ) m i n 正 1 ，x 。) s ，t x x l 多层规划问题通常有如下特点： ( 1 ) 系统是分层管理的，各层决策者依次做出决策，下层服从上层，但下层有相当的 自主权。 ( 2 ) 各层决策者有各自不同的目标，这些目标往往都是互相矛盾的。 5 北京科技大学硕士学位论文 ( 3 ) 各层决策者各自控制一部分决策变量，以优化各自的目标。 ( 4 ) 上层决策者优先做出决策，下层决策者在为优化自己的目标而选择策略时，不能 违背上层的决策。 ( 5 ) 上层的决策可能影响下层的决策集，因而部分地影响下层目标的达成，但上层不 能完全控制下层的决策，在上层决策允许范围内下层有自主决策权。 ( 6 ) 下层的决策不但决定着自身目标的达成，而且也影响上层目标的达成。因此，上 层在选择策略以优化自己的目标达成时，必须考虑到下层可能采取对自己的不利影响。 各层决策者的容许策略集通常是不可分离的，他们往往形成一个相互关联的整 体。 2 2 双层规划分类 双层规划是双层决策系统优化的数学模型，它是一种具有二层递阶结构的系统优化 问题，上层决策者和下层决策者都有各自的目标函数和约束条件，上层先给定一个决策 变量，下层各子系统以这个决策变量为参量，根据自己目标函数和约束条件，在可能的 范围内求得一个最优值，并将自己的最佳反应反馈给上层，上层再在下层的最佳反应的 基础上，在可能的范围内求得整体上的最优解。 双层规划的一般模型具有以下形式： pm j n f ( x ，y ) 量f g ，y ) s0 其中对每一个固定的x ，y 是下述规划问题的解向量。 r a i n ， ，y ) 只 7 鼠f g o ，) ，) s 0 其中z r “，y e r “，上下层的目标函数f ，厂：r “x r “一只，上下层的约束函数 g ：r “r “一r ”，g ：r “r “一r 。称蜀为双层规划的上层，最为双层规划的 下层，下层决策变量y 是上层决策变量x 的函数，即y y 0 ) ，函数一般被称为反应函 数。 根据下层向上层的最佳反应的不同形式，双层规划模型可分为如下两种类型： ( 1 ) 下层以其最优解反馈到上层的双层规划模型( 卯) ， 6 北京科技大学硕士学位论文 罡毋f o ，g ) ) x 一扛r 1 日 ) o j ；y o ) 一( ) ，。o ) ，y ：o ) ，) ，o ) ) y ；o ) 一a r g ，r a q i n l ( x ，y 。) ；k o ) 一。r “i g 。o ，y 。) s 畦f 一1 , 2 ，n 五：r “x r “_ r ( 2 ) 下层以其目标函数最优值反馈到上层的双层规划模型( 且p ) ， m i n f ( x ， ，o ) ) 石一仁r “i h o ) s o ，o ) 一( ， ) ，v ：o ) ， ，o ) ) u 0 ) 4 ，r a ，q i n ( ，) l ( x ，) ，t ) ；k o ) 2 杪一e r ig ； ，y j ) 墨o f i 1 , 2 ， f t ：r “x r “- r 根据上下层目标函数的不同情况，双层规划模型可分为如下三种模型： ( 1 ) 下层单人双层决策模型；上下各有一个决策者时，上层首先任意给定一个决策参 数，下层则在这个参数下根据自己的偏好在可能的约束范围内优化自己目标函数。上层 再在下层的最佳值反应的基础上在可能的约束范围内做出整体的最优决策。 只卿f o ，) ，) x 一仁r “1 日 ) s o j by4 缸g 熙，o ，) ，) y ) = r “i g ( x ，y ) s o 其中x ，y 分别是上下层的决策变量，f o ，) ，) ，o ，y ) 分别是上下层的目标函数， r f ，：月“r “r 。 ( 2 ) 下层多人无关联双层决策模型：上层只有一个决策单元，控制一个决策变量。下 层有r 个决策单元，且各单元相互独立，并受上层的控制。 e 卿f g ，y l ，) ，z ，y r ) x 一仁r “i o ) s 0 其中对每一个固定的x ，y 。，y ：，) ，是下述规划问题的解： 7 一 北京科技大学硕士学位论文 最赌l ( x ，y - ) m y h i n ? l ( x ，y r l 只g l g ，) ，i ) s 0i - 1 , 2 ， 其中& ：r “x r “- r “ ( 3 ) 下层多入有关联双层决策模型：上层只有一个决策单元，控制一个决策变量。下 层有，个决策单元，且各单元不相互独立，并受上层的控制。 只 m 婴f ( x ，y t ，y z ，y ，) z x e r mi n ( x ) o 其中对每一个固定的x ，y ，) ，：，) ，是下述规划问题的解： 最嘧五 ，儿，) ，：硝r ) m y p i n ? l ( x ，乳，y 2 , - - - , yr ) f - g j o ，y l ，y 2 ，y ，) s0i 王1 , 2 ，厂 上述双层规划模型中的诸函数，g ，h ，五，既( f l 2 ，) 中至少有一个为非线性函 数时，则称之为非线性双层规划，否则称之为线性双层规划。根据双层规划的上下层目 标函数f 和正为向量值函数或者单值函数，那么双层规划模型又可以分为单目标双层规 划和多目标双层规划。 8 一 北京科技大学硕士学位论文 3 本文i 作 3 1 线陛双层规划的一种全局优化算法 3 1 1 理论分析与证明 通过对双层规划的相关文献研究，发现在关于双层规划的模型描述时，有的将上下 两层的约束都置于最下层，而有的将约束分别置于上下两层。线性双层规划是双层规划 的一个特例，即上下层问题的目标函数和约束条件都是线性的，线性双层规划的模型包 括不带上层约束的线性双层规划和带上层约束的线性双层规划。 设上层决策变量为x e r ”，下层决策变量为y e r 4 ，不带上层约束的线性双层规划 模型如下【3 3 】； m i n c r u x + d t y 最苫o 其中y 求解 m i n d j y ( 3 1 ) 且 爿2 工+ b 2 y b 2 ， y2 0 c le r 4 ，d 1e r “，d 2e r “，6 2e r ，a 2 r k x nb 2e r “ 设上层决策变量为石r “，下层决策变量为) ，e r “，带上层约束的线性双层规划模麓 型如下【3 4 】： m i n c ，x + 武y 且厶a l 工+ b 1 y 之b l ， 石乏o 其中y 求解 m i n d ；y ( 3 2 ) & f a 2 工+ b z y 之b 2 ， y2 0 c le r 4 ，d l r “，b le r t , a 1e r ”，b l r 。一，d 2e r “，b 2e r ，a 2 尺”，b 2 月” 本节中我们针对带上层约束的线性双层规划( 3 2 ) ，在一定假设条件下给出了一些定 理，性质及其证明，最后给出一种全局优化算法。这些定理性质及其算法也适用于不带 上层约束的线性双层规划( 3 1 ) 。下面给出详细的理论分析。 关于线性双层规划( 3 2 ) 的几个基本概念【3 4 】： 9 北京科技大学硕士学位论文 ( 1 ) 线性双层规划( 3 2 ) 的约束区域： s k ，y ) e r “x r ” a l x + b t yb 1 ，a 2 x + b 2 y 苫6 2 ，o ，y ) 之0 ( 2 ) 对任给的工e r ”，线性双层规划( 3 2 ) 下层规划的可行解集合为： s o ) 一t y e r “i a 2 膏4 - 口2 ) ，苫b 2y 0 ( 3 ) s 在尺“上的投影为： q 一扛r “i 砂尺”，4 z + e y 之6 1 ，a 2 x + b 2 y 苫6 2 ，y ) z 0 ( 4 ) 对于工q ，线性双层规划( 3 2 ) 下层规划的合理反应集合为： d o ) 。p s g ) iy a t g 墨鹣矗) ，j ( 5 ) 线性双层规划( 3 2 ) 的可行解集合为： i 一缸，y ) io ，) ，) s ，y d ) ( 6 ) 若 ，y - ) 是问题m i nc + d f y 的最优解，则称 ，y - ) 为线性双层规划( 3 2 ) 的全局 “，y j e - s 最优解，简称最优解。 设s 为非空集合，且对所有x q ，线性双层规划( 3 乃的下层问题都有唯一最优 解。当上层给定某个允许决策x q 后，线性双层规划( 3 2 ) 的下层最佳反应是求解如下 问题： m i n d x z y y 置a2工+b2yb2(je) y 苫0 问题( 只) 的对偶规划为： m a x a 1p 2 一彳2 工) 且口；ad2，(dd a20 引理1 1 3 5 1 ：罗d ) 是线性双层规划( 3 2 ) i 的t 层子规划参变量为- l 对的最优解当 且仅当存在a - e r ，使得侈，万) 在参变量为i 时，满足下列不等式： a 2 孑4 - b 2 y 芑b 2 ，b ；a s d 2 ，( 4 2 孑+ b 2 y 一6 2 ) t a 年0 ，( d 2 一b a ) t y 毒0 ，y ，a2 0 根据引理1 ，显然可以得到如下定理： 定理1 1 3 5 】：o ，y ) 是线性双层规划( 3 2 ) 的最优解当且仅当存在f r 使得 ( 石。，y ，a ) 是规划( 3 3 ) 的最优解，且最优值相等。 1 0 北京科技大学硕士学位论文 ( r a 。i m nc + d ，y & f a 1 x + b i y 之b l ， a 2 工 4 - b 2 y2 b 2 ， 霹as d 2 ， ( 3 3 ) 0 2 工+ b 2 y b 2 ) a o ， p ：- b ；x ) 7 y 一0 ， 工，y ，a 0 定理2 ：令妒 ，y ，a ) 一砉m i n ( a 2 x + b z y - b 2 ) ，九) + 蓦m i n 缸：一曰：t a ) ，) ， ，则 驴 ，y ，a ) 一0 即2 石+ b 2 y 一6 2 ) 7 a o ，( d 2 一曰；a ) 1 y 一0 ，其中( 础+ b 2 y 一也x ， 分别是口：x + 口：y - b 2 ) ，a 的第f 个分量， ：- b j x ) ，y j 分别是“2 一蟛a ) ，y 的第，个 分量( i 一1 , 2 kj 一1 ，2 ，小) 。 证明：伊( x ，y ，a ) 一0 m i n ( 彳：x + 曰：y b e ) ， 一0 ( f 一1 , 2 ，k ) r m i n e d ：一口a ) ，y ， 一0 ( ，- l 2 ，m ) 对每个呼一1 ，2 ，七) 有石+ b z y b z x o 或丸一o ； 对每个j ( j 一1 ，2 ，所) 有 ：一口三a ) 一0 或y ，一0 争( 爿2 x + b 2 y b 2 ) j - 00 1 1 ，2 ，七) 且( d 2 一曰j a ) y ，1 0 ( _ ，奢1 , 2 ，oo * 9 历) 以2 x + b z y 一6 ：) a 。似：石+ 口z y b 2 ) 一九j o ； 2 一b 手a ) 7 ) ，一 2 一日一) ，y ，一o 。 综上所述，定理2 锝证。 定理2 中用妒o ，y ，a ) 一0 代替了规划( 3 3 ) 2 4 j 束条件中的即+ b z y 一) 7 a 一0 ， “：一口一) 7 y 一0 ，简化了表达方式。 记h 一杠i 曰a s d 2 , a o ，记日5 为h 的所有极点( 基可行解) 组成的集合。记 s 5 为s 的所有极点组成的集合。 定理3 1 3 6 ：若单层规划( 3 3 ) 有最优解，则必可在s 6 h 5 上达到。 一1 1 北京科技大学硕士学位论文 综上，线性双层规划( 3 2 ) 的最优解与规划( 3 3 ) 的最优解之间具有一一对应关系，因 此，可把线性双层规划( 3 2 ) 转化为形式比较简单的单层规划( 3 3 ) 来考虑。下面我们给出 求解算法。 3 1 2 算法步骤及算法比较 一、算法步骤 基于以上定理结论，我们给出如下算法，算法的基本思想是：先求出的所有极 点，然后对s 的极点按c + a ? y 的值由小到大进行枚举，通过妒0 ，y ，a ) 一0 判定其是 否为线性双层规划( 3 2 ) 的最优解。下面给出算法描述： 步骤0 ：首先用修正单纯形法【3 7 】求出一协i 曰sd ：，a 之o 的所有极点，记为 刀，刀。 步骤1 ：求解如下规划的最优解，记为o ，y ) ，s a , w 一缸1 ，y 1 ) ，t 一妒，转步 骤2 。 嘶c t x + d t y 量f a l x + b 1 y b l ， a 2 工+ b 2 y 苫b 2 x ，y 苫0 步骤2 ：将o ，y ) 代入伊o ，y ，a ) ，再将舻。一l 2 一，f ) 依次带入妒o ，y ，a ) ，若 存在某一舻使得妒o ，y ，a ) 一0 ，则停止，o ，y ) 即为最优解，否则，转 步骤3 。 步骤3 ：记w ，】为0 5 ，_ ) ，) 的相邻极点，令r r u b ，y ) ，w - ( i vl j l 嵋 , 1 ) r ， 转步骤4 。 步骤4 ：j s 十1 ，选择g ，y 5 ) 使得c + d f ) ，一m i n c ，x + d t y ：o ，) 矽 ，转 步骤2 。 下面给出一个带上层约束的线性双层规划的例子，用本文算法求解。 椤! i1 ： 1 2 北京科技大学硕士学位论文 m a x f o ，) ，) 一x + 3 y 墨z 一2 y j6 2 x 一) ，s 2 1 , 工2o ，其中，求解 m a x ， ，y ) 一一3 y y & x4 - 2 y l o , z + 2 y 量3 8 , 一z + 2 ys 1 8 ) ，苫0 用修正单纯形法求得日一协i2 一2 九一2 九3 , a 之o ) 有两个极点，分别为 刀一( n o ，o ) ，矛一( 1 5 ，0 ，0 ) 。 记仍一妒y ，刀) ，仍一伊o ，y ，牙) ，其中妒y ，舻) 一m i n ( x + 2 y 1 0 ，硝) 4 - m i n ( - x 一2 y + 3 8 ，丝) + m i n ( x 一2 y + 1 8 ，硝) + m i n ( 3 2 硝+ 2 硝+ 2 硝，_ ) ，) 。 求解例1 的数值结果如表3 1 所示： 表3 1 本文算法求解例1 的数值结果 s 3 ，y )仍妒2 w e ，i w l( 1 0 ，1 4 )31 5 ( 1 6 11 ) ( o ，9 ) ) ( 1 6 ，11 ) ( 0 ，9 ) 2 ( 1 6 ，1 1 )31 5 ( 1 0 , 1 4 ) ( 1 2 ，3 ) ) ( 1 2 ，3 ) ( 0 ，9 ) ) 3 ( o ，9 )31 5 缸1 0 ，1 4 ) ( o j ) ( 0 ，5 ) ( 1 2 ，3 ) 4( 1 2 ，3 )31 。5 ( 16 1 1 ) ( 8 ，1 ) d ，5 ) ( 8 ，1 ) ) 5( 0 ，5 )30 由表3 1 可见，例1 的最优解为o ，_ ，) 一( 0 ，5 ) 。 二、算法比较 本文给出的算法是针对带上层约束的线性双层规划( 3 2 ) 提出的，易见本文算法同样 适用于不带上层约束的线性双层规划( 3 1 ) 。文献 3 3 1 中针对不带上层约束的线性双层规 划( 3 1 ) 提出了一种算法，我们把它称之为z g 算法。 z g 算法的算法思想： 1 3 北京科技大学硕士学位论文 首先将线性双层规划( 3 1 ) 转化为单层规划( 3 4 ) ： m i n c + d ，_ ) ， s j a 2 j + b 2 y 之b 2 ， 口；a d 2 ， ( 3 4 ) a ：y a 1 ( 6 2 一彳2 石) 一0 工2 0 ，y 苫o ，a 之0 令s 一缸，y ) e r “r 4i a ：x + b ：y 6 ：，( x ，y ) 0 ；h 一协l 口j a s d ：，a 苫o j ，记 h 5 为日的所有极点的集合。记s 5 为s 的所有极点的集合。再由规划( 3 4 ) 有最优解， 则必可在s 5 h 5 上达到这一结论，先求出h 5 ，记为h 5 一协，刀 ，再分别将 刀，刀代入到规划( 3 4 ) 的约束条件a ：y 一矿 一4 工) 一0 中，这样就将非线性规划( 3 4 ) 转化为如下t 个线性规划： m i n c f f x + a ? y j y f a 2 工+ b 2 y 之b 2 ， d j y 一( 。矿) t ( 6 2 4 ：茗) 10 工苫0 y 乏0 ( 厶p ( a 7 ) ) 其中p 一1 ，2 ，t 。 分别求解这t 个线性规划上尸( 舻) 一1 ，2 ，f ) ，将得到的解分别代入到目标函数 c + a ? r 中，使得目标函数最小的那组解，即为线性双层规划( 3 1 ) 的最优解。 本文算法与z g 算法比较优势在于，本文算法用极点迭代代替了z g 算法中的求解 多个线性规划，减少了计算量。下面我们通过计算实例来比较两种算法。 首先给出比较简单的一个算例，如下： 例2 ： m i n f 一y 曼t 工芝o 其中y 的解为 m i nf y f 一x 一2 y s - 1 0 膏+ 7 ys 7 0 工一2 ys 6 5 x 一2 ys 5 4 x 。y 苫0 1 4 北京科技大学硕士学位论文 本文算法求解例2 过程： 第轮迭代： 步骤 0 ： 下层问题的对偶问题是： m a x z 一( - x + 1 0 ) 九+ g 一7 0 ) 九+ o 一6 ) 厶+ ( 5 x 一5 4 ) a , s t 2 一7 屯+ 2 九+ 2 a 4 墨1 九，九， ，九2 0 用修正单纯形法求得 日一鼽一( ，如，九，a 。) 1 2 一7 a ：+ 2 九+ 2 , 3 , 4 1 , z m 的极点为： 刀一( o ，o ，o ，o ) 矛一( 0 5 ，0 ，o ，0 ) ，矿，( o ，o ，0 5 ，o ) ，一( 0 , 0 ，0 ，0 5 ) 。 步骤1 ： m i n f 一一) ， s j ，一z 一2 y s 一1 0 工+ 7 y 王7 0 x 一2 ys 6 缸一2 y 5 4 x ，y 之0 用单纯形法求解上述规划得最优解0 1 ，_ ) ，- ) 。( o ，l o ) ，j 。l w 。k - ，y - ) ，r 乏。 步骤2 ： 妒，一驴g ，y ，) 一m i n ( x + 2 y 一1 0 , 群) + m i n ( 7 0 一z 一7 y ，硝) + r a i n ( 6 - - x + 2 ) ，剪) + r a i n ( 5 4 缸+ 2 ) ，硝) + m i n 0 2 舛+ 7 硝一2 硝一2 z ：，y ) ， 其中群为的第i 个分量( p 一1