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

1、西南交通大学2013-2014学年第（二）学期考试试卷线订装封密题号二三四五八七八九十线订装封密题号二三四五八七八九十总成绩得分阅卷教师签字：-填空题（共20分，每题2分）1。线性规划模型中，没有取值约束的决策变量也称为 自由变量 。2。把满足线性规划模型约束条件方程组的解称为可行解。一3。线性规划模型无解指的是无 可行解 和可能.4。对线性规划模型求解，确定基本可行解的方法是一 矩阵 。5。对偶问题最优目标函数值和原问题最优目标函数值厂 相等 的。线订装封密6。b.值灵敏度分析就是在不改变原来最优解基变量但基变量取值可 以变动的前提下，求出4值的允许变动范围。线订装封密7。运输问题的表上作业

2、法中，任意一个非基变量都能和若干号学个 基变量构成唯一的闭号学8。标准指派问题模型的目标函数是 min形式.9。匈牙利法需要把指派问题的系数 矩阵转换为等效 矩阵.10。0一1规划求解方法只检查部分组合，此方法称为 隐枚举 法。二选择题（共15分，每题3分）1。用对偶单纯形法求解时，要求线性规划模型中的B，0。A 约束方程右端值biB 未知数当C目标函数系数c 1D约束方程系数a.2。线性规划模型灵敏度分析中，不改变原来最优解基变量及其取值的情线订装封密况，从而求出值的允许变动范围，指的是A B 灵敏度分析。线订装封密A ci.B ai.C biD x.3。 线性规划模型有解指的是模型有B 和

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

4、问题最优解也可以从对偶问题的最优单纯形表中读出来。（V）4。用单纯形法求解时，检验数为零的变量一定是基变量。（X ） 如果模型存在多重最优解时，也存在非基变量的检验数为零.5。运输问题的解可能会有唯一解、多重解、无界解、不可行解。（X ） 运输问题必定有最优解,有可能是唯一最优解，也有可能出现多重解。6。对整数规划模型的非整数解用凑整方法处理后得到的解一定也是模型 的最优解（X ）凑整得到的解有时不是可行解，有时既使是可行解但不一定是最优解。四简答题（共12分）线性规划模型中所谓的“线性”主要指的是？（4分）答：（1）目标函数是线性的函数形式，有可能是求最大值，如追求利润最大，也有可能是求最小

5、值，如追求成本最低。（2分）（2）约束条件方程组由线性的等式或线性的不等式组成，有W、二、N三种形式。（2分）线性规划模型的c.灵敏度分析中，如果c.在允许的范围内变动时，目 标函数值是否也会发生改变？为什么？（8分）答：（1）当Cj对应的变量X.为非基变量时，最优解不会改变，目标函数值也不会改变， 因为尽管c发生了变动，但作为非基变量x的取值为0,所以目标函数中cx 项的取值仍然为0。（4分）Jjj（2）当对应的变量为基变量时，最优解不会改变，但目标函数值可能会发生改 变，因为尽管基变量没有改变，但匕发生了变动，那么目标函数的匕项取 值就发生了变动，从而可能造成目标函数值变动。（4分）五计算

6、题（共30分）1。（10分）有如下线性规划模型：max z = X + 尤2- 2 xi + % 4s.t.X-s.t.3X + x2 0请用单纯形法求解并判断此模型解的情况。解:将模型化为标准型：max z = X + 尤2 + 0 x X3 + 0 x x4 + 0 x X52 x + 尤？ + 尤3= 4s.t.x尤2+ s.t. 0, i = ,2,3,4,5c. jc.11000cBxbx.x.x3x4x55Bx422300 x3x421-10100 x53-31001Zj jj00000迭代求解,得到如下单纯形表:初始单纯形表如下：c z.上表中非基变量X2的检验数为正数，应该作为

7、换入变量，但所对应的列向量全部小于 0,另外也没有其它非基变量可作为换入变量，所以此线性规划模型为无界解。判卷标准：求解过程8分，出现错误适当扣分，模型解判定2分。2。（10分）某公司需要把三个存储地A1. A2、A3的货物运往三个销售地 B、B、B3,已知三个存储地A当、A3分别有货物7吨、4吨、9吨， 三个销售地B、B、B3分别需要货物3吨、6吨、5吨。另外，如果剩 余货物，三个存储地AA2、A3将分别收取单位存储费10、8、5。 从各工厂到销售地的单位产品运费如下表所示.产地一一一肖地BB 2B 33113A 2192A 37410产销不平衡，虚拟一个销售点鸟，令其销量&4=2014=6

