第六章 随机规划

第六章随机规划

第一节问题的提出

随机规划所研究的对象是含有随机因素的数学规划问题。例如，我们

熟悉的线性规划问题

minf(X)=CX

AX=b(6.1)

X>0

如果其中的A，b，C的元素中部份的或者全部的是随机变量，则称其为随

机线性规划问题。

在数学规划中引入随机性是很自然的事情。在模型中的A，b，C的元

素往往代表价格、成本、需求量、资源数量、经济指标等参数。由于各种

不确定性因素的影响，这些参数时常浮现波动。例如，市场上对某种商品

的需求量普通无法精确的预知，只能作出大致的预测，某种产品的生产成

本往往受原材料价格、劳动生产率等各种因素的影响而时常变化，这些变

化与波动，在许多场合可以用一定的概率分布去描述。因此，在数学规划

中引入随机变量，能够使模型更加符合实际情况，从而是的决策更加合理。

例1某化工厂生产过程中需要A，B两种化学成份，现有甲、乙两种

原材料可供选用。其中原料甲中化学成份A的单位含量为a/10,B的单位含

量为a/3；原料乙中化学成份A的单位含量为1/10,B的单位含量为1/3。根

据生产要求，化学成份A的总含量不得少于7/10个单位，化学成份A的总含

量不得少于4/3个单位。甲、乙两种原料的价格相同，问如何采购原料，使

得即满足生产要求，又是的成本最低？

显而易见，这个问题可以用线性规划模型来描述。根据题意，设原料

甲的采购数量为x，原料乙的采购数量为x，容易得到如下线性模型：

12

minf(X)=x+x

12

ax+x>7

12

bx+x>4(6.2)

12

x>0,x>0

12

1

第七章随机规划

于是只要知道a和b的值，即将可以求得最优解。

但是，如果由于某种原因，原料甲中化学成份A、B的单位含量不稳定,

其中a=(a,b)T是矩形｛KX44,内的均匀分布随机向量，则问题(7.2)

3

就成为随机线性规划问题了。

由于引入了随机量，随机规划问题的分析与求解比普通数学规划问题

要复杂大多。在处理随机规划问题时，人们最容易想到的方法也许是将模

型中的随机变量用它们的期望值来代，从而得到确定性的数学规划模型，

再去求解。事实上，过去许多确定性数学规划正是这样建立起来的，但是

应当指出，这种处理方法在实际问题中并不总可行的。为了说明这一点，

我们不妨用此方法试解例1中的问题。容易求得

E(g)=E[(a,b)T]=(5/2,2/3)T，(6.3)

将此值代入问题(7.2),得到确定线性规划模型如下：

minf(X)=x+x

12

5

—x+x>7

212

o

—x+x>4(6.4)

3i2

x>0,x>0

12

可以求得此问题的惟一最优解为

X*=(X-,X-)T=(18/11,32/11)T,(6.5)

12

于是以此X•作为原随机线性规划问题(7.2)的最优解。可是，由于问题(7.2)

中的(a,加是随机向量，我们自然希翼知道，上述X•是问题(7.2)的最优解

这一事件的概率有多大？是问题(7.2)的可行解这一事件的概率有多大？

然而，我们发现,

P{(a,b)T^x-+X->7,bx♦+x->4}

212(6.6)

=P{(a,b)T|a>5/2,b>2/3}=1/4

也即，X,对问题(7.2)是可行解以0.75的概率是不可能的，惟独0.25的

可能性，这个解显然是不可用的。这个例子说明，用上述方法处理随机规

2

第七章随机规划

划问题时应当十分谨慎。

随机规划问题可以大致分为两种类型：被动型和主动型。被动型即所

谓“等待且看到(waitandsee)”模型，即决策者等待着观察问题中随机变

量的实现，然后适当地利用这些实现的信息作出决策，分布问题即属于此

种类型。主动型即所谓“这里且现在(hereandnow)”模型，决策者必须在

没有机变量的实现的信息的情况下就作出决策，二阶段问题和机会约束规

划均属于这种类型。

第二节分布问题

一、分布问题的提法

例1设某工厂生产几种产品，需要用m种原料。第j种产品对第i种原

料的单位需要量为a，第i种原料的拥有量为b,第j种产品的单位利润为

c,试问如何安排等产品的生产量x(j=1,...,n)),以使的在现有条件下利

润最大？

容易列出这个问题的线性规划模型为

max/(X)=^cx

-nax<b,i=m

ijji(6.7)

j=1

x>0,j=1,...,n

i

进一步考虑后，发现上述模型中的系数a总存在误差，故认为a是服从正

态分布的随机变量；而单位利润系数c速可能随市场价格波动而变化，此

保管等皮于是发生短缺。于是，上述系数均

外原料拥有量b:也可能因运输、

可视为随机变高记为a(w)，

c(w)，b(w)w=C(i=1j=1)o

为了合理安排生产，显然希翼知道，在各种可能的情况下，maxf(X)的值是

什么，也即希翼知道maxf(X)的分布如何，或者希翼知道maxf(X)的数学期

望是多少。

3

第七章随机规划

也就是说，对于每一个样本wq求解一个线性规划问题

%蚂c娜

ma(w)x=b(w),i=

>ij>,(6.8)

i-1

x>0,j=1

j

然后再求maxf(X)的分布。这就是本节将要讨论的分部问题。

普通地，所谓分布问题就是对于每一个样本we。求解一个线性规划问

