不确定优化问题的若干模型与算法研究(5)

山东大学博士学位论文

对信息如何进行科学地判断、分析、处理，促发了对科学决策系统的研究。此系统涉及的背景范畴体现了多维不确定性，其形态和结构各异。如上面提到的随机性，模糊性、粗糙型及多维不确定性，对于多维不确定性问题的决策系统，经典的优化方法通常是无能为力的，虽然已有的随机规划和模糊规划可以解决一部分随机决策系统和模糊决策系统的优化问题，但远未解决多维不确定性的决策系统优化问题的需求。因此建立完善统一的不确定环境下优化理论和方法既有深远理论意义又有广泛应用前景。不确定环境下的系统优化方法——不确定规划［１，６，１０，１７，３４］与不确定理论［２，３３］正是在这种背景下产生的。不确定规划针对不确定信息环境下的优化决策问题提供建模方法，形成了沟通不确定理论与优化应用的桥梁纽带。

系统优化决策中出现的不确定变量可分为四种基本类型：随机变量、模糊变量、粗糙变量、区间变量，含有不确定变量的目标函数或约束函数统称为不确定函数。概率论与数学规划结合，就产生了随机规划［３，４］：模糊数学与数学规划结合，就产生了模糊规划［５，６］：粗糙集与数学规划结合就产生了粗糙规划；区间变量与数学规划结合引发了区间规划［８１］。随机规划、模糊规划以及粗糙规划的交叉渗透则孕育了更一般的不确定规划。不确定优化问题计算的特点是大规模化与方法的综合化，基本算法是混合智能算法，其基本思路是将遗传算法、算法模拟以及神经网络有机地结合为一体，结合问题的数学性质结构特点，同时也可借鉴现有的数学规划算法，来解决大规模计算。

不确定规划、不确定理论目前已被应用到诸多方面，尤其在不确定决策分析、不确定信息管理等领域大显身手，例如：水库调度［１０］、生产过程［１７］、存储系统［２６，２８］、资金预算［７，２７］、网络优化［１０］、车辆调度［１６］、系统可靠’１生［３０］、作业排序［３２］、设备选址问题［３１］、ＤＥＡ分析［１８］等。这些课题的研究一方面反映了不确定规划在实际应用中行之有效，另一方面也衬托出不确定规划的研究背景，为不确定规划的研究提供了动力源泉。

２．本课题的研究背景

数学规划是运筹学的一个重要分支，它在社会进步、经济发展中体现了重要的实际应用价值，自从它产生之日起．就吸引了古今中外许多优秀的科学家致力于该领域的研究。

数学规划研究的主要内容为在一组等式或不等式约束条件下寻求一个或多个目标函数极值。２０世纪初期，出现了蕴含线性规划思想和方法的书籍和论文，

山东人学博士学位论文

如前苏联数学家康托罗维奇于１９３９年从工厂的经济活动出发，提出并研究了一类特殊的新型规划问题，而最一般的线性规划模型则是１９４７年由ＤａｎｔｚｉｇＧ．Ｂ提出的，从此开创了数学规划的研究领域。在过去的５０多年来，数学规划得到了很大的发展和广“泛应用，尤其是线性规划理论中单纯性算法的出现，对数学规划、运筹学以及其他应用学科的发展起了重大的推动作用。实际的应用反过来也促进了数学规划的发展，它的理论、算法、研究内容都在日新月异的发生着变化，如椭球算法、内点算法，非线性规划、凸规划、整数规划、动态规划、描述复杂系统的双层规划和交叉规划等分支都有了长足的发展和具体应用。

但是经典的数学规划模型建立在一个非常重要的假设基础上，即假定系数均为确定性数据。换言之，研究问题所处的环境为确定的，关于模型中参数的信息是完全确定的，模型中的目标函数和约束函数也是比较简单的，如线性或二次的或非线性的，通常还是可导的，模型中的决策变量之间也是独立的。但在许多情况下，用确定性的模型取描述复杂多变的现实优化问题会不可避免地存在诸多失真、偏差问题。

