2015年961管理运筹学二解析

2015年961管理运筹学二解析（西南交通大学）一、问答题（70分，共10小题，每小题7分）（答在试卷上的内容无效）应用单纯型法求解线性规划问题时，出现不可行解的特征是什么？答：当b的值出现负数时即表明出现不可行解。简述建立对偶模型的规则。答：规则如下：（1）在原问题（P）中，目标函数为求「，其约束条件统一成“2”或“=”。jjj1（2）在对偶问题（D）中，目标函数为求minzbiuii1（3）在原问题（P）中与bi相应的一个约束条件，对应着对偶问题（D）的一个变量ui：如果该约束条件为不等式，则ui20;若该约束条件为等式，则ui为自由变量。（4）在原问题（P）的每个变量xj对应对偶问题（D）的每一个约束条件：若（P）中xj；maiiuicj若；maiiuicj若xj为自由变量，则i1maiiuicji1针对增加约束条件方程时，应如何应用对偶单纯型法进行求解？答：其步骤如下：（1）检验原来的最优解是否满足新增的约束条件，若满足原最优解就是新的最优解，否则转第二步；（2）将新增的约束条件方程加上松弛变量或减去多余变量使其化为等式，再把这个等式方程的系数补加到原模型的最有单纯型表中；（3）令原来的基变量和新增的松弛或多余变量作为新的基变量；（4）对新的单纯型表进行初等变换，使新基的系数矩阵变为单位矩阵，此时可以得到一个满足最优检验但不一定满足非负约束条件的可行解；5）利用对偶单纯型法进行迭代求解对bi的灵敏度分析的目的是什么？答：其目的是在cj和aj不变的前提下并在保证不改变原来最优解基变量但基变量取值可以变动的情况下，求出bi值允许变化的范围。并且是在求出最优解以后不必将参数从头算起，就知道最优解及其目标函数值会发生什么变化，使决策者只花很少的费用就可以得到比一组最优解更多的信息。简述表上作业法的主要求解步骤。答：步骤如下：（1）利用差值法或最小值法求出一组初始可行解：（2）用闭回路法或位势法求检验数，若无负检验数即得最优解，若有，则转第（3）步；（3）利用闭回路法进行调整；（4）重复第（2）步，直到得到最优解。分支定界法在满足什么情况下停止分支？答：当发生下列三种情况之一，就不再分支：（1）该分支子问题无可行解，再分也无可行解；（2）已求得一个不违反任一整数约束的解，此时再分也不可能得到更优的解；（3）此子问题的解不优于任一不违反整数约束的另一子问题的目标函数值。简述寻找最小生成树的避圈法的思路。答：思路如下：（1）在连通的无向图G中，从所有边中选出一条权最小的边，并把它纳入树中；（2）在G中剩余的边中再选择一条权最小且与选进树中的边不构成回路的边，同样将其纳入树中；（3）如此反复，直到找不出这样的边为止。简述平行作业法在缩短工期时的思路。答：在工程项目任务十分紧迫、工作面允许以及资源保证供应的条件下，可以组织几个

相同的施工队，在同一时间、不同的工区上进行施工，称为平行施工组织方式。可以充分利用工作面，争取时间、缩短施工工期。简述时间参数法确定关键路线的思路。答：思路如下：（1）正确绘制统筹图并计算出时间参数即最早时间和最迟时间；（2）计算出总时差，此时总时差为0的工序就是关键工序；（3）由关键工序组成的一条路线就是关键路线。针对网络流f,如何鉴别其为最小费用流？答：构造图G的伴随网络图Gf,检查其中是否存在负费用增流圈若不存在，则是最小是否存在负费用增流圈若不存在，则是最小费用最大流，否则，就不是。二、计算题（60分，共4小题，每小题15分）（答在试卷上的内容无效）1.某运输网络G如下图，各条边数字依次为容量、流量、费用。8,8,210,4,28,8,210,4,2t8,6,14,2,4 v2请完成（1）判断图G是否为可行流。（3分）（分）（2）判断图G是否为流值为10的最小费用流，若不是，将当前网络调整为最小费用流。要求计算出总费用。（6分）（3）求图G的最小费用最大流。要求计算出总费用。（6分）解析：本题是求最小费用最大流，应当熟知什么是可行流，掌握求最大流和最小费用最大流的算法。解：（1）由于每条边的流量守恒，故此流是可行流。值均满足容量限制每个节点的流量也满足流值均满足容量限制每个节点的流量也满足流（2）构造伴随网络Gf如下：图中存在负费用增流圈v图中存在负费用增流圈v1v2tv1,所以不是最小费用流。在增流圈上调整即具有负费用的边减去调整值2费用为正值的边加上调整值2得：去调整值2费用为正值的边加上调整值2得：此图已不存在负费用增流圈。则已求得流值为10的最小费流，费用为：8义2+2义4+6X2+8X1+2X4=52（3）用标号算法求最大流：找到增流链SV1V2I调整量为找到增流链SV1V2I调整量为2,调整后得:(s,2)(-v2,2)(vb2)\10,6,2^^^8826448.8,210,4,2上图已找不到增流链，故得最大流，流值为6448.8,210,4,2上图已找不到增流链，故得最大流，流值为现构造其伴随网络图:

