运筹学第八章解剖12949.pdf

《运筹学第八章解剖12949.pdf》由会员分享，可在线阅读，更多相关《运筹学第八章解剖12949.pdf（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、西安邮电学院试题库管理系统试题表 第 16 页 共 17 页 专业代码 11 专业名称 信息管理与信息系统 课程代码 18 课程名称 运筹学 试题类型代码 08 试题类型名称 计算题 出题人 管理员 出题 日期 2005-11-4 知识点 代码 题 干 答 案 评分标准 难度系数 认知分类 建议分数 建议时间 11180801 10 吨集装箱最多只能装 9 吨，现有 3 种货物供装载，每种货物的单位重量及相应单位价值如表所示。应该如何装载货物使总价值最大。货物编号 1 2 3 单位加工时间 2 3 4 单位价值 3 4 5【解】设装载第 I 种货物的件数为xi（i=1,2,3）则问题可表为：1

2、23123123max3452349,0zxxxxxxx xx且为整数 利用背包问题的前向动态规划计算，建立动态规划模型。由于决策变量离散型值，所以可用列表法求解。当 R=1 时，121210/2()max(3)xsf sx。计算结果如下：s2 0 1 2 3 4 5 6 7 8 9 f（s2）0 0 3 3 6 6 9 9 12 12 x1*0 0 1 1 2 2 3 3 4 4 当 R=2 时，f2（s3）=4/210maxsx 4x2+f1（s3-3x2）计算结果如下：s3 0 1 2 3 4 5 6 7 8 9 x2 0 0 0 0 1 0 1 0 1 0 1 2 0 1 2 0 1

3、2 0 1 2 3 C2+f2 0 0 3 3 4 6 4 6 7 9 7 8 9 10 8 12 10 11 12 13 11 12 f2（s3）0 0 3 4 6 7 9 10 12 13 x2*0 0 0 1 0 1 0 1 0 1 当 R=3 时，f3（9）=230maxx5x3+f2（9-4x3）（x3为整数）=220maxxf2（9），5+f2（5），10+f2（1）=max13，12，10=13 较难 分析 12 14 设有两种资源，第一种资源有 x 单位，第二种资源有 y 单位,计划分配给 n 个部门。把第一种资源有 xi单位，第二种资源有 yi单位分配给部门 i 所得的利润为

4、记为 ri（xi，yi）。如设 x=3，y=3，n=3，其利润 ri（x，y）列于表中，试用动态规划方法如何分配这两种资源到 i 个部门去，使总的利润最大？y x r1（x，y）r2（x，y）r3（x，y）0 1 2 3 0 1 2 3 0 1 2 3 0 0 1 3 6 0 2 4 6 0 3 5 8 1 4 5 6 7 1 4 6 7 2 5 7 9 2 5 6 7 8 4 6 8 9 4 7 9 11 3 6 7 8 9 6 8 10 11 6 9 11 13 最优决策为：33163002001332211，最大利润为，fyxyxyx 中 运用 10 12 有一辆货车载重量为 10 吨，

5、用来装载货物 A、B 时成本分别为 5 元/吨和 4 元/吨。现在已知每吨货物的运价与该货物的重量有如下线性关系：A：P1=15-x1，B：P2=18-2x2 其中 x1、x2 分别为货物 A、B 的重量。如果要求货物满载，A 和 B 各装载多少，才能使总利润最大 【解】由题意可得各种货物利润函数为 21111112222222()(155)10()(1824)142g xxxxxgxxxxx 原问题的数学模型归结为 2211221212max(10)(142)10,0zxxxxxxx x 最优解：x1=6，x2=4；z48 某有限公司有五台新设备，将有选择的分配配给下属的三个工厂，所得收益如