8、.求解的某一 过程如下表所示：f销地f销地产地29310B1B，B3B4产量0A1XX3113107一以2XX192845A3XX741059销量3656=20请解决以下问题：（1）求出所花费用最低的运输方案。（7分）_销地产地3_销地产地3B9B,3B10B产量021922184-5A3794101259销量36562=20对上表用闭回路法或位势法继续求检验数，得到下表：（判卷标准:此过程1分）上表没有负检验数，说明已经找到最优解。最优运输方案为：（1分）（x，x，x ,x，x，x ）二（5,2,3，1，6， 3）（2）在求出的最优运输方案下，支出的总费用为多少？运

9、输费用为多少？存储费用为多少？ （3分）解：在最优运输方案（x13，x14,x21，x24，x32，x34）=（5,2，3,1，6，3）下，支出的总费f _销地产地2B9B,3B10B产量0A13-111一23107一以219128-145A37104101259销量3656=20上表中，有&4的检验数为负值，说明当前的基本解还不是最优解，把&4作为换入变量，继续求解 如下表所示：（判卷标准：此过程3分）销地产地 f39310B1B,B3B4产量0A1XX3113107-2A2XX192845A3XX741059销量36562=20用为:用为:1=3x5+10 x2+1x3+8x1+4x6+5

10、x3=85.运输费用为：3x5+1x3+4x6=42。存储费用为：10 x2+8x1+5x3=43。资源消耗 产品设备（台时）原材料A （kg）资源消耗 产品设备（台时）原材料A （kg）原材料B （kg）I140II204资源数量816123.（10分）某企业计划生产I、II两种产品，已知生产单位产品所需要 的设备台时以及原材料A和B的消耗分别如下表所示：该工厂每生产一件产品I获利2万元，每生产一件产品I获利3万 元。设、分别表示I、I两种产品的产量（在此假设产品小数）， 建立的线性规划模型如下：Max Z = 2 x + 3 xs.tx + 2x 84 x 164 x 2 0求解的最优单纯

11、形表如下表所示：c.23000cBJ xBbx1x2x3x4x52x41001/400 x540021/213x22011/21/801. J233/21/80c. -1.003/2-1/80j由最优单纯形表可知，I、I两种产品的产量分别是4和2，那么获 得的最大总利润就为1=2X4+3X2=14 （万元）.请解决以下问题：（1）如果将原材料A、B出让、设备出租，如何定价才能使所得收入不低于生产I、I两种产品所得的最佳利润？ （2分）（2）如果某商家给出设备租金0元、原材料A单位售价0元、原材料B单位售价2万元的方案，是否可以接受？为什么？ （2分）（3）若把可用的设备台时由8增加到10，是否

12、改变生产方案？如果 改变，求出新的生产方案以及利润变化情况（6分）解：（1）通过最优单纯形表可读出对偶问题最优解，即设备租金为3/2,原材料A售价为1/8，而原材料B的售价为0。（判卷标准:此过程错一问扣1分）（2）可以接受，因为总利润为2*12=24万元,高于基本利润14万元。（判卷标准:此过程错一问扣1分）（3）多增加设备台时，意味着对。1的灵敏度分析，根据公式有：Max -2/（1/2） A1Min （-4/（-2） , 4Ab12,即 b1 的灵敏度范围为4, 10. （判卷标准：此过程2分）多增加2个设备台时，即 b1=2，在灵敏度范围内，新的解为：XN=Xo+Ab1*P3,=4 4

13、 2 +2*0 2 1/2 =4 0 3即新生产方案为I产品生产量为4,11产品生产量为3。（判卷标准:此过程错3分）新的最大总利润为：2*4+3*3=17，总利润会增加，增加了 17-14=3万元。或利用边际值可知q= lz2+1 I =3/2。总利润会增加3/2* （10-8）=3万元。（判卷标准：此过程1分）六建模题（5分）一架货运飞机有效载重为24t,可运输货物重量及运费收入见下表所示：货物123456重量（，）8136957收入（元）352423在飞机载重量的限制下，选择一组收入最多的货物运输；另外，在货物 4、6当中优先运4；货物1和3不能混装;货物2和5至少有一个运走. 请建立0-1规划模型.解：设