西南交通大学管理运筹学929-2018年试题和解析

1、西南交通大学管理运筹学 9292018 年试题和解析( 总 10 页)-本页仅作为文档封面，使用时请直接删除即可-内页可以根据需求调整合适字体及大小-2222机密启用前西南交通大学 2018 年硕士研究生招生入学考试试卷试题代码：929试题名称：管理运筹学一考试时间：201712考生注意：3150效；请在答题纸上按要求填写试题代码和试题名称；试卷不得拆开，否则遗失后果自负。一、 问答题（60分，共10小题，每小题6分）（答在试卷上的内容无效1、线性规划模型中，何谓自由变量自由变量和决策变量是什么关系解答：用设定的未知数来表示线性规划问题问题中的未知量，这个设定的未知量就叫做决策变量，决策变量没

2、有非负约束即为自由变量；自由变量一定是决策变量，但决策变量不一定是自由变量。2、请分别解释无可行解、无界解、最优解的概念。解答：无可行解：约束方程组没有公共解，造成线性规划模型无解的解。无界解：没有任何一个可行解能使得目标函数达到最优，即目标函数没有上界或下界。最优解：在线性规划模型的所有可行解中，使得目标函数达到最优的解3、说明下面的数学模型不符合线性规划模型的什么特点z 6x 4x x 3xx 23303s.t. x 1 x1833(2x )2 2x3 49x ,10312解答：此模型不符合线性规划模型目标函数应该是线性函数的特点；此模型不符合线性规划模型目标函数求最大值最小值的特点；式的

3、特点。4、以目标函数Min 型为例，从基本可行解、求检验数以及基本可行解改进3333三个方面说明单纯形法和表上作业法的区别。解答：本可行解。检验数：单纯形法是算出机会费用 zj以后，直接计算检验数的代数式c zjj，而表上作业法是通过另外的闭回路法或者位势法来计算检验数。c zjj 0 的情况下进一步改进基本可行解，即若基本可行解不是最小值，那么需要迭代调 通过行运算进行迭代。5、用表上作业法求运输问题的检验数的方法有闭回路法和位势法，位势法的思路是针对基变量 xiju 和viju vij c 。请利用闭回路ij法的思路及以下图形的回路， 证明位势法求非基变量检验数的公式ciju v 。ijx

4、ijxxijxijxi jxi j证明：基变量基变量因为 xij, xi j, xi j是基变量，由已知条件有以下方程：u vij c ,u vijic,u vi ji ci j根据闭回路法，非基变量的检验数为ij (cijci j) (cijci j) cijcijci jci j故证得ij c uij即ijv 。j c u vuijijv u vji c u vijij6、针对整数规划的分枝定界法：先使用什么方法求出不考虑整数约束的最优解（3）xk取值为整数，但用分支定界算法求出 bk 的值不是整数，那么需要使用什么方法求出分支以后的解（3） 3 分）4444解答：法求得最优解。分枝法：在

