（应用数学专业论文）基于遗传算法的机会约束规划区间估计.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 随机规划是数学规划的一个重要分支，然而它不同于普通的数学规划。 由于在系数中引入工髓机变量，使得随机规划问题的求解比普通的数学规划 要复杂得多。厂本文试图利用概率统计有关理论作为工具，对随机规划特别是 机会约束规划进行研究。 ( 随机规划的解法目前不外乎两种有效的途径。其第一种途径是将随机规 划转化为各自的等价确定性规划，然后利用已经发展得较为完善的确定性规 划的解法去解之。另一种途径是逼近方法，利用随机模拟技术，通过一定的 遗传算法程序，最后得到机会约束规划问题的近似的目标函数最优值和最优 解。乙p 一 7 本文总结分析了这两种解决机会约束规划的方法。针对第一种途径，把 那些可转化为确定性规划的机会约束规划的类型推广到系数具有指数族结 构的情形。对更一般的机会约束规划问题，在前人工作的基础上，得到了目 标函数最优解的区间估计和最优值的估计区域，讨论了影响该估计的精度的 要素，并指出提高估计精度的方法。该区间估计中包含了目标函数的一个最 优估计值。鉴于基于随机模拟技术的遗传算法在求解随机规划问题上的优越 性，本文指出，改变遗传算法的参数条件，在此基础上求得机会约束规划的 若干个最优值，以这些最优值为样本点，利用多元样条回归，拟合得到最优 值函数，进而求出最优值函数的l i p s c h i 呼s 常数，从而对于任一机会约束规 划问题，都可以得到它的一个区间估计。任遗传算法的基础上对机会约束规 划进行区间估计，这一做法一方面弥补了传统方法解决机会约束规划问题的 不足，另一方面又继承了遗传算法在求解机会约束规划的优点，为解决随机 规划特别是机会约束规划提供了一个较好的途径。) 卫一 关键词： 随机规划；机会约束短翮；遗传算法；区间估计；l i p s c h i t z s 常数、 j 西南交通大学硕士研究生学位论文第1 l 页 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 sa ni m p o r t a n tb r a n c ho fm a t h e m a t i c a lp r o g r a m m i n g h o w e v e r i ti sv e r yd i f f e r e n tf r o mo r d i n a r ym a t h e m a t i c a lp r o g r a m m i n g h o wt o s o l v ei ti sm u c hm o r ec o m p l e xt h a nt h a to fo r d i n a r ym a t h e m a t i c a lp r o g r a m m i n g b e c a u s eo fi t sr a n d o mc o e f f i c i e n t s t h i sp a p e rt r i e st o s t u d ys t o c h a s t i e p r o g r a m m i n g ，e s p e c i a l l yc h a n c ec o f l s t r f l j n e dp r o g r a m m i n go f ft h et h e o r yo f p r o b a b i l i t ya n ds t a t i s t i e s a tp r e s e n tt h e r ea r et w om a i nm e t h o d st os o l v i n gs t o c h a s t i cp r o g r a m m i n g t h e f i r s ti st r a n s f o r m i n gi ti n t oe q u i v a l e n td e t e r m i n i s t i cp r o g r a m m i n ga n dt h e n s o l v i n gi tb yu s i n gt h et h e o r yo fd e t e r m i n i s t i cp r o g r a m m i n gt h a th a sb e e n d e v e l o p e ds u c c e s s f u l l y a n o t h e ri sg e t t i n gt h ea p p r o x i m a t eo p t i m u mv a l u ea n d o p t i m u ms o l u t i o no fc h a n c e c o n s t r a i n e dp r o g r a m m i n gt h r o u g hs o m ec e r t a i n g e n e t i c a l g o r it h mb a s e do nr a n d o ms i m u l a t e dt e c h n o l o g y t h is p a p e rs u m m a r i z e st w om e t h o d so fc 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 a c c o r d i n gt ot h ef i r s tm e t h o d ，t h i sa r t i c l eg e n e r a l i z e st h ec o e f f i c i e n tt y p e o ft h o s et h a tc a nb et r a n s f o r m e di n t od e t e r m i n i s t i cp r o g r a m m i n gt oe x p o n e n t i a l f a m il y f o rm o r eg e n e r a lc 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 。w eh a v eo b t a i n e dit s e s t i m a t e di n t e r v a la n dh a v ed i s c u s s e dt h ef a c t o r st h a ta f f e c tt h ep r e c i s i o n o fe s t i m a t e do p t i m u mv a l u ea n dp o i n t e do u tt h em e t h o dt h a tr a i s e se s t i m a t e d p r e c i s i o n t h i se s t i m a t e di n t e r v a lc o n t a i n e da ne s t i m a t e dv a l u eo fg o a lf u n c t i o n i nv i e wo ft h ef a c tt h a tt h eg e n e t i ca l g o r i t h mo fs t o c h a s t i cp r o g r a m m i n gb a s e d o nr a n d o ms i m u l a t e dt e c h n o l o g yh a ss u c c e e dg r e a t l y ，t h isp a p e rp o i n t so u tt h a t c h a n g i n gp a r a m e t e r so fg e n e t i ca l g o r i t h mc a n 曲t a i n as e q u e n c eo fo p t i m u mv a l u e s o fg o a lf u n c t i o n t a k i n gt h e s eg e n e t i ca l g o r i t h mv a l u e sa ss a m p l i n gd a t a ，w e c a ng e tf i t t i n go p t i m u mf u n c t i o nb yu s i n gm u l t i v a r i a t es p l i n er e g r e s s i o na n d g e tt h el i p s c h i t z sc o n s t a n to ft h ef i t t i n go p t i m u mf u n c t i o n s of o ra n yc h a n c e c o n s t r a i n e dp r o g r a m m i n gp r o b l e m ，w ec a ng e ti t si n t e r v a le s t i m a t e k e yw o r d s ：s t o c h a s t i c p r o g r a m m i n g ，c h a n c e c o n s t r a i n e dp r o g r a m m i n g g e n e t i ca l g o r i t h m ， i n t e r v a le s t i m a t e ，l i p s h c i t z sc o n s t a n t 西南交通大学硕士研究生学位论文第l 页 第一章绪论 1 1 问题的提出 在日常生活中，很多问题都可以归结为数学规划问题。例如运输问题、 经济利益最大问题、费用最小问题以及路程最短问题等等，都可以用数学规 划去描述。近年来，数学规划的理论日渐成熟，并在经济生产中发挥了很大 的作用。在普通的数学规划中，模型的系数一般都是确定的常量。但在现实 世界中，特别在人们更为关心的经济生活中，这种系数在相当多的情况下不 是常量，而是呈现一定的随机性。因此人们在普通数学规划的基础上发展了 随机规划的理论，使之更符合客观实际情况。 广义的说，凡是含有随机变量的数学规划都可以称为随机规划。如上所 述，由于引进了随机因素，随机规划显得比普通数学规划更切合实际。但也 正因为随机规划模型中含有随机系数，所以不能简单地套用普通数学规划的 现成理论，因此随机规划比普通数学规划更难以处理。显然，解决随机规划 的关键在于如何处理模型中的随机变量。目前，国内外解决随机规划的手段 大致有两类：其一是对某些具有特殊结构的随机规划，通过各种办法，将其 转化为确定性等价类，即将随机规划转化为确定性的数学规划，然后利用大 量的已有的普通数学规划的理论去解决；其二是逼近的方法。正如在普通数 学规划中利用线性规划去逼近非线性规划一样，在随机规划中也利用某些较 为简单的随机线性规划去逼近其它的复杂的随机规划，或直接用确定性的数 学规划去逼近随机规划。近几年来，某些智能逼近算法在解决随机规划问题 上显示了它们的优越性。在这些智能算法中，尤以利用遗传算法解决机会约 束规划较为成功。遗传算法主要通过随机模拟技术去处理机会约束规划中的 约束条件，它不象一般的逼近方法那样需要繁杂的计算。以下本文在涉及到 第二种方法时，以遗传算法作为代表。 以上两种解决随机规划的方法，各有所长，互有优缺点。第一种方法是 在随机规划发展初期，人们使用的主要方法，这种方法虽然能够得到问题的 精确的理论解，但它只能解决一小部分特殊类型的随机规划；对于大部分的 随机规划问题，这种基于转化的方法是无能为力的，因而这种方法的应用范 围受到很大的限制；第二种方法即遗传算法具有普遍性，理论上它能够近似 西南交通大学硕士研究生学位论文第2 页 解决相当一部分的随机规划问题。特别地，对于某些复杂的随机规划，智能 算法也许是唯一的可行方法。但美中不足的是，智能算法只能得到问题的近 似解，而且难以评价近似解的精度。 在数理统计中，对某一变量作出区间估计，并讨论该估计的精度以及改 进精度的办法是相当重要的。一般情况下，随机规划的目标函数最优值及决 策变量的最优解集是与模型中的随机系数有关的，从而呈现出一定的随机 性。那么，能不能给这种具有随机性的目标函数最优值以及决策变量的最优 解集作出某种程度的区间估计呢? 众所周知，衡量区间估计的精度的一个重 要指标是估计区间的长度，估计区间长度越小，估计精度就越大：反之，估 计区间长度越大，估计精度就越小。进一步，如果能够得到某种区问估计， 那么又如何改进该估计区间的精度呢? 如上所述，随机规划有两种解法，而这两种解法各有千秋。能不能结合 这两种方法的优点，并将其用于随机规划的目标函数的最优值以及决策变量 的最优解集的区间估计? 目前，国内外的文献还没有这方面的尝试。本文试 图在前人工作的基础上，结合这两种方法的优点，利用遗传算法求解机会约 束规划的目标函数的最优值和决策变量的最优解集，尝试给出目标最优值和 最优解集的置信区间，并简单讨论影响该估计区间精度的主要因素。 1 2 国内外的研究状态 随机规划实际上是确定性数学规划的延续和更高发展，它的理论适合于 解决含有随机因素的数学规划。 当前，国内外对于随机规划的研究，主要集中于三个方面。其一是继续 寻找随机规划的新的和更为有效的算法，但这方面的研究并没有取得太大的 进展。1 9 9 5 年n g r o w e z j 研究了随机规划的数值解法：2 0 0 0 年c a s e y 【2 】 发表了关于随机规划的极限理论的论文；w a n g 3 研究t 二阶段规划模型的逼 近解法并将之应用于地下水的规划使用；国内学者刘宝碇对包括随机规划在 内的不确定性规划也作了大量研究。其二是基于实际应用的要求，同数学中 许多其它的理论一样，深入研究随机规划问题的稳定性和敏感性，国内外不 少学者都在这方面作出了努力。如g o n g 4 l 在分析了最短路径机会约束规划 模型解的结构后，得到了机会约束规划的稳定性与敏感性的一些结论；2 0 0 1 年骆建文【2 2 l 也作了概率约束规划的稳定性分析。其三是现有随机规划理论成 西南交通大学硕士研究生学位论文第3 页 果的应用。近年来，许多随机规划方面的文献，都侧重于利用已经发展起来 的随机规划的理论去解决现实生活中的规划问题。这种应用性的研究开展得 如火如荼，事实上，当前发表的随机规划方面的论文大都是这种应用性的。 如d ep a o l o 5 在他的博士学位论文中研究了高等学校的教育质量与注册学 生的素质、资金投入、财政盈余等之间的随机规划模型；h e i k k i n e n 【6 】研究了 网络稀有资源的分配与定价问题的随机规划模型；k a r a b u k 7 对高技术条件 下半导体产品的供给与需求进行了研究，得到了多阶段随机规划模型； s a a d o u l i 瞄j 研究了水资源的利用和保护的多目标随机规划模型。 受于限制，经典的随机规划主要关注线性模型。现在，许多研究试图在 随机动态规划、随机整数规划、随机分式规划、随机目标规划以及随机多目 标规划 9 - 1 0 1 等领域取得进展。 1 3 本文的结构 本论文的结构大致如下：由于随机规划的传统解法是把它们转化为其各 自等价的确定性数学规划。因此，作为基础知识，论文第一章一般性地介绍 了数学规划的基本概念、分类及其相应的解法。对于某一随机规划，如果能 够找到它的等价的确定性规划，则本文就认为该随机规划已经得到解决。第 二章介绍了随机规划的背景和分类；对于分布问题和二阶段规划，只简单介 绍了它们的概念，而重点介绍了机会约束规划的传统解法。第三章介绍了本 文处理问题时用到的两种方法，即基于随机模拟的遗传算法和多元样条回 归。遗传算法中的随机模拟技术主要用来处理机会约束规划的约束条件，而 样条回归则主要用来处理遗传算法所产生的机会约束规划的目标函数的最 优数据。本文并没有采取数理统计中常用的多元回归，主要因为所得到的数 据不一定是正态的；而线性回归和多元回归的理论一般要假设所处理的数据 是正态的；本文同样没有采用非参数回归，主要是考虑到非参数回归( 如核 回归) 对拟合显式的回归方程有一定的难度。采用多元样条回归的另一个考 虑是可以充分利用m a t l a b 软件的强大的插值功能。第四章在前人工作的基础 上，给出了机会约束规划的目标函数最优值和决策变量最优解集的区间估 计。最后，文章给出了基于随机模拟技术和遗传算法的机会约束规划区间估 计的一个实例，用以验证算法的有效性。需要说明的是，由于随机模拟技术 中的变量是随机产生的，因此每次执行的结果可能不太一致。正如数理统计 西南交通大学硕士研究生学位论文第4 页 中某参数0 的置信区间尸 鼠0 0 2 l 一口不能理解成是参数口落入某区间 q ，岛 的概率为1 一口，而应理解为大量的这种置信区间中有百分之 1 0 0 ( 1 一口) 的区间能够包含参数0 ，即它是一种大样本的统计性质；本文中的 区间估计也必须作同样的理解。因此，如果某些置信区间的结果偏离了预期 的值，也是较为正常的。 1 4 本文的主要工作 本论文主要作了如下方面的工作：第一，推广了能够利用传统方法求解 的机会约束规划的类型，即将能够转化为确定性的机会约束规划的类型推广 到系数随机变量服从指数族的情形；第二，结合求解机会约束规划的两种方 法( 即传统方法和智能算法) 的优点，给出了机会约束规划的基于遗传算法的 目标函数最优值和决策变量最优解的估计区间，并讨论了影响该估计区间精 度的主要因素和改进精度的方法。 西南交通大学硕士研究生学位论文第5 页 第二章数学规划简介 2 1 数学规划发展简述 数学规划fm 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 rp 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 sp 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 rp 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 cp 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 y 发表的“生产组织与计划中的数 学方法”一书，是线性规划的首批著作。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 u 和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 提出，可以看成是多目标规划问题 的一个特殊情况。在实际问题中，一个目标通常只有在牺牲另些目标的情 况下才能实现，而这些目标之间一般是不相容的。因此，在这些不相容的目 标之间，根据其重要性，可以建立一个优先级。并根据这个优先级为所有目 标排序，尽可能实现更多的目标。 在某些线性规划问题中，决策变量只有取整数值才有意义，即约束条件 中需补充决策变量取整数值的限制，从而得到整数规划。整数规划可以分为 线性整数规划，非线性整数规划，多目标控数规划与目标整数规划。如果决 策变量仅取0 或1 ，则称整数规划为0 - 1 规划。 线性规划与非线性规划所研究的问题，通常是与时间无关的静态问题。 1 9 5 4 年，b e l l m a n 创立了动态规划的基本理论。 西南交通大学硕士研究生学位论文第6 页 2 2 数学规划的基本概念 数学规划可以描述为在一些数学关系诸如等式或不等式表示的约束条 件下，求一个( 或一组) 函数的极值问题的方法。设f ( x l i ，) ； g l ( x 1 ，一，x 。) ，g 口( ，x 。) ；h i ( 一，x 。) ，矗p ( x 1 一，x 。) 都是行个 变量一，x 。的实值函数。数学规划问题就是对某一性能指标f ( x l i ，x ，) ( 如经济利益最大，费用最小以及路程最短等) 求最大值( 或最小值) ，其中变 量一，x 。应满足由函数g ，( x l i 一，x ，)( i = 1 , 2 ，q ) 及函数 h j ( x l ，_ 一，x 。) ( ，= l ，2 ，p ) 的不等式和等式所限定的条件。写成数学表达式， 即求x l ，使得f ( x l ，一，x 。) 达到最小值，记为 m i n f ( x l ，x ，) 满足限定条件 g ，( x l ，x 。) 0i = 1 , 2 ，一，g h j ( ，x 。) = 0 ，= l ，2 ，p 称厂( 一，x 。) 为目标函数；称( ，x 。) ( i = 1 , 2 ，q ) ， h j ( 而，x 。) ( ，= 1 , 2 ，p ) 为约束函数：称 g ( x t ，z 。) 0i = l ，2 ，g ，( x l ，x 。) = 0，= 1 , 2 ，一，p 为约束条件；称满足约束条件的一组变量值五，x 。为数学规划问题的一组 可行解；所有可行解的集合组成可行解域。 数学规划的标准形式为： 兰翟黑盐川z ，。 记x = i x l ，x 。】7 ，g ( x ) = 【g l ( x ) ，g ，( 工) 】7 。 则问题( p ) 又可以写成 i m i n f ( x ) i g ( x ) 0 若记所有满足条件的解的集合为 r = x i g ( x ) 0 西南交通大学硕士研究生学位论文第7 页 即r 为问题的可行解集合。此时，问题又可以写成 r a i n ) 任意形式的数学规划问题都可以化为上述的标准形式，以下分别予以说明。 ( 1 ) 若约束条件中有等式约束，如 h 。( x ) = 0 婀令 曼嵩：。 即同时要求h ( x ) 0 ，h i ( x ) s 0 ，显然，必定满足 ( x ) = 0 。反之亦然。于 是，可将一个等式约束转化为等价的两个不等式约束。 ( 2 ) 若对目标函数要求最大值，如 ( p m 缸) m 野，( z ) 则可令f ( x ) = - f ( x ) 可转化为( f ) m 啦f c ( x ) 该问题( - f i ) 与原问题( p 。) 是等价的。 2 3 数学规划的分类 如果目标函数及约束条件都为线性函数，则称其为线性规划：如果目标 函数或约束条件中至少有一个函数是关于而，工。的非线性函数时，则称其 为非线性规划。 数学规划大致可以分为确定性数学规划与不确定性数学规划两大类。其 中确定性数学规划包含线性规划、整数规划、分式规划、动态规划、目标规 划、多目标规划和非线性规划等。不确定规划主要包括随机规划与模糊规划。 其中随机规划有分布问题、机会约束规划和二阶段规划等。 2 4 线性( 非线性) 规划的解法概述 线性规划一般有如下的标准形式 西南交通大学硕士研究生学位论文第8 页 ( l p ) m l n c j x l + c 2 x 2 + c m x m a l i x l + a 1 2 x 2 + + a l m x m = b l a 2 1 x 1 + a 2 2 x 2 + + a 2 m x = b 2 a s i x l + a s 2 x 2 + + a s m x = b j o l o ，x 2 0 ，一，x 0 警 其中， c = ( c l ，c 2 ，一，c ，) 7 ，a = ( 口。) ，b = ( 6 l ，6 2 ，一，b ，) 7 ， 西南交通大学硕士研究生学位论文第9 页 第三章随机规划 群 西南交通大学硕士研究生学位论文第1 0 页 另一方面，数学上习惯按决策者所获得的信息，把随机规划问题大致分 为两种类型，即被动型和主动型。被动型即所谓“等待且看到( w a i ta n ds e e ) ” 模型，即决策者等待观察问题中随机变量的实现，然后适当利用这些实现的 信息作出决策，分布问题属于此种类型；主动型即所谓“这里且现在( h e r ea n d n o w ) ”模型，决策者必须在没有随机变量的实现信息的情况下就作出决策， 二阶段问题和机会约束规划问题均属于此种类型。 以下简单介绍分布问题和二阶段规划的概念。 3 2 分布问题与二阶段问题简介 3 2 1 分布问题 所谓分布问题( d i s t r i b u t i o np r o b l e m ) ，就是对每一个样本点m q ，求解 线性规划问题1 2 0 】 f 孝 ) = m i n c7 ( o j ) x a ( w ) x = b ( c o )( 2 ) 【x o 并求善 ) 的分布或其它概率特征。 3 3 1 二阶段规划 二阶段规划的特点是必须在随机变量的实现之前作出决策。考虑如下的 随机规划f 2 1 1 ： f m i n c 7 x a ( w ) x = b ( e o )( 3 ) l x o ( 3 ) 式中c 为确定性向量。如果需要在观察到一( 国) 和b ( r _ o ) 的任何实现之 前就作出决策以确定x 的值，显然这时x 不一定能够保证对所有的印q 都 满足约束条件a ( w ) x = b ( e o ) ，也就是说，4 h 一6 ) 未必为0 。令 y = a ( w ) x b ( e o ) ，即差a ( w ) x b ( e o ) 可以用向量y 来刻划。由于约束条件收 到破坏，决策者肯定会因此受到一些惩罚，设其为q r ( c o ) y 。对于决策者来 说，自然希望这一惩罚越小越好，所以就产生了另一种求极值问题： 西南交通大学硕士研究生学位论文第1 1 页 lm i n q 。( o g ) y 4 ( 沁+ ( ) y = 6 ( 棚) ( 4 ) l y o 将确定决策变量x 的问题称为第一阶段问题，则上述问题( 4 ) 就称为第二 阶段问题。上述问题最终化为： i m i n c 7 x + e ( m i n q ( y l ( 叻+ 月( ) x = b ( c o ) ，y 2 0 ) )，、 ( 5 l h d c r ” 问题( 5 ) 即为一般形式的二阶段问题。其中缈称为补偿矩阵。用q ( x ，c o ) 表示 问题( 4 ) 的目标函数的极小值，即q ( x ，国) = m i n q 7 ( ) y 。记q ( x ) = e q ( x ，0 3 ) ， 则问题( 5 ) 等价于下列问题： j m i n c r x + g ( ( 6 ) i x d 问题( 6 ) 是个确定性问题，称为与问题( 5 ) 等价的确定性规划。其中q ( x ) 般是非线性函数，故式( 6 ) 通常是一个非线性规划问题。 求解二阶段问题的一般方法是，先求出q ( x ) ，然后用非线性规划的方法 解问题( 6 ) ，最后求解问题( 5 ) 。 3 3 机会约束规划 机会约束规划的一般形式为 m i n f ( x )( 7 1 i p a 。x 玩) q 、 式中4 = ( 口。) 为系数矩阵，b 1 为系数，厂( x ) 为目标函数。机会约 束规划问题的特点是，要求满足约束条件的概率在一定范围内。 例如，一零售商每天要决定某种食品的进货量x ，该食品的批发单价为 h ，零售单价为g ，若当天不能售完，剩余的食品将变质。该种食品每天的 销售量是一随机变量，7 ( 国) 。如果发生剩余变质情况，零售商就要受到损失， 在这种情况下，零售商在决定进货量x 时，为了保险起见，希望食品销售不 出而变质的概率小于o 1 。在此前提下，试建立利润最大的优化模型。 依题意，可得如下的机会约束规划模型： 西南交通大学硕士研究生学位论文第1 2 页 f m a x ( g h ) x 1 p x 叩( ) ) 一墨 s2l i i f仃+ 西巧 。川 = 2， 此因 西南交通大学硕士研究生学位论文第1 3 页 = 巾 其中，m 为标准正态分布( 0 ，1 ) 的分布函数。 于是，机会约束尸 一，x 6 ， 口，等价于 m c 弘q 拿巾一一( q ) 、 芝即，叫佳叩2 ，2 耐卜- ( 蚴心x ，叫l x ，+ 盯川。( ) j = l j = l ( 2 ) 伽玛分布族情形 此时，口，与b 均服从g a m m a 分布。为讨论方便起见，考虑只有一个约 束条件p ，芝a x + b o p 。 l j z l 设a ，( j = 1 , 2 ，m ) 服从g a m m a 分布 a g f i ( g i , 触，)( 口，五 0 ) j = 1 , 2 ，一，m 由于g a m m a 函数在尺度参数相同的条件下关于形状参数具有可加性，且具 有如下性质： 若x g a ( a ，旯)( 口，旯 o ) ，贝0 n r g a ( a ，兰)( 口 0 ) 于是 a j x j g a ( a ，a ) j = 1 , 2 ，m d ，x ，g a ( 吩，名) j * l ；l 又设b g a ( a ，名) ，则 口，x + 6 g a ( 口j + 口，旯) j - ii - i 令a = a ，则 西南交通大学硕士研究生学位论文第1 4 页 y a j x + 6 一g 口( 口，五) 格 叫可高一e r 。t r 凄三，x 薯q e “出p cp 为置信水平， 由于伽玛分布族包含了指数分布族与z 2 分布族，即 e x p ( 2 ) = g a ( 1 ，a ) 以胪g ，尹1 因此，当口，与b 均为指数变量或z 2 变量时，也可以将机会约束转化为确定 性约束。 ( 3 ) 指数族情形 下面本文将能够转化为确定性规划的机会约束规划的类型，推广到系数 随机变量为指数族情形。此时，a 与b 均为服从同一类型指数族随机变量。 指数族随机变量具有成如下的密度形式。”： r 1 厶( x ) = c ( 口) e x p i t , c ，( 目) 乃( x ) ( x ) l ，；1j 其支撑缸：厶( 工) 0 不依赖于口，又可写成“” 厶 ) = c ( x ) e x p ( & 一6 ( 口) ) ( 考虑x 为一维) 设x ，艺，y 卅为独立的随机变量，且均服从指数族分布。可以证明，指数族 变量的和仍为指数族变量”1 。即当r ( f = 1 , 2 ，m ) 有分布 厶( y ) = c ( y ) e x p ( 6 y 一6 ( 目) ) 时，$ 艮从c ( y ) e x p o y m b ( o ) ) ，其中c ( j ，) 可能与 西南交通大学硕士研究生学位论文第1 5 页 目( y ) 中的c ( _ y ) 不同。 设n ( j = 1 , 2 ，m ) 为指数族变量， 口c j ( x ) e x p ( o j x b ( o j ) ) j = 1 , 2 ，m 则 q x ，c ，+ e x p x 詈x 一。c q ，l 而q x ，仍然服从指数族分布，不妨设 口，x ，c ( y ) e x p o y - b ( o ) 若b 也服从指数族分布 6 亭( y ) e x p 函一6 ( 万) 则巳o + 6 也仍然服从指数族分布，设为 杰q _ + 6 e ( y ) e x p 妨y 一6 万) ) 于是机会约束p f 芝a j x j + b 0 0 l j - o l 口转化为如下确定性约束于是机会约束p 口转化为如下确定性约束 j 一 一1 【石( y ) e x p 渺一6 ( 口) 妙口 ( t 2 为置信水平 3 3 3 机会约束规划的稳定性 逼近方法是求解随机规划的一个很重要的方法，但为了保证所求的近似 解的确为原问题的解的近似，就有必要研究随机规划的稳定性。近年来，许 多学者作了机会约束规划稳定性的研究 1 3 , 1 4 , 1 5 , 1 6 , 1 7 , 1 8 , 1 9 “，如我国学者骆建文f 2 2 】 得到了如下较好的结果： 当随机变量序列诲耻( m ) 依分布收敛于善 ) 时，相应于话耻( ) 的机会 约束规划问题的最优值收敛于原问题的最优值。具体如下： 定理1 设f ( x ，“) 在r ”。上连续，g ，( x ，“) 在r ”。上为连续凸函数 j = 1 , 2 ，p ，x r “，“r 。f ( ) 具有严格拟凹概率分布，且对每一x ， g ，( x ，孝( ) ) 有连续分布( j = 1 , 2 ，p ) 。此外，至少存在一点，使得 西南交通大学硕士研究生学位论文第1 6 页 尸p j g s ( x 。，善) ) 0 ，= 1 ，2 ，讲 口，则手1 ) 当依分布收敛于孝( 印) 时， 最优值序列z ( 害( ) ) 收敛于z ( 孝 ) ) 。其中， z ( ( ) ) = 。r a i n 渺( x ，( m ) ) i p 取，( ) ) o ，= 1 ，2 ，p ) a ) z ( 孝( 棚) ) - 。r a 洲i n 渺( x ，孝( 国) ) ip 虹，善( 训o ，j = 1 如，p j 口j 其中x 紧致。 证明：具体详见 2 2 1 定理3 2 。 西南交通大学硕士研究生学位论文第17 页 第四章多元样条回归和遗传算法 4 1 多元样条回归 4 1 1 三次样条函数 所谓“样条”( s p l i n e ) ，本来是指在制造飞机或轮船的过程中，为了描 绘出光滑的外形曲线而使用的一种工具，即富有弹性的细长木条。绘图时， 将样条固定在样点上，其它地方随其自由弯曲，然后顺着样条画下曲线，称 为样条曲线。样条曲线实际上是由一段一段的三次多项式拼接而成的，在拼 接处( 即样点上) ，不仅函数自身连续，而且它的一阶、二阶导数也连续。 二十世纪四十年代，由数学工作者从数学上加以概括，就得到数学样条的概 念。 定义1 ：给定区间【口，b 】的一个划分a ：a = x l x 。= b ，以及陋，6 】 上的一个函数，( x ) 。若函数j ( x ) 满足下列条件【3 0 】： ( i ) 一致通过+ 1 个点( x ，儿) ，即s ( x j ) = f ( x ，) = 只，i = 0 ，1 ，2 ， ； ( i i ) _ - 阶连续，即j ( 力c 2 【口，b 】； ( i i i ) 三次分段，即在每个小区间k + x ，】上均为三次多项式。则称满足以 上三个条件的函数s ( x ) 为 口，6 】上以x 。，黾，x 。为待定点的插值三次样条 函数。 为了求出三次样条函数s ( x ) 的表达式，引入三次半截多项式 t = 仁东 x i 自身以及它的一阶、二阶导数处处连续，而三阶导数却是一个在x = 0 处跳 跃的阶梯函数。利用三次半截多项式，个三次样条函数s ( x ) 可以唯一地表 示为【3 2 1 s ( x ) = 吩x 7 + f l 。( x - x 。) ： 式中口，= 0 ，l ，2 ，3 及鼠，k = 1 , 2 ，n 一1 为待定系数，因此需要 ”+ 3 个条件来确定。由三次样条函数定义条件( i ) ，可以有疗+ 1 个方程，此外 西南交通大学硕士研究生学位论文第1 8 页 还需要两个条件才能唯一确定”+ 3 个待定系数。一般在边界结点x 。与x 。处 各给出一个条件，称为边界条件。 由不同的边界条件可将插值问题分为三类1 3 0 l ： i 型插值问题： j ( 工。) = f ( x 。) ，j ( x 。) = f ( x 。) 其中厂( x 。) = f 。，f ( x 。) = f 。已失口。 i i 型插值问题： 一( x 。) = f ”( x 。) ，j ”( j ) = 厂”( x 。) 其中，”( ) = f ”。，厂”( x 。) = 厂”。已知。特别地，当一( x 。) = s ”( x 。) = 0 时，称为自然边界条件，由它确定的样条函数称为自然样条函数。 i i i 型插值问题： s ( + o ) = s ( x 。一0 ) ，k = 0 ，1 ，2 这类边界条件给出的样条函数称为周期型样条函数。 由三次样条函数定义中的条件( i ) 以及两个边界条件，可得到疗+ 3 个方程 组成的线性方程组。可以求出疗+ 3 个待定系数。这种方法原则上可行，但系 数矩阵一般是病态的，往往使计算结果失真，或根本无法得到结果。更好地 构造三次样条函数的方法有三弯矩方法与三转角方法【3 1 1 ，这里不再祥述。 4 1 2 多元样条函数及多元样条回归 当待拟合的自变量有多个而，工：，x 。时，设多元样条空间为线性空间的 线性组合，则多元样条函数可写为 s ( x l ，x 2 ，) = s ( x ，) t = l m3mn - i = 口。x ? + ( 工一一) ： t - ij = o1 - 1j = z 当给定因变量y 和m 个自变量x 的n 个样本后，可采用逐步样条回归方 法确定 m3n - 1 s ( x 。，靠) = 口。x + 彰( 一一一) ： ，t l j ；0 i = l j - i 其中的参数为口。，彰，。 西南交通大学硕士研究生学位论文第1 9 页 当样本数量不足够大时，应尽量采用较低阶数的多项式，可较好地避免 高阶多项式出现震荡的龙格现象，从而提高回归模型的拟合能力。具体步骤 如下 3 2 , 3 3 ： ( 1 ) 确定分点 对第i 个自变量x ，的 个样本数据x 。x 。，x 。，按从小到大的顺序排 列，得到新序列一，于是可得到样本区间的所有可能分点个： x f 1 x ，2 x ，。，l = 1 7 1 。 ( 2 ) 生成逐步样条回归备选因子集 当分点确定以后，按下式作变量替换，可得到样条逐步回归各选因子集。 令 z f o = 一 z n = x ? z ；o = z ? z 0 = ( 一一吖) ： z 然= ( t 一吒) ： 则得因子集，z = 【z ? 】譬z ：+ ：，总因子数为( 上+ 3 ) m 个。样条全回归形式为 p ：a z 7 ( 3 ) 引入逐步回归 对因子集k ? 】进行筛选，可从中自动挑选最优分点，合并某些不必要的 分段。例如，若( t 一0 。) ：这一因子在逐步回归中没有入选，则可认为分点0 。 可以去掉，即把第f 个因子的第3 个子区间【0 ”，0 0 与第4 个子区间【一”，】 合并。因此，在多元样条回归中，应用逐步回归筛选技术，具有自动挑选最 优自变量、最优分点和最优表达式的能力。最终建立多元逐步回归模型为： p ：a z r 注：具体回归过程中，五可用其甩个样本的均值i = 替以进行回归。 x l l + x 1 2 + 胛 西南交通大学硕士研究生学位论文第2 0 页 4 1 3 二维多项式插值 设被插值函数为f ( x ，y ) ，可以用二维多项式u ( x ，y ) 去逼近它，例如含有 x 、y 的二次项可以写成 u ( x ，y ) = a o + a l x + 订2 y + a 3 x 2 + a 4 砂+ a s y 2 当方次较低时，可由插值条件直接求待定系数a 0a 1 i 一，a ，以求出插值 函数u ( x ，y ) 。当方次较高时，处理的方法是，先令一个自变量为常数，则二 维多项式就变成只有一个自变量的多项式。例如令x = x ，上式可写成 u ( x l ，y ) = b o + b l y + b 2 y 2 就成为单变量插值问题，可用前面的插值方法求解。 多元样条回归的优点在于多元样条回归模型是用光滑对接的分段多项 式来拟合待逼近的函数，与数理统计中常用的线性( 非线性) 回归或多元回 归相比，多元样条回归更适合于处理随机产生的一般数据的拟合，而线性( 非 线性) 回归或多元回归则仅局限于正态分布的数据拟合。多元样条回归与非 参数回归如核回归相比，也有它的独到之处，因为它可以显式的确定回归函 数，而核回归却存在难以准确确定核函数的问题。 4 2 遗传算法 求解机会约束规划的传统方法是根据事先给定的置信水平，把机会约束 转化为各自的确定等价类，然后用传统的方法求解其等价的确定性模型。对 一些特殊情况，机会约束规划问题确实可以转化为确定性数学规划问题，但 对较复杂的机会约束规划问题，如目标函数是多峰的或者机会约束条件不能 转化为确定性条件的机会约束规划，利用传统的方法很难得到满意的