运筹学随机规划ppt课件.ppt

随 机 规 划,随机规划,在确定性数学规划问题中, 要求目标函数是确定性函数, 约束条件确定的集合是一个确定的可行域. 但是，数学规划问题中目标函数或约束条件中的系数往往是随机变 (向) 量. 含有随机变 (向)量的数学规划问题被称为随机规划. 随机规划这一学科的理论和计算方法还不完善和成熟, 但已在管理科学、经济学、最优控制等学科和应用中显示了越来越强的生命力, 已成为运筹学的一个重要分支.,随机规划模型及研究模式,设有标准线性规划问题,假设模型中系数A,b,c或它们的一部分分量可能是随机向量,不妨设是定义在概率空间 上的随机向量.,有随机线性规划模型,实际上，这个数学规划模型是没有定义的，由于随机变量的出现，使得min和约束条件的意义并不明确！,有几种方式理解随机规划模型以适合于不同的实际背景.,期望值模型： 取随机变量对应的函数的数学期望, 把随机规划转化为一个确定数学规划问题.,随机规划模型及研究模式,称这种在期望值约束下, 使目标函数的期望值达到最优的确定数学规划为期望值模型.,报童问题：设一报童每天清晨去批发报纸来零售, 每天可以售出报纸份数为随机变量b(假设根据他长期卖报的经验, b的概率分布是已知的).根据规定,如果报童没有卖完当天的报纸, 卖不完的报纸不能退回.设所订购的报纸数量为x份, 每份报纸的批发价为p分, 售价为a分. 报童所面临的决策问题为, 清晨, 他应批发多少份报纸最好?,期望值模型,收益函数 是随机变量, 考虑其期望收益,这里E表示期望值算子, 表示需求量b的概率密度函数.,报童问题就是寻找最优的订购数量x, 使期望收益E(f(x,b)达到最大值. 这是一个典型的期望值模型.,期望值模型,解：由于每天可以售出报纸份数为随机变量b. 若xb, 则每天报纸的剩余量为x-b; 否则为0. 于是, 报童的收益为,期望值模型,一般的，单目标的期望值模型可以表示如下：,期望值模型,期望值模型的确是随机优化问题中常用且有效的方法，但我们并不总是关心极大化期望值收益问题或极小化期望值费用问题。实际上，有时可能更要考虑所谓的风险问题。给定两种不同的投资方案，它们的期望收益相同而风险不同。有些人(称为风险爱好者)可能为追求最大效益而选择风险较大的方案，而另一些人(称为风险厌恶者)可能为躲避风险而选择风险较小的投资方案，也可能有些人不太在乎风险，认为哪一种方案都可以接受，这也是期望值模型的理论基础。,期望值模型,如果决策者希望在给定的期望收益水平下实现风险的极小化, 则有如下风险最小模型,如果决策者希望同时考虑期望收益和风险，则有如下两目标规划模型,在有些情况下, 使用期望值模型会显得不太合理, 如圣彼得堡悖论.,例：某化工厂生产过程中需要A, B两种化学成分,现有甲、已两种原料可提供选用.其中原料甲中化学成分A的单位含量为a/10, B的单位含量为b/3; 原料乙中化学成分A的单位含量为1/10, B的单位含量为1/3. 根据生产要求, 化学成分A的总含量不得少于7/10个单位, B的总含量不得少于4/3个单位. 甲、乙两种原料的价格相同. 由于某种原因, 原料甲中化学成分A, B的单位含量不稳定, 其中 是矩形 内均匀分布的随机变量. 问如何采购原料, 使得既满足生产要求, 又使得成本最低?,期望值模型,解：设原料甲和原料乙的采购数量分别为x1, x2, 则有线性规划模型(LP),期望值模型,期望值模型,(LP1)有惟一最优解,(LP1)的最优解x*位于D的概率仅为0.25!,(LP)的期望值模型为,期望值模型,凸性是数学规划中经常讨论的课题，如果一个数学规划模型的目标函数和可行域都是凸的，则该规划模型称为凸规划。对期望值模型，在凸性方面有如下结论：,期望值模型,从数学观点来看, 确定性优化问题和期望值模型并没有什么区别, 唯一的区别是后者存在多重积分.,随机模拟, 也称为Monte Carlo模拟, 是一种实现随机(或确定)系统抽样实验的技术, 其基础是从给定的概率分布中抽取随机变量. 随机模拟的应用范围非常广泛，可以用来求解数学、物理、工程技术以及生产管理等方面的问题。,估计随机积分,期望值模型,Liu和Iwamura提出用基于随机模拟的遗传算法求解一般的期望值模型.,第0步, 输入参数pop_size,Pc及Pm第1步, 初始产生pop_size个染色体,其中可能使用随机模拟计算约束函数中的多重积分;第2步, 对染色体进行交叉及变异操作,其中可能使用随机模拟技术检验后代的可行性;第3步, 使用随机模拟技术计算所有染色体的目标值;第4步, 根据目标值, 使用基于序的评价函数计算每个染色体的适应度;第5步, 旋转赌轮, 选择染色体;第6步, 重复步骤2到步骤5, 直到完成给定的循环次数;第7步, 给出最好的染色体作为最优解.,期望值模型,基于随机模拟的遗传算法,(2) 机会约束规划(Chance Constrained Programming, 简称CCP). 机会约束规划模型由Charnes和Cooper提出，该模型主要针对约束条件中含有随机变量，且必须在贯彻到随机变量的实现之前作出决策的情况.,随机规划模型及研究模式,机会约束规划,考虑到所做的决策在不利情况发生时可能不满足约束条件，(CCP)模型采取如下一种原则即允许所作决策在一定的程度上不满足约束条件, 但该决策应使约束条件成立的概率不小于某一事先给定的置信水平 (0 1).,其中P表示事件成立的概率, 为事先给定的约束条件成立的置信水平值.,一般的, 考虑目标函数和约束条件中同时带随机变量的数学规划,机会约束规划,Liu对机会约束规划模型提出了如下形式的扩展模型：,其中P表示事件成立的概率, 分别为事先给定的约束条件和目标函数的置信水平.,联合机会约束,可行点：点x为可行点当且仅当事件 的概率测度不小于 , 即违反约束条件的概率小于 .,机会约束规划,机会约束规划,Max-max机会约束规划,机会约束规划,在随机环境中，在机会约束条件下，想极大化在给定置信水平值处的悲观值，有如下minimax CCP模型：,从极小化目标值 的观点来看, 所要的目标值 应该是目标函数 在保证置信水平至少是 时所取的最小值, 即,机会约束规划,对应的, 机会约束规划模型有如下形式的扩展模型：,Min-min模型,机会约束规划,作为单目标机会约束规划的推广, 多目标机会约束规划可以表示成如下形式,机会约束规划,根据决策者的优先结构和目标信息, 机会约束目标规划模型可以表示为如下形式,求解机会约束规划的传统方法是根据事先给定的置信水平, 把机会约束转化为各自的确定等价类, 然后传统的非线性规划的算法可以用来解决这类问题. 但对较复杂的机会约束规划问题, 通常很难做到这一点. 一些革新算法如遗传算法等的提出, 使复杂的机会约束规划可不必通过转化而直接得到解决.,机会约束规划,考虑如下机会约束条件：,机会约束规划确定等价类,机会约束规划确定等价类,例：考虑机会约束,考虑如下机会约束条件：,机会约束规划确定等价类,考虑如下机会约束条件：,机会约束规划确定等价类,机会约束规划确定等价类,例：假设机会约束有如下形式 Pa1x1+a2x2+a3x3b 0.95其中a1, a2, a3和b分别服从正态分布N(1,1), N(2,1), N(3,1)和N(4,1),于是，得到该机会约束条件的确定等价类为 x1+2x2+3x3+1.645(x12+x22+x32+1)1/2 4,如果能够方便地计算出 及其梯度 的值, 则任何非线性规划算法都可用来求解机会约束规划问题. 但在实际问题中 和 的计算大都是很不容易的.到目前为止, 能够求出数值解的, 基本上只局限于下述类型的问题:,机会约束规划数值解法,机会约束规划与确定性规划的区别在于前者存在机会约束，因此讨论的重点在于如何处理机会约束. 如果机会约束比较容易处理，则可以将机会约束转化为各自的确定等价类，否则可以使用随机模拟技术处理复杂的机会约束.,考虑如下机会约束规划模型,1) 检验随机系统约束 2) 计算目标值,机会约束规划数值解法,1) 检验随机系统约束,由大数定律知, 可以用频率N/N 估计此概率.,因此, 机会约束 成立当且仅当 频率,机会约束规划数值解法,设N表示N次实验中,机会约束规划数值解法,步骤1：置N=0.,步骤2：由概率分布 生成随机变量.,步骤4：重复步骤2和步骤3共N次.,机会约束规划数值解法,例: 估计如下事件发生的概率 =P1+ 22 3，3+42 9其中1服从均匀分布U(2,5), 2服从指数分布exp(3), 3和4分别服从正态分布N(3,2)和N(1,1).,模拟结果为0.85，即上述事件发生的概率为0.85.,从概率分布 中产生N个彼此相互独立的随机变量,2) 计算目标值,这样得到序列,取N为 的整数部分. 由大数定律可知， 中的第N个最大的元素可以作为 的估计.,机会约束规划数值解法,步骤1：从概率分布 生成N个随机向量,例: 求使下式成立的最大的f 0 P1+ 22 +33f 0 0.8其中1服从均匀分布U(1,3), 2服从指数分布exp(1), 3服从正态分布N(2,1).,抽样1000次, 其第800个最大元素为4.988, 于是f 0的估计值为4.988.,机会约束规划数值解法,4) 基于随机模拟的遗传算法,机会约束规划数值解法,Liu和Iwamura提出使用基于随机模拟的遗传算法求解一般的机会约束规划.,第0步, 输入参数pop_size,Pc及Pm第1步, 初始产生pop_size个染色体,其中可能使用随机模拟技术检验染色体的可行性;第2步, 对染色体进行交叉及变异操作,其中可能使用随机模拟技术检验后代的可行性;第3步, 使用随机模拟技术计算所有染色体的目标值;第4步, 根据目标值, 使用基于序的评价函数计算每个染色体的适应度;第5步, 旋转赌轮, 选择染色体;第6步, 重复步骤2到步骤5, 直到完成给定的循环次数;第7步, 给出最好的染色体作为最优解.,基于随机模拟的遗传算法是解决复杂的机会约束规划模型(包括机会约束多目标规划和机会约束目标规划)的有力工具. 基于随机模拟的遗传算法的有效性已被大量实验所证实.优点：（1）能够很好地得到全局最优解；（2）不需要把机会约束转化为它们各自的确定性等价类, 从而保证可处理更加一般的机会约束规划模型. 缺点： 计算费用较高，耗时较多。,机会约束规划数值解法,机会约束规划数值解法,例：考虑一个简单的机会约束规划模型：,机会约束规划数值解法,例：考虑单目标机会约束规划模型：,机会约束规划数值解法,例：某炼油厂冶炼两种原油(分别记为raw1和raw2), 需要提前制定一周的生产计划, 以便为天燃气公司提供天燃气(记为prod1)和为火力发电厂提供燃料用油(记为prod2). 假定原料raw1所能生产出的天燃气的产量(raw1,prod1)和原料raw2所能生产出的燃料用油的产量 (raw2,prod2)是随机变化的, 而所生产的其他产品的产量却是固定的. 这里假设,其中 为服从均匀分布 的随机变量， 为服从参数 的负值数分布的随机变量。,机会约束规划应用,已知用户(天然气公司和火力发电厂)对天然气一周的需求量h1和对燃料的需求量h2也是随机变化的, 可以分别表示,和 是分别服从正态分布N(0,12) 和N(0,9) 的随机变量.,假设x1和x2分别是原料raw1和raw2的一周使用量, 单价分别为c1=2, c2=3, 生产能力(即原材料的最大消耗量)假设为100. 试建立此问题的随机规划模型.,机会约束规划应用,x1+x2 100.,分析：由原材料的最大消耗量可知，有如下约束条件,由于每周的生产计划(x1,x2)是提前制定的, 且一周内不能改变, 同时在相应的周内客户希望他们的实际需要得到满足, 即,此约束中含有随机变量，一种可行的方法是使用机会约束, 对两个用户分别给予置信水平 有,由于希望在满足用户需求的机会约束下尽可能地降低总费用, 把这个生产计划问题建模为机会约束规划模型,机会约束规划应用,随机资源分配考虑水资源供给系统, 有3处水资源和4个用户, 水资源供给网络如下,机会约束规划应用,机会约束规划应用,例：设某工厂生产n种产品, 需m种原料. 第j种产品对第i种原料的单位需求量为aij, 第i种原料的拥有量为bi, 第j种产品的单位利润为cj. 试问如何安排各产品的生产量xj(j=1,2,n), 以使得在现有条件下利润最大?,设系数均为随机变量, 记为aij(w),bi(w),cj(w),分布问题：希望知道在各种可能情况下, max z的值是什么, 即max z的分布如何, 或max z的数学期望是多少.,分布问题,对任一样本 ，求解如下线性规划问题,然后再求max z(w) 的分布函数.,分布问题,分布问题,最优目标函数值z(w)的取值可能有如下三种情况：(1) z(w)=- (当其对偶问题的可行解集为空集时);(2) z(w)=+(当原问题的可行解集为空集时) ;(3) z(w)为有限值(当上述两个可行解集均非空时).,分布问题,分布问题的算法,实际计算中并不真的需要解N个线性规划问题, 因为由(A(i),b(i),c(i) 求zi时, 可能它的最优可行基也是其他(A(k),b(k),c(k)的最优可行基, 这时求相应的zk会是非常方便的.,分布问题,分布问题,进一步, 由此容易求出Fz(t)和E(z).,分布问题,分布问题,分布问题,报童问题(续)：根据假设, 决策x要在知道当天能卖出的份数b(w) 实现之前作出, 所以报童面临的规划问题为,当决策x作出后, b(w) 可能会出现二种情况;(1) b(w) x: 缺少y+ 份, 报童遭受损失0y+;,有补偿的二阶段问题,报童的净收入为(-p+a)x-Q(x,w). (Q(x,w)为随机变量) 报童面临的真正决策问题是,报童应该考虑使由于约束条件 不被满足而造成的损失最小, 即,有补偿的二阶段问题,W称为补偿矩阵,q称为惩罚向量,二阶段问题模型,因为需要在观察到A(w), b(w)实现之前就作出决策以确定x的值, 显然, x不一定能够保证对所有w都满足约束条件A(w)x=b(w),引进补偿量W(w)y, 有 A(w)x+W(w)y=b(w),W(w)y作为原约束条件受到破坏程度的一种度量,由此将给决策者带来一定程度的惩罚, 设惩罚量为qT(w)y.,这是在x,w给定的条件下关于y的极值问题, 记最优值为Q(x,w).,二阶段问题模型,决策者当然希望在满足A(w)x+W(w)y=b(w) 条件下使惩罚量qT(w)y达到最小,最优决策应使cTx+Q(x,w)达到极小, 由于事先不知道哪个样本点w出现, 比较合理的考虑应是将E(Q(x,w)加到cTx上,二阶段问题模型,将确定x的问题(2)称为第一阶段问题, 确定y的问题(1)称为第二阶段问题.,记Q(x)=E(Q(x,w), 求解模型(2)实际上是求解一确定的非线性规划问题, 而要知道目标函数中Q(x)=E(Q(x,w), 实际上是要求解一分布问题.,二阶段问题模型,为使问题(2)在实际上和数学上有意义, 决策变量x的取值范围应使Q(x)为有限值，由Q(x,w)的意义可知，其不可能为-,(2),二阶段问题模型,具有简单补偿矩阵的二阶段问题,二阶段问题模型,有补偿的二阶段问题,有补偿的二阶段问题,具体分析如下：,有补偿的二阶段问题,下面，分三种情况分别求解如下线性规划模型:,可解得最优值为77.5, 其最优解为x1*=75, x2*=25.,练习题,