山东大学
博士学位论文
不确定优化问题的若干模型与算法研究
姓名：戎晓霞
申请学位级别：博士
专业：运筹学与控制论
指导教师：刘家壮
20050101原创性声明
本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进
行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何
其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡
献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人
承担。
论文作者签名：疲鲤鏖日期：．型：！。！Ｐ
关于学位论文使用授权的声明
本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保
留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅
和借阅；本人授权山东大学可以将本学位论文的全部或部分内容编入有关
数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本
学位论文。
（保密论文在解密后应遵守此规定）
论文作者签名：越睦霞导师签名：剑象生日
期：舻』、３、砑山东人学博士学位论文
不确定优化问题的若干模型与算法研究
戎晓霞
（山东大学数学与系统科学学院，济南，２５０１００）
中文摘要
当今世界处在一个信息时代，信息是人类认识世界和改造世界的知识源泉，
人们接触到的各种各样的信息有时候是确定性的，更多的时候是不确定的。对信
息如何进行科学地判断、分析、处理，促发了对科学决策系统的研究。此系统涉
及的背景范畴体现了多维不确定性，其形态和结构各异，如随机性，模糊性、粗
糙型及区间性等。对于多维不确定性问题的决策系统，经典的优化方法通常是无
能为力的，虽然已有的随机规划和模糊规划町以解决一部分随机决策系统和模糊
决策系统的优化问题，但远末解决多维不确定性的决策系统优化问题的需求。因
此建立完善统一的不确定环境Ｆ优化理论和方法既有深远理论意义又有广泛应用前景。不确定环境下的系统优化方法——不确定规划与不确定理论正是在这种
背景下产生的。不确定规划针对不确定信息环境下的优化决策问题提供建模方
法，形成了沟通不确定理论与优化应用的桥梁纽带。不确定优化问题计算的特点
是大规模化与方法的综合化，基本算法是混合智能算法，其基本思路是将遗传算
法、算法模拟以及神经网络有机地结合为一体，结合问题的数学性质结构特点，
同时也可借鉴现有的数学规划算法，来解决大规模计算。
本文的主要工作为：训论了随机规划的基本模型及内在联系；研究了两种随
机规划的重要模型：合成机会约束模型与二（多）阶段有补偿模型的性质与算法；
结合选址问题、约简问题研究ｒ区间优化和粗糙优化。
第一章绪论，首先叙述了本课题的研究背景、不确定优化问题的主要分类及
现有研究工作：然后在第二节中按照一个主脉线索：建模机理来归纳整理了现有
的随机规划基本模型，完善了随机模型关于可行解与最优值的定义，简单介绍为：
在实际问题中经常采用的处理规划问题随机变量的方法有两种：一种是等待观察
到随机变量的实现以后再作决策，引发了分布问题；另一种是在观察到随机变量
实现前便做出决策。在后种情况下，义细分为如下模型：
首先，假设随机变量仅出现在约束集合中，有
（ａ）机会约束模型；（ｂ）惩罚模型：
（ｃ）补偿模型，山东大学博士学位论文
其次，假设随机变量仅出现在目标函数中，有
（ｄ）Ｅ一模型；（ｅ）方差模型；（ｆ）违背机会极小模型ｉ（ｈ）上界极小模型；
（ｇ）期望效用最大模型。
在此基础上第三节讨论了基本模型之间的内在联系及相互转化，指出它们之
间存在密切联系：
命题１．３．１二阶段有补偿模型、机会约束模型、Ｅ一模型、Ｐ．模型、效用模型
都具有如下的统一形式：ｒａｉｎＥＦ（ｘ，ｆ）
ｓ．ｔ．ＥＧ，（ｒ，｛）≥０，ｉ＝１，２，…ｍ
命题Ｌ３．３［４４１惩罚模型为一类特殊的有补偿模型
命题１．３．４效用模型是期望模型与Ｐ．模型的一般推广．
以上命题同时显示了随机规划与确定性规划存在紧密联系，但其等价的确定
性规划往往具有复杂的表示，只是在少数特殊情形下可以转化为确定性情况，如
命题１．３．２举例。第四节列出了本文的结构安排。
机会约束模型是随机规划的一类基本模型，但它存在两方面的问题。其一它
仅从定性的角度考察可行与不可行的概率，而没有涉及由随机性引发的数量问题
（如补偿模型）；其二关于它的数学性质，一般来讲只有当随机向量满足某些较
强的条件或好的分布时，可行解集合才能保持凸性，【８，４４】中都有实例表明转化
后的约束不再保持原约束集合的凸性（可见第二章中的对比实例），而这一点对
于规划问题的求解尤其重要，这种非凸性会带来极大的计算困难。为了克服不利
之处，研究者于１９７０年对该模型进行了改进与完善，在其基础上提出了合成机
会约束模型［３８］。但迄今为止对该模型的研究工作非常少，可见到的仅有［４４，４５］，
究其原因，应是计算中的复杂性。但该模型具有很好的性质，又能对风险研究、
经济决策控制起到重要作用［４７］。因此本文在第二章中对合成机会约束模型（简
记为ｒｃｃ（口））进行了重点研究。
第一节给出了合成机会约束定义的若干扩展变形：
在定义２．１．３中，同时考虑资源的剩余情况与短缺情况，定义资源的剩余量为：ｑｊ（ｘ，ｃｏ）＝ｍａｘ｛Ｏ，仇），则平均剩余为Ｅｒｌ？，且满足Ｅ，７７＋Ｅ玎？＝Ｅｈｌ。独立
的合成机会约束为：Ｅ，７ｉ兰ａ。Ｅｌ，７。ｌ，ｆ＿ｌ，２，…，ｍ，相应的联合合成机会约束为：
Ｅ（ｒ］－，ｉ＝１…ｍ）≤口．该定义避免了对依赖矾（ｘ，功）分布的屈取值这一困难。在定
义２．１．４【７】中，引入ｙ∈［ｏ，ｏｏ）代表决策者对条件期望ＥＥ（ｚ／一）ｈ＜Ｏｌ短缺的最大承山东大学博士学位论文
受值，定义合成机会约束为：Ｅｖｉ≤ｙＪＤ（矾＜０），本文解释了其合理性，相应可行解集合为Ｘ４（ｙ）≥（ｘ∈Ｒ”，￡碍ｉ≤７·￡｛玎ｍ。
之后第二节讨论了该模型的性质，给出了当随机约束函数为决策变量的凸函
数时，可行解集合的凸性、约束函数的连续性与可微性等性质，推广了［４４】中关
于线性函数的结论，主要结果为：
定理２．２．３若随机规划ｒａｉｎ｛ｆ（ｘ１：ｇ㈦础）≥０，Ｘ∈Ｄ）中，Ｄ为一确定的有限
闭域，ｇ（ｘ．国）是ｘ的凸函数，且每一个随机变量满足Ｅ（∞，）＜０（３，则有：
虿（ｘ）＝Ｅ［ｇ（ｘ，∞）一］为有限的、非负的凸函数，且满足Ｌｉｐｓｃｈｉｔｓ连续。荇
（ｄＣ∞），ｂ（∞））服从有限的离散分布，则喜（ｚ）为分片凸函数；若（“（∞），ｂ（ｏＤ）服从连
续分布，则ｇ（ｘ）为连续可微的凸函数，从而可行解集ｘ（ｐ）＝｛ｘ∈Ｒ”：ｇ（ｘ）≤∥｝
为凸集。特别地当约束函数为ｇ（ｘ，∞）＝∑ａ，（甜扛；一６（甜）时，季（ｘ）的偏导函数为，＝ｆ罢盟＝研卫２以，ｘ，ｓｇｎ（ｇ（ｘ））］，进一步ｌｉｌ。塑羔堕掣：Ⅱ（∑巳（叻谚）一］。
口·…／Ｌ３＝１该定理为后面两节的算法设计做了理论准备，接下来定理２．２．５讨论了该模
型的Ｌａｇｒａｎｇｅ问题，指出上（五）形式上等价于（单纯的）补偿模型或惩罚模型。
『４５．４７１在对金融风险研究中，通过对风险值的评价方法转化得到了补偿模型与合
成机会约束模型的等价性，与我们从Ｌａｇｒａｎｇｅ问题出发分析结果一致。当补偿
系数不易确定时，合成机会约束横型能更为精确地描述不确定模型，并且借助其
良好的性质论，显示了利用Ｌａｇｒａｎｇｅ对偶问题设计（１ｃｃ（∥））计算方法的可能性，并且也为补偿模型的计算提供了一种新的崽路。
随后的第三节与第四节中，分别假设模型中的随机变量服从有限的离散分布
或连续分布，来建立模型的优化计算方法。在第三节中，基于可行解集合的结构
特点（可见定理２．３．１、定理２．３．２），设计了求解该模型的混合智能算法２．３，关
于随机生成阅题的对比实例验证了算法的有效性：在第四节中，根据约束集合与
函数的性质，利用带分解的内点算法，给出了多项式时间算法２．４，具有较低的
复杂度为Ｏ（ｎ３Ｌ）。
第三章对一类随机规划基本模型：二（多）阶段有补偿模型（简记为２ｓ—ＳＰ）
进行两方面的研究。在第一节中，本文通过对比该模型与双（多）层规划的建模
思想，发现二者存在极大类似之处，具有形式上的等价性，命题３．１．１与３．１．２
指出：２Ｓ—ＳＰ为一类随梳双层规划，进一步地２Ｓ—ＳＰ等价于下层只含一个子系统
的随机值型双层规划。山东大学博士学位论文
有补偿问题为ＮＰ，Ｈａｒｄ问题，现有的研究成果多局限于讨论解的计算方法与
实现方面［３，４，８］，双层规划近二十年来已在基本理论、最优性、算法等方面得到
较为全面深入的研究［７１．７４］，因此上述命题告诉我们可以借鉴双层规划来研究有补偿问题。
在定理３．１．４、定理３．１．５中讨论了２Ｓ．ＳＬＰ、２Ｓ，ＳＮＬＰ最优解的存在情况。
接下来，我们讨论二阶段有补偿优化模型的对偶。鉴于随机规划模型的复杂
性与多样性，在现有的研究资料中很少专门提到它的对偶理论，在少量文献中，
如［４４，９９］只是把随机规划转化为确定性等价形式后，利用确定性规划的对偶理论
给出它的对偶形式，［７０】利用转化后的确定性形式的对偶来设计求解大规模随机优化问题的聚合算法。因此，在第二节中我们对这一重要理论进行研究。
对于ｆ３．２．１）描述的关于凸函数的二阶段有补偿问题，根据扰动理论，建立其
对偶问题：
ｓｕｐＤ＝ｓｕｐｉｎｆＬ（ｘ，Ｙ）．，ｙ
其中三（‘ｙ）＝ｉ肫ｎｕｆ｛ｕＴｙ＋Ｆ（ｘ，“））＝工－（丘ｙ）＋【上２（ｃｏ，工１，ｘ２（∞））ｐ（ｄ∞）·
特别地，当所有／为ｘ的线性函数时，得到问题（３．２４）描述的２Ｓ—ＳＬＰ的对偶
规划为：
ｍａｘｖｂ＋Ｉ７ｒ（ｃｏ）Ｈ（ｃｏ）ｐ（ｄｃｏ）
ｃ。一ｖＡ—ｐ（国）丁（∞）Ｐ（豳）≥０
ｃ２（０９）一丌（∞）∥（珊）２０（３．２．５）ｖ，Ｊｒ（ｃｏ）≥０
不难看出，如果在原问题（３．２．４）及其对偶规划（３．２．５）中去掉约束及目标中的
随机函数，即可得到传统的确定性线性优化的原一对偶表示，并且与文献［７４］中
关于非减值型双层规划的对偶形式也是一致的。（３．２．５）把线性规划的对偶推广至
二阶段的随机线性规划，完善了随机规划的理论，也为有补偿模型的算法设计提
供了新的源泉。
第四章从应用角度出发，研究了其它两类不确定性优化问题。第一个为运筹
学研究的重点问题：选址问题。在目前已有的研究成果中，只有很少一部分讨论
了不确定环境下的优化问题，如应用模糊评判方法来进行最优选址［７９】；需求量
为随机变量时的优化选址等【８０】。但前者关于模糊变量隶属函数的选取含有较大
Ｖ