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

中国计量学院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、右端常数项b D、系数矩阵A5、具有m个产地n个销地的平衡运输问题模型具有特征为（ ）A、有 mn个约束条件 B、有m+n个非基变量 C、有mn-m-n-1个变量 D、有m+n-1个基变量6、max Z =3x1 + x2 ,4x1 + 3x2 7, x1+ 2x2 4 x1,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、绘制网络图时，对引入的虚活动说法正确的是（ ）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答案改错三、（20分）对于如下的线性规划问题 min z = 3x1 + 2x2 +x3装订线s.t. x1 + x2 + x3 15 (1) 2x1 - x2 + x3 9 (2) -x1 + 2x2 +2x3 8 (3) x1 x2 x3 0 1、（5分）写出题目中线性规划问题的对偶问题； 2、（10分）分别求出原始问题和对偶问题的最优解（求解的次序和方法不限）； 3、（5分）C3如何变化，使该问题的最优性保持不变。四、（15分）在一个33的运输问题中，已知供应量a115，a230，a385；而需求量b120，b230，b380，其最优解运输量如下表所示：15525580又设各位势为u1-2，u23，u35，v12，v25，v310，现问：1、最优总运费是多少？（10分）2、在保持上面解最优解的条件下，各个非基变量的Cij的最小值是什么？（5分）五、（10分）某项目网络图如下，英文字母表示工序，数字表示该工序需要的时间。 a ,7 e,10 g,35 b,8 d,17 h,26装订线 C,12 f,24 i,17 j,34 1、 指出项目的关键路线；（5分）2、 求项目的完工期。（5分）六、（15分）1、求以下网络的最小支撑树（5分）；2、求以下网络从节点1到节点12的最短路径（10分）。 3 4 7 6 2 5 1 1 9 8 4 8 6 3 7 2 4中国计量学院200 200 学年第 学期 运筹学 课程试卷（ C ）参考答案及评分标准开课二级学院：经管学院 ，学生班级： ，教师： 一、单项选择题（20分，每题2分）单项选择题答题表题号12345678910答案DCABDDBDAA二、判断及改错题（20分，每题2分） 判断及改错题答题表题号12345678910答案改错可能有无界解目标值变化不确定/割集弧的容量之和/ 三、（20分）对于如下的线性规划问题 min z = 3x1 + 2x2 +x3s.t. x1 + x2 + x3 15 (1) 2x1 - x2 + x3 9 (2) -x1 + 2x2 +2x3 8 (3) x1 x2 x3 0 1、（5分，每个方程各1分）写出题目中线性规划问题的对偶问题； 解：max w = 15y1 + 9y2 + 8y3s.t. y1 + 2y2 - y3 3 (1) y1 - y2 + 2y3 2 (2) y1 + y2 + 2y3 1 (3) y10、 y2 0、y3 0 2、（10分，步骤为6分，结果为4分）分别求出原始问题和对偶问题的最优解（求解的次序和方法不限）； 解：先将原问题化成以下形式，则有 min z = 3x1 + 2x2 + x3s.t. x1 + x2 + x3 + x4 = 15 (1) -2x1 + x2 - x3 + x5 = -9 (2) -x1 + 2x2 +2x3 +x6 = 8 (3) x1 x2 x3 x4 x5 x6 0X1X2X3X4X5X6右端z-3-2-1000X411110015X5-21-1010-9X6-1220018X1X2X3X4X5X6右端z-1-300-109X4-1201106X32-110-109X6-540021-10X1X2X3X4X5X6右端z0-19/500-7/5-1/511X406/5013/5-1/58X303/510-1/52/55X11-4/500-2/5-1/52 原始问题的最优解为（X1 X2 X3 X4 X5 X6）=（2，0，5，8，0，0），minz=11 对偶问题的最优解为（y1 y2 y3 y4 y5 y6）=（0，7/5，-1/5，0，19/5，0），maxw=11 3、（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/52 X1X2X3X4X5X6右端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/50同时成立，则有-7q 1/2，即有-61+q3/2因此当C3在-6，3/2的范围内变化时，最优性不变。 四、（15分）150552585108015根据位势法原理：基变量cijui+vj计算各基变量的运价（如上图所示）最优总运费为015+55+255+105+80151475（结果6分，步骤4分）根据位势法原理非基变量ijcij-（ ui+vj）所有的ij满足大于零。12c12-（-2+5）0，所以c123，最小值为313c13-（-2+10）0，所以c128，最小值为823c23-（3+10）0，所以c1213，最小值为1311c11-（5+2）0，所以c127，最小值为7（结果3分，步骤2分）五、 （10分）求项目的完工期和关键路线。 a ,7 e,10 g,35 b,8 d,17 h,26 C,12 f,24 i,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)=maxTES(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=53TLS(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)