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

山东大学

博士学位论文

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

姓名：戎晓霞

申请学位级别：博士

专业：运筹学与控制论

指导教师：刘家壮

20050101

原创性声明

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

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

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

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

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

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

山东人学博士学位论文

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

戎晓霞

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

中文摘要

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

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

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

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

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

山东大学博士学位论文

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

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

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

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

ｒａｉｎ

』ＥＦ（ｘ，ｆ）

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

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

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

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

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

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

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

山东大学博士学位论文

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

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

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

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

口 …／Ｌ３＝１

该定理为后面两节的算法设计做了理论准备，接下来定理２．２．５讨论了该模型的Ｌａｇｒａｎｇｅ问题，指出上（五）形式上等价于（单纯的）补偿模型或惩罚模型。『４５．４７１在对金融风险研究中，通过对风险值的评价方法转化得到了补偿模型与合成机会约束模型的等价性，与我们从Ｌａｇｒａｎｇｅ问题出发分析结果一致。当补偿系数不易确定时，合成机会约束横型能更为精确地描述不确定模型，并且借助其良好的性质论，显示了利用Ｌａｇｒａｎｇｅ对偶问题设计（１ｃｃ（∥））计算方法的可能性，并且也为补偿模型的计算提供了一种新的崽路。

随后的第三节与第四节中，分别假设模型中的随机变量服从有限的离散分布或连续分布，来建立模型的优化计算方法。在第三节中，基于可行解集合的结构特点（可见定理２．３．１、定理２．３．２），设计了求解该模型的混合智能算法２．３，关于随机生成阅题的对比实例验证了算法的有效性：在第四节中，根据约束集合与函数的性质，利用带分解的内点算法，给出了多项式时间算法２．４，具有较低的复杂度为Ｏ（ｎ３Ｌ）。

第三章对一类随机规划基本模型：二（多）阶段有补偿模型（简记为２ｓ—ＳＰ）进行两方面的研究。在第一节中，本文通过对比该模型与双（多）层规划的建模思想，发现二者存在极大类似之处，具有形式上的等价性，命题３．１．１与３．１．２指出：２Ｓ—ＳＰ为一类随梳双层规划，进一步地２Ｓ—ＳＰ等价于下层只含一个子系统的随机值型双层规划。

山东大学博士学位论文

有补偿问题为ＮＰ，Ｈａｒｄ问题，现有的研究成果多局限于讨论解的计算方法与实现方面［３，４，８］，双层规划近二十年来已在基本理论、最优性、算法等方面得到较为全面深入的研究［７１．７４］，因此上述命题告诉我们可以借鉴双层规划来研究有补偿问题。

在定理３．１．４、定理３．１．５中讨论了２Ｓ．ＳＬＰ、２Ｓ，ＳＮＬＰ最优解的存在情况。接下来，我们讨论二阶段有补偿优化模型的对偶。鉴于随机规划模型的复杂性与多样性，在现有的研究资料中很少专门提到它的对偶理论，在少量文献中，如［４４，９９］只是把随机规划转化为确定性等价形式后，利用确定性规划的对偶理论给出它的对偶形式，［７０】利用转化后的确定性形式的对偶来设计求解大规模随机优化问题的聚合算法。因此，在第二节中我们对这一重要理论进行研究。

对于ｆ３．２．１）描述的关于凸函数的二阶段有补偿问题，根据扰动理论，建立其对偶问题：

ｓｕｐＤ＝ｓｕｐｉｎｆＬ（ｘ，Ｙ）．

。

，ｙ

其中三（‘ｙ）＝ｉ肫ｎｕｆ｛ｕＴｙ＋Ｆ（ｘ，“））＝工－（丘ｙ）＋【上２（ｃｏ，工１，ｘ２（∞））ｐ（ｄ∞）

特别地，当所有／为ｘ的线性函数时，得到问题（３．２４）描述的２Ｓ—ＳＬＰ的对偶规划为：

ｍａｘｖｂ＋Ｉ７ｒ（ｃｏ）Ｈ（ｃｏ）ｐ（ｄｃｏ）

ｃ。一ｖＡ—ｐ（国）丁（∞）Ｐ（豳）≥０

ｃ２（０９）一丌（∞）∥（珊）２０

ｖ，Ｊｒ（ｃｏ）≥０（３．２．５）

不难看出，如果在原问题（３．２．４）及其对偶规划（３．２．５）中去掉约束及目标中的随机函数，即可得到传统的确定性线性优化的原一对偶表示，并且与文献［７４］中关于非减值型双层规划的对偶形式也是一致的。（３．２．５）把线性规划的对偶推广至二阶段的随机线性规划，完善了随机规划的理论，也为有补偿模型的算法设计提供了新的源泉。

第四章从应用角度出发，研究了其它两类不确定性优化问题。第一个为运筹学研究的重点问题：选址问题。在目前已有的研究成果中，只有很少一部分讨论了不确定环境下的优化问题，如应用模糊评判方法来进行最优选址［７９】；需求量为随机变量时的优化选址等【８０】。但前者关于模糊变量隶属函数的选取含有较大Ｖ

山东大学博十学位论文

的人为因素，后者则假设随机变量的分布函数已知。在实际决策时若依据经验或专家给出，则不同的专家往往给出不同的分布函数和隶属函数，从而使问题更加不确定化。因而，最能真实恰当地描述这一问题的当数区间变量。本文在这一假设下，首先介绍了区间规划，然后根据不同的决策目标，建立了选址的若干区间规划模型，包括：乐观模型、悲观模型、期望模型、不确定度模型、损失模型、鲁棒模型、与多目标优化模型。

第二个问题为粗集的决策表属性约简问题。作为信息系统中知识发现，数据挖掘的重要内容，约简近年来已成为计算机科学的热点问题之一，其算法越来越得到人们的重视。目前已有多种属性约简算法［８６—９１１，有从代数角度的基于区分矩阵的最小约简方法，还有从信息角度出发的基于信息熵的约简算法。因为求属陛集合的最小约简是ＮＰ—Ｈａｒｄ问题，在大规模问题与计算中，人们还常采用启发式智能算法，如遗传算法、并行协同算法等进行研究。４．２节中我们依据属性约简与逻辑运算的关系，给出一种新的计算最小约简的整数规划算法４．２，该算法能有效地避免大量逻辑运算，并且当系统的属性及论域处于动态变化的环境时，只需应用该算法做某些局部调整即可求得新决策表的最小约简。对上述两类问题和算法均进行了实例分析。

第五章为本文的总结，包括论文主要工作、创新点与相关问题展望。

本论文的创新点町以归纳为以下几方面：

ｌ归纳整理了现有的随机规划基本模型，阐明了随机模型中可行解与最优值的定义：完善了基本模型之间的内在联系及等价转化，为随机决策问题建模提供了方法依据。

２在合成机会约束模型中，把随机约束函数为线性函数的性质推广至凸函数情

形，得到了约束函数的连续性与可微性、解的存在性等性质，并利用其性质，设计了求解含离散随机变量与连续随机变量的该模型的两种算法。

３应用双层规划来研究二阶段有补偿模型，讨论了该模型的双层规划等价形式

以及最优解的存在性，并给出了该模型关于随机凸函数、线性函数的对偶问题表示，是一个理论与方法上的创新。

４利用不确定优化的区间规划和粗糙优化理论，设计了有效的算法来解决两类

重要的实际问题：选址问题和约简问题，是应用与方法上的一个创新。

关键词：随机规划合成机会约束模型二阶段有补偿模型区间规划粗糙优化Ｖ

山东大学博士学位论文

ＲＥＳＲＡＲＣＨＯＮＭＯＤＥＬＡＮＤＡＬＧＯＲｌＴＨＭＡＢＯＵＴＵＮＣＥＲＴＡＮｌＮ

ＯＰＴｌＭｌＺＡＴｌ０ＮＰＲＯＢＬＥＭＳ

ＲＯＮＧＸｉａｏ－ｘｉａ

（ＳｃｈｏｏｌｏｆＭａｔｈｅｍａｔｉｃｓａｎｄＳｙｓｔｅｍＳｃｉｅｎｃｅ，ＳｈａｎｄｏｎｇＵｎｉｖｅｒｓｉｔｙ，Ｊｉｎａｎ２５０１００）

