运筹学-随机规划课件

随机规划随机规划随机规划在确定性数学规划问题中,要求目标函数是确定性函数,约束条件确定的集合是一个确定的可行域.但是，数学规划问题中目标函数或约束条件中的系数往往是随机变(向)量.含有随机变(向)量的数学规划问题被称为随机规划.随机规划这一学科的理论和计算方法还不完善和成熟,但已在管理科学、经济学、最优控制等学科和应用中显示了越来越强的生命力,已成为运筹学的一个重要分支.随机规划在确定性数学规划问题中,要求目标函数是确定性函数,随机规划模型及研究模式设有标准线性规划问题假设模型中系数A,b,c或它们的一部分分量可能是随机向量,不妨设是定义在概率空间上的随机向量.有随机线性规划模型实际上，这个数学规划模型是没有定义的，由于随机变量的出现，使得min和约束条件的意义并不明确！随机规划模型及研究模式设有标准线性规划问题假设模型中系数A,有几种方式理解随机规划模型以适合于不同的实际背景.期望值模型：取随机变量对应的函数的数学期望,把随机规划转化为一个确定数学规划问题.随机规划模型及研究模式称这种在期望值约束下,使目标函数的期望值达到最优的确定数学规划为期望值模型.有几种方式理解随机规划模型以适合于不同的实际背景.期望值模型报童问题：设一报童每天清晨去批发报纸来零售,每天可以售出报纸份数为随机变量b(假设根据他长期卖报的经验,b的概率分布是已知的).根据规定,如果报童没有卖完当天的报纸,卖不完的报纸不能退回.设所订购的报纸数量为x份,每份报纸的批发价为p分,售价为a分.报童所面临的决策问题为,清晨,他应批发多少份报纸最好?期望值模型报童问题：期望值模型收益函数是随机变量,考虑其期望收益这里E表示期望值算子,表示需求量b的概率密度函数.报童问题就是寻找最优的订购数量x,使期望收益E(f(x,b))达到最大值.这是一个典型的期望值模型.期望值模型解：由于每天可以售出报纸份数为随机变量b.若x≥b,则每天报纸的剩余量为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)期望值模型解：设原料甲和原料乙的采购数量分别为x1,x2,则有线性期望值模型(LP1)有惟一最优解(LP1)的最优解x*位于D的概率仅为0.25!(LP)的期望值模型为期望值模型(LP1)有惟一最优解(LP1)的最优解x*位于D期望值模型凸性是数学规划中经常讨论的课题，如果一个数学规划模型的目标函数和可行域都是凸的，则该规划模型称为凸规划。对期望值模型，在凸性方面有如下结论：期望值模型凸性是数学规划中经常讨论的课题，如果一个数学规划模期望值模型从数学观点来看,确定性优化问题和期望值模型并没有什么区别,唯一的区别是后者存在多重积分.随机模拟,也称为MonteCarlo模拟,是一种实现随机(或确定)系统抽样实验的技术,其基础是从给定的概率分布中抽取随机变量.随机模拟的应用范围非常广泛，可以用来求解数学、物理、工程技术以及生产管理等方面的问题。期望值模型从数学观点来看,确定性优化问题和期望值模型并没有估计随机积分期望值模型估计随机积分期望值模型Liu和Iwamura提出用基于随机模拟的遗传算法求解一般的期望值模型.第0步,输入参数pop_size,Pc及Pm第1步,初始产生pop_size个染色体,其中可能使用随机模拟计算约束函数中的多重积分;第2步,对染色体进行交叉及变异操作,其中可能使用随机模拟技术检验后代的可行性;第3步,使用随机模拟技术计算所有染色体的目标值;第4步,根据目标值,使用基于序的评价函数计算每个染色体的适应度;第5步,旋转赌轮,选择染色体;第6步,重复步骤2到步骤5,直到完成给定的循环次数;第7步,给出最好的染色体作为最优解.期望值模型基于随机模拟的遗传算法Liu和Iwamura提出用基于随机模拟的遗传算法求解一般的(2)机会约束规划(ChanceConstrainedProgramming,简称CCP).

