运筹学2020最新试卷带答案

1、运筹学样卷参考答案（48课时）一、判断题（对的记/,错的记乂，共10分，每小题2分）线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可 TOC o 1-5 h z 行域的范围一般将扩大；（）已知y *为线性规划的对偶问题的最优解，若匕0说明在最优生产计划中第i种资源已完全耗尽；（）运输问题是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之一：有惟一最优解、有无穷多最优解、无界解和无可行解；（）求解整数规划是可以先不考虑变量的整数约束，而是先求解相应的线性规划问题，然后 对求解结果中的非整数的变量凑整即得最优解。（）11个公司之间可能只有4个公司与偶数个公司

2、有业务联系；（）答案：1. T； 2. T；3. F； 4. F； 5. F二、选择题（共15分，每小题3分）在利用图解法求解最大利润问题中中，通过各极点作与目标函数直线斜率相同的平行线，这些平行线称之为。（）可行解B.可行域C.等利润线D.等成本线用单纯形法求解线性规划问题时引入的松弛变量在目标函数中的系数 。（）0B.很大的正数C.很大的负数D.1以下关系中，不是线性规划与其对偶问题的对应关系的 。（）约束条件组的系数矩阵互为转置矩阵一个约束条件组的常数列为另一个目标函数的系数行向量两个约束条件组中的方程个数相等约束条件组的不等式反向需求量大于供应量的运输问题需要做的。（）A.虚设一个需求

3、点B.删去一个供应点虚设一个供应点，取虚设供应量为恰当值令供应点到虚设的需求点的单位运费为0对一个求目标函数最大的混合整数规划问题，以下命题中不正确的 。（）其线性规划松弛问题的最优解可能是该整数规划问题的最优解。该问题可行解的个数一定是有限的；任一可行解的目标函数值不可能大于其线性规划松弛问题的目标函数值；该问题可行解中可能存在不取整数值的变量。答案：6.C7.A 8.C 9.C 10.B三、简答题（每题5分，共15分）线性规划问题的三个要素是什么？线性规划模型有哪些特征？答案：线性规划问题的三个要素是决策变量、目标函数和约束条件。线性规划模型的特征有：（1）目标函数是决策变量的线性函数；（

4、2）约束条件是决策变量的线性（不）等式；（3）决策变量连续变化。利用0-1变量表示下列约束条件（要求说明0-1变量的意义）:x取值0，2，4，6，8中的一个答案：设y.= 1为取第j个数，否则必=0.则工=0 y + 2 y + 4 y + 6 y + 8)1234=1,5y + y + y + y + y=1,512345y = 0 or 1, j = 1,2,3.i j3.写出求极大值的运输问题的产销平衡表B1 .B2B3B4产量A17891030A21716151420A3534615销量15101520答案：令新表中单位运价为Cj = 17 -匕，总产量=6560=总销量，增加一个虚拟

5、的销地，销量为5.B1B2B3B4B5产量A110987030A20123020A312141311015销量151015205（10分=5分+5分）某产品有三个产地、四个销地，各产地的产量、各销地的销量以及产地到 销地之间的单位运价见下表，用表上作业法求该运输问题的最优调运方案。、销地B1Bb3_B4. 产量产地、一3_A1_ _412411_ _16A2一21039_ _10A3一85116_ _22销量 _8_1412_14答案：为了简便，表中口中的数为运行方案，（）中的数为检验数。最小儿素法：销地BiB2B3_b4一 产量产地y1234A14(1)12(2)41011_16_ A22_

6、 _ 10(1)32 _ _9(-1)_ _10 _A38(10)_51411(12)_6_ _ 22 _销量_8_1412_14-48检验数。24 =-1 0，当前方案不是最优，调整如下：f-销地B1B2B3 | B4| 产量-产地-一一_-A1_4(0)12(2)41211141162810(2)3(1)92110-A3_一 8(9) _-5F141 _一 11(12) 一-6_一 22 销量814121448所有检验数非负，当前方案为最优方案.有非基变量检验数为0,有无穷多最优解。(4)用图解法求下列目标规划的满意解： TOC o 1-5 h z HYPERLINK l bookmark