Ａｂｓｔｒａｃｔ

ＴｏｄａｙｗｅａｒｅｆａｃｉｎｇａｎｉｎｆｏｒｍａｔｉｏｎｔｉｍｅａｎｄｔｈｅｉｎｆｏｒｍａｔｉｏｎｉｓｋｎｏｗｌｅｄｇｅｈｅａｄｓｐｒｉｎｇｆｒｏｍｗｈｉｃｈｐｅｏｐｌｅｋｎｏｗａｎｄｒｅｂｕｉｌｄｗｏｒｌｄＡｌｌｋｉｎｄｓｏｆｉｎｆｏｒｍａｔｉｏｎｍａｙｂｅｃｅｒｔａｉｎｂｕｔｍｏｒｅｉＳｕｎｃｅｒｔａｉｎ．Ｉｔ

ｔｏｉｎｄｕｃｅｓｔｈｅｒｅｓｅａｒｃｈａｂｏｕｔｓｃｉｅｎｔｉｆｉｃｄｅｃｉｓｉｏｎ—ｍａｋｉｎｇｓｙｓｔｅｍｔｈａｔｈｏｗｊｕｄｇｅ、ａｎａｌｙｓｉｓａｎｄｄｅａｌｗｉｔｈｉｎｆｏｒｍａｔｉｏｎ。Ｔｈｅ

ｂａｃｋｇｒｏｕｎｄｉｎｖｏｌｖｅｄｂｙｔｈｉｓｓｙｓｔｅｍｓｈｏｗｓｕｎｃｅｒｔａｉｎｏｆｍｕｌｔｉ—ｄｉｍｅｎｓｉｏｎ，ｗｈｉｃｈｉｓｄｉｆｆｅｒｅｎｔｓｕｃｈｉＳｒａｎｄｏｍｎｅｓｓ，ｆｕｚｚｉｎｅｓｓ，ｒｏｕｇｈｎｅｓｓ，ｉｎｔｅｒｖａｌｎｅｓｓ，ｅｔｃ．Ｔｈｅｃｌａｓｓｉｃａｌｍｅｔｈｏｄｓｉｓｎｏｔｃａｐａｂｌｅｔｏ

ｓｔｏｃｈａｓｔｉｃｏｒｔｈｅｍｕｌｔｉ－ｄｉｍｅｎｓｉｏｎｕｎｃｅｒｔａｉｎｓｙｓｔｅｍ，ａｌｔｈｏｕｇｈｓｏｍｅＣａｌｌｆｕｚｚｙｐｒｏｇｒａｍｍｉｎｇｄｅａｌｓｏｍｅｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍｓ．ｗｈｉｃｈｉｓｆａｒｆｒｏｍｔｈｅｇｏａｌｏｆｓｏｌｖｉｎｇｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍｓａｂｏｕｔｍｕｌｔｉ—ｄｉｍｅｎｓｉｏｎｕｎｃｅｒｔａｉｎｓｙｓｔｅｍ．Ｓｏｉｔｈａｓｓｉｇｎｉｆｉｃａｔｅａｐｐｌｉｃａｔｉｏｎｆｏｒｅｇｒｏｕｎｄｔｏｅｓｔａｂｌｉｓｈａｎｄｃｏｎｓｕｍｍａｔｅｏｐｔｉｍｉｚａｔｉｏｎｔｈｅｏｒｙｗｉｔｈｍｅｔｈｏｄｉｎｕｎｃｅｒｔａｉｎｅｎｖｉｒｏｎｍｅｎｔ．Ｔｈｅｓｙｓｔｅｍｉｃｏｐｔｉｍｉｚａｔｉｏｎｍｅｔｈｏｄｉｎｕｎｃｅｒｔａｉｎｅｎｖｉｒｏｎｍｅｎｔｃｏｍｅｓｉｎｔｏｂｅｉｎｇｕｎｄｅｒｔｈｅｂａｃｋｇｒｏｕｎｄａｂｏｖｅ．Ａｓｔｈｅｂｒｉｄｇｅｃｏｎｔａｃｔｉｎｇｕｎｃｅｒｔａｉｎｔｈｅｏｒｙａｎｄａｐｐｌｉｃａｔｉｏｎ，ｕｎｃｅｒｔａｉｎｐｒｏｇｒａｍｍｉｎｇａｆｆｏｒｄｓｔｈｅｗａｙｏｆｍｏｄｅｌｉｎｇｔｏｄｅｃｉｓｉｏｎ—ｍａｋｉｎｇｐｒｏｂｌｅｍｓＴｈｅｍａｉｎｃｈａｒａｃｔｅｒｉｓｔｉｃｏｆｕｎｃｅｒｔａｉｎｐｒｏｂｌｅｍｓｉｓｔｈｅｍｅｔｈｏｄｃｏｌｌｉｇａｔｉｏｎａｎｄｌａｒｇｅ－ｓｃａｌｅ．Ｔｈｅｂａｓｉｃａｌｇｏｒｉｔｈｍｉｓｍｉｘｅｄｉｎｔｅｌｌｉｇｅｎｃｅａｌｇｏｒｉｔｈｍ，ｗｈｉｃｈ

ｓｉｍｕｌａｔｉｏｎｃｏｍｂｉｎｅｓｏｎｔｈｅｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ，ａｌｇｏｒｉｔｈｍａｎｄｎｅｕｒａｌｎｅｔｗｏｒｋ，ｂａｓｉｎｇ

ｔｏｔｈｅｍａｔｈｅｍａｔｉｃｆｌａｍｅｃｈａｒａｃｔｅｒ，ｏｒｕｓｉｎｇｅｘｉｓｔｉｎｇｐｒｏｇｒａｍｍｉｎｇａｌｇｏｒｉｔｈｍ

Ｔｈｅｍａｉｎｗｏｒｋｏｆｔｈｉｓｓｏｌｖｅｌａｒｇｅ—ｓｃａｌｅｐｒｏｂｌｅｍｓ．ｏｆｓｔｏｃｈａｓｔｉｃａｒｔｉｃｌｅｉｓ：ｄｉｓｃｕｓｓｉｎｇｔｈｅｂａｓｉｃｍｏｄｅｌｓ

ｐｒｏｇｒａｍｍｉｎｇａｎｄｔｈｅｒｅｌａｔｉｏｎｓｂｅｔｗｅｅｎｔｈｅｍ；ｒｅｓｅａｒｃｈｉｎｇｔｈｅｃｈａｒａｃｔｅｒａｎｄ

ａｂｏｕｔｉｎｔｅｇｒａｔｅｄｃｈａｎｃｅｃｏｎｓｔｒａｉｎｔｓａｌｇｏｒｉｔｈｍｍｏｄｅｌ（ＩＣＣ（∥））ａｎｄ

ａｎｄｔｗｏ—ｓｔａｇｅｍｏｄｅｌｗｉｔｈｒｅｃｏｕｒｓｅ（２Ｓ．ＳＰ）；ｓｔｕｄｙｉｎｇｉｎｔｅｒｖａｌｏｐｔｉｍｉｚａｔｉｏｎｒｏｕｇｈｏｐｔｉｍｉｚａｔｉｏｎｃｏｍｂｉｎｅｄ

ｗｉｔｈｌｏｃａｔｉｏｎｐｒｏｂｌｅｍａｎｄｒｅｄｕｃｔｉｏｎｐｒｏｂｌｅｍｓ．

Ｉｎｔ１１ｅｆｉｒｓｔｃｈａｐｔｅｒ，ｗｅｒｅｖｉｅｗｔｈｅｂａｃｋｇｒｏｕｎｄ，ｃｌａｓｓｏｆｕｎｃｅｒｔａｉｎｐｒｏｇｒａｍｓａｎｄｔｈｅｅｘｉｓｔｉｎｇｗｏｒｋ．Ｓｕｂｓｅｑｕｅｎｔｌｙｉｎ§１．２ｔｈｅｂａｓｉｃｍｏｄｅｌｓｏｆｓｔｏｃｈａｓｔｉｃｐｒｏｇｒａｍｍｉｎｇａｒｅｉｎｄｕｃｅｄａｃｃｏｒｄｉｎｇｔｏｔｈｅｍｏｄｅｌｉｎｇｍｅｃｈａｎｉｓｍａｎｄｔｈｅｒｅｌａｔｉｏｎｓｂｅｔｗｅｅｎｔｈｅｍａｒｅＶ

