胡运权运筹学第七章习题解

1、7.3某厂每月生产某种产品最多600件，当月生产的产品若未销出，就需贮存（刚入库的产品下月不付存储费）月初就已存储的产品需支付存储费，每100件每月1000元。已知每100件产品的生产费为5千元，在进行生产的月份工厂支出经营费4千元，市场需求如表7-19所示，假定1月初及4月底库存量为零，试问每月应生产多少产品，才能在满足需求条件下，使总生产及存贮费用之和最小。月份1234产品（100件）5321解：设阶段变量：k=1,2,3状态变量： 第k个月初的库存量决策变量：第k个月的生产量状态转移方程：阶段指标：由于在4月末，仓库存量为0，所以对于k=4阶段来说有两种决策： 5+4=9 = 1 对K=

2、3 012345602*5+4+9=233*5+4+1=2020311*5+4+9=182*5+4+1+1=1616222*5+9=191*5+1+4+1=1111133*1+1=440K=2 d2X2 0123456f(x)d03*5+4+20=394*5+4+16=395*5+4+106*5+4+438611+2*5+4+20=353*5+4+16+1=364*5+4+11+1=365*5+4+4+1=3434521*4+4+20+2=2302*5+4+16+2=323*5+4+11+2=324*5+4+4+2=3030433+20=321*5+4+16+3=282*5+4+11+3=28

3、3*5+4+4+3=2323344+16=205+4+11+4=232*5+4+4+4=2220055+11=161*5+4+4+5=1616066+4=10100K=1时0123456F(x)d05*5+4+38=676*5+4+34=68675 解得：第一个月生产500份，第二个月生产600份，第三个月生产0份，第四个月生产0份。7.4某公司有资金4万元，可向A，B，C三个项目投资，已知各项目不同投资额的相应效益值如表7-20所示，问如何分配资金可使总效益最大。表 7-20项目投资额01234A041486066B042506066C064687876解：设阶段变量k，每一个项目表示一个阶

4、段;状态变量Sk，表示可用于第k阶段及其以后阶段的投资金额；决策变量k，表示在第k阶段状态为Sk下决定投资的投资额； 决策允许集合：0kSk 状态转移方程：Sk+1=Sk-k; 阶段指标函数：V k(Skk)； 最优指标函数：fk(Sk)=max V k(Skk)+ fk+1(Sk+1) 终端条件：f4(x4)=0； K=4, f4(x4)=0 k=3, 03S3 S3 3f3(S3)=max V3(S33)+ f4(S4)f3(S3)U3*0123400001064641206468682306468787834064687876783k=2, 02S2S2 2f2(S2)=max V 2(

5、S22)+ f3(S3)f2(S2)U2*0123400+00010+6442+064020+6842+6450+0106130+7842+6850+6460+0114240+7842+7850+6860+6466+01243k=1, 01S1S1 1f1(S1)=max V1(S11)+ f2(S2)f1(S1)U1*03400+00010+6441+064020+10641+6448+0106130+11441+10648+6460+0114040+12441+11448+10660+6455+01551所以根据以上计算，可以得到获得总效益最大的资金分配方案为（1，2，1）.7.5为了保证

6、某设备正常运行,须对串联工作的三种不同零件A1,A2,A3,分别确定备件数量。若增加备用零件数量，可提高设备正常运转的可靠性，但费用要增加，而总投资额为8千元。已知备用零件数和他的可靠性和费用关系如表所视，求A1,A2,A3,的备用零件数个为多少时可使设备运转的可靠性最高。设备数可靠性备用零件费用（千元）A1A2A3A1A2A310.30.20.113220.40.50.225330.50.90.7364解：设第k阶段的状态为Sk；第k阶段决定投入的备件为Xk;Ck(Xk)为第k阶段选择k个零件的费用；Rk(Xk)为第k个阶段选择k个零件的可靠性。状态转移方程为：Sk+1=Sk- Ck(Xk)

