随机规划

1第二讲随机规划第一节基本概念1、问题的提出许多实际决策问题，尤其是比较复杂的决策问题，可以建立如下的线性规划模型：.0,...,,............min11221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatosubjectxcxcxc（1.1）用矩阵向量分析法，简化问题（1.1）得：0..minxbAxtsxcT（1.2）线性规划模型，在工业生产、运输业、农业、能源、生态、工程等领域都有广泛（典型）的应用。在问题（1.1）中系数jc（例如价格因素）、ija（比如生产率）、jb（比如需求量或存储能力）假设都已知为实数，这样我们的任务就是：寻找满足约束条件的决策变量jx（比如投入因素、生产率水平、能源流），使这一组合达到最优。显然，在现实生活中，如果相关的函数（例如，费用函数或生产函数）关于决策变量是线性的，那么模型（1.1）就能够合理的描述现实生活中的问题。如果现实中不是这样2的，比如，因为产品的边际成本（边际成本指的是每一单位新增生产的产品（或者购买的产品）带来到总成本的增量）的增长或边际报酬的减少，我们就需要更一般的形式来建立问题的模型，如下：.,...,1,0)(..)(min0niIRXxmixgtsxg（1.3）形式如（1.3）的问题就是一个数学规划问题。这里的集合X以及函数miIRIRgni,...,0,:可以理解为是在建模过程中给出的。在许多模型建立过程中（如问题(1.1)和(1.3)），若系数iijjbac,,或函数ig（和集合X）分别为给定值，这是不合理的。比如说，在水电发电站，流入发电站蓄水池的流水量，及运输网络中各个节点的需求量等等的因素，在建模的过程中，通常都作为不确定的参数。在一个生产问题中，未来的生产率，用概率分布来描述是最好的。但在建模过程中，这些参数真实值的不确定性，并不能用他们的平均值或别的估计值来消除（即真实值与平均值/估计值存在偏差）。就是说，在考虑实际情况的时候，问题（1.1）、（1.3）的模型，可能并不适合来解决更实际的问题。在这一章我们着重并尽可能的阐明，对于实际生活中的决策问题，需要扩大建模范围的必要性。在数学规划中引入随机性是很自然的事情。在模型中的系数iijjbac,,常常代表价格、成本、需求量、资源数量、经济指标等参数。由于各种不确定性因素的影响，这些参数经常出现波动。例如，市场3上对某种商品的需求量一般无法精确的预知，只能作出大致的预测，某种产品的生产成本往往受原材料价格、劳动生产率等各种因素的影响而经常变化，这些变化与波动，在许多场合可以用一定的概率分布去描述。因此，在数学规划中引入随机变量，能够使模型更加符合实际情况，从而是的决策更加合理。例1某化工厂生产过程中需要A，B两种化学成分，现有甲、乙两种原材料可供选用。其中原料甲中化学成分A的单位含量为10/a，B的单位含量为3/a；原料乙中化学成分A的单位含量为10/1，B的单位含量为3/1。根据生产要求，化学成分A的总含量不得少于10/7个单位，化学成分A的总含量不得少于3/4个单位。甲、乙两种原料的价格相同，问如何采购原料，使得即满足生产要求，又是的成本最低？显而易见，这个问题可以用线性规划模型来描述。根据题意，设原料甲的采购数量为1x，原料乙的采购数量为2x，容易得到如下线性模型：21)(minxxXf0,047212121xxxbxxax（1.4）于是只要知道a和b的值，立即可以求得最优解。但是，如果由于某种原因，原料甲中化学成分A、B的单位含量不稳定，其中Tba),(是矩形}131,41{yx内的均匀分布随机向4量，则问题（1.4）就成为随机线性规划问题了。由于引入了随机量，随机规划问题的分析与求解比普通数学规划问题要复杂大多。在处理随机规划问题时，人们最容易想到的方法也许是将模型中的随机变量用它们的期望值来代，从而得到确定性的数学规划模型，再去求解。事实上，过去许多确定性数学规划正是这样建立起来的，但是应当指出，这种处理方法在实际问题中并不总可行的。为了说明这一点，我们不妨用此方法试解例1中的问题。容易求得TTbaEE)3/2,2/5(]),[()(，（1.5）将此值代入问题（1.4），得到确定线性规划模型如下：21)(minxxXf0,0432725212121xxxxxx（1.6）可以求得此问题的唯一最优解为TTxxX)11/32,11/18(),(*2*1*，（1.7）于是以此*X作为原随机线性规划问题（1.4）的最优解。可是，由于问题（1.4）中的Tba),(是随机向量，我们自然希望知道，上述*X是问题（1.4）的最优解这一事件的概率有多大？是问题（1.4）的可行解这一事件的概率有多大？然而，我们发现，54/1}3/2,2/5),{(}4,7),{(*2*1*2*1babaPxbxxaxbaPTT，（1.8）也即，*X对问题（1.4）是可行解以0.75的概率是不可能的，只有0.25的可能性，这个解显然是不可用的。这个例子说明，用上述方法处理随机规划问题时应当十分谨慎。随机规划问题可以大致分为两种类型：被动型和主动型。被动型即所谓“等待且看到（waitandsee）”模型，即决策者等待着观察问题中随机变量的实现，然后适当地利用这些实现的信息作出决策，分布问题即属于此种类型。主动型即所谓“这里且现在（hereandnow）”模型，决策者必须在没有机变量的实现的信息的情况下就作出决策，二阶段问题和机会约束规划均属于这种类型。2、分布问题分布问题的提法例1设某工厂生产几种产品，需要用m种原料。第j种产品对第i种原料的单位需要量为ija，第i种原料的拥有量为ib，第j种产品的单位利润为jc，试问如何安排各产品的生产量jx（),...,1nj），以使的在现有条件下利润最大？容易列出这个问题的线性规划模型为njjjxcXf1)(max6njxmibxajinjjij,...,1,0,...,1,1（1.9）进一步考虑后，发现上述模型中的系数ija总存在误差，故认为ija是服从正态分布的随机变量；而单位利润系数jc亦可能随市场价格波动而变化，此外原料拥有量ib也可能因运输、保管等原因而发生短缺。于是，上述系数均可视为随机变量，记为)(waij，jc)(w，)(wbi，w（njmi,...,1;,...,1）。为了合理安排生产，显然希望知道，在各种可能的情况下，)(maxXf的值是什么，也即希望知道)(maxXf的分布如何，或者希望知道)(maxXf的数学期望是多少。也就是说，对于每个样本w求解一个线性规划问题njjjxwcXf1)()(maxnjxmiwbxwajinjjij,...,1,0,...,1),()(1，（1.10）然后再求)(maxXf的分布。这就是本节将要讨论的分部问题。一般地，所谓分布问题就是对于每个样本w求解一个线性规划问题XwCw)(min)(0)()(XwbXwA，（1.11）7并求)(w的分布函数或其他概率特征。上述问题中，)(wA为随机矩阵，)(wb和)(wc分别随机向量。显然为使上述分布问题在数学上有意义，首先要求)(w必须是一个随机变量，即)(w是概率空间),,(PP上的Borel可测函数。对此有如下定理。定理1在上述分部问题中，最优目标函数值)(w是一个随机变量，并且适当选择后可以找到该问题的一个最优解)(*wX为随机向量。随着w的变化，问题（7.9）的最优目标函数值)(w可能有限，也可能为无穷大。如果)(w取活的概率大于0，则)(w的数学期望及其它概率特征均不存在，从而该问题在许多情况下将无实际意义。因此，我们感兴趣的是：1))(:(wwP的情况，此时问题的最优值称为无缺陷的分布。对于分部问题可以像对待普通线性规划那样按照参数规划的思路来讨论和求解，比如单纯形法、灵敏度分析等。3、期望值模型在期望约束下，使得目标函数的期望值达到最优的数学规划称为期望值模型。期望值模型是数学规划中常见的形式之一，如期望费用极小化，期望值模型极大化问题等等。首先考虑报童问题。报童需要每天提前到邮局定购报纸并确定所定购的报纸数量x分，每份价格为c元。已经知道每份报纸的售价为a元。如果报童没有卖完当天的报纸，则回收中心以极低的价格b元回8收报纸。假设每天报纸的需求量为，若x，则每天报纸的剩余量为x，否则为0。这样报童的受益为xbaxcbxxcaxf,)()(,)(),(，（1.12）在实际问题中，报童的需求量通常是随机变量，从而导致效益函数),(xf也是随机变量。既然不能准确地预测出订购x份报纸的实际收益，一个自然的方法就是考虑期望收益xxdxcadbaxcbxfE)()()(])()[()],([0，（3.2）其中E表示期望值算子，)(表示需求量的概率密度函数。报童问题就是寻找最优的定购数量x使期望收益)],([xfE达到最大值，这是一个典型的期望值模型。（1）期望算子假设t维随机向量的概率密度函数为)(，则随机向量的期望值定义为tRdE)(][，（1.13）通常也称其为均值设f为定义在tR上的实函数，则)(f是一个随机变量，其期望值))((fE可以通过下式来计算：tRdffE)()()]([，（1.14）9期望值算子有如下的基本性质：若ba，其中a和b是常数，则baEE][][，（1.15）更一般的情况，设n,...,,21是n个随机变量，且期望值][iE（ni,...,2,1）存在，则有][...][][]...[2121nnEEEE，（1.16）设n,...,,21是n个相互独立的随机变量，且期望值][iE（ni,...,2,1）存在，则有][]...[].[]....[2121nnEEEE，（1.17）（2）期望值模型单目标期望值模型的一般形式为qkXhEpjXgEtsXfEkj,...,2,1,0)],([,...,2,1,0)],([.)],([max，（1.18）其中X是一个n维决策向量，是一个t维随机向量，其概率密度函数为)(，),(Xf是目标函数，),(Xgj和),(Xhk是随机约束函数，pj,...,2,1，qk,...,2,1由于tRdXfXfE)(),()],([10tRjjdXgXgE)(),()],([，pj,...,2,1（1.19）tRkkdXhXhE)(),()],([，qk,...,2,1一个可行解*X是期望模型最优解，如果对于任意的可行解X，有)],([)],([*XfEXfE成立。4、机会约束规划作为第二种随机规划，机会约束规划（ChanceConstrainedProgramming）主要是针对约束条件中含有随机变量，且必须在观察到随机变量的实现之前作出决策的情况。考虑到所做的决策在不利情况发生时可能不满足约束条件，而采用一种原则：即允许所作决策在一定程度上不满足约束条件，但是该决策应使约束条件成立的概率不小于某一个置信水平。求解机会约束规划的传统方法是根据事先给定的置信水平，把机会约束规划化为各自的确定等价类，然后用传统的方法求解其等价的确定性模型。对一些特殊的情况，机会约束规划问题确实可以化为确定性数学规划问题，但对较复杂的机会约束规划问题，通常很难做到这一点。然而，随着计算机的高速发展，一些革新算法如遗传算法的提出，使得复杂的机会约束规划问题可以不必通过转化为确定性数学规划而直接得到解决。（1）机会约