山尔大学博士学位论文

ｃｏｎｓｕｍｍａｔｅｄ，ｗｈｉｃｈｉｓｇｉｖｅｎａｓ：

Ｗｈｅｎｍａｋｉｎｇｄｅｃｉｓｉｏｎａｆｔｅｒｔｈｅｒｅｌａｔｉｏｎｏｆｒａｎｄｏｍｖａｒｉａｂｌｅ，ｄｉｓｔｒｉｂｕｔｉｎｇｐｒｏｂｌｅｍｉｓｐｒｏｄｕｃｅｄ；ｏｔｈｅｒｗｉｓｅｔｈｅｓｔａｔｅｃａｎｂｅｐａｒｔｉｔｉｏｎａＳ：

Ｆｉｒｓｔｌｙ，ａｓｓｕｍｉｎｇｒａｎｄｏｍｖａｒｉａｂｌｅｉｓｉｎｖｏｌｖｅｄｏｎｌｙｉｎｃｏｎｓｔｒａｉｎｓｓｅｔ，ｔｈｅｒｅａｒｅ：（ａ）ＣｈａｎｃｅＣｏｎｓｔｒａｉｎｓｍｏｄｅｌ；（ｂ）Ｐｕｂｌｉｓｈｉｎｇｍｏｄｅｌ；（ｃ）Ｒｅｃｏｕｒｓｅｍｏｄｅｌ．

Ｓｅｃｏｎｄｌｙ，ａｓｓｕｍｉｎｇｒａｎｄｏｍｖａｒｉａｂｌｅｉｓｉｎｖｏｌｖｅｄｏｎｌｙｉｎｇｏａｌｆｕｎｃｔｉｏｎ，ｔｈｅｒｅａｒｅ：（ｄ）Ｅ—ｍｏｄｅｌ；（ｅ）Ｖａｒｉａｎｃｅｍｏｄｅｌ；（ｆ）Ｍｉｎｉｍｉｚｅ

ｍｏｄｅｌ；（ｈ）Ｍｉｎｉｍｉｚｅ

ｍｏｄｅｌ．ｔｈｅｓｕｐｒｅｍｅｂｏｕｎｄｔｈｅｐｒｏｂａｂｉｌｉｔｙｏｆｂａｎｋｒｕｐｔｃｙｔｈｅｅｘｐｅｃｔｅｄｕｔｉｌｉｔｙｍｏｄｅｌ；（曲Ｍａｘｉｍｉｚｅ

ＰｒｏｐｏｓｉｔｉｏｎＩ．３．１２Ｓ—ＳＰｍｏｄｅｌ、ＣｈａｎｃｅＣｏｎｓｔｒａｉｎｓｍｏｄｅｌ、Ｅ—ｍｏｄｅｌ、ｐ－ｍｏｄｅｌａｎｄＵｔｉｌｉｔｙｍｏｄｅｌｈａｖｅｔｈｅｕｎｉｆｉｅｄｆｏｒｍ

ｒａｉｎａｓｆｏｌｌｏｗｉｎｇ：ＥＦ（ｘ，｛）

ｓ．ｔ．ＥＧ．（ｘ，ｆ）≥０，ｉ＝１，２， ｍ

Ｐｒｏｐｏｓｉｔｉｏｎ１．３．３［４４］ＰｕｂｌｉｓｈｉｎｇｍｏｄｅｌｉｓａｓｐｅｃｉａｌＲｅｃｏｕｒｓｅｍｏｄｅｌ．

Ｐｒｏｐｏｓｉｔｉｏｎ１．３．４ＵｔｉｌｉｔｙｍｏｄｅｌｉｓｔｈｅｅｘｔｅｎｄｉｎｇｏｆＥ—ｍｏｄｅｌａｎｄｐ－ｍｏｄｅｌ．

Ｐｒｏｐｏｓｉｔｉｏｎｓａｂｏｖｅｓｈｏｗｔｈａｔｓｔｏｃｈａｓｔｉｃｐｒｏｇｒａｍｍｉｎｇｉｓｒｅｌｅｖａｎｔ

ｓｔａｔｅｔｏｃｅｒｔａｉｎｃａｎｐｒｏｇｒａｍｍｉｎｇ，ｂｕｔｔｈｅｅｑｕｉｖａｌｅｎｃｅｏｆｃｅｒｔａｉｎ

ｂｅｔｒａｎｓｌａｔｅｄｏｎｌｙｉｎ

Ａｓａｏｆｔｅｎｈａｓｃｏｍｐｌｅｘｆｏｒｍ．ＴｈｅｙｃａｎＳｏｉｎｅｓｐｅｃｉａｌｃａｓｅａｎｄｅｘａｍｐｌｅｓｂｅｓｅｅｎＰｒｏｐｏｓｉｔｉｏｎ１．３．２．ｂａｓｉｃｓｔｏｃｈａｓｔｉｃｍｏｄｅｌ，ｃｈａｎｃｅｃｏｎｓｔｒａｉｎｓｍｏｄｅｌｈａｓｔｗｏｄｉｆｆｉｃｕｌｔ．Ｏｎｅｉｓ

ｔｏｔｈａｔｉｔｏｎｌｙｐａｉｄａｔｔｅｎｔｉｏｎ

ｒｅｆｅｒｒｉｎｇｔｈｅｑｕａｎｔｉｔｙｓｕｃｈ

ｔｈａｔｔｈｅｓｏｌｕｔｉｏｎｓｅｔｔｈｅｐｒｏｂａｂｉｌｉｔｙｏｆｆｅａｓｉｂｉｌｉｔｙｆｒｏｍｔｈｅｑｕａｌｉｔａｔｉｖｅ，ｎｏｔｒｅｃｏｕｒｓｅａｓｍｏｄｅｌＴｈｅｏｔｈｅｒｉｓａｂｏｕｔｔｈｅｍａｔｈｃｈａｒａｃｔｅｒｉｓｃｏｎｖｅｘｏｎｌｙｗｈｅｎｔｈｅｒａｎｄｏｍｖａｒｉａｂｌｅｓｓａｔｉｓｆｙｓｏｍｅｆｉｎｅ

ｔｈｅｃｏｎｖｅｘｃｏｎｄｉｔｉｏｎｓＴｈｅｅｘａｍｐｌｅｓ

ｉｍｐｏｒｔａｎｔｔＯｉｎ限４４］ｓｈｏｗｉｓｎｏｔｋｅｐｔｙｅｔ，ｗｈｉｌｅｗｈｉｃｈｉｓｓｏｌｖｉｎｇｔｈｅｐｒｏｂｌｅｍ。Ｓｏｆｏｒｔｈｅｓａｋｅｏｆｄｉｓａｄｖａｎｔａｇｅ．ｓｏｍｅｉｎｖｅｓｔｉｇａｔｏｒｐｒｏｐｏｓｅｄｉｎｔｅｇｒａｔｅｄｃｈａｎｃｅｃｏｎｓｔｒａｉｎｔｓｍｏｄｅｌｉｎ１

ｉｓｌｉｔｔｌｅａｎｄ９７０［３８］。Ｂｕｔｔｈｅｒｅｌｅｖａｎｔｒｅｓｅａｒｃｈｏｎｌｙ［４４，４５】ａｒｅｃｏｎｓｕｌｔｅｄ，ｔｈｅｒｅａｓｏｎｏｆｗｈｉｃｈｍａｙｂｅｔｈｅｃｏｍｐｌｅｘｉｔｙｏｆ

ｔＯｃｏｍｐｕｔｉｎｇＯｎｔｈｅｏｔｈｅｒｈａｎｄ，ｔｈｉｓｍｏｄｅｌｈａｓｖｅｒｙｇｏｏｄｃｈａｒａｃｔｅｒａｎｄｉｓｉｍｐｏｒｔａｎｔ

