运筹学 第八章

1、西安邮电学院试题库管理系统试题表专业代码11专业名称信息管理与信息系统课程代码18课程名称运筹学试题类型代码08试题类型名称计算题出题人管理员出题日期2005-11-4知识点代码题 干答 案评分标准难度系数认知分类建议分数建议时间1118080110吨集装箱最多只能装9吨，现有3种货物供装载，每种货物的单位重量及相应单位价值如表所示。应该如何装载货物使总价值最大。货物编号123单位加工时间234单位价值345【解】设装载第I种货物的件数为xi（ i =1,2,3）则问题可表为： 利用背包问题的前向动态规划计算，建立动态规划模型。由于决策变量离散型值，所以可用列表法求解。当R=1时， 。计算结果

2、如下：s20123456789f（s2）003366991212x1*0011223344当R=2时，f2（s3）=4x2+f1（s3-3x2）计算结果如下：s30123456789x20000101010120120120123C2+f2003346467978910812101112131112f2（s3）0034679101213x2*0001010101当R=3时，f3（9）=5x3+f2（9-4x3） （x3为整数）=f2（9），5+f2（5），10+f2（1）=max13，12，10=13较难分析1214设有两种资源，第一种资源有x单位，第二种资源有y单位,计划分配给n个部门。把第

3、一种资源有x单位，第二种资源有y单位分配给部门i所得的利润为记为r（x，y）。如设x=3，y=3，n=3，其利润r（x，y）列于表中，试用动态规划方法如何分配这两种资源到i个部门去，使总的利润最大？ yxr（x，y）r（x，y）r（x，y）0 1 2 30 1 2 30 1 2 300 1 3 60 2 4 60 3 5 814 5 6 71 4 6 72 5 7 925 6 7 84 6 8 94 7 9 1136 7 8 96 8 10 116 9 11 13最优决策为：中运用1012有一辆货车载重量为10吨 ，用来装载货物A、B时成本分别为5元/吨和4元/吨。现在已知每吨货物的运价与该货

4、物的重量有如下线性关系：A：P1=15-x1 ，B：P2=18-2x2 其中x1 、x2 分别为货物A、B的重量。如果要求货物满载，A和B各装载多少，才能使总利润最大【解】由题意可得各种货物利润函数为 原问题的数学模型归结为最优解：x1 =6，x2 =4；z48某有限公司有五台新设备，将有选择的分配配给下属的三个工厂，所得收益如表中所示。问该公司应如何分配设备，可使总收益最大？ 单位：千元新设备台数工 厂000013542710639111141211125131112答案 ：两种最优分配方案总收益均为21千元某公司有5台设备，分配给所属A,B,C三个工厂。各工厂获得不同的设备台数所能产生效益

5、（万元）的情况如下表。求最优分配方案，使总效益最大。（用动态规划方法求解） 台数 工厂012345A01015202325B51720222324C71215182023答案：阶段k：每分配一个工厂作为一个阶段；状态变量xk：分配第k个工厂前剩余的设备台数；决策变量dk：分配给第k个工厂的设备台数；决策允许集合：0dkxk状态转移方程：xk+1=xk-dk阶段指标：vk(xk,dk)第k次分配产生的效益，见表中所示；递推方程：fk(xk)=maxvk(xk,dk)+fk+1(xk+1)终端条件：f4(x4)=0k=4，f4(x4)=0k=3，分配给工厂C，0d3x3，x4=x3-d3x3D3(

6、x3)x4v3(x3,d3)v3(x3,d3)+f4(x4)f3(x3)d3*000 7 7+0= 000101 7 7+0= 7121101212+0=12*202 7 7+0= 7152111212+0=12201515+0=15*303 7 7+0= 7183121212+0=12211515+0=15301818+0=18*404 7 7+0= 7204131212+0=12221515+0=15311818+0=18402020+0=20*505 7 7+0= 7235141212+0=12231515+0=15321818+0=18412020+0=20502323+0=23*k=

7、2，分配给工厂B，0d2x2，x3=x2-d2x2D2(x2)x3v2(x2,d2)v2(x2,d2)+f3(x3)f2(x2)d2*00055+7=1212010155+127=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

8、*322222+15=37412323+12=35502424+7=31k=1，分配给工厂A，0d1x1，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某公司决定投资6

9、0万元（以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动态规划基本方程： 最后得到解：产品A投资10

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 阶段的投入资金数；状态转

