西南交通大学管理运筹学929.docx

西南交通大学管理运筹学■_rJ201年试题和解析（总1929-0页）--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小-机密★启用前西南交通大学 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 以后，直接计算检验数的代数式c -z，而表上作业法是通过另外的闭回路法或者位势法来计算检验 jj数3）基本可行解改进：单纯形法和表上作业法均是在当c - z < 0的情况下进 一步改进基本可行解，即若基本可行解不是最小值，那么需要迭代调 整。

二者在确定换入变量和换出变量的原则是一样的，但是方法不同， 表上作业法是通过闭回路的方法来确定换入变量和换出变量；单纯形法 通过行运算进行迭代5、 用表上作业法求运输问题的检验数的方法有闭回路法和位势法，位势法 的思路是针对基变量X给定系数u和v，建立方程u +v =c请利用闭回路 ij i j i j ij法的思路及以下图形的回路， 证明位势法求非基变量检验数的公式九=c — u — vij ij i j非基变量基变量-ij矿X1X 基变量基变量证明：因为 x ,x ,x 是基变量，由已知条件有以下方程：• ■I .1 ■ I .1 ■ij' i' j ' i' ju + v 二 c , u + v 二 c , u + v 二 c i j ' ij ' i' j ' i' j ' i ' j i' j 根据闭回路法，非基变量的检验数为九=(c + c ) — (c + c ) = c — c + c — c ij ij i' j' ij ' i' j ij 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法求出5的值不是整数，那么需要使用什么方法求出分支以后的解k（3） 3 分）解答：(1)2)7、先不考虑原问题的整数约束，求解相应的松弛问题用图解法或单纯形 法求得最优解分枝法：在最优解中选择一个不符合整数约束条件的 x 其值为 b ，以 jj［b ］表示小于b的最大整数构造两个约束条件：x ＜［b ］和x ＞［b ］分 别加入原LP问题形成两个子问题，因为［b ］与［b ］ +1之间无整数，故 这两个子集内的整数解必定与原可行解集合整数解一致利用Ford-Fulkerson算法对网络的流量进行调整时，必须遵守容量约束条件和流量守恒条件请利用以下图形示例解释：在增加网络的流量时，为何 增流链前向边的流量要加上调整量5 (其中假设有增流链xv vvy)345v 点接受流量4之和为8}67, 34, 2v4点发出流量之和解析：针对中间点v，接收流量之和与发出流量之和均为8,满足流量守恒，针4对增流链xv v v y，边(v ,v )是v接收流量的边，而边(v ,v )是中间点v发出流 3 4 5 3 4 4 4 5 4量的边。

若给增流链xvvvy加上调整量5，就会导致中间点v接收量之和为3 4 5 48+ 5，为了满足流量守恒的条件，中间点v的发出量之和也应该为8+ 5，所以4 需要把增流链前向边的流量要加上调整量5 8、 假设某统筹图的关键路线有 2 条，如果某一个非关键工序的工序时间延长，关键路线的状态有什么变化？9、 10、解析： 若该非关键工序的工序时间延长后不超过关键工序的工序时间，那么统筹 图的关键路线不变；若该非关键工序的工序时间延长后超过关键工序的工序时间，那么统筹图 的关键路线变为该路线11、 对线性规划模型目标函数的 c 进行灵敏度分析时，如果 c 在允许范围内 jj变动，那么模型的目标函数值是否会改变为什么解析：当c对应的变量x为非基变量时，若c在允许范围内变动，最优解不会改 变另外，目示函数值也不会改变尽管cj发生了变动，但作为非基变量x.的 取值为0,所以目标函数中cx项的取值仍然为0jj当c对应的变量x为基变量时，如果c在允许范围内变动，最优解不会改 变，但是目示函数值会发生改变因为尽管基变量x.没有改变，但［发生了变 动，所以目标函数c x项的取值也发生了变动，从而造成目标函数值变动。

10、在排队系统中，如果顾客到达时间的间隔是均衡固定的，是否会产生排队 现象？为什么解析：会产生排队现象理由是：排队现象的产生是由于顾客到达的时间存在随机性 或者服务员的服务时间存在随机性，因此在顾客到达的时间间隔均衡固定的情 况下，服务时间不均衡固定是会产生排队现象的二、 计算题（75 分，共 3 小题）（答在试卷上的内容无效）1. （25 分）某企业利用有限的设备台时以及 A、B 两种原材料，制定出生产甲、乙两种产品获利最多的生产方案，此方案求解过程如下表所示已知 x、x 12 分别表示甲、乙两种产品数量， x ,x , x 均为松弛变量345c Ti23000cBxBbx1x2x3x4x52x521010-1/20x4800-4123x2301001/4zi2320-1/4c 一 zi i00-201/4请解决以下问题：（1） 求解该企业获利最多的生产方案以及获得的最大利润10 分）（2） 如果该企业打算制定将设备出租、A和B两种原材料出售的获利方案, 此方案的线性规划模型是什么（10 分）（3） 上面第（2）个问题中的线性规划模型的最优解是什么（（4） 5 分）解答：（1）题中单纯性表中仍然有正检验数c -z = 1/4，所以没有达到最优解，并55且存在有a >0，需要迭代循环求解，迭代后的单纯形表如下：c Ti23000cBxBbx1x2x3x4x52x541001/400x4400-21/213x22011/2-1/80zi233/21/80c 一 zi i00-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对应的矩阵变为单位矩阵，结果如345下：c T23000IcBxBbx1x2x3x4x50x38121000x416400100x51204001基于上表，可以写出此方案的线性规划模型如下：max z 二 2 x + 3x12x + 2 x < 84 x1 2 < 16< 1 4 x < 12、x. > 0, j2二 1,2如果把生产方案看作原问题，那么将设备出租、A和B两种原材料出售获利的 方案可以看作是对偶问题基于生产方案原问题的模型，即可写出对偶问题的 线性规划模型：min q = 8 y +16 y +12 y123y + 4 y > 2< 2 y1 + 4 y2 > 3、y > 0, j3= 1,2,3（5） 上面第（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个单位请在保证总运输费用最小的前提下， 请设计半年以后的运输方案6,1,24,4,33,1,33，0，5 2,0,4J3>v15,4,34,4,3 ' v解答：首先找到增流链v Tv T v T v1网络图如下：取调整量5 = 2，得到运输量为7。