随机规划.doc

第二讲随机规划
第一节基本概念
问题的提出
许多实际决策问题,尤其是比较复杂的决策问题,可以建立如下的线性规划模型:
()
用矩阵向量分析法,简化问题()得:
()
线性规划模型,在工业生产、运输业、农业、能源、生态、工程等领域都有广泛(典型)的应用。
在问题()中系数(例如价格因素)、(比如生产率)、(比如需求量或存储能力)假设都已知为实数,这样我们的任务就是:寻找满足约束条件的决策变量(比如投入因素、生产率水平、能源流),使这一组合达到最优。显然,在现实生活中,如果相关的函数(例如,费用函数或生产函数)关于决策变量是线性的,那么模型()就能够合理的描述现实生活中的问题。
如果现实中不是这样的,比如,因为产品的边际成本(边际成本指的是每一单位新增生产的产品(或者购买的产品)带来到总成本的增量)的增长或边际报酬的减少,我们就需要更一般的形式来建立问题的模型,如下:
()
形式如()的问题就是一个数学规划问题。
这里的集合以及函数可以理解为是在建模过程中给出的。
在许多模型建立过程中(如问题()和()),若系数或函数(和集合X)分别为给定值,这是不合理的。比如说,在水电发电站,流入发电站蓄水池的流水量,及运输网络中各个节点的需求量等等的因素,在建模的过程中,通常都作为不确定的参数。在一个生产问题中,未来的生产率,用概率分布来描述是最好的。但在建模过程中,这些参数真实值的不确定性,并不能用他们的平均值或别的估计值来消除(即真实值与平均值/估计值存在偏差)。就是说,在考虑实际情况的时候,问题()、()的模型,可能并不适合来解决更实际的问题。在这一章我们着重并尽可能的阐明,对于实际生活中的决策问题,需要扩大建模范围的必要性。
在数学规划中引入随机性是很自然的事情。在模型中的系数
常常代表价格、成本、需求量、资源数量、经济指标等参数。由于各种不确定性因素的影响,这些参数经常出现波动。例如,市场上对某种商品的需求量一般无法精确的预知,只能作出大致的预测,某种产品的生产成本往往受原材料价格、劳动生产率等各种因素的影响而经常变化,这些变化与波动,在许多场合可以用一定的概率分布去描述。因此,在数学规划中引入随机变量,能够使模型更加符合实际情况,从而是的决策更加合理。
例1 某化工厂生产过程中需要,两种化学成分,现有甲、乙两种原材料可供选用。其中原料甲中化学成分的单位含量为,的单位含量为;原料乙中化学成分的单位含量为,的单位含量为。根据生产要求,化学成分的总含量不得少于个单位,化学成分的总含量不得少于个单位。甲、乙两种原料的价格相同,问如何采购原料,使得即满足生产要求,又是的成本最低?
显而易见,这个问题可以用线性规划模型来描述。根据题意,设原料甲的采购数量为,原料乙的采购数量为,容易得到如下线性模型:

()
于是只要知道和的值,立即可以求得最优解。
但是,如果由于某种原因,原料甲中化学成分、的单位含量不稳定,其中是矩形内的均匀分布随机向量,则问题()就成为随机线性规划问题了。
由于引入了随机量,随机规划问题的分析与求解比普通数学规划问题要复杂大多。在处理随机规划问题时,人们最容易想到的方法也许是将模型中的随机变量用它们的期望值来代,从而得到确定性的数学规划模型,再去求解。事实上,过去许多确定性数学规划正是这样建立起来的,但是应当指出,这种处理方法在实际问题中并不总可行的。为了说明这一点,我们不妨用此方法试解例1中的问题。容易求得
, ()
将此值代入问题(),得到确定线性规划模型如下:

()
可以求得此问题的唯一最优解为
, ()
于是以此作为原随机线性规划问题()的最优解。可是,由于问题()中的是随机向量,我们自然希望知道,上述是问题()的最优解这一事件的概率有多大?是问题()的可行解这一事件的概率有多大?然而,我们发现,
, ()
也即,对问题(),,这个解显然是不可用的。这个例子说明,用上述方法处理随机规划问题时应当十分谨慎。
随机规划问题可以大致分为两种类型:被动型和主动型。被动型即所谓“等待且看到(wait and see)”模型,即决策者等待着观察问题中随机变量的实现,然后适当地利用这些实现的信息作出决策,分布问题即属于此种类型。主动型即所谓“这里且现在(here and now)”模型,决策者必须在没有机变量的实现的信息的情况下就作出决策,二阶段问题和机会约束规划均属于这种类型。

分布问题
分布问题的提法
例1 设某工厂生产几种