运筹学-第八章

西安邮电学院试题库管理系统——试题表第1页共17页专业代码11专业名称信息管理与信息系统课程代码18课程名称运筹学试题类型代码08试题类型名称计算题出题人管理员出题日期2005-11-4知识点代码题干答案评分标准难度系数认知分类建议分数建议时间1118080110吨集装箱最多只能装9吨，现有3种货物供装载，每种货物的单位重量及相应单位价值如表所示。应该如何装载货物使总价值最大。货物编号123单位加工时间234单位价值345【解】设装载第I种货物的件数为xi（i=1,2,3）则问题可表为：123123123max3452349,,0zxxxxxxxxx且为整数利用背包问题的前向动态规划计算，建立动态规划模型。由于决策变量离散型值，所以可用列表法求解。当R=1时，121210/2()max(3)xsfsx。计算结果如下：s20123456789f（s2）003366991212x1*0011223344当R=2时，f2（s3）=4/210maxsx[4x2+f1（s3-3x2）]计算结果如下：s30123456789x20000101010120120120123C2+f2003346467978910812101112131112f2（s3）0034679101213x2*0001010101当R=3时，f3（9）=230maxx[5x3+f2（9-4x3）]（x3为整数）=220maxx[f2（9），5+f2（5），10+f2（1）]=max[13，12，10]=13较难分析1214设有两种资源，第一种资源有x单位，第二种资源有y单位,计划分配给n个部门。把第一种资源有xi单位，第二种资源有yi单位分配给部门i所得的利润为记为ri（xi，yi）。如设x=3，y=3，n=3，其利润ri（x，y）列于表中，试用动态规划方法如何分配这两种资源到i个部门去，使总的利润最大？yxr1（x，y）r2（x，y）r3（x，y）012301230123001360246035814567146725792567846894791136789681011691113最优决策为：33163002001332211，，最大利润为，，，，，fyxyxyx中运用1012有一辆货车载重量为10吨，用来装载货物A、B时成本分别为5元/吨和4元/吨。现在已知每吨货物的运价与该货物的重量有如下线性关系：A：P1=15-x1，B：P2=18-2x2其中x1、x2分别为货物A、B的重量。如果要求货物满载，A和B各装载多少，才能使总利润最大【解】由题意可得各种货物利润函数为21111112222222()(155)10()(1824)142gxxxxxgxxxxx原问题的数学模型归结为2211221212max(10)(142)10,0zxxxxxxxx最优解：x1=6，x2=4；z＝48某有限公司有五台新设备，将有选择的分配配给下属的三个工厂，所得收益如表中所示。问该公司应如何分配设备，可使总收益最大？单位：千元新设备台数工厂ⅠⅡⅢ000013542710639111141211125131112答案：两种最优分配方案总收益均为21千元西安邮电学院试题库管理系统——试题表第2页共17页某公司有5台设备，分配给所属A,B,C三个工厂。各工厂获得不同的设备台数所能产生效益（万元）的情况如下表。求最优分配方案，使总效益最大。（用动态规划方法求解）台数工厂012345A01015202325B51720222324C71215182023答案：阶段k：每分配一个工厂作为一个阶段；状态变量xk：分配第k个工厂前剩余的设备台数；决策变量dk：分配给第k个工厂的设备台数；决策允许集合：0≤dk≤xk状态转移方程：xk+1=xk-dk阶段指标：vk(xk,dk)第k次分配产生的效益，见表中所示；递推方程：fk(xk)=max{vk(xk,dk)+fk+1(xk+1)}终端条件：f4(x4)=0k=4，f4(x4)=0k=3，分配给工厂C，0≤d3≤x3，x4=x3-d3x3D3(x3)x4v3(x3,d3)v3(x3,d3)+f4(x4)f3(x3)d3*00077+0=00010177+0=7121101212+0=12*20277+0=7152111212+0=12201515+0=15*30377+0=7183121212+0=12211515+0=15301818+0=18*40477+0=7204131212+0=12221515+0=15311818+0=18402020+0=20*50577+0=7235141212+0=12231515+0=15321818+0=18412020+0=20502323+0=23*k=2，分配给工厂B，0≤d2≤x2，x3=x2-d2x2D2(x2)x3v2(x2,d2)v2(x2,d2)+f3(x3)f2(x2)d2*00055+7=1212010155+12=17241101717+7=24*20255+15=20291111717+12=29*202020+7=2730355+18=23321或2121717+15=32*212020+12=32*302222+7=2940455+20=25351或2131717+18=35*222020+15=35*312222+12=34402323+7=3050555+23=28382141717+20=37232020+18=38*322222+15=37412323+12=35502424+7=31k=1，分配给工厂A，0≤d1≤x1，x2=x1-d1x1D1(x1)x2v1(x1,d1)v1(x1,d1)+f2(x2)f1(x1)d1*50500+38=38493141010+35=45231515+32=47322020+29=49*412323+24=47502525+12=37最优解为x1=5,d1*=3,x2=x1-d1=2,d2*=1,x3=x2-d2*=1,d3=1,x4=x3-d3=0，即分配给工厂A设备3台，工厂B设备1台，工厂C设备1台，最大效益为49万元。较难分析1212某公司决定投资60万元（以10万元为单位），以提高三种主要产品A、B、C的产量。现决定每种产品至少要投资10万元。各种产品投资不同资金后可获得的期望利润如下：分配的投资金额利润产品A产品B产品C1014.516.215.92016.418.418.43018.019.922.64019.624.124.2试确定如何安排对各种产品的投资数，可获得最大总期望利润？阶段：k=1,2,3,4分别考虑产品A、B、C和终止阶段；状态：sk表示第k阶段初的现有资金数；决策：uk表示第k阶段的投入资金数；状态转移方程：sk+1=sk–uk动态规划基本方程：0)4(4)1(1),(max)(sfkskfkukskvkskf最后得到解：产品A投资10万，产品B投资10万，产品C投资20万.总的期望利润为49.1万。某公司准备资金600万元（以100万元为单位），有四项可选择投资的工程A、B、C、D。现决定每项工程至少要投资100万元。各项工程投资不同资金后可获得的期望利润如下：分配的投资金额利润工程A工程B工程C工程D100150167164158200169189190185300185204226215试确定如何安排对各项工程的投资数，可使获得的总期望利润最大？阶段：k=1,2,3,4,5分别考虑项目A、B、C、D和终止阶段；状态：sk表示第k阶段初的资金数；决策：uk表示第k阶段的投入资金数；状态转移方程：sk+1=sk–uk动态规划基本方程：0)()(),(max)(5511sfsfusvsfkkkkkkk最后得到解：项目A投资100万，项目B投资100万，项目C投资200万，项目D投资200万总的期望利润为692万西安邮电学院试题库管理系统——试题表第3页共17页现有一面粉加工厂，每星期上五天班。生产成本和需求量见表。星期(k)12345需求量(dk)单位：袋1020253030每袋生产成本(ck)8691210面粉加工没有生产准备成本，每袋面粉的存储费为hk＝0.5元/袋，按天交货，分别比较下列两种方案的最优性，求成本最小的方案。（1）星期一早上和星期五晚的存储量为零，不允许缺货，仓库容量为S=40袋；（2）其它条件不变，星期一初存量为8。【解】动态规划求解过程如下：阶段k：日期，k=1,2,…,6状态变量sk：第k天早上（发货以前）的冷库存量决策变量xk：第k天的生产量状态转移方程：sk+1=sk+xk－dk；决策允许集合：400,0)(kkkkkkkdxsxxsD阶段指标：vk(sk，xk)=ckxk+0.5sk终端条件：f6(s6)=0,s6=0；递推方程：)(),(min)(),(min)(1)(11)(kkkkkkkkskDkxkkkkkkskDkxkkdxsfxsvsfxsvxf当k=5时，因为s6=0，有6555550,15,ssxdxs由于s5≤15，55555515*555()min100.51509.5,15xsfsxssxsk=4时，5440153015,ssx，0有44445sxs30，444444444455()44()*4444*444()min120.5()}min2.59435}11.551030,3094354030,0xDsxDsfsxsfsxsssxsssxk=3时，当0≤s4≤30时，332530s+x0，得3332555sxs有333333()max[0.25]55Dsxsxs333333333333344()334()33()*333()min90.5()}min90.511.5510}min2.511797.5}8.566055xDsxDsxDsfsxsfsxssxssxs取上界：当30≤s4≤40时，4330,302540xs+x，有333333()5565Dsxsxs333333333(1)333344()334()*33()()min90.5()}min90.59435}min8.5210},xDsxDsxDsfsxsfsxssxx取任意值显然此决策不可行。当k=2时，由4322030,0252025,sssx，0x2的决策允许集合为222222()max[0,20]45Dsxsxs22222222222()22()*222()min60.56608.5}min2.58830}5.5717.545xDsxDsfsxssxssxs取上界：当k=1时，由21102001020ssx，，则x1的决策允许集合为111111()max[0,10]30Dsxsxs11111111112()11()()min80.5717.55.5min2.55772.5797.5xDsxDsfsxssxs因为110,10,sx22232233433445445510100,4545,2025,5530,2530,300,300,1515.sxsssxxsssxxsssxxs(2)期初存储量s1=8,与前面计算相似，x1=2.MinZ=772.5+2.5x1-5s1=737.5则总成本最小的方案是第二种。有一个车队总共有车辆100辆，分别送两批货物去A、B两地，运到A地去的利润