《2015年961管理运筹学二解析(西南交通大学)》由会员分享，可在线阅读，更多相关《2015年961管理运筹学二解析(西南交通大学)（12页珍藏版）》请在金锄头文库上搜索。
1、2015 年管理运筹学二真题解析一、问答题（70 分，共 10 小题，每小题 7 分） （答在试卷上的内容无效）1.应用单纯型法求解线性规划问题时，出现不可行解的特征是什么？答：当 b 的值出现负数时即表明出现不可行解。2.简述建立对偶模型的规则。答：规则如下：（1）在原问题（P）中，目标函数为求 ，其约束条件统一成“”或1minjfcx“=”。（2）在对偶问题（D）中，目标函数为求 。1imizbu（3）在原问题（P）中与 bi 相应的一个约束条件，对应着对偶问题（D）的一个变量ui：如果该约束条件为不等式，则 ui0；若该约束条件为等式，则 ui 为自由变量。（4）在原问题（P）的每个变量
2、 xj 对应对偶问题（D ）的每一个约束条件：若（P）中xj0，则（D）中为 ；若 xj 为自由变量，则 。1mijac1mijac3.针对增加约束条件方程时，应如何应用对偶单纯型法进行求解？答：其步骤如下：（1）检验原来的最优解是否满足新增的约束条件，若满足原最优解就是新的最优解，否则转第二步；（2）将新增的约束条件方程加上松弛变量或减去多余变量使其化为等式，再把这个等式方程的系数补加到原模型的最有单纯型表中；（3）令原来的基变量和新增的松弛或多余变量作为新的基变量；（4）对新的单纯型表进行初等变换，使新基的系数矩阵变为单位矩阵，此时可以得到一个满足最优检验但不一定满足非负约束条件的可行解；
3、（5）利用对偶单纯型法进行迭代求解。4.对 bi 的灵敏度分析的目的是什么？答：其目的是在 cj 和 aj 不变的前提下并在保证不改变原来最优解基变量但基变量取值可以变动的情况下，求出 bi 值允许变化的范围。并且是在求出最优解以后不必将参数从头算起，就知道最优解及其目标函数值会发生什么变化，使决策者只花很少的费用就可以得到比一组最优解更多的信息。5.简述表上作业法的主要求解步骤。答：步骤如下：（1）利用差值法或最小值法求出一组初始可行解：（2）用闭回路法或位势法求检验数，若无负检验数即得最优解，若有，则转第（3）步；（3）利用闭回路法进行调整；（4）重复第（2）步，直到得到最优解。6.分支定
4、界法在满足什么情况下停止分支？答：当发生下列三种情况之一，就不再分支：（1）该分支子问题无可行解，再分也无可行解；（2）已求得一个不违反任一整数约束的解，此时再分也不可能得到更优的解；（3）此子问题的解不优于任一不违反整数约束的另一子问题的目标函数值。7.简述寻找最小生成树的避圈法的思路。答：思路如下：（1）在连通的无向图 G 中，从所有边中选出一条权最小的边，并把它纳入树中；（2）在 G 中剩余的边中再选择一条权最小且与选进树中的边不构成回路的边，同样将其纳入树中；（3）如此反复，直到找不出这样的边为止。8.简述平行作业法在缩短工期时的思路。答：在工程项目任务十分紧迫、工作面允许以及资源保证
5、供应的条件下，可以组织几个相同的施工队，在同一时间、不同的工区上进行施工，称为平行施工组织方式。 可以充分利用工作面，争取时间、缩短施工工期。9.简述时间参数法确定关键路线的思路。答：思路如下：（1）正确绘制统筹图并计算出时间参数即最早时间和最迟时间；（2）计算出总时差，此时总时差为 0 的工序就是关键工序；（3）由关键工序组成的一条路线就是关键路线。10.针对网络流 f,如何鉴别其为最小费用流？答：构造图 G 的伴随网络图 Gf，检查其中是否存在负费用增流圈，若不存在，则是最小费用最大流，否则，就不是。二、计算题（60 分，共 4 小题，每小题 15 分） （答在试卷上的内容无效）1.某运输
6、网络 G 如下图，各条边数字依次为容量、流量、费用。请完成（1）判断图 G 是否为可行流。 （3 分）（2）判断图 G 是否为流值为 10 的最小费用流，若不是，将当前网络调整为最小费用流。8,6,110,4,26,4,44,2,48,8,2 tv2v1s要求计算出总费用。 （6 分）（3）求图 G 的最小费用最大流。要求计算出总费用。 （6 分）解析：本题是求最小费用最大流，应当熟知什么是可行流，掌握求最大流和最小费用最大流的算法。解：（1）由于每条边的流值均满足容量限制，每个节点的流量也满足流量守恒，故此流是可行流。（2）构造伴随网络 Gf 如下：6,-16,2 2,48,-2 tv2v1
7、s 2,42,-44,-24,-42,1图中存在负费用增流圈 v1 v2 t v1, 所以不是最小费用流。在增流圈上调整即具有负费用的边减去调整值 2，费用为正值的边加上调整值 2 得：6,2,48,8,110,6,28,8,2 tv2v1s 4,2,4继续构造伴随网络图：8,-14,24,48,-2 tv2v1s 2,42,-46,-22,-4此图已不存在负费用增流圈。则已求得流值为 10 的最小费流，费用为：82+24+62+81+24=52（3）用标号算法求最大流：4,2,4sv1v2t8,8,2 10,6,28,8,16,2,4(0,+)(s,2)(-v2,2) (v1,2)找到增流链
8、 sv1v2t,调整量为 2，调整后得：6,4,48,8,110,4,28,8,2 tv2v1s 4,4,4上图已找不到增流链，故得最大流，流值为 12.现构造其伴随网络图：8,-16,22,48,-2 tv2v1s 4,-44,-24,-4图中已找不到负费用增流圈，故得到最小费用最大流，其费用为：82+44+44+42+81=64。2、某企业经营管理 2 个加工厂甲和乙，有 3 个原材料基地以下列数量供应原料：原材料基地 A：200t，单价 200 元/t；原材料基地 B：300t，单价 180 元/t；原材料基地 C：400t，单价 600 元/t；单位运价表（元/t）如下：加工厂原材料基
9、地甲 乙A 40 50B 20 30C 100 60两个加工厂的容量及加工费如下：加工厂 甲 乙容量 450t 500t加工费 400 元/t 300 元/t请完成（1）试建立该运输问题的模型。 （6 分）（2）加工厂出售产品的价格是 900 元/t，问该企业如何组织两个加工厂的生产，使获得的利润最大？利润值是多少？（9 分）解析：本题考查的时不平衡运输问题及表上作业法。需要注意的是，此时的“运费”包括单位运价和加工费，由于供需不平衡，需要虚设一个原材料基地 D，其供应量为 50t；至于求检验数的方法有闭回路和位势法，一般情况下闭回路法较为简单，不易出错而位势法需要求多个变量的值容易算错。解：
10、（1）需要虚设一个原材料基地 D，其供应量为 50t，得供需平衡表如下：加工厂原料甲 乙 销量A 640 750 200B 600 510 300C 660 520 400D 0 0 50产量 450 500用差值法求解（括号中即为运量）：加工厂原料甲 乙 销量A （200） 200B （200） （100） 300C （400） 400D （50） 50产量 450 500用闭回路法非基变量检验数(括号中数字) 如下:加工厂原料甲 乙 销量A 200 (200) 200B 200 100 300C (50) 400 400D 50 (90) 50产量 450 500所有检验数都大于 0,已得
11、最优解为(X 11,X21,X22,X32,X41)=(200,200,100,400,50)最大利润 900900-200640-200600-100510-400520=303000 元.3.下图所示的运输网络，边旁数字表示的最大通行能力。假设该运输网络中某些节点有流量需求，此处已知 v6 需要 5 个流量。请构造分配最大流的新网络图，并分配最大流。1083643342945 v7v6v5v4v3v2v1解析：本题是有节点流量限制的最大流分配问题，一般处理方法是将节点分成两个节点中间相连接的边的权即为该节点所需流量；解：将节点 6 拆分为 v61 和 v62，新网络图如下：5 v62v61
12、 1083643342945 v7v5v4v3v2v1初始可行流为 0，用标号算法求最大流：(v5,2)(v2,)(v1,5)(0,+)5,0 v62v61 10,08,03,06,04,03,03,04,02,09,04,05,0 v7v5v4v3v2v1增流链 v1v2v5v7,调整量 2：v1v2v3v4v5v75,2 4,09,02,24,03,03,04,06,0 3,08,210,0v61 v625,0继续寻找增流链：(v62,4)(v61,4)(v3,4)(v1,9)(0,+)v1v2v3v4v5v75,2 4,09,02,24,03,03,04,06,0 3,08,210,0v
13、61 v625,0增流链为 v1v3v61v62v7,调整量 4：v1v2v3v4v5v75,2 4,09,42,24,43,03,04,06,0 3,08,210,4v61 v625,4继续寻找增流链：(v5,4)(v4,)(v1,4)(0,+)v1v2v3v4v5v75,2 4,09,42,24,43,03,04,06,0 3,08,210,4v61 v625,4增流链为 v1v4v5v7，调整量为 4：v1v2v3v4v5v75,2 4,49,42,24,43,03,04,46,0 3,08,610,4v61 v625,4继续寻找增流链：(v62 ,1)(v61 ,1)(v4 ,3)(v
14、3 ,)(v1,5)(0,+)v1v2v3v4v5v75,2 4,49,42,24,43,03,04,46,0 3,08,610,4v61 v625,4增流链为 v1v3v4v61v62v7，调整量为 1：v1v2v3v4v5v75,2 4,49,52,24,43,03,14,46,1 3,08,610,5v61 v625,5此时标号已无法进行，得到最大流，流值为 11.4.下图为统筹网络图，边旁数字表示工序名称和工序时间（天） 。5edb43 51234a1cf 2问题如下：（1）利用时间参数法计算总工期并确定关键路线及关键工序。 （6 分）（2）通过改进措施，使工序 c 的工序时间减少 1
15、 天，是否对工程总工期有影响？为什么？（3）因为意外原因，使工序 b 的工序时间延长了 2 天，是否对工程总工期有影响？为什么？（3 分）（4）因为意外原因，使工序 b 的工序时间延长了 2 天，工序 d 的工序时间延长了 3 天，是否对工程总工期有影响？为什么？（3 分）解析：本题是绘制统筹图相关的问题。解决本题的步骤是：先绘制完统筹图，再计算时间参数，再确定关键路线。解：（1）统筹图如下：121253773300 2fc1a 432153 4b de5粗实线表示的即为关键路线为 1，2，4，5；关键工序为 ace。（2）c 减少一天，总工期减少一天。因为 c 是关键工序，并且减少一天并未改
16、变关键路线和关键工序。（3）b 延长两天对总工期无影响，因为 b 还未成为关键工序。（4）b 的工序时间延长了 2 天，工序 d 的工序时间延长了 3 天，总工期会增加一天，因为此时的关键路线为 1，3,4,5.关键工序为 bde，总工期为 13 天。三、综合题（20 分，共 2 小题，每小题 10 分） （答在试卷上的内容无效）1.已知某种产品有 n 个销售点，有 m 个配送中心可供选择以实现对该产品的配送。设在配送中心 i 对该产品的年配送能力上限为 Ci，并因配送该产品而会增加年费用为 Fi。各个销售点对该产品必须得到满足，设在销售点 j 对该产品的需求量为 Dj。从配送中心 i 到销售点 j 的单位产品运费为 wij。要求建立整数规划模型，使得运输成本和配送成本总和最小。解析：此题是整数规划问题中关于选址的问题，是 0-1 规划问题，是书上（寇伟华版）原题的小改编。解：设有两组决策变量， 表示从配送中心 i 到销售点 j 的产品
