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

西南交通大学2013－2014学年第(二)学期考试试卷课程代码0220510课程名称运筹学(运输)Ⅰ考试时间120分钟题号一二三四五六七八九十总成绩得分阅卷教师签字：一填空题（共20分，每题2分）1.线性规划模型中，没有取值约束的决策变量也称为自由变量。2.把满足线性规划模型约束条件方程组的解称为可行解。3.线性规划模型无解指的是无可行解和无界解两种可能。4.对线性规划模型求解，确定基本可行解的方法是构造单位矩阵。5.对偶问题最优目标函数值和原问题最优目标函数值是相等的。6.bi值灵敏度分析就是在不改变原来最优解基变量但基变量取值可以变动的前提下，求出bi值的允许变动范围。7.运输问题的表上作业法中，任意一个非基变量都能和若干个基变量构成唯一的闭回路。8.标准指派问题模型的目标函数是min形式。9.匈牙利法需要把指派问题的系数矩阵转换为等效矩阵。10.0-1规划求解方法只检查部分组合，此方法称为隐枚举法。二选择题（共15分，每题3分）1.用对偶单纯形法求解时，要求线性规划模型中的B≥0。A约束方程右端值biB未知数xjC目标函数系数cijD约束方程系数aij2.线性规划模型灵敏度分析中，不改变原来最优解基变量及其取值的情况，从而求出值的允许变动范围，指的是AB灵敏度分析。AcijBaijCbiDxj3.线性规划模型有解指的是模型有B和D两种可能。A不可行解B唯一解C无界限解D多重解4.线性规划模型约束条件方程组中含有≥型的求解方法有ACD。A两阶段法B分枝定界法C大M法D对偶单纯形法5.整数规划模型求解的分枝定界法会用到A或C。A单纯形法B匈牙利法C对偶单纯形法D表上作业法班级学号姓名密封装订线密封装订线密封装订线三判断对错（在括号内打×或√，在横线上说明错误原因，每题3分，共18分，不说明错误原因不得分。）1.线性规划模型如果有最优解，则只能在可行域D极点上达到。（×）如果存在多重解，其它点也能使目标函数达到最优。2.把线性规划模型加入松弛变量或多余变量，目的是为了确定基本可行解而构造单位矩阵。（×）目的是把约束条件方程的不等式变换为等式。3.原问题最优解也可以从对偶问题的最优单纯形表中读出来。（√）4.用单纯形法求解时，检验数为零的变量一定是基变量。（×）如果模型存在多重最优解时，也存在非基变量的检验数为零。5.运输问题的解可能会有唯一解、多重解、无界解、不可行解。（×）运输问题必定有最优解，有可能是唯一最优解，也有可能出现多重解。6.对整数规划模型的非整数解用凑整方法处理后得到的解一定也是模型的最优解（×）凑整得到的解有时不是可行解，有时既使是可行解但不一定是最优解。四简答题（共12分）1.线性规划模型中所谓的“线性”主要指的是？（4分）答：（1）目标函数是线性的函数形式，有可能是求最大值，如追求利润最大，也有可能是求最小值，如追求成本最低。（2分）（2）约束条件方程组由线性的等式或线性的不等式组成，有≤、=、≥三种形式。（2分）2.线性规划模型的cj灵敏度分析中，如果cj在允许的范围内变动时，目标函数值是否也会发生改变？为什么？（8分）答：（1）当cj对应的变量xj为非基变量时，最优解不会改变，目标函数值也不会改变，因为尽管cj发生了变动，但作为非基变量xj的取值为0，所以目标函数中cjxj项的取值仍然为0。（4分）（2）当cj对应的变量xj为基变量时，最优解不会改变，但目标函数值可能会发生改变，因为尽管基变量xj没有改变，但cj发生了变动，那么目标函数的cjxj项取值就发生了变动，从而可能造成目标函数值变动。（4分）五计算题（共30分）1.（10分）有如下线性规划模型：0,33242..2121212121xxxxxxxxtsxxzmax请用单纯形法求解并判断此模型解的情况。解：将模型化为标准型：5,4,3,2,1,033242..00052142132154321ixxxxxxxxxxtsxxxxxzmaxi初始单纯形表如下：cj→11000cBxBbx1x2x3x4x5000x3x4x5423-21-31-11100010001zj00000cj-zj11000迭代求解，得到如下单纯形表：cj→11000cBxBbx1x2x3x4x5010x3x1x5829010-1-1-2100213001zj1-1010cj-zj020-10上表中非基变量x2的检验数为正数，应该作为换入变量，但所对应的列向量全部小于0，另外也没有其它非基变量可作为换入变量，所以此线性规划模型为无界解。判卷标准：求解过程8分，出现错误适当扣分，模型解判定2分。2.（10分）某公司需要把三个存储地A1、A2、A3的货物运往三个销售地B1、B、B3，已知三个存储地A1、A2、A3分别有货物7吨、4吨、9吨，三个销售地B1、B、B3分别需要货物3吨、6吨、5吨。另外，如果剩余货物，三个存储地A1、A2、A3将分别收取单位存储费10、8、5。从各工厂到销售地的单位产品运费如下表所示。销地产地B1B2B3A13113A2192A37410求解分析：三个存储地的货物总量为20，三个销售地总销售量为14，产销不平衡，虚拟一个销售点B4，令其销量b4=20-14=6。求解的某一过程如下表所示：请解决以下问题：（1）求出所花费用最低的运输方案。（7分）解：计算出所有非基变量的检验数，并将求出的检验数填到综合表中对应的非基变量xij的位置，如下表所示：（判卷标准：此过程2分）销地产地2B19B23B310B4产量0A113211④3③107-1A2③119①2-184-5A3107⑥41210③59销量3656Σ=20上表中，有x24的检验数为负值，说明当前的基本解还不是最优解，把x24作为换入变量，继续求解如下表所示：（判卷标准：此过程3分）销地产地3B19B23B310B4产量0A1×3×11⑤3②107-2A2③1×9×2①84-5A3×7⑥4×10③59销量3656Σ=20对上表用闭回路法或位势法继续求检验数，得到下表：（判卷标准：此过程1分）销地产地3B19B23B310B4产量0A103211⑤3②107-2A2③12912①84-5A397⑥41210③59销量3656Σ=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=3×5+10×2+1×3+8×1+4×6+5×3=85。销地产地2B19B23B310B4产量0A1×3×11④3③107-1A2③1×9①2×84-5A3×7⑥4×10③59销量3656Σ=20运输费用为：3×5+1×3+4×6=42。存储费用为：10×2+8×1+5×3=43。（判卷标准：此过程每问1分）3.（10分）某企业计划生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需要的设备台时以及原材料A和B的消耗分别如下表所示：资源消耗产品设备(台时)原材料A(kg)原材料B(kg)ⅠⅡ124004资源数量81612该工厂每生产一件产品Ⅰ获利2万元，每生产一件产品Ⅱ获利3万元。设x1、x2分别表示Ⅰ、Ⅱ两种产品的产量（在此假设产品小数），建立的线性规划模型如下：0,12416482.3221212121xxxxxxtsxxZMax求解的最优单纯形表如下表所示：由最优单纯形表可知，Ⅰ、Ⅱ两种产品的产量分别是4和2，那么获得的最大总利润就为z=2×4+3×2=14（万元）。请解决以下问题：（1）如果将原材料A、B出让、设备出租，如何定价才能使所得收入不低于生产Ⅰ、Ⅱ两种产品所得的最佳利润？（2分）（2）如果某商家给出设备租金0元、原材料A单位售价0元、原材料B单位售价2万元的方案，是否可以接受？为什么？（2分）（3）若把可用的设备台时由8增加到10，是否改变生产方案？如果改变，求出新的生产方案以及利润变化情况（6分）解：（1）通过最优单纯形表可读出对偶问题最优解，即设备租金为3/2，原材料A售价为1/8，而原材料B的售价为0。（判卷标准：此过程错一问扣1分）（2）可以接受，因为总利润为2*12=24万元，高于基本利润14万元。（判卷标准：此过程错一问扣1分）（3）多增加设备台时，意味着对b1的灵敏度分析，根据公式有：Max{-2/(1/2)}≤△b1≤Min{-4/(-2)},-4≤△b1≤2，即b1的灵敏度范围为[4，10]。（判卷标准：此过程2分）cj→23000cBxBbx1x2x3x4x5203x1x5x24421000010-21/21/41/2-1/8010zj233/21/80cj-zj00-3/2-1/80多增加2个设备台时，即△b1=2，在灵敏度范围内，新的解为：XN=XO+△b1*P3’=[442]+2*[0-21/2]=[403]即新生产方案为Ⅰ产品生产量为4，Ⅱ产品生产量为3。（判卷标准：此过程错3分）新的最大总利润为：2*4+3*3=17，总利润会增加，增加了17-14=3万元。或利用边际值可知q1=|z2+1|=3/2。总利润会增加3/2*(10-8)=3万元。（判卷标准：此过程1分）六建模题（5分）一架货运飞机有效载重为24t，可运输货物重量及运费收入见下表所示：货物123456重量(t)8136957收入(元)352423在飞机载重量的限制下，选择一组收入最多的货物运输；另外，在货物4、6当中优先运4；货物1和3不能混装；货物2和5至少有一个运走。请建立0-1规划模型。解：设变量xi表示装载第i种货物，则有：目标函数为MaxZ=3x1+5x2+2x3+4x4+2x5+3x68x1+13x2+6x3+9x4+5x5+7x6≤24x4≥x6x2+x5≥1x1+x3≤1xi=0或1，i=1,2,3,4,5,6评分标准：设变量xi为1分；目标函数为1分；约束方程中每个方程为1分，若自然约束不写或写错扣1分。i,0i1,xi种货物不装载第种货物装载第