ｔｈｅｒｉｓｋｒｅｓｅａｒｃｈ，ｅｃｏｎｏｍｙｄｅｃｉｓｉｏｎｃｏｎｔｒ０１．Ｓｏｗｅｇｉｖｅｅｍｐｈａｓｅｓ

Ｓｏｍｅｋｉｎｄｓｏｆｄｅｆｉｎｉｔｉｏｎｔｏｉｔｉｎｃｈａｐｔｅｒ２ａｒｅｅｘｐａｎｄｏｆｉｎｔｅｇｒａｔｅｄｃｈａｎｃｅｃｏｎｓｔｒａｉｎｔｓｍｏｄｅｌｇｉｖｅｎｉｎ§２．１．

Ｄｅｆｉｎｉｔｉｏｎ

ｓｕｒｐｌｕｓ２。１．３ｃｏｎｓｉｄｅｒｓｔｈｅｓｕｒｐｌｕｓａｎｄｓｈｏｒｔａｇｅｔｏｇｅｔｈｅｒ．Ｄｅｆｉｎｉｔｉｏｎｔｈｅｒｅｓｏｕｒｃｅｉｓ：，７ｊ（ｘ，ｃｏ）＝ｍａｘ｛０，Ⅳ。），ｔｈｅｎｔｈｅａｖｅｒａｇｅｓｕｒｐｌｕｓ￡＿？ｓａｔｉｓｆｙＶ

山东大学博士学位论文

￡可ｉ＋Ｅ，７ｊ＝Ｅｌ叩，｛．Ｔｈｅｉｎｄｉｖｉｄｕａｌ

ｉ＝１，２，…，ｍ，ａｎｄｔｈｅｉｎｔｅｇｒａｔｅｄｃｈａｎｃｅｃｏｎｓｔｒａｉｎｔｓｉｓ：Ｅｒ／（ｓａ，ＥＩｑ，｛，ｊｏｉｎｔｉｎｔｅｇｒａｔｅｄｃｈａｎｃｅｃｏｎｓｔｒａｉｎｔｓｉｓ：Ｅ（ｑ，－，ｉ…ｌ

ｆｌ，．Ｉｎ

ａｃｃｅｐｔｖａｌｕｅ

ａｎｄｒｍ）≤口Ｔｈｉｓｄｅｆｉｎｉｔｉｏｎｏｖｅｒｃｏｍｅｓｔｈｅｄｉｆｆｉｃｕｌｔｙｏｆｔａｋｉｎｇｖａｌｕｅｆｏｒｄｅｆｉｎｉｔｉｏｎ２．１．４［７］，ｃｏｎｄｉｔｉｏｎｓｅｔｙ∈［Ｏ，００）ｉｓｅｘｐｅｃｔａｔｉｏｎｉｎｔｒｏｄｕｃｅｄｔｏｒｅｐｒｅｓｅｎｔｔｈｅｍａｘｉｍｕｍｏｆＥ【（７７一）１叩＜０］，ｄｅｆｉｎｉｎｇＥｒ／，一≤ｙ Ｐ（ｑ，＜０）ｓｏｌｕｔｉｏｎ

ｉｓＸ４（ｙ）≥｛ｘ∈Ｒ“，Ｅｑ７≤ｙ－Ｅ１１．１）．Ｉｔ＇ｓｒａｔｉｏｎａｌｉｔｙｉｓｇｉｖｅｎｉｎｔｈｉｓａｒｔｉｃｌｅ．

Ｓｕｂｓｅｑｕｅｎｔｌｙｔｈｅｃｈａｒａｃｔｅｒｏｆｔｈｉｓｍｏｄｅｌｉｓｄｉｓｃｕｓｓｅｄｉｎ§２．２，ｗｈｉｃｈｉｎｃｌｕｄｉｎｇｔｈｅｃｏｎｖｅｘｉｔｙｏｆｓｏｌｕｔｉｏｎｓｅｔ，ｃｏｎｔｉｎｕｕｍａｎｄｄｉｆｆｅｒｅｎｔｉａｂｉｌｉｔｙｏｆｒｅｓｔｒｉｃｔｉｏｎｆｕｎｃｔｉｏｎｕｎｄｅｒｔｈｅｐｒｅｃｏｎｄｉｔｉｏｎｔｈａｔｒｅｓｔｒｉｃｔｉｏｎｆｕｎｃｔｉｏｎｉｓ

ｅｘｐａｎｄｉｎｇｏｆｌｉｎｅａｒｃｏｎｄｉｔｉｏｎｃｏｎｖｅｘａｂｏｕｔｖａｒｉａｂｌｅ．Ａｓｔｈｅｉｎ［４４］，ｔｈｅｍａｉｎｒｅｓｕｌｔｉｓ：

Ｔｈｅｏｒｅｍ２，２．３Ｆｏｒｓｔｏｃｈａｓｔｉｃ

ｉｓａｐｒｏｇｒａｍｍｉｎｇ：ｒａｉｎ｛ｆ（ｘ）：ｇ（ｘ，０９）≥Ｏ，ｘ∈Ｄ｝，Ｄｃｏｎｖｅｘｆｉｘｅｄ，ｃｌｏｓｅｄ，ｆｉｎｉｔｅｓｅｔ，ｇ（ｘ，甜）ｉｓａｂｏｕｔｘａｎｄｅａｃｈｒａｎｄｏｍｖａｒｉａｂｌｅｓａｒｓｆｙｉｎｇＥ（ｃｏ，）＜∞，ｔｈｅｎ：

ｇ（ｘ）＝Ｅ［ｇ（ｘ，ＣＯ）一】ｉｓ

ｆｉｎｉｔｅｄｉｓｃｒｅｔｅｄｉｓｔｒｉｂｕｔｉｏｎ

ｆｏｒｃｏｎｔｉｎｕｏｕｓｄｉｓｔｒｉｂｕｔｉｏｎｆｉｎｉｔｅ、ｎｏｎｎｅｇａｔｉｖｅ，ｃｏｎｖｅｘａｎｄＬｉｐｓｃｈｉｔｓｃｏｎｔｉｎｕｏｕｓ．Ｆｏｒｐｉｅｃｅｗｉｓｅｌｙｃｏｎｖｅｘｏｆ（ａ（ＣＯ），ｂ（ＣＯ）），ｇ（ｘ）ｉｓｏｆ（ａ（ＣＯ），ｂ（ＣＯ）），ｇ（ｘ）ｉｓ

ｓｅｔ．Ｆｏｒｆｕｎｃｔｉｏｎ．ａｎｄｃｏｎｔｉｎｕｏｕｓａｎｄｄｉｆｉｅｒｅｎｔｉａｂｌｅ．Ｓｏｘ（ｆ１）＝｛ｘ∈Ｒ”：季（ｘ）≤卢）ｉｓｃｏｎｖｅｘｇ（ｘ，ｏＪ）＝∑臼，（∞扛；一６（∞），ｔｈｅｒｅｉｓ

掣生：日一２ａｊｘｓｇｎ（ｇ（ｘ）一）］，删。ｏｖｅＬＯＸ

！ｉ墨塑二譬型：日（∑ｎｑ（曲）巧）一］＾呻４＾。—ｉｉ。。

Ｔｈｅｔｈｅｏｒｅｍａｂｏｖｅｉｓｂａｓｉｎｇｆｏｒａｌｇｏｒｉｔｈｍｌａｔｅｒ，ｔｈｅｎｔｈｅｏｒｅｍ２．２．５ｇｉｖｅｓｔｈｅＬａｇｒａｎｇｅ

ｒｅｃｏｕｒｓｅｐｒｏｂｌｅｍｏｆｔｈｉｓｍｏｄｅｌ，ｉｎｄｉｃａｔｉｎｇｔｈａｔ￡（五）ｉｓｅｑｕｉｖａｌｅｎｔｏｒｔｏ（ｓｉｍｐｌｅ）ｐｕｂｌｉｓｈｉｎｇｍｏｄｅｌ，。Ｉｎｒｅｓｅａｒｃｈａｂｏｕｔｒｉｓｋｆｉｎａｎｃｅ［４５，４７１，ｔｈｅｅｑｕｉｖａｌｅｎｃｅｉｓｇｏｔｔｅｎｂｙ

