中央财经大学：《运筹学》 第四章（4-4） 应用举例

4.4应用举例

例限期采购问题(随机型) 某部门欲采购一批原料,原料价格「原料价格(元)概等 在五周内可能有所变动,预测得每 种价格的概率如右表所示,试问该30 0.3 600 0.3 部门应在五周内采用什么采购方案, 700 0.4 可使采购价格的均值最小 分析:ξ是个随机变量 均值E()=0.3×500+0.3×600+0.4×700=610 方案一: 50Q600700 Q0600 700 第一周买买 不买 第一周|买不买不买 第二周|买买 不买 第二周买不买不买 第三周|买买 不买 第三周买|不买|不买 第四周|买买 不买 第四周|买不买不买 第五周买买 头 第五周买买

例 限期采购问题（随机型） 某部门欲采购一批原料，原料价格 在五周内可能有所变动，预测得每 种价格的概率如右表所示，试问该 部门应在五周内采用什么采购方案， 可使采购价格的均值最小。 原料价格ζ（元） 概率p 500 0.3 600 0.3 700 0.4 分析：ζ 是个随机变量 均值E（ζ）= 0.3×500+ 0.3×600+ 0.4×700=610 方案一： 500 600 700 第一周 买 买 不买 第二周 买 买 不买 第三周 买 买 不买 第四周 买 买 不买 第五周 买 买 买 方案二： 500 600 700 第一周 买 不买 不买 第二周 买 不买 不买 第三周 买 不买 不买 第四周 买 不买 不买 第五周 买 买 买 η1 η2

原料价格(元)概p「方案5060470设n=按第一方案 第一周买买不买 购买的价格 500 0.3 第二周买买不买 500 第三周「买买不买 600 0.3 第四周买买不买 n1=1600 700 0.4 第五周买「买买 700 设A=第;出现价格500 B1=第i周出现价格600,C1=第;周出现价格700 n=500=A4+C12+CC241+CC2C,4+CCCC4 p(n=500)=03+04×03+0.42×0.3+043×03+04×0.3=049488 600=B,+C B2+C,C,B+C,C,CB+CC,CC.B p(n1=600)-0304×03+042×03+045×03+04×03=049488 p(n=700)=P(CC2C3CC3)=04=001024 E(n71)=0.49488×500+049488×X600+001024×700=551536

原料价格ζ（元） 概率p 500 0.3 600 0.3 700 0.4 方案一 500 600 700 第一周 买 买 不买 第二周 买 买 不买 第三周 买 买 不买 第四周 买 买 不买 第五周 买 买 买 设η1 =按第一方案 购买的价格 η1 =      700 600 500 设Ai = 第i周出现价格500 1 = 500= ( 500) p 1 = =0.3 +0.4×0.3 =0.49488 Bi = 第i周出现价格600 ,Ci = 第i周出现价格700 C1 A2 + C1 C2 A3 + C1 C2 C3 A4 + C1 C2 C3 C4 A5 0.4 0.3 2 +  0.4 0.3 3 +  0.4 0.3 4 +  1 = 600= B1 +C1 B2 + C1 C2 B3 + C1 C2 C3 B4 + C1 C2 C3 C4 B5 ( 600) p 1 = =0.3 +0.4×0.3 0.4 0.3 =0.49488 2 +  0.4 0.3 3 +  0.4 0.3 4 +  ( 700) p 1 = ( ) =0.01024 = P C1 C2 C3 C4 C5 5 = 0.4 ( )=0.49488×500+0.49488×600+0.01024×700 =551.536 E 1 A1 +