题

q(w)=minC(w)X

A(w)X=b(w)(69)

X20

并求七(w)的分布函数或者其他概率特征。

上述问题中，A(w)为随机矩阵，b(w)和c(w)分别随机向量。显然为使上

述分布问题在数学上故意义，首先要求弓(w)必须是一个随机变量，即1(w)是

概率空间(Q,p,p)上的Borel可测函数。对此有如下定理。

定埋1在上述分部问题中，最优目标函数值匕(w)是一个随机变量，并

且适当选择后可以找到该问题的一个最优解X*(w)为随机向量。

随着W的变化，问题(7.9)的最优目标函数值g(W)可能有限，也可能

为无穷大。如果之(w)取+/舌一oc的概率大于0,则z(w)的数学期望及其它概

率特征均不存在，从而该问题在许多情况下将无实际意义。因此，我们感

兴趣的是：P(w：70V(w)〈用)=1的情况，此时问题的最优值称为无缺陷的

分布。

对于分部问题可以像对待普通线性规划那样按照参数规划的思路来讨

论和求解，比如单纯形法、灵敏度分析等。

4

第七章随机规划

第三节期望值模型

在期望约束下，使得目标函数的期望值达到最优的数学规划称为期望

值模型。期望值模型是数学规划中常见的形式之一，如期望费用极小化，

期望值模型极大化问题等等。

首先考虑报童问题。报童需要每天提前到邮局定购报纸并确定所定购

的报纸数量X分，每份价格为c元。已经知道每份报纸的售价为a元。如果

报童没有卖完当天的报纸，则回收中心以极低的价格b元回收报纸。假设每

天报纸的需求量为飞，若x>飞，则每天报纸的剩余量为x-飞，否则为Oo这

样报童的受益为

f（%飞）二心-淤'三;，（6.10）

l（b-c）x+（a-b）飞，x>飞

在实际问题中，报童的需求量飞通常是随机变量，从而导致效益函数

f（x,飞）也是随机变量。既然不能准确地预测出订购x份报纸的实际收益，一

个自然的方法就是考虑期望收益

E［f（x,飞）］=J［（b-c）x+（a-b）飞］0（飞）d飞+jw（a-c）xO（飞）d飞,（6.11）

0x

其中E表示期望值算子，0仆）表示需求量飞的概率密度函数。报童问题就是

寻觅最优的定购数量x使期望收益E［f（x,飞）］达到最大值，这是一个典型的期

望值模型。

一、期望算子

假设t维随机向量飞的概率密度函数为0（飞），则随机向量飞的期望值定义

为

Ensi=j飞0（飞）d飞，（6.12）

田

通常也称其为均值

设f为定义在Rt上的实函数，则f（飞）是一个随机变量，其期望值E（f（飞））

可以通过下式来计算：

E［f（飞）］=jf（飞）0（飞）d飞，（6.13）

5

第七章随机规划

期望值算子有如卜的基本性质：若n二a飞+b,其中a和b是常数，则

E［n］=aEn＜］+b，（6.14）

更普通的情况，设飞，飞，…，飞是n个随机变量，且期望值E［飞］（i=1,2,...,n）存

12ni

在，则有

E［飞+飞+…+飞］=E［飞］+E［飞］+...+ER卜（6.15）

12n12n

设飞，飞，…，飞是n个相互独立的随机变量，且期望值E［飞］（i=）

12ni

存在，则有

E"书.用］=E［^］.Er^］...EnS］，（6.16）

二、期望值模向2n

单目标期望值模型的普通形式为

zimaxE［f（X飞）］

/s・t,（6.17）

（X.飞］VO.J=l,2，…,p

E|/J（X3］=0,A:=1,2，…,q

k

其中x是一个n维决策向量，飞是一个t维随机向量，其概率密度函数为0飞），

f（X,飞）是目标函数，g（X,飞）和h（X,飞）是随机约束函数,j=1,2,...,p，k=

jk

由于

♦（X,飞）］=jf（x飞）0OS）d飞

R

E［g（X飞）］二jg（X,飞）（O）d飞，j=i,2,...,p，（6.18）

i.R：j

E［h（X飞）］=jh（X,飞）0（飞）d飞，k=1,2,...,q

kRik

一个可行解X•是期望模型最优解，如果对于任意的可行解X，有

E［f（X\飞）］之E［f（X，飞）］成立。

6

第七章随机规划

第四节机会约束规划

作为第二种随机规划，机会约束规划（ChanceConstrainedProgramming）

主要是针对约束条件中含有随机变量，且必须在观察到随机变量的实现之

前作出决策的情况。考虑到所做的决策在不利情况发生时可能不满足约束

条件，而采用一种原则：即允许所作决策在一定程度上不满足约束条件，

但是该决策应使约束条件成立的概率不小于其一个置信水平a。

求解机会约束规划的传统方法是根据事先给定的置信水平，把机会约

束规划化为各自的确定等价类，然后用传统的方法求解其等价的确定性模

型。对一些特殊的情况，机会约束规划问题确实可以化为确定性数学规划

问题，但对较复杂的机会约束规划问题，通常很难做到这一点。然而，随

着计算机的高速发展，一些革新算法如遗传算法的提出，使得复杂的机会

约束规划问题可以不必通过转化为确定性数学规划而直接得到解决。

一、机会约束规划模型

考虑带有随机参数的数学规划模型

（Imaxf（X,飞）

/