资源分配问题实用教案

1、会计学1资源分配问题资源分配问题(wnt)第一页，共35页。2第1页/共35页第二页，共35页。3 项目投入资金ABC1 万元15 万吨13 万吨11 万吨2 万元28 万吨29 万吨30 万吨3 万元40 万吨43 万吨45 万吨4 万元51 万吨55 万吨58 万吨求对三个项目(xingm)的最优投资分配，使总投资效益最大。资资 源源 分分 配配 问问 题题第2页/共35页第三页，共35页。4fk(xk)=maxvk(xk ,dk)+fk+1(xk+1)8.边界条件：f4(x4)=0资资 源源 分分 配配 问问 题题第3页/共35页第四页，共35页。5x3D3(x3)x4v3(x3,d3)

2、v3(x3,d3)+f4(x4)f3(x3)d3*00000+0=0000100+0=01101111+0=11*1110200+0=0111111+0=112203030+0=30*3020300+0=0121111+0=11213030+0=303304545+0=45*4530400+0=0131111+0=11223030+0=30314545+0=454405858+0=58*584资资 源源 分分 配配 问问 题题第4页/共35页第五页，共35页。6x2D2(x2)x3v2(x2,d2)v2(x2,d2)+f3(x3)f2(x2)d2*00000+0=0000100+11=1111

3、01313+0=13*1310200+30=30*111313+11=242202929+0=293000300+45=45*121313+30=43212929+11=403304343+0=434500400+58=58131313+45=58222929+30=59*314343+11=544405555+0=55592资资 源源 分分 配配 问问 题题第5页/共35页第六页，共35页。7x1D1(x1)x2v1(x1,d1)v1(x1,d1)+f2(x2)f1(x1)d1*0400+59=59131515+45=60*222828+30=58314040+13=534405151+0=

4、51601最优解为 x1=4, d1*=1, x2=x1-d1=3, d2*=0, x3=x2-d2*=3, d3=3, x4=x3-d3=0， 即项目 A 投资 1 万元，项目 B 投资 0 万元，项目 C 投资 3 万元，最大效益为 60 万吨。 资资 源源 分分 配配 问问 题题第6页/共35页第七页，共35页。8第7页/共35页第八页，共35页。9 设有n种物品，每一种物品数量无限。 第i种物品每件重量为wi， 每件价值ci。现有一只可装载重量为 W 的背包，求各种物品应各取多少件放入背包， 使背包中物品的价值最高。 这个问题可以用整数规划模型来描述。设第i种物品取xi件 （i=1,2