7、递退方程：所以有上可知当A1；A2；A3；分别为k=1;k=2;k=3时S1=8; S2=5,6,7; S3=1,2,3,4;当k=3时S3X3F3(x3)X3*100无210.113120. 10.2241230.10.20.73当k=2时S2X2F2(x2)X2*5120. 2*0.1=0.020.5*0=0161230. 2*0.2=0.040. 5*0=00.9*0=0171230. 2*0.7=0.140.5*0.1=0.050.9*0=01当k=1时S1X1F1(x1)X1*81230.3*0.14=0.0420.4*0.04=0.0160.5*0.02=0.011由上表可知，最优

8、解的可靠性为0.042；此时X1=1；X2=1；X3=3。7.7 某工厂接受一项特殊产品订货，要在三个月后提供某种产品1000kg，一次交货。由于该产品用途特殊，该厂原无存货，交货后也不留库存。已知生产费用与月产量关系为：C=1000+3d+0.005d，其中d为月产量（kg），C为该月费用（元）。每月库存成本为2元/kg，库存量按月初与月末存储量的平均数计算，问如何决定3个月的产量是总费用最小。解：用动态规划法求解阶段k：每一个月为一个阶段k=1,2,3状态变量s：第k个月初的库存量决策变量d：第k个月的生产量状态转移方程：s= s+d最优指标函数：f( s)：第k个月状态为s时到第3个月末

9、的总费用最小则第k个月的库存费用为：E= （s +s）/22= s +s=2 s+ds=0，d+d+d=1000 当k=3时f(s)=minE+C =min2s+d+1000+ 3d+0.005d = min3000+ 2d+0.005d = 3000+2(1000- s)+0.005(1000- s) 当k=2时f(s)=minE+C+ f(s) =min2s+d+1000+3d+0.005d+3000+2(1000- s)+0.005(1000- s)=min2s+1000+4d+0.005d+3000+2(1000-s-d)+0.005(1000- s-d)=min6000+2d+0.0

10、05d+0.005(1000- s-d)只有当d=1000- s 时f(s)取最小值6000+2（1000- s）+0.005（1000- s）f(s)=minE+C+ f(s) =min2 s+ d+1000+3 d+0.005d+6000+2（1000- s）+0.005（1000- s） =min9000+4 d+0.005d+0.005（1000- d）=min14000-6d+0.01d 只有当d=300时f(s)取最小值13100元 此时s= d+ s=300那么d=1000- s=700，f(s)=9850元 d=1000-d-d=0，f(s)=3000元即：三个月的产量分别为3

11、00、700、0时，总费用最小。7-11.某工厂生产三种产品，各产品重量与利润关系如表。现将此三种产品运往市场出售，运输总重量不超过6t，应运输每件产品各多少件使总利润最大？产品重量（t/每件）利润（千元/每件）12802313034180解：设:：第K种产品的数目；：第K种产品的利润；：第K种产品之初的总重量；; ()：第K3种产品的总价值；（）=max+()且()=0K=3：0346数目01180K=2：6000000101000202000301300130+0=1301301401410+180=180130+0=1301800501520+180=180130+0=130180060

12、126300+180=180130+0=130260+0=2602602K=1：6060+260=2602600/11480+180=26022160+0=16030240+0=240答:故最大利润为260，产品数目为“0，2，0”或“1，0，1”。7.12 某公司需要对某产品决定未来4个月内每个月的最佳存储量，以使总费用最小。已知各月对该产品的需求量和单位订货费用、存储费用如表7-23所示。假定每月初订货于月末到货并入库，下月开始销售。表7-23月份k1234需求量dk50454030单位订货费用Ck850850775825单位存储费用Pk35204030解：阶段k：月份 k=1，2，3，4

13、，5状态变量Xk：第k个月初的存量决策变量r：第k个月的订货量状态转移方程：Xk+1=Xk+rk-dk决策允许集合：rk（Xk）=rkrk0 dk+1Xk+1 =rkdk+1Xk+rk-dk阶段指标：Ckrk +PkXkf5（X5）=0 X5=0fk（Xk）=minVk(Xk, rk)+fk+1(Xk+1) =minCkrk+ PkXk + fk+1(Xk+rk-dk)对于k=4 X5=0 r4=0 X4=d4f4（X4）=minV4(X4, r4)+f5(X5) =min30 X4 =900对于k=3F3（X3）=minV3(X3, r3)+f4(X4) =minC3r3+ P3X3 + f