6、表中所示。问该公司应如何分配设备，可使总收益最大？单位：千元 新设备台数 工 厂 0 0 0 0 1 3 5 4 2 7 10 6 3 9 11 11 4 12 11 12 5 13 11 12 答案：两种最优分配方案总收益均为 21 千元 西安邮电学院试题库管理系统试题表 第 16 页 共 17 页 某公司有5台设备，分配给所属A,B,C三个工厂。各工厂获得不同的设备台数所能产生效益（万元）的情况如下表。求最优分配方案，使总效益最大。（用动态规划方法求解）台数 工厂 0 1 2 3 4 5 A 0 10 15 20 23 25 B 5 17 20 22 23 24 C 7 12 15 18

7、20 23 答案：阶段 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)=0 k=4，f4(x4)=0 k=3，分配给工厂 C，0d3x3，x4=x3-d3 x3 D3(x3)x4 v3(x3,d3)v3(x3,d3)+f4(x4)f3(x3)d3*0 0 0 7 7+0=0 0 0 1 0 1

8、 7 7+0=7 12 1 1 0 12 12+0=12*2 0 2 7 7+0=7 15 2 1 1 12 12+0=12 2 0 15 15+0=15*3 0 3 7 7+0=7 18 3 1 2 12 12+0=12 2 1 15 15+0=15 3 0 18 18+0=18*4 0 4 7 7+0=7 20 4 1 3 12 12+0=12 2 2 15 15+0=15 3 1 18 18+0=18 4 0 20 20+0=20*5 0 5 7 7+0=7 23 5 1 4 12 12+0=12 2 3 15 15+0=15 3 2 18 18+0=18 4 1 20 20+0=20

9、5 0 23 23+0=23*k=2，分配给工厂 B，0d2x2，x3=x2-d2 x2 D2(x2)x3 v2(x2,d2)v2(x2,d2)+f3(x3)f2(x2)d2*0 0 0 5 5+7=12 12 0 1 0 1 5 5+12=17 24 1 1 0 17 17+7=24*2 0 2 5 5+15=20 29 1 1 1 17 17+12=29*2 0 20 20+7=27 3 0 3 5 5+18=23 32 1或 2 1 2 17 17+15=32*2 1 20 20+12=32*3 0 22 22+7=29 4 0 4 5 5+20=25 35 1或 2 1 3 17 17

10、+18=35*2 2 20 20+15=35*3 1 22 22+12=34 4 0 23 23+7=30 5 0 5 5 5+23=28 38 2 1 4 17 17+20=37 2 3 20 20+18=38*3 2 22 22+15=37 4 1 23 23+12=35 5 0 24 24+7=31 k=1，分配给工厂 A，0d1x1，x2=x1-d1 x1 D1(x1)x2 v1(x1,d1)v1(x1,d1)+f2(x2)f1(x1)d1*5 0 5 0 0+38=38 49 3 1 4 10 10+35=45 2 3 15 15+32=47 3 2 20 20+29=49*4 1

11、23 23+24=47 5 0 25 25+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 万元。较难 分析 12 12 某公司决定投资 60 万元（以 10 万元为单位），以提高三种主要产品 A、B、C 的产量。现决定每种产品至少要投资 10 万元。各种产品投资不同资金后可获得的期望利润如下：分配的 投资金额 利 润 产品 A 产品 B 产品 C 10 14.5 16.2 15.9 20 16.4 18.4 1

12、8.4 30 18.0 19.9 22.6 40 19.6 24.1 24.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 万元为单位），有四项可选择投资的工程

