试题2答案.doc_第1页
试题2答案.doc_第2页
试题2答案.doc_第3页
试题2答案.doc_第4页
免费预览已结束,剩余1页可下载查看

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

运筹学答案与评分标准(试题2)一、(30分)给出线性规划问题:max st.用单纯形法求最优解,写出最终单纯形表。试分析下列各种条件下最优解(基)的变化:(1)目标函数中变量x3的系数变为5 ;(2)分别确定目标函数中变量x1的系数c1在什么范围内变动时最优解不变;(3)约束右端项由变为;解:将线性规划问题化为:max st. (3)因此,可得如下初始单纯形表:(5)cj23100CB基bx1x2x3x4x50x411/31/31/3100x531/34/37/301cj- zj23100因321,所以选x2进基,因3/(4/3)1/(1/3),故选x5出基,则得cj23100CB基bx1x2x3x4x50x41/41/40-1/41-1/43x29/41/417/403/4cj- zj5/40-17/40-9/4因5/40,所以选x1进基,因(1/4)/(1/4)(9/4)/(1/4),故选x4出基,则得cj23100CB基bx1x2x3x4x52x1110-14-13x22012-11cj- zj00-3-5-1最优解为:(1,2,0)。(7分)(1)目标函数中变量x3的系数变为5 时,得如下单纯形表,并用单纯形法求解步骤进行计算,其过程如下:cj23500CB基bx1x2x3x4x52x1110-14-13x22012-11cj- zj001-5-1因20,所以选x3进基,因20,故选x2出基,则得cj23500CB基bx1x2x3x4x52x1211/207/2-1/25x3101/21-1/21/2cj- zj0-1/20-5/4-3/2得最优解为:(2,0,1),代入目标函数得z = 9 。(5分)(2)设目标函数中变量x1的系数为c1,则由原单纯形表得如下单纯形表:cjc13100CB基bx1x2x3x4x5c1x1110-14-13x22012-11cj- zj00c1-53-4c1c1-3若要保持原问题最优解不变,则应有所有检验数均小于等于0;即 即 (5分)(3)约束右端项由变为;有 = 将上述结果反映到单纯形表中得:cj23100CB基bx1x2x3x4x52x1010-14-13x23012-11cj- zj00-3-5-1此时,上表中的解仍为可行解,故最优解为:(0,3,0),代入目标函数得z = 9 。(5分)评分标准:1. 单纯形法求最优解15分,若结果不正确,但步骤正确可得10分。2.(1)、(2)(3)小题各5分。3. 其他情况酌情给分。二、(10分)已知线性规划问题求:(1)写出其对偶问题;(5分)(2)直接写出对偶问题的最优解。(5分)解:该问题的对偶问题为: 由对偶问题性质可知: 解之得: 所以Y*=(0,-2)T Max Z=-4 评分标准:写出对偶问题得5分,求解得5分,其他情况酌情给分。三、(15分)已知某运输问题如下(单位:百元/吨):单位运价 销地产地B1B2B3供应量(吨)A137218A2581012A394515需求量(吨)161217求:(1)使总运费最小的调运方案和最小运费。(12分)(2)该问题是否有多个最优调运方案?若没有,说明为什么;若有,请再求出一个最优调运方案来。(3分)解:(1)用伏格尔法确定初始调运方案为:B1B2B3供A111718A21212A331215需16121712=9;22=0;23=6;33=-3 (5分)有ij0,所以需要调整为:B1B2B3供A141418A21212A312315需16121712=6;22=5;23=6;31=3 (5分)因为ij0, 所以为最优方案。 Min Z=3*4+2*14+12*5+12*4+3*5=163 为唯一最优解。 (2分)(2)无,因为ij0,所以该题仅有唯一最优方案。 (3分)评分标准:1. 得运输表5分。2. 运输问题求解8分。3.得出最终结论2分4. 其他情况酌情给分。四、(10分)某市准备在下一年度预算中购置一批救护车,已知每辆救护车购置价为20万元。救护车用于所属的两个郊区县,各分配x1台和x2台。1县救护站从接到电话到救护车出动的响应时间为40-3x1 min,2县相应的响应时间为50-4x2 min。该市确定如下优先级目标:P1:用于救护车购置费用不超过400万元;P2:1县的响应时间不超过5min;P3:2县的响应时间不超过5min。建立求解该问题的目标规划模型。解:其目标规划模型为:评分标准:1. 本题主要考察学生对目标规划的理解。2.求出目标规划的模型得10分。3. 其他情况酌情给分。五、(15分)甲、乙、丙、丁四人加工A、B、C、D四种工件所需时间(分钟)如下表所示。应指派何人加工何种工件,能使总的加工时间最少?工件人ABCD甲149415乙117910丙132105丁1791513工件人ABCD甲149415乙117910丙132105丁1791513解:使用匈牙利方法求上述指派问题的最优解。第一步:变换系数矩阵。(5分)6508002070804061第二步:确定独立零元素。(8分)658278461已经找到4个独立的零元素,故可以确定指派问题的最优指派方案。即甲去加工C工件, 乙去加工A工件, 丙去加工D工件, 丁去加工B工件;其总的加工时间最少,为:4 + 11 + 5 + 9 = 29 。(2分)评分标准:1. 本题主要考察学生指派问题的应用。2.变换系数矩阵得5分,求最优解给8分,得出结论给2分,若结果不正确,但步骤正确可得8分。3. 其他情况酌情给分。六、(20分)某工厂生产三种产品,每种产品重量与利润关系如下表所示。现将此三种产品运往市场出售,运输能力总重量不超过10t,问如何安排运输使总利润最大?种类重量(t/件)利润(元/件)121002314034180解:设第i种产品装载的件数为xi(i=1,2,3) 。则问题可表示为:max 建立动态规划模型,由于决策变量取离散值,所以可用列表法求解。当k=1时,计算结果见下表:S2012345678910f1(s2)00100100200200300300400400500x1*00112233445当k=2时,计算结果见下表S301234567x20000 10,10, 10,1,20,1,2C2+f100100100,140200,140200,240300,240,280300,340,280f2(s3)00100140200240300340x2*00010101S38910x20,1,2,0,1,2,3,0,1,2,3,C2+f1400,340,380400,440,380,420500,44,480,420f2(s3)400440500x2*010当k=3时,=m

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论