西南交通大学管理运筹学929 2018年试题和解析
机密启用前西南交通大学 2018年硕士研究生招生入学考试试卷试题代码：929试题名称：管理运筹学一考试时间：2017 年 12 月考生注意：1. 本试题共三大题，共 3 页，满分 150 分，请认真检查；2. 答题时，请直接将答题内容写在考场提供的答题纸上，答在试卷上的内容无效；3. 请在答题纸上按要求填写试题代码和试题名称；4. 试卷不得拆开，否则遗失后果自负。一、问答题（60分，共10小题，每小题 6分）（答在试卷上的内容无效）1、线性规划模型中，何谓自由变量？自由变量和决策变量是什么关系？ 解答：用设定的未知数来表示线性规划问题问题中的未知量，这个设定的未知量就 叫做决策变量，决策变量没有非负约束即为自由变量；自由变量一定是决策变量， 但决策变量不一定是自由变量。2、请分别解释无可行解、无界解、最优解的概念。 解答：无可行解：约束方程组没有公共解，造成线性规划模型无解的解。 无界解：没有任何一个可行解能使得目标函数达到最优，即目标函数没有上 界或下界。最优解：在线性规划模型的所有可行解中，使得目标函数达到最优的解。3、说明下面的数学模型不符合线性规划模型的什么特点？z = 6x + 4x x + 3x2X + x2h330 3X * x 2> 18s.t 13（x）23+ 2x < 49x , x > 0 312解答：（1）此模型不符合线性规划模型目标函数应该是线性函数的特点；（2）此模型不符合线性规划模型目标函数求最大值最小值的特点；（3）此模型不符合线性规划模型约束条件方程组由线性的等式或线性的不等 式的特点。4、以目标函数Min型为例，从基本可行解、求检验数以及基本可行解改进三个方面说明单纯形法和表上作业法的区别。解答：（1）基本可行解：单纯形法是通过构造单位矩阵来确定初始基本可行解，而表 上作业法是通过另外的西北角法、最小元素法或差值法来确定初始基本可 行解。（2）检验数：单纯形法是算出机会费用 z 以后，直接计算检验数的代数式jC _z，而表上作业法是通过另外的闭回路法或者位势法来计算检验数。（3）基本可行解改进：单纯形法和表上作业法均是在当c Z < 0的情况下进 一步改进基本可行解，即若基本可行解不是最小值，那么需要迭代调整。 二者在确定换入变量和换出变量的原则是一样的，但是方法不同，表上作 业法是通过闭回路的方法来确定换入变量和换出变量；单纯形法通过行运 算进行迭代。5、用表上作业法求运输问题的检验数的方法有闭回路法和位势法，位势法的思路是针对基变量X给定系数U和V，建立方程U + V = C。请利用闭回路法的思 iji ji j ij路及以下图形的回路，证明位势法求非基变量检验数的公式九=c -u -V。ij ij i j非基变量基变量-ijXij'X1 i'jX ijj基变量基变量证明：因为X , X , X是基变量，由已知条件有以下方程： I! I!ij' i' j ' i' ju + V 二 c , u + V 二 c , u + V 二 ci j ' ij ' i'j'i' j' i'ji' j根据闭回路法，非基变量的检验数为九二（c + c ）-（c + c ）二c -c + c -cijij i' j 'ij'i' jij ij'i' j'i' j艮卩：九=c u V + u + V u V= c u Vij ij i j' i' j' i' j ij i j故证得九=c u V。ij ij i j6、针对整数规划的分枝定界法：（1）先使用什么方法求出不考虑整数约束的最优解？（3 分）（2）在整数规划模型中，设定决策变量x取值为整数，但用分支定界算法 k求出 b 的值不是整数，那么需要使用什么方法求出分支以后的解？（3 k分）解答：（1）先不考虑原问题的整数约束，求解相应的松弛问题。用图解法或单纯形法2）求得最优解。分枝法：在最优解中选择一个不符合整数约束条件的x其值为b ,以bj j j表示小于b的最大整数。构造两个约束条件：X b 和X nb分别加入原 LP 问题形成两个子问题，因为b 与b +1之间无整数，故这两个子集内的整数解必定与原可行解集合整数解一致。7、利用 FordFulkerson 算法对网络的流量进行调整时，必须遵守容量约束条件 和流量守恒条件。请利用以下图形示例解释：在增加网络的流量时，为何增流链 前向边的流量要加上调整量5 ?（其中假设有增流链xvvvy）v4点发出流量之和345v 点接受流量4之和为8解析：针对中间点v，接收流量之和与发出流量之和均为8,满足流量守恒，针对4增流链xvvvy，边（v , v ）是v接收流量的边，而边（v , v ）是中间点v发出流量3 4 5344454的边。若给增流链xvvvy加上调整量5，就会导致中间点v接收量之和为8+ 53 4 54为了满足流量守恒的条件，中间点v的发出量之和也应该为8+ 5，所以需要把4增流链前向边的流量要加上调整量5。8、假设某统筹图的关键路线有 2 条，如果某一个非关键工序的工序时间延长， 关键路线的状态有什么变化?解析： 若该非关键工序的工序时间延长后不超过关键工序的工序时间，那么统筹图 的关键路线不变；若该非关键工序的工序时间延长后超过关键工序的工序时间，那么统筹图的 关键路线变为该路线。9、对线性规划模型目标函数的c进行灵敏度分析时，如果c在允许范围内变动,jj那么模型的目标函数值是否会改变?为什么?解析：当c对应的变量x为非基变量时，若c在允许范围内变动，最优解不会改j j j变。另外，目标函数值也不会改变。尽管C发生了变动，但作为非基变量X的取jj值为0所以目标函数中c X项的取值仍然为0。jj当c对应的变量X为基变量时，如果c在允许范围内变动，最优解不会改j j j变，但是目标函数值会发生改变。因为尽管基变量X没有改变，但c发生了变动，jj所以目标函数c x项的取值也发生了变动，从而造成目标函数值变动。10、在排队系统中，如果顾客到达时间的间隔是均衡固定的，是否会产生排队现 象？为什么？解析：会产生排队现象。理由是：排队现象的产生是由于顾客到达的时间存在随机性或 者服务员的服务时间存在随机性，因此在顾客到达的时间间隔均衡固定的情况下 服务时间不均衡固定是会产生排队现象的。二、计算题（75分，共 3小题）（答在试卷上的内容无效）1. （25分）某企业利用有限的设备台时以及 A、B 两种原材料，制定出生产甲、乙 两种产品获利最多的生产方案，此方案求解过程如下表所示。已知 X、X 分别 12 表示甲、乙两种产品数量， X ,X , X 均为松弛变量。345c Tj23000cBXBbX1X2X3X4X52X5210101/20X48004123X2301001/4z/23201/4c 一 zjj00201/4请解决以下问题：（1）求解该企业获利最多的生产方案以及获得的最大利润。（10分）（2）如果该企业打算制定将设备出租、A和B两种原材料出售的获利方案，此 方案的线性规划模型是什么？（10分）（3）上面第（2）个问题中的线性规划模型的最优解是什么？（5 分） 解答：（1）题中单纯性表中仍然有正检验数c - z = 1/4，所以没有达到最优解，并且55存在有a >0，需要迭代循环求解，迭代后的单纯形表如下：ijc Tj23000cBXBbX1X2X3X4X52X541001/400x4400-21/213x22011/2-1/80z/233/21/80c 一 zjj00-3/2-1/80上表中所有的检验数都是小于等于0的，所以已经达到了最优，其中最优解为（x ,x ,x ,x ,x ） = （4,2,0,0,4），即生产了 4个单位甲产品和2个单位乙产品，可12345获得最大利润为z = 14兀。（2）此问题即是写出对偶问题的线性规划模型，但必须先写出原问题的的线性规划模型。利用最优单纯形表求解原问题线性规划模型如下：因为 x , x ,x 均为345 松弛变量，所以在初始单纯形表中，它们对应的矩阵是单位矩阵，这需要在对最 优单纯形表中进行行运算，使得x ,x ,x对应的矩阵变为单位矩阵，结果如下：345c Tj23000cBxBbx1x2x3x4x50x38121000x416400100x51204001基于上表，可以写出H此方案的线性扌规划模型如下：max z = 2 x + 3x12x + 2 x < 84 x12 < 16<1 4 x < 12x > 0, j2= 1,2j如果把生产方案看作原问题，那么将设备出租、A和B两种原材料出售获利的 方案可以看作是对偶问题。基于生产方案原问题的模型，即可写出对偶问题的 线性规划模型：min q = 8 y +16 y +12 y123y + 4 y > 2< 2 y1 + 4 y2 > 3、y > 0, j3= 1,2,3（4）上面第（2）问的中线性规划模型的最优解即是对偶问题的最优解，从第 （1）个问题中的最优单纯形表即可读出对偶问题决策变量的最优解： y1 = m+j =叩=3/ 厶 y2 = m+j =叩=1/ 8, y3 = m+j =可= 其中 m = 2 。则最优解为： （y,y ,y ） = （3 / 2,1/ 8,0）1232. （25分）假设下图是某物流公司交通运输线网，可知当前总运输量为5个 单位，边旁数字分别表示线路运输能力、当前运输量、单位运输费用。预测半年内，总的运输量将达到 7个单位。请在保证总运输费用最小的前提下 请设计半年以后的运输方案。52vv54,40,44,4,35,4,33,0,53,1,3解答：首先找到增流链v1网络图如下：v v v取调整量3462，得到运输量为 7 单位的5343,3,34,4,33,24,3然后构建此时运输量为7的网络图的增流网络G f如下图所示:234,-33,-34,-3此时不存在负回路，说明当前已是运输量为 7 的最小费用流，总费用为:W （f ） 3 2 3 3 3 2 4 3 4 3 4
