中国计量学院-运筹学期末试卷C试题及答案

中国计量学院200~~~200学年第学期《运筹学》课程试卷（C）第1页共6页中国计量学院200~200学年第学期《运筹学》课程考试试卷（C）开课二级学院：经管学院，考试时间：年___月__日时考试形式：闭卷√、开卷，允许带计算器、钢笔（圆珠笔）、学生证入场考生姓名：学号：专业：班级：题序一二三四五六总分得分评卷人一、单项选择题（共20分，每题2分）1、当线性规划问题的可行解集合非空时一定（）A、包含原点B、有界C、无界D、是凸集2、线性规划具有无界解是指（）A、可行解集合无界B、有相同的最小比值C、存在某个检验数Ó≥0且aik≤0(i=1,2,…,m)D、最优表中所有非基变量的检验数非零3.对偶单纯形法的适用条件是（）A、对偶可行，原始不可行B、对偶不可行，原始可行C、对偶可行，原始可行D、对偶不可行，原始不可行4、当基变量Xi的系数Ci波动时，最优表中引起变化的是（）A、基变量XB的数值B、所有非基变量的检验数C、右端常数项bD、系数矩阵A5、具有m个产地n个销地的平衡运输问题模型具有特征为（）A、有mn个约束条件B、有m+n个非基变量C、有mn-m-n-1个变量D、有m+n-1个基变量6、maxZ=3x1+x2,4x1+3x2≤7,x1+2x2≤4x1,x2=0或1，最优解是（）A、（0，0）B、（0，1）C、（1，0）D、（1，1）7、连通图G有n个点，其生成树是T，则有（）A、T有n个点n条边B、T有n个点n-1条边C、T中有m个点m-1条边(mn)D、T的长度等于G的每条边的长度之和8、绘制网络图时，对引入的虚活动说法正确的是（）装订线中国计量学院200~~~200学年第学期《运筹学》课程试卷（C）第2页共6页A、虚活动是真实的活动B、虚活动需要耗用一定时间C、虚活动用实箭线表示D、虚活动仅表示相邻活动之间的衔接关系，不需要时间9、对于不确定型的决策，某人采用乐观主义准则进行决策，则应在收益表中（）A、大中取大B、大中取小C、小中取大D、小中取小10、下列错误的结论是（）A、容量不超过流量B、流量非负C、容量非负D、发点的流出合流等于流入收点的合流单项选择题答题表题号12345678910答案二、判断及改错题，正确打√，错误打×，并将修改建议简写在对应题号下的改错栏。（共20分，每题2分）1、任何线性规划一定有最优解。（）2、线性规划问题减少一个变量，目标值不会比原来变差。（）3、高莫雷约束是将可行域中一部分非整数解切割掉。()4、运输问题的检验数就是对偶问题松弛变量的值。（）5、在指派问题的效率表的某行加上一个非零数最优解不变。（）6、割集中弧的流量之和称为割量。（）7、事件i的最迟时间等于以i为开工事件工序的最迟必须开工时间的最小值（）8、在网络计划中，总时差为0的工序成为关键工序（）9、在不确定型决策中，最小机会损失准则比等可能性准则保守性更强。（）10、普通单纯形法最小比值规则失效说明问题无界。（）判断及改错题答题表题号12345678910答案改错中国计量学院200~~~200学年第学期《运筹学》课程试卷（C）第3页共6页三、（20分）对于如下的线性规划问题minz=3x1+2x2+x3s.t.x1+x2+x3≤15(1)2x1-x2+x3≥9(2)-x1+2x2+2x3≤8(3)x1x2x3≥01、（5分）写出题目中线性规划问题的对偶问题；2、（10分）分别求出原始问题和对偶问题的最优解（求解的次序和方法不限）；3、（5分）C3如何变化，使该问题的最优性保持不变。装订线中国计量学院200~~~200学年第学期《运筹学》课程试卷（C）第4页共6页四、（15分）在一个3×3的运输问题中，已知供应量a1＝15，a2＝30，a3＝85；而需求量b1＝20，b2＝30，b3＝80，其最优解运输量如下表所示：[15][5][25][5][80]又设各位势为u1＝-2，u2＝3，u3＝5，v1＝2，v2＝5，v3＝10，现问：1、最优总运费是多少？（10分）2、在保持上面解最优解的条件下，各个非基变量的Cij的最小值是什么？（5分）中国计量学院200~~~200学年第学期《运筹学》课程试卷（C）第5页共6页五、（10分）某项目网络图如下，英文字母表示工序，数字表示该工序需要的时间。a,7e,10g,35②⑤b,8d,17h,26①④⑥⑨C,12f,24i,17③⑦j,34⑧1、指出项目的关键路线；（5分）2、求项目的完工期。（5分）装订线中国计量学院200~~~200学年第学期《运筹学》课程试卷（C）第6页共6页六、（15分））1、求以下网络的最小支撑树（5分）；2、求以下网络从节点1到节点12的最短路径（10分）。347①②③④6251198⑤⑥⑦⑧4863⑨⑩⑾⑿724中国计量学院200~~~200学年第学期《运筹学》课程试卷（C）第7页共6页中国计量学院200~200学年第学期《运筹学》课程试卷（C）参考答案及评分标准开课二级学院：经管学院，学生班级：，教师：一、单项选择题（20分，每题2分）单项选择题答题表题号12345678910答案DCABDDBDAA二、判断及改错题（20分，每题2分）判断及改错题答题表题号12345678910答案××√√√×√√√√改错可能有无界解目标值变化不确定///割集弧的容量之和////三、（20分）对于如下的线性规划问题minz=3x1+2x2+x3s.t.x1+x2+x3≤15(1)2x1-x2+x3≥9(2)-x1+2x2+2x3≤8(3)x1x2x3≥01、（5分，每个方程各1分）写出题目中线性规划问题的对偶问题；解：maxw=15y1+9y2+8y3s.t.y1+2y2-y3≤3(1)y1-y2+2y3≤2(2)y1+y2+2y3≤1(3)y1≤0、y2≥0、y3≤02、（10分，步骤为6分，结果为4分）分别求出原始问题和对偶问题的最优解（求解的次序和方法不限）；解：先将原问题化成以下形式，则有minz=3x1+2x2+x3s.t.x1+x2+x3+x4=15(1)-2x1+x2-x3+x5=-9(2)-x1+2x2+2x3+x6=8(3)中国计量学院200~~~200学年第学期《运筹学》课程试卷（C）第8页共6页x1x2x3x4x5x6≥0X1X2X3X4X5X6右端z-3-2-1000X411110015X5-21[-1]010-9X6-1220018X1X2X3X4X5X6右端z-1-300-109X4-1201106X32-110-109X6[-5]40021-10X1X2X3X4X5X6右端z0-19/500-7/5-1/511X406/5013/5-1/58X303/510-1/52/55X11-4/500-2/5-1/52原始问题的最优解为（X1X2X3X4X5X6）=（2，0，5，8，0，0），minz=11对偶问题的最优解为（y1y2y3y4y5y6）=（0，7/5，-1/5，0，19/5，0），maxw=113、（5分）C3如何变化，使该问题最优性不变。解：设有C3+q,当C3=1时，取最优表变形为：X1X2X3X4X5X6右端z0-19/5-q0-7/5-1/511X406/5013/5-1/58X303/510-1/52/55X11-4/500-2/5-1/52X1X2X3X4X5X6右端z0-19/5+3q/500-7/5-q/5-1/5+2q/511+5qX406/5013/5-1/58X303/510-1/52/55X11-4/500-2/5-1/52则若使最优解不变，应有：-19/5+3q/5≤0和-7/5-q/5≤0和-1/5+2q/5≤0同时成立，则有-7≤q≤1/2，即有-6≤1+q≤3/2因此当C3在[-6，3/2]的范围内变化时，最优性不变。中国计量学院200~~~200学年第学期《运筹学》课程试卷（C）第9页共6页四、（15分）[15]0[5]5[25]8[5]10[80]15根据位势法原理：基变量cij＝ui+vj计算各基变量的运价（如上图所示）最优总运费为0×15+5×5+25×5+10×5+80×15＝1475（结果6分，步骤4分）根据位势法原理非基变量σij＝cij-（ui+vj）所有的σij满足大于零。σ12＝c12-（-2+5）》0，所以c12》3，最小值为3σ13＝c13-（-2+10）》0，所以c12》8，最小值为8σ23＝c23-（3+10）》0，所以c12》13，最小值为13σ11＝c11-（5+2）》0，所以c12》7，最小值为7（结果3分，步骤2分）五、（10分）求项目的完工期和关键路线。a,7e,10g,35②⑤b,8d,17h,26①④⑥⑨C,12f,24i,17③⑦⑧j,34TES(1,2)=TES(1,3)=TES(1,4)=0TES(2,4)=TES(1,2)+t12=0+7=7=TES(2,5)TES(3,4)=TES(1,3)+t13=0+12=12=TES(3,7)TES(4,6)=max{TES(2,4)+t24,TES(1,4)+t14,TES(3,4)+t34,}=12TES(5,9)=TES(2,5)+t25=7+10=17TES(6,9)=TES(4,6)+t46=12+17=29TES(7,8)=TES(7,9)=TES(3,7)+t37=12+24=36TES(8,9)=TES(7,8)+t78=36+34=70TEF(5,9)=TES(5,9)+t59=17+35=52TEF(6,9)=TES(6,9)+t69=29+26=55TEF(8,9)=TES(8,9)+t89=70+0=70所以完工期为T=70天，结果为5分。TLS(5,9)=T-t59=70-35=35TLS(6,9)=T-t69=70-26=34TLS(7,9)=T-t79=70-17=53中国计量学院200~~~200学年第学期《运筹学》课程试卷（C）第10页共6页TLS(8,9)=T-t89=70-0=70TLS(7,8)=TLS(8,9)-t78=70-34=36TLS(2,5)=TLS(5,9)-t25=35-10=25TLS(4,6)=TLS(6,9)-t46=34-17=17TLS(3,7)=min{TLS(7,9)-t37,TLS(7,8)-t37}=12TLS(3,4)=TLS(3,7)-t34=12-0=12TLS(2,4)=TLS(2,5)-t24=25-0=25TLS(1,2)=min{TLS(2,5)-t12,TLS(2,4)-t12}=8TLS(1,3)=min{TLS(3,7)-t13,TLS(3,4)-t13}=0TLS(1,4)=TLS(4,6)-t14=17-8=5所以关键路线为：cfj，结果为5分。六、（共15分）最小支撑树为下图所示，权值为35；（最小支撑树为3分，权值为2分）34①②③④2511⑤⑥⑦⑧463⑨⑩⑾⑿24最短路径为1-2-3-4-8-12，路径为18。（其中最短路步骤为4分，结果为6分）