14、4(X4) =min40r3+ 40X3 + 900=min775r3+40x3+900d4=x4 则 d4=x3+r3-d3 r3+d3+d4-x3=70-x3f3(x3)=min775(70-x3)+40x3+900 =min63250-735x3当k=2时f2（x2）=minC2r2+ P2x2 + f3(x3)=min850r2+20x2+63250-735(x2+r2-d2)=min850r2+20x2+63250-735x2-735r2+33075=min96325-715x2+115r2R2(x2)=r2 r20 d3x2+r3-d2 =r2 r20 d3+d2 -x2r3 =r

15、2 r20 85-x2r3 f2（x2）=min96325-715x2+115 x2+9775=min106100-830x2当k=1时f1（x1）=min850r1+30x1+106100-830(x1+r1-50) =min147600-800x1+20r1r1（x1）=r1r10 d2+d1x1r1 =r1r10 95x1r1f1（x1）=min147600-800 x1+20（95X1） =min149500-820 x1根据题意x1=0 r1*=95x1f1（x1）=149500 r1*=95r1*=95x2 =x1+r1-d1 =45 f2（x2）= 68750r2*=8545=4

16、0x3 =x2+r2-d2=45+40-45=40f3（x3）=33850x4 = d4=30f4（x4）=9007.13 某罐头制造公司在近5周内需要一次性地购买一批原料，估计未来5周内价格有波动，其浮动价格及概率如表7-24所示，试求各周的采购策略，使采购这批原料价格的数学期望值最小。表7-24批单价概率90.480.370.3解：设阶段变量k，,每一周表示一个阶段;状态变量Sk，表示第k阶段的实际价格；决策变量k，当k=1，表示第k周决定采购；当k=0，表示第k周决定等待。SkE表示第k周决定等待，而在以后采用最优决策时采购价格的期望值； fk(Sk)表示第k周实际价格为Sk时，从第k周

17、至第五周采用最优决策所得的最小期望值。因而可写出逆序递推关系式为fk(Sk)=min Sk, SkE Sk9,8,7 (1)由SkE和fk(Sk)的定义可知SkE=E fk+1 (Sk+1)=0.4fk+1 (9)+0.3 fk+1 (8)+ 0.3 fk+1(7), (2) k=5 因为如果在第五周原材料尚未购买，则不管实际价格如何，都必须采取采购策略。 f5(S5)= S5 , 即f5(7) =7，f5(8)=8， f5(9)=9 k=4 S4E =0.4f5 (9)+0.3 f5 (8)+ 0.3 f5(7)=8.1 f4(S4)=min S4, S4E=min S4, 8.1= 所以在

18、第四周如果价格为9，则等待下周购买，如果价格为8或7，则选择采购k=3 S3E =0.4f4 (9)+0.3 f4(8)+ 0.3 f4(7)=7.74 f3(S3)=min S3, S3E=min S3, 7.74= 所以在第三周如果价格为9或8，则等待下周购买，如果价格为7，则选择购买k=2 S2E =0.4f3(9)+0.3 f3(8)+ 0.3 f3(7)=7.518 f2(S2)=min S2, S2E=min S2, 7.518=所以在第二周如果价格为9或8，则等待下周购买，如果价格为7，则选择购买k=1 S1E =0.4f2(9)+0.3 f2(8)+ 0.3 f2(7)=7.3

19、626 f1(S1)=min S1, S1E=min S1, 7.518=所以在第一周如果价格为9或8，则等待下周购买，如果价格为7，则选择购买7.14 某企业有1000万元资金可在三年内每年初对项目A、B投资，若每年初投资项目A，则年末以0.6的概率回收本利2000万元或以0.4的概率丧失全部资金；若投资项目B，则年末以0.1的概率回收本利2000万元或以0.9的概率回收1000万元。假定每年只能投资一次,每次1000万元（有多余资金也不使用），试给出三年末期望总资金最大的投资策略。K表示第K年的投资方案过程，状态表示每年可投资的资金，表示第K年的投资决策=阶段指标=0.6*(1)（2000+1000）+(0.1*2000+0.9*1000+10000)基本方程即每年年末期望最大总资金期望最大总资金的投资策略为7.15 某汽车公司的一个型号汽车，每辆年均利润函数r(t)与年均维修费用函数u(t) 如上表中所示 ，购买同型号新