11、移方程：sk+1 = sk uk动态规划基本方程： 最后得到解：项目A投资100万，项目B投资100万，项目C投资200万，项目D投资200万总的期望利润为692万现有一面粉加工厂，每星期上五天班。生产成本和需求量见表。星期(k)12345需求量(dk) 单位：袋1020253030每袋生产成本(ck)8691210面粉加工没有生产准备成本，每袋面粉的存储费为hk0.5元/袋，按天交货，分别比较下列两种方案的最优性，求成本最小的方案。（1）星期一早上和星期五晚的存储量为零，不允许缺货，仓库容量为S=40袋；（2）其它条件不变，星期一初存量为8。【解】动态规划求解过程如下：阶段k：日期，k=1,

12、2,6状态变量sk：第k天早上（发货以前）的冷库存量决策变量xk：第k天的生产量状态转移方程：sk+1=sk+xkdk；决策允许集合：阶段指标： vk(sk，xk)=ckxk+0.5sk终端条件：f6(s6)=0,s6=0；递推方程：当k=5时，因为s6=0，有由于s515，k=4时， k=3时，当0s430时，得 有当30s440时，有显然此决策不可行。当k=2时，由x2的决策允许集合为当k=1时，由，则x1的决策允许集合为因为(2)期初存储量s1=8, 与前面计算相似，x1=2. Min Z=772.5+2.5x1-5s1=737.5 则总成本最小的方案是第二种。有一个车队总共有车辆100

13、辆，分别送两批货物去A、B两地，运到A地去的利润与车辆数目满足关系100x ，x为车辆数，车辆抛锚率为30%，运到B地的利润与车辆数y关系为80y，车辆抛锚率为20%，总共往返3轮。请设计使总利润最高的车辆分配方案。【解】动态规划求解过程如下。阶段k：共往数k=1,2,3,4，k=1表示第一趟初，k=4表示第三趟末（即第六年初）；状态变量sk：第k趟初完好的车辆数（k=1,2,3,4），也是第k1趟末完好的车辆数，其中s4表示第三趟末的完好车辆数。决策变量xk：第k年初投入高负荷运行的机器数；状态转移方程：sk+1=0.7xk+0.8(skxk)决策允许集合：Dk(sk)=xk|0xksk阶段

14、指标：vk(sk，xk)=100xk+80(skxk)终端条件：f4(s4)=0递推方程： fk(xk)表示第k趟初分配xk辆车到A地，到第3趟末的最大总运价为因为s1=100，最大总运价f1(s1)=21900元某公司有三个工厂，它们都可以考虑改造扩建。每个工厂都有若干种方案可供选择，每种方案的投资及所能取得的收益如表所示。现公司有资金5千万元，问应如何分配投资使公司的总收益最大？m（方案）工厂i=1工厂i=2工厂i=3C（投资） R（收益）C（投资） R（收益）C（投资） R（收益）10 00 00 021 52 81 332 63 9- -4- -4 12- -（注：表中-表示无此方案）

15、最优方案有三个。即（m，m， m）=（3，2，2）或（2，3，2）或（2，4，1），总的收益为17千万元中运用1012设有一辆载重卡车，现有4种货物均可用此车运输。已知这4种货物的重量、容积及价值关系如表货物代号重量/t容积/m价值/千元1223232434254536若该卡车的最大载重为15t，最大允许装载容积为10 m，在许可的条件下，每辆装载每一种货物的件数不限。问应如何搭配这四种货物，才能使每车装载货物的价值最大。最优解有三个：（1）（2）（3）最大价值为20千元11180802在设备负荷分配问题中，n=10，a=0.7，b=0.85，g=15，h=10，期初有设备1000台。试确定1

16、0期的设备最优负荷方案。【解】由公式得(g-h)/g(b-a)0.2222，a0a1a21+0.70.492.192.222a0+a1a2a32.533，nt12，t=7，则16年低负荷运行，710年为高负荷运行。各年年初投入设备数如下表。年份12345678910设备台数1000850723614522444377264184.8129某工厂购进100台机器，准备生产p，p两种产品。若生产产品p，每台机器每年可收入45万元，损坏率为65%；若生产产品p，每台机器每年可收入35万元，损坏率为35%；估计三年后将有新的机器出现，旧的机器将全部淘汰。试问每年应如何安排生产。使在三年内收入最多？第一

