（控制科学与工程专业论文）区间参数不确定系统优化方法及其在汽油调和中的应用研究.pdf

浙江大学博士学位论丈 摘要 尽管确定性优化理论与算法成功地应用在人们生产实践的各个领域，但由于 检测技术的局限性，确定性优化模型中的许多参数取值或多或少带有误差，基于 这些误差数据的优化决策，必然带来决策效果的下降。研究不确定条件下的优化 决策问题，日益受到国内外的重视。根据不确定参量的数学描述不同，不确定性 优化理论主要有随机规划、模糊规划和区问规划三种。 本文针对区间参数不确定稳态和动态优化问题，提出了相应的确定化数学描 述形式，并应用主从式并行遗传算法求解确定化后的非线性规划问题，与此同时 将其应用到某炼油厂的汽油调和问题。本文的主要研究工作包括： 1 提出了区间非线性稳态优化问题的确定化描述形式。该形式能够恰当地 反映出决策者在追求最优值时所准备承担的风险程度，同时也能反映出决策者对 不确定参数给目标函数造成偏差程度的不同要求。 2 提出了区间非线性动态优化问题的确定化描述形式，给出了不确定条件 下决策满足路径约束可能性度量指标，分析了路径约束松弛程度的可行性问题， 提出了求解路径约束满足度初始值的算法。 3 将区间非线性规划转化为确定化形式的极大极小问题后，采用了主从式 并行遗传算法求解大规模非线性规划问题，并提出“应答式”策略解决从机间负 荷忙闲不均衡问题。 。 4 提出了汽油调和问题的区间规划命题，应用本文提出的区间不确定优化 算法，对某炼油厂的实际汽油调和问题进行了求解。与此同时，对比研究了在组 分油辛烷值发生波动时，确定性调和方案与区间不确定调和方案的优化性能，结 果表明：当组分油质量在一定范围内变动时，区间不确定调和策略具有较强的鲁 棒性，在一定程度上能保证产品质量合格和较高的调和利润。 5 为提高非线性规划问题的求解性能，提出了一种新的求解非线性规划问 题的混合遗传算法。该算法将具有良好全局搜索特性的遗传算法与局部寻优性能 的序列线性规划方法相结合，当迭代点没有发生交叉和变异时，将目标函数和约 束条件在迭代点处线性化，用线性规划算法对其进行寻优。 关键词：区问规划；非线性规划；动态优化；汽油调和；遗传算法 浙江大学博士学位论文 1 1 a b s t r a c t t h et r a d i t i o n a lo p t i m i z m i o nt h e o r yh a sb e e ns u c c e s s f u l l ya p p l i e di n t ot h ev a r i o u s f i e l d s ，b u ti n f a c tt h ec o e m c i e n t so ft h em o d e l sa r eu s u a l l yu n c e r t a i n t ya n d i m p r e c i s i o n t h eo p t i m a ld e c i s i o n sb a s e do nt h e s ei m p r e c i s ed a t aw i l lr e s u l ti np o o r s o l u t i o nq u a l i t y t h eo p t i m i z “o nt h e o r yu n d e ru n c e n a i m yh a sa t t m c t e dal o to f a t t e n t i o ni nr e c e n ty e a r s t h r e em a j o ra p p r o a c h e sh a v eb e e np r o p o s e df o rd e c i s i o n m a k i n gp r o b l e m su i l d e ru i l c e r t a i n t y ：s t o c h a s t i cp r o 铲糊i n 昏m z z yp r o g r a m m i n ga i l d i m e n r a lp r o g r a 衄i n g t od e a l 、v i t l lt h es t a t i ca 1 1 dd y n a m i cs y s t e m si n v 0 1 v i n gi n t e r v a ic o e f f i c i e m s ，t h e t h e s i sp r o p o s e st h ed e t e r m i n i s t i ci n t e r p r e t a t i o no fm eu n c e n a i no p t i m i z a t i o np r o b l e m s ， a 1 1 ds 0 1 v e st 1 1 et r a n s f o m l e dn o n l i n e 盯p r o 伊锄m i n g ，u s 血gt h em a s t e r s l a v ep a r a l l e l g e n e t i ca l g o r i t l l 】n ，a 1 1 da p p l i e s 血ep r o p o s e da l g o r i t l l 】 ni m ot l eg a s 0 1 i n eb l c n d i n g p m b l e m t h em a i nr e s e a r c hw o r k i sd e p i c t e da st h ef o l l o w s 1 t h i st h e s i sp r o p o s e sm ed e t e m l i n i s t i ci m e r p r e t a t i o no fi n t e r v a ln o n l i n e a r p r o g 均m m i n g t h i sf o r m u l a t i o ns h o w s t h ed e g r e eo f t h er i s kw 1 1 i c ht h ed e c i s i o nm a k e r s h o u l d 衄d e r t a k ew h e np 1 1 r s u m gm em a ) 【曲u mo b j e c t i v e 劬c t i o nv a l u e ，a n dt h ee h d r s i z eo ft h eo b j e c t i 、忙f l m c t i o nv a l u ed u et ot h eu n c e n a i np a r a m e t e r sa sm ed e c i s i o n ma ：k e r se x p e c t 2 t h i st l l e s i sp r o p o s e st 1 1 ed e t e m i l l i s t i ci n t e r p r e t a t i o no fd ”a m i co p t i m i z a t i o n i n v o l v i n gt l l ei n t e r v a lp 删e t e r s ，p u t sf o n a r dm ep a t l lc o n s t r a i n ts a t i s f a c t o r yf k t o r s ， a n a l y s i s e st 1 1 ef e a s i b i l i 哆p m b l e mo ft h ep a mc o n s t r a i mr e l a ) ( a t i o n ，a 1 1 dg i v e st 1 1 e c o m p u t a t i o nm e t h o do f t h ep a t hc o n s 仃a i n ts a t i s f a c t o r yf a c t o r s 3 a 舭rt r a n s f o m l i n gt h ei i l t c r v a ln o n l i n c a rp r 0 伊锄m i n gi n t ot h em i n i m a ) 【 o p t i m i z a t i o np r o b l e m ，t 1 1 et 1 1 e s i sp r o p o s e st h em a s t e r _ s l a v ep a r a l l e lg e n e t i ca l g o r i t h m t os o l v em el a r g es c a l en o n j i n e a rp r o 酽猢i n g c o m p a r e d 、v i mt 1 1 e 仃a d i t i o 删 m a s t e r s l a v ep 删1 e 1g e n e t i ca l g o r i t l l m ，t h ep r e s e n t e da l g o r i t l l l l lc a ns 0 1 v et l l ep m b l e m o f u n b a l a n c e dd i s t r i b u t i o no f m ec o m p u t a t i o n a ll o a da m o n gt h es l a v ec o m p u t e r s 4 t h em e s i sp m p o s e sm ei n t e r v a lp m g m m m i n gf o n n u l a t i o no ft h eg a s o l m e b l e n d i n gp r o b l e m ，g i v e st h es 0 1 u t i o no fm eg a s 0 1 i n eb l e n d i n gp m b l e mo fa no i l r e n n e r yp l a m ，a 1 1 dd i s c u s s e st 1 1 ep e r f o m l a l l c eo ft h ed e f i n i t eg a s o l i n eb l e n d i n g a l g o r i t l l ma n dt l l ei n t e r v a lg a s o l i n eb l e n d i n ga l g o r i t h mu n d e rt 1 1 en u c t u a t i o no ft l l e i v浙江大学博士学位论文 o c t a n en u m b e r so ft h ef b e d s t o c ks t r e a n l si 。h er e s u i t ss h o wt h a tt h ei n t e r v a lg a s o l i n e b l e n d i n ga l g o r i t h mi sc a p a b l eo fd e c r e a s i n gt h es e n s i t i v i t yo ft h eo p t i m a ls 0 1 u t i o n u n d e ru n c e r t a i n t y ，a n de n s u r e st h ed e s j r e dp r o d u c tq u a l i t ya n dp r o f h 5 t oi m p r o v et h ep e r f o m l a n c eo fs 0 1 v j n gt h en o n l i n e a rp r o g m m m i n gp m b l e m ， t h et h e s i sp r o p o s e san e wh y b r i dg e n e t i ca l g o r i t h mw l i c hc o m b i n e sag e n e t i c a l g o r i t l l i n 州t hs e q u e m i a l l i n e a r p r o g r 锄m i n g d u r i n gt 1 1 ei t e r a t i v ec o m p u t a t i o n p r o c e s s ，i ft h ei t e r a t i v ep o i m si nt h eg e n e “ca l g o r i t h md on o to b t a i nc r o s s o v e ro r m u t 砒i o no p e r a t i o n ，t 1 1 eo b j e c t i o nf i l n c t i o na n dc o n s t r a i n t sa tt l l e s ep o i n t sw i l lb e l i n e a r i z c d ，a n ds o l v e db ys e q u e n t i a ll i n e a rp r o g r a l l l i 】1 i n g y w o r 凼：i m e r v a lp m g r 猢i n g ；n o n l i n e a rp r o 伊黼i n g ；d y n a n l i co p t i m i z a t i o n ； g a s o l i n cb l e n d i l l g ；g e n e t i ca l g o r i m m 浙江大学博士学位论丈 v 致谢 首先感谢我的导师吴铁军教授，他渊博的学识，敏捷的思维，富于远见的学 术眼光，严谨的治学态度，踏实的科研和 ：作作风，尤其是勇于开拓创新的精神， 给我树立了精神上的榜样，也将永远激励我为实现理想而自强不息。感澍他在论 文选题、研究方法与思路上的悉心指导与帮助，感谢他在人生未来方向上给予的 谆谆教导与殷殷鼓励。吴老师的学识与人品将是我一生追求的目标，我将铭记他 的教诲与支持。 感谢我的副导师戴连奎教授的悉心指导。戴老师平易近人的学者风范、严谨 细致的工作态度、诲人不倦的高尚品德和忘我拼搏的工作精神，无论在学术研究、 实际工作，还是在为人处事中，都给我以深深的教益和启迪。戴老师从论文结构 和内容方面，不时启发我，提出很多新的观点，每次修改我的论文都是字斟句酌， 推敲锤炼，给我提供有价值的修改意见。 感谢智能所的杜树新老师、刘山老师、李艳君老师，他们在日常学习和工作 中给了我很多的启迪和帮助。 感谢周黔、付克昌、任世锦，李成安、嵇小辅、武晓莉、常爱英、孙丽丽、 崔承刚、杜方等博士以及贾国隽、江文德等硕士，他们在研究工作中给予我真诚 无私的帮助。 感谢中国石化上海高桥分公司炼油事业部林荣兴副总工程师、李振光副总工 程师、总调度员钱玮、质量管理科李婴、分析中心和调度科其他人员在本论文汽 油调和优化研究中所提供的支持与帮助。 感谢父母的养育和谆谆教诲，他们这些年来在背后默默的无私支持，使我始 终保持着前进的动力。感谢岳父母对我生活上的无私照顾、关心和支持。感谢我 的妻子刘斌女士、宝贝儿子蒋涵，为了使我能够顺利完成学业，他们付出和牺牲 了很多，他们的理解、支持和爱，给予我克服前进过程中任何困难的勇气和力量。 最后，谨以此文献给我深爱的妻子。 蒋峥 2 0 0 5 年5 月 于求是园 浙江大学博士学位论文 第一章绪论 摘要：本章简要叙述了不确定优化问题在人们生产实践中的来源与现 象，分析了国内外对于不确定优化问题的主要研究方法，阐述了解决不 确定性优化问题目前存在的困难，最后介绍了用智能优化方法解决不确 定性优化问题所具有的优势特点。 1 1 不确定优化问题的现象与研究意义 优化是在多种( 有限种或无限种) 决策中挑选最好决策的问题，它广泛应用 于工业、农业、国防、工程、交通等许多领域。在同样条件下，经过优化技术的 处理，对系统效率的提高、能耗的降低、资源的合理利用及经济效益的提高等均 有显著的效果。 大量的工程实践表明，系统优化具有投资少、见效快等特点，理想的工业应 用可在原有基础上增加2 5 的经济效益( 竺建敏，1 9 9 5 ) ：对年处理量l o o 万 吨的炼油厂催化裂化装置( f c c u ) 进行优化后，可增加经济效益6 0 0 1 5 0 0 万元 年，以中国石化股份有限公司为例，其拥有大型工业f c c u6 0 多套，仅通过优 化这一装置就可望增获效益3 6 亿元以上。同样，在线优化系统可适用于炼油厂 常减压、加氢裂化、催化重整等生产装置。另外，它完全适用于化工、制药、生 物化工等行业中的各种连续生产过程。可以预计，一个实用的在线优化系统所能 产生的经济效益将是非常巨大的。 对于实际物理系统的数学建模往往是非常复杂的，原因是有关系统的参数信 息常常是不完全，或是变化的，有噪声，甚至错误的。例如，在经济系统中，数 据往往存在着噪声，这些不确定性常来源于原材料的价格、产品的需求、燃料的 成本、电力的消耗、及银行利率波动的未知性。m o 唱e n s t e m 的著作( 1 9 6 3 ) 专 门研究了经济领域由噪声数据进行建模所产生的若干问题。在社会科学方面，用 于决策的数据也往往是不完全的，例如，定期的人口普查数据，并不能完全代表 实际的真实人口数量。另外，在工程系统中，不确定性常常来源于测量数据的不 精确性和随机外部干扰。例如，通过遥感进行图像重构时，得到的测量数据常存 在着误差，这将影响到建模的准确性。 第一章绪论 实际系统模型中存在的不确定性，可以用不确定模型参数或者未知的干扰来 描述。产生模型参数不确定性的原因是由于对对象特性缺乏了解或者系统参数发 乍变化，其表现形式可随应用背景的不同而有所差异。它可能表现为不完全的信 息，系统固有的波动性，或不可预知的变化。决策者可以确定参数变化的区问范 围，却不能预先指定参数出现的确切值，只能获得模型的感性知识。对此， k o u v e l i s ( 1 9 9 7 ) 分析了模型中参数不确定性可能的各种来源；另外，外部的下扰 如设备性能质量的波动，反应器中供料发生变化或者失败通常也会影响系统的优 化性能。m e i s t e r ( 1 9 9 6 ) 讨论了在油田开发周期中包括油田的投标、勘测、石油的 生产和销售，两种主要不确定性( 石油资源储量，市场价格) 在优化决策中的影响。 一般来说，模型参数不确定性表现为时不变或者随时间变化缓慢的特性，而外部 干扰的不确定性表现为变化很快的特性。 以工业过程动态优化问题为例，分析其中的不确定性问题。目前过程工业系 统几乎都采用这样的优化模式：先建立对象的数学模型，再依据模型进行优化搜 索以获得最优解，再将最优解加以实施。然而，在复杂的实际工业系统中，受技 术与资金等因素的限制，许多系统输入如原料的组成等，是无法测量的；同时不 少物性参数，如换热器的传热系数等，会随时间发生不确定的变化。这些不确定 因素的实际存在与模型本身的近似误差，造成许多确定性优化系统无法长周期有 效运行。p i s t i k o p o u l o s ( 1 9 9 5 ) 将过程系统中的不确定性总结为以下几种类型：1 ) 模型固有的不确定性。如动力学常数，物质的物理特性，传输系数等。2 1 过程 固有的不确定性。如流体流量或温度的变化。3 ) 外部不确定性。如产品需求量、 价格，过程的环境工况。3 ) 离散不确定性。如可供使用的设备数目。 不确定性优化理论是传统优化理论的延伸，它使得所作决策更加贴近客观环 境。事实上，现实世界中的绝大多数优化问题或多或少含有不确定因素。只是由 于数学处理上的困难和不便，在很多场合下才不得不作出简化，将多重不确定性 转化为单重不确定性，将不确定性转化为确定性。从辩证法的观点来讲，不确定性 是绝对的，确定性是相对的。 不确定优化不仅在理论上涵盖了经典规划、随机规划、模糊规划、区间规划 等数学规划的研究内容，而且已被应用到诸多领域。例如，生产计划( b i t r a n ，h a a s & m a t s u o ，19 8 6 ；d e m p s t e re ta 1 ，19 81 ；e s c u d e r o ，k 蛐e s 锄，k i l l g ，& w e t s ，l9 9 3 ； l 肌s 仃a ，砒皿o o yk a l l ，& s t o u g i e ，1 9 8 3 ) 、调度决策( b i r g e & d e n l p s t e r ，19 9 6 ； d 锄p s t e r ，1 9 8 2 ；d e m p s c e re ta 1 ，1 9 8 3 ；t a m1 1 l o m a s ，& n a 姐i ，1 9 9 5 ) 、路由定位 ( l 印o r t ee ta 1 ，1 9 8 9 ，1 9 9 2 ；s p a c c 锄e l ae ta 1 ，1 9 8 4 ；l 印o n ee ta 1 ，1 9 9 4 ) 、水资源管 理( d u p a c o v a ，g a i v o r o n s k i ，k o s ，& s z a n t a i ，1 9 9 1 ) 等。这些课题的研究一方面反映 了不确定规划在实际应用中行之有效，另一方面也折射出不确定规划的研究背景， 为不确定规划的研究提供了动力。 浙江大学博士学位论文 不确定优化理论的研究与实践应用，给社会带来的效益是巨大的。以工业牛 产为例，企业可以借助不确定优化技术，提高产品的质量和产量，满足牛产安令 规范，减少刈环境的破坏，适应复杂多变的市场环境，最终给企业带来可观的经 济、社会和环境效益。 1 2 不确定优化问题研究方法 在传统的数学规划中，描述客观对象的模型中的系数通常由专家假定为确定 性的取值。但在一个不精确或不确定的环境中，专家的这种假定通常是不合理的。 为此，在数学规划理论中，常采用模糊、随机和区间三类分析方法来描述和解决 一个真实决策问题中的不精确或不确定参量。在模糊规划中，约束条件和目标函 数被看作模糊集合，并假定其模糊隶属度函数为已知。在随机规划中，不确定参 量被视为随机向量，并假定其概率分布函数为已知。由于在真实决策环境中，要 精确获得不确定参量的模糊隶属度函数或概率分布函数往往很困难，而获得这些 不确定量的可能的变化范围相对容易些。在区间规划中，不确定参量的取值范围 以一个实数区间来表示。 不确定优化问题来源于人们的社会实践，例如生产计划调度问题、运输问题、 资源分配和工程设计问题都存在着在不确定环境下的决策问题。而不确定优化问 题的研究，最早始于上世纪5 0 年代b e l l m a i la 1 1 dz a d e h ( 1 9 5 7 ，1 9 7 0 ) ，c h a r l l e s ( 1 9 5 9 ) 等人的研究工作。本章将对三种形式的不确定优化方法进行讨论。 1 2 1 随机规划 随机规划可以分为随机线性规划、随机整数线性规划、随机非线性规划、鲁 棒随机规划和概率规划等类别，分别叙述如下。 随机线性规划 设随机线性规划问题 删n c _ ( 1 1 ) s t ： 一( h = 6 ( ) ，x 0 其中，c = ( c ，q ) ，爿只，6 = ( 6 l ，6 卅) ，苫= ( ，) 。目标函数系数 向量c 为确定性参数a 彳，6 的元素，电，f _ 1 ，用，= 1 ，n 是随机参数的， 它们定义在某一概率空间口上。 二阶段随机线性规划问题( b i r g e ，1 9 9 7 ；k a l l ，】9 9 4 ；王金德，1 9 9 0 ) 可以描述 为 第一章绪论 m i n c + e 。q q ( x ，m ) 】 s t ：0 且 q ( x ，甜) = m i ng ( m ) j ， ， s t ： ( 国) y = 6 ( m ) 一爿( ) x y y ( 】2 a ) ( 1 2 b ) 其中y c r ，月，q r “7 。优化问题( 1 2 a ) 称为第一阶段问题，决策变量 x 的取值需要在观察到不确定参数力的实现之前作出。问题( 1 2 b ) 称为第二阶 段问题。( 珊) 称为补偿矩阵( r e c o u r s em a m x ) ，y 称为补偿变量( r e c o u r s ev 撕a b l e ) ， 矿( 脚) y 表示决策x 在观察到不确定参数力的实现之后，约束不满足的大小， 而q ( x ，妫表示由于约束不满足，而给目标函数造成的最小的损失。由于取值 的随机性，e 。【q ( x ，珊) 表示约束不满足时，给优化目标带来损失的平均效果。 假定不确定参数具有离散的分布，问题( 1 2 ) 可以等价成一个大规模的线性规 划问题。根据补偿函数q ( ) 凸性性质，b i 耀e 和l o u v e a u ) ( ( 1 9 8 8 ) 提出了基于分解 原理的求解算法。对于不确定参数具有连续概率分布形式的情况，根据补偿函数 q ( ) 的这些凸性性质，许多学者提出了基于采样分解和近似原理的算法 ( r u s z c z y n s l ( i ，1 9 8 6 ；b i 唱e & l o u v e a u x ，1 9 8 8 ；h 培l e & s e n ，1 9 9 1 ；i n f h g e r ，1 9 9 4 ； s h a p i r o & h o m e m - d e m e l l o ，1 9 9 8 ；) 以及基于梯度的迭代算法( e 肌o l i e v 1 9 8 3 ； s h a p i m & w a r d i ，1 9 9 6 ) 。 采用筛选过程算法( f i l t r a t i o np r o c e s s ) 来描述不确定参数，可以将二阶段随机 规划推广到多阶段随机规划问题。采用分割时间阶段的分解算法( b 堍e ，1 9 8 5 ) ， 和采用分割场景空间( s c e n 撕os p a c e ) 的分解算法( r o c k a f e l l a r & w e t s ，1 9 9 1 ) ，都可 以用来求解多阶段随机线性规划。 有关随机线性规划问题的进一步研究，b i t g e 和l o u v e a u x ( 1 9 9 7 ) 、l 甜缸g e r ( 1 9 9 4 ) 、k a l l 和w a l l a c e ( 1 9 9 4 ) 、p r 6 k o p a ( 1 9 9 5 ) 都进行了详尽的讨论。 随机整数线性规划 如果将问题( 1 2 ) 中的集合】，限定为整数集合，问题( 1 2 ) 就转化成为随机整数 规划。随机整数规划的早期研究工作大都采用启发式算法( h e 砸s t i c s ) 来求解二阶 段随机整数规划( 例如d e m p s t e re ta 1 ，1 9 8 l ；s t o u g i e ，1 9 8 5 ) 。更为精确的求解算法 是近年来才提出来的，其中包括：用于求解随机线性规划问题的基于分解原理算 法的推广算法( c a r o e & t i n d ，1 9 9 8 ；l 印o r t e & l o u v e a u x ，1 9 9 3 ) ，l a g r a n g i a n 松弛 算法( c a r o e & s c h u l t z ，1 9 9 9 ；1 酞r i t i b i r g e ，& l o n 晷1 9 9 6 ) ，代数枚举法( s c h u l t z ， 浙江大学博士学位论文 s t o u 窖i e ，v a nd e rv l e t k ，1 9 9 8 ) ，凸化算法( h i 叠1 e & s e n ，2 0 0 0 ；s h e r “f r a t i c e l l i ， 2 0 0 2 ) ，与分枝定界法结合的分解算法( a l 硼e d ，t a w a 肿a l a n i ，& s a h i n i d i s ，2 0 0 3 ) 。 当随机整数规划的第二阶段问题具有简单补偿( s i m p l er e c o u r s e ) 的特殊结构 时，k l e i nh a n e v e l d 等人( 1 9 9 5 ，1 9 9 6 ) 提出了一种求解算法，该算法足基十埘第二 阶段值函数构建凸包( c o n v e xh u l l ) 来实现的。对丁更为一般的补偿结构，当第。 阶段问题的变量的取值为二进制时，l a p o n e 和l o u v e a u x ( 1 9 9 3 ) 提出了种基于 分解原理的随机整数规划的求解算法，采用分枝定界法在第一阶段问题的决策变 量空间中搜索全局最优解，同时应用优化切割( o p t i m a l i t yc u t s ) 来近似第二阶段问 题的值函数。由于第一阶段问题优化解的数目是有限的，所以这种算法可以在有 限次数的迭代后收敛终止。该算法已经有效地用于求解二阶段随机定位路由问 题( l a p o n e ，l o u v e a u x ，& m e r c l l r e ，19 8 9 ，l9 9 2 ，19 9 4 ；l 印o n e ，l o u v e a u x ，& v a l l h 锄m e ，1 9 9 4 ) 。但遗憾的是，如果第一阶段问题中有任一变量是连续的，这种算 法便不再适合。c a r o e 和t i n d ( 1 9 9 8 ) 提出了一种算法，用于处理混合整数 ( m i x e d i m e g e r ) 的第一和第二阶段变量的情况。这种算法用非线性整数规划对偶 函数，来近似第二阶段值函数。 c a m ee ta 1 ( 1 9 9 7 ，1 9 9 8 ，1 9 9 9 ) 使用r o c k a f c l l a r 和w e t s ( 1 9 9 1 ) 的场景分解方 法，提出了一种求解随机整数规划的分枝定界方法。 上述算法都是假定不确定参数具有离散的概率分布规律。而对于不确定参数 具有连续的概率分布情形，除少数情况下可以提供闭环形式的优化解，通常需要 应用采样技术( s a l l i n i d i s ，2 0 0 4 ) 。对于连续分布情形，n o r k i n 、e h i l o l i e v 、和 r u s z c z ”s k i ( 1 9 9 8 ) 提出了一种分枝定界算法，该算法应用了随机上界和下界方 法，并且证明算法是收敛的。 近年来，凸化( c o n v e x i f i c a t i o n ) 在随机整数规划应用方面受到了学者越来越多 的关注。h i g l e 和s e n ( 2 0 0 0 ) ，s h e r a l i 和f r a t i c e l l i ( 2 0 0 2 ) 提出了一种求解随机整 数规划的新思路，其基本思想来源于b a l a s ( 1 9 9 3 ) 所提出的提升一投影 ( 1 i m a i l d p r o j e c t ) 方法，和a d a m s ( 1 9 9 0 ) 所提出的重构一线性化 ( r e f o m u l a t i o n - l i n e a r i z a t i o n ) 技术。这些方法目前还处在理论研究阶段，还没有实 际应用的相关报导。a h m e de ta 1 ( 2 0 0 3 ) 分析研究了随机整数规划在某些结构上 的性质，针对某一类随机整数规划问题，提出了一种分枝定界求解方法。 随机非线性规划 随机非线性规划在生产实际中有许多应用实例，特别在工程设计、生产计划 和调度方面。二阶段非线性随机规划的一般形式为 m i n ( x ) + 毛。n 【9 ( x ，甜) 】( 1 3 a ) s t ： g ( x ) o 6第一章绪论 s t ： g ( ，x ，y ) 0 ，y ， ( 1 3 b ) 其中，j ，r7 ，甜是概率空间力的一个随机变量，力，函数g ，f 和g 分别具有相应的维数。 大多数用来求解随机线性规划的算法都可以推广到非线性情况。但是，非线 性特性可能会存在非凸性和局部最优。b a s t i n ( 2 0 0 1 ) 较为详尽地讨论了非线性随 机规划问题。 鲁棒随机规划 基于补偿的模型( 1 2 ) 是假定决策者不考虑决策风险因素。为了在随机规划 中，体现决策风险的思想，m u l v e y 、v a n d e r b e i 、和z e n i o s ( 1 9 9 5 ) 将问题( 1 2 ) 中目 标函数作了下述变化： i 血n c + 吃。n q ( 工，) 】+ 五( ，y ) ( 1 4 ) 其中厂是一个表征第二阶段损失变化的测度， 是一个非负的标量，表示决策者 对决策风险容忍的程度。五取值越大，最优解下的损失方差越小；丑取值越小， 最优解下的损失期望越小。 鲁捧随机规划及其各种变化形式，在生产实际中有许多成功的应用，如： 电力系统扩容方案决策( m a l c o l m & z e n i o s ，1 9 9 4 ) ； 电力分配( b e m l d i ，m u s m 黜l o ，& 嘣k i ，1 9 9 8 ) ； 化学过程设计( a h m e d & s a l l 衲i d i s ，1 9 9 8 ) ； 电讯网络设计( b a i ，c a r p e n t e r & m u l v e y ，1 9 9 7 ；l a g u n a ，1 9 9 8 ) ； 金融决策( b a ie ta 1 ，1 9 9 7 ；k o u w e n b e r g & z c n i o s ，2 0 0 l ；m u l v e ye ta 1 ，1 9 9 5 ) 。 各种事例( 瞄n g ，t a t i ，& a l l n l e d ，1 9 9 7 ；s e n h i 对e ，1 9 9 9 ) 表明对鲁棒模型 进行直接简单的确定性转化，将使得第二阶段的优化解是补偿问题( 1 2 ) 的次优 解。这种性质可能导致对补偿成本的低估。t a t i 和舢蛐e d ( 2 0 0 3 ) 给变化测度 提供了充分条件，用以解决这种问题。 概率规划 上述随机规划求解方法，要求决策者给补偿行为以一种惩罚，其实质是允许 给第二阶段问题的不可行解以某种惩罚。这种算法是最小化期望补偿成本。而在 概率规划中，考虑问题的焦点在于系统的可靠性，即在不确定环境下系统满足可 行性的能力。 考虑约束条件中含有随机向量f ( 鲫) 的非线性规划问题 浙江大学博士学位论文 f 1 5 、 s t ： g ，( x ，善( ，) ) o ，f = 1 ， 若决策者必须在观察到随机向量善( m ) 的实现之前作出决策工，则很有可能对某些 。，约束条件( 1 5 ) 不能成立。在某些情况下，可以允许约束条件受到某利t 程度 的破坏，即只要求使约束条件得到满足的概率不小于某一事先选定的常数即可。 这一要求又可分为两种情况，一种是，对( 1 5 ) 式中的每一约束条件有一指定常数 口，o 口，1 ，使得 p g ，( z ，吉( ) ) 0 a ， f = l ，朋 另一种是，对某一指定数口，o 口1 ，决策x 应使( 1 5 ) 中所有m 个约束条件同 时成立的概率不小于口，即 p 蜃( x ，孝( ) ) 0 ，f = 1 ，m ) 口 因此概率规划可分为单个概率规划问题和联合概率规划问题 m i n ，0 )( 1 6 ) s t ： p 岛( x ，善( 国) ) o ) 啦，f = l ，小 和联合概率规划问题 m i n 厂( x )( 1 7 ) s t ： p g ，( x ，考( 妫) o ，f = 1 ，m 口 ( 1 6 ) 或( 1 7 ) 的可行解x 并不能使约束条件( 1 5 ) 总能满足，而只是使其以一定的概 率成立。通常情况下，( 1 6 ) 或( 1 7 ) 是一个确定性的非线性规划问题。 p r e k o p “1 9 8 0 ) 和b o r e l l ( 1 9 7 5 ) 研究发现了概率规划问题的可行解集合的凸 性与概率测度的拟凹性之间存在着必然联系。求解概率规划问题的主要困难来自 计算约束条件的函数值及其梯度向量值，这些值的计算实际上是求高维随机向量 的分布函数值。显然，m o n t e c a r l o 方法是合适的方法，但是，由于一般的 m o n t e c a r l o 方法的收敛速度较慢，必须加进许多特别的技巧和减少估计量方差 的措施，才能使这种方法行之有效。对于较复杂一些的问题，可以采用逼进方法。 随机规划问题及其求解算法在社会科学、工程技术、财政金融等领域，有许 多成功应用实例。例如： 生产计戈0 ( b i t m n ，h a a s ，& m a t s u o ，1 9 8 6 ；d e m p s t e re ta 1 ，1 9 8 1 ；e s c u d e r o ， k a m e s a i l l ，k i n g ，& w e t s ，19 9 3 ；l e n s 把a ，r i n n o o yk 柚，& s t o u g i e ，19 8 3 ) ； 调度决策( b i 唱e & d e m p s t e r ，1 9 9 6 ；d e m p s t e r ，1 9 8 2 ；d e m p s t c re ta 1 ，1 9 8 3 ； 第一章绪论 i a y u r ，lh o m a s ，& n a t r a j ，l9 9 5 ) ； 路由定f 讧( l a p o n ee ta l ，】9 8 9 ，1 9 9 2 ；s p a c c a m e l ae ta 1 ，1 9 8 4 ；l 印o n ee ta 1 ， 1 9 9 4 、： 电力扩容( a h m e d ，k i n g ，& p a r u a ，2 0 0 3 ；b e r m a n ，g a i l z ，& w a g n er ，1 9 9 4 ； b i e n s t o c k & s h a p i r o ，1 9 8 8 ；d a v i s ，d e m p s t e r ，s e t h i ，& v 专r m e s ，1 9 8 7 ；e p p e n ，m a r t i n ， & s c h r a g e ，19 8 9 ；m a l c o l m & z e n i o s ，19 9 4 ；s h e m l i ，s o y s t e r ，m u r p h y ，& s e n ，l9 8 4 ) ； 能源投资和电力生产( c a r o e ，r u s z c z y n s k i ，& s c h u l t z ，1 9 9 7 ；l o u v e a u x ，1 9 8 0 ； m o n o n ，1 9 9 6 ；p e r e i r a & p i n t o ，1 9 9 1 ；1 心i t ie ta 1 ，1 9 9 6 ) ； 环境管理与决策( b i 曙e & r o s a ，l9 9 6 ；k i n g ，r o c k a f c l l 虬s o m i y o d y ，& w e t s ， 1 9 8 8 ；n o r k i ne ta 1 ，1 9 9 8 ；p i n t e r ，1 9 9 l ；s o m l y o d y & w e t s ，1 9 8 8 ；w a g n er ，s h 锄i r & m a r k s ，19 9 4 ；w a t a l l a b e & e l l i s ，l9 9 3 ) ； 水资源管理( d u p a c o v 屯g a i v o m n s k i ，k o s ，& s z a m a i ，1 9 9 1 ) ； 农业科学( h e l g a s o n & w a l l a c e ，1 9 9 1 ；s h u l ( 1 a & g u p t a ，1 9 8 9 ) ； 电讯技术( l a g l l l l a ，1 9 9 8 ；t o m a s g a r de ta 1 ，1 9 9 8 ) ； 化学过