5、最优解中选择一个不符合整数约束条件的xj其值为 b ，以jjjjjb x x 别加入原 LP 与jjjj7、利用Ford-Fulkerson算法对网络的流量进行调整时，必须遵守容量约束条件和流量守恒条件。请利用以下图形示例解释：在增加网络的流量时，为何增流链前向边的流量要加上调整量 （xv v v y ）3 4 5v3v37，38，3v54，26，3v46，5v 点接受流量4之和为8v 点发出流量4之和4解析：针对中间点v4，接收流量之和与发出流量之和均为 8，满足流量守恒，针xv v y ，边(v v 是接收流量的边，而边(v v 是中间点发出流3 4 5344454量的边。若给增流链 xv

6、 v v3 4 5y 加上调整量 ，就会导致中间点v4接收量之和为8+ ，为了满足流量守恒的条件，中间点v48+ ，所以需要把增流链前向边的流量要加上调整量 。8、假设某统筹图的关键路线有 2 条，如果某一个非关键工序的工序时间长，关键路线的状态有什么变化？9、解析：若该非关键工序的工序时间延长后不超过关键工序的工序时间，那么统筹图的关键路线不变；若该非关键工序的工序时间延长后超过关键工序的工序时间，那么统筹图的关键路线变为该路线。11、对线性规划模型目标函数的cj进行灵敏度分析时，如果 cj在允许范围内变动，那么模型的目标函数值是否会改变为什么解析：当c xj为非基变量时，若cj在允许范围内

7、变动，最优解不会改变。另外，目标函数值也不会改变。尽管c发生了变动，但作为非基变量 x 的jj0，所以目标函数中c xjj项的取值仍然为 0。5555当c xj为基变量时，如果cj在允许范围内变动，最优解不会改没有改变，但cj发生了变动，所以目标函数c xjj项的取值也发生了变动，从而造成目标函数值变动。10、在排队系统中，如果顾客到达时间的间隔是均衡固定的，是否会产生排队现象？为什么解析：会产生排队现象。理由是：排队现象的产生是由于顾客到达的时间存在随机性或者服务员的服务时间存在随机性，因此在顾客到达的时间间隔均衡固定的情况下，服务时间不均衡固定是会产生排队现象的。二、 计算题（75 分，共

8、 3 小题）（答在试卷上的内容无效）(25B乙两种产品获利最多的生产方案，此方案求解过程如下表所示。已知 x、xx x x5454212均为松弛变量。cj23000cBxBbx1x2x3x4x52x21010-1/20 x800-4123x301001/4zj2320-1/4c zjj00-201/4请解决以下问题：求解该企业获利最多的生产方案以及获得的最大利润。（10）如果该企业打算制定将设备出租、A和 B此方案的线性规划模型是什么（10）上面第（2）个问题中的线性规划模型的最优解是什么（4） 5 分）解答：题中单纯性表中仍然有正检验数c z55 1/ 4 ，所以没有达到最优解，并且存在有a

9、cBcB203cjxBx5x4x2zjc zjb4422x11003x20010 x30-21/20 x41/41/2-1/80 x50102j0303/2-3/21/8-1/8000，需要迭代循环求解，迭代后的单纯形表如下：6666上表中所有的检验数都是小于等于 0 的，所以已经达到了最优，其中最优解为(x x x x x (4, 2,0,0, 4) 4212345z 14元。此问题即是写出对偶问题的线性规划模型，但必须先写出原问题的的线性x x x 均为345松弛变量，所以在初始单纯形表中，它们对应的矩阵是单位矩阵，这需要在对x x x345对应的矩阵变为单位矩阵，结果如cBcB000cj

10、xBx3x4x523000bx1x2x3x4x581210016400101204001基于上表，可以写出此方案的线性规划模型如下：max z 2x13x2 x 2x 84x12 1614x 12x 0, 1,2j如果把生产方案看作原问题，那么将设备出租、AB两种原材料出售获利的方案可以看作是对偶问题。基于生产方案原问题的模型，即可写出对偶问题的线性规划模型：min q 8y116y212y3 y 4y 22 4y2 3 yj1 0, j3 1,2,3（5） 上面第（2）问的中线性规划模型的最优解即是对偶问题的最优解，从第（1）个问题中的最优单纯形表即可读出对偶问题决策变量的最优解：y z1m

11、1 z 3/ 2,y3 z zm241/ 8, y3 z zm35 0,其中m 2 。y y12, y ) (3 / 2,1/ 8,0)3（25）57请设计半年以后的运输方案。77775,1,25,1,2v33,1,3v46,1,23,0,52,0,4v1v64,4,3v24,4,35,4,3v5解答：首先找到增流链v v v134 v 取调整量 2 76网络图如下：5,3,25,3,2v33,3,3v46,3,23,0,52,0,4v1v64,4,3v24,4,35,4,3v5然后构建此时运输量为7的网络图的增流网络G，如下图所示：f3,-23,-2v33,-3v43,23,-22,23,5

12、2,4v1v61,34,-3v24,-3v54,-3此时不存在负回路，说明当前已是运输量为 7 的最小费用流，总费用为：W ( f) 32 33 32 43 43 43 57A(25工序代号a 工序代号a b cdba,c工序时间（天）10534工序代号e f gh紧前工序a,d ef , g工序时间（天）5655问题如下：绘制上述建设工程的统筹图。（5）利用事项的最早时间和最迟时间，确定出关键路线和工期（10）8888c工序节省出一台挖掘机，而一台挖掘机投入到其他工序，可使其它工序的工序时间减少 2到哪个工序可使工程的工期提前为什么（10）解答：d4d4f245e665 gh57a51013

13、cb53利用事项的最早时间和最迟时间，确定出关键路线为：014014141010d4f20202525245e66h575 g501a103c1515b5357即有两条关键工序工期均为 25 天： 需要把挖掘机放到工序a或h2524有关键工序，2b4序a或h中的一个。现在对将挖掘机分别放到a 或h 进行讨论如下： 当放于a 时，关键路线为99990 1201212882d4f1818232345e66h575 g501a83c1313b53554 、 当放于h 时，关键路线为0140141410102d4f2920232345e66h375 g501a103c1515b5375 综上所述：需要

14、把挖掘机放到工序a 或h 2523三、 建模题（15 分，共 1 小题）（答在试卷上的内容无效）有一个运输网络如下图所示，图中各个边给出了容量和费用。其中 x 有165x2有和两种产品，数量分别为 412x 87y、y、为三个3123y167y2需要和两49y3需要和两种产品，需求量分别为 8吨和 13 吨；x2处的产品只能运送到需求地 y2x 处的3y 。3请将此网络图转换为可用于求解的单源单汇、单一品种的网络图模型。10101010(+6)(+5)(-6)x1(7,5)x1(7,5)y1(8,5)(6,5)(4,5)v1x2(4,5)（3,5）(5,5)y2(9,5)v2(6,5)(3,5

15、)(6,5)v3(4,5)(8,5)(7,5)x3(8,5)y3(+4)(+12)(-4)(-9)(+8)(+7)(-8)(-13)解析：42471491122x* 生产产品2x* 生产产品3x x 拆成分别生产产品,的产地123x1x1x2x2 x3x3 ；yy y拆成分别销售产品,的销地123y1 y1 y2 y2 y3 y3 ，将转运地v v拆成分别转运产品，的12v1,v1 ,v1 ,v2,v2 ,v2 ,v3,v3 ,v3；最后得到如下单源单汇的网络图：(+6)(+6)(6,0,5)(6,0,5)(+5)v1(6,0,5)(6,0,0)(5,0,5)(8,0,0)(+4)xv1(5,0,5)y1(8,0,0)2(4,0,5)(14,0,0)(4,0,5)y1(5,0,0)(16,