17、年将100台机器全部生产p两种产品，第二年把余下的机器继续生产产品p，第三年把余下的所有机器全部生产产品p。三年的总收入为7676.25万元。设某中机器可以在高、低两种不同的负荷下生产。若机器在高负荷下生产，则产品的年产量a和投入的机器数量x的关系为a=8x，机器的年折损率为=0.3；若机器在低负荷下生产，则产品年产量b和投入的机器数量x的关系为b=5x，机器的年折损率为=0.1；设开始时有完好机器1000台，要求制定一个四年计划，每年年初分配完好机器在不同负荷下工作，使四年产品总产量达到最大。答案 ：四年中分配在高负荷下工作的机器台数分别为0,900,630和441，四年最高产量为20718

18、7某工厂使用一种关键设备，每年年初设备科需对该设备的更新与否做出决策。现已知在五年内购置该种设备的费用和各年内设备维修费用如表中所示。试制定五年内的设备更新计划，使总的支付费用最少。第i年初12345购置费用1111121213第i年12345维修费用5681118答案 ：两种方案，五年的总费用均为53000元。一台设备的价格为P，运行寿命为n年，每年的维修费用是设备役龄的函数，记为C(t)，新设备的役龄为t=0。旧设备出售的价格是设备役龄的函数，记为S(t)。在n年末，役龄为t的设备残值为R(t)。现有一台役龄为T的设备，在使用过程中，使用者每年都面临“继续使用”或“更新”的策略。（列出动态

19、规划模型）答案 ：阶段k：运行年份；状态变量xk：设备的役龄t；决策变量dk：状态转移方程：阶段指标：递推方程：终端条件：fn(t)=-R(t)较难分析121411180803系统可靠性问题。一个工作系统由个部件串联组成，见图1。只要有一个部件失灵，整个系统就不能工作。为提高系统的可靠性，可以增加部件的备用件。例如，用5个部件1并联起来作为一个部件与部件2串联，如果其中一个部件失灵其它4个部件仍能正常工作。由于系统成本（或重量、体积）的限制，应如何选择各个部件的备件数，使整个系统的可靠性最大。部件1部件2部件n图1假设部件上装有个备用件，该部件正常工作的概率为。设装一个部件的备用件的成本为，要

20、求备件的总费用为C。那么该问题模型为： （8.8）同理，如果一个复杂的工作系统由个部件并联组成的，只有当个部件都失灵，整个系统就不能工作，见图2。图2假设为第个部件失灵的概率，为提高系统的可靠性，可以增加部件的备用件。由于系统成本（或重量、体积）的限制，应如何选择各个部件的备件数，使整个系统的可靠性最大。系统的可靠性为，则该问题的数学模型归结为 （8.9） 利用式(8.8)或（8.9）求解下列问题。工厂设计的一种电子设备，其中有一系统由三个电子元件串联组成。已知这三个元件的价格和可靠性如表所示，要求在设计中所使用元件的费用不超过200元，试问应如何设计使设备的可靠性达到最大。元件单价可靠性14

21、00.952350.83200.6【解】数学模型为最优解X=(1，2，4)；可靠性Z=0.888653，总费用190。设有一个由四个部门串联组成的系统。为提高系统的可靠性，考虑在每个部件上并联1个、2个或3个同类元件。每个部件i(i=1,2,3,4)配备j个并联元件（j=1,2,3）后的可靠性R和成本c（单位：百元），由下表给出。假设该系统的总成本允许为15千元。试问如何确定各部件配备元件的数目，使该系统的可靠性最大？ji=1i=2i= 3i=4RcRcRcRc10.7040.6020.9030.80320.7550.8040.82530.857答案 ：可靠性为0.432中运用1012为保证某

22、一设备的正常运转，需备有三种不同的零件E，E，E。若增加备用零件的数量，可提高设备正常运转的可靠性，但增加了费用，而投资额仅为8 000元。已知备用零件数与它的可靠性和费用的关系如表所示。备件数增加的可靠性设备的费用/千元EEEEEEZ=10.30.20.1132Z=20.40.50.2253Z=30.50.90.7364现要求在既不超出投资额的限制，又能尽量提高设备运转的可靠性的条件下，问各种零件的备件数量应是多少为好？E备用1个，E备用1个，E备用3个，其总费用为8 000元，提高设备的可靠性为0.042用动态规划求解以下网络从A到F的最短路径，路径上的数字表示距离。B1B2B3C1C2D