13、 A、B、C、D。现决定每项工程至少要投资 100 万元。各项工程投资不同资金后可获得的期望利润如下：分配的 投资金额 利 润 工程 A 工程 B 工程 C 工程 D 100 150 167 164 158 200 169 189 190 185 300 185 204 226 215 试确定如何安排对各项工程的投资数，可使获得的总期望利润最大？阶段：k=1,2,3,4,5 分别考虑项目A、B、C、D和终止阶段；状态：sk 表示第 k 阶段初的资金数；决策：uk 表示第 k 阶段的投入资金数；状态转移方程：sk+1=sk uk 动态规划基本方程：0)()(),(max)(5511sfsfusv

14、sfkkkkkkk 最后得到解：项目A投资 100 万，项目B投资 100 万，项目C投资 200 万，项目D投资 200 万 总的期望利润为 692 万 西安邮电学院试题库管理系统试题表 第 16 页 共 17 页 现有一面粉加工厂，每星期上五天班。生产成本和需求量见表。星期(k)1 2 3 4 5 需求量(dk)单位：袋 10 20 25 30 30 每袋生产成本(ck)8 6 9 12 10 面粉加工没有生产准备成本，每袋面粉的存储费为hk0.5 元/袋，按天交货，分别比较下列两种方案的最优性，求成本最小的方案。（1）星期一早上和星期五晚的存储量为零，不允许缺货，仓库容量为 S=40 袋

15、；（2）其它条件不变，星期一初存量为 8。【解】动态规划求解过程如下：阶段k：日期，k=1,2,6 状态变量sk：第k天早上（发货以前）的冷库存量 决策变量xk：第k天的生产量 状态转移方程：sk+1=sk+xkdk；决策允许集合：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 由于s515，555555

16、15*555()min100.51509.5,15xsf sxssxs k=4 时，5440153015,ssx，0有44445sxs30，444444444455()44()*4444*444()min120.5()min2.5943511.551030,3094354030,0 xDsxDsfsxsf sxsssxsssx k=3 时，当 0s430 时，332530s+x0，得 3332555sxs 有333333()max0.2555D sxsxs 333333333333344()334()33()*333()min90.5()min90.511.5510min2.511797.58

17、.566055xDsxDsxDsf sxsfsxssxssxs 取上界：当 30s440 时，4330,302540 xs+x，有 333333()5565D sxsxs 333333333(1)333344()334()*33()()min90.5()min90.59435min8.5210,xDsxDsxDsfsxsfsxssxx取任意值 显然此决策不可行。当k=2 时，由4322030,0252025,sssx，0 x2的决策允许集合为 222222()max0,2045D sxsxs 22222222222()22()*222()min60.56608.5 min2.588305.57

18、17.545xDsxDsfsxssxssxs 取上界：当k=1 时，由211020 01020ssx，则x1的决策允许集合为 111111()max0,1030D sxsxs 11111111112()11()()min80.5717.55.5min2.55772.5797.5xD sxD sf sxssxs 因为110,10,sx 222322334334454455 10 100,4545,2025,5530,2530,300,300,1515.sxsssxxsssxxsssxxs (2)期初存储量 s1=8,与前面计算相似，x1=2.Min Z=772.5+2.5x1-5s1=737.5

19、 则总成本最小的方案是第二种。有一个车队总共有车辆 100 辆，分别送两批货物去 A、B 两地，运到 A 地去的利润与车辆数目满足关系 100 x，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年初投入高负荷运行的机器数；状态转

20、移方程：sk+1=0.7xk+0.8(skxk)决策允许集合：Dk(sk)=xk|0 xksk 阶段指标：vk(sk，xk)=100 xk+80(skxk)终端条件：f4(s4)=0 递推方程：11()10()max(,)()max 10080()0.70.8()kkkkkkkkkkkkxDskkkkkkkxsfsv sxfsxsxfxsx fk(xk)表示第k趟初分配xk辆车到 A 地，到第 3 趟末的最大总运价为 333333333440*333330()max 10080()()max2080 100 xsxsf sxsxfsxssxs最优 222222222330*222220()ma

21、x 10080()()max10160 170 xsxsfsxsxf sxssxs最优 111111111220*111110()max 10080()()max3216 219xsxsf sxsxfsxssxs最优 因为 s1=100，最大总运价f1(s1)=21900 元 西安邮电学院试题库管理系统试题表 第 16 页 共 17 页 某公司有三个工厂，它们都可以考虑改造扩建。每个工厂都有若干种方案可供选择，每种方案的投资及所能取得的收益如表所示。现公司有资金 5 千万元，问应如何分配投资使公司的总收益最大？mij（方案）工厂 i=1 工厂 i=2 工厂 i=3 C（投资）R（收益）C（投资

22、）R（收益）C（投资）R（收益）1 0 0 0 0 0 0 2 1 5 2 8 1 3 3 2 6 3 9-4-4 12-（注：表中-表示无此方案）最优方案有三个。即（mj1，mj2，mj3）=（3，2，2）或（2，3，2）或（2，4，1），总的收益为 17 千万元 中 运用 10 12 设有一辆载重卡车，现有 4 种货物均可用此车运输。已知这 4 种货物的重量、容积及价值关系如表 货物代号 重量/t 容积/m3 价值/千元 1 2 2 3 2 3 2 4 3 4 2 5 4 5 3 6 若该卡车的最大载重为 15t，最大允许装载容积为 10 m3，在许可的条件下，每辆装载每一种货物的件数不限

23、。问应如何搭配这四种货物，才能使每车装载货物的价值最大。最优解有三个：（1）01314321xxxx，（2）02124321xxxx，（3）00504321xxxx，最大价值为 20 千元 11180802 在设备负荷分配问题中，n=10，a=0.7，b=0.85，g=15，h=10，期初有设备 1000 台。试确定 10 期的设备最优负荷方案。【解】由公式100()n tn tiiiighaag ba 得(g-h)/g(b-a)0.2222，a0a1a21+0.70.492.192.222a0+a1a2a32.533，nt12，t=7，则 16 年低负荷运行，710 年为高负荷运行。各年年初

24、投入设备数如下表。年份 1 2 3 4 5 6 7 8 9 10 设备台数 1000 850 723 614 522 444 377 264 184.8 129 某工厂购进 100 台机器，准备生产 p1，p2两种产品。若生产产品 p1，每台机器每年可收入45 万元，损坏率为 65%；若生产产品 p2，每台机器每年可收入 35 万元，损坏率为 35%；估计三年后将有新的机器出现，旧的机器将全部淘汰。试问每年应如何安排生产。使在三年内收入最多？第一年将 100 台机器全部生产 p2两种产品，第二年把余下的机器继续生产产品 p2，第三年把余下的所有机器全部生产产品 p1。三年的总收入为 7676.

25、25 万元。设某中机器可以在高、低两种不同的负荷下生产。若机器在高负荷下生产，则产品的年产量 a 和投入的机器数量 x 的关系为 a=8x，机器的年折损率为=0.3；若机器在低负荷下生产，则产品年产量 b 和投入的机器数量 x 的关系为 b=5x，机器的年折损率为=0.1；设开始时有完好机器 1000 台，要求制定一个四年计划，每年年初分配完好机器在不同负荷下工作，使四年产品总产量达到最大。答案：四年中分配在高负荷下工作的机器台数分别为 0,900,630 和 441，四年最高产量为207187 某工厂使用一种关键设备，每年年初设备科需对该设备的更新与否做出决策。现已知在五年内购置该种设备的费

26、用和各年内设备维修费用如表中所示。试制定五年内的设备更新计划，使总的支付费用最少。第 i 年初 1 2 3 4 5 购置费用 11 11 12 12 13 第 i 年 1 2 3 4 5 维修费用 5 6 8 11 18 答案：两种方案，五年的总费用均为 53000 元。一台设备的价格为 P，运行寿命为 n 年，每年的维修费用是设备役龄的函数，记为 C(t)，新设备的役龄为 t=0。旧设备出售的价格是设备役龄的函数，记为 S(t)。在 n 年末，役龄为 t 的设备残值为 R(t)。现有一台役龄为 T 的设备，在使用过程中，使用者每年都面临“继续使用”或“更新”的策略。（列出动态规划模型）答案：

27、阶段 k：运行年份；状态变量 xk：设备的役龄 t；决策变量 dk：继续使用更新)Keep(K)place(ReRdk 状态转移方程：Kd1xRd1xkkk1k 阶段指标：Kd)t(CRd)t(S)0(CPKd)x(CRd)x(S)0(CPvkkkkkkk 递推方程：KdtftCRdftSCPKdxfxCRdxfxSCPxfkkkkkkkkkkkkkk)1()()1()()0(min)()()()()0(min)(111111 终端条件：fn(t)=-R(t)较难 分析 12 14 西安邮电学院试题库管理系统试题表 第 16 页 共 17 页 11180803 系统可靠性问题。一个工作系统由n

28、个部件串联组成，见图 1。只要有一个部件失灵，整个系统就不能工作。为提高系统的可靠性，可以增加部件的备用件。例如，用 5 个部件 1 并联起来作为一个部件与部件 2 串联，如果其中一个部件失灵其它 4 个部件仍能正常工作。由于系统成本（或重量、体积）的限制，应如何选择各个部件的备件数，使整个系统的可靠性最大。图 1 假设部件(1,2,)i in上装有ix个备用件，该部件正常工作的概率为()iip x。设装一个部件i的备用件的成本为ic，要求备件的总费用为 C。那么该问题模型为：11max()01,2,niiiniiijPp xc xCxin并且为整数，（8.8）同理，如果一个复杂的工作系统由n

29、个部件并联组成的，只有当n个部件都失灵，整个系统就不能工作，见图 2。图 2 假设()iip x为第i个部件失灵的概率，为提高系统的可靠性，可以增加部件的备用件。由于系统成本（或重量、体积）的限制，应如何选择各个部件的备件数，使整个系统的可靠性最大。系统的可靠性为11()niiip x，则该问题的数学模型归结为 11min()01,2,niiiniiijPp xc xCxin并且为整数，（8.9）利用式(8.8)或（8.9）求解下列问题。工厂设计的一种电子设备，其中有一系统由三个电子元件串联组成。已知这三个元件的价格和可靠性如表所示，要求在设计中所使用元件的费用不超过 200 元，试问应如何设

30、计使设备的可靠性达到最大。元件 单价 可靠性 1 40 0.95 2 35 0.8 3 20 0.6【解】数学模型为 312123123max(1 0.05)(1 0.2)(1 0.4)403520200,0 xxxZxxxx xx并且为整数 最优解 X=(1，2，4)；可靠性 Z=0.888653，总费用 190。设有一个由四个部门串联组成的系统。为提高系统的可靠性，考虑在每个部件上并联 1 个、2 个或 3 个同类元件。每个部件 i(i=1,2,3,4)配备 j 个并联元件（j=1,2,3）后的可靠性 Rij和成本 cij（单位：百元），由下表给出。假设该系统的总成本允许为 15 千元。试

31、问如何确定各部件配备元件的数目，使该系统的可靠性最大？j i=1 i=2 i=3 i=4 Rij cij Rij cij Rij cij Rij cij 1 0.70 4 0.60 2 0.90 3 0.80 3 2 0.75 5 0.80 4 0.82 5 3 0.85 7 答案：可靠性为 0.432 中 运用 10 12 为保证某一设备的正常运转，需备有三种不同的零件 E1，E2，E3。若增加备用零件的数量，可提高设备正常运转的可靠性，但增加了费用，而投资额仅为 8 000 元。已知备用零件数与它的可靠性和费用的关系如表所示。备件数 增加的可靠性 设备的费用/千元 E1 E2 E3 E1

32、E2 E3 Z=1 0.3 0.2 0.1 1 3 2 Z=2 0.4 0.5 0.2 2 5 3 Z=3 0.5 0.9 0.7 3 6 4 现要求在既不超出投资额的限制，又能尽量提高设备运转的可靠性的条件下，问各种零件的备件数量应是多少为好？E1备用 1 个，E2备用 1 个，E3备用 3 个，其总费用为 8 000 元，提高设备的可靠性为 0.042 用动态规划求解以下网络从A到F的最短路径，路径上的数字表示距离。答案：最短路径为 AB1C1D2E2F，长度为 26。较难 分析 12 12 部件 1 部件 2 部件 n B1 B2 B3 C1 C2 D1 D2 D3 E1 E2 F A

33、3 5 2 1 6 4 3 7 3 3 2 5 4 2 7 10 8 9 7 11 9 12 13 西安邮电学院试题库管理系统试题表 第 16 页 共 17 页 11180804 求解下列非线性规划 123123max0,1,2,3jZx x xxxxCxj 【解】（1）设 s3=x3,s3+x2=s2，s2+x1=s1=C 则有 x3=s3，0 x2s2，0 x1s1=C 用逆推法，从后向前依次有 k3，333333()max()xsf sxs 及最优解 x3*=s3 k2，22222222233222222000()max()max()max(,)xsxsxsfsx fxx sxh sx

34、由222222120,2hsxxsx则 222220,故 x2=221s为极小值点。因而有2*2222211(),22fssxs k1 时，1111211111111001()min()min(,)2xsxsf sxsxh s x 由111110hsxx 知*1111111,()2xsf ss 得到最优解1(1,1/2,1/2);2TXCzC 求解下列非线性规划 2123123123max2310,0Zxxxxxxx xx 【解】设 s3=x3,s3+x2=s2，s2+x1=s1=10 则有 x3=s3，0 x2s2，0 x1s1=10 用逆推法，从后向前依次有 k3 时，3323333()m

35、ax()xsf sxs 及最优解 x3=s3 k2 时，222222222222200()max3()max(,)xsxsfsxsxh sx 222222332202hsxxsx 时 而 222222320,2hxsx 故不是一个极大值点。讨论端点：当 x2=0 时2222()fss,x2=s2时222()3fss 如果 s23 时,2222()fss k1 时，111121111111100()max2()max(,)xsxsf sxsxh s x 11111122201hsxxsx 时 21122120,1hxsx 故不是一个极大值点 同理有,x1=0,f1（s1）=s12=100，x1=

36、s1,f1（s1）=2s1=20(舍去)得到最优解(0,0,10);100Xz 求解下列非线性规划 123123max42100,1,2,3jZx x xxxxxj 【解】设 s3=x3,2s3+4x2=s2，s2+x1=s1=10 则有 x3=s3，0 x2s2/4，0 x1s1=10 用逆推法，从后向前依次有 k1，333333()max()xsf sxs及最优解 x3*=s3 k2，22222222222204041()max(2)max(,)2xsxsfsxsxh sx 由22xh=21s2-4x2=0,则 x2=81s2 222240hx ,故 2218xs为极大值点。则2222()

37、32sfs 及最优解 x2*=s2/8 k1，1111211111111001()max()max(,)32xsxsf sx sxh s x 22*111 1111111(43)0,323hss xxxsx，故 31111()216f ss 得到最优解(10/3,5/6,5/3);125/27TXz 西安邮电学院试题库管理系统试题表 第 16 页 共 17 页 求解下列非线性规划 123123max24100,1,2,3jZx x xxxxxj 【解】按问题中变量的个数分为三个阶段 s1，s2，s3，且 s310，x1，x2，x3为各阶段的决策变量，各阶段指标函数相乘。设 s1=2x1,s1+

38、4x2=s2，s2+x3=s310，则有 x1=s1/2，0 x2s2/4，0 x3s3=10 用顺推法，从前向后依次有 k1，111111/2()max()2xssf sx 及最优化解 x1*=s1/2 k2，2222222222220/40/41()max(4)max(,)2xsxsfsx sxh sx 由22221402hsxx,则*2218xs 222240hx ,故 2218xs为极大值点。则32221()32fss k3，3333233333333001()max()max(,)32xsxsf sx sxh s x 由22*3333333311(43)0,323hss xxxsx

39、故33331()216f ss，由于 s310，则 s3=10 时取最大值，x310/3，s2=s3x320/3，x25/6，s1=s24x210/3，x15/3 得到最优解(5/3,5/6,10/3);125/27TXz 求解下列非线性规划 221123123123max228,0Zxxxxxxxx xx 【解】设 s1=x1,s1+x2=s2，s2+x3=s3=8 k1，1122111111()max(2)2xsf sxxss 及最优化解 x1*=s1 k2，222222222222222200()max 2()2()max(,)xsxsfsxsxsxh sx 2222622,hxsx22

40、2260hx x2*=0 时，f2（s2）=s22+2s2,x2*=s2时，f2（s2）=2s22 故 2222222()max2,2fssss k3，当 x2*=0 时，23333333333033033()max()2()max(,)xsxsf sxsxsxh s x 同样得 x3*=0 时，f3（s3）=s32+2s3 x3*=s3时，f3（s3）=s3 所以，f3（s3）=s32+2s3=80 当 x2*=s2时，f3（s3）=330maxsx x3+2（s3-x3）2 同样得 x3*=0 时，f3（s3）=2s32=128 x3*=s3时，f3（s3）=s3=8 所以，f3（s3）=

41、2s32=128 最优解为(0,8,0);128Xz 用动态规划求解下列线性规划问题。12121212max242624,0Zxxxxxxx x 【解】设 s2=x2,s2+2x1=s16 则有 0 x2=s24，0 x1s1/2 用逆推法，从后向前依次有 222()4fss及最优解 x2*=s2 111111122110/20/2()max 2()max 46 xsxsf sxf ssx 由 s2=s12x14，s16，取 s16，111110/2()max 246 xsf sx 又 1x12，取x11，11()18f s 最优解(1,4);18TXz 用动态规划方法求解下列问题 max z

42、=33221xxx st.3,2,1,06321ixxxxi 108;3,1,2max321zxxx 中 运用 10 12 用动态规划求解下面问题 max z=5x1+10 x2+3x3+6x4 st.4321i 0 x111054i4321，且为整数，xxxx 5500011max4321zxxxx，用动态规划求解下面问题 max z=3x1（2-x1）+2x2（2-x2）st.21i 0 x3i21，且为整数，xx 311max21zxx，用动态规划求解下面问题 min z=x21+x22+x23+x24 st.4321i 0 x10i4321，且为整数，xxxx 最优解有 6 个（1）2

43、3324321xxxx，（2）23234321xxxx，（3）22334321xxxx，（4）33224321xxxx，（5）32324321xxxx，（6）32234321xxxx，26minz最优值均为 用动态规划方法求解下列问题 max z=51x-2222129xxx st.2,1,0521ixxxi 8/131;4/9,2/5max21zxx 西安邮电学院试题库管理系统试题表 第 16 页 共 17 页 用动态规划方法求解下列问题 min z=23222143xxx st.3,2,1,09321ixxxxi 751.29;147.3,574.1,82.1max321zxxx 用动态规

44、划方法求解下列问题 max z=61x+722215xx st.2,1,0931022121ixxxxxi 92.702;2.0,6.9max21zxx 写出问题的动态规划的基本方程 max z=niiixg1)(st.nicxxaiiniii,2,1,01 基本方程 kkkkkkkkkkkkkkkkkksDxkknnxassbsnkbsssascxxsDnnksfxgsfsfkkk11111110|,min0|1,1,max0状态转移函数可达状态集合允许决策集合 用动态规划方法求解下列问题 max z=33222148xxx st.为正数bixbxxxi3,2,1,0102321 b4000

45、,33max32110/;10/,0,0bzbxxx 0b1/4,azxxxx100;0,0,0,10max4321(2)-1/4a1/4,最优决策有两个:25;5,0,5,0;0,5,5,0max43214321zxxxxxxxx或(3)abi，将导致额外的费用 c)y(3i1ib；若 y1iyi则劳动力的费用为 c其它）当（0)(24112iiiiyyyy（单位：千元）假定 y0=5（百人），使确定劳动力费用支出最小的方案。答案：万元，总费用单位：百人9.1)(6,6,8,8,5(),(54321yyyyy 一个工厂生产某种产品，17 月份生产成本和产品需求量的变化情况如下表：月份(k)1

46、 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。每个月生产的产品在月末入库，月初根据当月需求发货。求七个月的生产量，能满足各月的需求，并使生产成本最低。（列出动态规划模型）答案：阶段 k：月份，k=1,2,7,8；状态变量 xk：第 k 个月初（发货以前）的库存量；决策变量 dk：第 k 个月的生产量；状态转移方程：xk+1=xk-rk+dk；决策允许集合：Dk(xk)=dk|dk0,rk+1xk+1H =

47、dk|dk0,rk+1xk-rk+dkH；阶段指标：vk(xk,dk)=ckdk；终端条件：f8(x8)=0,x8=0；递推方程：fk(xk)=minvk(xk,dk)+fk+1(xk+1)dkDk(xk)=minckdk+fk+1(xk-rk+dk)dkDk(xk)较难 分析 12 14 设城市的道路结构如右图所示。两个路口之间标的数字表示通过这一段道路所需的费用（单位：元），该城市有一项奇怪的交通规则：车辆经过每个路口时，向左或向右转弯一次，要收取“转弯费”3 元。现有一辆汽车从 A 点出发到 P 点，求包括转弯费用在内，费用最小的行驶路线。（列出动态规划模型）答案：为了满足动态规划的这一

48、要求，必须重新构造状态变量。现将这个问题的动态规划模型构造如下：阶段 k：设起点 A 为第一阶段，到达 B 或 C 为第二阶段，如此等等。到达终点 P 为第七阶段。状态变量：(xk,rk),(k=1,2,6)，其中 xk为第 k 阶段所在位置，rk为从 xk出发行进的方向：ru upd downk()()上行下行 终点 P 的状态变量为(P,)，表示行进方向为空集。由图可见，点 G，J，K，M，N，O，P 只有一个状态，其余的点都有两个状态。由于状态变量包括所在位置和行进方向两个因素，决策变量也就已经包含在状态变量之中了。最优指标：fk(xk,rk)表示从 xk出发，按 rk方向前进一步，最终

49、到达 P 的最小费用（包括转弯费用）。阶段指标：uk(xk)从 xk出发上行一步的路程费用（不包括转弯费用）；dk(xk)从 xk出发下行一步的路程费用（不包括转弯费用）。递推方程：3)d,x(f)u,x(fmin)x(u3)d,x(f)x(u)u,x(f)x(umin)u,x(f1k1k1k1kkk1k1kkk1k1kkkkk)d,x(f3)u,x(fmin)x(d)d,x(f)x(d3)u,x(f)x(dmin)d,x(f1k1k1k1kkk1k1kkk1k1kkkkk 终端条件：f7(P,)=0 较难 分析 12 14 设有 n 个城市,其中每两个城市之间都有道路相连,城市 i 和城市

50、j 之间的距离为 Cij。从某城市出发周游所有城市,经过每个城市一次且仅一次，最后回到出发地,求总行程最短的周游路线。对于一般的情况可以假设两城市之间往返距离不相等。在此例中,为了简化问题，设往返距离相等，即 Cij=Cji。（列出动态规划模型即可）答案：由于此问题经过的路线是一条经过所有城市的闭合回路，因此从哪一点出发是无所谓的，因此不妨设从城市 1 出发。问题的动态规划模型构造如下：阶段 k：已经历过的城市个数，包括当前所在的城市。k=1,2,n,n+1，k=1 表示出发时位于起点，k=n+1 表示结束时回到终点。状态变量：xk=(i,Sk)，其中 i 表示当前所在的城市，Sk 表示尚未访