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

7.3某厂每月生产某种产品最多600件，当月生产的产品若未销出，就需贮存（刚入库的产品下月不付存储费）月初就已存储的产品需支付存储费，每100件每月1000元。已知每100件产品的生产费为5千元，在进行生产的月份工厂支出经营费4千元，市场需求如表7-19所示，假定1月初及4月底库存量为零，试问每月应生产多少产品，才能在满足需求条件下，使总生产及存贮费用之和最小。月份1234产品（100件）5321解：设阶段变量：k=1,2,3状态变量：kx第k个月初的库存量决策变量：kd第k个月的生产量状态转移方程：1kkkkxxrd阶段指标：(,)kkkkvxdcd由于在4月末，仓库存量为0，所以对于k=4阶段来说有两种决策：5+4=940x4()fx=141x对K=3334()54()fxxfx3d3x01234563()fx3d02*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=2d2X20123456f(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=283*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,3,2,1k，每一个项目表示一个阶段;状态变量Sk，表示可用于第k阶段及其以后阶段的投资金额；决策变量Ｕk，表示在第k阶段状态为Sk下决定投资的投资额；决策允许集合：0≤Ｕk≤Sk状态转移方程：Sk+1=Sk-Ｕk;阶段指标函数：Vk(SkＵk)；最优指标函数：fk(Sk)=max{Vk(SkＵk)+fk+1(Sk+1)}终端条件：f4(x4)=0；K=4,f4(x4)=0k=3,0≤Ｕ3≤S3S3Ｕ3f3(S3)=max{V3(S3Ｕ3)+f4(S4)}f3(S3)U3*0123400001064641206468682306468787834064687876783k=2,0≤Ｕ2≤S2S2Ｕ2f2(S2)=max{V2(S2Ｕ2)+f3(S3)}f2(S2)U2*0123400+00010+6442+064020+6842+6450+0106130+7842+6850+6460+0114240+7842+7850+6860+6466+01243k=1,0≤Ｕ1≤S1S1Ｕ1f1(S1)=max{V1(S1Ｕ1)+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为了保证某设备正常运行,须对串联工作的三种不同零件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)递退方程：114431()max{()()}()1()(1)kkKkkkKkKiikfsRxfsfsCxSC所以有上可知当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=016120.2*0.2=0.040.5*0=0130.9*0=071230.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由上表可知，最优解的可靠性为0.042；此时X1=1；X2=1；X3=3。7.7某工厂接受一项特殊产品订货，要在三个月后提供某种产品1000kg，一次交货。由于该产品用途特殊，该厂原无存货，交货后也不留库存。已知生产费用与月产量关系为：C=1000+3d+0.005d2，其中d为月产量（kg），C为该月费用（元）。每月库存成本为2元/kg，库存量按月初与月末存储量的平均数计算，问如何决定3个月的产量是总费用最小。解：用动态规划法求解阶段k：每一个月为一个阶段k=1,2,3状态变量sk：第k个月初的库存量决策变量dk：第k个月的生产量状态转移方程：s1k=sk+dk最优指标函数：fk(sk)：第k个月状态为sk时到第3个月末的总费用最小则第k个月的库存费用为：Ek=（sk+s1k）/22=sk+s1k=2sk+dks1=0，d1+d2+d3=1000当k=3时f3(s3)=min{E3+C3}=min{2s3+d3+1000+3d3+0.005d23}=min{3000+2d3+0.005d23}=3000+2(1000-s3)+0.005(1000-s3)2当k=2时f2(s2)=min{E2+C2+f3(s3)}=min{2s2+d2+1000+3d2+0.005d22+3000+2(1000-s3)+0.005(1000-s3)2}=min{2s2+1000+4d2+0.005d22+3000+2(1000-s2-d2)+0.005(1000-s2-d2)2}=min{6000+2d2+0.005d22+0.005(1000-s2-d2)2}只有当d*2=1000-s2时f2(s2)取最小值6000+2（1000-s2）+0.005（1000-s2）2f1(s1)=min{E1+C1+f2(s2)}=min{2s1+d1+1000+3d1+0.005d21+6000+2（1000-s2）+0.005（1000-s2）2}=min{9000+4d1+0.005d21+0.005（1000-d1）2}=min{14000-6d1+0.01d21}只有当d*1=300时f1(s1)取最小值13100元此时s2=d1+s1=300那么d*2=1000-s2=700，f2(s2)=9850元d*3=1000-d1-d2=0，f3(s3)=3000元即：三个月的产量分别为300、700、0时，总费用最小。7-11.某工厂生产三种产品，各产品重量与利润关系如表。现将此三种产品运往市场出售，运输总重量不超过6t，应运输每件产品各多少件使总利润最大？产品重量（t/每件）利润（千元/每件）12802313034180解：设:kX：第K种产品的数目；kV：第K种产品的利润；kS：第K种产品之初的总重量；1kkkkSSXW;kf(kS)：第K~3种产品的总价值；kf（kS）=max{kXkV+`1kf(1kS)}且4f(4S)=0K=3：333013344()max{()}xfSVXfS3013max{80}xXkS0~34~6*1X数目01180K=2：222022233()max{()}xfSVXfS2022332max{130(3)}xXfSX2S2X3S2332130(3)XfSX6*2X000000101000202000301300130+0=1301301401410+180=180130+0=1301800501520+180=180130+0=130180060126300+180=180130+0=130260+0=2602602K=1：111031122()max{()}xfSVXfS1031211max{80(2)}xXfSX答:故最大利润为260，产品数目为“0，2，0”或“1，0，1”。7.12某公司需要对某产品决定未来4个月内每个月的最佳存储量，以使总费用最小。已知各月对该产品的需求量和单位订货费用、存储费用如表7-23所示。假定每月初订货于月末到货并入库，下月开始销售。表7-23月份k1234需求量dk50454030单位订货费用Ck850850775825单位存储费用Pk35204030解：阶段k：月份k=1，2，3，4，5状态变量Xk：第k个月初的存量决策变量r：第k个月的订货量状态转移方程：Xk+1=Xk+rk-dk决策允许集合：rk（Xk）=｛rk︱rk≥0dk+1≤Xk+1｝=｛rk︱dk+1≤Xk+rk-dk｝1S1X2S121180(2)XfSX11()fS*1X6060+260=2602600/11480+180=26022160+0=16030240+0=240阶段指标：Ckrk+PkXkf5（X5）=0X5=0fk（Xk）=min｛Vk(Xk,rk)+fk+1(Xk+1)｝=min｛Ckrk+PkXk+fk+1(Xk+rk-dk)｝对于k=4X5=0r4=0X4=d4f4（X4）=min｛V4(X4,r4)+f5(X5)｝=min｛30X4｝=900对于k=3F3（X3）=min｛V3(X3,r3)+f4(X4)｝=min｛C3r3+P3X3+f4(X4)｝=min｛40r3+40X3+900｝=min{775r3+40x3+900}d4=x4则d4=x3+r3-d3r3+d3+d4-x3=70-x3f3(x3)=min{775(70-x3)+40x3+900}=min{63250-735x3}当k=2时f2（x2）=min｛C2r2+P2x2+f3(x3)｝=min{850r2+20x2+63250-735(x2+r2-d2)}=min{850r2+20x2+63250-735x2-735r2+33075}=min{96325-715x2+115r2}R2(x2)={r2r20d3x2+r3-d2}={r2r20d3+d2-x2r3}={r2r2085-x2r3}f2（x2）=min｛96325-715x2+115x2+9775｝=min{106100-830x2}当k=1时f1（x1）=min｛850r1+30x1+106100-830(x1+r1-50)｝=min{147600-800x1+20r1}r1（x1）=｛r1︱r1≥0d2+d1﹣x1≤r1｝=｛r1︱r1≥095﹣x1≤r1｝f1（x1）=min｛147600-800x1+20（95﹣X1）｝=min｛149500-820x1｝根据题意x1=0r1*=95﹣x1f1（x1）=149500r1*=95r1*=95x2=x1+r1-d1=45f2（x2）=68750r2*=85