23、1D2D3E1E2FA352164373325427108971191213答案：最短路径为AB1C1D2E2F，长度为26。较难分析121211180804求解下列非线性规划 【解】（1）设s3=x3 , s3+x2=s2，s2+x1=s1=C 则有 x3= s3 ，0x2s2，0x1s1=C 用逆推法，从后向前依次有k3， 及最优解 x3*=s3k2， 由 故 为极大值点。 所以 及最优解x2*=s2k=1时， ，由，得故已知知x1 + x2+ x3 = C，因而按计算的顺序推算，可得各阶段的最优决策和最优解如下， 由s2=s1x1*=2C/3， 由s3=s2x2*=C/3，最优解为：求解

24、下列非线性规划【解】设s3=x3 , s3+x2=s2，s2+x1=s1=C 则有 x3= s3 ，0x2s2，0x1s1=C 用逆推法，从后向前依次有k3， 及最优解 x3*=s3k2， 由 =40,故 x2=为极小值点。 因而有k1时， 由知 得到最优解 求解下列非线性规划【解】设s3=x3 , s3+x2=s2，s2+x1=s1=10 则有 x3= s3 ，0x2s2，0x1s1=10 用逆推法，从后向前依次有 k3时， 及最优解 x3=s3 k2时， 而 。讨论端点：当 x2=0时, x2= s2时 如果s23时, k1时， 同理有, x1=0, f1（s1）= s12= 100，x1

25、= s1, f1（s1）= 2s1= 20 (舍去)得到最优解求解下列非线性规划【解】设s3=x3 ,2s3+4x2=s2，s2+x1=s1=10 则有 x3= s3 ，0x2s2/4，0x1s1=10 用逆推法，从后向前依次有k1， 及最优解 x3*=s3k2， 由=s2-4x2=0,则 x2=s2,故 为极大值点。则 及最优解x2*=s2/8 k1， ，故 得到最优解求解下列非线性规划【解】按问题中变量的个数分为三个阶段s1 ，s2 ，s3 ，且s310，x1，x2，x3为各阶段的决策变量，各阶段指标函数相乘。设s1=2x1 , s1+4x2=s2，s2+x3=s310，则有 x1= s1

26、/2 ，0x2s2/4，0x3s3=10用顺推法，从前向后依次有k1， 及最优化解 x1*=s1/2k2， 由,则 ,故 为极大值点。则 k3， 由故，由于s310，则s3=10时取最大值，x310/3，s2=s3x320/3，x25/6，s1=s24x210/3，x15/3得到最优解求解下列非线性规划【解】设s1=x1, s1+x2=s2，s2+x3=s3=8 k1， 及最优化解 x1*=s1 k2，x2*=0时，f2（s2）=s22+2s2, x2*= s2时，f2（s2）=2s22故 k3，当x2*=0时， 同样得x3*=0时 ，f3（s3）=s32+2s3 x3*=s3时，f3（s3）

27、=s3 所以， f3（s3）= s32+2s3=80 当x2*= s2时，f3（s3）=x3+2（s3-x3）2同样得x3*=0时 ，f3（s3）=2s32 =128 x3*=s3时，f3（s3）=s3 =8 所以， f3（s3）= 2s32=128最优解为用动态规划求解下列线性规划问题。【解】设s2=x2 ,s2+2x1=s16 则有 0x2=s24，0x1s1/2 用逆推法，从后向前依次有 及最优解 x2*=s2 由 s2=s12x14， s16，取s16，又1x12，取x11， 最优解用动态规划方法求解下列问题max z=st.中运用1012用动态规划求解下面问题max z=5x+10x

28、+3x+6xst.用动态规划求解下面问题max z=3x（2- x）+2x（2- x）st.用动态规划求解下面问题min z=x+ x+ x+ xst.最优解有6个（1）（2）（3）（4）（5）（6）用动态规划方法求解下列问题max z=5-st.用动态规划方法求解下列问题min z=st.用动态规划方法求解下列问题max z=6+7st.写出问题的动态规划的基本方程max z=st.基本方程用动态规划方法求解下列问题max z=st.b4000, 0b1/4, (2)-1/4a1/4,最优决策有两个:(3) a-1/4, 最优决策有两个:用动态规划方法求解下列问题。答案 ：最优解有共6个：（