ｏｆｏｕｒｔｒａｎｓｌａｔｉｎｇｔｈｅＷｈｅｎｔｈｅｅｖａｌｕａｔｉｎｇｗａｙｏｆｒｉｓｋｖａｌｕｅ．ｗｈｉｃｈｉｓｃｏｎｓｉｓｔｅｎｔｗｉｔＩｌｔｈａｔｗｏｒｋｒｅｃｏｕｒｓｅｃｏｅｆｆｉｃｉｅｎｔｉｓｈａｒｄ

ａｔｏｄｅｔｅｒｍｉｎａｔｅ，Ｏｃｃ（卢））ｃａｎｄｅｓｃｒｉｂｅｔｈｅｗｏｒｄｍｏｒｅａｃｃｕｒａｔｅｌｙａｎｄｏｆｆｅｒｎｅｗｍｅｔｈｏｄｆｏｒｃｏｍｐｕｔｉｎｇ．

ｏｒＩｎ§２．３，§２．４，ａｓｓｕｍｉｎｇｔｈｅｒａｎｄｏｍｖａｒｉａｂｌｅｓｏｂｅｙｆｉｎｉｔｅｄｉｓｃｒｅｔｅｃｏｎｔｉｎｕｏｕｓ

ｄｉｓｔｒｉｂｕｔｉｏｎｒｅｓｐｅｃｔｉｖｅｌｙｗｅｈａｖｅｄｅｓｉｇｎｅｄｔｈｅａｌｇｏｒｉｔｈｍｓ．Ｔｈｅｈｙｂｒｉｄｉｎｔｅｌｌｉｇｅｎｔａｌｇｏｒｉｔｈｍ２．３ｉｓｇｉｖｅｎ，ｂａｓｅｄｏｎｔｈｅｓｔｒｕｃｔｕｒｅｃｈａｒａｃｔｅｒｏｆｓｏｌｕｔｉｏｎｓｅｔ（ｔｈｅｏｒｅｍＶＩＩＩ

山东大学博士学位论文

２．３．１，ｔｈｅｏｒｅｍ２．３．２）ａｎｄｃｏｍｐａｒｉｎｇｅｘａｍｐｌｅａｂｏｕｔｒａｎｄｏｍｐｒｏｂｌｅｍｓｈｏｗｓｔｈｅｖａｌｉｄｉｔｙｏｆａｌｇｏｒｉｔｈｍ２．３，Ｔｈｅａｌｇｏｒｉｔｈｍ２．４ｉｓｇｉｖｅｎｗｉｔｈｃｏｍｐｌｅｘｉｔｙｏｆＯ（ｎ’乙），ｂａｓｅｄｏｎｔｈｅｃｈａｒａｃｔｅｒｏｆｐｒｏｂｌｅｍａｎｄｉｎｔｅｒｉｏｒａｌｇｏｒｉｔｈｍｗｉｔｈｄｅｃｏｍｐｏｓｉｎｇ

Ｉｎｃｈａｐｔｅｒ３ｔｈｅｔｗｏ—ｓｔａｇｅｍｏｄｅｌｗｉｔｈｒｅｃｏｕｒｓｅ（２Ｓ－ＳＰ）ｉｓｒｅｓｅａｒｃｈｅｄ．Ｉｎ§３１，ｂｙｃｏｎｔｒａｓｔｉｎｇｔｈｅｍｏｄｅｌｉｎｇｉｄｅａ，ｗｅｇｅｔｔｈｅｃｏｎｃｌｕｓｉｏｎｔｈａｔ（２ｓ－ＳＰ）ｉｓｅｑｕａｌｆｏｒｍａｌｌｙｔｏｂｉｌｅｖｅｒｐｒｏｇｒａｍｍｉｎｇ．Ｐｒｏｐｏｓｉｔｉｏｎ３．１．１ａｎｄ３．１．２ｓｈｏｗ：２Ｓ—ＳＰｉｓａｃｌａｓｓｏｆｒａｎｄｏｍｂｉｌｅｖｅｒｐｒｏｇｒａｍｍｉｎｇ，ｍｏｒｅｏｖｅｒｒａｎｄｏｍｖａｌｕｅ ｔｙｐｅｂｉｌｅｖｅｒｐｒｏｇｒａｍｍｉｎｇｗｉｔｈｏｎｅｓｕｂ—ｓｙｓｔｅｍｉｎｔｈｅｌｏｗ．１ｅｖｅｒＡｓ

ｆｏｃｕｓｅｓｏｎａｎＮＰ—Ｈａｒｄｐｒｏｂｌｅｍ，ｒｅｓｅａｒｃｈｗｏｒｋａｂｏｕｔ（２Ｓ—ＳＰ）Ｈｏｗｅｖｅｒ，ｂｉｌｅｖｅｒｍａｉｎｌｙｔｈｅｃｏｍｐｕｔｉｎｇａｎｄｒｅａｌｉｚａｔｉｏｎｏｆｓｏｌｕｔｉｏｎ

ｏｎｐｒｏｇｒａｍｍｉｎｇｈａｓｇｏｔｔｅｎｄｅｔａｉｌｅｄｄｅｖｅｌｏｐｍｅｎｔ

ａｌｇｏｒｉｔｈｍ．Ｓｏｐｒｏｐｏｓｉｔｉｏｎｓａｂｏｖｅｍａｋｅｏｕｔｔｈｅｏｒｙ，ｏｐｔｉｍｉｚａｔｉｏｎｍｅｔｈｏｄａｎｄｃａｎｔｈａｔｗｅｓｔｕｄｙ（２Ｓ—ＳＰ）ｕｓｉｎｇｆｏｒｒｅｆｅｒｅｎｃｅ．Ｔｈｅｏｒｅｍ３．１．４．ｔｈｅｏｒｅｍ３．１．５ｄｉｓｃｕｓｓｔｈｅｅｘｉｓｔｉｎｇｃｏｎｄｉｔｉｏｎｏｆｏｐｔｉｍａｌｓｏｌｕｔｉｏｎｉｎ２Ｓ—ＳＬＰ、２Ｓ—ＳＮＬＰ．

ＴｈｅｎｗｅｃｏｎｓｉｄｅｒｔｈｅｄｕａｌｔｈｅｍＴｏｆ２Ｓ ＳＰｉｎ§３．２．Ｆｏｒｃｏｍｐｌｅｘｉｔｙａｎｄｖａｒｉｅｔｙ，ｔｈｅｄｕａｌｔｈｅｏｒｙｏｆｓｔｏｃｈａｓｔｉｃ

ｒｅｆｅｒｅｎｃｅｓｐｒｏｇｒａｍｍｉｎｇｉｓｏｎｌｙｔｈｅｄｕａｌａｓｍａｌｌｑｕａｎｔｉｔｙｏｆ，ｉｎｓｏｍｅｃｅｒｔａｉｎｐｒｏｇｒａｍｍｉｎｇａｆｔｅｒｊｕｓｔａｓｆ４４，９９】ｄｉｓｃｕｓｓｅｄｕｓｉｎｇ

ｔｒａｎｓｌａｔｉｎｇｓｔｏｃｈａｓｔｉｃｐｒｏｇｒａｍｍｉｎｇｉｎｔｏｄｅｔｅｒｍｉｎｅｄｆｏｒｍ，ａｌｓｏｄｉｄｉｎ【７０】ｔＯｄｅｓｉｇｎｉｎｇａｇｇｒｅｇａｔｉｏｎｍｅｔｈｏｄｆｏｒｌａｒｇｅ．ｓｃａｌｅｒａｎｄｏｍｐｒｏｂｌｅｍｂｙｕｓｉｎｇｔｈｅｄｕａｌｏｆｄｅｔｅｒｍｉｎｅｄｅｑｕｉｖａｌｅｎｃｅｆｏｒｍ．

Ｃｏｎｓｉｄｅｒｉｎｇ２Ｓ—ＳＰｓｕｃｈａｓ（３．２．１），ｗｈｉｃｈｈａｓ

ａｓｃｏｎｖｅｘｆｕｎｃｔｉｏｎｓ，Ｂａｓｉｎｇｏｎｐｅｒｔｕｒｂｔｈｅｏｒｙ，ｔｈｅｄｕａｌｐｒｏｂｌｅｍｉｓｇｏｔｆｏｌｌｏｗｓ：