原料价格(元概率p防案二500160700设n2=按第二方案 第一周买不买不买 购买的价格 500 0.3 第二周|买不买不买 500 第三周买不买不买 600 0.3 第四周买不买不买 600 700 0.4 第五周买买 头 700 设A1=第周出现价格500 B,=第i周出现价格600,C=第;出现价格700 仂h2=500}=4+442+4424+44244+441444 p(h2=500=0.3+07×03+0.72×0.3+073×03+0.7+×03=0.83193 b2=600}=44B3 p(h2=600=07×03=007203 (72=70)=P(441A3AC5)=0714×0.4=009604 E(2)=0.83193×500+007203×600+009604×700=526411

原料价格ζ（元） 概率p 500 0.3 600 0.3 700 0.4 设η2 =按第二方案 购买的价格 η2 =      700 600 500 设Ai = 第i周出现价格500 2 = 500= A1 + ( 500) p 2 = Bi = 第i周出现价格600 ,Ci = 第i周出现价格700 A1 A2 + 2 = 600 ( 600) p 2 = ( 700) p 2 = ( ) E 2 500 600 700 第一周 买 不买 不买 第二周 买 不买 不买 第三周 买 不买 不买 第四周 买 不买 不买 第五周 买 买 买 方案二 A1 A2 A3 +A1 A2 A3 A4 + A1 A2 A3 A4 A5 =0.3 +0.7×0.3 0.7 0.3 =0.83193 2 +  0.7 0.3 3 +  0.7 0.3 4 +  = A1 A2 A3 A4 B5 0.7 0.3 4 =  =0.07203 ( ) = P A1 A2 A3 A4 C5 0.7 0.4 =0.09604 4 =  = 0.83193 ×500 + 0.07203 ×600 + 0.09604 ×700 =526.411

方案一: 方案二: 50600 700 500600 700 第一周买买 不买 第一周买不买不买 第三周买」买不买 周买不买不买 第三周买买 不买 第三周买不买不买 第四周买买 不买 第四周买不买不买 第五周买买 第五周买买 设n1=按第一方案购 设η2=按第二方案购 买的价格 买的价格 500 500 n1=1600 n2=1600 700 700 E(n1)=551536 E(72)=526411V

方案一： 500 600 700 第一周 买 买 不买 第二周 买 买 不买 第三周 买 买 不买 第四周 买 买 不买 第五周 买 买 买 设η1 =按第一方案购 买的价格 η1 =      700 600 500 =551.536 方案二： 500 600 700 第一周 买 不买 不买 第二周 买 不买 不买 第三周 买 不买 不买 第四周 买 不买 不买 第五周 买 买 买 设η2 =按第二方案购 买的价格 η2 =      700 600 500 E(1 ) E(2 ) =526.411 √

试间该部门应采用什么方案购进这(求E(S) 批原料,可使采购价格的期望值最小。[60 0.3 700 0.4 解:阶段k=1,2,3,4,5 状态变量s—第k周的实际价格=500600700 决策变量uSs)=在第k周实际价格为S时决定是否买 1买 0不买 f(sk)=在第k周实际价格为s时,从第k周至第5 周采用最优策略采购时价格 =min Sk El fk+ sk+1)]) 边界 f(S5)5006000 p 0.30.30.4 E[f(S5)]=500×0.3+600×0.3+700×0.4=610

试问该部门应采用什么方案购进这 批原料，可使采购价格的期望值最小。 原料价格ζ（元） 概率p 500 0.3 600 0.3 700 0.4 解：阶段k=1，2，3，4，5 状态变量sk—第k周的实际价格 决策变量uk (sk )=在第k周实际价格为sk时决定是否买 fk（sk）=在第k周实际价格为sk时，从第k周至第5 周采用最优策略采购时价格 ,sk=500,600,700 uk=    0 1 买 不买 sk ， fk+1(sk+1 =min{ } ) 边界： E[f5（S5）]= ( ) 1 1 求Ef s E[ ] 500×0.3+600×0.3+700×0.4 =610 500 600 700 p 0.3 0.3 0.4 f5（S5）