7、43 o Current Document minz = Pd + + P(d + d +) + Pd - 1 12223 32 七 + % 右11(。)X -X + d-d + = 0 (b) HYPERLINK l bookmark46 o Current Document 1211 0(i = 1,2,3)l12 i i图略，满意解是线段GD上任意点，其中G点(2,4),D点(10/3,10/3),因为GD上任意点对应的 d - = 0 3(5)设图中各弧上数为距离，求该网络(看作无向图)的最小生成树。13.解：(113.解：(1)破圈法或加边法，过程略*如上图，为该网络(看作无向图)的

8、最小生成树，总的权重为18、解答题(共50分)（10分）某企业生产甲、乙两种产品，从工艺资料知道：每生产一吨产品甲需用资源A 3个单位，资源B 5个单位，每生产一吨产品乙需用资源A 4个单位，资源B 2个 单位。若一吨产品的甲和乙的经济价值分别为10千元和6千元，每天原料供应的能力 分别为10，12单位，企业应该如何安排生产计划，使得一天的总利润最大？解：设每天生产甲、乙各气,% 吨，则max z -10 x + 6 x 12& + 4 x 10 1 2 s.t 5x + 2x 012图解法求解：略最优解为：X=（2, 1 ），最优目标值为z=26.答：每天生产甲、乙各2吨和1吨，使得一天的总

9、利润最大下面三题选一:（1）已知线性规划问题（P）max z - 2x + 3x + 3x123x + x + x 3 1 2 3s.t x + 4x + 7x 02 j = 132,3 1 j的一个单纯形表如下。C23300CBXBb2X1X2玉A2X110-14/3-1/332012-1/31/3L00-1-5/3-1/3（a）写出（P）此时的基本可行解，并判断该解是否为最优解；（b）写出（P）的对偶模型及其最优解。答案：（1）基变量为X1,X2，故当前基本可行解为（1，2, 0，0，0），因为所有检验数 非正，故为最优解。（2）（P）的对偶模型为min w = 3 y + 9 yL 2y

10、 + 4 y 312七+7七3、y1, y2 0其最优解为原问题最优单纯表中检验数的相反数，即（5/3, 1/3）(2)已知线性规划问题:1234x(2)已知线性规划问题:1234x+3x+x 81242x+x 612x+x+x 6234x+x+x 0 (j=1,4)max z = 2x + 4x + x + xj解：对偶模型为234y + y =134又因为七=9 - 2 - 2 - 4 = 1 0 ,故 y4= 0从而 y3 = 1, y1 = 2/5, y2 = 4/5，所以对偶的最优解为X*=(2,2,4,0)，根据对偶理论求出对偶问题最优解。min w = 8 y + 6 y + 6

11、 y + 9 y1234y + 2 y + y 21243 y + y + y + y 31234y3 + y4 1y + y 114y, y , y , y 01234设对偶问题最优解为K* = (y, y , y , y )。因为原问题最优解为x*=(2,2,4,0)，1234y1 + 2 y2 +y4 = 23 y1 + y + y + y = 3问题的最优解为(2/5,4/5,1,0)下面三题选一:(1)用分枝定界法求解整数规划问题:max z = 3 尤 + 2 x122x + 3x 141 2 x + 0.5x 0且x为整数122解：该问题的松弛问题(L)为max z = 3x +

12、 2 x2x + 3x 141 -2 -x + 0.5x 012用图解法(略)得松弛问题(L)的最优解为(3.25,2.5)，最优目标值为14.75.对(L)分别增加条件x2 3,得两个子问题(L1)和(L2)，用图解法(略)得子问题(L1)的最优解为(3.5,2)，最优目标值为14.5,子问题(L2)的最优解为(2.5,3)，最优目标值为 13.5.因为解(3.5,2)满足气为整数条件，并且目标函数值是两个子问题中最大，故原问题的最优解为(3.5,2).18,解:1023159510152415514715201513 M 818,解:1023159510152415514715201513

13、 M 8M 0 0 0 0广803381302100921012 7 5 M-8 0401270如13079M-3-0T 一-0T-01139501302M-80-7-Z -40-0-1M、此时其中(3)608110MT40M-9 0003费用最小，Z* = 3 + 5 + 5 + 8 = 21丙做第一事，甲做第二事，乙做第二事戌做第四事求解0-1规划问题:(2)从甲，乙，丙，丁，戊五人中挑选四人去完成四项工作，已知每人完成各项工作的时间如 下表所示。规定每项工作只能由一个人去单独完成，每个人最多承担一项工作，假定甲必须 保证分配到工作，丁因某种原因不同意承担第四项工作。在满足上述条件下，如何

14、分配工作， 使完成四项工作总的花费时间最少。(20分)工作人一四甲1051520乙210515丙3151413丁15276戊94158max z - 3 x - 2 x + 5 xx + 2 x - x 2x1+4 x2+x3 4st x + x 34 x + x 0(0,0,1)5VV V V Vz 5(0,1,0)-2X(0,1,1)3X(1,0,0)3X(1,0,1)8VV V V V Vz 8(1,1,0)1X(1,1,1)6X从而得最优解n = (1,0,1)，最优值Z* = 8。(10分)(二选一)设图中各弧上数为距离，求七到七的最短距离与最短路径。(2(2)设图中各弧上数为容量，

15、求七到七的最大流量。标号过程：略；最短路为：V v2v6v9，最短距离为8.5标号过程：略；最大流量为 6，最小割集为：(S,T)=(Vi，v2),(v4,v7)，其中 S=V,v4，T=v2,v3,v5,v6,v7,v8,v9 割量为：C(S,T)=3+3=6.最大流量方案(答案不唯一)：f =3 f =3f =3f =3f =3f =1f =2f =1, 其余为零cy V1JIL I 虹 y J* III P-*，：1Q ,A A ,4。二 Q,4qC, 4/17,4 = 070 匕,QC，(、刀J y。131423394/787989下面二题选一：卜表为一机械加工工序，试画出PERT网络

16、图，并计算时间参数和确定关键路线。作业代码作业名称紧前作业作业时间（天）A项目设计4B外购包装材料A8C清理场地A7D外购零配件A6E机加工2人员培训A9F木模、铸件C15G机加工1D12H机加工2D、E8I工装制造G10J装配、调试B、 F、 H、 I4关键工序：A,C,F,J关键路线：132333738工程完工期限：38某农场要决定一块地中选择什么作物，条件如下，如何决策?旱正常多雨0.20.70.1蔬菜100040007000r力、麦200050003000棉花300060002000（1）分别用乐观法、悲观法、等可能法与最小后悔值法对生产方案作出决策。（2）根据往年天气资料，旱、正常和

17、多雨三种天气的概率分别为）.2、0.7和0.1，求利润期 望最大和后悔期望最小的策略。答：利润表如下表所示。旱正常多雨Maxmin等可能法利润期 望值0.20.70.1蔬菜1000400070007000100040003700小麦2000500030005000200033334200棉花3000600020006000200036676800乐观法（大中取大）：最佳方案为：蔬菜悲观法（小中取大）：最佳方案为：小麦或棉花等可能法：最佳方案为：蔬菜最大利润期望值法：最佳方案为：棉花后悔值如下表所示。旱正常多雨Max损失期望值0.20.70.1蔬菜20002000020001800小麦10001

18、000400040001300棉花0050005000500最小后悔值法：最佳方案为：蔬菜 最小损失期望值法：最佳方案为：棉花四、建立下面问题的数学模型（9分）1.某造船厂根据合同从当年起连续三年末各提供四条规格相同的大型客货轮。已知该厂这三年内生产大型客货轮的能力及每艘客货轮成本如下表所示:年度正常生产时间内可完 成的客货轮数加班生产时间内可完成的客货轮数正常生产时每艘成本（万元）133500252600323500已知加班生产时，每艘客货轮成本比较正常时高出60万元；又知造出来的客货轮若当年不交 货，每艘每年积压一年造成损失为30万元。在签定合同时，该厂已积压了两艘未交货的客货 轮，而该厂希望在第三年未完成合同还能储存一艘备用。问该厂如何安排每年客货轮的生产 量，在满足上述各项要求的情况下总的生产费用最少？答案：设第i年正常生产艘，加班生产*艘，交付后储贮R艘产销存平衡:x + j + z = z + 4, i = 1,2,3产销存平衡:i ii-1iZ0 = 2, z3 = 10 x 3,0 j 3加工能力限制：0 x2 5,0 七 20 x 2,0 j 3