1、第七章 随机规划1第六章 随机规划第一节 问题的提出随机规划所研究的对象是含有随机因素的数学规划问题。例如，我们熟悉的线性规划问题CXf)(min（6.1）0bA如果其中的 ， ， 的元素中部分的或全部的是随机变量，则称其为随机线性规划问题。在数学规划中引入随机性是很自然的事情。在模型中的 ， ， 的AbC元素常常代表价格、成本、需求量、资源数量、经济指标等参数。由于各种不确定性因素的影响，这些参数经常出现波动。例如，市场上对某种商品的需求量一般无法精确的预知，只能作出大致的预测，某种产品的生产成本往往受原材料价格、劳动生产率等各种因素的影响而经常变化，这些变化与波动，在许多场合可以用一定的概
2、率分布去描述。因此，在数学规划中引入随机变量，能够使模型更加符合实际情况，从而是的决策更加合理。例 1 某化工厂生产过程中需要 ， 两种化学成分，现有甲、乙两种AB原材料可供选用。其中原料甲中化学成分 的单位含量为 ， 的单位10/aB含量为 ；原料乙中化学成分 的单位含量为 ， 的单位含量为 。3/a 10/ 3/根据生产要求，化学成分 的总含量不得少于 个单位，化学成分 的7A总含量不得少于 个单位。甲、乙两种原料的价格相同，问如何采购原/4料，使得即满足生产要求，又是的成本最低？显而易见，这个问题可以用线性规划模型来描述。根据题意，设原料甲的采购数量为 ，原料乙的采购数量为 ，容易得到如
3、下线性模型：1x2x1)(minXf第七章 随机规划2（6.2）0,4721xba于是只要知道 和 的值，立即可以求得最优解。a但是，如果由于某种原因，原料甲中化学成分 、 的单位含量不稳AB定，其中 是矩形 内的均匀分布随机向量，则问Tb),( 13,41yx题（7.2）就成为随机线性规划问题了。由于引入了随机量，随机规划问题的分析与求解比普通数学规划问题要复杂大多。在处理随机规划问题时，人们最容易想到的方法也许是将模型中的随机变量用它们的期望值来代，从而得到确定性的数学规划模型，再去求解。事实上，过去许多确定性数学规划正是这样建立起来的，但是应当指出，这种处理方法在实际问题中并不总可行的。
4、为了说明这一点，我们不妨用此方法试解例 1 中的问题。容易求得， （6.3）TTbaE)3/2,5(),()将此值代入问题（7.2） ，得到确定线性规划模型如下：21)(minxXf（6.4）0,432751x可以求得此问题的唯一最优解为， （6.5）TTxX)1/32,/8(),(*21*于是以此 作为原随机线性规划问题（7.2）的最优解。可是，由于问题*（7.2）中的 是随机向量，我们自然希望知道，上述 是问题（7.2）Tba),( *X的最优解这一事件的概率有多大？是问题（7.2）的可行解这一事件的概率有多大？然而，我们发现， ， （6.6）4/13,/5),(7*2*21baPxxbT
5、第七章 随机规划3也即， 对问题（7.2）是可行解以 0.75 的概率是不可能的，只有 0.25 的*X可能性，这个解显然是不可用的。这个例子说明，用上述方法处理随机规划问题时应当十分谨慎。随机规划问题可以大致分为两种类型：被动型和主动型。被动型即所谓“等待且看到（wait and see） ”模型，即决策者等待着观察问题中随机变量的实现，然后适当地利用这些实现的信息作出决策，分布问题即属于此种类型。主动型即所谓“这里且现在（here and now） ”模型，决策者必须在没有机变量的实现的信息的情况下就作出决策，二阶段问题和机会约束规划均属于这种类型。 第二节 分布问题一、分布问题的提法例
6、1 设某工厂生产几种产品，需要用 种原料。第 种产品对第 种原mji料的单位需要量为 ，第 种原料的拥有量为 ，第 种产品的单位利润为ijai ib，试问如何安排各产品的生产量 （ ） ，以使的在现有条件下利jc jx),.1n润最大？容易列出这个问题的线性规划模型为 njjxcXf1)(max（6.7）njxmibjinji,.,0,1进一步考虑后，发现上述模型中的系数 总存在误差，故认为 是服从正ijaija态分布的随机变量；而单位利润系数 亦可能随市场价格波动而变化，此jc外原料拥有量 也可能因运输、保管等原因而发生短缺。于是，上述系数ib均可视为随机变量，记为 ， ， ， （ ） 。)
7、(waijj)(wbi njmi,.1;,.为了合理安排生产，显然希望知道，在各种可能的情况下， 的值)(axXf是什么，也即希望知道 的分布如何，或者希望知道 的数)(mxXf学期望是多少。第七章 随机规划4也就是说，对于每个样本 求解一个线性规划问题wnjjxcXf1)()(max， （6.8）njxmiwbjinjij,.,0,.)()(1然后再求 的分布。这就是本节将要讨论的分部问题。)(maxXf一般地，所谓分布问题就是对于每个样本 求解一个线性规划问题wXCw)(min)(， （6.9）0XbA并求 的分布函数或其他概率特征。)(w上述问题中， 为随机矩阵， 和 分别随机向量。显然
8、为使)(w)(wbc上述分布问题在数学上有意义，首先要求 必须是一个随机变量，即是概率空间 上的 Borel 可测函数。对此有如下定理。)(),(P定理 1 在上述分部问题中，最优目标函数值 是一个随机变量，并)(且适当选择后可以找到该问题的一个最优解 为随机向量。*wX随着 的变化，问题（7.9）的最优目标函数值 可能有限，也可能w )(为无穷大。如果 取 活 的概率大于 0，则 的数学期望及其它)(概率特征均不存在，从而该问题在许多情况下将无实际意义。因此，我们感兴趣的是： 的情况，此时问题的最优值称为无缺陷1)(:(wP的分布。对于分部问题可以像对待普通线性规划那样按照参数规划的思路来讨
9、论和求解，比如单纯形法、灵敏度分析等。第七章 随机规划5第三节 期望值模型在期望约束下，使得目标函数的期望值达到最优的数学规划称为期望值模型。期望值模型是数学规划中常见的形式之一，如期望费用极小化，期望值模型极大化问题等等。首先考虑报童问题。报童需要每天提前到邮局定购报纸并确定所定购的报纸数量 分，每份价格为 元。已经知道每份报纸的售价为 元。如果xc a报童没有卖完当天的报纸，则回收中心以极低的价格 元回收报纸。假设b每天报纸的需求量为 ，若 ，则每天报纸的剩余量为 ，否则为x x0。这样报童的受益为， （6.10）xbaxcbf ,)()(,),(在实际问题中，报童的需求量 通常是随机变量
10、，从而导致效益函数也是随机变量。既然不能准确地预测出订购 份报纸的实际收益，),(xf一个自然的方法就是考虑期望收益, （6.11）xx dcadbacbfE )()()(),(0其中 表示期望值算子， 表示需求量 的概率密度函数。报童问题就是寻找最优的定购数量 使期望收益 达到最大值，这是一个典型x),(fE的期望值模型。一、期望算子假设 维随机向量 的概率密度函数为 ，则随机向量 的期望值定t)(义为， （6.12）tRdE)(通常也称其为均值设 为定义在 上的实函数，则 是一个随机变量，其期望值ft )(f可以通过下式来计算：)(E第七章 随机规划6， （6.13）tRdffE)()(期
11、望值算子有如下的基本性质：若 ，其中 和 是常数，则baab， （6.14）E更一般的情况，设 是 个随机变量，且期望值 （ ）n,.21 iEn,.21存在，则有， （6.15）. 2121 nnEE设 是 个相互独立的随机变量，且期望值n,.21（ ）存在，则有iE， （6.16）.2121 nnEE二、期望值模型单目标期望值模型的一般形式为， （6.17）qkXhEpjgtsfkj ,.21,0),(.),(max其中 是一个 维决策向量， 是一个 维随机向量，其概率密度函数为Xnt， 是目标函数， 和 是随机约束函数， ，)(),f ),(gj ),(Xhk pj,.21qk.2,1由
12、于tRdXffE)(,),(， ， （6.18）tjjgg pj,.21，tRkkhh)(,),( qk一个可行解 是期望模型最优解，如果对于任意的可行解 ，有*X X成立。),(),(*fEf第七章 随机规划7第四节 机会约束规划作为第二种随机规划，机会约束规划（Chance Constrained Programming）主要是针对约束条件中含有随机变量，且必须在观察到随机变量的实现之前作出决策的情况。考虑到所做的决策在不利情况发生时可能不满足约束条件，而采用一种原则：即允许所作决策在一定程度上不满足约束条件，但是该决策应使约束条件成立的概率不小于某一个置信水平 。求解机会约束规划的传统方
13、法是根据事先给定的置信水平，把机会约束规划化为各自的确定等价类，然后用传统的方法求解其等价的确定性模型。对一些特殊的情况，机会约束规划问题确实可以化为确定性数学规划问题，但对较复杂的机会约束规划问题，通常很难做到这一点。然而，随着计算机的高速发展，一些革新算法如遗传算法的提出，使得复杂的机会约束规划问题可以不必通过转化为确定性数学规划而直接得到解决。一、机会约束规划模型考虑带有随机参数的数学规划模型， （6.19）pjXgtsfj ,.21,0),(.),(max其中 是一个 维决策向量， 是一个随机向量， 是目标函数，Xn ),(Xf是随机约束函数， 。),(gj j,.但是这个模型由于还有随机参数，意义不很明确。机会约束规划模型， （6.20）,.21,0),(.maxpjXgPfftsfj其中 和 分别是事先给定的置信水平。第七章 随机规划8一个点 是可行的当且仅当 ，即违反约束X ,.21,0),(pjXgPj条件的概率小于 。)1(无论何种随机参数 和何种函数形式 ，对每一个给定的决策 ，f X都是随机变量，其概率密度函数用 表示，这种可能有多少),(f )(,fXf个 使得 成立。从极大化目标值 的观点看，我们所要的),(fXfP目标值 应该是目标函数 在保证置信水平至少是 时所取的最大值，),(X即， （6.21）),(maxffPf.
