中农大水资源和环境模型与优化课件第6讲 随机规划

1第6讲

随机规划

StochasticProgramming不确定规划在现实世界中，人们制定决策时经常会碰到不确定性现象，这种不确定性现象包据我们所熟悉的两类：一类是随机现象，一类是模糊现象；描述、刻画随机现象的量称为随机变量。描述、刻画模糊现象的量称为模糊集。为了方便，我们不妨把二者分别称为随机参数和模糊参数。含有随机（模糊）参数的数学规划称为随机（模糊）规划，二者统称为不确定规划。2随机规划在确定性数学规划问题中，要求目标函数是确定性函数，约束条件确定的集合是一个确定的可行域。但是，数学规划问题中目标函数或约束条件的系数往往是随机变量，含有随机变量的数学规划问题被称为随机规划。随机规划是对含有随机变量的优化问题建模的有效的工具并已有一个世纪的历史。一种随机规划是美国经济学家丹泽1955年提出的，康托罗维奇在这方面的贡献，不在于这个新方法本身，而在于把它应用于制定最优计划。是广泛使用的期望值模型，即在期望约束条件下，使得期望收益达到最大或期望损失达到最小的优化方法。3随机规划另一种是由查纳斯（A.Charnes）和库伯（W.W.Cooper）于1959年提出的机会约束规划，是在一定的概率意义下达到最优的理论。还有一种是两阶段随机规划Sincethe1960’s,applicationsofTSPhavebeenwidelyinvestigated.Stancu-MinasianandWetsidentifiedmanypapersinthisareaand,sincethattime,morestudiesofTSPmethodologiesandapplicationshavebeenconducted.4主要内容机会约束规划(Chanceconstrainedprogramming)机会约束规划模型由CharnesandCooper提出，主要针对约束条件中含有随机变量,该模型允许所做决策在一定程度上不满足约束条件，但该决策应使约束条件成立的概率不小于某一事先给定的置信水平；两阶段随机规划(Two-stagestochasticprogramming)第一阶段的决策在随机事件发生前做出，当随机事件发生时做出第二阶段的决策使损失达到最小，具有补偿的效果。5期望值模型

6期望值模型

7期望值模型

8期望值模型

9两阶段规划（Two-stage）

10机会约束规划模型

11机会约束规划模型

12p1-p机会约束规划模型

13机会约束规划模型

14机会约束规划模型

15机会约束规划的应用

16机会约束规划的应用

17知道怎么来的吗？机会约束规划的应用随机资源分配考虑随机资源分配问题，其中有多处资源和多个用户。随机资源分配的任务是确定各种资源的组合，使其满足给定的目标。例如，前面提到的水资源配置问题。有3处水资源和4个水用户，水资源供给网络如图所示。181234321水源用户

机会约束规划的应用

19机会约束规划的应用下面引入机会约束目标规划来求解这个问题管理目标是满足四个用户的需求，其需求量分别为3,1,2和3，同时假设有如下的目标值和优先结构：第1优先级，尽可能满足用户1的需求，即第2优先级，尽可能满足用户2的需求，即第3优先级，尽可能满足用户3的需求，即最后一个优先级，尽可能满足用户4的需求，即20机会约束规划的应用那么有关此问题的机会约束目标规划可以表示为基于随机模拟的遗传算法给出的最优解为21随机模拟将在下节课介绍随机规划研究实例StochasticProgrammingChanceConstrainedProgramming(CCP)Two-stagestochasticprogramming(TSP)Multistagestochasticprogramming(MSP)ExamplesGuoP,HuangGH,LiYP.Aninexactfuzzy-chance-constrainedtwo-stagemixed-integerlinearprogrammingapproachforflooddiversionplanningundermultipleuncertainties.

AdvancesinWaterResources,2010,33(1):81-91.

