《1　前言》

1　前言

20 世纪下半叶以来，优化技术在物理、化学系统，生产计划、调度系统，定位与运输问题，经济系统中的资源分配及工程设计等方面得到了广泛的应用，同时，关于不确定条件下的设计和优化问题得到了人们越来越多的关注[1]。处理不确定性信息的方法一般有：概率论、证据理论、可能性理论、模糊集理论、灰集理论、粗集理论、区间代数等，当然这些理论之间存在着互相交叉。选择何种方法取决于所能获得的信息和决策者的态度及目的。以这些理论为基础，常用的不确定优化方法包括灵敏度分析、随机规划、模糊规划、鲁棒优化等。

鲁棒优化中“鲁棒”的含义是：模型对数据的不确定具有免疫性。关于带有不确定数据的线性优化问题的鲁棒优化方法，最早由 Soyster[2]提出。他建立了一种线性优化模型来构建一个解，使其对一个凸集的所有数据均为可行，并可以证明，对随机参数的每一个实现，从模型得到的最优解都是可行的，实际上类似于最坏情形分析。从此展开了线性优化问题的鲁棒优化方法的研究，近年来所提出的鲁棒优化方法，主要针对最坏情形利用 min-max 目标进行优化，但是结果过于保守。后来研究的重点在于如何降低解的保守性。

Ben Tal[3,4]对 Soyster 的模型进行了改进，虽然降低了保守性，但模型成为非线性，变得复杂了。Dimitris[5,6]考虑相似的问题，建立了一种新的鲁棒模型，引入参数用于控制约束的违反概率和对目标函数值的影响之间的平衡。而所谓的鲁棒的代价即对标称问题的目标函数值造成的影响。

而上述鲁棒优化的方法都存在共同的局限性：第一，不确定性只考虑约束左端参数的变化；第二，随机参数的分布是对称的，而且没有利用概率分布的信息；第三，鲁棒性的提高是以标称问题的性能指标为代价的。针对上述问题，笔者借鉴随机规划中的机会约束规划思想，提出了鲁棒性指标的定义，根据约束中随机参数的概率分布，构造了两种新的鲁棒性约束，在此基础上，提出了一种考虑概率分布的线性优化问题的鲁棒优化模型，并可以方便地将其推广到非线性问题中。仿真实例说明了模型的有效性。

《2　机会约束规划》

2　机会约束规划

机会约束规划 （chance constraint programming）又被称为概率规划（probabilistic programming），其形式很多，比如刘宝碇[7]提出的 Maximax 机会约束规划、Minimax 机会约束规划及随机相关机会规划等。机会约束规划模型的基本形式：

其中，x 为决策变量，ξ 为随机参数， 表示目标的实现概率，α 表示相应约束的可行概率。

对含有随机参数的线性问题，模型可表示为

其中，ζj ， ηij ， ξi  为随机参数，概率密度函数已知，分别为 θj （ζj ）， （ηij ）， φij （ξi ），并且所有的随机参数互相独立。参照机会约束规划，对解的鲁棒性指标作如下的定义。

定义 1　鲁棒性指标。设 x * 为预选用的解，则

称 为 x * 对约束 i  的鲁棒性指标。令 =，称 为 x * 对模型的鲁棒性指标。

根据上述定义可知，当 =1 时，可以适应随机变量的任何一种实现，鲁棒性最强，但这种解过于保守，与 Soyster 模型的效果类似。另外，若直接求定义的鲁棒性指标，相当于求多个随机变量线性组合的概率分布，难度可想而知，目前常用的方法是使用 Monte-Carlo 模拟，但需要进行大量的计算，也就是现在机会约束规划经常采用的方法。

将根据概率论中的相关理论依据，将机会约束转换为确定性约束并满足一定的鲁棒性指标，从而形成一种考虑概率分布的鲁棒优化模型。

《3　鲁棒性约束》

3　鲁棒性约束

为了便于分析，参照式（2）中的约束和定义 1，对随机变量相对其期望值进行平移，则相应的约束方程的可行机会为

为处理方便，忽略原约束方程中边界上的点，对于在原可行域内的点，即式（3）的“  ”右侧大于零，则式（3）可转化为

如果在原模型中增加鲁棒性约束以取代通过概率计算得到的机会约束，使得式（4）大于等于给定的鲁棒性能指标 ，则解可以满足鲁棒性要求。

《3.1　随机参数独立有界》

3.1　随机参数独立有界

1963 年 Hoeffding 给出了独立有界随机变量之和的概率不等式，已成为概率论和统计学的一个非常重要的结果，并且得到了广泛的应用。对其结果陈述如下：

定理（Hoeffding）[8] 假设 Y1 ， …， Yn 是拥有零均值的随机变量序列，且 ，对任意的 δ 0，有不等式

成立。

根据上述定理，有如下结论成立。