在现实世界中，随机现象是普遍存在的一类不确定现象，概率论就是一门研究随机现象的数量规律性的数学分支学科。人们在处理优化问题的过程中，很自然地将未来需求、资源变化等都认为是随机变量。当概率论与数学规划结合时，就产生了随机规划。随机规划在许多场合下比确定的数学规划模型更贴近实际情况。

随机规划研究涉及随机参数的优化决策问题，随机规划的最早文献可追溯到上世纪５０年代［１ｌ—１５］，随着随机规划研究的不断深入与日趋成熟，国内外有关方面的专著也不断出现，如中文的［６，８，１７］，英文的［２０一２５，２９］，随着互联网技术的快速发展，随机规划的专业网站［１８，１９］也面世了，为众多的研究爱好者提供了共享资源。关于随机规划研究的一系列相关文章及综述文章可见［１，２，９，１０，１６］，伴随着随机规划理论与方法的进展，随机规划在众多领域的应用也同步丌展起来。

３．本文的主要研究内容

伴随着线性和非线性规划的应用和逐步深入发展，随机规划得以建立，在ｉ垃十多年的发展历史中，结合各种应用，出现了多种模型。如Ｇ．Ｄａｎｔｚｉｇ以及Ｂｅａｌｅ将线性规划应用于航线班机最优次数的设计［３５，３６］，提出了有补偿的二阶段优化问题；Ａ．Ｃｈａｒｎｅｓ，Ｗ．Ｃｏｏｐｅｒ和他的同事们在［４０］中研究了炼油厂的生产和存

山东大学博士学位论文

储问题，提出了机会约束规划模型；在６０年代和７０年代，随机规划的模型和应用得到了较大的发展，如Ｍａｒｋｏｗｉｔｚ的均方差分析方法、Ｄｕｐａｃｏｖａ的惩罚模型、Ｎｅｕｍａｎｎ的效用模型，Ｇａｒｓｔｋａ与Ｚｉｅｍｂａ等人将其应用到经济均衡分析、金融风险测度、经济活动的最优评判等领域，得到了许多重要结论，对经济和社会的发展起了积极的推动作用。但是，众多的模型从建模机理、表现形式上存在某些重叠混杂之处，它们之间的联系也需进行补充完善，本文将在第一章中按照一个主脉线索来分类讨论已有的随机规划模型，并且对模型之间的联系（包括转化、等价、区别）进行补充完善。

机会约束模型是随机规划的一类基本模型，但它存在两方面的问题。其一它仅从定性的角度考察可行与不可行的概率，而没有涉及由随机性引发的数量问题（如下面提到的补偿模型）；其二关于它的数学性质，一般来讲只有当随机向量满足某些较强的条件或好的分布时，可行解集合才能保持凸性，［８，４４］中都有实例表明转化后的约束不再保持原约束集合的凸性（可见第二章中的对比实例），而这一点对于规划问题的求解尤其重要，这种非凸性会带来极大的计算困难。为了克服不利之处，研究者于１９７０年对该模型进行了改进与完善，在其基础上提出了合成机会约束模型［３８］。但迄今为止对该模型的研究工作非常少，可见到的仅有［４４，４５］，究其原因，应是计算中的复杂性。但该模型具有很好的性质，又能对风险研究、经济决策控制起到重要作用［４７］。因此本文在第二章中对合成机会约束模型进行了专门研究。首先综合给出了该模型定义的若干扩展变形；其次重点讨论该模型的性质，研究了当随机约束函数为决策变量的凸函数时，可行解集合的凸性、约束函数关于决策变量的连续性与可微性；在此理论基础上，随后假设模型中的随机变量服从有限的离散分布或连续分布，结合模型可行解集合的结构特点，分别给出了求解该模型的混合智能算法和复杂度为０（ｎ＇Ｌ）的多项式时间算法，并用大规模实例验证了算法的有效性。

二（多）阶段有补偿模型是随机规划的一类重要组成，在许多实际优化问题中得到广泛应用。本文在第三章中对该模型进行研究。因为该 …… 此处隐藏：2412字，全部文档内容请下载后查看。喜欢就下载吧 ……