5、,n，xi为非负整数） ，背包中物品的价值为z，则 背 包 问 题第8页/共35页第九页，共35页。10背 包 问 题第9页/共35页第十页，共35页。11背 包 问 题第10页/共35页第十一页，共35页。1230max)(max)(3/04433/033333333dxfdcxfwxdwxd列出f3(x3)的数值表 背 包 问 题第11页/共35页第十二页，共35页。13x3 D3(x3) x4 30d3+f4(x4) f3(x3) d3* 0 0 0 0+0=0 0 0 1 0 1 1 0 0+0=0 30+0=30* 30 1 2 0 1 2 2 1 0 0+0=0 30+0=30 6

6、0+0=60* 60 2 3 0 1 2 3 3 2 1 0 0+0=0 30+0=30 60+0=60 90+0=90* 90 3 4 0 1 2 3 4 4 3 2 1 0 0+0=0 30+0=30 60+0=60 90+0=90 120+0=120* 120 4 5 0 1 2 3 4 5 5 4 3 2 1 0 0+0=0 30+0=30 60+0=60 90+0=90 120+0=120 150+0=150* 150 5 第12页/共35页第十三页，共35页。14对于k=2 )3(80max)(max)(22323/03322/02222222dxfdxfdcxfxdwxd 列出

7、f2(x2)的数值表 x2 D2(x2) x3 80d2+f3(x3) f2(x2) d2* 0 0 0 0+f3(0)=0+0=0* 0 0 1 0 1 0+f3(1)=0+30=30* 30 0 2 0 2 0+f2(2)=0+60=60* 60 0 3 0 1 3 0 0+f3(3)=0+90=90* 80+f3(0)=80+0=80 90 0 4 0 1 4 1 0+f3(4)=0+120=120* 80+f3(1)=80+30=110 120 0 5 0 1 5 2 0+f3(5)=0+150=150* 80+f3(2)=80+60=140 150 0 第13页/共35页第十四页，共

8、35页。15对于k=1 )2(65max)(max)(11212/02211/01111111dxfdxfdcxfxdwxd 列出f1(x1)的数值 x1 D1(x1) x2 65d1+f2(x2) f1(x1) d1* 0 0 0 0+f2(0)=0+0=0* 0 0 1 0 1 0+f2(1)=0+30=30* 30 0 2 0 1 2 0 0+f2(2)=0+60=60 65+f2(0)=65+0=65* 65 1 3 0 1 3 1 0+f2(3)=0+90=90 65+f2(1)=65+30=95* 95 1 4 0 1 2 4 2 0 0+f2(4)=0+120=120 65+f2

9、(2)=65+60=125 130+f2(0)=130+0=130* 130 2 5 0 1 2 5 3 1 0+f2(5)=0+150=150 65+f2(3)=65+90=155 130+f2(1)=130+30=160* 160 2 第14页/共35页第十五页，共35页。16由题意知，x1=5，由表f1(x1)、f2(x2)、f3(x3)，经回朔可得： d1*=2，x2=x1-2d1=1，d2*=0，x3=x2-3d2=1，d3*=1，x4=x3-d3=0 即应取第一种物品 2 件,第三种物品 1 件,最高价值为 160 元,背包没有余量。由f1(x1)得列表可以看出，如果背包得容量为W

10、=4，W=3，W=2 和W=1 时，相应的最优解立即可以得到。 第15页/共35页第十六页，共35页。17第16页/共35页第十七页，共35页。18月份(k) 1 2 3 4 5 6 7 生产成本(ck) 11 18 13 17 20 10 15 需求量(rk) 0 8 5 3 2 7 4 为了调节生产和需求， 工厂设有一个产品仓库，库容量H=9。已知期初库存量为 2，要求期末（七月低）库存量为 0。每个月生产的产品在月末入库，月初根据当月需求发货。 求七个月的生产量， 能满足各月的需求， 并使生产成本最低。 生生 产产 库库 存存 问问 题题第17页/共35页第十八页，共35页。19；n阶段

11、指标：vk(xk ,dk)=ckdk；n终端条件：f8(x8)=0,x8=0；生生 产产 库库 存存 问问 题题第18页/共35页第十九页，共35页。20生生 产产 库库 存存 问问 题题第19页/共35页第二十页，共35页。21生生 产产 库库 存存 问问 题题第20页/共35页第二十一页，共35页。22生生 产产 库库 存存 问问 题题第21页/共35页第二十二页，共35页。23生生 产产 库库 存存 问问 题题第22页/共35页第二十三页，共35页。24生生 产产 库库 存存 问问 题题第23页/共35页第二十四页，共35页。25 由于 在f4(x4)的表达式中d4的系数是-3， 因此d

12、4在决策(juc)允许集合中应取集合中的最大值，即d4=12-x4由此 f4(x4)=-3(12-x4)-20 x4+280 =-17x4+244生生 产产 库库 存存 问问 题题第24页/共35页第二十五页，共35页。26生生 产产 库库 存存 问问 题题第25页/共35页第二十六页，共35页。27生生 产产 库库 存存 问问 题题第26页/共35页第二十七页，共35页。28生生 产产 库库 存存 问问 题题第27页/共35页第二十八页，共35页。29生生 产产 库库 存存 问问 题题第28页/共35页第二十九页，共35页。30k 1 2 3 4 5 6 7 ck 11 18 13 17 20 10 15 rk 0 8 5 3 2 7 4 xk 2 9 5 9 9 7 4 d