文档介绍：1
第二讲随机规划
第一节基本概念
1、问题的提出
许多实际决策问题，尤其是比较复杂的决策问题，可以建立如下的线性规划模型：
min{?x+cx+...+cx
1122nn
subjectto
ax+ax+...+ax
，得到确定线性规划模型如下：
minf(X)=
x+x
12
10
32
5
x+x>7
12
2
)
x+x>4
12
x>0,x>0
12
可以求得此问题的唯一最优解为
X*=(x*,x*)T=(18/11,32/11)t,()
12
于是以此x*作为原随机线性规划问题（）的最优解。可是，由于问题（）中的（a,b）T是随机向量，我们自然希望知道，上述X*是问题（）的最优解这一事件的概率有多大？是问题（）的可行解这一事件的概率有多大？然而，我们发现，
13
13
P{(a,b)Tax*+x*>7,bx*+x*>4}
)
1212
=P{(a,b)Ta>5/2,b>2/3}=1/4
也即，X*对问题()，
的可能性，这个解显然是不可用的。这个例子说明，用上述方法处理
随机规划问题时应当十分谨慎。
随机规划问题可以大致分为两种类型：被动型和主动型。被动型即所谓“等待且看到(waitandsee)”模型，即决策者等待着观察问题中随机变量的实现，然后适当地利用这些实现的信息作出决策，分布问题即属于此种类型。主动型即所谓“这里且现在(hereandnow)”模型，决策者必须在没有机变量的实现的信息的情况下就作出决策，二阶段问题和机会约束规划均属于这种类型。
2、分布问题
分布问题的提法
例1设某工厂生产几种产品，需要用m种原料。第j种产品对第i种原料的单位需要量为a，第i种原料的拥有量为b.，第j种产品的iji
单位利润为c，试问如何安排各产品的生产量x(j=1,...,n))，以使
jj
的在现有条件下利润最大？
容易列出这个问题的线性规划模型为
maxf(X)=2cx
jj
j=1
14
兰ax<b,i=1,・・・,mijji
j=1
x>0,j=1,...,n
j
)
进一步考虑后，发现上述模型中的系数a总存在误差，故认为a是服
ijij
从正态分布的随机变量；而单位利润系数c亦可能随市场价格波动而
j
变化，此外原料拥有量b也可能因运输、保管等原因而发生短缺。于
i
是，上述系数均可视为随机变量，记为a(w)，c(w)，b(w)，weQijji
(i=1,...,m;j=1,...,n)。为了合理安排生产，显然希望知道，在各种可能的情况下，maxf(X)的值是什么，也即希望知道maxf(X)的分布如何，或者希望知道maxf(X)的数学期望是多少。
也就是说，对于每个样本weQ求解一个线性规划问题
maxf(X)=£c(w)x
jj
j=1
兰a(w)x=b(w),i=1,.・・,m
ijji
j=1
x>0,j=1,...,n
j
)
然后再求maxf(X)的分布。这就是本节将要讨论的分部问题。
一般地，所谓分布问题就是对于每个样本weQ求解一个线性规
划问题
g(w)=minC(w)X
A(w)X=b(w)X>0
)
15
16
并求g(w)的分布函数或其他概率特征。
上述问题中，A(w)为随机矩阵，b(w)和c(w)分别随机向量。显然为使上述分布问题在数学上有意义，首先要求g(w)必须是一个随机变量,即g(W)是概率空间(Q,P,P)上的Borel可测函数。对此有如下定理。
定理1在上述分部问题中，最优目标函数值g(w)是一个随机变量，并且适当选择后可以找到该问题的一个最优解X*(w)为随机向量。
随着w的变化，问题()的最优目标函数值g(w)可能有限，也可能为无穷大。如果g(w)取活7的概率大于0则g(w)的数学期望及其它概率特征均不存在，从而该问题在许多情况下将无实际意义。因此，我们感兴趣的是：P(w:-8<g(w)<+8)=1的情况，此时问题的最优值称为无缺陷的分布。
对于分部问题可以像对待普通线性规划那样按照参数规划的思路来讨论和求解，比如单纯形法、灵敏度分析等。
3、期望值模型
在期望约束下，使得目标函数的期望值达到最优的数学规划称为期望值模型。期