29、2，3，3，2），（3，2，3，2）， （3，3，2，2），（2，2，3，3），（2，3，2，3），（3，2，2，3）z=26用动态规划方法求解下列问题。答案 ：最优解有3个：（1，1，4，1），（2，1，2，1），（1，1，2，2），z11180805某商店在未来的4个月里，准备利用商店里一个仓库来专门经销某种商品，该仓库最多能装这种商品1 000单位。假定商店每月只能卖出它仓库现有的货。当商店决定在某个月购货时，只有在该月的下个月才能得到该货。据估计未来4个月商店买卖价格如表所示。假定商店在1月开始经销时，仓库贮存商品有500单位。试问：如何指定这4个月的订购与销售计划，使获得利润最大？(

30、不考虑仓库的存贮费用)月份（k）买价（c）卖价（p）110122993111341517各月份订购与销售的最优决策为：月期前存货（s）售出量（x）购进量（y）15005000200100031000100010004100010000利润最大为16 000较难分析1212某厂准备连续3个月生产A种产品，每月处开始生产。A的生产成本费用为x，其中x是A产品当月的生产数量。仓库存货成本费用是每月每单位1元。估计3个月的需求量分别为d=100，d=110，d=120。现设开始时第一个月月初存货s=0，第三个月月末存货s=0。试问：每月的生产数量应是多少才能使总的生产和存货费用为最小。最佳生产量为：x

31、=110，x=110，d=109。总的最低费用为36 321元中运用1012考虑一个有m个产地和n个销地的运输问题。设a为产地i（i=1，m）可发运的物资数，b为销地j（j=1，n）所需要的物资数。又从产地i往销地j发运x单位物资所需的费用为h（x），试将此问题建立动态规划的模型。较难分析1214某公司打算在三个不同的地区设置4个销售点,根据市场预测部门估计,在不同的地区设置不同数量的销售店,每月可得到的利润如表所示.试问在各个地区应如何设置销售点,才能使每月获得的总利润最大?其值是多少?销售店利润地区01234101625303220121721223010141617在第一个地区设置2个销

32、售点,在第二个地区设置1个销售点, 在第三个地区设置1个销售点.每月获得的总利润为47某工厂生产三种产品，各种产品重量与利润关系如表。现将此三种产品运往市场出售，运输能力总重量不超过10t，问如何安排运输使总的利润最大？种类重量/（t件）利润/（元件）121002314034180最优解有两个：（1）（2）总利润为480元某纺织品公司计划在今后四个月内经营一种高级成衣。根据预测，该种商品在5至8月份的每套进价和售价如表所示。已知库存能力为600套，5月初有库存200套，并假定销售是在月初进行，至8月末全部销售完，使对这四个月的销购做出安排，使总的利润最大？ 单位：元/套月价5678进价4038

33、4042售价45423944答案 ：5月份销售200套，进货600套。6月份销售600套，进货600套。7月份销售0套，进货0套。8月份销售600套，进货0套。总的利润为13800元11180806设有n种物品，每一种物品数量无限。第i种物品每件重量为wi公斤，每件价值ci元。现有一只可装载重量为W公斤的背包，求各种物品应各取多少件放入背包，使背包中物品的价值最高。（用动态规划方法求解）答案 ：这个问题可以用整数规划模型来描述。设第i种物品取xi件（i=1,2,n，xi为非负整数)，背包中物品的价值为z，则maxz=c1x1+c2x2+cnxns.t.w1x1+w2x2+wnxnWx1,x2,

34、xn 为非负整数阶段k：第k次装载第k种物品（k=1,2,n）状态变量xk：第k次装载时背包还可以装载的重量；决策变量dk：第k次装载第k种物品的件数；决策允许集合：Dk(xk)=dk|0 dkxk/wk，dk为整数；状态转移方程：xk+1=xk-wkdk阶段指标：vk=ckdk递推方程：fk(xk)=maxckdk+fk+1(xk+1)=maxckdk+fk+1(xk-wkdk)终端条件：f4(x4)=0对于一个具体问题：c1=65，c2=80，c3=30w1=2，w2=3，w3=1以及W=5用动态规划求解对于k=3列出f3(x3)的数值表f3(x3)x3D3(x3)x430d3+f4(x4

35、)f3(x3)d3*0000+0=000101100+0=030+0=30*30120122100+0=030+0=3060+0=60*6023012332100+0=030+0=3060+0=6090+0=90*903401234432100+0=030+0=3060+0=6090+0=90120+0=120*120450123455432100+0=030+0=3060+0=6090+0=90120+0=120150+0=150*1505对于k=2列出f2(x2)的数值表f2(x2)x2D2(x2)x380d2+f3(x3)f2(x2)d2*0000+f3(0)=0+0=0*001010+