原料价格概率p -第k周的实际价格 4=买 (元) 500 0.3 =500600700 0不买 600 0.3 700 0.4 f(sk)=在第k周实际价格为s时,从第k周至第5 周采用最优策略采购时价格,求ELf(s 基本方程: f(s)=min{,E[(s那k-4,3,2,1 Ef(s9月=610 当k=4时f4(4)=mn{s4,E/(s}=mim{,610 500 S1=500 f(s4) 600 S4=600 610 700

基本方程： ( )   ( ) k=4，3，2，1 ( )    = = + + [ ] 610 min , 5 5 1 1 E f s f s s E f s k k k k k 原料价格ζ （元） 概率p 500 0.3 600 0.3 700 0.4 sk—第k周的实际价格 fk（sk）=在第k周实际价格为sk时，从第k周至第5 周采用最优策略采购时价格 =500,600,700 uk=    0 1 买 不买 , [ ( )] 1 1 求E f s        s 500 4=500 s 600 4=600 s 610 4=700 u4*=1 u4*=1 u4*=0 f 4 (s4 ) = min s4 ,E[ f 5 (s5 )] = min s4 ,610 f 4 (s4 ) = 当k=4时:

yKE-第k周决定等待,而以后用最优策「原料价格概率 略采购时价格的期望值 (元) 500 0.3 f(s)=在第k周实际价格为s时,从第k[6003 周至第5周采用最优策略采购时 700 0.4 价格=mn{Sk,E[fk(sk1) 500 S4=500 f(s,)=1600 S4=600 610 S4=700 与k=3时:f(3)=min{3,E[4(s那=mn53,574} E[/4(4)=500×03+600×03+610×04=574 500 2=500 * f(3) 574 600 574 S3700

= min sk ,Ef k+1 (sk+1 )        s 500 4=500 s 600 4=600 s 610 4=700 u4*=1 u4*=1 u4*=0 f 4 (s4 ) = 原料价格ζ （元） 概率p 500 0.3 600 0.3 700 0.4        s 500 3=500 s 574 3=600 s 574 3=700 u3*=1 u3*=0 u3*=0 f 3 (s3 ) = min s3 ,Ef 4 (s4 )= min s3 ,574 f 3 (s3 ) = 当k=3时: =500×0.3+600×0.3+610×0.4 =574 ykE--第k周决定等待，而以后采用最优策 略采购时价格的期望值 fk（sk）=在第k周实际价格为sk时，从第k 周至第5周采用最优策略采购时 价格  ( ) 4 4 E f s

yKE-第k周决定等待,而以后用最优策「原料价格概率 略采购时价格的期望值 (元) 500 0.3 f(s)=在第k周实际价格为s时,从第k[6003 周至第5周采用最优策略采购时 700 0.4 价格=mn{sk,E[f(sk1) 500 s3=500u3=1 3(s)=1574 S3=600 u3*=0 574 S3700 当k=2时f2(s2)=min{2,E[/(3)}=min{2,551:8} E[/3(3)=500×03+574×03+574×04=5518 500 S2=500 f(2) 551.8 S2=600 551.8 S,=700

原料价格ζ （元） 概率p 500 0.3 600 0.3 700 0.4        s 500 3=500 s 574 3=600 s 574 3=700 u3*=1 u3*=0 u3*=0 f 2 (s2 ) = min s2 ,Ef 3 (s3 )= min s2 ,551.8 f 3 (s3 ) = 当k=2时: =500×0.3+574×0.3+574×0.4 ykE--第k周决定等待，而以后采用最优策 略采购时价格的期望值 fk（sk）=在第k周实际价格为sk时，从第k 周至第5周采用最优策略采购时 价格 =551.8        s 500 2=500 s 551.8 2=600 s 551.8 2=700 u2*=1 u2*=0 u2*=0 f 2 (s2 ) = = min sk ,Ef k+1 (sk+1 )  ( ) 3 3 E f s

yKE-第k周决定等待,而以后用最优策「原料价格概率 略采购时价格的期望值 (元) 500 0.3 f(s)=在第k周实际价格为s时,从第k[6003 周至第5周采用最优策略采购时 700 0.4 价格=mn{sk2E[f(s1 500 S2=500 u’*=1 551.8 ,=600 5518 =700 与k=1时:f(s)=mmn{S12E[/2(s2)=min{s153626 E/2(2)=500×03+5518×03+5518×04=53626 500 S1=500 fils) 53626s1=600 u 536261=700

原料价格ζ （元） 概率p 500 0.3 600 0.3 700 0.4 当k=1时: f 1 (s1 ) = min s1 ,Ef 2 (s2 )= min s1 ,536.26 =500×0.3+551.8×0.3+551.8×0.4 ykE--第k周决定等待，而以后采用最优策 略采购时价格的期望值 fk（sk）=在第k周实际价格为sk时，从第k 周至第5周采用最优策略采购时 价格        s 500 1=500 s 536.26 1=600 s 536.26 1=700 u1*=1 u1*=0 u1*=0 f 1 (s1 ) =        s 500 2=500 s 551.8 2=600 s 551.8 2=700 u2*=1 u2*=0 u2*=0 f 2 (s2 ) = =536.26 = min sk ,Ef k+1 (sk+1 )  ( ) 2 2 E f s