定理 1　对于 MILP 模型（见式（2））中的约束 i，如果随机参数独立有界，则其满足鲁棒性指标的充分条件为

证明：由 Hoeffding 定理可得

即可以得到独立有界的随机变量和的概率分布的下界。分析式（4），对于某一特定的 x，随机变量 θij ，θ′ij ， 分别为

如果原系统中的随机参数独立，且满足 cij  ηij dij ， j = 1， …， r， r + 1， …， n， 。可知，对于某一特定的 x，式（7）至式（9）所对应的随机变量均值为零，独立有界，并且边界可以求出，满足 Hoeffding 定理的条件。令 δ =1，将其代入式（6），可得

显然，如果式（10） 右端 ，左端必然也 ，即满足系统的关于约束 i  的鲁棒性指标。（证毕）

因此，式（5）可作为随机参数有界时鲁棒优化模型的鲁棒性约束。

《3.2　随机参数单边有界》

3.2　随机参数单边有界

2003 年 Andreas 对于独立单边有界随机变量之和的概率分布有如下的结论。

定理（Andreas）[9]　令 为独立的随机变量， 。设 S = ，且 δ ＞0，若 Yi   bi ， =，则有不等式

成立。

同样，根据上述定理，有如下结论成立。

定理 2　对于 MILP 模型（见（2）式）中的约束 i，随机参数独立，且 ，j = 1，…， r， r + 1， …， n， ，则其满足鲁棒性指标的充分条件为

证明：由 Andreas 定理可得式（12）成立：

同定理 1 的证明，如果约束 i  中随机参数独立，且 ，j = 1，…， r， r + 1， …， n，。可知，对于特定的 x，式（7）至式（9）中对应的随机变量也满足 Andreas 定理要求，并且边界很容易求出，另外期望值为零。同样令 δ =1，将其代入式（12），可得

其中 D  是方差算子。

显然，如果式（13）右端 ，左端必然也 ，即满足系统的关于约束 i  的鲁棒性指标。（证毕）

同理，式（11）可以作为随机参数单边有界时鲁棒优化模型的鲁棒性约束。

综上所述，如果在含有随机参数的 MILP 模型中，随机参数独立有界或单边有界，满足定理 1 和定理 2 的条件，则以形如式（5）和式（11）的鲁棒性约束取代原有的不确定约束，就可使解满足鲁棒性要求，从而形成一种新的鲁棒优化模型。

《4　应用举例》

4　应用举例

假设一含有随机参数的数学规划模型为

其中，η1 为服从均匀分布 U（0.8， 0.8） 的随机变量；η2 为服从指数分布 exp（0.4）的随机变量；ξ1 和 ξ2 分别服从正态分布 N（0，12）和 N（0，9）。根据概率论中的“3σ 规则”，即对于正态分布的随机变量来说，它的值落在区间 [ μ - 3σ，μ + 3σ ] 内几乎是肯定的，这里取 ξ1 的上下界为[ -10.464，10.464 ]，ξ2 的下界为 -9 。

根据模型中随机参数的概率分布情况，在模型式（14）的基础上，分别为两个含有随机参数的约束方程建立形如式（5）和式（11）的鲁棒性条件约束，设相应的鲁棒性能指标为 0.8， 0.7， 0.7，修改上述模型，得

运用遗传算法对模型进行求解，计算得到的最优解为（35.14， 23.72）目标值为 141.47。更进一步，结合机会规划，有 = 0.997， ≈（ 0.912， ≈ 0.912。计算时间为 1.126 s。

用随机模拟的方法解相应的机会约束规划模型，在同样的条件下运用遗传算法，得到的最优解为（31.92， 22.65），目标值为 131.85，且 = 0.88， ≈ 0.70，≈ 0.7。计算时间为 133.514 s。

运用最坏情形分析的方法得最优解为（41.35，23.43），目标值为 153.12， ≈ 1。对结果进行比较，所提出鲁棒性约束及鲁棒优化模型，鲁棒性能指标较高，而且计算速度快， 从 133.514 s 缩短为 1.126 s，弥补了基于随机模拟的机会约束规划模型的缺点，且与最坏情形分析相比，保守性降低。

《5　结语》

5　结语

对于含有随机参数的优化问题来说，若需降低解的保密性，必然需要充分利用概率分布信息，文章针对随机参数的不同分布情况，得到了使可行解满足鲁棒性能指标的充分各件，建立了鲁棒优化模型。该模型可以处理约束左、右两端同时含有随机变量的情况，并且充分利用了随机参数的概率分布，在一定程度上弥补了已有鲁棒优化模型的不足。另外从定理 1、定理 2 的证明过程可以知道，该方法不但适用于 MILP 模型，还可以推广到非线性的情况，只要求随机参数相互独立，且与决策变量的函数呈线性关系即可。仿真实例说明了模型的有效性。