ｓｕｐＤ＝ｓｕｐｉｎｆＬ（ｘ，ｙ）．

４

，）

Ｗｈｅｒｅ，上（ｘ．∥）＝ｉｎｆ｛“７ｙ＋Ｆ（ｘ，Ⅳ））５上１（ｒ，ｙ）＋ｆＬ２

ＥｓｐｅｃｉａｌｌｙｗｈｅｎａｌｌｆｕｎｃｔｉｏｎｓａｒｅｇＯ，Ｘ１，Ｘ２（珊））ｐ（ｄ珊）ｒｄｕａｌｐｒｏｇｒａｍｍｉｎｇｏｆｌｉｎｅａｒａｂｏｕｔｘ，ｔｈｅ

２Ｓ—ＳＬＰｗｈｉｃｈｈａｓｔｈｅｆｏｒｍ（３．２．４）ｉｓ：

ｍａｘ

ｖ口ｆｍ｝ｖｂ＋ｌ删ｒｒ（ｃ。）Ｈ（ｃｏ）ｐ（ｄｏａ）

ｃ１一ｖＡ—Ｉｚｃ（ｒｏ）Ｔ（ｃｏ）ｐ（ｄｃｏ）≥０

“＿｛Ｃ２（０３）一７ｒ（ｃｏ）ｗ（ｃｏ）≥０

Ｖ、Ｆ（∞）≥０

Ｌ（３．２．５）

Ｗｅｃａｎｓｅｅａｔｏｎｃｅｔｈａｔｉｆｄｅｌｅｔｅｔｈｅｒａｎｄｏｍｆｕｎｃｔｉｏｎｓｉｎｐｒｉｍａｌｐｒｏｂｌｅｍ（３．２４）

山东大学博士学位论文

ａｎｄｄｕａｌｐｒｏｂｌｅｍ（３．２．５）ｔｈｅｎｗｅｃａｎｇｅｔｔｒａｄｉｔｉｏｎａｌｐｒｉｍａｌ—ｄｕａｌｆｏｒｍａｂｏｕｔｃｅｒｔａｉｎｐｒｏｂｌｅｍ．Ｗｈａｔ’Ｓｍｏｒｅ，ｔｈｅｃｏｎｃｌｕｓｉｏｎａｂｏｖｅｉｓｃｏｎｓｉｓｔｅｎｔｗｉｔｈｔｈａｔｉｎ［７４］．（３．２５）ｅｘｔｅｎｄｓｔｈｅｄｕａｌｏｆｌｉｎｅａｒｐｒｏｇｒａｍｍｉｎｇｔｏ２Ｓ—ＳＬＰ，ｗｈｉｃｈｎｏｔｏｎｌｙｃｏｎｓｕｍｍａｔｅｓｔｈｅｔｈｅｏｒｙｂｕｔａｌｓｏｂｒｉｎｇｎｅｗｉｄｅａｆｏｒｃｏｍｐｕｔｉｎｇｔｈｉｓｍｏｄｅｌ．

Ｉｎｔｈｅｖｉｅｗｏｆａｐｐｌｉｃａｔｉｏｎ，ｏｔｈｅｒｔｗｏｕｎｃｅｒｔａｉｎｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍｓａｒｅｓｔｕｄｉｅｄｉｎｃｈａｐｔｅｒ４．Ｏｎｅｉｓｌｏｃａｔｉｏｎｐｒｏｂｌｅｍｉｎｕｎｃｅｒｔａｉｎｅｎｖｉｒｏｎｍｅｎｔｓｔｕｄｉｅｄｉｎ§４．１．ＢｙｎＯＷｉｔｏｎｌｙｈａｖｅａｐｐｅａｒｅｄｉｎｌｉｔｔｌｅｒｅｆｅｒｅｎｃｅｓｓｕｃｈａｓａｐｐｌｙｉｎｇｆｕｚｚｙｊｕｄｇｅａｎｄｃｏｎｓｉｄｅｒｉｎｇｔｈｅｒａｎｄｏｍｄｅｍａｎｄ．Ｂｕｔｔｈｅｆｏｒｍｅｒｈａｓｔｈｅｄｉｆｆｅｒｅｎｔｓｕｂｊｅｃｔｉｏｎｆｕｎｃｔｉｏｎｂｙｄｉｆｆｅｒｅｎｔｅｘｐｅｒｔｓａｎｄｔｈｅｌａｔｔｅｒｏｆｔｅｎｓｕｐｐｏｓｅｄｉｓｔｒｉｂｕｔｉｏｎｆｕｎｃｔｉｏｎｈａｓｂｅｅｎｋｎｏｗｎ．ＴｈｉｓｃａｓｅｗｉｌｌｂｎｎｇｍｏｒｅｕｎｃｅｒｔａｉｎｅｌｅｍｅｎｔｆｏｒｄｅｃｉｓｉｏｎｍａｋｅｒＳＯｗｅｉｎｔｒｏｄｕｃｅｉｎｔｅｒｖａｌｖａｒｉａｂｌｅｔｏｄｅｓｃｒｉｂｅｔｈｅｌｏｃａｔｉｏｎｐｒｏｂｌｅｍ．Ｉｎｔｅｒｖａｌｐｒｏｇｒａｍｍｉｎｇｉｓｉｎｔｒｏｄｕｃｅｄｆｉｒｓｔｌｙ，ｔｈｅｎｓｏｍｅｉｎｔｅｒｖａｌｐｒｏｇｒａｍｍｉｎｇａｂｏｕｔｌｏｃａｔｉｏｎａｒｅｅｓｔａｂｌｉｓｈｅｄｗｈｉｃｈｉｎｃｌｕｄｅｓ：ｏｐｔｉｍｉｚｅｍｏｄｅｌ、ｐｅｓｓｉｍｉｓｍｍｏｄｅｌ、ｅｘｐｅｃｔａｔｉｏｎｍｏｄｅｌ、ｕｎｃｅｒｔａｉｎ－ｖａｌｕｅｍｏｄｅｌ、ｌｏｓｉｎｇｍｏｄｅｌ、ｒｏｂｕｓｔｍｏｄｅｌａｎｄｍｕｌｔｉ－ｐｒｏｇｒａｍｍｉｎｇ．

Ｔｈｅｏｔｈｅｒｐｒｏｂｌｅｍｉｓａｂｏｕｔｔｈｅｒｅｄｕｃｔｉｏｎｉｎｄｅｃｉｓｉｏｎｔａｂｌｅｂａｓｅｄｏｎｒｏｕｇｈｓｅｔ．Ｄｕｅｔｏｉｔｓｐｒａｃｔｉｃａｌｕｓｅｉｎｋｎｏｗｌｅｄｇｅｄｉｓｃｏｖｅｒｙａｎｄｄａｔａｍｉｎｉｎｇ，ｒｅｄｕｃｔｉｏｎｉｓｂｅｃｏｍｉｎｇｍｏｒｅｉｍｐｏｒｔａｎｔａｓｐｅｃｔｏｆｃｏｍｐｕｔｅｒｓｃｉｅｎｃｅ．Ｎｏｗｔｈｅｒｅａｒｅｓｏｍｅａｔｔｒｉｂｕｔｅｒｅｄｕｃｔｉｏｎｍｅｔｈｏｄｓ【８６—９１］：ｓｕｃｈａｓｂａｓｅｄｏｎｄｉｓｔｉｎｇｕｉｓｈｍａｔｒｉｘｉｎａｌｇｅｂｒａｖｉｅｗａｎｄｕｓｉｎｇｅｎｔｒｏｐｙｉｎｉｎｆｏｒｍａｔｉｏｎｖｉｅｗ．Ａｔｔｈｅｓａｍｅｔｉｍｅ，ｆｏｒｉｔ＇ｓｃｈａｒａｃｔｅｒｏｆＮＰ—Ｈａｒｄ，ｐｅｏｐｌｅｏｆｔｅｎｉｎｔｒｏｄｕｃｅｓｕｇｇｅｓｔｉｎｇｉｎｔｅｌｌｉｇｅｎｔａｌｇｏｒｉｔｈｍａｓｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍａｎｄｐａｒａｌｌｅｌｃｏｏｐｅｒａｔｉｎｇａｌｇｏｒｉｔｈｍｉｎｌａｒｇｅ－ｓｃａｌｅｐｒｏｂｌｅｍＢａｓｅｄｏｎｔｈｅｒｅｌａｔｉｏｎｓｈｉｐｂｅｔｗｅｅｎａｔｔｒｉｂｕｔｅｒｅｄｕｃｔｉｏｎａｎｄｌｏｇｉｃｏｐｅｒａｔｉｏｎｓ，ａｌｌｉｎｔｅｇｅｒｐｒｏｇｒａｍｍｉｎｇａｌｇｏｒｉｔｈｍ４．２ｔｏｆｉｎｄｉｎｇｍｉｎｉｍａｌｓｉｚｅｒｅｄｕｃｔｉｏｎｉｓｐｒｏｐｏｓｅｄｉｎ§４．２．ｗｈｉｃｈｃａｒｌａｖｏｉｄｃｏｍｐｉｉｃａｔｅｄｌｏｇｉｃｏｐｅｒａｔｉｏｎｓ，ａｎｄｂｅｃｏｍｅｓｍｏｒｅｅｆｆｅｃｔｉｖｅｌｙｉｎｄｙｎａｍｉｃｅｎｖｉｒｏｎｍｅｎｔ．Ｔｈｅｅｘｐｅｒｉｍｅｎｔｓａｎａｌｙｓｉｓｉｓｇｉｖｅｎｔｏｓｈｏｗｔｈｅｅｆｆｉｃｉｅｎｃｙｏｆａｌｇｏｒｉｔｈｍｓｉｎｃｈａｐｔｅｒ４．