GuoP,HuangGH,LiYP.Inexactfuzzy-stochasticprogrammingforwaterresourcesmanagementundermultipleuncertainties.EnvironmentalModeling&Assessment,2010,15(2):111-124.GuJ.J.,GuoP.andHuangG.H.,InexactstochasticdynamicprogrammingmethodandapplicationtowaterresourcesmanagementinShandongChinaunderuncertainty.StochasticEnvironmentalResearchAndRiskAssessment.2013;27(5):1207-121922随机规划研究实例Two-stagestochasticprogramming(TSP)waseffectiveforproblemswhereananalysisofpolicyscenarioswasdesiredandwhentheright-hand-sidecoefficientswererandomwithdiscoveredprobabilitydistributions.TSPcouldhandleuncertaintiesexpressedasPDFsaswellasaccountforeconomicpenaltieswithrecourseagainstanyinfeasibility;however,itcouldhardlyreflectdualandmultipleuncertainties.23DualuncertaintiesMultipleuncertainties随机规划研究实例Interval-ParameterFuzzy-StochasticTwo-StageProgrammingWhenuncertaintiesofsomeelementsinAcanbeexpressedasfuzzysetsandthoseinBcanbeexpressedasprobabilitydistributions,theproblemcanbeconvertedtoWhenuncertaintiesofsomeelementsinBcanbeexpressedasrobabilitydistributions,thechance-constrainedprogramming(CCP)methodcanbeused.IntermsofuncertaintiesinB,considerageneralstochasticlinearprogramming(SLP)problemasfollows:24随机规划研究实例1

25随机规划研究实例126前面讲到的洪水规划的例子还记得吗？Considerawatershedsystemwhereinfloodwaterneedstobedivertedfromariverchanneltowaterdiversionregionsinawetseason.Theriverhasalimitedwater-conveyancecapacityandmayoverflowduringhigh-flowseasons.Basedonthelocalfloodmanagementpolicies,afloodwarningleveloftheriverhasbeenpre-regulatedandafixedflooddiversiontargettoeachregionhasbeenassigned.随机规划研究实例minimizefloodingrisksubjecttoexistingregularcapacityconstraintsexistingmaximumcapacityconstraintsexpandedcapacityconstraintstotaldiversioncapacityconstraints27

随机规划研究实例1floodflowconstraintsnon-negativityconstraintsbinaryconstraintsforcapacityexpansiondiversioncapacityofregionicanbeexpandedonlyoncewithoptionm28

随机规划研究实例129FrameworkoftheIFCTIPapproach随机规划研究实例1

30随机规划研究实例1

31Membershipfunctionforfuzzysetspunderdifferentacutlevels随机规划研究实例2Thedevelopedmethodisappliedtoahypotheticalcasestudyofwaterresourcesallocationamongasetofenduserswithinanagriculturalsector.Consideringanagriculturesystemwhereinawatermanagerisresponsibleforallocatingwaterinadryseasonfromanunregulatedreservoirtothreefarmscroppedwithpotato,wheat,andalfalfa.Inthestudysystem,thestreamflowsvaryamongdifferentlevels.Thenetbenefittofarmipercubicmeterofwaterallocatedandthelosstofarmipercubicmeterofwaternotdeliveredalsovarytemporallyandspatially.32随机规划研究实例233(wateravailabilityconstraints)(allowablewaterallocationconstraints)(non-negativityandtechnicalconstraints)随机规划研究实例2qjistheprobabilityofoccurrenceofflowleveljj=1representinglowlevelflows,j=2representingmediumlevelflows,andj=3representinghighlevelflows.34Membershipfunctionforfuzzysetp

