附录1:习题参考答案
【习题1】
1.1 填空
(1)线性规划,图论,决策论,排队论,存储论;(2)系统论,控制论,信息论。 1.2 判断
(1)√;(2)√;(3)×;(4)√;(5)×。 1.3 略。 1.4 略。 1.5 略。 1.6 略。
【习题2】
2.1 填空
(1)可行解;(2)01
≥-b B ,01
≤--A B C C B ;(3)零;(4)增加或减少一个单
位的该产品目标函数的增加或减少值;(5)零。 2.2 判断
(1)×;(2)×;(3)×;(4)×;(5)√。 2.3 略
2.4 可行域如右图阴影部分所示。
(1)当2/11=c 时,有无穷多组最优解,参看线段BC 。
(2)当11=c 时,有无穷多组最优解,参看线段
AC 。
(3)当11>c 时,有唯一最优解,见图中点B 。 (4)当2/11 2.5 (1)这个问题可行域为( EABF ); (3)这个问题基础解为( ABCDEFGHIJ ); (3)这个问题基础可行解为( EABF ); (4)这个问题最优解为( E ); (5)G 点对应的解中,大于0的变量为( 21,x x ),等于0的变量为( 53,x x ),小于0的变量为( 4x ); (6)F 点对应的基变量为( 321,,x x x ), 1=x 0 2=x 0 3=x 12 3221=+x x 0 4=x 6 321=+x x 0 5=x 3 321=+-x x 5 .1221=+-x x A C D E F G H I J A o B C 6 21=+x x 1 x 2 x 10 221=+x x 非基变量为( 54,x x ); (7)E 点对应的基变量为( 432,,x x x ),非基变量为( 51,x x ); (8)从F 到E 的单纯形叠代,进基变量为( 4x ),离基变量为( 1x ); (9)E 点对应的对偶变量,大于0的是( 5w ),等于0的是( 43,w w ),小于0的是( 无 )。 2.6 (1)131011011????=-??????B ,1 1120121201212---?? ??=????-?? B 2.7 (1)最优基为? ? ?? ??=1101B ,??????-=-11011 B ,123040b b ????=????????; (2)显然0=f ,510a g ???? =???? -???? ,23d =-,5e =-; (3)对偶问题的最优解为[]05 * =w 。 2.8 (1)0,,0<>f e a ; (3)00,0=或f e a =>; (2)0,,0e d g >≤; (4)0,20>≤ 2.10 (1)用大M 法,所得最优解为)0,0,0,2,3/2(* =X ,最优目标函数值22/3; (2)用对偶单纯形法,最优解为,)1,2 3,0(T X =* 最优目标函数值36。 2.11 略。 2.12 略。 2.13 (1)对偶问题为 21125m in y y w += ???????≥≥+≥+≥+无约束 2121212 1, 03 421322y y y y y y y y (2)根据松弛互补定理,由于21,x x 大于零,所以对偶问题的最优解满足2221=+y y , 1321=+y y ,所以41=y ,12-=y 。 (3)第一个约束资源的影子价格为4。 2.14 (1)原问题的最优解为T T x x x x x X )0,0,1,3,0(),,,,(54321*==,最优值为36。 (2)对偶问题的最优解为* 12345(,,,,)(2,6,2,0,0)Y y y y y y ==,最优值为36。 (3)根据松弛互补定理,得140y x =;250y x =;130x y =;240x y =;350x y =,依照这些对应关系寻找检验数与最优解的关系。 2.15 (1)]2/25,4/15[1∈c ;]3/40,4[2∈c ; (2)]16,5/24[1∈b ;]15,2/9[2∈b ; (3)最优解发生变化,变为T T x x X )0,5/8(),(21* ==; (4)最优解发生变化,变为T T x x X )0,3/11(),(21* ==。 2.16 (1)获利最大的生产计划是C B A ,,各生产5,0,3,最大利润为27元; (2)令13c λ=-,5 953≤≤- λ; (3)应生产D ,最优计划为D C B A ,,,的产量分别为0,0,5,,2 5 最大利润为27.5; (4)应购进原材料,再购进原材料15单位,最大利润为30=z 。 2.17 令 ?? ?==)10,,2,1(,0,1 i s s x i i i 个井位钻井 若不选择第个井位钻井若选择第 该问题的整数规划模型为 ∑==10 1min i i i x c w ???? ? ?? ?? ? ? ?? =≤+++≤+≤+=+=+=∑=10 ,,2,110211 11587655453878110 1 i x x x x x x x x x x x x x x i i i 变量-是 2.18 令 ?? ?==)6,,2,1(,0,1 i i i x i 件装备 若不安装第件装备 若安装第 该问题的整数规划模型为 ???? ? ?????? ?? ==-≥+≥+≤≤=∑∑∑===6 ,,2,110111max 654231616 1 6 1 i x x x x x x x W x w V x v x c z i i i i i i i i i i 变量,-为 【习题3】 3.1 填空 (1)m n ?,m n +;(2)ij ij i j c u v σ=--;(3)不构成闭回路;(4)初始基本可行解;(5)不发生;(6)1。 3.2 判断 (1)×;(2)√;(3)√;(4)×;(5)√。 3.3 3.4 然后求出最优调运方案,并令22c =k ,计算空格检验数,见下表。当所有空格检验数都大于等于零时,该解仍为最优解,联立解空格检验数的不等式组,得[1,10]c k =∈。 3.5 3.6 3.7 单位运价表可调整为下表: 求解上面产销平衡运输问题,得到最优解见下表,即从A→甲150万吨;从A→乙250万吨;从B→甲140万吨;从B→丙310万吨,最小费用为14650元。 3.8 (1A,最小完成总时间为105。 (2)最小指派时间为乙完成两项的指派计划,即乙→C,甲→B,乙→D,丙→E,丁→A,总时间的最小值为131。 【习题4】 4.1 填空 (1)弧的权;(2)容量限制条件,流量平衡条件;(3)唯一确定的;(4)大于零;(5)边数等于点数减1。 4.2 判断 (1)×;(2)√;(3)√;(4)√;(5)√。 4.3 据题意,可转换为最小树问题,最小树的权为3236。 4.4 提示:破圈,转化为最小树问题。 4.5 根据最短路Floyd算法,得到各城市之间的最短路矩阵为 035453525103501520302545150102035352010010252530201003510 253525350???????? ?????? ?? ?? 4.6 1v 到各点的最短路见下图,1v 不能到达34,v v 。 6 v 1 v 2 v 3 v 4 v 5 v 7 v 4 8 v 1 3 4 3 2 6 1 4 3 6 7 4.7 (1)截集有①{}23(,),(,)s s v v v v ;②{}23234(,),(,),(,)s v v v v v v ;③{}32(,),(,)s t v v v v ; ④{}234(,),(,)t v v v v ;⑤{}24(,),(,)t t v v v v 。 (2)最小截集{}234(,),(,)t v v v v 的容量为5; (3)根据最小截集最大流定理,可知图中给出的可行流为最大流。 4.8 将A 、B 、C 、D 、E 、F 分别用一个点表示,相互之间有桥梁相连的连一条弧,弧的容量就是两点间桥梁的数量。确定该网络的最大流,确定出最小截集,可知⑹,⑺,⑿号桥为切断A 、F 之间联系的最少要破坏的桥梁。 4.9 下图为最小费用最大流。 s v 2 v 3 v 4 v 5 v t v (4,4) (5,1) (1,1) (3,3) (2,2) (2,0) (5,3) (2,2) (1,0) 4.10 图中只有A和D点为奇数次点,应用奇偶点图上作业法,寻找A和D点的最短路,添加重复边即可。A和D点的最短路为A→C→D,长度为8.6,添加一条长度为8.6的A和D的重复边,该图就变为欧拉图,然后应用弗罗莱(Fleury )算法确定最短邮路。 4.11 可按照顺序L →Pa →N →M →T →Pe →L 安排最短旅行路线,最短路线长度为212。 【习题5】 5.1填空 (1)关键路线;(2)非关键,关键;(3)最可能;(4)不;(5)网络计划。 5.2判断 (1)√;(2)×;(3)√;(4)√;(5)×;(6)√。 5.3 略。 5.4 (1)绘制网络图如下: (2)如果缩短活动E 的工期,肯定会影响整个网络的工期,因为E 是关键工序。 5.5 (1)绘制的网络图如下: (2)、(3)、(4)略。 5.6 节点的时间参数见下表 工序时间参数计算略,关键路线A E K M →→→和C G K M →→→。 5.7 用工计划安排见下表。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 (2) (3) (4) 完工期提前3天的概率为( 1.34)Φ=Φ-=0.0901;推迟5天的概率(2.24)Φ=Φ=0.9875。 【习题6】 6.1 填空 (1) 1 1n i i u ==∑;(2)α=1,α=0;(3)不确定,风险;(4)不确定;(5)决策树法;(6)TP 。 6.2 判断 (1)×;(2)×;(3)×;(4)×;(5)√。 6.3 (1)选择方案1;(2)该公司可以进行这项调查。 6.4 略。 6.5 ①该公司值得求助于咨询公司;②如咨询意见可投资开发,可投资于开发过程,如咨询意见不宜投资开发,应将多余现金存入银行。该题要注意的是开发失败将损失全部资金,尽管其概率0.04很小,但破坏力极强,所以决策者需反复权衡决策方案。 6.6 略。 6.7 状态转移矩阵为0.60.4(1)0.30.7?? =? ? ?? P ,0.42860.5714lim 0.42860.5714??=????P ,可得2种报纸的市场占有率分别为0.4286,0.5714。 6.8 状态转移矩阵为0.80.10.1(1)0.070.90.030.10.20.7????=??????P ,0.27590.57470.1494lim 0.27590.57470.14940.27590.57470.1494?? ??=?????? P ,可得三种型号化妆品的市场占有率分别为0.2759,0.5754,0.1494 【习题7】 7.1填空题 (1)多阶段;(2)作为整个过程的最优策略具有这样的性质,即无论过去的状态和决策如何,对于先前的决策所形成的状态而言,余下的诸决策必须构成最优策略;(3)无后效性——马尔科夫性;(4) 剩余重量;(5)存储数量,生产数量。 7.2 判断题 (1)√;(2)×;(3)×;(4)√;(5)√。 7.3 略。 7.4 最大总利润为17,最优分配方案有6个,其中方案之一为零售店1卸下1箱,零售店2卸下2箱;零售店3卸下2箱;零售店4卸下1箱。 7.5 最优分配方案为分配工厂乙两台,工厂丙1台,获利为14个单位。 7.6 建立动态规划基本方程,可知三种新产品研制都不成功的概率为0.06,可知最优分配方案为A 产品1万元,B 产品不分配,C 产品1万元。 7.7 最优策略为{K ,K ,R ,K },即第一年初购买的设备到第三年初更新一次,用到第4年末,其总效益为62.5万元。 7.8 运输方案有2个:一是运送产品2两件;一是运送产品1一件,运送产品3一件。 【习题8】 8.1 填空 (1)系统中顾客人数限制;(2)负指数;(3) //1//5/M M FCFS ∞;(4)5,12;(5)独立性、平稳性、普通性。 8.2 判断 (1)√;(2)√;(3)×;(4)×;(5)√。 8.3 略。 8.4* 记3分钟内到达的人数为i x ,对应每个人数的频数i f ,3分钟平均到达人数为 6 100i i i x x f ===∑ 1.97(人/3分钟) 记各组服务时间的组中值为i y ,对应每个服务时间的频数i f ,则平均服务时间为 6 100i i i y y f ==∑=31.72(秒) 8.5 略。 8.6 这是一个2个服务台,顾客容量为7的服务系统。 (1)潜在顾客的损失率()01!N N N c P c P c c ρ-==0.0037; (2)平均逗留时间 (1) s s N L W P λ= -=0.3154(小时)=18.924(分钟) 8.7 据题知,这是一个2个服务台单队列的服务系统。 系统的绩效指标为: 10011!!(1)k c c k P k c λλμρμ-=??????=+?? ? ?-???????? ∑=0.1111 2()!(1) c q c L P c ρρρ=-=2.8444 s q L L μ λ =+=4.4444 s s L W λ ==0.6944 1 q q s L W W λ μ = =- =0.6250 8.8 这是一个单服务台单队列的服务系统,其中0.5μ=架/分钟, 10q W ≤分钟 1 11 100.50.5q s W W μλ=- = -≤- 0.416λ≤ 1111 4.951110.416/5 s L ρρρ==-=-=---(架) 8.9 这是一个多服务台单队列的服务系统,应设置6个电话亭。 8.10 各方案每天的总费用为1010e s F c W λ λμ +??+??,由于乙方案的总费用最小,所以应选择方案乙。 8.11 这是一个单服务台单队列的服务系统,该服务系统每年的服务成本为400250s L ?=100000×λμλ -,求最小值得16042K =元,16.142μ=台/天。 8.12* 略。 【习题9】 9.1 填空 (1)间断;(2)200; (4)%i ;(5)变小。 9.2 判断 (1)×;(2)×;(3)√;(4)√;(5)√。 9.3 每次订货费用3c =2250;年订货次数=1200÷300=4(次);年保管费用=150×60=9000(元);年存储总费用=订货费用+保管费用=4×2250+150×60=18000(元)。 9.4 允许缺货成本较低,每次生产40万册,每年生产3次。 9.5 选择自行生产,经济批量455.73件,最大存储量236.98件;存储水平118.48件。 9.6 接受此项数量折扣,将建材的订货批量提高到200吨/次。 9.7 进货量为19件。 9.8 最好准备6个零件。 9.9 当前存储策略为:当30>I 时,不必补充存储;当30≤I 时,补充达到40箱。 9.10 进货77台。 9.11每次订货为4000件,再订货点为1413,即当库存降到1413件时,订购货物4000件。