Ｔｈｅｉｎｎｏｖａｔｅｖｉｅｗｐｏｉｎｔｓｏｆｔｈｉｓｄｉｓｓｅｒｔａｔｉｏｎａｒｅａｓｆｏｌｌｏｗｓ：

１．Ｗｅｃｏｏｒｄｉｎａｔｅｔｈｅｂａｓｉｃｍｏｄｅｌｓｏｆｓｔｏｃｈａｓｔｉｃｐｒｏｇｒａｍｍｉｎｇａｎｄｐｅｒｆｅｃｔｔｈｅｄｅｆｉｎｉｔｉｏｎｏｆｏｐｔｉｍａｌｖａｌｕｅａｎｄｓｏｌｕｔｉｏｎｉｎｒａｎｄｏｍｍｏｄｅｌ．Ｗｈａｔ’Ｓｍｏｒｅ，ｔｈｅｒｅｌａｔｉｏｎｓｂｅｔｗｅｅｎｔｈｅｍａｒｅｄｉｓｃｕｓｓｅｄａｎｄｔｈｅｅｑｕｉｖａｌｅｎｃｅｆｏｒｍｓａｒｅｒｅｉｎｆｏｒｃｅｄ．

２．Ｉｎｉｎｔｅｇｒａｔｅｄｃｈａｎｃｅｃｏｎｓｔｒａｉｎｔｓｍｏｄｅｌ，ｔｈｅｃｈａｒａｃｔｅｒｏｆｓｕｂｊｅｃｔｉｖｅｌｉｎｅａｒｆｕｎｃｔｉｏｎｉｓｅｘｐａｎｄｅｄｔｏｔｈａｔｏｆｃｏｎｖｅｘｆｕｎｃｔｉｏｎ．Ｗｅｇｅｔｇｏｏｄｃｈａｒａｃｔｅｒｗｈｉｃｈｉｎｃｌｕｄｉｎｇｔｈｅｃｏｎｖｅｘｉｔｙｏｆｓｏｌｕｔｉｏｎｓｅｔ，ｃｏｎｔｉｎｕｕｍａｎｄｄｉｆｆｅｒｅｎｔｉａｂｉｌｉｔｙｏｆｒｅｓｔｒｉｃｔｉｏｎｆｕｎｃｔｉｏｎａｎｄＸ

些查查堂堕主兰｜三堡笙茎

ｄｅｓｉｇｎｔｗｏａｌｇｏｒｉｔｈｍｓ

ｖａｒｉａｂｌｅ．

３Ｂｙａｐｐｌｙｉｎｇｂｉｌｅｖｅｒｐｒｏｇｒａｍｍｉｎｇ

ｆｉｎｄｔｈａｔｔｏｔｏｃｏｍｐｕｔｅｒｒａｎｄｏｍｐｒｏｂｌｅｍｓｗｉｔｈｄｉｓｃｒｅｔｅｏｒｃｏｎｔｉｎｕｅｓｓｔｕｄｙｔｈｅｔｗｏ—ｓｔａｇｅｍｏｄｅｌｗｉｔｈｒｅｃｏｕｒｓｅ，ｗｅｂｉｌｅｖｅｒｐｒｏｇｒａｍｍｉｎｇａｎｄｇｉｖｅｔｈｅｅｘｉｓｔｉｎｇ２Ｓ．ＳＰｉｓｅｑｕａｌｆｏｒｍａｌｌｙｔｏ

ｃｏｎｄｉｔｉｏｎｏｆｏｐｔｉｍａｌｓｏｌｕｔｉｏｎｉｎ２Ｓ—ＳＬＰ、２Ｓ．ＳＮＬＰ．Ａｔｔｈｅｓａｍｅｔｉｍｅｗｅｒｅｓｅａｒｃｈｔｈｅｄｕａｌｔｈｅｏｒｙｏｆ２Ｓ—ＳＰａｎｄｐｒｏｐｏｓｅｔｈｅｄｕａｌｐｒｏｂｌｅｍ，ｗｈｉｃｈ

ｏｆＬＰａｎｄＢＲＩｔｉｓｔｈｅｉｎｎｏｖａｔｉｏｎａｂｏｕｔｔｈｅｏｒｙａｎｄｍｅｔｈｏｄ．

４ｃｏｖｅｒｓｔｈｅｄｕａｌｅｘｐｒｅｓｓｉｎｇＢａｓｉｎｇｏｎｉｎｔｅｒｖａｌｐｒｏｇｒａｍｍｉｎｇａｎｄｒｏｕｇｈｏｐｔｉｍｉｚａｔｉｏｎ，ｗｅｐｒｏｐｏｓｅｅｆｆｅｃｔｉｖｅ

ｓｏｌｖｅｔｗｏｉｍｐｏｒｔａｎｔｐｒｏｂｌｅｍｓ：ｌｏｃａｔｉｏｎａｎｄｒｅｄｕｃｔｉｏｎＩｔｉｓｔｈｅａｌｇｏｒｉｔｈｍｓｔｏ

ｉｎｎｏｖａｔｉｏｎａｂｏｕｔａｐｐｌｉｃａｔｉｏｎａｎｄｍｅｔｈｏｄ．

Ｋｅ）’ｗｏｒｄｓ：Ｓｔｏｃｈａｓｔｉｃｐｒｏｇｒａｍｍｉｎｇ；Ｉｎｔｅｇｒａｔｅｄｃｈａｎｃｅｃｏｎｓｔｒａｉｎｔｓｍｏｄｅｌ；Ｔｗｏ—ｓｔａｇｅ

ｍｏｄｅｌｗｉｔｈｒｅｃｏｕｒｓｅ；Ｉｎｔｅｒｖａｌｐｒｏｇｒａｍｍｉｎｇ；Ｒｏｕｇｈｏｐｔｉｍｉｚａｔｉｏｎ，

山东大学博士学位论文

第一章绪论

首先在引言中介绍不确定优化问题研究的意义、背景、主要分类及本文研究内容，然后从建模机理出发，对现有的随机规划基本模型进行归纳整理，在此基础上讨论了基本模型之间的内在联系及相互转化。

§１．１

１．不确定优化问题研究的必要性引言

