运筹学试卷F试题

中国计量学院200~~~200学年第学期《运筹学》课程试卷（F）第1页共6页中国计量学院200~200学年第学期《运筹学》课程考试试卷（F）开课二级学院：经管学院，考试时间：年___月__日时考试形式：闭卷√、开卷，允许带计算器、钢笔（圆珠笔）、学生证入场考生姓名：学号：专业：班级：一、单项选择题（共20分，每题2分）1、线形规划具有多重最优解是指（）A、目标函数系数与某约束系数对应成比例B、最优表中存在非基变量的检验数为0C、可行解集合无界D、存在基变量等于02、对偶单纯形法的最小比值规则是为了保证（）A、使原问题保持可行B、使对偶问题保持可行C、逐步消除原问题不可行性D、逐步消除对偶问题不可行性（）3、X1要求是非负整数，它的来源行是X1-5/3X4+7/3X5=8/3,高莫雷方程是（）A、-1/3X4-1/3X5=2/3B、X4-X5=-2C、X4+X5+S=2D、-1/3X4-1/3X5+S=-2/34、原问题与对偶问题都有可行解，则有（）A、原问题有最优解，对偶问题可能没有最优解B、原问题与对偶问题可能都没有最优解C、可能一个问题有最优解，另一个问题具有无界解D、原问题与对偶问题都具有最优解5、要求不超过第一目标值，恰好完成第二目标值，目标函数是（）A、minZ=P1d1-+P2(d2-+d2+)B、minZ=P1d1++P2(d2-+d2+)C、minZ=P1(d1-+d1+)+P2(d2-+d2-)D、minZ=P1(d1-+d1+)+P2d2-6、下列说法正确的是（）A、分支定界法在处理整数规划问题时，借用线性规划单纯形法的基本思想，在求相应的线性模型解的同时，逐步加入对各变量的整数要求限制，从而把原整数规划问题通过分支迭代求出最优解。B、用割平面法求解整数规划问题，构造的解割平面有可能切去一些不属于最优解的整数解。C、用分支定界发求解一个极大化的整数规划时，当得到多于一个可行解时，通常可任取其中一个作为下界，再进行比较剪支。D、整数规划问题的最优值优于其相应的线性规划问题的最优值。装订线中国计量学院200~~~200学年第学期《运筹学》课程试卷（F）第2页共6页7、对运输问题的描述，下列说法正确的是（）A、若变量B组包含有闭回路，则B中的变量对应的列向量线性无关。B、运输问题的对偶问题不一定存在最优解。C、第i行的位势ui是第i个对偶变量。D、运输问题的对偶问题的约束条件为大于等于约束。8、工序（i,j）的最早开工时间TES（i,j）等于（）A、TE（i）B、max{TEs（k）+tki}C、TL（i）D、min{TL（j）-tij}9、下列哪项不属于按环境分类的决策（）A、确定型B、不确定型C、风险型D、单项决策型10、对动态规划问题的描述，下列错误的结论是（）A、给定某一阶段的状态，则在这一阶段以后过程的发展不受这一阶段以前的各个阶段状态的影响，而只与当前状态有关，与过程过去的历史无关。B、动态规划问题数学模型由阶段、状态、决策与策略、状态转移方程及指标函数5个要素组成。C、动态规划是求解多阶段决策问题的一种算法策略，当然也是一种算法。D、动态规划是一种将问题分解为更小的，相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。二、判断题，正确打√，错误打×,并将修改建议简写在对应题号下的改错栏。（20分，每题2分）1、目标规划没有系统约束时，不一定存在满意解。（）2、图解法同单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。（）3、线性规划模型中增加一个约束条件，可行区域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大。（）4、工序时间是随机的，期望值等于3种时间的算术平均值。()5、在折衷主义准则中，乐观系数α的确定与决策者对风险的偏好有关。()6、旅行售货员问题是遍历每一个点的问题。()7、按最小元素法给出的初始基可行解，从每一空格出发可以找出而且仅能找出唯一的闭回路。（）8、在目标规划模型中，正偏差变量应取正值，负偏差变量应取负值。（）9、在任一图G中，当点集V确定后，树图是G中边数最少的连通图。（）10、用动态规划求解一般线性规划问题是将约束条件数作为阶段数，变量作为状态。（）三、数学建模题（10分）某班有男生30人，女生20人，周日去植树。根据经验，一天男生平均每人挖坑20个，或栽树30棵，或给25棵树浇水；女生平均每人挖坑10个，或栽树20棵，或给15棵树浇水。装中国计量学院200~~~200学年第学期《运筹学》课程试卷（F）第3页共6页每个同学在挖坑、栽树、浇水三种工作种只做一种。问应怎样安排，才能使植树（包括挖坑、栽树、浇水）最多？请建立此问题的线性规划模型，不必求解。四、（20分）某运输问题的供需平衡表与单位运价表如下，求出使总的运费最小的最优运输方案以及最小运输费用。运价（元/吨）B1B2B3供应量（吨）A11235A23246需求量（吨）254五、（15分）已知项目各工序的三种估计时间如下表所示1、绘制网络图并计算各工序的期望时间；（5分）2、计算关键工序和关键路线。（5分）工序紧前工序工序的三种时间（小时）ambA－91012BA6810CA131516DB8911EB,C151720FD,E91214装订中国计量学院200~~~200学年第学期《运筹学》课程试卷（F）第4页共6页3、项目完工时间的期望值。（5分）六、（15分）计算如图所示的从A到E的最短路线及其长度（单位：km）.试卷（F）参考答案及评分标准一、单项选择题（20分，每题2分）题号12345678910答案BBDDBACBDC二、判断题（20分，每题2分）题号12345678910答案×√√×√√√×√×Wij中国计量学院200~~~200学年第学期《运筹学》课程试卷（F）第5页共6页改错一定有满意解等于(a+4m+b)/6正负偏差变量均为非负变量数作为阶段数，资源限量为状态变量三、数学建模题（10分）某班有男生30人，女生20人，周日去植树。根据经验，一天男生平均每人挖坑20个，或栽树30棵，或给25棵树浇水；女生平均每人挖坑10个，或栽树20棵，或给15棵树浇水。每个同学在挖坑、栽树、浇水三种工作种只做一种。问应怎样安排，才能使植树（包括挖坑、栽树、浇水）最多？请建立此问题的线性规划模型，不必求解。求解：设男生中挖坑、栽树、浇水的人数分别为x11、x12、x13，女生中挖坑、栽树、浇水的人数分别为x21、x22、x23,S为植树棵树。由题意，模型为：maxS＝20x11+10x21s.t.x11+x12+x13=30x21+x22+x23=2020x11+10x21=30x12+20x22=25x13+15x23Xij≥0i=1,2；j=1,2,3（评分标准：决策变量设对3分，其他每列式1分，合计7分）四、（20分）某运输问题的供需平衡表与单位运价表如下，求出使总的运费最小的最优运输方案以及最小运输费用。运价（元/吨）B11B21B33供应量（吨）A10[2]112[3]35A2113[5]2[1]46需求量（吨）254minz=25元五、（15分）已知项目各工序的三种估计时间如下表所示工序紧前工序工序的三种时间（小时）ambA－91012BA6810CA131516DB8911EB,C151720FD,E91214中国计量学院200~~~200学年第学期《运筹学》课程试卷（F）第6页共6页1、绘制网络图并计算各工序的期望时间；（5分）2、计算关键工序和关键路线。（5分）3、项目完工时间的期望值。（5分）【解】（1）网络图工序紧前工序工序的三种时间（小时）期望值ambA－9101210.17BA68108CA13151614.83DB89119.167EB,C15172017.17FD,E9121411.83(2)关键工序：A,C,E,F；关键路线：①→②→④→⑤→⑥(3)项目完工时间的期望值：10.17+14.83+17.17+11.83＝54(小时)六、（15分）计算如图所示的从A到E的最短路线及其长度（单位：km）.解：最短路线：A-B2-C1-D1-E，其长度为8（最短路用标号法步骤为8分，结果为7分；用动态规划法步骤为10分，结果为5分；）Wij