（应用数学专业论文）相关机会规划的解法及其应用.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 随机规划是处理数据带有随机性的+ 类数学规划，它与确定性数学规 划最大的小同在于其系数中引进了随机变量，这使得随机规划比起确定性 数学规划更适合于实际问题。在管理科学、运筹学、经济学、最优控制等 领域，随机规划有着广泛的应用。 随机规划的求解方法大致分两种。第一种是转化法，即将随机规划转 化成各自的确定性等价类，然后利用已有的确定性规划的求解方法解之； 另一种是逼近方法，利用随机模拟技术，通过一定的遗传算法程序，得到 随机规划问题的近似最优解和目标函数的近似最优值。本文总结分析了已 有的可转化为确定性等价类的机会约束规划，将其推广到系数满足多元联 合l r 态分布的情况。 相关机会规划是使事件的机会函数在不确定环境下达到最优的方法。 本文针对机会函数中随机变量几种不同的约束条件和分布，得到了相关机 会规划的一些确定性等价类，讨论了相关的性质，并给出了基于随机模拟 技术的遗传算法。又将相关机会规划引入运输问题中，从而避免了一般解 法所给出的最优解可能在实际中无法执行的问题。 基于相关机会规划的运输问题是一个多目标随机规划，本文根据机会 函数的性质，提出了一个新的评价函数，从而将之转化为单目标随机规划， 使之便于求解。后又进一步推厂了基于相关机会规划的运输问题，将目标 规划引入，建立起基于相关机会目标规划的运输问题的数学模型。 关键词：随机规划：机会约束规划：相关机会规划；目标规划；运输问题 遗传算法 亘南交通大学硕士研究生学位论文第| 1 页 a b s t r a c t s t o c h a s t i cp r o g r a m m i n gi sac l a s so f m a t h e m a t i c a lp r o g r a m m i n g ，w h i c h d e a l sw i t hd a t ac o n t a i n i n gs t o c h a s t i ci n f o r m a t i o n i ti sd i f f e r e n tf r o mc o m n l o n m a t h e m a t i c a l p r o g r a m m i n g ，b e c a u s eo fi t s r a n d o mc o e f f i c i e n t s i tm a k e s s t o c h a s t i c p r o g r a m m i n gf i t t e r f o rt h er e a l i s t i c p r o b l e ma n d h a saw i d e a p p l i c a t i o ni nm a n yf i e l d s ，s u c ha s m a n a g e m e n t ，o p e r a t i o n ，e c o n o m ya n d o p t i m i z a t i o nc o n t r 0 1 t h e r ea r et w om a i n w a y s t os o l v es t o c h a s t i cp r o g r a m m i n g t h ef i r s to n e i st r a n s f o r m a t i o n ，i e t r a n s f o r m i n gs t o c h a s t i cp r o g r a m m i n gi n t oi t se q u i v a l e n t d e t e r m i n i s t i c p r o g r a m m i n ga n dt h e ns o l v i n gi tb yu s i n gt h et h e o r yo ft h e d e t e r m i n i s t i cp r o g r a m m i n g t h eo t h e ro n ei sa p p r o a c h i n g m e t h o d ，i e g e t t i n g t h e a p p r o x i m a t eo p t i m a l v a l u ea n ds o l u t i o no fs t o c h a s t i c p r o g r a m m i n g t h r o u g hg e n e t i ca l g o r i t h mb a s e do ns t o c h a s t i cs i m u l a t i o n t h em e t h o d so f t r a n s f o r m a t i o na r es u m m a r i z e di nt h ep a p e r , a n di ti sg e n e r a l i z e dt h et y p eo f t h ec o e f f i c i e n t ss a t i s f y i n gp o l y n o m i a ln o r m a ld i s t r i b u t i o n d e p e n d e n tc h a n c ep r o g r a m m i n g ( d c p ) i st h em e t h o do fo p t i m i z i n gt h e c h a n c ef u n c t i o no ft h ee v e n tu n d e ru n c e r t a i ns u r r o u n d i n g i nt h i sp a p e rs o m e d e t e r m i n i s t i c e q u i v a l e n c e s a r ea t t a i n e d a c c o r d i n g t os o m ed i f f e r e n t c o n s t r a i n e dc o n d i t i o n sm a dd i s t r i b u t i o n s s o m ec o r r e s p o n d i n gp r o p e r t i e sa r e d i s c u s s e d ，a n dag e n e t i ca l g o r i t h mb a s e do ns t o c h a s t i cs i m u l a t i o ni s g i v e n t h e nd c pi sa p p l i e dt ot r a n s p o r t a t i o np r o b l e m ，i no r d e rt oa v o i dt h a tt h a tt h e s o l u t i o ng i v e nb yc o m m o nm e t h o d sc a l l tb eu s e di nr e a l i t y t r a n s p o r t a t i o np r o b l e mb a s e do nd c pi s a m u l t i o b j e c t i v e s t o c h a s t i c p r o g m l n m i n g an e we v a l u a t i n gf u n c t i o ni sg i v e na c c o r d i n gt oc h a r a c t e r i s t i c 西南交通大学硕士研究生学位论文第1 ll 页 o f c h a n c e f u n c t i o n ，t o t r a n s f o r mi tt oa s i n g l eo b j e c t i v e s t o c h a s t i c p r o g r a m m i n g a tl a s tt r a n s p o r t a t i o np r o b l e mb a s e do nd c pi sg e n e r a l i z e db y i n t r o d u c i n gg o a lp r o g r a m m i n g ，a n dt r a n s p o r t a t i o n p r o b l e m b a s e do n d e p e n d e n tc h a n c eg o a lp r o g r a m m i n gi sm o d e l e d k e y w o r d s ：s t o c h a s t i cp r o g r a m m i n g ；d e p e n d e n tc h a n c ep r o g r a m m i n g ；g o a l p r o g r a m m i n g ；t r a n s p o r t a t i o np r o b l e m ；g e n e t i ca l g o r i t h m 亘宣窒堕盔兰塑堡窒生堂焦迨塞篁! 基 1 1 背景概述 第一章绪论 数学规划( m a t h e m a t i c a lp r o g r a m m i n g ) 足运筹学( o p e r a t i o nr e s e a r c h ) 的一个重要分支，并已被广泛地应用到很多领域。它是2 0 世纪5 0 年代前 后由d o r f m a n 提出来的，主要包括线性规划( l i n e a r p r o g r a m m i n g ) 、非线 性规划( n o n l i n e a rp r o g r a m m i n g ) 、多目标规划( m u l t i o b j e c t i v e s p r o g r a m m i n g ) 、同标规划( g o a lp r o g r a m m i n g ) 、整数规划( i n t e g e r p r o g r a m m i n g ) 、动态规划( d y n a m i cp r o g r a m m i n g ) 、随机规划( s t o c h a s t i c p r o g r a m m i n g ) 和模糊规划( f u z z yp r o g r a m m i n g ) 等等。 线性规划是数学规划的个重要分支，是解决静态优化最有效的数学 工具之一。1 9 3 9 年苏联数学家k a h t o p o b n 发表的“生产组织与计划中的 数学方法”书，是线性规划的首批著作。1 9 4 7 年美国数学家d a n t z i g 提 出求解一般线性规划问题的单纯形法( s i m p l e xm e t h o d ) 。1 9 7 2 年 k h a c h i y a n 提出了线性规划的第一个多项式算法一一椭球算法。1 9 8 4 年， k a r m a r k a r 提出线性规划的另一个多项式算法，即k a r m a r k a r 算法。 2 0 世纪5 0 年代，k u h n 和t u c k e r 提出非线性规划的基本原理。对某 些非线性规划问题，已经建立了大量的经典方法，如k u h n t u c k e r 条件。 线性规划和非线性规划是求个目标函数的极大值或极小值。但在很多实 际问题中，通常要对一组目标函数求极大值或极小值，这就是多目标规划。 同标规划首先由c h a r n e s 和c o o p e r 提出，可以看成是多目标规划问题的 个特殊情况。在实际问题中，一个目标通常只有在牺牲另一些目标的情 况f 才能实现，而这些目标之间一般是不相容的。因此，在这些不相容的 目标之问，根据其重要性，可以建立一个优先级。并根据这个优先级为所 有目标排序，尽可能实现更多的目标。 在某些线性规划问题中，决策变量只有取整数值才有意义，即约束条 件中需补充决策变量取整数值的限制，从而得到整数规划。整数规划可以 分为线性整数规划，非线性整数规划，多目标整数规划与目标整数规划。 西南交通大学硕士研究生学位论文第2 页 如果决策变量仅取o 或1 ，则称整数规划为o 1 规划。 线性规划与非线性规划所研究的问题，通常足与时问无关的静念问 题。1 9 5 4 年，b e l l m a n 创立了动态规划的基本理论。 在普通的数学规划中，模型的系数一般都是确定的常量。但存现实世 界中，系数在相当多的情况下不是常量，而是呈现一定的随机性。n _ 【t - l 人 们在确定性数学规划的基础上发展了随机规划的理论，使之更符合客观实 际情况。 解决随机规划的关键在于如何处理模型中的随机变量，出于不i _ j 的管 理目标和要求，采用的方法也随之不同。第一种处理随机规划中随机变量 的方法是期望值模型( e x p e c t a t i o nv a l u em o d e l ) ，即在期望约束条件下，使 目标函数达到最优。第二种是由c h a r n e s 和c o o p e r i l l l 提出的机会约束规划 ( c h a n c ec o n s t r a i n e dp r o g r a m m i n g ，简称c c p ) 。主要针对约束条件中含 有随机变量，且必须在观测到随机变量实现之前作出决策的情况。机会约 束规划模型允许决策者作出的决策在一定程度上不满足约束条件，但该决 策应使约束条件成立的概率不小于某一置信水平。第三种是相关机会规划 ( d e p e n d e n c ec h a n c ep r o g r a m m i n g ) ，由l i u i l 驯提出，是种使事件的机 会函数在不确定环境下达到最优的优化理论。 由于引进了随机因素，随机规划比确定性数学规划更切合实际。但也 正阕为随机规划模型中含有随机变量，所以不能简单地套用确定性数学规 划的现成理论，故随机规划比确定性数学规划更难以处理。f 1 前，国内外 解决随机规划的手段大致有两种：第一种是对某些具有特殊结构的随机规 划，通过各种办法，将其转化为确定性等价类，即将随机规划转化为确定 性的数学规划，然后利用大量的已有的确定性数学规划的理论去解决；第 二种是逼近的方法。正如在确定性数学规划中利用线性规划去逼近非线性 规划一样，存随机规划中也利用某些较为简单的随机线性规划去逼近其它 的复杂的随机规划，或直接用确定性的数学规划去逼近随机规划。近儿年 来，某些智能逼近算法在解决随机规划问题上显示了它们的优越性。在这 些智能算法中，尤以遗传算法较为成功。遗传算法主要是通过随机模拟技 术去处理随机规划中的随机变量，不需要一般的逼近方法那样繁杂的计 算。 西南交通大学硕士研究生学位论文第3 页 1 2 国内外的研究状态 随机规划实际上是确定性数学舰划的延续和更高发展，它的理论适合 丁解决含有随机因素的数学规划。 当前，圈内外对于随机规划的研究，主要集中于三个方面。其一是继 续寻找随机规划的新的和更为有效的算法，但这方面的研究并没有取得太 大的进展。1 9 9 5 年n g r o w e 1 】研究了随机规划的数值解法；2 0 0 0 年c a s e y 2 】 发表了关丁随机规划的极限理论的论文；d d e n t c h e v a l 2 2 2 4 1 在探讨了离散 分布的凸机会约束规划的基础l ，给出机会约束整数规划的圆锥生成算 法；w a n g 3 1 研究了二阶段规划模型的逼近解法并将之应用于地下水的规划 使用；国内学者占福文【4 1 研究了机会约束规划最优解的存在性。其二是 由于逼近算法的要求，同数学中许多其它的理论一样，深入研究随机规划 问题的稳定性和敏感性，国内外不少学者都在这方面做出了努力。如j d u p a c o v a 1 5 1 研究了随机规划的稳定性与敏感性；g o n g 【4 】在分析了最短路 径机会约束规划模型解的结构后，得到了机会约束规划的稳定性与敏感性 的一些结论；2 0 0 1 年骆建文【22 j 也作了概率约束规划的稳定性分析。其三 是现有随机规划理论成果的应用。近年来，许多随机规划方面的文献，都 侧重于利用已经发展起来的随机规划的理论去解决现实生活中的规划问 题。这种应用性的研究开展得如火如荼，事实上，当前发表的随机规划方 面的论文大都是这种应用性的。如a d a mj b e r g e r l 5 j 在他的博士学位论文 中研究了大规模的资产、信用度、投资目标、存款和消费等金融活动的随 机规划模型：h e i k k i n e n 6 】研究了网络稀有资源的分配与定价问题的随机规 划模型；k a r a b u k 。”对高技术条件下半导体产品的供给与需求进行了研究， 得到了多阶段随机规划模型。 经典的随机规划主要关注线性模型。现在，许多研究试图在随机动态 觑划、随机整数规划、随机分式规划、随机目标规划以及随机多目标规划 9 - 1 0 等领域取得进展。 耍豳窒通大学硕士研究生学位论文第4 页 1 3 本文的主要工作 某些具有特殊结构的随机规划模型可以转化成等价的确定性规划，从 而利用解决确定性规划的方法来得出它们的最优解，本文总结分析，已有 的可转化为确定性等价类的机会约束规划，将其推广到系数满足多元联合 j 卜念分布的情况。 l i u ”j 提出了相关机会规划模型，但是对于这个模型目前没有相j 衄的 解法，本文针对机会函数中随机变量几种不同的约束条件和分布，得到了 相关机会舰划的一些确定性等价类，讨论相关机会随机规划的一些性质。 运输问题是运筹学中4 门以优化运输费用为主要研究对象的综合性 学科。其数学模型即为一个数学规划，它的约束条件中也常常出现随机变 量，即运输问题中的产量和销量可能是随机变量。而一般的处理方法即将 其转化为期望值模型或机会约束规划抑或是普通随机规划进行求解，而在 这些模型建立之后，其可行集本质上是确定的，这能导致所给出的最优解 在实际中无法执行。本文将相关机会规划引入运输问题中，由于相关机会 规划其并不假定可行集是确定的，而其可行集即为约束中的不确定环境， 从而避免了卜述问题。在求解过程中，文中根据机会函数的性质，提出了 个新的评价函数，使求得的解是一个有效解。 1 4 本文的结构 本论文分为如1 - 部分：论文第二章介绍随机规划的分类及其解法，重 点讨论机会约束规划的确定性等价类。第三章研究相关机会规划及其性 质，和相应的遗传算法。第叫章将相关机会规划引入运输问题，建立基于 相关机会规划的运输问题的数学模型，并对模型进行分析求解，给出基于 相关机会规划的运输问题的一个实例。 亘壶窒道盍堂亟塑窒生学位论文第5 页 第二章随机规划的解法 2 1 随机规划及其分类 黔 ：= ? 7 f 互= = = = 堕壹奎塑奎掌塑圭塑塞圭兰焦迨塞 篁! 垂 分为两种类型，即被动型和主动型。被动型即所谓“等待且看司t 丽而 s e e ) ”模型，即决策者等待观察r n ? n o e 随机变量的实现，然后适当利用这 些实现的信息作出决策，分布问题属于此种类型：主动型即所谓“这罩且 现在( h e r ea n d n o w ) ”模型，决策者必须在没有随机变量的实现信息的情 况下就作出决策，二阶段问题和机会约束规划问题均属于此种类型。 2 2 期望值模型 所谓期望值模型，就是在期望约束下，使目标函数的期望值达到最优 的数学规划。其一般形式表示如下： m a x e f ( x ，亭) e g f x 蔷 0 f - 1 m ( 2 1 ) ，( x ，亭) ，f = , 2 ，- 一，m 。7 e h ，( x ，掌) 】= o ，j - = 1 , 2 ，h 其中，x 是一个r 维决策向量，毒是个t 维随机向量，f ( x ，毒) 是目标函 数，e 表示关于随机向量告的期望算予，g ，( x ，孝) ，h ( x ，善) 表示随机约束函 数，f _ 1 , 2 ，m ；j = 1 , 2 ，n 。 期望值模型实际就是一个确定性规划模型，可以用已有的确定性规划 的理沦求解。若其为线性规划模型，可以用单纯形法、修f 单纯形法、对 偶单纯形法、椭球算法与k a r m a r k a r 算法等。若其为非线性规划，则根据 有无约束条件可以将非线性规划分为无约束非线性规划和约束非线性规 划。对于无约束非线性规划，根据目标函数的性质，可用直接法、梯度法 和h e s s i a n 矩阵法等方法求解。而对于约束非线性规划，可用可行方向法、 梯度投影法、线性近似法与罚函数法等。 2 3 机会约束规划 机会约束规划的一般形式为 西南交通大学硕士研究生学位论文第7 页 fm i n i ( 互) s i( 2 2 ) l p r g j ( x ，孝) o 口，j = 1 , 2 ，。，h 机会约束规划问题的特点是，要求满足约束条件的概率在定范围 内，即 p r g ，( z ，亭) 0 口，( 2 _ 3 ) 称其为机会约束条件。 2 3 1 传统解法 如果能够把机会约束转化成普通约束，那么机会约束规划就变为它们 各自的确定性等价类，从而使问题得到解决。 考虑下述形式的机会约束： p r g ( x ，亭) 0 ) t 2 ( 2 4 ) 显然机会约束( 2 3 ) 是这种形式的组合。 情况1 假设函数g ( x ，孝) 的形式为g ( x ，善) = h ( x ) 一善，则机会约束( 2 4 ) 可以 表示成如下形式： p r h ( x ) 善 醪( 2 5 ) 其中h ( x ) 是决策向量x 的线性或非线性函数，古是随机变量，概率分布函 数为o f - ) 。 显然，对每一个给定的置信水平a ( o a 1 ) ，必存在个数k 。( 可 能多个或无穷) ，使得 p r k 。毋= 口 ( 2 6 ) 若用个较小的数代替k 。，则左端概率将变大。因此p r h ( x ) 兰毋d 当且仅当h ( x ) k 。 注意到等式p r k 。s 善) = 1 - o ( k 。) 总是成立的，由( 2 6 ) 有 西南交通大学硕士研究生学位论文第8 页 k 。= 巾1 ( 1 一口) 其中中“是的逆函数。等式( 2 6 ) 的解可能不唯，等价地，函数西。1 是 多值的。对这种情况，需要取最大的那个，保证可行集尽可能大，即 k 。= s u p k l k = 中。( 1 一“) ) ， 因此可得( 2 7 ) 的等价类，其形式如下： h ( x ) k 。 情况2 假设函数g ( x ，善) = 掌一 ( x ) ，则机会约束( 2 4 ) 可以写成如下形式： p r ( x ) f d ( 2 7 ) 其中 ( x ) 是决策向量x 的( 线形或非线形) 函数，告是随机变量，概率分 伟函数为( ) 。 显然，对每一个给定的置信水平a ( o “1 ) ，存在一个数彪。，使得 p r k 。掌) = a ( 2 8 ) 若用一个较大的数代替k 。，左端的概率将变大。因此，p r h ( x ) 掌 a 当 且仅当h ( x ) k 。 注意到等式p r k 。g ) = 中( k ) 总是成立，因此， k 。= 巾。( 口) 其中m ，是函数m 的逆函数。等式( 2 8 ) 的解可能不唯一，等价地，函数巾1 是多值的。需要取最小的那一个，保证可行集尽可能大，即 k 。= i n f k l k = m 。( a ) 因此可得( 2 7 ) 的等价类，其形式如下： 西南交通大学硕士研究生学位论文第9 页 情况3 独立正态分布族情形 假没函数g ( x ，掌) 有形式 h ( x ) k 。 g ( x ，喜) = a l x i + 口2 x 2 + 。+ a m x 。一b 其中亭= ( ，a ：，日。6 ) ，a ，$ 1 1 b 为相互独立的正态随机变量， a ，n ( p ，仃? ) ，b n ( p m + 1 2 + ) 。则可将机会约束( 2 4 ) 按如卜，转化为等价 的确定性约束。 r 、 p r g ( x ，善) o ) = p r d x ，一b 0 l i = 1j 由于d ，与6 均为f 态变量，故d ，一一b 也是一态变量。为确定其分 布函数，只需求出其数学期望和方差仃2 。显然 2 = “一一心+ f - 【 盯2 = x ? 砰+ 2 。 i = 1 因此， p r 贴瑚 o _ p r 倭叩 l 叩。一b 一 p r 一盟一 l仃 ：中( 一旦) 盯 其中，中为标准正念分布n ( o ，1 ) 的分布函数。 于是，机会约束( 2 4 ) 等价于 中( 一生) d 一坐 盯 西南交通大学硕士研究生学位论文第1 0 页 篡一巾1 ( 口) 盯 即机会约束等价于 ， r 。、i i 附。一- + 巾。1 ( 口) 【仃+ 仃圳o f l i = l 2 3 2 传统解法的推广 在实际问题中，o ，a ：，a m , b 满足独立正态分布的情况非常少，很多 时候，它们之问是相关的。为了解决这类问题，本节将其推广到系数满足 多元联合正态分布的情况。 假设函数g ( x ，孝) 有形式 g ( x ，善) = a l x i + c 1 2 x 2 + 。+ “。x 。一b “1 ，“2 ，甜，b 有m 十1 维联合f a 分布。 设d 和厂是分别具有密度函数驴( f ) 和( 叩) 的m + 1 维随机向量。其中 d = ( d 1 ，d 2 ，d ) 1 = ( a 1 ，口2 ，d 。，6 ) 则 p ( f ) ：) 一一ij 1 ( 2 j rd e t z e 一如y 2 1 ( 川 妒( f ) =) 2ii 2 e 2 其中，= e ( d 。) ，仃? = ( y 3 。= e ( d ，一, u i ) 2 若，= t d ，t 为一个非奇异矩阵，则 妒( 叮) = 妒( ，。节) j d e t tj 。1 对x r ”，有 西南交通大学硕士研究生学位论文第11 页 则 兀x 1 = 一lo o一1 00 o0 厂= - d ，i ：1 , 2 ，m = t d ，一d 。= 叩，一b 且因为1d e t r i 一= 1 ，所以， 其中 ( 即) = 妒( 丁1 ( x ) q ) r 1 仃、一竿id l71咖训一口1咖训etx e2 t ( 2 z ) 2i1 2 。 ( 2 万) 等1id e t l 一；。；1 一r 1 9 一j _ r q 。( x ) = r 。( z ) 一t 一2 ( x ) q ( x ) = t ( x ) 2 t ( x ) 因此r 有正态分布，特别地 具有均值( x ) 厶+ ，= 叩。一b = p , x ，一心+ ， 西南交通大学硕士研究生学位论文第12 页 和方差0 - 2 ( x ) = ( q ( 工) ) 。+ x 【 x 2 ： x m 一1 所以，。，+ 】( ( x ) ，o - ( x ) ) ，姒0 州如瑚钏蛆倭叩。挑0 = p r f 。+ 1 0 ) ：p r j 厶i 二丛生坐! l 【a ( x )盯( x ) j 叫一然) 其中，巾为标准正态分布n ( 0 ，1 ) 的分布函数。 j ：是，机会约束( 2 4 ) 等价于 蚌筹x 脚 盯( ) 掣一巾t ( 口) a ( x ) 、 即机会约束等价于 4 x ) + 巾。1 ( a ) a ( x ) 0 这样，机会约束规划就转化成一个确定性规划模型，可以用已有的 确定性规划的理论求解。 对于相关机会姗量i 的解泱，熔存下一童中重点讨诊。 第三章相关机会规划 在确定性规划以及期望值模型和机会约束规划中，当对实际问题建模 以后，可行集本质f ：已经确定，然而所给出的最优解在实际问题中可能根 本无法执行。而相关机会规划是一种使事件的机会函数在不确定环境下达 到最优的优化理论，其并不假定可行集是确定的。虽然相关机会规划也给 出一个确定的解，但这个解只是要求在实际问题中尽可能地被执行。 3 。1 随机集合与机会函数 定义3 1 假设q 是由全体元素z 构成的集合，集合a 称为q 中的随机 集合，若 爿= ( x ，以( x ) ) l x q ) ， 其中心0 ) 称为元素x 属于a 的概率。 定义中，2 。( x ) 是元素x 属于a 的概率的意思是在某些给定的随机环 境f ，a 中的元素x 能够实现的概率是。( x ) 。 定义3 2 由所有属于随机集合4 且概率= = i f i 小于瑾的元素构成的集合称 为随机集合爿的甜水平截集，表示为： a 。= x qj ( x ) d ) 考虑具有如下形式的机会约束规划， im a x 可( x ，掌) “ ( 3 1 ) l p r g ，( x ，善) o ，= 1 , 2 ，一，p ) 口 其中，x 是决策向量，亭是随机向量，f ( x ，考) 是目标函数，e 表示关于随 机向量亏的期望算子，g ，( x ，孝) 表示随机约束函数，j = 1 , 2 ，p ，p r ) 表 示事件 的概率，口表示事先给定的置信水平。显然，可以用随机集合 西南交通大学硕士研究生学位论文第14 页 s = ( x ，风( x ) ) f x r “ ( 3 2 ) 表示随机约束毋( 工，孝) o ，= l ，2 ，p ，其中概率函数烁( x ) 定义为 。( x ) = p r g ，( z ，善) o ，= 1 , 2 ，p ) 则( 3 1 ) 中的约束集合是由( 3 2 ) 定义的随机集合s 的“水平截集，记 为s 。所以机会约束规划模型( 3 1 ) 又可以表示为 1 搿矽( 。，手) 定义3 3 旧对于一个给定事件e ，机会函数、f ) 是事件e 在不确定性环 境 g ，( x ，手) s o ，_ ，2 1 , 2 ，p 的概率，其中善是随机向量。 用矿( e ) 表示决策向量x 的分量中与这个事件有关的分量所构成的集 合。 3 。2 相关机会规划模型 相关机会规划其基本形式可以表示成如下形式： m a x f ( x ) x e s 或等价地表示为 i1 1 1 0 2 4 ，( x ) s r i g ，( x ，f ) 0 ，21 ，2 ，p 其中厂0 ) 是某个事件的机会函数，x 是n 维决策向量 合，概率函数为 ( 3 3 ) s 是r ”上的随机集 西南交通大学硕士研究生学位论文第15 页 地( x ) = p r g ，( x ，善) 妄o ，= 1 , 2 ，t ，p x s 表示x 可行的概率为风( 芹) 。值得注意的是集合s 是随机的而不是确 定的。 个点x + s 称为( 3 3 ) 的最优解，若对任意的x s ，有 f ( x + ) f ( x ) 。 用v ( e ) 表示x 中满足事件的分量构成的集合，则当x e ( 即v ( e 1 的 分量满足此事件) 时，机会函数a x ) 将是v ( e ) 中的分量能够实现的最人概 率，若小能满足此事件，则定义机会函数为0 ，即 八加t m a x p r 挺嚣井 l 0 ，x e ， 其中 e + = y = ( y l ，y 2 ，y 。) l y = x ，勘，矿( e ) ；f = 1 , 2 ，一，h 注意对e 4 中的任意元素y = ( y l ，y ：，y 。) ，其中v ( e ) 中的决策分量y 。是 确定的，并且等于x ，而其它的分量是任意的。 在实际问题中，对每一个x = ( 工，x ：，x 。) e ，通常不难确定v ( e ) 以 外的分量x j 的值，使得y + ( x ) = ( y ? ，y ：，j ，：) ，其中 y ? = f ! ；i ； 喜； - zs 拧， 满足 厂( x ) = p r g ，( _ y + ( x ) ，善) - 0 ，= 1 , 2 ，p ) 其巾x e 。因此，事件e 的机会函数为 西南交通大学硕士研究生学位论文第16 页 ，、。，：f p r g ，；! j ? ；。) ，x ee 。，。， 1 0 ， t 仨e ， 通常，点y ( z ) 一般在一些极端的位置耿值。例如，对工e ，决策变 量中v ( e ) 以外的分量x ? 将取值0 。称约束 g ，( y + ( x ) ，善) 0 ，= l ，2 ，p 为关于事件e 的诱导约束。 3 3 相关机会规划的解法 由( 3 4 ) 知f ( x 1 0 ，所以相关机会规划( 3 3 ) 等价丁 f m a x p r g ，( y + ( x ) ，孝) o ，= l ，2 ，一，p ) l x e 现刘随机约束条件中的函数毋( y + ( x ) ，告) ，j = 1 , 2 ，p 的不同情形哥以 讨论。不妨先只考虑一个约束条件的情形，若g ( y + ( x ) ，善) = h ( x ) 一舌，则可 以得到以下定理。 定理1 ：随机规划j m a x p “6 譬垮毋等价于确定性规划 m i n 6 譬。 fx l 茁e f 明：p r h ( x ) f = 1 一( d ( ( x ) ) 因为中是h ( x ) 分布函数，则中单调递增，所以 鼍野p r 矗( x ) 毋= m 曼x 1 一o ( 矗( z ) ) = 1 - 鼍磐中( ( x ) ) 西南交通大学硕士研究生学位论文第17 页 = 1 一m ( m i n ( x ) ) 证毕。 若g ( y + ( x ) ，亭) = 口，一一b ，其中q ，口。，6 有m + l 维联合正态分巾 其均值为= ( “，。) 和协方差为，则 a ，x 。一b n ( p z ，= z ) 其中f = ( 一，h ，一1 ) ( 本章中出现的z 均与此同，其后不再说明) 。 定理2 ：随 【规划 m a ) ( p r 善q t s ( 3 5 ) 等价于确定性规划 lx e 忐，。 lx e 证明： p r ( q ts 研= p r 口。x ，一b 一, u z 一： 因为。足分御函数，则巾单调递增。所以 m a xp r z a 。x 。b ，) 三丝二 z 三 学卜( 惫 ) 、lll， 三一刳是一万吨 。 卜 西南交通大学硕士研究生学位论文第18 页 ：1 一m i 。由f 善 脏” l z 。zj 吖卿惫 证毕。 随机关系”1 假设一个决策向量的月个分量能够被划分成k 组，这组之 问是相互随机独立的，而每组内部的分量却是随机相关的，并且当每组的 分量同时要求实现时，则它们有相同的实现机会。 根据随机关系，一般地，g ，( t 亭) 兰o , j = 1 , 2 ，p 是相互随机独立的， 所以 p r g 心，善) o ，= 1 ，2 ，p ) = 兀p r g ，( x ，舌) so 因此，根据定理t 和定理2 可以推出； 推论，随机规划 m a x p “6 “翟! 玺产1 2 ，脚等价于确定性规划 1 】1 觚珥 1 加删】。 1x e 推论2 随机规划f m a xp r 口，：兰z 。1 2 ，印等价于确定性规划 卜垂卜。c 轰 。 ix e 其中a ，是随机变量矩阵爿的第行，, u j 和分别是埘+ 1 维正态随机 i j m 一- ( 爿，b ，) ：( an ，a 。，d ，6 ，) 的均值向量与协方差矩阵。 西南交通大学硕士研究生学位论文第19 页 定理。：如果：+ 是m i n - 了：怠) 的最优解，且胆。 。，则存在 + 使得 ix e 心扫铲。，且如孙，其鸭是卜譬最雠 觋 = 等， 十参) 最蹴删于任意的 x e 二上t ， ( 扩z z 4 ) 2( z 。z z ) 2 蚓为j _ t + l ，f o ，且肛4 o ，故 参黑蔓三2 ( 患十1 )胆4 r z 十t + 1 ： 、矿。4 7 对上式两边同时乘以，z z + ，再加上一三一z z ，得 生z + r 。一土z - 三z 1 = + , u z + 22 因为a + ：z * z z l * ，则 此$ 旯+ 肛一圭z z z - + 肛l j l z + 由j 一。的任意性，故当 ：a + 时，。+ 是m a x 枷一；一z ) 的最优解 即z 8 = 2 因m 罟，所以脚一扣豳。_ o 。证毕。i 口 。 + 西南交通大学硕士研究生学位论文第2 0 页 由定理3 知，满足肛。一z ：乙：o 的丑+ ，使得 “a x 五+ 一言。z ) j1 九 1x e 一 的最优解：。且肛。， 。，则孙为m i n 差茜) 的最优解。又由定理：， fx e 知其为随机规划( 3 5 ) 的最优解，办即给出厂随机规划( 3 5 ) 最优解的 另一种解法。 m a x “ s t p r 芝叩，6 ) 口 36 z e m 二 而p r d ，x ，6 ) a 等价于胆+ 中“( a ) ( z z z ) 2 0 ，故随机规划( 3 6 ) ，1 】 等价于确定性规划： m a n 5 f i ( 37 ) 胆+ 中一1 ( 口) ( 一z z ) 2 0 z e 其中，当。一( 口) 0 时，约束条件中的l a z + 中。 ) ( f ) 2 是一个凸函数， 着为凸集，则( 3 7 ) 的可行集为凸集。如下面的定理将证明其是凸函 数 定理4 ：当中1 ( d ) o 时，函数，0 ) = # z + q b l 心) 7 西是凸的。 证明：因为p z 是一个线性函数，即凸函数，且1 ( 口) 0 ，所以只需证明 西南交通大学硕士研究生学位论文第2 1 页 r p ( z ) = - , z 1 e z 是凸的。 对r 任意的z ，z ：和2 o ，1 ， p ( z i ，z z ， ) 垒 妒 厄。+ ( 1 一五) z 2 】一 丑妒( z ) + ( 1 一丑) 妒( z 。) e 2 z l + ( 1 2 ) z 2 + 2 1 5 0 ( z 1 ) + ( 1 一a ) 妒( z 2 ) 】) = 妒2 枉f + ( 1 2 ) z 2 卜f p ( z t ) + ( 1 一五) 妒( z ：) 2 = 丑2 z 芦+ 2 2 ( 1 2 ) z l y z 2 + ( 1 一五) 2 z ；z 2 2 2 z z z 一2 2 ( 1 一丑) 三辱i i 压一( 1 一丑) 2z ；z z ： = 2 2 ( 1 一五) ( z j ：一乖；：- , z ；2 2 2 ) 协方差矩阵是半正定的，即对于任意的r ，有： ( 也+ z 2 ) z ( t z + z 2 ) = f2 z 2 z i + 2 t z z z 2 + z ；z z 2 0 所以，判别式0 ，即( z ；z z ：) 2 ( z ；z z ：) ( z i ：) ，则z ：。止i 酉；蚕i 所以p ( 互，z 2 丑) 0 ， n y , j 妒【允、+ ( 1 2 ) z 2 】+ 五p ( z 。) + ( 1 一五) 妒( z ：) 0 ，贝0 妒 z l + ( 1 2 ) z 2 】一 2 ( o ( z 1 ) + ( 1 一五) 妒( 三：) 0 所以 妒【丑z l + ( 1 2 ) z 2 兄妒( z 1 ) + ( 1 一a ) p ( z 2 ) 故妒( z ) 是凸的。证毕。 3 4 求解算法 虽然文中给出了相关机会规划的一些解法，但其求解仍然很困难，甚 至某些无法用已有的理论求解，这时运用遗传算法求解给我们带来了极大 西南交通大学硕士研究生学位论文第2 2 页 的方便。 3 4 1 常见分布的随机变量的产生 常见分布的随机变量的产生是以均匀分布为基础的，下面给出常见分 御的m a t l a b 程序。 常见分布m a t l a b 语句 ( 1 ) 均匀分布u o ，1 】r = r a n d ( m ，n ) ( 2 ) 均匀分布u a ，6 r = “ i f r n d ( a ，b ，m ，”) ( 3 ) 指数分布e x p ( 五)r = e x p r n d ( 2 ，m ，n ) ( 4 ) 下态分布( ，j 2 )r = n o r m r n d ( ，盯2 ，川，h ) ( 5 ) 二项分布b ( n ，p )r = b i n o r n d ( n ，p ，m ，f ) ( 6 ) 1 e t 松分饰丌( a )r = p o i s s r n d ( 2 ，m ，n ) 3 4 2 机会函数的随机模拟 设g ，( x ，告) ，= 1 ，2 ，p 是事件e 在点x 的诱导约束，则机会函数f ( x ) 由下式给出： ：( x ) = p r g j y + x ) 吉i 。，= l 2 ，一，p ：i 主! 其中 是随机变量，其概率分布