当今世界处在一个信息时代，信息是人类认识世界和改造世界的知汉源泉，人们接触到的各种各样的信息有时候是确定性的，更多的时候是不确定的，比如自然界中普遍存在着各种不确定现象：经济生活中伴随着大量的不确定信息，股票证券或期货市场总是处在不确定的波动状态；某些传染性疾病的传播过程中有诸多不确定因素。在现实世界中，不确定信息可谓无处不在，而信息的不确定性表现又是复杂多样的，例如随机信息、模糊信息、粗糙信息、模糊随机信息、双重随机信息、双重模糊信息等等。信息本身的确定或不确定属性不能用“好坏”进行简单地判定，我们不能片面地认为确定信息纯粹就是好，不确定信息全然就是坏事，问题在于人们怎样认识和把握不确定性。确定与不确定现象分别揭示和反映事物变化发展过程中的必然与偶然、清晰与模糊、精确与近似之间的关系。确定性是指客观事物联系和发展的过程中有规律的、必然的、清晰的、精确的属性；不确定性是指客观事物联系和发展的过程中无序的、或然的、模糊的、近似的属性。确定与不确定，既有本质区别，又有内在联系，两者辨证统一，既相互矛盾，相互依存，在一定条件下又可相互转化。人们应该重视不确定性，善于利用有利的不确定性，避免不利的不确定性，通过不确定性掌握确定性，从“不定”中求“有定”。实际中人类对不确定性的认识由来已久，概率论的产生可以追溯到几百年的历史，模糊数学诞生于上个世纪六十年代，粗糙集合的问世则是近二十年的事情，概率论已经广泛应用于众多的学科，模糊数学的理论与方法也逐渐受到人们的青睐。随着软计算研究的兴起，租糙集合的理论与方法也日益引起人们的关注。一大批数学工作者、计算机研究人员、控制工程师、语言逻辑学家甚至哲学家，对不确定性的研究表现出了浓厚的兴趣，不确定信息处理的研究越柬越引超人们的重视。

山东大学博士学位论文

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

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

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

２．本课题的研究背景

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

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

山东人学博士学位论文

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

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

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

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

３．本文的主要研究内容

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

山东大学博士学位论文

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

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

二（多）阶段有补偿模型是随机规划的一类重要组成，在许多实际优化问题中得到广泛应用。本文在第三章中对该模型进行研究。因为该优化问题为ＮＰ—Ｈａｒｄ问题，现有的研究成果多局限于讨论解的计算方法与实现方面［３，４，８］，而双层规划近二十年来己在基本理论、最优性、算法等方面得到较为全面深入的研究［７１—７４］。在第一节中，本文通过对比该模型与双（多）层规划的建模思想，发现二者存在极大类似之处，具有形式上的等价性，因此给出两阶段模型的双层规鲻等价形式，并讨论了在期望模型、机会约束模型下的形式变形，以及最优解的存在情况。接下来，我们把目光转向二阶段有补偿优化模型的对偶。鉴于随机规

山东大学博士学位论文

划模型的复杂性与多样性，在现有的研究资料中很少专门提到它的对偶理论，在少量文献中，如［４４，９９］只是把随机规划转化为确定性等价形式后，利用确定性规划的对偶理论给出它的对偶形式，［７０］利用转化后的确定性形式的对偶来设计求解大规模随机优化问题的聚合算法。但与其等价的双层规划的对偶理论已开始得到较为系统的研究。故本文立足双层规划的角度，在第二节研究二阶段有补偿模型的对偶，给出了凸函数、线性函数的对偶形式，完善了该模型的理论，也为进一步的算法设计提供支持。

第四章从应用角度出发，研究了其它两类不确定性优化问题。第一个为运筹学研究的重点问题：选址问题。在目前已有的研究成果中，只有很少一部分讨论了不确定环境下的优化问题，如应用模糊评判方法来进行最优选址［７９］；需求量为随机变量时的优化选址等［８０］。但前者关于模糊变量隶属函数的选取含有较大的人为因素，后者则假设随机变量的分布函数已知。在实际决策时若依据经验或专家给出，则不同的专家往往给出不同的分布函数和隶属函数，从而使问题更加不确定化。因而，最能恰当地描述这一现象的当数区间变量。本文假设需求量为一般的不确定变量：区间变量，根掘不同的决策目标，建立了选址的若干区间规划模型。第二个为粗集的决策表属性约简问题，作为信息系统中知识发现，数据挖掘的重要内容，约简近年来已成为计算机科学的热点问题之一，约简算法越来越得到人们的重视。目前已有多种属性约简算法［８６—９１］，有从代数角度的基于区分矩阵的最小约简方法，如基于区分矩阵中属性重要度的、基于区分矩阵和逻辑运算的、基于条件一决策关联度的；还有从信息角度出发的基于信息熵的约简算法。因为求属性集合的最小约简（即所含属性个数最少的约简）是ＮＰ—Ｈａｒｄ问题，在大规模问题与计算中，人们还常采用启发式智能算法，如遗传算法、并行协同算法等进行研究。本文依据属性约简与逻辑运算的关系，给出一种新的计算最小约简的整数规划算法，该算法能有效地避免大量逻辑运算，并且当系统的属性及论域处于动态变化的环境时，只需应用该算法做某些局部调整即可求得新决策表的最小约简。最后对两类问题进行了实例分析。

§１．２随机规划的基本优化模型

随机规划是一门新兴学科，它是随着线性和非线性规划等的应用和发展逐步深入而形成、发展起来的，它的形成始于上世纪５０年代。

最早提出随机规划问题的是线性规划创始人之一的Ｇ．Ｄａｎｔｚｉｇ以及Ｂｅａｌｅ，在［３５，３６］他们将线性规划应用于航线班机最优次数的设计，考虑到客流量是随

山东大学博士学位论文

机变量，提出了有补偿的二阶段优化问题，Ｗｅｔｓ［３７—３９］对该类问题进行了系统研究。Ａ．Ｃｈａｒｎｅｓ，Ｗ．Ｃｏｏｐｅｒ和他的同事们首先提出了概率约束规划模型（也被命名为机会约束规划，即Ｃｈａｎｃｅｃｏｎｓｔｒａｉｎｅｄｐｒｏｇｒａｍ），他们在［４０］中研究了炼油厂的生产和存储问题，Ｐｒｅｋｏｐａ作了重要的理论贡献［４１，４２］，在６０年代和７０年代，随机规划的模型、方法、理论和应用得到了较大的发展，如Ｍａｒｋｏｗｉｔｚ的均方差分析方法、Ｄｕｐａｃｏｖａ的惩罚模型、Ｎｅｕｍａｎｎ的效用模型，Ｇａｒｓｔｋａ与Ｚｉｅｍｂａ等人将其应用到经济均衡分析、金融风险测度等领域，得到了许多重要结论。

本节将按照随机变量进入经典规划问题的可行域或目标函数，分别讨论几种主要的建模方法。

１．随机规划的定义

传统的确定性规划的一般形式为：

ｍｉｎｆ（ｘ）

ｊ＾ｇ．（ｘ）≥Ｏ，ｆ＿１…．．ｍ

其中，ｆ（ｘ）为目标函数，ｇ，（ｘ）为一组约束函数，ｘ∈Ｒ”为决策向量。当．厂Ｏ），ｇ（ｘ）中的确定性参数取值为随机变量，如对下述线性规划：

ｍｉｎ∑ｃＪｘ，

ｊ＝ｌ

“．∑ｑ。Ｊ

，＝Ｉ２６．，『＝ｌ…ｍ

ｘ。≥Ｏ，，＝１…”

若确定性的参数ｃ，，ｏ，，ｂ，部分或全部为概率空间（Ｑ，Ｆ，Ｐ）中的随机变量，则相应地称（ＬＰ）为随机线性规划（Ｓｔｏｃｈａｓｔｉｃ

～般形式为：ｌｉｎｅａｒｐｒｏｇｒａｍ）简记为（ＳＬＰ），其

ｍ。ｉｎ∑ｃ膨弦，

“．∑气（∞）ｘ，≥６，（曲），ｆ＝１…ｍ，

其中ｃｏ为样本点，｛ｃ（ｃｏ），口∞），６扣）｝为概率空间（Ｑ，Ｆ，Ｐ）中的随机向量，Ｄ为确定性集合。与（Ｐ）问题相适应的随机规划（ＳＰ）的一般形式为：

ｒａｉｎｆ（ｘ，孝）５ｔ，ｇ．（ｚ，ｆ）≥Ｏ，卜１…ｍ．

本文来源：https://www.bwwdw.com/article/fz1i.html