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

山东大学

博士学位论文

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

姓名：戎晓霞

申请学位级别：博士

专业：运筹学与控制论

指导教师：刘家壮

20050101

原创性声明

本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人承担。

论文作者签名：疲鲤鏖日期：．型：！。！Ｐ

关于学位论文使用授权的声明

本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本学位论文。

（保密论文在解密后应遵守此规定）

导师签名：剑象生日期：舻』、３、砑论文作者签名：越睦霞

山东人学博士学位论文

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

戎晓霞

（山东大学数学与系统科学学院，济南，２５０１００）

中文摘要

当今世界处在一个信息时代，信息是人类认识世界和改造世界的知识源泉，人们接触到的各种各样的信息有时候是确定性的，更多的时候是不确定的。对信息如何进行科学地判断、分析、处理，促发了对科学决策系统的研究。此系统涉及的背景范畴体现了多维不确定性，其形态和结构各异，如随机性，模糊性、粗糙型及区间性等。对于多维不确定性问题的决策系统，经典的优化方法通常是无能为力的，虽然已有的随机规划和模糊规划町以解决一部分随机决策系统和模糊决策系统的优化问题，但远末解决多维不确定性的决策系统优化问题的需求。因此建立完善统一的不确定环境Ｆ优化理论和方法既有深远理论意义又有广泛应用前景。不确定环境下的系统优化方法——不确定规划与不确定理论正是在这种背景下产生的。不确定规划针对不确定信息环境下的优化决策问题提供建模方法，形成了沟通不确定理论与优化应用的桥梁纽带。不确定优化问题计算的特点是大规模化与方法的综合化，基本算法是混合智能算法，其基本思路是将遗传算法、算法模拟以及神经网络有机地结合为一体，结合问题的数学性质结构特点，同时也可借鉴现有的数学规划算法，来解决大规模计算。

本文的主要工作为：训论了随机规划的基本模型及内在联系；研究了两种随机规划的重要模型：合成机会约束模型与二（多）阶段有补偿模型的性质与算法；结合选址问题、约简问题研究ｒ区间优化和粗糙优化。

第一章绪论，首先叙述了本课题的研究背景、不确定优化问题的主要分类及现有研究工作：然后在第二节中按照一个主脉线索：建模机理来归纳整理了现有的随机规划基本模型，完善了随机模型关于可行解与最优值的定义，简单介绍为：在实际问题中经常采用的处理规划问题随机变量的方法有两种：一种是等待观察到随机变量的实现以后再作决策，引发了分布问题；另一种是在观察到随机变量实现前便做出决策。在后种情况下，义细分为如下模型：

首先，假设随机变量仅出现在约束集合中，有

（ａ）机会约束模型；（ｂ）惩罚模型：（ｃ）补偿模型，

山东大学博士学位论文

其次，假设随机变量仅出现在目标函数中，有

（ｄ）Ｅ一模型；（ｅ）方差模型；（ｆ）违背机会极小模型ｉ（ｈ）上界极小模型；（ｇ）期望效用最大模型。

在此基础上第三节讨论了基本模型之间的内在联系及相互转化，指出它们之间存在密切联系：

命题１．３．１二阶段有补偿模型、机会约束模型、Ｅ一模型、Ｐ．模型、效用模型都具有如下的统一形式：

ｒａｉｎ

』ＥＦ（ｘ，ｆ）

ｓ．ｔ．ＥＧ，（ｒ，｛）≥０，ｉ＝１，２，…ｍ

命题Ｌ３．３［４４１惩罚模型为一类特殊的有补偿模型

命题１．３．４效用模型是期望模型与Ｐ．模型的一般推广．

以上命题同时显示了随机规划与确定性规划存在紧密联系，但其等价的确定性规划往往具有复杂的表示，只是在少数特殊情形下可以转化为确定性情况，如命题１．３．２举例。第四节列出了本文的结构安排。

