2015年961管理运筹学二解析(西南交通大学)

一、问答题(70分，共10小题，每小题7分)(答在试卷上的内容无效)1.应用单纯型法求解线性规划问题时，出现不可行解的特征是什么？当b的值出现负数时即表明出现不可行解。。答：规则如下： xjjj=1 (2)在对偶问题(D)中，目标函数为求minz=mbu。iii=1 (3)在原问题(P)中与bi相应的一个约束条件，对应着对偶问题(D)的一个变量ui (4)在原问题(P)的每个变量xj对应对偶问题(D)的每一个约束条件：若(P)中xj≥0，则(D)中为mauc；若xj为自由变量，则mau=c。iiijiiijii=13.针对增加约束条件方程时，应如何应用对偶单纯型法进行求解？答：其步骤如下： (1)检验原来的最优解是否满足新增的约束条件，若满足原最优解就是新的最优解，否则转第二步； (2)将新增的约束条件方程加上松弛变量或减去多余变量使其化为等式，再把这个等式方程的系数补加到原模型的最有单纯型表中； (3)令原来的基变量和新增的松弛或多余变量作为新的基变量； (4)对新的单纯型表进行初等变换，使新基的系数矩阵变为单位矩阵，此时可以得到一个满足最优检验但不一定满足非负约束条件的可行解； (5)利用对偶单纯型法进行迭代求解。答：其目的是在cj和aj不变的前提下并在保证不改变原来最优解基变量但基变量取值可以变动的情况下，求出bi值允许变化的范围。并且是在求出最优解以后不必将参数从头算起，就知道最优解及其目标函数值会发生什么变化，使决策者只花很少的费用就可以得到优解更多的信息。法的主要求解步骤。答：步骤如下： (1)利用差值法或最小值法求出一组初始可行解： (2)用闭回路法或位势法求检验数，若无负检验数即得最优解，若有，则转第(3)步； (3)利用闭回路法进行调整； (4)重复第(2)步，直到得到最优解。6.分支定界法在满足什么情况下停止分支？发生下列三种情况之一，就不再分支： (1)该分支子问题无可行解，再分也无可行解； (2)已求得一个不违反任一整数约束的解，此时再分也不可能得到更优的解； (3)此子问题的解不优于任一不违反整数约束的另一子问题的目标函数值。7.简述寻找最小生成树的避圈法的思路。答：思路如下： (1)在连通的无向图G中，从所有边中选出一条权最小的边，并把它纳入树中； (2)在G中剩余的边中再选择一条权最小且与选进树中的边不构成回路的边，同样将其纳入树中； (3)如此反复，直到找不出这样的边为止。8.简述平行作业法在缩短工期时的思路。织几个相同的施工队，在同一时间、不同的工区上进行施工，称为平行施工组织方式。可以充分利用工作面，争取时间、缩短施工工期。9.简述时间参数法确定关键路线的思路。答：思路如下： (1)正确绘制统筹图并计算出时间参数即最早时间和最迟时间； (2)计算出总时差，此时总时差为0的工序就是关键工序； (3)由关键工序组成的一条路线就是关键路线。10.针对网络流f,如何鉴别其为最小费用流？二、计算题(60分，共4小题，每小题15分)(答在试卷上的内容无效)tv2v1s请完成 (1)判断图G是否为可行流。(3分) (2)判断图G是否为流值为10的最小费用流，若不是，将当前网络调整为最小费用流。 (3)求图G的最小费用最大流。要求计算出总费用。(6分)解析：本题是求最小费用最大流，应当熟知什么是可行流，掌握求最大流和最小费用最大流解：(1)由于每条边的流值均满足容量限制，每个节点的流量也满足流量守恒，故此流是 (2)构造伴随网络Gf如下：v1tsv2vvtv1,所以不是最小费用流。在增流圈上调整即具有负费用的边正值的边加上调整值2得：t8,8,210,6,2v2继续构造伴随网络图：v1tssv2此图已不存在负费用增流圈。则已求得流值为8×2+2×4+6×2+8×1+2×4=52此图已不存在负费用增流圈。则已求得流值为8×2+2×4+6×2+8×1+2×4=52 (3)用标号算法求最大流：2v1tsv2tv2vs上图已找不到增流链，故得最大流，流值为12.现构造其伴随网络图：v1t4,-4v2图中已找不到负费用增流圈，故得到最小费用最大流，其费用为：8×2+4×4+4×4+4×2+8×1=64。2、某企业经营管理2个加工厂甲和乙，有3个原材料基地以下列数量供应原料：单位运价表(元/t)如下：加工厂加工厂乙原材料基地ABC两个加工厂的容量及加工费如下：40甲甲450t400元/t乙加工厂容量加工费请完成 (1)试建立该运输问题的模型。(6分) (2)加工厂出售产品的价格是900元/t，问该企业如何组织两个加工厂的生产，使获得的利润最大？利润值是多少？(9分)解析：本题考查的时不平衡运输问题及表上作业法。需要注意的是，此时的“运费”包括单检验数的方法有闭回路和位势法，一般情况下闭回路法较为简单，不易出错而位势法需要求易算错。解：(1)需要虚设一个原材料基地D，其供应量为50t，得供需平衡表如下：原料ABC加工厂甲乙销量400DD产量04500用差值法求解(括号中即为运量)：原料ABCD产量加工厂甲 (200) (200) (50)450乙 (100) (400)销量400用闭回路法非基变量检验数(括号中数字)如下:乙乙100400甲2002000450原料ABCD产量销量400加工厂所有检验数都大于0,已得最优解为(X11,X21,X22,X32,X41)=(200,200,100,400,50)最大利润900×900-200×640-200×600-100×510-400×520=303000元.3.下图所示的运输网络，边旁数字表示的最大通行能力。假设该运输网络中某些节点有流量6需求，此处已知v需要5个流量。请构造分配最大流的新网络图，并分配最大流。65584v766244v24v335解析：本题是有节点流量限制的最大流分配问题，一般处理方法是将节点分成两个节点中间相连接的边的权即为该节点所需流量；解：将节点6拆分为v61和v62，新网络图如下：223446345835v24v3571初始可行流为0，用标号算法求最大流：25v025v22(0,+∞)v31257,增流链vvv1257,v224,05,24v74v16,03继续寻找增流链：55v22(v(0,+∞)4(0,+∞)4333增流链为vvvvv增流链为vvvvv调整量4：v224,05,24v74v16,03继续寻找增流链：v220,+∞)0,+∞)v1v3145145724,4v4v35v71继续寻找增流链：55v224,4,+∞),+∞)324,4v4v35v71此时标号已无法进行，得到最大流，流值为11.4.下图为统筹网络图，边旁数字表示工序名称和工序时间(天)。cc4fd23a3b1问题如下： (1)利用时间参数法计算总工期并确定关键路线及关键工序。(6分) (2)通过改进措施，使工序c的工序时间减少1天，是否对工程总工期有影响？为什么？ (3分) (4)因为意外原因，使工序b的工序时间延长了2天，工序d的工序时间延长了3天，是否对工程总工期有影响？为什么？(3分)解析：本题是绘制统筹图相关的问题。解决本题的步骤是：先绘制完统筹图，再计算时间参0000解：(1)统筹图如下：a3b1774d253c4f5 (2)c减少一天，总工期减少一天。因为c是关键工序，并且减少一天并未改变关键路线 (3)b延长两天对总工期无影响，因为b还未成为关键工序。 (4)b的工序时间延长了2天，工序d的工序时间延长了3天，总工期会增加一天，因为三、综合题(20分，共2小题，每小题10分)(答在试卷上的内容无效)1.已知某种产品有n个销售点，有m个配送中心可供选择以实现对该产品的配送。设在配点对该产品必须得到满足，设在销售点j对该产品的需求量为Dj。从配送中心i到销售点j的单位产品运费为wij。要求建立整数规划模型，使得运输成本和配送成本总和最小。解析：此题是整数规划问题中关于选址的问题，是0-1规划问题，是书上(寇伟华版)原题的小改编。ijiiiijijiii=1j=1i=1配送中心配送能力的约束条件为：ijiij=1ii此，为保证每个销售点的需求都得到满足，有约束条件方程：ijji=1所以整个模型为：ijijiii=1j=1i=1ii销地y1产地x15y2y6y34供应量yxyxyxyxxxx需求量36768