) 是随机约束函数887700葡京登陆

当前位置:887700葡京手机版 > 887700葡京登陆 > ) 是随机约束函数887700葡京登陆
作者: 887700葡京手机版|来源: http://www.djwjd.com|栏目:887700葡京登陆

文章关键词:887700葡京手机版,随机规划

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  第八章 随机规划 第八章 随机规划 第一节 问题的提出 随机规划所研究的对象是含有随机因素的数学规划问题。例如,我们 熟悉的线性规划问题 min f ( X )  CX AX  b (8.1) X  0 b 如果其中的 , , 的元素中部分的或全部的是随机变量,则称其为随机 A C 线性规划问题。 b 在数学规划中引入随机性是很自然的事情。在模型中的 , , 的元 A C 素常常代表价格、成本、需求量、资源数量、经济指标等参数。由于各种 不确定性因素的影响,这些参数经常出现波动。例如,市场上对某种商品 的需求量一般无法精确的预知,只能作出大致的预测,某种产品的生产成 本往往受原材料价格、劳动生产率等各种因素的影响而经常变化,这些变 化与波动,在许多场合可以用一定的概率分布去描述。因此,在数学规划 中引入随机变量,能够使模型更加符合实际情况,从而是的决策更加合理。 例 1 某化工厂生产过程中需要 , 两种化学成分,现有甲、乙两种 A B 原材料可供选用。其中原料甲中化学成分 的单位含量为 , 的单位含 A a /10 B 量为 ;原料乙中化学成分 的单位含量为 , 的单位含量为 。根 a / 3 A 1/10 B 1/ 3 据生产要求,化学成分 的总含量不得少于 个单位,化学成分 的总含 A 7 /10 A 量不得少于 个单位。甲、乙两种原料的价格相同,问如何采购原料,使 4 / 3 得即满足生产要求,又是的成本最低? 显而易见,这个问题可以用线性规划模型来描述。根据题意,设原料 甲的采购数量为 ,原料乙的采购数量为 ,容易得到如下线 min f ( X )  x  x 1 2 ax  x  7 1 2 bx  x  4 (8.2) 1 2 x1  0,x2  0 1 第八章 随机规划 b 于是只要知道 和 的值,立即可以求得最优解。 a 但是,如果由于某种原因,原料甲中化学成分 、 的单位含量不稳定, A B 其中 (a,b)T 是矩形{1  x  4, 1  y 1} 内的均匀分布随机向量,则问题(8.2) 3 就成为随机线性规划问题了。 由于引入了随机量,随机规划问题的分析与求解比普通数学规划问题 要复杂大多。在处理随机规划问题时,人们最容易想到的方法也许是将模 型中的随机变量用它们的期望值来代,从而得到确定性的数学规划模型, 再去求解。事实上,过去许多确定性数学规划正是这样建立起来的,但是 应当指出,这种处理方法在实际问题中并不总可行的。为了说明这一点, 我们不妨用此方法试解例1 中的问题。容易求得 E()  E[( T T , (8.3) a,b) ]  (5/ 2, 2 / 3) 将此值代入问题(7.2 ),得到确定线性规划模型如下: min f ( X )  x  x 1 2 5 x  x  7 1 2 2 2 x  x  4 (8.4) 1 2 3 x1  0,x2  0 可以求得此问题的唯一最优解为 * * * T T , (8.5) X  (x , x )  (18/11, 32 /11) 1 2 * X 于是以此 作为原随机线)的最优解。可是,由于问题(8.2) T X * 中的(a,b) 是随机向量,我们自然希望知道,上述 是问题(8.2)的最优解 这一事件的概率有多大?是问题(8.2)的可行解这一事件的概率有多大? 然而,我们发现, P{(a,b)T ax*  x*  7, bx*  x*  4} 1 2 1 2 , (8.6)  P{(a,b)T a  5 / 2, b  2 / 3} 1/ 4 * X 也即, 对问题(8.2)是可行解以0.75 的概率是不可能的,只有0.25 的 可能性,这个解显然是不可用的。这个例子说明,用上述方法处理随机规 2 第八章 随机规划 划问题时应当十分谨慎。 随机规划问题可以大致分为两种类型:被动型和主动型。被动型即所 谓“等待且看到(wait and see )”模型,即决策者等待着观察问题中随机变 量的实现,然后适当地利用这些实现的信息作出决策,分布问题即属于此 种类型。主动型即所谓“这里且现在(here and now )”模型,决策者必须在 没有机变量的实现的信息的情况下就作出决策,二阶段问题和机会约束规 划均属于这种类型。 第二节 分布问题 一、分布问题的提法 j 例 1 设某工厂生产几种产品,需要用 种原料。第 种产品对第 种原 m i j 料的单位需要量为 ,第 种原料的拥有量为 ,第 种产品的单位利润为 a i b ij i j 1,...,n) ,试问如何安排各产品的生产量 ( ),以使的在现有条件下利 c x j j 润最大? 容易列出这个问题的线性规划模型为 n max f ( X )  c x j j j 1 n a x b , i 1,...,m j 1 ij j i (8.7) x j  0, j 1,...,n 进一步考虑后,发现上述模型中的系数 总存在误差,故认为 是服从正 a a ij ij 态分布的随机变量;而单位利润系数 亦可能随市场价格波动而变化,此 c j b 外原料拥有量 也可能因运输、保管等原因而发生短缺。于是,上述系数均 i (w) b (w) i 1,...,m;j 1,...,n 可视为随机变量,记为a (w) ,cj , i ,w  ( )。 ij 为了合理安排生产,显然希望知道,在各种可能的情况下,max f (X ) 的值是 什么,也即希望知道max f ( X ) 的分布如何,或者希望知道max f ( X ) 的数学期 望是多少。 3 第八章 随机规划 也就是说,对于每个样本w  求解一个线性规划问题 n max f ( X )  c (w)x j j j 1 n a (w)x b (w), i 1,...,m j 1 ij j i , (8.8) x j  0, j 1,...,n 然后再求max f ( X ) 的分布。这就是本节将要讨论的分部问题。 一般地,所谓分布问题就是对于每个样本w  求解一个线性规划问题 (w)  min C(w) X A(w) X  b(w) , (8.9) X  0 (w) 并求 的分布函数或其他概率特征。 A(w) b(w) c(w) 上述问题中, 为随机矩阵, 和 分别随机向量。显然为使上 述分布问题在数学上有意义,首先要求 必须是一个随机变量,即 是 (w) (w) 概率空间(, P , P) 上的Borel 可测函数。对此有如下定理。 (w) 定理 1 在上述分部问题中,最优目标函数值 是一个随机变量,并 且适当选择后可以找到该问题的一个最优解X * (w) 为随机向量。 w (w) 随着 的变化,问题(8.9 )的最优目标函数值 可能有限,也可能 (w)    (w) 为无穷大。如果 取 活 的概率大于0 ,则 的数学期望及其它概 率特征均不存在,从而该问题在许多情况下将无实际意义。因此,我们感 兴趣的是:P(w :  (w)  ) 1 的情况,此时问题的最优值称为无缺陷的 分布。 对于分部问题可以像对待普通线性规划那样按照参数规划的思路来讨 论和求解,比如单纯形法、灵敏度分析等。 4 第八章 随机规划 第三节 期望值模型 在期望约束下,使得目标函数的期望值达到最优的数学规划称为期望 值模型。期望值模型是数学规划中常见的形式之一,如期望费用极小化, 期望值模型极大化问题等等。 首先考虑报童问题。报童需要每天提前到邮局定购报纸并确定所定购 的报纸数量 分,每份价格为 元。已经知道每份报纸的售价为 元。如果 x c a b 报童没有卖完当天的报纸,则回收中心以极低的价格 元回收报纸。假设每 天报纸的需求量为 ,若x  ,则每天报纸的剩余量为 ,否则为0 。这  x  样报童的受益为  (a c)x, x  f ( x,)   , (8.10) (b c)x (a b), x  在实际问题中,报童的需求量 通常是随机变量,从而导致效益函数  f ( x,) 也是随机变量。既然不能准确地预测出订购 份报纸的实际收益,一 x 个自然的方法就是考虑期望收益 x  E[ f ( x,)]  [(b c)x (a b)]()d (a c)x()d, (8.11)   0 x () 其中 表示期望值算子, 表示需求量 的概率密度函数。报童问题就是 E  x E[ f ( x,)] 寻找最优的定购数量 使期望收益 达到最大值,这是一个典型的期 望值模型。 一、期望算子  ()  假设 维随机向量 的概率密度函数为 ,则随机向量 的期望值定义 t 为 E[]  ()d , (8.12) t R 通常也称其为均值 f Rt f () E (f ()) 设 为定义在 上的实函数,则 是一个随机变量,其期望值 可以通过下式来计算: E [f ()] t f ()()d , (8.13) R 5 第八章 随机规划 b 期望值算子有如下的基本性质:若 ab ,其中 和 是常数,则 a E[]  aE[] b , (8.14) 更一般的情况,设 是 个随机变量,且期望值 ( )存 , ,..., n E[] i 1,2,...,n 1 2 n i 在,则有 E[  ...  ]  E[]  E[ ] ...  E[ ] ,887700葡京登陆 (8.15) 1 2 n 1 2 n 设 是 个相互独立的随机变量,且期望值 ( ) , ,..., n E[] i 1,2,...,n 1 2 n i 存在,则有 E[.... ]  E[].E[ ]...E[ ] , (8.16) 1 2 n 1 2 n 二、期望值模型 单目标期望值模型的一般形式为  max E[ f ( X ,)]   s.t  , (8.17) E[g j ( X ,)]  0, j 1,2,..., p E[h ( X ,)]  0, k 1,2,...,q  k n 其中 是一个 维决策向量,是一个 维随机向量,其概率密度函数为 , X  t () f ( X ,) j 1,2,..., p k 1,2,...,q 是目标函数, 和h ( X ,) 是随机约束函数, , g j ( X ,) k 由于 E [f (X ,)] t f (X ,)()d R E[g ( X ,)]  g ( X ,)()d,j 1,2,..., p , (8.18) j t j R E [h (X ,)] h (X ,)()d ,k 1,2,...,q k t k R * X 一个可行解 是期望模型最优解,如果对于任意的可行解 ,有 X E[f (X * ,)] E[f (X ,)] 成立。 6 第八章 随机规划 第四节 机会约束规划 作为第二种随机规划,机会约束规划(Chance Constrained Programming ) 主要是针对约束条件中含有随机变量,且必须在观察到随机变量的实现之 前作出决策的情况。考虑到所做的决策在不利情况发生时可能不满足约束 条件,而采用一种原则:即允许所作决策在一定程度上不满足约束条件, 但是该决策应使约束条件成立的概率不小于某一个置信水平 。  求解机会约束规划的传统方法是根据事先给定的置信水平,把机会约 束规划化为各自的确定等价类,然后用传统的方法求解其等价的确定性模 型。对一些特殊的情况,机会约束规划问题确实可以化为确定性数学规划 问题,但对较复杂的机会约束规划问题,通常很难做到这一点。然而,随 着计算机的高速发展,一些革新算法如遗传算法的提出,使得复杂的机会 约束规划问题可以不必通过转化为确定性数学规划而直接得到解决。 一、机会约束规划模型 考虑带有随机参数的数学规划模型  max f ( X ,)   s.t , (8.19)  g ( X ,)  0, j 1,2,..., p  j n f ( X ,) 其中 是一个 维决策向量,是一个随机向量, 是目标函数, X  g j ( X ,) 是随机约束函数,j 1,2,..., p 。 但是这个模型由于还有随机参数,意义不很明确。机会约束规划模型  max f   s.t  , (8.20)  P{ f ( X ,)  f }   P{g ( X ,)  0, j 1,2,..., p}   j   其中 和 分别是事先给定的置信水平。 一个点 是可行的当且仅当 ,即违反约束条 X P{g j ( X ,) 0, j 1,2,..., p}  件的概率小于(1) 。  f 无论何种随机参数 和何种函数形式 ,对每一个给定的决策 , X 7 第八章 随机规划 f ( X ,) 都是随机变量,其概率密度函数用 ( f ) 表示,这种可能有多少个 f ( X ,) 使得P{ f ( X ,)  f } 成立。从极大化目标值 的观点看,我们所要的目 f f 标值 应该是目标函数f (X ,) 在保证置信水平至少是 时所取的最大值,即 f  f  max{ f P{ f ( X ,)  f }  } , (8.21) . 8

网友评论

我的2016年度评论盘点
还没有评论,快来抢沙发吧!