机会约束模型是随机规划的一类基本模型，但它存在两方面的问题。其一它仅从定性的角度考察可行与不可行的概率，而没有涉及由随机性引发的数量问题（如补偿模型）；其二关于它的数学性质，一般来讲只有当随机向量满足某些较强的条件或好的分布时，可行解集合才能保持凸性，【８，４４】中都有实例表明转化后的约束不再保持原约束集合的凸性（可见第二章中的对比实例），而这一点对于规划问题的求解尤其重要，这种非凸性会带来极大的计算困难。为了克服不利之处，研究者于１９７０年对该模型进行了改进与完善，在其基础上提出了合成机会约束模型［３８］。但迄今为止对该模型的研究工作非常少，可见到的仅有［４４，４５］，究其原因，应是计算中的复杂性。但该模型具有很好的性质，又能对风险研究、经济决策控制起到重要作用［４７］。因此本文在第二章中对合成机会约束模型（简记为ｒｃｃ（口））进行了重点研究。

第一节给出了合成机会约束定义的若干扩展变形：

在定义２．１．３中，同时考虑资源的剩余情况与短缺情况，定义资源的剩余量为：ｑｊ（ｘ，ｃｏ）＝ｍａｘ｛Ｏ，仇），则平均剩余为Ｅｒｌ？，且满足Ｅ，７７＋Ｅ玎？＝Ｅｈｌ。独立的合成机会约束为：Ｅ，７ｉ兰ａ。Ｅｌ，７。ｌ，ｆ＿ｌ，２，…，ｍ，相应的联合合成机会约束为：Ｅ（ｒ］－，ｉ＝１…ｍ）≤口．该定义避免了对依赖矾（ｘ，功）分布的屈取值这一困难。在定义２．１．４【７】中，引入ｙ∈［ｏ，ｏｏ）代表决策者对条件期望ＥＥ（ｚ／一）ｈ＜Ｏｌ短缺的最大承

山东大学博士学位论文

受值，定义合成机会约束为：Ｅｖｉ≤ｙＪＤ（矾＜０），本文解释了其合理性，相应可行解集合为Ｘ４（ｙ）≥（ｘ∈Ｒ”，￡碍ｉ≤７ ￡｛玎ｍ。

之后第二节讨论了该模型的性质，给出了当随机约束函数为决策变量的凸函数时，可行解集合的凸性、约束函数的连续性与可微性等性质，推广了［４４】中关于线性函数的结论，主要结果为：

定理２．２．３若随机规划ｒａｉｎ｛ｆ（ｘ１：ｇ㈦础）≥０，Ｘ∈Ｄ）中，Ｄ为一确定的有限闭域，ｇ（ｘ．国）是ｘ的凸函数，且每一个随机变量满足Ｅ（∞，）＜０（３，则有：

虿（ｘ）＝Ｅ［ｇ（ｘ，∞）一］为有限的、非负的凸函数，且满足Ｌｉｐｓｃｈｉｔｓ连续。荇（ｄＣ∞），ｂ（∞））服从有限的离散分布，则喜（ｚ）为分片凸函数；若（“（∞），ｂ（ｏＤ）服从连续分布，则ｇ（ｘ）为连续可微的凸函数，从而可行解集ｘ（ｐ）＝｛ｘ∈Ｒ”：ｇ（ｘ）≤∥｝为凸集。特别地当约束函数为ｇ（ｘ，∞）＝∑ａ，（甜扛；一６（甜）时，季（ｘ）的偏导函数为罢盟＝研卫２以，ｘ，ｓｇｎ（ｇ（ｘ））］，进一步ｌｉｌ。塑羔堕掣：Ⅱ（∑巳（叻谚）一］。，＝ｆ

口 …／Ｌ３＝１

该定理为后面两节的算法设计做了理论准备，接下来定理２．２．５讨论了该模型的Ｌａｇｒａｎｇｅ问题，指出上（五）形式上等价于（单纯的）补偿模型或惩罚模型。『４５．４７１在对金融风险研究中，通过对风险值的评价方法转化得到了补偿模型与合成机会约 …… 此处隐藏：2056字，全部文档内容请下载后查看。喜欢就下载吧 ……