（控制理论与控制工程专业论文）基于鲁棒优化的电梯群控调度策略的研究.pdf

摘要 论文主要研究了基于鲁棒优化的电梯群控调度。 鲁棒优化作为研究不确定优化问题的一种新方法，受到了众多学者的青睐。 论文在对不确定优化问题分析的基础上，对鲁棒优化研究的代表人物b e n t a l 和 b e r t s i m a s 的研究成果进行了总结，重点对鲁棒线性规划和鲁棒离散优化进行了 阐述。研究了不确定优化问题鲁棒优化模型的建立，充分体现了其事先分析的建 模策略，即在问题的优化模型中充分考虑了参数的不确定性，使参数在所给不确 定集合内的所有实现均能满足问题的约束条件，而对其服从何概率分布没有要 求。此后，论文重点阐述了鲁棒优化研究的核心问题，即如何将所建立的鲁棒优 化模型转化为鲁棒对等式，使初始的不确定优化问题转化为计算易处理的确定性 优化问题，从而采用优化软件对问题进行求解。 随着社会的发展，人们对大楼内垂直交通的要求使得电梯群控调度成为一个 很重要的研究课题。对于该课题经历了从传统方法到智能方法的转变，本文在对 已有方法分析的基础上，重点对电梯群控调度中存在的难点，即交通流不确定性， 进行了讨论。从优化的角度对电梯群控调度问题进行分析，结合b c r t s i m a s 鲁棒 优化研究框架，把交通流当作不确定参数，把乘客候梯成本的最小化当作目标， 建立了该问题的鲁棒优化模型，即鲁棒0 - 1 离散优化。同时，还在问题的分析中 采用了按层派梯的思想和重派梯策略，在候梯成本的计算中考虑了电梯的门状 态，增加了调度的合理性。经过推导得到的优化模型的鲁棒对等式最终等价于一 个混合整数规划。 编写群控算法，在其内完成上述混合整数规划的求解。通过交通流发生器模 拟产生上高峰、下高峰和随机层间三种模式交通流，在电梯群控虚拟仿真环境中 进行仿真实验。通过与其它调度算法的实验结果进行比较，显示了本文算法在不 同交通流条件下的优异性能，验证了所建电梯群控调度鲁棒优化模型的可行性。 关键词：不确定优化鲁棒优化鲁棒对等式电梯群控调度 a b s t r a c t t h i st h e s i sm a i n l yf o c u s e so nt h er e s e a r c ho fe l e v a t o rg r o u pc o n t r o ls c h e d u l i n g p o l i c yo i lr o b u s to p t i m i z a t i o n r o b u s to p t i m i z a t i o nh a sb e e nr e m a r k a b l eb ym a n yr e s e a r c h e r sa san e wm e t h o df o r d e a l i n gw i t l lu n c e r t a i no p t i m i z a t i o np r o b l e m s a l t e rh a v i n ga l la n a l y s i so uu n c e r t a i n o p t i m i z a t i o np r o b l e m s ，t h et h e s i si n t r o d u c e st h er e s e a r c hr e s u l t so fb e n t a la n d b e r t s i m a s ，a n dm a i n l yh a sad e t a i ld i s c r i p t i o no nr o b u s tl i n e a rp r o g r a m m i n ga n d r o b u s td i s c r e t eo p t i m i z a t i o n t h i st h e s i sa l s oi n t r o d u c e sh o wt om o d e lt h eu n c e r t a i n o p t i m i z a t i o np r o b l e m sa n dg e t st h er o b u s to p t i m i z a t i o nm o d e l ，i n d i c a t i n gt h ep o l i c y o fp r i o r - a n a l y s i s ，t h a ti st a k i n gi n t ot h ep a r a m e t e ru n c e r t a i n ya c c o u n ti nt h e o p t i m i z a i t o nm o d e l ，m a k i n gs u r eo fc o n s t a i n ts a t i s f a c t i o no nt h er e a l i z a t i o no f a l lt h e p a r a m e t e r st h o s em a k ev a l u e si nt h eg i v e nu n c e r t a i ns e t , a n dn o to r d e r i n gt h e p a r a m e t e rt oo b e ys o m ep r o b a b i l i t yd i s t r i b u t i n g a f t e rt h a t ，t h e t h e s i s m a i n l y i n t r o d u c e st h ec o r ep r o b l e m w h i c hi sh o wt ot r a n s f o r mt h er o b u s to p t i m i z a t i o nm o d e l i n t ot h er o b u s tc o u n t e r p a r t t h ep u r p o s ei st ot r a n f o r mt h ep r i o ru n c e r t a i n o p t i m i z a t i o np r o b l e mi n t oat r a c t a b l eo p t i m i z a t i o np r o b l e m ，w h i c hc a l lb es o l v e db y o p t i m i z a t i o ns o t ) w a r e w i t ht h e d e v e l o p m e n to ft h es o c i e t y , t h er e q u i r e m e n to fab e t t e r v e r t i c a l t r a n s p a t a t i o ns e r v i c ef o rt h ep e o p l ei nt h eo f f i c eb u i l d i n gm a k e st h ee l e v a t o rg r o u p c o n t r o ls c h e d u l i n gb e c o m i n ga l li m p o r t a n tp r o b l e m t h e r ei sac h a n g ef r o mt h e c l a s s i c a lm e t h o d st oa r t i f i c i a lm e t h o d so nt h ep r o b l e m o nt h eb a s i so f a n a l y z i n gt h e m e t h o d st h o s em e n t i o n e da b o v e ，t h i st h e s i sm a i n l yd i s c u s s e st h ed i f f i c u l t yo ft h e e l e v a t o rg r o u pc o n t r o ls c h e d u l i n g ，w h i c hi st h eu n c e r t a i n t yo ft r a f f i cf l o w t h i st h e s i s a n a l y z e st h ee l e v a t o rg r o u pc o n t r o ls c h e d u l i n gf r o mt h ep o i n to fp r o g r a m m i n g ， i n c o p o r a t i n g w i t ht h eb e r t s i m a sr e s e a r c hf o r m u l a t i o no nr o b u s to p t i m i z a t i o n t r a f f i cf l o wi sa st h eu n c e r t a i n t yp a r a m e t e r t h em i n i m i z i n gc o s to fp a s s e n g e r s w a i t i n gt i m ei sa st h eo b j e c t i v e t h er o b u s to p t i m i z a t i o nm o d e lo fe l e v a t o rg r o u p c o n t r o ls c h e d u l i n gi sar o b u s t0 - 1d i s c r e t eo p t i m i z a t i o n a tt h es a m et i m e ，t h i st h e s i s n o to n l ya d o p t st h ei d e ao fd i s p a t c h i n gf l o o ra n dt h ep o l i c yo fr e d i s p a t c h i n g ，b u ta l s o t h i n k sa b o u tt h ed o o rs t a t eo ft h ee l e v a t o rd u r i n gt h ec o m p u t a t i o no ft h ec o s to f p a s s e n g e r s w a i t i n gt i m e ，w h i c he n h a n c e st h er e a s o n a b l i l i t yo ft h es c h e d u l i n g a f t e r t h ed e d u c t i o no nr o b u s t0 - 1d i s c r e t eo p t i m i z a t i o n ，t h er o b u s tc o u n t e r p a r ti se q u a lt oa m i x e di n t e g e rp r o g r a m m i n gf i n a l l y t h em i x e di n t e g e rp r o g r a m m i n gi ss o l v e di nt h eg r o u pc o n t r o la l g r i t h o mf o rt h i s t h e s i s a f t e rp r o d u c i n gt h eu p - p e a kt r a f f i cf l o w , d o w n - p e a kt r a f f i cf l o wa n dt h e s c h a o s t i cf l o o rt r a f 菇cf l o wi nt h et r a f f i cf l o wp r o d u c e r , t h es i m u l a t i o n sa r ed o n ei nt h e e l e v a t o rg r o u pc o n t r o lv i r t u a ls i m u l a t i o ne n v i r o m e n t r e s u l t ss h o wt h eg o o d p e r f o r m a n c eo nd i f f e r e n tt r a f f i cf l o w sf o rt h ep r o p o s e da l g r i t h o mi nc o n t r a s tt ot h e o t h e ro l l e s ，a n da l s ov e r i f yt h ef e a s i b l i t yo ft h er o b u s to p t i m i z a t o nm o d e lo ne l e v a t o r g r o u pc o n t r o ls c h e d u l i n gp r o b l e m k e yw o r d s ：u n c e r t a i no p t i m i z a t i o n ，r o b u s to p t i m i z a t i o n , r o b u s tc o u n t e r p a r t , e l e v a t o rg r o u pc o n t r o ls c h e d u l i n g 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得墨鲞盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：孑小志、娟签字日期： 石年- 7 月；日 学位论文版权使用授权书 本学位论文作者完全了解鑫盗蠢鲎有关保留、使用学位论文的规定。 特授权墨鲞盘鲎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部f j 或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：球薄赠 导师签名： 签字日期： 似年1 月弓日 签字臼期：嘶7 月 日 第一章绪论 1 1 课题的选择依据 第一章绪论 优化是在多种决策中挑选最好决策的问题。在理论上，优化是决策科学中一 个非常重要的分支，它与数学、管理、生命、系统、自动化、力学等学科有着密 切的联系，同时互相促进。在实际应用中，优化作为人们一个强有力的思想，其 研究已经在物理和化学系统、生产规划和调度系统、交通系统、商业系统中的资 源分配和工程设计等许多领域得到应用，产生了巨大的经济效益和社会效益。随 着优化理论研究的深入，它对社会发展的贡献将越来越大。 在优化技术的理论研究和实际应用中，不可避免的都存在着客观的或入为的 不确定性因素。不确定性表现在系统的结构或系统的参数上。不确定性因素给优 化问题的研究带来了机遇，同时也带来了挑战。人们对决策和优化结果低风险的 追求是不确定优化问题深入研究的一个很重要的原因。 1 1 1 不确定优化命题的提出 在不确定优化问题的研究中，开创性的工作已经由b e a l e 、b e l l m a n 、z a d e h 、 c h a r n e s 、c o o p e r 、d a n t z i g 和t i n t n e r 等人于2 0 世纪5 0 年代中期完成。尽管基于 不确定性的优化理论和算法至今得到了快速发展，但是d a n t z i g 仍认为其是优化 领域中最重要的问题之一i 】1 。 在展开不确定优化问题的讨论之前，首先对传统优化问题有一个概念性了 解，传统优化模型的数学表达形式如下： m i n ，( i ) s ，g ，( i ) 0 , i = 1 ，州( 1 - 1 ) 式中，表示目标函数、g 。，i = 1 ，m 表示约束函数，m 表示约束函数的个数， x 孵“表示仃维决策向量，目标函数和约束函数都有确切的表达形式。 在传统的优化问题数学表达式中，优化模型的结构和参数是确定的。但是， 在实际当中，不确定性无处不在，它的产生是由决策环境引起的，既有系统本身 的因素，也有人为的因素在里面，这些不确定因素可能对优化模型的结构和参数 产生影响，从而使得优化模型的解不再满足约束条件，同样，优化模型的最优目 第一章绪论 标值也就不成立了。如何在问题的分析中将不确定性因素纳入到所建立的优化模 型的范畴中去，并在此基础上通过采用有效的算法使问题得以解决就成为一个很 重要的课题。在本文接下来的讨论中，主要针对系统优化模型的参数不确定性展 开讨论。 在对不确定优化问题进行分析之前，要明确参数的不确定性是如何产生的。 在实际问题当中，参数不确定性与以下几个因素有关 2 f 1 7 1 ： 第一，在数据采集和数据统计过程中，由于测量工具和测量方法的不同，不 可避免的存在数据测量误差。 第二，在问题的分析中，有时需要用到部分当前并不存在而需要事先给定或 预测的数据，如未来需求、价格等，这样就不可避免的存在数据预测误差。 第三，所建模型有时并不能充分表达研究对象，如用近似的简单模型来描述 复杂的对象等，对模型的离散化和定量化都有可能产生不确定性，这样对于那些 不确定数据就有可能采用其期望值来表示，不可避免的存在数据替代误差。 第四，模型的解有时候并不能通过精确计算得到，在执行过程中会用近似数 据进行代替，不可避免的存在数据执行误差。 1 1 2 不确定优化问题的基本分析 在对优化问题的分析过程中，将参数不确定性因素考虑进去，就有两种不同 的思路：一种是采用事先分析技术，即将能够考虑到的参数不确定因素纳入到优 化模型的建立中，使得优化模型的解具有鲁棒性；一种是采用事后分析技术，典 型的方法是灵敏度分析，即在建立优化模型的过程中，不考虑参数不确定性因素， 在得到模型的优化解之后，使得模型参数在一个确定的范围内发生改变，观察其 对优化解的影响程度。如果在设计范围内，问题的解对于参数变化很敏感，那么 表明此时得到的优化解不能满足要求。总而言之，这种事后分析技术方法相对简 单，是一种事后被动的而不是事先主动的处理模型参数不确定性的方法，这也是 该分析策略的最大弱势所在。 为了能够更加真实地建立决策环境中问题的优化模型，最佳的方案是使得数 据的不确定性在所建立的优化模型中得以体现，采取事先分析的建模策略，本文 的讨论也是以此策略为基础的，这样得到不确定优化模型的数学表达形式如下： m i nf ( x ，蛰 s g ( x ，曲o ，v ；u ，i = 1 ，所 ( 1 2 ) 式中，厂表示目标函数，g ，i = l ，m 表示约束函数，m 表示约束函数的个数， x 9 t ”表示疗维决策向量，；表示不确定参数，u 表示不确定参数的集合，目标 函数和约束函数都有确切的表达形式。 第一章绪论 对于由( 1 2 ) 式表达的不确定优化闯题，可以根据不确定集u 的不同而进行如 下分类唧8 i ： 第一，如果u 是一个情景集，如：是有限状态的集合。因为集合内仅包括有 限离散的状态，所以分析起来不是很复杂，这种优化问题被称作情景设计问题 ( s c e n a r i od e s i g np r o b l e m ) ，有时也被称作随机鲁棒优化问题( s t o c h a s t i cr o b u s t o p t i m i z a t i o np r o b l e m ) 。 第二，如果u 是一个随机不确定集，如：u 是一个随机变量的集合，它的 分布是已知的，可以通过连续的或离散的概率密度函数表示，以期望结果最大化 为目标，这种优化问题被称作随机优化问题( s t o c h a s t i co p t i m i z a t i o np r o b l e m ) 。 第三，如果影是一个模糊逻辑集合，这种优化闯题被称作软约束优化闯题 ( s o f tc 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 ) ，在数学上也被称为模糊数学规划( f u z z y m a t h e m a t i c a lp r o g r a m m i n g ) 。 第四，如果u 是一个有界闭集，这种优化问题的分析是建立在凸优化理论基 础之上的，被称作鲁棒优化问题( r o b u s t o p t i m i z a t i o np r o b l e m ) ，虽然其与随机优 化很相似，但是不确定集( ，的概率分布是未知的，要求对于所有的约束函数，f 的任何实现都在【，内。 在不确定优化问题的研究中，对于“大”数据不确定性经常通过随机优化的 方法，首先得到不确定参数的分布模型，通过该分布产生大量的采样样本，用期 望值代替不确定参数来解决问题。这种方案的优点：事先主动的、直观的，可以 从概率信息中找到数据值；缺点：在许多情况下，很难得到可靠的不确定数据的 分布规律，对于低概率事件往往不予考虑，难于实现“硬”约束，而且，问题难 于求解。 在不确定优化问题的研究中，对于“小”数据不确定性经常被忽视，问题中 不确定参数多采用数据的“标称”值。这种方案的优点：问题很快得到简化；缺 点：在许多情况下，小数据扰动会使优化解严重不可行，或者对目标而言具有“高 代价”，因此，在实际中毫无意义。 在不确定优化问题的研究中，近年来清华大学的刘保碇等人f 9 阳2 懈优化问题 中所出现的不确定参数看作不确定变量，并将其分为三种基本类型：随机变量、 模糊变量、粗糙变量，将含有不确定变量的目标函数或约束函数称为不确定函数， 在此基础上，提出了可信性理论。在建模理念的角度上，总结出三条基本途径： 第一，从期望值的角度出发。用不确定函数的期望值分别代替原来目标函数和约 束条件中的不确定函数，建立期望值模型。第二，从机会测度的角度考虑。当约 束条件中含有不确定变量且必须在观测到不确定变量实现之前作出决策时，采用 一种原则：允许所作决策在一定程度上不满足约束条件( 不考虑违反约束条件的 第一章绪论 惩罚) ，即只要求使约束条件得到满足的机会测度不小于预先给定的置信水平。 第三，极大化事件实现的机会( 如概率测度、可能性测度、必要性测度、可信性 测度、信任测度等) 。 1 1 3 鲁棒优化概念的提出 在不确定优化问题的研究中，有一种新的建模思想，即鲁棒优化。鲁棒优化 是一个含有不确定输入的优化问题的建模方法，是随机规划和灵敏度分析的补充 替换，其不确定集u 是一个有界闭集，与其它不确定优化方法的最大区别在于： 第一，鲁棒优化强调的是所谓的硬约束，寻求一个对于不确定输入的所有实 现都能有良好性能的解，即不确定优化闯题的解对于任何一个f u 的实现都必 须是可行的，而其它不确定优化问题并没有这个要求1 2 1 1 ”1 。 第二，鲁棒优化的建模思想与其它优化方法不同，它是以最坏情况下的优化 为基础，这代表了一个保守的观点。褥到的优化方案并不是最优的，僵是，当参 数在给定的集合内发生变化时，仍能确保优化方案是可行的，使模型具有定的 鲁棒性，即优化方案对参数扰动不敏感。 第三，鲁棒优化对于不确定参数没有分布假定，只是给出不确定参数集，不 确定参数集合内的所有值都同等重要。 1 2 鲁棒优化的国内外研究现状 首次采用鲁棒优化的思想解决不确定线性优化问题是由美国弗吉尼亚州立 大学的a l s o y s t e r l l 4 1 于1 9 7 3 年提出的，虽然其方法过于保守，但它是研究不确 定优化问题的一种新思路，是基于对所谓最环情况优化的考虑，从而弓陡；了众多 学者的关注，为此后鲁棒优化理论的快速发展建立了基石。 1 2 1 基于m u i r a y 的鲁棒优化 鲁棒优化的概念是由美国普林斯顿大学的j m m u l v e y 于1 9 9 1 年至1 9 9 5 年 作为首席科学家对由美国空军科学研究基金资助的名为“大规模系统鲁棒优化： 一项新技术”的项目研究中与另两位学者r j v a n d e r b e i 和s a z e n i o s 首次提出 的。1 9 9 3 年，e s c u d e r o 等人提出了制造业中外部采购问题的鲁棒优化模型。1 9 9 5 年，g u t i e r r e z 和k o u v e l i s 提出了多国间生产调度问题的鲁棒优化模型。同年， m u l v e y 等人给出了基于情景集的鲁棒优化的一般模型框架，发表了在该方向研究 上的两篇重要文献l 蟮 f j 。他们将优亿模型中的变量分为不受输入数据影响的设 第一章绪论 计变量和受输入数据影响的控制变量，并相应的给出结构化约束和控制约束，为 了定义鲁棒优化问题，介绍了一个情景集，给出了每个情景不同实现下的概率， 提出了解鲁棒和模型鲁棒的概念，将目标函数分为聚合函数和罚函数，使得不同 情景下得到的优化值变化不大，以此来消除参数不确定给优化问题带来的负面影 响。同时，还将其与处理数据不确定性的灵敏度分析和随机优化方法进行了比较， 利用就餐问题和高风险决策问题很好的说明了鲁棒优化的概念。尽管鲁棒优化模 型的求解采用并行计算的方法相对于线性优化求解更加复杂，但还是将鲁棒优化 模型应用到了实际的优化调度问题中，如电力容量扩展问题、矩阵平衡问题、图 像重构、美国空军航线调配问题等。应用表明，该方法对于减少因参数变化而频 繁修正优化模型的情况起到了一定的积极作用。除此以外，1 9 9 8 年，乔治亚科 技学院的a h m e d s 等【1 7 利用基于情景集的鲁棒优化方法对化工流程规划问题进 行了研究。1 9 9 8 年，美国科罗拉多州立大学的m l a g u n a 亭【1 8 】在m u l e y 对鲁棒优 化研究的基础上，针对电信网络的容量扩展问题建立鲁棒优化模型，将需求作为 不确定因素，用场景对不确定参数进行建模，建立了其基于情景集的鲁棒优化模 型，采用动态规划递归和最短路径的求解方案，结果表明：计算时间对所有场景 中需求最大值的敏感度大于对场景个数的敏感度。2 0 0 0 年，台= i l s h i hc h i e n 大学 的c h i a n - s o n v u t l 9 1 等在研究随机物流问题中，针对物流规划和库存管理中存在的 不确定性，在m u l v e y 等人研究的基础上提出了新的基于情景集的鲁棒优化框架， 其特色是减少了一半的控制变量和约束的数目，大大减轻了优化模型求解的负 担，使得基于情景集的鲁棒优化方法可以得到更为广泛的应用，但是还有两个不 足之处，首先是只能处理线性模型：其次是目标函数和约束中的所有系数必须是 易于说明的。2 0 0 2 年，香港城市大学的s ，c h l e u n g 等1 2 0 l 对于香港制造商在内 地建厂后，产品在香港和内地之间的物流运送问题，建立了情景优化模型以获得 一个长期的交通运输策略，从而减少运输成本，计算结果表明了采用该方法解决 不确定环境下物流问题的有效性。 通过对基于情景集的鲁棒优化的分析，发现在该方向上的研究主要集中在 2 0 世纪9 0 年代中期至2 1 世纪初的这段时间里，其q 6 m u l v e y 等人将该方法应用 到了许多实际问题中，取得了一定的成果。在该方法中，不确定参数由情景集表 达，情景由离散概率分布函数或者连续概率分布函数的离散化形式表示。尽管该 方法相对于灵敏度分析和随机优化有一定的优点，但是随着不确定参数的增加， 情景个数呈指数规模增长，使建立的优化模型难以求解”，这正是其理论深入和 应用推广中最大的不足。 第一章绪论 1 2 2 基于b e n - t a i 的鲁棒优化 随着鲁棒优化思想的不断传播，在该方向上的奠基之作被认为是由以色列学 者a b e n - t a l 和a n e m i r o v s k i 2 i t 3 l 伫，以及美国加州伯克利大学的l e i g h a o u i f 5 】| 6 1 在上世纪9 0 年代后期完成。 a b e n - t a l 所提出的鲁棒优化框架是以凸优化理论为基础的，不确定参数集 要求为内点非空的有界凸闭集，一般由椭球体或者几个椭圆体的交集表达，采用 该表达方式的原因为：首先，从数学的观点看，椭球体不仅易于表达，而且还容 易数字化处理。其次，对于许多随机的不确定数据可以用椭球体或几个椭球体的 交集近似表达。最关键的一点为可以对鲁棒优化模型进行数学推导，得到其鲁棒 对等式，将初始的不确定优化问题转化成基于凸优化理论的确定性优化问题。与 m u l v e y 等人提出的基于情景集的鲁棒优化方法所不同的是，他们的方法能够实 现所谓的“硬约束”，即不确定参数在集合内的任何实现都能够满足约束函数。 a b e n - t a l 等人将其所作的研究归纳为鲁棒凸优化理论，并在此方向上取得 了很大迸展，其理论成果如下i z l ：( 1 ) 由椭球体或几个椭球体交集表达的不确定 线性规划问题的鲁棒对等式是一个确定的锥二次规划问题。( 2 ) 由椭球体集表达 的不确定凸二次约束二次规划问题的鲁捧对等式是一个半定规划问题，如果不确 定参数集由几个椭球体的交集表达时，那么得到的鲁棒对等式是一个n p - h a r d 问 题。( 3 ) 由椭球体集表达的不确定锥二次规划问题的鲁棒对等式在增加一些限定 的条件下是一个半定规划问题，如果不确定参数集由几个椭球体的交集表达时， 那么得到的鲁棒对等式是一个n p h a r d 问题。( 4 ) 由椭球体集表达的不确定半定规 划问题的鲁棒对等式是一个n p h a r d 问题，如果不确定集有一个“良好的结构”， 那么得到的鲁棒对等式是计算可处理的。同时，还给出了一般不确定半定规划问 题的计算可处理的近似鲁棒对等式。在得到初始不确定优化问题的鲁棒对等式以 后，采用多项式时间内可解的内点算法得到优化模型的最优解。 l e 1 g h a o u i 等人对鲁棒优化的研究是从鲁棒控制理论中的鲁棒性分析得 到启发，通过矩阵值函数的线性分式表示对鲁棒优化理论进行分析，研究了不确 定最小二乘和不确定半定规划问题。在不确定半定规划问题上考虑了不确定集合 中数据间非线性相关的情况，将其理论成果作为a b e n t a l 等人的一个补充。 。 随着鲁棒优化理论研究的深入，2 0 0 4 年，a b e n t a l 等人1 2 2 l 提出了可调整鲁 棒优化的概念，认为其可以处理不确定动态决策问题，在考虑多阶段不确定线性 规划问题时，认为有些变量始终是不确定的，即不可调整的；而有些变量在问题 的求解过程中由原来的不确定转变为可选择的，即可调整变量，可调整鲁棒优化 将鲁棒优化从静态优化向动态优化进行了延伸。2 0 0 5 年，a b e n - t a l 等人1 2 3 1 在其 第一章绪论 对鲁棒优化研究的基础上，提出了不确定优化问题的综合鲁棒对等式的概念，即 在优化模型中的参数取值超越了不确定参数集的范围后，如何控制约束违背的程 度以满足优化性能，这是a b e n - t a l 等人对鲁棒优化研究的最新进展。 a b e n - t a l 等人不仅在鲁棒优化的理论研究中取得了很大进展，而且还将其 很好的应用到实际问题中。其中1 9 9 7 年，a b e n - t a l 和a n e m i r o v s k i 1j l 对于t r u s s 拓扑设计问题，建立了其鲁棒优化模型，这是其在该方向的研究中发表的第一篇 文献。1 9 9 9 年，a b e n - t a l 等人口】在研究不确定线性规划问题中，以一个投资组 合为例说明了鲁棒优化模型如何建立，并与基于情景集的鲁棒优化方法进行对 比，结果显示了该方法的有效性。2 0 0 0 年，a b e n t a l 等口l i 将该方法应用在 n e t l i b 优化问题中，提出了可靠性指数的概念，并用大量的例子说明当不确定 等级变化时，标称解的可靠性变化情况。2 0 0 2 年，a b e n - t a l 等 4 1 将该方法用在 了天线设计、不确定动态系统的稳定性分析等问题上，显示了鲁棒优化方法在减 少小数据扰动给优化性能带来负面影响这个问题上的优势。2 0 0 3 年，a b e n - t a l 等【2 4 1 还将该方法用在了供应链管理问题中。2 0 0 4 年，为了解决不确定多周欺( 多 阶段) 优化问题，a b e n t a l 等【2 2 】提出了可调整鲁棒优化的思想，对多阶段库存 管理问题进行了研究。 除了a b e n - t a l # b ，鲁棒优化理论还引起了其他学者的研究兴趣，包括哥伦 比亚大学的gi y a n g a r 和d g o l d f a r b l 2 ”、卡内基一梅隆大学的r e h ah t u t u n c u l 2 6 j 、 俄克拉荷马州立大学的t h e o d o r eb t r a f a l i s l 2 7 1 、加州伯克利大学的a t a m t 膛r k 【2 ”、 莱斯大学的nz h a n g t 2 9 1 、乔治亚工业大学的j a n ec a m m o n s 【l 、意大利 p o l i t e e n i e od it o r i n o 大学i 拘g i u s e p p ec a l a f i o r e i 川等。qi y e n g a r l 3 2 】认为其研究的鲁 棒凸二次约束规划属于a b e n - t a l 研究的鲁棒凸规划的一个子集，他们的重点放 在了不确定结构上，介绍了在三类不确定集的条件下，即离散多面体不确定集、 仿射不确定集和因数化不确定集，使相应的不确定凸二次约束规划问题转化为一 个二阶锥规划问题。同时gl y e n g a r 在以上研究的基础上对投资组合i 圳以及投资 管理【3 4 恫题进行了分析。r e h ah t u t u n e u l 2 6 1 针对具有不确定参数的非线性多周期 优化问题建立了可调整鲁棒优化模型，在a b e n - t a l 对可调整鲁棒优化研究的基 础上，将不确定集定义为有限点集合的凸包，研究了在何条件下将可调整鲁棒优 化问题简化为单确定的优化问题。以两阶段优化问题为例，指出当第二阶段的 可行集具有类凸特性时，问题的简化是可行的，并在此基础上拓展到三周期和多 周期优化问题中。t h e o d o r eb t r a f a l i s p s i 针对支持向量机分类模型中输入数据存 在边界扰动的问题，采用鲁棒优化的方法建立线性规划支持向量机模型，分析了 其解对模型鲁棒性和稳定性的影响。除此以外，还有不少学者将鲁棒优化理论用 在了实际问题中，普林斯顿大学的c h r i s t o d o u l o sa f l o u d a s 等36 j 对生产调度中过 第一章绪论 程时间、市场需求以及原材料和产品价格存在不确定性这个问题，建立其鲁棒优 化模型。加州伯克利大学的s a m e rm m a d a n a t 对道路网络中交通需求的波动不可 预测问题1 3 7 1 以及资产管理问题3 8 1 进行了研究。南加州大学的f e r n a n d o o r d 篑e z 【3 9 1 水1 岍究了运输网络，公路网络以及电信网络中的容量扩展问题。康奈 尔大学的m i l l i ec h u 4 2 i 针对肿瘤患者采用强可调辐射治疗计划，建立其鲁棒优化 模型获得治疗方案。奥地利格拉茨大学的g e r a l ds t e i n e r l 4 3 l 等人研究了电磁设计问 题。 a ，b e n t a l 等人主要对基于椭球体集的鲁棒凸优化问题进行了研究，从单阶 段不确定优化问题向多阶段不确定优化问题进行延伸，取得的理论成果部分已经 应用到实际问题中，但是其仅局限在对连续不确定优化问题的研究上，经过转化 得到的鲁棒对等式相对于初始不确定优化问题，其求解的复杂度大大提高，此外， 其不确定参数集过渡依赖椭球体集或几个椭球体的交集上，只有这样才能够保证 将初始不确定优化问题转化为多项式时间内可解的鲁棒对等式，因此将其研究的 方法拓展到更为一般的优化问题中，以及应用到更多的实际问题中还需要大量的 工作。 1 2 3 基于b e r t s i i l l a s 的鲁棒优化 2 0 0 3 年，麻省理工大学的d ，b e r t s i r n a s 等在b e n t a l 等人研究的基础上，提出 了新的鲁棒优化框架，根据不确定参数集的不同选择，得到不同的鲁棒对等式， 将研究的重点放在了鲁棒对等式继承初始不确定优化问题的计算复杂度上，并形 成了自己的研究体系l “h 4 ”。其对鲁棒优化的研究分为两类：第一类是研究参数 不确定性的结构化数学规划问题，将基于不同参数不确定集的优化问题转化为一 个可求解的确定性优化问题，如鲁棒线性规划、鲁棒二阶锥优化、鲁棒半定优化 等属于这类问题。第二类是采用鲁棒建模的方法研究基于参数不确定集的随机和 动态规划问题，与随机和动态规划不同是，该方法不要求知道不确定参数的概率 分布。d b e r t s i m a s 的理论研究成果如下：( 1 ) 不确定线性优化问题的鲁棒对等式 仍为一个线性优化问题，而且该方法在理论上和实际上都是计算可处理的。尤其， 对于一个整数规划问题，当目标函数中的代价系数和约束中的系数均受到不确定 性影响时，提出了一个鲁棒整数规划方法，使得问题求解的复杂度在一个可控的 范围内，并可以根据约束违背的概率边界控制保守度。( 2 ) 多项式时间内可解的 不确定o 1 离散优化问题仍然保持其计算复杂度，一个n p - h a r d 的不确定硝近似 o 1 离散优化问题仍然保持口近似。( 3 ) 不确定锥优化问题的鲁棒对等式仍然保 持其初始结构，尤其是不确定二阶锥优化问题的鲁棒对等式仍然为二阶锥优化问 题，不确定半定规划问题具有类似特性。 第一章绪论 2 0 0 4 年，土耳其b i l k e n t 大学的m u s t a f ac p i n a r 4 8 l 在b e r t s i m a s 研究的基础上， 针对o 1 优化问题，给出了只有成本参数受到不确定性影响下，由鲁棒解得到的 优化值比鲁棒目标函数值小的概率边界。2 0 0 5 年，新加坡国立大学的m s i m 4 9 介 绍了能够表达随机变量非对称分布的一个新的不确定参数集，将与随机交量相关 的前向和反向偏差测度应用到不确定集的设计中，此外，还提出了求解一类具有 机会约束的随机优化问题的鲁棒优化方法，并应用在活动完成时间不确定的项目 管理问题上。 为了检验鲁棒优化理论在实际问题中的应用效果，2 0 0 3 年，d b e r t s i m a s 将 其应用于网络流量和库存管理1 5 0 问题中。2 0 0 4 年，d b c n s i m a s 刚将其应用 于离散时间内具有随机需求的供应链管理中，采用该方法对需求是否为确定的分 布没有要求，实验结果表明，在参数范围较大的情况下，采用该方法比采用动态 规划的方法效果要好很多。加州伯克利大学的h e n r yl i n 等1 5 习对公共水系统的污 染物传感器放置问题进行了研究。麻省理工大学的g e o r g i ap e r a k i s p 引在动态价格 和库存控制问题上，采用基于需求不确定性的鲁棒优化方法进行分析。乔治亚科 技学院的a l a nl e r e r a 等1 5 4 】对物流中转服务中的空闲再配置问题进行了研究。威 斯康星大学的j i a n g a n gl u 等人【55 】在研究智能交通系统问题时，建立了路线导航的 鲁棒优化模型，并最终运用在实际的交通网络中。 b e n s i m a s 的鲁棒优化研究框架涵盖了不确定连续优化和离散优化，其所建 优化模型的鲁棒对等式转化为确定性优化问题的思路比较独特，其最主要的特点 是这种转化不增加问题求解的复杂度，使得该理论更容易应用到实际问题中，具 有良好的发展前景。 1 2 4 鲁棒优化存在的问题 鲁棒优化作为研究不确定优化问题的新方法受到了越来越多的学者的关注， 采用事先分析的策略，在优化模型建立的过程中就考虑了参数的不确定性，其优 化解的鲁棒性突破了过去优化模型不确定参数过多依赖先验知识以及服从概率 分布的假定。尽管鲁棒优化还未形成统一的理论体系，但正是这种百花齐放的研 究思路给该领域的研究注入了活力，同时也表明该领域的研究还有许多亟待解决 的问题： 第一，在不确定集的确定上，如何与参数不确定性产生的来源和敏感级别结 合起来，选择集合的形状和大小。 第二，完善并丰富初始不确定优化问题转化为鲁棒对等式的理论体系，使鲁 棒对等式为计算可处理的。 第三，对优化模型参数在其不确定集以外取值的情况加以分析，找到控制优 第一章绪论 化性能恶化的途径和方法。 第四，推广鲁棒优化的应用范围，使该理论不仅可以在经济管理问题中得以 应用，而且还可以拓展到实际的优化调度问题中。电梯群控调度是建筑物内垂直 交通研究中一个很重要的实际问题，其存在的交通流不确定性是该问题的一个关 键点，结合群控调度目标，可以从不确定优化的角度对该问题进行分析，从而建 立其鲁棒优化模型。 1 3 论文的主要研究内容 1 对鲁棒优化理论的基本概念、原理和思想进行南述，给出其理论研究的路线 图。然后，探讨了不确定优化问题鲁棒优化模型的建立，对a b e n t a l 和 b e r t s i m a s 的鲁棒优化框架分别加以分析，其中后者将作为本文的理论基础而 得到重点阐述。 2 将电梯群控系统作为本文的研究对象，对现有电梯群控调度方法进行分析和 总结。对电梯群控调度问题中交通流存在的不确定性加以分析，在此基础上， 建立基于b e r t s i m a s 理论的电梯群控调度鲁棒优化模型，并给出其鲁棒对等 式，从而将初始鲁棒o 1 离散优化问题转化为一个计算可处理的混合整数规 划问题。 3 对于经过转化得到的电梯群控调度鲁棒优化模型的鲁棒对