（应用数学专业论文）线性多层规划及其交互式模糊规划法的研究.pdf

西南交通大学硕士研究生学位论文 v 第1 页 摘要 在现代决策系统中，存在大量具有层次递阶特性的系统，归结 为数学模型，即为多层规划。因此，研究多层规划决策模型的性质 及有效算法具有非常重要的理论价值和实际意义。全文的主要内容 如f ： 首先，简要介绍多层规划问题以及模糊集合理论的实际背景及 发展概况。 进步，本文对线性多层规划问题进行了综合性讨论，介绍一 类特殊的线性多层规划问题的性质，然后介绍多层规划的求解算法， 其中较详细地介绍s h i h 等人提出使用模糊集合理论的隶属函数来解 决二层规划问题，从而引出交互式多层规划求解算法。由于s h i h 等 人主张交互式多层规划法应该把目标满意度和决策变量满意度都考 虑进去，显得有点复杂，实际上只需考虑目标满意度即可。因为在 实际问题中，决策者很难知道最优值为何值，因此所谓的决策变量 的满意度要求就没有实际意义：同时，在分别求解各层最优解时如 果出现多个最优解同时存在，就会出现多个关于决策变量的隶属函 数，出现计算时的复杂性和不一致性，所以不需要考虑变量的满意 度。 最后，在后两章中，用不考虑决策变量满意度的交互式模糊规 划法，分别来求解确定性以及带有模糊参数的线性多层规划，求解 具有渐进性，先是对二层，然后延伸到多层，并有具体数字算例来 说明方法的可行性。 关键词：线性多层规划；可行解；模糊参数；满意度；交互式模糊 规划 西南交通大学硕士研究生学位论文第1i 页 a b s tr a c t l nr e a ld e c i s i o n m a k i n gs y s t e m s ，m a n yo ft h e ma r ec h a r a c t e r i z e d b ym u l t i l e v e ls t e p s w h i c ha r ec a l l e da sm u l t i l e v e lp r o g r a m m i n gi n m a t h e m a t i c sm o d e l s oi ti s i m p o r t , n t t o s t u d yt h ep r o p e r t i e so fi t i n t h e o r y a n dt of i n de f f i c i e n tw a y st o a p p l y i ti n r e a l i t y t h e m a i n c o n t r i b u t i o n so ft h i sp a p e rc a nb es u m m a r i z e da sf o l l o w s ： f i r s t ，t h eb a c k g r o u n d a n dc u r r e n ts t a t eo ft h em u l t i l e v e l p r o g r a m m i n ga n df u z z ys e t st h e o r yi sg i v e ns i m p l y t h e n ，t h i sp a p e rt a k e sas y n t h e t i cs t u d yo ft h el i n e a rm u l t i l e v e l p r o g r a m m i n gp r o b l e m a f t e rt h ei n t r o d u c i n go ft h ep r o p e r t i e s o fo n e k i n do f s p e c i a ll i n e rm u l t i l e v e lp r o g r a m m i n g ，s e v e r a la l g o r i t h m s w h i c h a r e a p p l i e dt ot h em u l t i l e v e lp r o g r a m m i n gp r o b l e ma r eg i v e n a m o n g t h e m ，t h ea l g o r i t h m w h i c hi s p r e s e n t e db ys h i h ，e t c i sd i s c u s s e d p a r t i c u l a r l y ，i n w h i c ht h e s o l v i n ga l g o r i t h m t ot h ei n t e r a c t i v e m u l t i l e v e lp r o g r a m m i n gp r o b l e mi si n d u c e db yt h ea p p l i c a t i o no ft h e m e m b e r s h i pf u n c t i o no ft h ef u z z ys e t st h e o r yt ob i l e v e lp r o g r a m m i n g p r o b l e m b e c a u s ei ti st o oc o m p l e xt oh a v e t h eg o a ls a t i s f a c t o r yd e g r e e a n dt h ed e c i s i o nv a r i a b l e s a t i s f a c t o r yd e g r e e t a k e ni n t oa c c o u n ti n s h i h sa l g o r i t h m ，p e o p l em e r e l yu s et h eg o a ls a t i s f a c t o r yd e g r e ei nf a c t i nt h ea p p l i c a t i o n i ti si m p o s s i b l ef o rt h ed e c i s i o nm a k e r st od e t e r m i n e w h i c hv a l u ei st h eo p t i m u mv a l u e 。s ot h ed e c i s i o nv a r i a b l es a t i s f a c t o r y d e g r e ei s n o tn e c e s s a r ya c t u a l l y m e a n w h i l e ，t h ev a r i a b l es a t i s f a c t o r y d e g r e ei sn o tt a k e ni n t oa c c o u n t b e c a u s et h ec o m p l e x i t ya n dv a r i a n c ei n c a l c u l a t i n ga c c o m p a n y i n g w i t hv a r i o u s m e m b e r s h i p v a r i a b l e sa b o u t d e c i s i o nv a r i a b l ew i l la r i s ei ft h e r ea r ev a r i o u so p t i m u ms o l u t i o n si n s o l v i n ge a c hl e v e lo p t i m u ms o l u t i o n a tt h el a s to ft h i sp a p e r ，t h es o l v i n gt ot h ea s s u r a n c ep r o b l e ma n d t h el i n e a rm u l t i l e v e l p r o g r a m m i n gp r o b l e m w i t h f u z z yp a r a m e t e r s a c c o r d i n g t ot h ew a yo ft h ei n t e r a c t i v e f u z z yp r o g r a m m i n gw i t h o u t c o n s i d e r i n g d e c i s i o nv a r i a b l ei s g i v e n t h es o l v i n g h a st h e i m p e r c e p t i b l ep r o p e r t y ，i t i sf i r s tt o b i l e v e l ，a n d t h e ne x t e n d st o 西南交通大学硕士研究生学位论文第1ii 页 m u l t i l e v e l t h ef e a s i b i l i t yi sa p p r o v e db yt h ec o n c r e t ee x a m p l e s k e yw o r d s ：l i n e a rm u l t i l e v e lp r o g l a m m i n g ；f e a s i b l es o l u t i o n ； p a r a m e t e r ；s a t i s f a c t o r yd e g r e e ； i n t e r a c t i v e p r o g r a m m i n g f u z z y f u z z y 西南交通大学硕士研究生学位论文第1 页 第1 章绪论 1 1 引言 我们知道，数学规划是属于最优化理论的重要分支，是人们在工 程技术，科学研究和经济管理等各个领域中经常遇到的问题，例如， 工程设计中怎样选择设计参数，使得设计方案既满足设计要求又能 降低成本；资源分配中，怎样分配有限资源，使得分配方案既能满 足各方的要求，又能获得好的经济效益；生产计划安排中，选择怎 样的计划方案才能提高产值和利润等等，在人类活动的各个领域中， 诸如此类，不胜枚举。最优化这一数学分支，正是为这些问题提供 了理论基础和求解方法，是一门应用广泛，实用性很强的学科。 数学规划问题是个古老的课题，长期以来人们对它进行了深入地 探讨和研究。1 9 3 9 年苏联数学家康托洛维奇( j i b k a h t o p o b f i ) 提出了解决下料和运输问题，并提出求解这两种线性规划问题的方 法。虽然人们关于最优化问题的研究工作随着历史的发展而不断深 入，但是任何科学的进步都受到历史条件限制。直到上世纪三十年 代，数学规划这个古老的课题并没：有形成独立的有系统的学科。 随着生产和科学研究突飞猛进的发展，特别是电子计算机日益广 泛应用，这使得对数学规划问题的研究不仅成为一种迫切需要，而 且有了求解的有力工具。数学规划理论和方法始终是伴随着它的广 泛应用不断臻善的，在工程、经济、商业、管理乃至一些基础科学 中( 如物理、化学等) 都会涉及到数学规划的模型、理论和方法。 从而，最终形成了一个新的学科。 我国自1 9 5 6 年以来已开始有人从事线性规划和非线性规划的理 论、方法及应用方面的研究工作，特别近几年，从事这方面工作的 人员与日俱增，同时也促进了本学科的发展。 长期以来，传统的优化和决策方法只考虑所有决策变量由一个 “独裁”的主导决策者控制并处理的情形，即只限于单层优化问题。 然而，现实世界中任何一个社会组织、机构乃至国家都可归为一个 有主从之分的分层系统，其中上级部门处于主导地位，下级部门是 有一定自主能力的从属个体。其自主性体现为它往往在定的权力 西南交通大学硕士研究生学位论文第2 页 范围内独立自主地决策，上级部门对下级的管理或领导仅仅依靠影 响其决策环境来间接导致下层决策者做出有利于上级部门的决策， 而不允许上层的直接介入或命令。这种“民主”的而非“独裁”的 决策方式更合理、更为科学。分层次的最优决策问题就是研究如何 使这类系统发挥最佳效益的基本模型，故称之为分权( 分治、分层、 分级) 规划问题，为体现主次有序，称之为多层规划问题。 多层规划问题是一种具有多级递阶结构的系统优化问题，它包含 一个上层问题和若干个下层子问题，上层问题和下层子问题都有各 自的目标函数和约束条件。上层问题的目标函数和约束条件不仅与 决策变量有关，而且还依赖于下层问题的最优解；而下层问题的目 标函数和约束又受到上层决策变量的影响，下层问题针对给定的上 层决策变量，求出自己的最优解并将该最优解反馈给其上层决策者。 对二层规划问题的研究最早可追溯到关于s t a c k e l b e r g 问题】的 个经济学解释，后来b r a c k e n 和m c g i l l 【2 j 】进一步给出了二层线性 规划问题的数学形式。8 0 年代以来，许多学者对二层规划问题进行 了深入分析，得到了一些较好的结论1 4 , 5 ，如当没有上层约束条件时， 线性二层规划问题的可行集是闭连通集，且最优值在某个极点处达 到。9 0 年代，随着二层规划横向和纵向的拓广，对其研究也随之更 加深入。下层有多个子问题的二层规划、多层规划、多层混合整数 规划、二层多目标规划及由平衡约束的数学规划等都纳入多层规划 的研究范畴，取得许多成果。在此领域表现活跃的著名学者有 a i y o s h i 、s h i m i n z u 、b a r d 、o u t r a t a 、y e 和l u o 等。 对于多层规划问题的讨论最早见于c a n d l e r 【6 7 1 。后来人们在假设 下层子问题最优解唯一的条件下推到了线性规划问题的一系列基本 性质，如可行集连通、最优值在某个极点处达到。在国内，多层规 划的研究在= 十世纪九十年代初才引起关注i s 。较早从事研究的单 位有东南大学、中科院系统所和自动化所、湘潭大学、西南交通大 学、天津大学和西安电子科技大学等，许多学者做出了优秀的工作。 人们在处理实际问题时经常遇到大量的不确定因素像模糊性、随 机性，而这些不确定性因素所带来的问题，用传统的数学规划方法 一般难以解决。1 9 6 5 年，美国加利福尼利亚大学控制论专家扎德 ( z a d e t hl a ) 教授在i n f o r m a t i o na n dc o n t r o l 杂志上发表了一篇 西南交通大学硕士研究生学位论文第3 页 开创性论文“f u z z ys e t s ” ，这标志着模糊数学的诞生。它的产生 与其它科学一样，是由于实践需要而产生的。这种模糊概念( 或现 象) 无处不在，不管是在日常生活还是在生命科学、经济管理领域。 而当代科学发展趋势之一，就是各个学科领域都要定量化、数学化， 当然模糊概念所面对的这种趋势也毫不例外地促使人们要寻找一种 解决此类问题的新的数学方法。而模糊集合作为经典集合的推广， 可以用来表示人类知识大量存在的模糊性概念。模糊集合的出现， 使人们处理带有模糊概念的问题就比较容易得多了。 在模糊集合论中，为了对模糊集中的元素有一个定量的描述， z a d e t h 9 , 1 0 教授引入了“隶属函数”的概念，同时也给出对模糊现象 的分析运算方法。在求解数学规划的实际问题中，不管是在目标函 数中，还是在约束条件中，均会涉及到模糊量的问题，这种问题是 无法用常规的数学规划方法来解决的。因此人们就设法把模糊集合 理论与传统数学规划相结合，这不仅给传统的规划问题带来了新的 活力，而且还形成了一门新的学科一一模糊数学规划。 1 2 本文的结构及主要内容 本文基于前人对相关问题的研究成果的分析，主要讨论线性多层 规划及其性质、交互式模糊规划法以及用它求解确定性和带有模糊 参数的线性多层规划问题。 1 、首先对数学规划以及模糊集理论的发展进行了简单的阐述， 重点概述国内外在多层线性规划研究的发展概况。 2 、第二章首先对线性多层规划问题进行了综合性讨论，介绍一 类特殊的线性多层规划问题的性质，然后介绍多层规划的求解算法， 其中较详细地介绍s h i h 。2 1 等人提出使用模糊集合理论的隶属函数来 解决二层规划问题，从而引出交互式多层规划求解算法。 3 、由于s h i h 等人主张交互式多层规划法应该把目标满意度和 决策变量满意度都考虑进去，显得有点复杂。作者认为，实际上只 需考虑目标满意度即可，因为在实际问题中，决策者很难知道最优 值为何值，因此所谓的决策变量的满意度要求就没有实际意义，同 时，在分别求解各层最优解时如果出现多个最优解同时存在，就会 出现多个关于决策变量的隶属函数，出现计算时的复杂性和不一致 西南交通大学硕士研究生学位论文第4 页 性，所以可以不考虑变量的满意度。这样改进的算法相对简捷、运 算量小、易操作等。因此，在最后两章中，用不考虑决策变量满意 度的交互式模糊规划法，分别来求解确定性以及带有模糊参数的线 性多层规划，求解具有渐进性，先是对二层，然后延伸到多层，并 有具体数字算例来说明方法的可行性。 最后，为了便于本文的简捷叙述，下面给出几个简单记号： 1 、线性二层规划问题一l b p p 2 、线性多层规划问题一l m p p 3 、带模糊参数的线性二层规划问题一f l b p p 4 、带模糊参数的线性多层规划问题一f l m p p 西南交通大学硕士研究生学位论文第5 页 第2 章线性多层规划问题( l m p p ) 多层规划问题是一类重要的数学规划问题，它是用于解决具有 层次结构的多个决策者参与决策的问题，其决策变量的一部分是一 个以某些变量为参数规划问题的最优解。该问题有如下特征】： 1 在一个有主从之分的层次结构系统里存在相互作用的决 策单位。 2 执行决策的过程是有序的，从上层到下层。下层决策者要 在考虑到其所有上层的决策之后提出自己的决策。 3 每个决策单位独立优化自己的目标函数，但可以被其他层 的行为或反应所影响。 4 影响某个决策的因素反应在目标函数及可行决策集上。 其决策过程可以描述为：上层决策者做出一个决策，并要求下 层决策者在上层决策的基础上独立地做出自己的最优决策。这个决 策再返回到上层决策者手中，上层决策者再考虑整体利益的基础上 做出一个决策。这个过程不断地继续直到找到一个最优决策。 2 1 问题的提出 在经济、环境、政治、生态、机械、交通等多个领域的决策中， 都存在着递阶的关系，即处于不同地位的决策者，他们在考虑问题 时都是假设其他层次的决策者会做出什么样的反应。多层规划正是 以这种递阶决策问题为研究对象的：量化方法。 同时，多层规划问题还描述了现代的社会大生产中上层决策者 和下层决策者之间的利益关系及制约关系。当上层决策者选定了下 层变量的选择范围。反过来，下层决策者根据上层决策者的选择， 决定自己的最优选择，并把这个最优选择反馈给上层决策者，从而 影响上层决策者的利益。 下面给出多层规划( m p p ) 一般模型： 西南交通大学硕士研究生学位论文第6 页 m i n z ( 五，x 2 ，) s t ( ，x 2 ，- - ，) x l , 且( 墨，t ) 解 1 1 1 i f 班( ，屯，一) s t ( x l ，x 2 ，- ，) x 2 , 且：而，- - ，t ) 解 m i 蜕一l ( ，x 2 ，t ) “( 五，x 2 ，) x t - ! ，且薯解 i n i 够( ，x 2 ，t ) j t ( 五，恐，x t ) ( 2 1 ) 其中而r 一为第i 层决策者控制变量，工： 石- r “为第i 层决 策者的目标函数，x cr 8 ， i = 1 ，2 ，t ， = h 1 + n 2 + + 。 特别地，当t = 2 时，上述问题称为二：层规划( b i l e v e lp r o g r a m m i n g ) ； 当t = 3 时，问题( m p p ) 称为三层规划( t r i l e v e lp r o g r a m m i n g ) 。 对于多层规划问题r m p p ) ，定义其容许集x = n 石2 n n ， 同时为了讨论的方便，类似于【1 3 ，1 4 】可以定义 第t 层问题的可行集s ( 五，x 2 ，、i ) = tjx = ( 而，而，- l ，) x 。 ； 第t 一1 层问题的可行集s t - 1 ( ，而，一2 ) = ( t _ 1 ，五) i 工= ( 而，x 2 ，+ ) z 卜1 ，且d r g r a i n z ( x t ，屯，一1 ，若) l 易s ( ，恐，- ，一1 ) ) ： 第i 层问题的可行集s ( 五，x 2 ，而一。 ) = ( x i ，_ + 】，x c d i ，) lx = (_ ，t ，t 一1 ，_ )x ，并且， ( x i + i ，鼍+ 2 ，- ，x ) a r g r a i n ，：+ l ( 吒，屯，- ，t ，x f + l ，五) i “，蕾+ 2 ，萎) s ”。( ，z 2 ，x i ) ) ) ；i = f 一1 ，t - 2 ，2 ； 第2 层问题的可行集s 2 ( ) = ： ( 屯，恐，) l 了= “，屯，薯) x 2 ，( 而，x 4 ，) a r g r a i n 携( 玉，屯，x _ 3 ，毛) i ( 毛，矗，五) 酽( x l ，屯) 第1 层问题的可行集= ( 一，x 2 ，) lz = ( 葺，屯，x t ) x 1 且 ( x 2x 3 ，x ，) a r g m i n ( f 2 “，叠，五) i ( 点2 ，为，萎) s 2 “) 根据以上定义，可以称j 1 为( m p e ) 问题的可行集，记为= f ， 并且，多层规划f 艘p ) 问题可以简写为： 西南交通大学硕士研究生学位论文第7 页 c 删黜怒苏s 。 z ， 定义2 1 若z f ，则称j x 是( m p p ) 的可行解。 定义2 2 若i f ，对任意x f ，且石( i ) 石( x ) ，则称i 是( 肘即) 问题的全局最优解。 定义2 3 若i f ，存在i 的一个邻域( - j ) ，任意鼻f nn ( 2 ，d ) ， 且石( _ ) z ( 王) ，则称i 是( 脱p p ) 问题的局部最优解。 当问题的目标函数和约束条件均是线性函数时，我们称为线性多 层规划问题( l m p p ) 。 为了讨论问题的方便，假定y 和z 是e u c l i d e a n 空间的有限维向 量，且( y ，z ) 是两个向量的内积，从而线性多层规划问题( 脚) 朐模 型可表示为 t l m p p ) m i n ( c l 薯) s ( 五，x 2 ，x t ) 缸i s j ( ，x 2 ，x t ) x l 4 ，t 6 1 ) ， - 5 2 ( 2 3 ) m i n i c ，x t ) f s ? ( 五，) x l 4 j t 包) f = i 其中q ，j r ， 6 f r 竹， 4 ，i r 砷。 ，( f ，七= l ，2 ，t ；j = f ，i + 1 ，- 一，f ) ，从模 型中可以看出，下层问题的目标函数省略了他上层的决策变量是因 为处理下层问题时，该层决策者是在上层变量已经固定的条件下求 西南交通大学硕士研究生学位论文第8 页 解他自己的多层规划问题。由于一般模型具有复杂的性质，所以只 讨论文献 1 2 中给出的特殊的模型，其一般形式为 ( s l m p p ) 柚( q ，薯) s t ( x l ，屯，) xl 矗，葺6 l m ! n ( c 2 一屯) s f ( 五，岛，) x l 4 ， 6 2 ) m i n ( c 。，x t ) t s f ( 五，x 2 ，x t ) e 缸l 4 ；玉岛) l = l ( 2 4 ) 其中c 1 i r “，q ，r ， 觑r 叶，4 te r _ 帆， ( i = 1 ，2 ， j = 2 ，3 ，t ；k = 1 , 2 ，i ) 。 这类模型是b e n s o n 1 2 1 提出来的，该模型具有很好的性质，如可 行集是由容许集的一些面组成等，我们将在下一节按本文定义2 。1 来分析s l m p p 的基本性质。 2 2s l m p p 的基本性质 引理2 1 18 1 如果容许集z 非空有界，则x = ( 五，屯，而) 为( s l m p p ) 的可行解的充分必要条件是工月且当i = l ，2 ，t - 1 时，对给定的 五，x 2 ，一- ，而，( x i + ，t + ：，) 是子问题 m i n ( c ，1 ，五“) i j 。4 。蕃。兰岛。- e 4 扎j t ， j = i 西南交通大学硕士研究生学位论文第9 页 ( 2 5 ) 4 ，西i 一4 。j x j j = lj = l 的最优解。 由引理2 1 可知， 1 2 中( s l m p p ) 可行解的定义是本文定义的一 个充分条件，子问题( 2 5 ) 的可行集是 1 2 中相应子问题可行集的 子集，当容许集x 有界时，并不能保证1 1 2 】中子问题的可行集一定有 界，从而不能保证一定有最优解。 弓i 理2 2 1 2 1 x 1 ，x 2 x ，0 丑l ，若x = 五工1 + ( 1 - 五) 工2 f ，贝x 1 f 由此引理有如下推论 推论如果x 1 工2 x ，一薯f ，则线段 m x 2 ) = x = 肌1 + ( 1 - 五) x 2 ，o 旯1 ) 上所有的点均不是可行解。 证明 假设存在线段lx 1 ，x 2 ) 上一点x = 2 , x 1 + ( 1 一旯) x 2 f ，由于 x 1x 2 x 且0 1 ，由引理2 2 有x 1 f ，这与已知条件矛盾，从而结 论成立。 定理2 3 如果工f 是f 的极点，则x 也是z 的极点。同时，如果 z x 是x 的极点并且x f ，则x 也是f 的极点。 证明如果x 芒f 是f 的极点，假设z 不是x 的极点，则存在 工1 ，x 2 x 及0 丑 1 使得x = 兄石1 + ( 1 一a ) z 2 ，由弓i 理2 2 知x 1 f ，且x 2 f ， 但这与算是f 的极点矛盾，从而z 是工的极点。 如果x x 是j 的极点并且石f ，但x 不是f 的极点，则存在 一，x 2 f 及0 丑 1 使得x ，= 缸+ ( 1 一i k ，令= ( 五一1 ) a ，则 x = 丑i + ( 1 一a ) 嘞，0 爿 1 ，由于i ，x 2 k x ，且x f ，根据引理2 2 有 i f ，因此世f 定义2 4 设s 是r “中的闭凸集，k c s 且芷为凸集，若对任意 工，y s ，x y 当以置y 为端点的闭线段 x ，y 】的相对内部与k 的交集非 空时，一定有墨y 1 c k ，则称k 是s 的面 显然，空集和s 自身都是s 的面 由定理2 5 ，显然有如下推论 推论设盖是容许集x 的非空面，存在x r i ( x ) ，且x f ，则 x 1 暑f 由于容许集是一个非空有界的多面体，因此它仅有有限个面。下 面将证明可行集由容许集的一些面组成 引理2 6 ”阳设s 是r “中的闭凸集，则对于任意石s ，均存在唯一 的面k 使得x r i ( k ) 定理2 7x ( 1 ) ，x ( 2 ) ，x ( w ) 是容许集x 的所有非空面，则 f = u x ( i ) ，其中妒是w = 1 ，2 ，w ) 的一个予集 i c w 证明由于容许集z 非空有界，任意取x x ，我们可以用引理2 1 提供的方法得到一个可行解i f ，因此( s l m p p ) 的可行解菲空 由定理2 5 的推论，可以设旷为使得对所有i 矿，均存在 z 一( x ( f ) ) ，且工f 的w 的最大子集，因此f ox o ) ，反之，对任 意石f x ，由引理2 6 知，存在并的唯一一个面x ( i ) ，使得 z “( 爿( f ) ) ，由旷的定义可知，i 旷，因此f u ，从而结论成 西南交通大学硕士研究生学位论文第1 1 页 立 由于多层规划可以简写为( 2 2 ) 的形式，如果目标函数为线性 函数且可行集为某些闭区间多面体的并集时，可以证明最优解一定 可以在可行集的某个极点处达到。 定理2 8 ( 脱脱p p ) 的最优解一定在容许集的某个极点处达到 证明由以上论述过程可知，可行集f 是有界闭集，根据( s l m p p ) 的等价形式( 2 2 ) ，我们知道( s l m p p ) 一定可以达到最优解 假设( s l m p p ) 的最优解不在任意一个极点达到，不妨设 x = ( x i ，也，x t ) 为其最优解，由定理2 7 ，设x x ( 1 ) ，由于容许集z 是 非空有界多面体，而并( 1 ) 是x 的一个面，因此也是非空有界多面体 集，于是存在的工( 1 ) 极点一，工2 ，r 以及五1 ，丑2 ，满足 工= ；，五v ，且| - 。- - 1 则不等式：；，( q _ ) 二彤一o ) = 口l ，o ) ，矛盾 因此假设不成立，定理得证。 以上证明了( s l m p p ) 问题可行集的一些基本性质，从而我们知 道，( s l m p p ) 最优值可在容许集( 或可行集) 的某个极点处达到。 2 3 交互式多层规划求解算法 2 3 。1 二层系统决策的决策机理 1 、上、下层之间交互的三个阶段怕“ 二层决策就是上下层的决策者相瓦作用、交互，共同做出决策 的过程。上下层之间的交互可以分为三个不同的阶段：预期，指示 和反应。 。 ( 1 ) 、预期( a n t i c i p a t i o n ) 西南交通大学硕士研究生学位论文第12 页 在这一阶段，为给出一个可行的决策，上层考虑下层有关的特 征，称这些特征为“设想的下层”，通常，设想的下层仅仅是上层对 下层的一种大致描述或对下层某些方面的把握，预期就是选择一个 设想的下层并考虑它对上层决策的可能影响，一般地，预期可理解 为下层对上层潜在影响。预期是描述层次系统的主要概念之一。 ( 2 ) 、指示( i n s t r u c t i o n ) 在对下层做出预期后，上层做出相应的决策，这个决策将会影 响到下层决策，称这一决策为上层对下层的指示，指示可以看作是 上层对下层的影响。 ( 3 ) 、反应( r e a c t i o n ) 下层在接受上层的指示后所做出的决策成为反应，反应下层对 上层的显示影响，也可以把反应理解为一种反馈影响，以区分预期 阶段的前馈影响。 只要“反应”成为可能，便有上、下层之间的交流、沟通和谈 判，在许多情况下，不止一个这种“预期一指示一反应”，而需要多 次自上而下和自下而上的交互，上、下层方能最终获得一个可实现 的目标系统的决策，上、下层之间的交换关系可以用下图表示： 熬1 上下层的交誊 2 、上下层之问的交互过程 现在考察上、下层之间的交互过程。假设作为决策个体的上下 层决策者的决策过程分别为z ； m k l i k = l ，2 ， 和 z 。= f m k l k = 1 ，2 ， ，上层的第k 个决策阶段记为m k l ，其决策记为 d k 7 d k 7 ，上层决策者在考虑了上一轮下层的( 最优) 反应r k 一1 ， 并对下层做出预期a k 7 后，做出最优指示i k + = i ( d k 。) ，最优指示是由 上层将目标准则进行优化而得到的。下层在接受到上层的( 最优) 西南交通大学硕士研究生学位论文第13 页 指示i k + 后，做出最优反应r k ，最优反应是根据优化下层目标准则而 得到的。把这样的交互过程进行下去，直到得到一个上、下层均可 以接受( 满意) 的最终决策。 由此可以总结出二层系统决策的决策机理：上层给下层一定的 政策( 指示) ，下层依据这些指示，按照自己的可能条件和利益准则 做出反应；上层必须预见( 预期) 到下层的这种反应而设计好自己 的策略，以期做出符合全局利益的决策，上层给出的指示不但制约 下层的可行域，而且影响下层的目标( 指标) 函数，下层的反应则 是对上层指示的对策，这种对策在下层看来是最好的；下层的反应 ( 响应) 又反过来影响上层的目标函数，最后上层综合下层反馈上 来的信息，调整自己的决策，使整体的决策尽可能达到最优。 2 3 2 多层规划交互式求解算法 二层规划确定性求解算法主要分为二种，一种是定点列举法， 另一种是转换法，转换法主要基于惩罚函数【32 ”】和基于k u h n t u c k e r 条件【33 ，”j 两类。顶点列举法的缺点在于当模型复杂或变量很多时， 该方法缺乏效率：而转换法则是将下层规划问题转换成上层的约束， 其缺点在于转换后的约束经常呈非线性，使得运算处理上增加了困 难度与复杂性。s h i h 等人【2 2 】提出使用模糊集合论的隶属函数来解决 二层规划问题，其方法如下，考虑如下的二层规划问题： m 。i n f l ( x l ，x 2 ) = q 1 西+ c 1 2 屯 m 如i n 五( 五，屯) = c 2 j x t + c 2 2 屯 ( 2 - 6 ) s f 4 鼍+ 4 屯b 而，x 2 0 其中，决策变量而，分别为上、下层的决策者的控制向量，两目 标函数z ，五也分别被视为上下层决策者的绩效函数，且为线性、有 边界的，此外q l , c l ：，c 2 ，与b 为常数向量，4 ，4 为常数矩阵。上下层 决策者根据其目标函数与约束，分别求出其问题的解，假设上层的 解为( 茸，l ，斤) ，下层的解则为( ，) ，其中，上层l 代表领导 者( l e a d e r ) ：f 代表追随者( f o l l o w e r ) 。上下层均将结果告知对方 西南交通大学硕士研究生学位论文第1 4 页 如果( 对，瑶) = ( x i ，x ；) ，则可获得最优解，但这通常是少见的，因为两者 的目标在本质上存在着冲突。如上层决策者可以给予其变量五一定程 度的“容忍范围”，则可以使得下层决策者有较宽广的空间以寻求最 优解。假设五的最大容忍范围为p ，则通过模糊集合论，我们可以建 立x a 的隶属函数： “。( 五) = ( 2 7 ) 同样，上层决策者也可以根据其目标函数值，指定其可容忍的 范围，以便当下层决策者寻求最优解时，给予监督或指引。假设上 层决策者可接受的目标函数值下限为石= _ ：( ，而f ) ，则工的隶属函数 为： ( f ( x l ，而) ) l ，石( 五，屯) 【z ( ，t ) 一z j e f , 一z 】，石 z ( 西，屯) _ ( 2 - 8 ) o ，五( 葺，x 0 - a i ( 2 9 ) ( 工瓴，x o ) 声 西，而0 口 o ，1 1 ，“0 ，1 】 耐枷 一 一 p 葺 一 一 砰砰他西b 其，弘q 讷_钟印矿睹 旷卜卜儿110 西南交通大学硕士研究生学位论文第15 页 ， 啜2 可轷区域圈 其中，口与分别为决策变量x t 与目标函数 ( 五，而) 的最小可接受 的满意水平；i 为单位向量， u 。“) 口，与” ( 石“，屯) ) ，两约束所 围成的可行区域为图2 中粗线的部分。显而易见，下层决策者可以 根据上层决策者制定的不同的口与p ，来分析所对应的不同的解。面 对许多可以提供给上层决策者参考的解，当然下层决策者也可以针 对其目标函数建立所属的隶属函数，这样它可以对于不同的解来评 估自我满意水平。假设下层决策者根据目标函数建立起来如下的隶 属函数： u a ( 五( ，也) ) = l ，( 五，而) 五( 而，而) 一 1 z ，矗 正( 而，屯) s 岔( 2 1 0 ) o ，厶“，屯) h ( z ( i ) ) ，那么d m l 通过增加占来更 新最小满意水平舌，从而得到更新的满意水平彦，这时d m 2 就解带 有争的问题( 3 7 ) ，那么d m l 就得到