underdifferentαcutlevelsDistributionwithfuzzy-intervalprobability随机规划研究实例235FrameworkoftheIFRTSPmodel随机规划研究实例236Streamflowdistributions(in106m3)underdifferentcombinationsofpiandαlevelsandrelevantprobabilitylevels随机规划研究实例237SolutionsofIFRTSPandITSLPmodels(in106m3)Itwasindicatedthatthesolutionsfortheobjectivefunctionvalueanddecisionvariables(relatedtowaterusesinthepotato,wheat,andalfalfafarms)underdifferentlevelsofflowrate.Incaseofinsufficientwater,allocationshouldfirstlybeguaranteedtopotatofarm,secondlytowheat,andlastlytoalfalfa.Thiswasbecausepotatofarmbringsaboutthehighestbenefitwhenwaterdemandwassatisfiedandwassubjecttothehighestpenaltyifthepromisedwaterwasnotdelivered;thewheatandalfalfafarmscorrespondedtolowerbenefitsandpenalties.随机规划研究实例2IFSTPprovidesdecisionmakerswithinformationunderuncertaintyandrecourse,withthefollowingadvantages:(a)iteffectivelycommunicatesuncertaintiesintotheoptimizationprocessunderdifferentlevelsofstreamflows;(b)itdealswithdualuncertaintiesoftheconstraints’left-handsides(presentedasfuzzyintervals)andmultipleuncertaintiesoftheconstraints’right-handsides(asintervals,probabilitydistributions,andintegrationofintervals,fuzzysets,andprobabilitydistributions);(c)itisapplicabletopracticalproblemssincethesolutionalgorithmdonotleadtomorecomplicatedintermediatemodels;.(d)itprovidesbasesforidentifyingdesiredwaterresourcesmanagementplanswithreasonablebenefitandrisklevels.38随机规划研究实例3

39随机规划研究实例3

40随机规划研究实例3

41随机规划研究实例3通过将区间数学规划（IP）引入联合概率约束规划（JCP）中以解决上述问题，其整合以后的模型为区间联合概率约束规划模型（Interval-parameterJointProbabilityConstrainedProgramming,IJCP）其中上标符号‘+’代表区间元素的上边界，‘-’代表区间数的下边界42随机规划研究实例3通过将IJCP引入MSP中可以解决MSP中出现的随机性因素并且可以分析约束违规时系统的风险。其整合以后的模型可以建立适合水资源管理系统多水库联合调度系统的区间多阶段联合概率规划模型（Interval-parameterMultistageJoint-probabilisticProgramming,IMJP)43随机规划研究实例3区间多阶段联合概率规划模型（IMJP）不仅可以处理以联合概率和区间形式出现的不确定性因素，也可以分析系统在不同侵犯下的系统安全可靠性。这个模型可以反应系统在各阶段间的动态关联性,，并可以在多情景下得到决策结果。44区间多阶段联合概率规划模型（IMJP）流程图随机规划研究实例3案例研究45沂河是淮河流域泗沂沭水系中的较大河流。位于山东省南部与江苏省北部，为古淮河支流泗水的支流。选取淮河流域沂河区域田庄水库与跋山水库组成的梯级水库水资源配置系统为研究对象研究区水资源配置体系随机规划研究实例346水资源配置系统流程图梯级水库水资源主要供给跋山水库下游区域的社会经济发展。当来水量过少的时候可能会达不到区域水资源的需求量，这就需要进行外调水或抽取地下水，这样一来用水的成本就会增加。但是当来水量过大时，就会导致多余水量的产生，更严重的时候会产生洪涝灾害，所以必须进行分流以避免洪涝灾害的风险产生。规划期内提供的水资源量为随机性变量，随着区域社会经济的发展，其水资源的需求量也越来越大，当水资源缺乏时会限制当地区域经济的发展。但是，如果区域来水量过大而超过区域水资源存储能力的时候，就会进行水资源的分流，当来水量急速增加时，则有可能产生洪涝灾害。随机规划研究实例3由于区域的来水与需水之间始终存在着变化的关系，本研究的目标是设计一套在不确定条件下既可以防洪又可以防旱而且又能使区域经济最大化的水资源优化配置系统。不确定性因素存在系统的很多方面，比如，河流流量、水利设施、水资源消耗量、供水量、社会经济等等。“两条”供给下游区域社会经济发展的河流（河流1，河流2）由于相互独立且服从随机分布所以存在以联合概率形式出现的不确定性因素。所以不确定性因素在水资源系统中以概率分布和随机数的形式出现。这些不确定性因素会导致在水资源配给和分流的时候出现交互性和动态性方面的复杂性。以往没有研究对田庄水库和跋山水库进行梯级水库优化配置的研究。由于本案例中存在联合概率问题，所以相比较现存的不确定性优化模型，运用区间多阶段联合概率规划模型（IntervalParameterMultistageJoint-probabilityProgramming，简称IMJP）可以更有效的解决水资源系统中出现的不确定性问题。47随机规划研究实例3不确定性多阶段联合概率规划模型函数目标为系统收益最大化通过向第一产业、第二产业和第三产业供水使三产创造经济效益减去因缺水所导致的外调水和抽取额外地下水的财政支出，同时减去因为分流所消耗的费用，其结果为整体系统的收益。约束条件现阶段和下一阶段水库来水量、水库存水量和水库泄水量之间的关系48

