运筹学课件 主讲:唐晓斌 ●课件制作:何茂佳 小组成员: ●何茂佳2002044034 ●唐晓斌2002044051 ●袁浩2002044027 ●彭苑建2002044045 ●李一良2002044057 ●陈庆宇2002044013 谭爱桃2002044056 ●周军2002044030
运筹学课件 • 主 讲：唐晓斌 • 课件制作：何茂佳 • 小组成员： • 何茂佳2002044034 • 唐晓斌2002044051 • 袁 浩2002044027 • 彭苑建2002044045 • 李 良2002044057 • 陈庆宇2002044013 • 谭爱桃2002044056 • 周 军2002044030
例9采购与销售问题 某商店在未来的4个月里,准备用它的一个仓库来专门经销某种商 品,仓库最大容量能贮存这种商品1000单位假定该商店每月只能出卖 仓库现有的货当商店在某月购货时,下月初才能到货预测该商品未来 四个月的买卖价格如表7-12所示,假定商店在1月开始经销时,仓库贮有 该商品500单位试问若不计库存费用,该商店应如何制定1月至4月的 订购与销售计划,使预期获利最大。 月份()购买单位(C)销售单位(P 10 1234 11 15 837
例9 采购与销售问题 某商店在未来的4个月里,准备用它的一个仓库来专门经销某种商 品,仓库最大容量能贮存这种商品1000单位.假定该商店每月只能出卖 仓库现有的货,当商店在某月购货时,下月初才能到货.预测该商品未来 四个月的买卖价格如表7-12所示,假定商店在1月开始经销时,仓库贮有 该商品500单位.试问若不计库存费用,该商店应如何制定1月至4月的 订购与销售计划,使预期获利最大。 12 8 13 17 10 9 11 15 1 2 3 4 月份(k) 购买单位( ) 销售单位( ) k c pk
解 按月份划分为4个阶段,K=1,2,3,4 状态变量S:第K月初时仓库中的存货量(含上月订货) 决策变量Xk:第K月卖出的货物数量 yk:第K月定购的货物数量 状态转移方程:Sk+1=Sk+yk+Xk 最优指标函数:第K月初存货量为时,从第K月到4月末所获得最大利润 则有逆序递推关系式为: f(s)= max LPX-CV+J&(+DI 0≤x.≤ Sk 0≤y≤1000-(3-x) k=4,3,2,1 s)=0
k s 解 ： 按月份划分为4个阶段， 状态变量 : 决策变量 ： ：第K月定购的货物数量 状态转移方程： 最优指标函数 ：第K月初存货量为 时，从第K月到4月末所获得最大利润。 则有逆序递推关系式为： k 4,3,2,1 ( ) [ ( )] 0 1000 ( ) 0 ( ) max 5 5 1 1 0 = = − + − − = + + f s p x c y f s y s x x s f s k k k k k k k k k k k k k xk yk sk +1= sk + yk + xk 第K月初时仓库中的存货量（含上月订货） K＝1，2，3，4 第K月卖出的货物数量
当K=4时 f(s)= max[,] 0<x,<S 0y341000(54x4 显然,决策应取x=S,y=0时才有最大值:f(s)=175 当K=3时 max 13x3-11y3+f4(S4) 0≤x2≤ 0≤y3s1000(33-x3) max13x3-11y3+17(s3+y3-x3) 0≤x2≤s 0≤y3≤1000(s3-x3) max[-4x3+63+173 0≤x2≤S 0≤y3≤1000(53-x3)
当 K＝4 时 ( ) max [17 15 ] 4 4 3 4 4 4 4 4 4 0 1000 ( ) 0 f s x y y s x x s = − − − 显然，决策应取 x4 * = s4 ， y4 * = 0 时才有最大值： 4 4 17 4 f (s)= s 当 K＝3 时 ( ) max [13 11 ( )] 3 3 4 4 0 1000 ( ) 0 3 3 3 3 3 3 3 f s x y f s y s x x s = − + − − max [13 11 17( )] 3 3 3 3 3 0 1000 ( ) 0 3 3 3 3 3 x y s y x y s x x s = − + + − − − max [ 4 6 17 ] 3 3 3 0 1000 ( ) 0 3 3 3 3 3 x y s y s x x s = − + + − −
这个阶段需求解一个线性规划问题 maxz=-4s3+6y3+17s3 X2≤S y3=x3≤10083 x3y3≥0 因为只有两个变量x3y3,可以用图解法,也可以用单纯形法,求解得到 x3=s3y3=1000时有最大值f3(3)=6000+1353 当K=2时 max[8x2-9y2+f3(2+y2-x2) ≤S2 0≤y2≤1000-(s2-x2) max8x2-9y2+6000+13(2+y2=x2) 0≤x2≤S 0≤y2≤1000-(s2-x2) amX600135-5x2+4y2 0≤y2≤1000-(
这个阶段需求解一个线性规划问题： − − = − + + 0 1000 x max 4 6 17 3, 3 3 3 3 3 3 3 3 3 x y y x s s z s y s 因为只有两个变量 x3 ， y3 ，可以用图解法，也可以用单纯形法，求解得到： , 1000 * 3 3 * x3 = s y = 时有最大值 3 3 6000 13 3 f (s ) = + s 当 K＝2 时 ( ) max [8 9 ( )] 2 2 3 2 2 2 0 1000 ( ) 0 2 2 2 2 2 2 2 f s x y f s y x y s x x s = − + + − − − max [8 9 6000 13( )] 2 2 2 2 2 0 1000 ( ) 0 2 2 2 2 2 x y s y x y s x x s = − + + + − − − max [6000 13 5 4 ] 2 2 2 0 1000 ( ) 0 2 2 2 2 2 s x y y s x x s = + − + − −
求解线性规划问题 maxz=6000+13s2-5x2+4 x2≤S y2-x2≤1000 ≥0 得:x3=0,y3=1000-S2 2(S2)=6000+132+4000-4s2=1000+9 当K=1时 f(s1) max 12x1-10y1+f2(S1+y1-x1 0≤x1≤ 0≤y1000(51-x1) 因为S1=500 所以(500)=max2x1-10y1+10000+9s1+y-x1 0≤x1≤500 0≤y1≤500+x mx3x1-y1+14501 x1≤500 0≤y1≤500+x1
求解线性规划问题： − − = + − + , 0 1000 max 6000 13 5 4 2 2 2 2 2 2 2 2 2 2 x y y x s x s z s x y 得： 2 2 6000 13 2 4000 4 2 1000 9 2 f (s ) = + s + − s = + s 2 * 3 * x3 = 0, y = 1000 − s 当 K＝1 时 ( ) max [12 10 ( 1)] 1 1 2 1 1 0 1000 ( ) 0 1 1 1 1 1 1 1 x y s x x s f s = x − y + f s + y − − − 因为 s1 = 500(500) max [12 10 10000 9( 1)] 1 1 1 1 0 500 0 500 1 1 1 1 x y x x f = x − y + + s + y − + max [3 14500] 1 1 0 500 0 500 1 1 1 = − + + x y y x x 所以
解线性规划问题 maxz=14500+3x1-y x,<500 y1=x1≤500 x12y1≥0 得决策x1=500y1=0.f(500)=14500+3×500=16000 最优策略见下表,最大利润为16000 月份期前存货()售出量()购进量( 500 500 0 2 0 0 1000 34 1000 1000 1000 1000 1000 0
− = + − , 0 500 500 max 14500 3 1 1 1 1 1 1 1 x y y x x z x y 解线性规划问题： 得决策 500, 0, 1 (500) 14500 3 500 16000 * 1 * x1 = y = f = + = 最优策略见下表，最大利润为16000 月份 期前存货( ) 售出量（ ） 购进量（ ） 1 500 500 0 2 0 0 1000 3 1000 1000 1000 4 1000 1000 0 sk xk yk