2017年上海应用技术学院经管学院825运筹学之运筹学教程考研冲刺密押题
● 摘要
一、判断题
1． 结点最早时间同最迟时间相等的点连接的线路就是关键路线。（ ）
【答案】√
【解析】关键路线是指总时差为零的工作链，而该工作链是由一系列最早时间同最迟时间相等的点连接而成的。
2． 如果线性规划问题无最优解，则它的对偶问题也一定没有最优解。（ ）
【答案】√
【解析】它的对偶问题可能无解，也可能有无界解。
3． 在任一图G 中，当点集v 确定后，树图是G 中边数最少的连通图。， （ ）
【答案】×
【解析】连通且不含圈的无向图称为树。
4． 运输问题按照最小元素法给出的初始基可行解，从每一空格出发可以找出且仅能找出惟一的闭合回路。（ ）
【答案】√
【解析】从每一空格出发一定存在和可以找到惟一的闭回路。因（m+n-l）个数字格（基变量）对应的系数向量是一个基。任一空格（非基变量）对应的系数向量是这个基的线性组合。而这些向量构成了闭回路。
二、填空题
5． 运输问题任一基可行解非零分量的个数的条件是_____。
【答案】小于等于行数+列数-1
【解析】任意运输问题的基可行解可变量个数为:行数+列数一l 。然而基变量也可能等于0，所以运输问题 任一基可行解非零分量的个数小于等于行数+列数一1。
6． 现有m 个约束条件，若某模型要求在这m 个条件中取”个条件作为约束，用，1
变量来实现 该问题的约束条件组为:_____。
【答案】
【解析】0一l 变量取1时取该约束条件，否则不取，又一共取S 个约束条件。则可得到约束条件组为:
。
7． 在用对偶单纯形法求解某线性规划问题时, 当进基变量x i 确定后，出基变量的选取原则是:_____。
【答案】
8． 最速下降法的搜索方向_____。
牛顿法的搜索方向为_____。 拟牛顿法的搜索方向为_____。 【答案】
【解析】最速下降法:
可以得出，
当
时，下降最快。
牛顿法：正定二次函
数
即搜索方向是
拟牛顿法
：
（单位阵）
若
是最优点，
则
三、计算题
9． 已知有六台机床x 1，x 2，…，x 6，六个零件y 1，y 2，…，y 6。机床x 1可加工零件y 1; x 2可加工零件y 1，y 2; x3可加工零件y 1，y 2，y 3，x 4可加工零件y 2; x 5可加工零件y 2，y 3，x 4; x 6可加工零件y 2，y 5，y 6。现在要求制订一个加工方案，使一台机床只加工一个零件，一个零件只在一台机床上加工，要求尽可能多地安排零件加工。试把这个问题化为求网络最大流的问题，求出能满足上述条件的加工方案。
【答案】依题意，画出最大容量的网络图，并令（l ）标号过程。进行标号，并找出增广链:
，如图所示。
因v t 已标号，转入调整过程。
图
（2）调整过程。按点的第一个标号找到一条增广链整:
调整后得如图所示的可行流，对这个可行流进入重新标号，寻找增广链。
。按照
在
上调
图
反复标号过程和调整过程，最后得到如图所示的结果。
图
可知，最优加工方案为:机床x 1加工零件y 1，机床x 2加工零件y 2，机床x 3加工零件y 3，机床x 5加工零件y 4，机床x 6加工零件y 6，机床x 4不加工零件，零件y 5没有机床加工。
最大流量是V （f ）=5。
10．已知某运输问题的供需关系及单位运价如表所示，要求:
（l ）用表上作业的方法求出最优调运方案: