西南交通大学运筹学IA考试题

1、线订装封密 线订装封密 线订装封密 名姓 号学 级班题号一二三四五六七八九十总成绩得分阅卷教师签字：西南交通大学2013 2014学年第（二）学期考试试卷课程代码0220510课程名称 运筹学（运输）I考试时间120分钟一填空题（共20分，每题2分）1.线性规划模型中，没有取值约束的决策变量也称为自由变量 。2,把满足线性规划模型约束条件方程组的解称为可行解 。3.线性规划模型无解指的是无可行解 和无界解两种可能。4,对线性规划模型求解，确定基本可行解的方法是构造单位矩阵 。.对偶问题最优目标函数值和原问题最优目标函数值是相等 的。, 值灵敏度分析就是在不改变原来最优解基变量但基变量取值可以变

2、动的前提下，求出0值的允许变动范围。.运输问题的表上作业法中，任意一个非基变量都能和若干个 基变量构成唯一的闭回路。.标准指派问题模型的目标函数是min 形式。9,匈牙利法需要把指派问题的系数矩阵转换为等效 矩阵。10.0-1规划求解方法只检查部分组合，此方法称为隐枚举 法。二选择题（共15分，每题3分）1,用对偶单纯形法求解时，要求线性规划模型中的 B0A约束方程右端值biB未知数XjC目标函数系数CjD约束方程系数aj2.线性规划模型灵敏度分析中，不改变原来最优解基变量及其取值的情况，从而求出值的允许变动范围，指的是 A B灵敏度分析。 TOC o 1-5 h z A CjBajCbiDX

3、j3,线性规划模型有解指的是模型有B 和 D 两种可能。A不可行解 B 唯一解 C 无界限解 D 多重解4,线性规划模型约束条件方程组中含有A型的求解方法有ACDA两阶段法 B 分枝定界法 C大M法 D 对偶单纯形法5,整数规划模型求解的分枝定界法会用到与或_C。A单纯形法 B 匈牙利法 C 对偶单纯形法D表上作业法三 判断对错（在括号内打X或，在横线上说明错误原因，每题 3分， 共18分，不说明错误原因不得分。）.线性规划模型如果有最优解，则只能在可行域D极点上达到。（X ） 如果存在多重解，其它点也能使目标函数达到最优。.把线性规划模型加入松弛变量或多余变量,目的是为了确定基本可行解 而构

4、造单位矩阵。（X ）目的是把约束条件方程的不等式变换为等式。 TOC o 1-5 h z .原问题最优解也可以从对偶问题的最优单纯形表中读出来。Fv）.用单纯形法求解时，检验数为零的变量一定是基变量。）如果模型存在多重最优解时，也存在非基变量的检验数为零。.运输问题的解可能会有唯一解、多重解、无界解、不可行解。fx）运输问题必定有最优解，有可能是唯一最优解，也有可能出现多重解。.对整数规划模型的非整数解用凑整方法处理后得到的解一定也是模型 的最优解（x ）凑整得到的解有时不是可行解，有时既使是可行解但不一定是最优解。四简答题（共12分） TOC o 1-5 h z .线性规划模型中所谓的“线性

5、”主要指的是？（4分）答：（1）目标函数是线性的函数形式，有可能是求最大值，如追求利润最大，也有可能是求最小值，如追求成本最低。 （2分）（2）约束条件方程组由线性的等式或线性的不等式组成，有&、=、三种形式。（2分）.线性规划模型的Cj灵敏度分析中，如果q在允许的范围内变动时，目 标函数值是否也会发生改变？为什么？（ 8分）答：（1）当c对应的变量为为非基变量时，最优解不会改变，目标函数值也不会改变，因为尽管Cj发生了变动，但作为非基变量 Xj的取值为0,所以目标函数中CjXj 项的取值仍然为0。（4分）（2）当Cj对应的变量Xj为基变量时，最优解不会改变，但目标函数值可能会发生 改变，因为

