1、姓名：报考专业：准考证号码：密封线内不要写题2018年全国硕士研究生招生考试初试自命题试题科目名称：运筹学（A卷B卷）科目代码：817考试时间：3小时 满分 150 分可使用的常用工具：无 R计算器 R直尺 圆规（请在使用工具前打）注意：所有答题内容必须写在答题纸上，写在试题或草稿纸上的一律无效；考完后试题随答题纸交回。一、 填空题(共 5 小题，每小题 3 分，共 15 分)1、（ 3 分）人工变量的含义是 _。 2、（ 3 分）假设某线性规划的可行解的集合为A，而其基本可行解的集合为B，那么B在集合A的 _。3、（ 3 分）线性规划问题MaxZ=CX；AX=b，X0（A为kxl的矩阵，且l
2、k）的基的最多个数为_，基的可行解的最多个数为_。 4、（ 3 分）线性规划问题的所有可行解构成的集合是_,它们有有限个_,线性规划问题的每个基可行解对应可行域的_。 5、（ 3 分）运输问题的产销平衡表中有m个产地n个销地，其决策变量的个数有_ _个，其数值格有_个。 二、判断题并改错 (共 5 小题，每小题 3 分，共 15 分)1、（ 3 分）运输问题的基本可行解在运输表中可能包含闭回路。2、（ 3 分）匈牙利法能求解所有的指派问题。3、（ 3 分）如果对偶问题有可行解且目标值无界，则原问题可能存在可行解也可能不存在可行解。4、（ 3 分）排队论中排队产生的前提是系统中服务率小于到达率。
3、5、（ 3 分）采用对偶单纯形法求解最大值的线性规划问题时，检验数可能会出现正值。三、名词解释( 共 5 小题，每小题 4 分，共 20 分 )1、（ 4 分）可行流：2、（ 4 分）欧拉圈： 3、（ 4 分）基矩阵： 4、（ 4 分）最小树： 5、（ 4 分）动态规划的决策： 四、计算题( 共 5 小题，共 80分)1、（ 20 分）用单纯形法求解线性规划问题，并进行灵敏度分析： （1） 目标函数中变量的系数的变化范围，使其最优解保持不变。（2）当约束条件右端常数项从（2，5）T变为（1，3）T时，讨论最优解的变化。（3）当约束条件右端常数项从（2，5）T变为（2，1）T时，讨论最优解的变化
4、。（4）增加约束条件，讨论最优解的变化。 2、（ 15 分） 用表上作业法求解下述运输问题的最优解，其产品的产地，销地，产销量及运价如下表所示（M为一无穷大值）：产地 运价 销地B1B2B3B4B5产量A181137520A25M84730A36396830销量25252010203、（ 15 分）求下列网络流图的最小费用最大流，弧旁数字为（bij，cij）4、（ 15 分）某公司下属A,B,C三个工厂，生产能力分别为每天30,20,10个单位，每天产品通过下图所示运输网络运到F,G,H三个仓库。工厂车队做出调度，安排了每条运输道路上的一天运输量。问能否完成全部产品的进库任务？为了完成进库任务
5、，应如何调整各运输道路上的运输量？ 5、（ 15 分）用单纯形表求解线性规划问题MaxZ=2X1+5X2X142X1123X1+2X218X1,X20五、建模题( 共 1 小题，共 20分)1、（ 20 分）某种钢材每根长度为3795mm，要将其截成423mm，1053mm，503mm三种长度的材料各90根，应如何安排，才能使消耗的钢材的根数最少？试建立模型。2018年全国硕士研究生招生考试初试自命题试题科目名称：运筹学（A卷B卷）科目代码：817考试时间：3小时 满分 150 分可使用的常用工具：无 R计算器 R直尺 圆规（请在使用工具前打）注意：所有答题内容必须写在答题纸上，写在试题或草稿
6、纸上的一律无效；考完后试题随答题纸交回。二、 填空题(共 5 小题，每小题 3 分，共 15 分)1、（ 3 分）人为将线性规划变成标准型，而人为添加的变量。 2、（ 3 分）顶点地方取得。3、（ 3 分）_Clk_， _ Clk_。 4、（ 3 分）_凸集_, _顶点_, _顶点_。 5、（ 3 分）_m*n _个， _ m+n-1_个。 二、判断题并改错 (共 5 小题，每小题 3 分，共 15 分)1、（ 3 分）错误，基本可行解不包含闭回路2、（ 3 分）错误，匈牙利法只能求解最小值的指派问题。3、（ 3 分）错误，则原问题无可行解。4、（ 3 分）错误，应为服务率大于到达率。5、（
7、3 分）错误，检验数只能是负值，表明对偶可行性。三、名词解释( 共 5 小题，每小题 4 分，共 20 分 )1、（ 4 分）满足弧上的容量约束及起讫点流量守恒等条件的网络流。2、（ 4 分）连通图G中，存在一个圈，这个圈过G的每边一次且仅一次，则该圈称为欧拉圈。 3、（ 4 分）线性规划问题中m行系数列向量里，m个线性无关列向量组成的矩阵。4、（ 4 分）图的支撑树中，所有边的权重之和最小的树。 5、（ 4 分）一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策。四、计算题( 共 5 小题，共 80分)1、（ 20 分）解：将原问题化为标准型Cj-4-3-800
8、bCBXBx1x2x3x4x5-4x1101-102-3x20120-15检验数002-4-3-23-8x3101-102-3x2-2102-11检验数-200-2-3-19因为检验数都不大于零，且b0，此时得到最优解，X=(0，1，2，0，0)T；minz=19。（1）x1为非基变量（2）、B-1=，B-1b1=故此时最优基保持不变，最优解如下X=(0，1，1，0，0)T minz=11（3）、B-1b11=此时最优基改变，采用对偶单纯形法，得最后结果如下X=(3/2，0，1/2，0，0)T minz=10 （4）、将x1-x33加入原最终表，并通过矩阵变换，使x3，x2，x6构成单位矩阵，
9、求得最优解X=(3，5，0，1，0，0)T minz=4*3+3*5+8*0=27 2、（ 15 分） 解：该题为产销不平衡问题，需增加产地A4，利用伏格尔法得如下解利用位势法求得检验数，得检验数均大于0，故该解最优。即A1运20到B3；A2运20到B1，运10到B4；A3运5到B1，25到B2；运费=3*20+4*10+5*6+25*3+5*20=3053、（ 15 分）即f(2)为最大流，Wf(2)为最小费用最大流；总费用=1+3+2+3+4+4=17。4、（ 15 分）解：增加虚拟始点S和虚拟终点T，然后对其进行标号求其最大流，如下图所示由图知，其最大流为50。由于每天进库量要求为60，
10、所以当前运输量不足以完成产品入库任务。还差10个单位的运输链量。故调整方案：抽调弧（A，B）上的5个单位运输能力和弧（B，E）上的5各单位运输能力去加强关键弧（B，D），使CBD=20，CAB=15，CBE=5，就能完成入库任务。5、（ 15 分）解：化为标准型，然后利用单纯形法求解，如下Cj25000bCBXBX1X2X3X4X50X31010040X420010120X53200118检验数250000X31010040X420010125X21.51000.59检验数-5.5000-2.5由最终表可知，非基变量检验数小于零，且b0，故为最优解X=(0,9,4,12,0)T，最大值Z=5*9=45五、建模题( 共 1 小题，共 20分)1、（ 20 分）解：截断方案如下：法1法2法3法4法5法6法7法8法9法101053332222111150310321054324230101230124余量13321318026034042022730738744法11法12法13法14法15法16法17法18法19法201053110000000050310765432104235601345678余量1242042743541191171251331411共20种截法，设每种截法对应的根数为xj第 9 页 共 9 页
