运筹学课件第11章存储论-第3,4节课件.pdf

运筹学第13章存贮论第3节随机性存储模型第13章存贮论第3节随机性存储模型第4节其他类型存贮问题第3节随机性存储模型随机性存储模型的重要特点是需求为随机的,其概率或分布为已知。在这种情况下，前面 所介绍过的模型已经不能适用了。例如商店 对某种商品进货500件，这500件商品可能 在一个月内售完，也有可能在两个月之后还 有剩余。商店如果想既不因缺货而失去销售 机会，又不因滞销而过多积压资金，这时必 须采用新的存储策略可供选择的策略主要有三种(1)定期订货，但订货数量需要根据上一个周期末剩下 货物的数量决定订货量。剩下的数量少，可以多订货。剩下的数量多，可以少订或不订货。这种策略可称为 定期订货法。(2)定点订货，存储降到某一确定的数量时即订货，不 再考虑间隔的时间。这一数量值称为订货点，每次订 货的数量不变，这种策略可称之为定点订货法。(3)把定期订货与定点订货综合起来的方法，隔一定时 间检查一次存储，如果存储数量高于一个数值s,则不 订货。小于s时则订货补充存储，订货量要使存储量达 到S,这种策略可以简称为(s,S)存储策略。与确定性模型不同的特点还有:不允许缺货的条件只能从概率的意义 方面理解，如不缺货的概率为0.9等。存储策略的优劣通常以赢利的期望值 的大小作为衡量的标准。为了讲清楚随机性存储问题的解法，先通过一个例题介绍求解的思路。例7某商店拟在新年期间出售一批日历画片，每 售出一千张可赢利700元。如果在新年期间 不能售出，必须削价处理，作为画片出售。由于削价，一定可以售完，此时每千张赔损 400元。根据以往的经验，市场需求的概率 见表13-1。表 1 3-1需求量r（千张）012345(5)概率 P(r)X P(r)=l3=o)0.0 50.1 00.2 50.3 50.1 50.1 9每年只能订货一次，问应订购日历画片几 千张才能使获利的期望值最大？解如果该店订货4千张，我们计算获利 的可能数值当市场需求为（千张）获利（元）0(-4 0 0)X 4=-1 60 01(-4 0 0)X3+700=-5002(-4 0 0)X 2+70 0 X 2=60 03(-4 0 0)X 1+70 0 X 3=1 70 04(-4 0 0)X 0+70 0 X 4=2 80 05(-4 0 0)X 0+70 0 X 4=2 80 0订购量为4千张时获利的期望值:EC(4)=(-160 0)X 0.0 5+(-50 0)X 0.1 0+60 0 X 0.2 5+1 70 0 X 0.3 5+2 80 0 X 0.1 5+2 80 0 X 0.1 0=1315(元)上述计算法及结果列于表13-2获利期望值最大者标有(*)记号，为1440元。可知该店订购3000张日历画片可使获利期望值最大。获利4012345获利的 期望值000000001-4007007007007007006452-800300140014001400140011803-1200-10010002100210021001440*4-1600-50060017002800280013155-2000-9002001300240035001025从相反的角度考虑求解当订货量为Q时，可能发生滞销赔损（供过于 求的情况），也可能发生因缺货而失去销售 机会的损失（求过于供的情况）。把这两种损 失合起来考虑，取损失期望值最小者所对应 的Q值。订购量为2千张时，损失的可能值:当市场需求量为（千张）滞销损失（元）0(-400)X2=-8001(-400)X1=-40020（元）（以上三项皆为供大于需时滞销损失）3(-700)X1=-7004(-700)X2=-14005（-700）X3=-2100（以上三项皆为供小于需时，失去销售机会而少获利的损失）当订货量为2千张时，缺货和滞销两种损 失之和的期望值 EC(2)=(-800)X0.05+(-400)X0.10+0X0.25+(-700)X0.35+(-1400)X0.15+(-2100)X0.10=745(元)按此算法列出表13-3。表 1 3-3订货量（千张）012345损失的期望值-1 92 5-1 2 80-74 5-4 85*-61 0-90 0比较表中期望值以-485最大，即485为损失最小值。该店订购3000张日历画片可使损失的期望值最小。这结论与前边得出的结论一样，都是订购3000张。这说明对同一问题可从两个不同的角度去考虑：一是考虑获利最多，一是考虑损失最小。这是一个问题的不同表示形式。3.1模型五：需求是随机离散的报童问题：报童每日售报数量是一个随机变量。报 童每售出一份报纸赚k元。如报纸未能售出，每份 赔h元。每日售出报纸份数r的概率P(r)根据以往的 经验是已知的，问报童每日最好准备多少份报纸？这个问题是报童每日报纸的订货量Q为何值时，赚 钱的期望值最大？反言之，如何适当地选择Q值，使因不能售出报纸的损失及因缺货失去销售机会的 损失，两者期望值之和最小。现在用计算损失期望 值最小的办法求解。解 设售出报纸数量为r,其概率P(r)为已知 设报童订购报纸数量为Q。供过于求时(Q),这时报纸 因不能售出而承担的损失，其期望值为：供不应求时(rQ),这时因 缺货而少赚钱的损失，其期 望值为：Jh(Q-r)P(r)r=000Zk(r-Q)P(r)r=Q+l综合，两种情况，当订货量为Q时,损失的期望值为：C(Q)=Q 00=h(Q-r)P(r)+k(r-Q)P(r)r=0 r=Q+l要从式中决定Q的值，使C(Q)最小。由于报童订购报纸的份数只能取整数，r是 离散变量，所以不能用求导数的方法求极值。为此设报童每日订购报纸份数最佳量为Q,其损失期望值应有：C(Q)C(Q+1)C(Q)C(Q-1)从出发进行推导有Q ooh(Q-r)P(r)+k J；(r-Q)P(r)r=0 r=Q+lQ+l oo0r=0kk+hQ P(r)2 r=0由出发进行推导有Q ooh(Q-r)P(r)+k(r-Q)P(r)r=0 r=Q+lQ-l ooh(Q-l-r)P(r)+k(r-Q+l)P(r)r=0 ill r=QQ-l Q-l k(k+h)p(r)-k VO 一r=0 r=0 k+h报童应准备的报纸最佳数量Q 应按下列不等式确定：Q-i k QP(r)-Q时，报童因为只有Q份报纸可供 销售，赢利的期望值为00Zk QP(r)r=Q+l无滞销损失。由以上分析知赢利的期望值:Q QC(Q)江 k rP(r)-h(Q-r)P(r)+r=0 r=000+Zk QP(r)r=Q+l为使订购Q赢利的期望值最大，应满足下列关系式：C(Q+1)C(Q)C(Q-1)4C(Q)从式推导，Q+l Q+l cok rP(r)(Q+1 r)P(r)+k(Q+l)P(r)r=0 r=0 r=Q+2Q Q oo k rP(r)-h(Q-r)P(r)+k Q-P(r)r=0 r=0 r=Q+l经化简后得Q ook P(Q+1)-h P(r)+h Z P(r)4。|r=0 r=Q+2-Qk l-P(r)r=0-hP(r)r=0kk+h同理从推导出Q-1P(r)Wr=0kk+h用以下不等式确定Q的值，这一公式与(13-25)式完全相同。Q-1P(t)r=0Q4P(Dr=0kk+h现利用公式(13-2 5)解例7的问题。已知：k=7,h=4,P(0)=0.05,x 0.637 k+h P(1)=0.10,P(2)=0.25,P(3)=0.35 2 3P(r)=0.40 0.637 P(r)=0.75 r=0 r=0知该店应订购日历画片3千张。例8某店拟出售甲商品，每单位甲商品成本50 元，售价70元。如不能售出必须减价为40 元，减价后一定可以售出。已知售货量r的 概率服从泊松分布（入=6为平均售出数）问该店订购量应为若干单位？P(r)=。一及尤 t解 该店的缺货损失，每单位商品为70-50=20o滞销损失，每单位商品50-40=10,利用(15-13)式，其中k=20,h=10kk+h薪“-667一 6二/P(c)=，记:p)=F(Q)t r=0e6R6)=2T=0=0.6063,7 p66rF江下T=0 L-=0.7440因kF(6)-=0.667 F(7)k+h故订货量应为：7单位，此时损失的期望值最小。例9上题中如缺货损失为10元，滞销损失为 20元。在这种情况下该店订货量应为若干？解 利用(15-13)式,其中k=10,h=20kh+k 300.333查统计表，找与0.3333相近的数4 0_6万 5F(4)=0.2851,F(5)=X_=0.4457r=0 石 r=0 2！F(4)0.3333 0)0生产或订购的数量为Q,问如何确定Q的数 值，使赢利的期望值最大？解 首先我们来考虑当订购数量为Q时，实际 销售量应该是minr,Q。也就是当需求为r而r 小于Q时，实际销售量为r；之Q时，实际销售量只能是Q需支付的存储费用C/Q）二q(Q-r)0r 0货物的成本为KQ,本阶段订购量为Q赢利为W（Q）,赢利的期望值记作EW（Q）。本阶段的赢利：W(Q)=P minrQ-KQ-C1(Q)（赢利）=（实际销售货物的收入）_（货物成本卜（支付的存储费用）赢利的期望值：由 俨(QEW(Q)=1 P侬r)dr+.PQ阿dr-KQ-q(Q-Mr)dr=jPr阿dr-Pr阿dr+PQ阿dr-KQ-f C1(Q-r)(r)drr r(Q=PE(r)-P(r-Q)(r)dr+Q(Q-r)(r)dr+KQ)v J)J常量（平均盈利）因缺货失去销售机会损失的期望值因滞销受到损失的期望值常量记EC(Q)二=P g(r-Q)(r)dr+G,(Q r),(r)dr+KQ为使赢利期望值极大化，有下列等式：max EW(Q)=PE(r)-minEC(Q)(13-26)max EW(Q)+minEC(Q)=PE(r)(13-27)(13-26)式表明了赢利最大与损失极小所得 出的Q值相同。(13-27)式表明最大赢利期望值与损失极小 期望值之和是常数。从表13-2与表13-3中对应着相同的Q,去掉 13-3表中数据的负号后，两者期望值之和皆为1925,称为该问题的 平均盈利。求赢利极大可以转化为求EC(Q)(损失期 望值)极小。当Qm以连续取值时，EC(Q)是Q的连续函 数。可利用微分法求最小。d dQEC(Q)二dQLP p Q)O(r)dr+GQd=-P 0(r)dr+G O(r)dr+K Q 4)二0令 dEC(Q)dQ=0,记 F(Q)=dr0C】F(Q)-Pl-F(Q)+K=O从此式中解出Q,记为Q*,Q*为EC(Q)的驻点。又因c fEICXQ)dQ2=C0(Q)+P0(Q)O知Q*为EC(Q)的极小值点，在本模型中也是最小值点。若 P-KWO显然由于F(Q)NO,等式不成立，此时Q*取 零值。即售价低于成本时，不需要订货(或 生产)。式中只考虑了失去销售机会的损失,如果缺货时要付出的费用C2P时，应有EC(Q)=C2(r-QW)drQ+G(Q r)0(r)dr+KQ按上述办法推导得Q C KF(Q)=p(r)dr=模型五及模型六都是只解决一个阶段的问题。从一般情况来考虑，上一个阶段未售出的货物可以在第二阶段继续出售O这时应该如何制定存储策略呢?假设上一阶段未能售出的货物数量为I,作为本阶段初的存储，有minEC(Q)二=K(Q-I)+C2(r-QM dr+Q(Q-r)(r)dr=-KI+minp2 Rr-Q)(r)dr+G：(Q-r)O(r)dr+KQ常量与(13-28)式相同定期订货，订货量不定的存储策略Q C K利用 F(Q)=p(r)dr=二一 求出 Q*值，C+C2相应的存储策略为：当I2 Q*时，本阶段不订货。当I 0)期初存储量为I,定货量为Q,此时期初存储 达到S=l+Q。问如何确定Q的值，使损失的 期望值最小(赢利的期望值最大)？本阶段需订货费解 期初存储I在本阶段中为常量，订货量为Q,则期初存储达到S=I+QO本阶段需订货费 C3+KQ,本阶段需付存储费用的期望值为d+Q=SC(S r)0(r)dr0需付缺货费用的期望值为然、I C2(r-SMr)dr本阶段所需订货费及存储费、缺货费期望 值之和C(I+Q)=C(S)=C3+KQ+J Cj(S-r)(r)dr+C2(r-S)(r)dr=C3+K(S-I)+C(S r)0(r)dr+0+rC2(r-SMr)drQ可以连续取值，C(S)是S的连续函数。dCP 乂/乂/人 dC(S)_nds=K+Cq (r)dr-C21(r)dr；令=0,e C K有F(S)=J/)dr=(1 3-2 9)1 I V.X c严格小于1,q+c2r k称为临界值，以N表示：=N q+c2本阶段的存储策略：/S由 (r)dr=N,确定S的值0订货量Q二S-1、本模型中有订购费C3,如果本阶段不订货C3=0,因此可设想是否存在一个数值s(sWS)使下面不等式能成立。fS 弊Ks+Cx(s-r)(r)dr+C2 J(r-s)(r)drC3+KS+C1(S-r)(r)dr+C2(r-SW)dr当s=S时，不等式显然成立。当s 0相应的存储策略是：每阶段初期检查存储，当库存l s时，需订货，订货的数量为Q,Q=S-L当库存INS时，本阶段 不订货。这种存储策略是：定期订货但订货量不 确定。订货数量的多少视期末库存I来决定订货 量Q,Q=S-L对于不易清点数量的存储，人们 常把存储分两堆存放，一堆的数量为s,其余的 另放一堆。平时从另放的一堆中取用，当动用了 数量为s的一堆时，期末即订货。如果未动用s的 一堆时，期末即可不订货，俗称两堆法。2.需求是离散的随机变量时设需求r取值为口，n,rm(rKn+Jm其概率为 p(r0),p(n),p(rm),Z p(rJ=li=0原有存储量为1(在本阶段内为常量)当本阶段开始时订货量为Q,存储量达到I+Q本阶段所需的各种费用：订货费：c3+kq存储费：当需求rI+Q时，未能售出的存储部分需付存储费。当需求rI+Q时，不需要付存储费。所需存储费的期望值：ZG（I+Q-r）P（r）rI+Q时，(lQ)部分需付缺货费。缺货费用的期望值：J；C2(r-I-Q)p(r)rI+Q本阶段所需订货费及存储费、缺货费期望之和：C(I+Q)=C3+KQ+C1(I+Q-r)p(r)+C2(r-I-Q)p(r)rI+Q本阶段所需的各种费用：I+Q表示存储所达到的水平，记S=I+Q,上式可写为:C(s)=C3+K(S-1)+工 C(S-r)p(r)+rS求出s值使C(S)最小。求解(1)将需求r的随机值按大小顺序排列为 r0?n,rm.riS+!C(sj=C3+K(Sr1)+Z C(Sr)p(r)+Z C2(r-S Jp(r)rSi-i选出使C(S1)最小的S值,Si应满足下列不等式：C(Si+i)-C(Si)NO C(Si)-C(Si-i)0定义 A C(Si)=C(Si+i)C(Si)9A C(Si-i)=C(Si)-C(Si-i)AC(SX)由可推导出AKSX+C1AS1p(r)-C2AS1p(r)rSiKASUGAS2P(r)心 9 1-Zp(r)rSi|_ rSiKASi+(CX+C2)ASip(r)C2ASi r0因ASj w 0即即K+(C1+C2)p(r)C20rSi有p(r)2rSic2-kQ+c2=N由同理可推导出EpW-5c2-kC+C=N综合以上两式，得到为确定Si的不等式()rSi4c2-kC=N2p(r)r0C(SJ C(SQ0其中C(SQ-C(SJ=AKSX+C1AS1p(r)-C2AS1p(r)rSi=KAS1+gas2p(D-Zp(r)rSi|_ rSi=KA0+(G+C2)A*Z P(D C A0 r0 rSjr k因ASi。，化简后有 ZP(r)2 二N rSj C+C2同理可推出 EpWNf.1综合上面两式,可利用下面不等式确定Si2 p(r)N p(r)rSi4 r N 成立的Si最小值作Sr0.204P(3 0)+P(4 0)=0.2 0+0.2 0=0.4 0 0.2 0 4Si=4 0,作为 S 原存储10,订货量Q=S-1=4 0-1 0=3 0答该公司应订购塑料30箱。下面对答案进行验证分别计算S为30,40,50所需订货费及存储 费期望值、缺货费期望值三者之和。比较它 们看是否当S为40时最小（见表13-4）。SIQ 二 ST订货费 C3+KQ存储费期望值C】Z（S r）P（r）rS总计3010201606001624032300401020240608081203 2 2 60*50102032060240203034330计算s的方法：考查不等式(1 3-3 1)Ks+Z G(s r)p(r)+工 C2(r s)p(r)rs C3+KS+Z G(S-r)p(r)+Z C 2(r-S)p(r)rS(13-31)因S也只从口，n,，rm中取值。使(13-31)式成立的n(nS)的值中最小者定为so当s30箱时 不必补充存储。当代30箱时补充存储量达到 40箱。例11某厂对原料需求量的概率为 P(r=80)=0.1,P(r=90)=0.2,P(r=100)=0.3 P(r=110)=0.3,P(r=120)=0.1 订货费C3=2825元，K=850元 存储费C1=45元(在本阶段的费用)缺货费C2=1250元(在本阶段的费用)求该厂存储策略。求解(1)利用公式(1 3-30)计算临界值N=1250-8501250+45=0.309(2)求 S：P(r=80)+P(r=90)=0.3 0.309P(r=80)+P(r=90)+P(r=1 0 0)=0.60.3 0 9可知S=1 0 0求解(3)用(13-31)式计算sS=1 0 0,(1 3-31)式右端为2825+850 X100+45 X(1 0 0-80)X 0.1+(1 0 0-90)X 0.2+(1 0 0 0-1 0 0)X 0.3 J+1 2 50 X(1 1 0-1 0 0)X 0.3+(1 2 0-1 0 0)X 0,1 =94255s=80,(1 3-31)式左端为850 X 80+45 X(80-80)X 0.1+1250 X (90-80)X 0.2+(1 0 0-80)X 0.3+(1 1 0-80)X 0.3+(1 2 0-80)X 0,1=94250由于 9425080时不补充。例12某市石油公司，下设几个售油站。石油存放在郊区大型油库里，需要时用 汽车将油送至各售油站。该公司希望确 定一种补充存储的策略，以确定应储存 的油量。该公司经营石油品种较多，其 中销售量较多的一种是柴油。因之希望 先确定柴油的存储策略。经调查后知每月柴油出售量服从指数分布，平均销售量每月为一百万升。其密度为：、fO.OOOOOl eooooool xr r0f（r）=0 r s=0,667两端取对数解出 S=405000（升利用(1 3-3 1)式，求S只需把相应的求和部分利用积分计算即可。2s+Ox(s-r)f(r)dr+3(r-s)f(r)dr 0 62S+0 x(S-r)f(r)dr+3(r-S)f(r)dr J)JS即 2s+3、(r-s)f(r)drL的概率。Fx（L）=Zx（r）FrLPl的计算很繁，简化计算为了简化记缺货费的期望值为c2pL,n。次缺货费的期望值为n0C2PL,每年的存储费用为一Q0+B CiC 1H)由于Q。是根据存储费用和订购费用权衡后得出的最佳值，因此只需要考虑维持缓冲存储量的存储费用以及缺货费期望值两者之和最小。即令nCR+CiB最小以确定L和Bo由关系式L=u P+B可知只要确定了 L就相当于B也确定了：例13（模型八）某厂生产中需用钢材，t时 间内需求的概率服从泊松分布：/二e 一 t（夕 t）r!每天平均需求为一吨p二1,年平均需求量D为365吨。则t时间内需求为r的概率外任）=r!例13备货时间为X天的概率服从正态分布 伙心=7。一）2平均备货时间口二15（天）,方差。2二1。P(x)=1 c(x15)2/2石例13年存储费用每吨为50元，每次订购费用为 1500元，缺货费用每吨为5000元，问每年 应分多少批次?又订购量Q,缓冲存储量B,订货点L,各为何值才使费用最少？解：八 12c3D（2x 1500 x 365“十、QlJJ 50）n0D356Qo146x 2.5（次）下面计算L及B,各步算出的数值列于表 13-5。（-）备货时间X(二)备货时间的概率p(】r 1 2、p(x)=Le-(x-1 5)/2L r=0e-xxr!L=1 5L=2 1L=2 2L=2 3L=2 4L=2 5L=2 6L=3 1 0.2 3 60.0 1 40.0 0 80.0 0 40.0 0 20.0 0 100 0.3 3 10.0 2 90.0 1 70.0 0 90.0 0 50.0 0 30.0 0 10 0.4 3 20.0 530.0 3 30.0 1 90.0 1 10.0 0 60.0 0 30 0.53 30.0 890.0 580.0 3 70.0 2 20.0 1 30.0 0 80 0.62 90.1 3 80.0 950.0 630.0 4 00.0 2 50.0 1 50.0 0 1续表1 3-5（五）相应备货时间及需求两者概率的乘积P（x）Fx（L）（五）二（二）X（四）L=1 5L=2 1L=22L=23L=2 4L=25L=2 6L=3 1 0.0 1 20000000 0,0 790.0 0 70.0 0 40.0 0 10.0 0 10.0 0 10.0 0 00 0.1 730.0 2 10.0 1 30.0 0 40.0 0 20.0 0 20.0 0 10 0.1 2 80.0 2 10.0 1 40.0 0 50.0 0 30.0 0 30.0 0 20 0.0 3 10.0 0 70.0 0 50.0 0 20.0 0 10.0 0 10.0 0 10根据表1 3-5算出Pl、B和费用的数值 见表13-6。LL=1 5L=2 1L=2 2L=2 3L=2 4L=2 5L=2 6L=3 1Pl0.4 2 30.0 560.0 3 60.0 2 10.0 1 20.0 0 70.0 0 40B067891 01 11 6费用52 87.51 0 0 080 066360 0588*60 080 017Pl=Zp（x）Fx（L）,R=L x=15说明:备货时间小于13,或大于18者，因为它 们的概率很小，故略去。L的选值可以多一些，如保证可以选到最 小值，L选值也可少一些。由表中可以看到 当L=25,B=10费用588*为最小。据此即可 确定存储策略。答 该厂定购批量为146吨，定购点为25吨，每年 订货2.次（两年订货5次），缓冲存储量为10吨。当清点存储花费劳动多，或清点困难时，人们 常把存储物分成三堆存放。以例13来说，将缓冲存储量B=10吨放一处，称 之为第三堆。将平均拖后时间内的平均需求量 DL=|jp=15吨放另一处称第二堆。第三堆、第二堆之和等于订货点25吨。其余存储另放一处称第一堆。平日从第一堆取 川，第一堆用完，动用第二堆时，立即订货。动用第三堆时，即需采取措施以防缺货。第4节*其他类型存储问题有些存储问题远较本章所述模型复杂，上述 公式不能用来求解，也可以利用运筹学的其 他方法求解。如水库储水的调度问题，有人 利用排队论方法处理问题，有人利用动态规 划方法，都做出了成绩。下面介绍一个例题，与本章前述的方法无关,可用线性规划方法求解。4.1库容有限制的存储问题例14已知仓库最大容量为A,原有存储量 为I,要计划在m个周期内，确定每一个周期 的合理进货量与销售量，使总收入最多。已 知第i个周期出售一个单位货物的收入为期 而订购一个单位货物的订货费为(i=1,2,，m)o例14：解 设为必分别为第i个周期的 进货量及售货量，这时总收入为mC=Z(aiyibiX j1=1 要求出XM使C达到最大值(i=1,2,m)o容 易理解XM,这些变量不能任意取值。(1)它们受到库容的限制，即进货量加上原 有存储量不能超过A；(2)每个周期的售出量不能超过该周期的存 储量；(3)进货量及售出量不能取负值。用方程组表示上述的限制(约束条件)：S 1+区-A,(s=l,2,m)1=1s y5 I+Z(Xi y)(s=l,2,m)1=1(3)Xi三0,yi三0(i=l,2,，m).目标函数，约束条件都是线性的，可利用线性规划方法求解。