6、尽管基变量Xj没有改变，但Cj发生了变动，那么目标函数的CjXj项 取值就发生了变动,从而可能造成目标函数值变动。 （4分）五计算题（共30分）1. （10分）有如下线性规划模型：max z = Xi X22xi + X2 4s.t.L 冷气 - 3xi + X2 0请用单纯形法求解并判断此模型解的情况。解：将模型化为标准型：maX z = Xi X2 0 X3 0 x4 0 X5 一 2xi + X2 + X3=4s.t. J-X2+X4- 3xi + X2+ X5 = 3Xj 之 0, i =i,2,3,4,5初始单纯形表如下：Cjii000CbXbbXiX2X3X4X50X34-2ii0

7、00X42i-i0i00X53-3i00izj00000Cj-Zjii000迭代求解，得到如下单纯形表:Cjii000CbxbbXiX2X3X4X50X380-ii20iXi2i-i0i00X590-203iZji-i0i0Cj-Zj020-i0上表中非基变量X2的检验数为正数，应该作为换入变量，但所对应的列向量全部小 于0,另外也没有其它非基变量可作为换入变量，所以此线性规划模型为无界解。 判卷标准：求解过程8分，出现错误适当扣分，模型解判定 2分。（i0分）某公司需要把三个存储地 Ai、A2、A3的货物运往三个销售地 Bi、B、B3,已知三个存储地 Ai、A2、A3分别有货物7吨、4吨、9

8、吨, 三个销售地Bi、B、B3分别需要货物3吨、6吨、5吨。另外，如果剩 余货物，三个存储地A” A2、A3将分别收取单位存储费i0、8、5。 从各工厂到销售地的单位产品运费如下表所示。产地、销地BiB 2B 3Ai3ii3A 2i92A 374i0求解分析：三个存储地的货物总量为 20,三个销售地总销售量为i4,产销不平衡，虚拟一个销售点 B4,令其销量b4=20-14=6。求解的某一 过程如下表所示：产地、销地2B19B23B310B40A13X11X3107-1 A219X28X4-5 A37X410X59销量36562 =20请解决以下问题：(1)求出所花费用最低的运输方案。(7分)解

9、：计算出所有非基变量的检验数，并将求出的检验数填到综合表中对应的非基变量Xij的位置,如下表所示：(判卷标准：此过程 2分)产地销地2Bi9B23B310B40Al311123107-1 a219128-14-5 A37104101259销量36562=20上表中，有X24的检验数为负值，说明当前的基本解还不是最优解，把X24作为换入变量，继续求解如下表所示：(判卷标准：此过程 3分)产地口一销地3Bi9B23B310B40Al3X11X3107-2 A219X2X84-5 A37X410X59销量36562=20对上表用闭回路法或位势法继续求检验数，得到下表：(判卷标准：此过程 1分)产地、

10、销地3Bi9B23B310B40Al301123107-2 A21922184-5 A3794101259销量36562=20上表没有负检验数，说明已经找到最优解。最优运输方案为：(1分)(X13, X14, X21, X24, X32, X34)=(5,2,3,1,6,3)(2)在求出的最优运输方案下，支出的总费用为多少？运输费用为多少？存储费用为多少？(3分)解：在最优运输方案(X13, X14, X21, X24, X32,X34)=(5,2,3,1,6,3)下，支出的总费用为:z=3X5+10 X2+1 X3+8X1+46+5X3=85。运输费用为：3X5+1 X3+4 X6=42o 存储费用为:10 X2+8 X1+5 3=43。（判卷标准：此过程每问1分）（10分）某企业计划生产I、II两种产品，已知生产单位产品所需要 的设备台时以及原材料 A和B的消耗分别如下表所示：资源消耗 产品、设备（台时）原材料A（kg）原材料B（kg）I1:410n204资源数量81612该工厂每生产一件产品I获利2万元，每生产一件产品II获