随机规划研究实例3下游区域的配水量必须满足该区域的生态需水向下游区域的配水量在各规划期必须满足各行业的最小需水量且不能大于其最大需水量下游配水量必须满足区域最小需水量但不能超过区域最大配水量水库分流（或者泄洪）的水量及向下游区域的配水量不能超过水库的泄水量梯级水库群的总体分流量为各个时期分流量之和49

随机规划研究实例3水库存水量不能大于水库的最大存水量水库存水量必须大于水库的死库容量水库向三个产业的分别配水量之和为向三产的总体配水量水库向三个产业的分别配水时的差额量之和为向三产的总体配水时的差额量下游区域配水时的差额量不能超过配水量且其差额量为非负值50

随机规划研究实例3当来水量过少的时候可能会达不到区域水资源的需求量，这就需要进行外调水或抽取地下水，这样一来用水的成本就会增加。但是当来水量过大时，就会导致多余水量的产生，更严重的时候会产生洪涝灾害，所以必须进行分流以避免洪涝灾害的风险产生。

51

规划期概率T=1T=2T=3规划期河流1枯水期流量(108m3)0.4[2,5.5][4,5][3,5.2]规划期河流1平水及丰水期流量(108m3)0.6[6,12][9,14][8.5,13]规划期河流2枯水期流量(108m3)0.4[4,34][7,29][6,35]规划期河流2平水及丰水期流量(108m3)0.6[40,71][42,82][39,73]河流1及河流2在规划期内的流量及其对应的流量概率随机规划研究实例3相关数据52(108m3）田庄水库跋山水库[1.24,1.39][4.683,5.29]0.2670.684水库库容相关数据(108m3)T=1T=2T=3第一产业[9.0058,10.0294][10.7385,11.7607][12.8046,13.7909]第二产业[0.8674,0.9660][1.0343,1.1328][1.2333,1.3283]第三产业[0.3106,0.3459][0.3703,0.4056][0.4416,0.4756](108m3)T=1T=2T=312.079014.325216.950513.426015.699418.3130[0.3562,0.3918][0.4440,0.4883][0.5317,0.5849][1.7169,1.8886][1.9737,2.1710][2.2304,2.4534]区域三产及生态需水量随机规划研究实例3模型的上边界模型为s.t.53后面省略……随机规划研究实例3下边界模型为s.t.54后面省略……随机规划研究实例3本例选择了三阶段的水资源规划。由于有两个水库和“两条”河流（河流1和河流2），且两条河流的流量相互独立，且流量服从随机分布，所以会有64种不同的排列组合，也就是说有64种相应的情景。此外，一系列的概率约束被用来考虑水库的水短缺。它还有助于分析系统违反约束的风险进而取得更好的水分配计划。由于联合概率的存在，模型中分析了9个代表联合概率的组合。随着可能性的提高，侵犯库容约束的风险增加了。对应于目标函数的上边界和下边界，每一种模型能够被划分成两个子模型。通过模型的运行，可以解决两个问题：1）预测区域的经济效益；2）制定合理的水供给计划，使系统得到利益的最大化，同时系统损失最小化（水短缺导致的外调水及抽取额外地下水费用消耗，水分流的成本）。55随机规划研究实例3ConditionJointprobabilityIndividualprobabilitySystembenefit(108RMB

yuan）1Q=0.01q1=0.001,q2=0.009[11325.02,14254.36]2q1=0.005,q2=0.005[11324.97,14254.31]3q1=0.009,q2=0.001[11324.92,14254.25]4Q=0.05q1=0.01,q2=0.04[11325.59,14254.95]5q1=0.025,q2=0.025[11325.39,14254.74]