运筹学试卷及答案.doc

沈阳理工大学试卷参考答案及评分标准（2005 -2006 学年第 二 学期）课程名称 运筹学考试班级 04421-4 04451-3命题教师 赵忠华答 案 A或B B 考核形式开、闭 闭考试类型考查、考试 考试2006年5月20日二五二六学年 第二学期 运筹学 试卷 B 参考答案及评分标准一、已知线性规划问题：（14分） 求：（1）、用图解法求解；（6分） （2）、写出其对偶问题；（4分） （3）、直接写出对偶问题的最优解。（4分）解：（1）、 x2 2 Z Z x1x1-x2=-10 2 40.5x1+x2=2 （3分）由图可知： 解之得： （2分）则最优解为X=（4，0）T Max Z=-4-0=-4 为唯一最优解 （1分）（2）、该问题的对偶问题为： （1分） （1分） （1分） （1分）（3）、由对偶问题性质可知：二五二六学年 第二学期 运筹学 试卷 B 参考答案及评分标准 解之得： 所以Y*=（0，-2）T Max Z=-4 （4分）二、已知下列线性规划问题：（22分）求：（1）、用单纯形法求解，并指出问题属于哪一类解；（20分） （2）、若增加一约束条件，则最优解如何变化？（2分）解：（1）、将原问题划为标准形得： =60 （4分） （计算表每步4分）二五二六学年 第二学期 运筹学 试卷 B 参考答案及评分标准6-33000b0603111000202-2401006033-30016-330006-33000b03004-51-3/206101-1201/2003006-90-3/2103-90-306-33000b0100011-1/2-2/3615101/201/41/6-3501-3/20-1/41/600-9/20-9/4-1/2所以X=（15，5，0，10，0，0）T 为唯一最优解 （2分）Max Z=6*15-3*5=75 （2分）（2）、将X=（15，5，0，10，0，0）T代入给出的约束条件中可知，最优解满足此约束条件。所以，最优解不变。 （2分）二五二六学年 第二学期 运筹学 试卷 B 参考答案及评分标准三、已知某运输问题如下（单位：百元/吨）：（12分）单位运价 销地产地B1B2B3供应量（吨）A137218A2581012A394515需求量（吨）161217求：（1）、使总运费最小的调运方案和最小运费。（10分）（2）、该问题是否有多个最优调运方案？若没有，说明为什么；若有，请再求出一个最优调运方案来。（2分）解：1）用伏格尔法确定初始调运方案为：B1B2B3供A111718A21212A331215需16121712=9；22=0；23=6；33=-3 （4分）有ij0,所以需要调整为：B1B2B3供A141418A21212A312315需16121712=6；22=5；23=6；31=3 （4分）因为ij0， 所以为最优方案。 Min Z=3*4+2*14+12*5+12*4+3*5=163 为唯一最优解。 （2分）2）无，因为ij0，所以该题仅有唯一最优方案。 （2分）四、分配甲、乙、丙、丁、戊五个人去完成A、B、C、D、E五项工作，每个人完成各项任务的时间如下表所示。（10分） (表中单位：小时)任务人数A B C D E甲乙丙丁戊25 28 31 41 3840 38 26 26 33 35 27 28 40 32 24 42 37 23 45 30 29 26 20 32已知甲不可能完成任务D，丁只可以完成任务B、C，试确定最优分配方案，使完成任务的总时间为最少。 二五二六学年 第二学期 运筹学 试卷 B 参考答案及评分标准解： （初始4分，其余每步1分）即：甲A；乙E；丙B；丁C；戊D （1分）Min Z=25+33+27+37+20=142小时 （2分）五、某台机器可连续工作4年，也可于每年末卖掉，换一台新的。已知于各年初购置一台新机器的价格及不同役龄机器年末的处理价如下表所示，又新机器第一年运行及维护费用为0.3万元，使用1-3年后机器每年的运行及维修费用为0.8、1.5、2.0万元。试确定该机器的最优更新策略，使4年内用于更换、购买及运行维修的总费用为最省。 （12分） 单位：万元j第一年第二年第三年第四年年初购置价2.52.62.83.1使用j年后的处理价2.01.61.31.1解： 6.0 2.3 2.0 2.1 0.8 0.9 1.1 1.40 1 2 3 40 0.8 1.7 2.8 4.0 3.93.8 二五二六学年 第二学期 运筹学 试卷 B 参考答案及评分标准由上图可知： （画图并标出权重4分，计算最短路径4分，写出答案4分）最佳更新策略为：第一年初购入，年末卖出；第二年年初购入年末卖出，第三年年初购入用至第四年末。 MinZ=4.0六、求下图的网络最大流，并写出最小割集。（12分） V1 4 V4 8 7 6 4 5Vs 9 V2 3 V5 3 Vt 15 5 2 8 7 V3 7 V6解：找增广链： （6分） (Vs,4) V1 (4,4) V4 (8,4) 7 6 4 (5,4)Vs ( 9,3) V2 (V1,4) (3,3) V5 (3,3) Vt (15,7) 5 2 8 (7,7) V3 (7,7) V6 (Vs,8) （3分）最小割集为：V*=（V3，V6），（V2，V5），（V1，V4） （1分）C*（V，V）=14 （1分）且V*（f）=14 （1分）七、某厂有一种新产品，其推销策略有三种可供选择，各方案所需的资金、时间不同，市场情况也有差别，因而获利和亏损情况不同，而市场情况有三种：（需要量大），（需要量一般），（需要量低）。其概率为0.3，0.4，0.3，其损益矩阵如下表：（10分）二五二六学年 第二学期 运筹学 试卷 B 参考答案及评分标准 QiSi市场情况 Q1Q2Q3S14510-8S225280S31599 (1)分别用最大收益期望值(EMV)决策准则和最小机会损失期望值（EOL）决策准则决定该公司最佳设计方案。（4分）(2)如果该公司能确切掌握市场需求信息，求完备信息的收益期望值(EPPI)。（3分）(3)若有一单位愿帮助该公司调查市场的确切需要量，该公司最多能付出调查费是多少(EVPI)？（3分）解：（1）最大收益期望矩阵为：Q1Q2Q3EMVEMV*S14510-815.1S22528018.7S3159910.8 （2分）最小机会损失矩阵为：Q1Q2Q3EMVEOL*S10181712.3S220088.7S33019016.6 （2分）（2）EPPI=45*0.3+28*0.4+9*0.3=27.4 （3分）（3）EVPI=27.4-18.7=8.7= EOL* （3分）八、A、B两种产品，都需要经过前后两道工序，每一个单位产品A需要前道工序1小时和后道工序2小时，每单位产品B需要前道工序2小时和后道工序3小时。可供利用的前道工序有11小时，后道工序有17小时。 每加工一个单位产品B的同时，会产生两个单位的副产品C，且不需要任何费用，产品C一部分可出售盈利，其余只能