8X8X2+4义4+4X4+4义2+8义1=64。2、某企业经营管理2个加工厂甲和乙，有3个原材料基地以下列数量供应原料：原材料基地A：200t,单价200元/t;A：200t,单价200元/t;原材料基地B：300t,单价180元/t;原材料基地C：400t,单单位运价表（元/t）如价600元/t;原材料基地'TOC\o"1-5"\h\zB 20 30C 100 60两个加工厂的容量及加工费如下:加工厂■^量加工厂■^量加工费-450t 500t400元/300元/t请完成（1）试建立该运输问题的模型。（6分）（2）加工厂出售产品的价格是900元/t,问该企业如何组织两个加工厂的生产，使获得的利润最大？利润值是多少？（9分）解析：本题考查的时不平衡运输问题及表上作业法。需要注意的是，此时的“运费”包括单位运价和加工费，由于供需不平衡，需要虚设一个原材料基地D，其供应量为50t；至于求检验数的方法有闭回路和位势法，一般情况下闭回路法较为简单，不易出错而位势法需要求多个变量的值容易算错。解：（1）需要虚设一个原材料基地D,其供应量为50t，得供需平衡表如下：量为50t，得供需平衡表如下：加工厂原料A640750200B600510300C660520400D0050产量450£73——/，工口■1■口500乙销量j牛、丁口节甲 加工厂原料AB-c-D-产量AB-c-D-产量（200）（200）（50）450(100)(400)5002003004005F用闭回路法非基变量检验数（括号中数字）如下:加工厂原料甲乙销量A200(200)200

B200100300CD-产量CD-产量(50)50"450400(90)50040050r于0,为(X11,X21,X22,X32,X41)=(200,200,100,400,50)最大利润900义900-200义640-200义600-100X510-400X520=303000元.3.下图所示的运输网络，边旁数字表示的最大通行能力。假设该运输网络中某些节点有流量需求，此处已知v6需要5个流量。请构造分配最大流的新网络图，并分配最大流。解析：本题是有节点流量限制的最大流分配问题，一般处理方法是将节点分成两个节点中间相连接的边的权即为该节点所需流量；解：将节点6拆分为v61和v62,新网络图如下：

2增流链VW2V5V7,调整2增流链VW2V5V7,调整10,0继续寻找增流链：2,2(vi,9) (3,4)%V3V61V62V7次罡星毋培沂班内士旨加班力V1V4V5V7,响罡里力：V1V3V4V61V62V7,调整量为1：增流链为11.此时标号已无法进行，得到最大流，4.下图为统筹网络图，边旁数字表示工序名称和工序时间（天）问题如下：（1）利用时间参数法计算总工期并确定关键路线及关键工序。（6分）（2）通过改进措施，使工序c的工序时间减少1天，是否对工程总工期有影响？为什么？（3）因为意外原因，使工序b的工序时间延长了2天，是否对工程总工期有影响？为什么？（3分）（4）因为意外原因，使工序b的工序时间延长了2天，工序d的工序时间延长了3天，是否对工程总工期有影响？为什么？（3分）解析：本题是绘制统筹图相关的问题。解决本题的步骤是：先绘制完统筹图，再计算时间参数，再确定关键路线。解：（1）统筹图如下：粗实线表示的即为关键路线为1，2，4，5；关键工序为ace。（2）c减少一天，总工期减少一天。因为c是关键工序，并且减少一天并未改变关键路线和关键工序。（3）b延长两天对总工期无影响，因为b还未成为关键工序。（4）b的工序时间延长了2天，工序d的工序时间延长了3天，总工期会增加一天，因为此时的关键路线为1,3,4,5.关键工序为bde,总工期为13天。三、综合题（20分,共2小题,每小题10分）（答在试卷上的内容无效）1.已知某种产品有n个销售点,有m个配送中心可供选择以实现对该产品的配送。设在配送

中心i对该产品的年配送能力上限为Ci，并因配送该产品而会增加年费用为Fi。各个销售点对该产品必须得到满足，设在销售点j对该产品的需求量为7。从配送中心i到销售点j的单位产品运费为wij。要求建立整数规划模型，使得运输成本和配送成本总和最小。解析：此题是整数规划问题中关于选址的问题，是0-1规划问题，是书上（寇伟华版）原题的小改编。解：设有两组决策变量，表示从配送中心i到解：设有两组决策变量，表示从配送中心i到销售点j的产品数量表示是否由配送点i进行配送，若是则yi1，否则yi0，则目标函数为：行配送，若是则yi1，否则yi0，则目标函数为：mnmminzwijxijFiyii1j1 i1配送中心配送能力的约束条件为：xijCiyi,i1,2,3...mj1不配送销售点i时yi0上式左端必为0；配送销售点i时，yi1，从配送中心到各销售点的产品数量应小于等于该配送中心的配送能力。因此为保证每个销售点的需求都得到满足，有约束条件方程：xijDj,j1,2,3...n所以整个模型为：i1mnmminz wijxij FiyixijCiyi,i1,2,3...mj1mxijDj,j1,2,3...ni1xij0,i1,2,...,m;j1,2,...,n0yi1,yi为整数，i1,2,...,m2.已知某产品