2015年管理运筹学二真题解析
一、问答题（70分，共10小题，每小题7分）（答在试卷上的内容无效）
1.应用单纯型法求解线性规划问题时，出现不可行解的特征是什么？ 答：当b的值出现负数时即表明出现不可行解。
2.简述建立对偶模型的规则。 答：规则如下：
（1）在原问题（P）中，目标函数为求minf??cjxj，其约束条件统一成“≥”或“=”。
j?1n（2）在对偶问题（D）中，目标函数为求minz??biui。
i?1m（3）在原问题（P）中与bi相应的一个约束条件，对应着对偶问题（D）的一个变量ui：如果该约束条件为不等式，则ui≥0；若该约束条件为等式，则ui为自由变量。
（4）在原问题（P）的每个变量xj对应对偶问题（D）的每一个约束条件：若（P）中xj≥0，则（D）中为?aiiui?cj；若xj为自由变量，则?aiiui?cj。
i?1i?1mm
3.针对增加约束条件方程时，应如何应用对偶单纯型法进行求解？ 答：其步骤如下：
（1）检验原来的最优解是否满足新增的约束条件，若满足原最优解就是新的最优解，否则转第二步；
（2）将新增的约束条件方程加上松弛变量或减去多余变量使其化为等式，再把这个等式方程的系数补加到原模型的最有单纯型表中；
（3）令原来的基变量和新增的松弛或多余变量作为新的基变量；
（4）对新的单纯型表进行初等变换，使新基的系数矩阵变为单位矩阵，此时可以得到一个满足最优检验但不一定满足非负约束条件的可行解；
（5）利用对偶单纯型法进行迭代求解。
4.对bi的灵敏度分析的目的是什么？
答：其目的是在cj和aj不变的前提下并在保证不改变原来最优解基变量但基变量取值可以变动的情况下，求出bi值允许变化的范围。并且是在求出最优解以后不必将参数从头算起，就知道最优解及其目标函数值会发生什么变化，使决策者只花很少的费用就可以得到比一组最优解更多的信息。
5.简述表上作业法的主要求解步骤。 答：步骤如下：
（1）利用差值法或最小值法求出一组初始可行解： （2）用闭回路法或位势法求检验数，若无负检验数即得最优解，若有，则转第（3）步； （3）利用闭回路法进行调整；
（4）重复第（2）步，直到得到最优解。
6.分支定界法在满足什么情况下停止分支？ 答：当发生下列三种情况之一，就不再分支： （1）该分支子问题无可行解，再分也无可行解；
（2）已求得一个不违反任一整数约束的解，此时再分也不可能得到更优的解； （3）此子问题的解不优于任一不违反整数约束的另一子问题的目标函数值。
7.简述寻找最小生成树的避圈法的思路。 答：思路如下：
（1）在连通的无向图G中，从所有边中选出一条权最小的边，并把它纳入树中； （2）在G中剩余的边中再选择一条权最小且与选进树中的边不构成回路的边，同样将其纳入树中；
（3）如此反复，直到找不出这样的边为止。
8.简述平行作业法在缩短工期时的思路。
答：在工程项目任务十分紧迫、工作面允许以及资源保证供应的条件下，可以组织几个相同的施工队，在同一时间、不同的工区上进行施工，称为平行施工组织方式。 可以充分利用工作面，争取时间、缩短施工工期。
9.简述时间参数法确定关键路线的思路。 答：思路如下：
（1）正确绘制统筹图并计算出时间参数即最早时间和最迟时间； （2）计算出总时差，此时总时差为0的工序就是关键工序； （3）由关键工序组成的一条路线就是关键路线。
10.针对网络流f,如何鉴别其为最小费用流？
答：构造图G的伴随网络图Gf，检查其中是否存在负费用增流圈，若不存在，则是最小费用最大流，否则，就不是。
二、计算题（60分，共4小题，每小题15分）（答在试卷上的内容无效） 1.某运输网络G如下图，各条边数字依次为容量、流量、费用。
v18,8,2s4,2,46,4,4t10,4,28,6,1v2请完成
（1）判断图G是否为可行流。（3分）
（2）判断图G是否为流值为10 的最小费用流，若不是，将当前网络调整为最小费用流。要求计算出总费用。（6分）
（3）求图G的最小费用最大流。要求计算出总费用。（6分）
解析：本题是求最小费用最大流，应当熟知什么是可行流，掌握求最大流和最小费用最大流的算法。 解：（1）由于每条边的流值均满足容量限制，每个节点的流量也满足流量守恒，故此流是可行流。
（2）构造伴随网络Gf如下：
4,-4v12,48,-2s6,22,42,-4v2
图中存在负费用增流圈v1 v2 t v1, 所以不是最小费用流。在增流圈上调整即具有负费用的边减去调整值2，费用为正值的边加上调整值2得：
t4,-22,16,-1v18,8,2s6,2,4t10,6,24,2,4v28,8,1
继续构造伴随网络图：
2,-4v14,48,-2s4,22,42,-4v26,-28,-1t
此图已不存在负费用增流圈。则已求得流值为10的最小费流，费用为： 8×2+2×4+6×2+8×1+2×4=52
（3）用标号算法求最大流：
(-v2,2)v18,8,2(0,+∞)s4,2,46,2,4(v1,2)t10,6,28,8,1v2(s,2)
找到增流链sv1v2t,调整量为2，调整后得：
v18,8,2s6,4,4t10,4,24,4,4v28,8,1
上图已找不到增流链，故得最大流，流值为12.现构造其伴随网络图：
4,-4v12,48,-2s4,-4v26,24,-28,-1t
图中已找不到负费用增流圈，故得到最小费用最大流，其费用为： 8×2+4×4+4×4+4×2+8×1=64。
2、某企业经营管理2个加工厂甲和乙，有3个原材料基地以下列数量供应原料： 原材料基地A：200t，单价200元/t；
原材料基地B：300t，单价180元/t； 原材料基地C：400t，单价600元/t； 单位运价表（元/t）如下： 加工厂 原材料基地 A B C 两个加工厂的容量及加工费如下：
加工厂 容量 加工费 甲 450t 400元/t 乙 500t 300元/t 甲 40 20 100 乙 50 30 60 请完成
（1）试建立该运输问题的模型。（6分）
（2）加工厂出售产品的价格是900元/t，问该企业如何组织两个加工厂的生产，使获得的利润最大？利润值是多少？（9分）
解析：本题考查的时不平衡运输问题及表上作业法。需要注意的是，此时的“运费”包括单位运价和加工费，由于供需不平衡，需要虚设一个原材料基地D，其供应量为50t；至于求检验数的方法有闭回路和位势法，一般情况下闭回路法较为简单，不易出错而位势法需要求多个变量的值容易算错。 解：（1）需要虚设一个原材料基地D，其供应量为50t，得供需平衡表如下： 加工厂 原料 A B C D 产量 加工厂 原料 A B C D 产量 加工厂 原料 A B C D
甲 640 600 660 0 450 甲 （200） （200） （50） 450 甲 200 200 (50) 50 乙 750 510 520 0 500 乙 （100） （400） 500 乙 (200) 100 400 (90) 销量 200 300 400 50 销量 200 300 400 50 销量 200 300 400 50 用差值法求解（括号中即为运量）： 用闭回路法非基变量检验数(括号中数字)如下:
管理运筹学二解析（西南交通大学）