机会约束规划模型由Charnes和Cooper提出，该模型主要针对约束条件中含有随机变量，且必须在贯彻到随机变量的实现之前作出决策的情况.随机规划模型及研究模式考虑带随机变量的数学规划其中x是一个n维决策变量，(2)机会约束规划(ChanceConstrained机会约束规划考虑到所做的决策在不利情况发生时可能不满足约束条件，(CCP)模型采取如下一种原则—即允许所作决策在一定的程度上不满足约束条件,但该决策应使约束条件成立的概率不小于某一事先给定的置信水平α(0<α<1).其中P表示事件成立的概率,为事先给定的约束条件成立的置信水平值.机会约束规划考虑到所做的决策在不利情况发生时可能不满一般的,考虑目标函数和约束条件中同时带随机变量的数学规划机会约束规划Liu对机会约束规划模型提出了如下形式的扩展模型：其中P表示事件成立的概率,分别为事先给定的约束条件和目标函数的置信水平.联合机会约束一般的,考虑目标函数和约束条件中同时带随机变量的数学规划机联合机会约束有时可以分成几个独立的机会约束，可行点：点x为可行点当且仅当事件的概率测度不小于,即违反约束条件的概率小于.机会约束规划联合机会约束有时可以分成几个独立的机会约束，可行点：点x为可机会约束规划Max-max机会约束规划机会约束规划Max-max机会约束规划机会约束规划在随机环境中，在机会约束条件下，想极大化在给定置信水平值处的悲观值，有如下minimaxCCP模型：机会约束规划在随机环境中，在机会约束条件下，想极大化在给定置从极小化目标值的观点来看,所要的目标值应该是目标函数在保证置信水平至少是时所取的最小值,即机会约束规划对应的,机会约束规划模型有如下形式的扩展模型：Min-min模型从极小化目标值的观点来看,所要的目标值应该是机会约束规划作为单目标机会约束规划的推广,多目标机会约束规划可以表示成如下形式机会约束规划作为单目标机会约束规划的推广,多目标机会约束规机会约束规划根据决策者的优先结构和目标信息,机会约束目标规划模型可以表示为如下形式机会约束规划根据决策者的优先结构和目标信息,机会约束目标规求解机会约束规划的传统方法是根据事先给定的置信水平,把机会约束转化为各自的确定等价类,然后传统的非线性规划的算法可以用来解决这类问题.但对较复杂的机会约束规划问题,通常很难做到这一点.一些革新算法如遗传算法等的提出,使复杂的机会约束规划可不必通过转化而直接得到解决.机会约束规划求解机会约束规划的传统方法是根据事先给定的置信水平,把机会考虑如下机会约束条件：机会约束规划—确定等价类考虑如下机会约束条件：机会约束规划—确定等价类机会约束规划—确定等价类例：考虑机会约束机会约束规划—确定等价类例：考虑机会约束考虑如下机会约束条件：机会约束规划—确定等价类考虑如下机会约束条件：机会约束规划—确定等价类考虑如下机会约束条件：机会约束规划—确定等价类考虑如下机会约束条件：机会约束规划—确定等价类机会约束规划—确定等价类例：假设机会约束有如下形式P{a1x1+a2x2+a3x3≤b}≥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’表示N次实验中1)检验随机系统约束由大数定律知,可以用频率N’/N估机会约束规划—数值解法步骤1：置N’=0.步骤2：由概率分布生成随机变量.步骤3：如果则令N’=N’+1.步骤4：重复步骤2和步骤3共N次.步骤5：如果返回“成立”,否则返回“不成立”。机会约束规划—数值解法步骤1：置N’=0.步骤2：由概率分布机会约束规划—数值解法例:估计如下事件发生的概率

θ=P{ξ1+ξ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个随机向量从概率分布中产生N个彼此相互独立的随机变量例:求使下式成立的最大的f0P{ξ1+ξ22+ξ33≥f0}≥0.8其中ξ1服从均匀分布U(1,3),ξ2服从指数分布exp(1),ξ3服从正态分布N(2,1).抽样1000次,其第800个最大元素为4.988,于是f0的估计值为4.988.机会约束规划—数值解法例:求使下式成立的最大的f0抽样1000次,其第8004)基于随机模拟的遗传算法机会约束规划—数值解法Liu和Iwamura提出使用基于随机模拟的遗传算法求解一般的机会约束规划.第0步,输入参数pop_size,Pc及Pm第1步,初始产生pop_size个染色体,其中可能使用随机模拟技术检验染色体的可行性;第2步,对染色体进行交叉及变异操作,其中可能使用随机模拟技术检验后代的可行性;第3步,使用随机模拟技术计算所有染色体的目标值;第4步,根据目标值,使用基于序的评价函数计算每个染色体的适应度;第5步,旋转赌轮,选择染色体;第6步,重复步骤2到步骤5,直到完成给定的循环次数;第7步,给出最好的染色体作为最优解.4)基于随机模拟的遗传算法机会约束规划—数值解法Liu和I基于随机模拟的遗传算法是解决复杂的机会约束规划模型(包括机会约束多目标规划和机会约束目标规划)的有力工具.基于随机模拟的遗传算法的有效性已被大量实验所证实.优点：（1）能够很好地得到全局最优解；（2）不需要把机会约束转化为它们各自的确定性等价类,从而保证可处理更加一般的机会约束规划模型.缺点：计算费用较高，耗时较多。机会约束规划—数值解法基于随机模拟的遗传算法是解决复杂的机会约束规划模型(包括机会机会约束规划—数值解法例：考虑一个简单的机会约束规划模型：机会约束规划—数值解法例：考虑一个简单的机会约束规划模型：机会约束规划—数值解法例：考虑单目标机会约束规划模型：机会约束规划—数值解法例：考虑单目标机会约束规划模型：机会约束规划—数值解法机会约束规划—数值解法例：某炼油厂冶炼两种原油(分别记为raw1和raw2),需要提前制定一周的生产计划,以便为天燃气公司提供天燃气(记为prod1)和为火力发电厂提供燃料用油(记为prod2).假定原料raw1所能生产出的天燃气的产量π(raw1,prod1)和原料raw2所能生产出的燃料用油的产量π(raw2,prod2)是随机变化的,而所生产的其他产品的产量却是固定的.这里假设其中为服从均匀分布的随机变量，为服从参数的负值数分布的随机变量。机会约束规划应用已知用户(天然气公司和火力发电厂)对天然气一周的需求量h1和对燃料的需求量h2也是随机变化的,可以分别表示和是分别服从正态分布N(0,12)和N(0,9)的随机变量.例：某炼油厂冶炼两种原油(分别记为raw1和raw2),需假设x1和x2分别是原料raw1和raw2的一周使用量,单价分别为c1=2,c2=3,生产能力(即原材料的最大消耗量)假设为100.试建立此问题的随机规划模型.机会约束规划应用x1+x2

≤100.分析：由原材料的最大消耗量可知，有如下约束条件由于每周的生产计划(x1,x2)是提前制定的,且一周内不能改变,同时在相应的周内客户希望他们的实际需要得到满足,即此约束中含有随机变量，一种可行的方法是使用机会约束,对两个用户分别给予置信水平有假设x1和x2分别是原料raw1和raw2的一周使用量,单由于希望在满足用户需求的机会约束下尽可能地降低总费用,把这个生产计划问题建模为机会约束规划模型当置信水平分别取为0.8和0.7时,使用基于随机模拟的遗传算法,经过500代以后,得到的最优生产计划为(x1*,x2*)=(31.95,22.65),其总费用为f(x1*,x2*)=131.85.更进一步,有机会约束规划应用由于希望在满足用户需求的机会约束下尽可能地降低总费用,把这随机资源分配考虑水资源供给系统,有3处水资源和4个用户,水资源供给网络如下机会约束规划应用input1input2input3output1output2output3output4随机资源分配机会约束规划应用input1input2inpu机会约束规划应用机会约束规划应用例：设某工厂生产n种产品,需m种原料.第j种产品对第i种原料的单位需求量为aij,第i种原料的拥有量为bi,第j种产品的单位利润为cj.试问如何安排各产品的生产量xj(j=1,2,…,n),以使得在现有条件下利润最大?设系数均为随机变量,记为aij(w),bi(w),cj(w),分布问题：希望知道在各种可能情况下,maxz的值是什么,即maxz的分布如何,或maxz的数学期望是多少.分布问题例：设某工厂生产n种产品,需m种原料.第j种产品对第i种对任一样本，求解如下线性规划问题然后再求maxz(w)的分布函数.分布问题对任一样本，求解如下线性规划问题然后再求并求最优值z(w)的分布函数Fz(t)及有关的均值E(z)、方差Var(z)等.分布问题就是对每一样本点求解线性规划问题分布问题最优目标函数值z(w)的取值可能有如下三种情况：(1)z(w)=-∞(当其对偶问题的可行解集为空集时);(2)z(w)=+∞(当原问题的可行解集为空集时);(3)z(w)为有限值(当上述两个可行解集均非空时).并求最优值z(w)的分布函数Fz(t)及有关的均值E(z)、分布问题分布问题的算法实际计算中并不真的需要解N个线性规划问题,因为由(A(i),b(i),c(i))求zi时,可能它的最优可行基也是其他(A(k),b(k),c(k))的最优可行基,这时求相应的zk会是非常方便的.分布问题分布问题的算法实际计算中并不真的需要解N个线性规划问分布问题236468(2,4)(2,6)(2,8)(3,4)(3,6)(3,8)(6,6)(6,8)(6,4)分布问题236分布问题(2,4)(2,6)(2,8)(3,4)(3,6)(3,8)(6,6)(6,8)(6,4)进一步,由此容易求出Fz(t)和E(z).分布问题(2,4)(2,6)分布问题分布问题分布问题分布问题分布问题分布问题报童问题(续)：根据假设,决策x要在知道当天能卖出的份数b(w)实现之前作出,所以报童面临的规划问题为当决策x作出后,b(w)可能会出现二种情况;(1)b(w)<x:多余y-份,报童遭受损失py-;(2)b(w)>x:

缺少y+份,报童遭受损失0y+;有补偿的二阶段问题报童问题(续)：当决策x作出后,b(w)可能会出现二种情报童的净收入为(-p+a)x-Q(x,w).(Q(x,w)为随机变量)报童面临的真正决策问题是报童应该考虑使由于约束条件不被满足而造成的损失最小,即有补偿的二阶段问题W称为补偿矩阵q称为惩罚向量报童的净收入为(-p+a)x-Q(x,w).(Q(x,w)一般的，考虑如下随机线性规划其中为确定性约束，c为确定性向量，A(w)为型随机矩阵，b(w)为m