36、f3(1)=0+30=30*3002020+f2(2)=0+60=60*600301300+f3(3)=0+90=90*80+f3(0)=80+0=80900401410+f3(4)=0+120=120*80+f3(1)=80+30=1101200501520+f3(5)=0+150=150*80+f3(2)=80+60=1401500对于k=1列出f1(x1)的数值表f1(x1)x1D1(x1)x265d1+f2(x2)f1(x1)d1*0000+f2(0)=0+0=0*001010+f2(1)=0+30=30*300201200+f2(2)=0+60=6065+f2(0)=65+0=65*

37、651301310+f2(3)=0+90=9065+f2(1)=65+30=95*95140124200+f2(4)=0+120=12065+f2(2)=65+60=125130+f2(0)=130+0=130*130250125310+f2(5)=0+150=15065+f2(3)=65+90=155130+f2(1)=130+30=160*1602由题意知，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元,背包没

38、有余量。由f1(x1)得列表可以看出，如果背包得容量为W=4，W=3，W=2和W=1时，相应的最优解立即可以得到。较难分析1214用动态规划求解以下背包问题阶段指标：vk=ckdk递推方程：fk(xk)=maxckdk+fk+1(xk+1) =maxckdk+fk+1(xk-wkdk)终端条件：f4(x4)=0用动态规划求解对于k=3，列出f3(x3)的数值表f3(x3)x4=x3-3d2x3D3(x3)x415d3+f4(x4)f3(x3)d3*0000+0=0002020+0=000401410+0=015+0=150=015+0=1530+0=30*302801

39、28520+0=015+0=1530+0=30*302100123107410+0=015+0=1530+0=3045+0=45*453对于k=2列出f2(x2)的数值表f2(x2)x3=x2-4d2x2D2(x2)x322d2+f3(x3)f2(x2)d2*0000+0=0002020+0=000401400+15=1522+0=22*221601620+30=30*22+0=2230080128400+30=3022+15=3744+0=44*4421001210620+45=4522+30=52*44+0=44521对于k=1列出f1(x1)的数值表f1(x1)x2=x1-2d1x1D1

40、(x1)x212d1+f2(x2)f1(x1)d1*1001234510864200+53=5312+44=5624+30=5436+22=5848+0=4860+0=60*605由题意知，x1=10，由表f1(x1)、f2(x2)、f3(x3)，经回朔可得：d1*=5，x2=x1-2d1=0，d2*=0，x3=x2-4d2=0，d3*=0，x4=x3-2d3=0即应取第一种物品5件,第二种物品0件,第三种物品0件,最高价值为60元,背包没有余量。较难分析1214背包问题，这是运筹学问题中的一个著名问题。某人外出旅游，需将五个物品放进背包，但背包重量有限制，总重量W不能超过13kg，物品重量及

41、其价值的关系如下图所示：物品重量（kg）价值（元）A79B54C43D32E10.5答案 ：最优解为装A，B，E各一件，重6.5kg，最大价值为13.5元。中运用1012用动态规划方法求解以下背包问题 答案 ：阶段k：第k次装载第k种物品（k=1,2,n）状态变量xk：第k次装载时背包还可以装载的重量；决策变量dk：第k次装载第k种物品的件数；决策允许集合：Dk(xk)=dk|0 dkxk/wk，dk为整数；状态转移方程：xk+1=xk-wkdk阶段指标：vk=ckdk递推方程：fk(xk)=maxckdk+fk+1(xk+1) =maxckdk+fk+1(xk-wkdk)终端条件：f4(x4

42、)=0用动态规划求解对于k=3，列出f3(x3)的数值表f3(x3)x4=x3-20d2x3D3(x3)x435d3+f4(x4)f3(x3)d3*0000+0=0009020+0=000100100+0=00020012000+0=035+0=35*351300130100+0=035+0=35*35140012402000+0=035+0=3570+0=70*702500125030100+0=035+0=3570+0=70*702对于k=2列出f2(x2)的数值表f2(x2)x3=x2-41d2x2D2(x2)x372d2+f3(x3)f2(x2)d2*0000+0=0*00100100+0=0*00200200+35=35*350300300+35=35*350400400+70=70*70050015090+70=7072+0=72*721对于k=1列出f1(x1)的数值表f1(x1)x2=x1-10d1x1D1(x1)x217d1+f2(x2)f1(x1)d1*50012345504030201000+72=7217+70=87*34+35=6951+35=8668+0=6885+0=85871由题意知，x1=50，由表f1(x1)、f2(x2)、f3(x3)，经回朔可得：d1*=1，x2=x1-10d1=40，d2*=0，x3=x2