第5章-随机规划模型

确定性因素和随机性因素随机因素可以忽略随机因素影响可以简单地以平均值的作用出现随机因素影响必须考虑概率模型统计回归模型马氏链模型随机模型确定性模型随机性模型传送带挂钩产品工作台工人将生产出的产品挂在经过他上方的空钩上运走，若工作台数固定，挂钩数量越多，传送带运走的产品越多。背景在生产进入稳态后，给出衡量传送带效率的指标，研究提高传送带效率的途径9.1传送系统的效率问题分析•进入稳态后为保证生产系统的周期性运转，应假定工人们的生产周期相同，即每人作完一件产品后，要么恰有空钩经过他的工作台，使他可将产品挂上运走，要么没有空钩经过，迫使他放下这件产品并立即投入下件产品的生产。•可以用一个周期内传送带运走的产品数占产品总数的比例，作为衡量传送带效率的数量指标。•工人们生产周期虽然相同，但稳态下每人生产完一件产品的时刻不会一致，可以认为是随机的，并且在一个周期内任一时刻的可能性相同。模型假设1）n个工作台均匀排列，n个工人生产相互独立，生产周期是常数；2）生产进入稳态，每人生产完一件产品的时刻在一个周期内是等可能的；3）一周期内m个均匀排列的挂钩通过每一工作台的上方，到达第一个工作台的挂钩都是空的；4）每人在生产完一件产品时都能且只能触到一只挂钩，若这只挂钩是空的，则可将产品挂上运走；若该钩非空，则这件产品被放下，退出运送系统。模型建立•定义传送带效率为一周期内运走的产品数（记作s,待定）与生产总数n（已知）之比，记作D=s/n•若求出一周期内每只挂钩非空的概率p，则s=mp为确定s，从工人考虑还是从挂钩考虑，哪个方便？设每只挂钩为空的概率为q，则p=1-q如何求概率设每只挂钩不被一工人触到的概率为r，则q=rn设每只挂钩被一工人触到的概率为u，则r=1-uu=1/mp=1-(1-1/m)nD=m[1-(1-1/m)n]/n一周期内有m个挂钩通过每一工作台的上方模型解释若(一周期运行的)挂钩数m远大于工作台数n,则)]2)1(1(1[2mnnmnnmD传送带效率(一周期内运走产品数与生产总数之比）])11(1[nmnmD定义E=1-D(一周期内未运走产品数与生产总数之比）提高效率的途径：•增加m•习题1当n远大于1时,En/2m~E与n成正比，与m成反比若n=10,m=40,D87.5%(89.4%)mn2119.2报童的诀窍问题报童售报：a(零售价)b(购进价)c(退回价)售出一份赚a-b；退回一份赔b-c每天购进多少份可使收入最大？分析购进太多卖不完退回赔钱购进太少不够销售赚钱少应根据需求确定购进量每天需求量是随机的优化问题的目标函数应是长期的日平均收入每天收入是随机的存在一个合适的购进量等于每天收入的期望建模•设每天购进n份，日平均收入为G(n)调查需求量的随机规律——每天需求量为r的概率f(r),r=0,1,2…准备))(()(rncbrnrbarnr赔退回赚售出nbannr)(赚售出nrnrrnfbarfrncbrbanG01)()()()])(()[()(求n使G(n)最大•已知售出一份赚a-b；退回一份赔b-cnndrrnpbadrrprncbrbanG0)()()()])(()[()(dndG求解将r视为连续变量概率密度）()()(rprf0dndGcbbadrrpdrrpnn)()(0nndrrpbadrrpcb0)()()()(ndrrpbannpba)()()()(ndrrpcbnnpba0)()()()(cbbadrrpdrrpnn)()(0结果解释nnPdrrpPdrrp201)(,)(nP1P2cbbaPP21取n使a-b~售出一份赚的钱b-c~退回一份赔的钱ncbnba)(,)(0rp9.3随机存贮策略问题以周为时间单位；一周的商品销售量为随机；周末根据库存决定是否订货，供下周销售。（s,S)存贮策略制订下界s,上界S，当周末库存小于s时订货，使下周初的库存达到S;否则，不订货。考虑订货费、存贮费、缺货费、购进费，制订（s,S)存贮策略,使(平均意义下)总费用最小模型假设•每次订货费c0,每件商品购进价c1,每件商品一周贮存费c2,每件商品缺货损失费c3(c1c3)•每周销售量r随机、连续，概率密度p(r)•周末库存量x,订货量u,周初库存量x+u•每周贮存量按x+u-r计0)(0),()(10uxLuuxLuccuJxxdrrpxrcdrrprxcxL032)()()()()(建模与求解（s,S)存贮策略0usx确定(s,S),使目标函数——每周总费用的平均值最小平均费用订货费c0,购进价c1,贮存费c2,缺货费c3,销售量rSuxusx,0s~订货点，S~订货值12130)()(ccccdrrpdrrpSSuxuxdrrpcdrrpccdudJ0321)()(建模与求解1）设xs,求u使J(u)最小，确定SSSdrrpccdrrpcc01321)()()()(Sux01)(drrp0dudJScSc23,建模与求解xxdrrpxrcdrrprxcxL032)()()()()(0)(0),()(10uxLuuxLuccuJSP1P20rp21PP2）对库存x，确定订货点s)()(101SLxSccJ若订货u,u+x=S,总费用为)(2xLJ若不订货,u=0,总费用为12JJ)()(1xIxLxc记)()(0SIcxI订货点s是的最小正根建模与求解xxdrrpxrcdrrprxcxL032)()()()()(0)(0),()(10uxLuuxLuccuJ)()()(10SLxSccxL不订货)()(101SLSccxLxc)()(0SIcxI)()(0SIcxI最小正根的图解法J(u)在u+x=S处达到最小xI(x)0SI(S)sI(S)+c0I(x)在x=S处达到最小值I(S)I(x)图形建模与求解xxdrrpxrcdrrprxcxL032)()()()()(0)(0),()(10uxLuuxLuccuJ)()(1xLxcxIJ(u)与I(x)相似I(S))()(0SIcxI的最小正根s9.4轧钢中的浪费轧制钢材两道工序•粗轧(热轧)~形成钢材的雏形•精轧(冷轧)~得到钢材规定的长度粗轧钢材长度正态分布均值可以调整方差由设备精度确定粗轧钢材长度大于规定切掉多余部分粗轧钢材长度小于规定整根报废随机因素影响精轧问题：如何调整粗轧的均值，使精轧的浪费最小背景分析设已知精轧后钢材的规定长度为l，粗轧后钢材长度的均方差为记粗轧时可以调整的均值为m，则粗轧得到的钢材长度为正态随机变量，记作x~N(m,2)切掉多余部分的概率)(lxPP整根报废的概率)(lxPPPPm,存在最佳的m使总的浪费最小lPPPm,0p(概率密度)mxP´mPP´lldxxxpdxxplxW)()()(ldxxlpdxxxp)()(建模选择合适的目标函数切掉多余部分的浪费整根报废的浪费总浪费=+lPm粗轧一根钢材平均浪费长度粗轧N根成品材PN根成品材长度lPN总长度mNNlPNmNlPm共浪费长度mN-lPNlPmPNlPNmN)()(mPmmJ记222)(21)(,)()(mxlexpdxxpmP选择合适的目标函数粗轧一根钢材平均浪费长度lPmNlPNmN得到一根成品材平均浪费长度更合适的目标函数优化模型：求m使J(m)最小（已知l,）建模粗轧N根得成品材PN根,mxylm,)()(J2221)()()(yzeydyyz)()(mPmmJ222)(21)()()(mxlexpdxxpmPz)()()(zzzJ)()(J求解求z使J(z)最小（已知）求解)()()(zzzJ0)()()(zzz)(/)(zzz)()(zz0dzdJ2221)()()(yzeydyyz)(/)()()(zzzFzzF简表)()()(zzzFz*z例设l=2(米),=20(厘米)，求m使浪费最小。=l/=10z*=-1.78*=-z*=11.78m*=*=2.36(米)求解1.2530.8760.6560.5160.4200.3550227.0-3.00.556.79-2.51.018.10-2.01.57.206-1.52.02.53.4771.680-1.0-0.5zzF(z)F(z)zzF)(1.02.00-1.0-2.0105F(z)z9.5随机人口模型背景•一个人的出生和死亡是随机事件一个国家或地区平均生育率平均死亡率确定性模型一个家族或村落出生概率死亡概率随机性模型对象X(t)~时刻t的人口,随机变量.Pn(t)~概率P(X(t)=n),n=0,1,2,…研究Pn(t)的变化规律；得到X(t)的期望和方差若X(t)=n,对t到t+t的出生和死亡概率作以下假设1)出生一人的概率与t成正比，记bnt;出生二人及二人以上的概率为o(t).2)死亡一人的概率与t成正比，记dnt;死亡二人及二人以上的概率为o(t).3)出生和死亡是相互独立的随机事件。bn与n成正比，记bn=n,~出生概率；dn与n成正比，记dn=n，~死亡概率。进一步假设模型假设)()1)(()()()(1111totdtbtPtdtPtbtPttPnnnnnnnn建模为得到Pn(t)P(X(t)=n),的变化规律，考察Pn(t+t)=P(X(t+t)=n).事件X(t+t)=n的分解X(t)=n-1,t内出生一人X(t)=n+1,t内死亡一人X(t)=n,t内没有出生和死亡其它(出生或死亡二人，出生且死亡一人，……)概率Pn(t+t)Pn-1(t),bn-1tPn+1(t),dn+1tPn(t),1-bnt-dnto(t))()()()1()()1(11tnPtPntPndtdPnnnn)()()()(1111tPdbtPdtPbdtdPnnnnnnnn~一组递推微分方程——求解的困难和不必要00,0,1)0(nnnnPn(t=0时已知人口为n0)转而考察X(t)的期望和方差bn=n，dn=n微分方程建模1)()()()(nntEtnPdtdE)()()()1()()1(121111tPntPnntPnndtdEnnnnnn1)()(nntnPtEX(t)的期望求解)()()()1()()1(11tnPtPntPndtdPnnnn基本方程1)()1(kktPkkn-1=k1nndtdPndtdEn+1=k)()1(1tPkkkk求解0)0()()(nEtEdtdErtextx0)(比较：确定性指数增长模型)()()(212tEtPntDnnX(t)的方差E(t)-(t)-=rD(t)rentErt,)(0E(t)+(t)Et0n0,D(t)]1[)()()(0tteentDX(t)大致在E(t)2(t)范围内（(t)~均方差）r~增长概率r~