武汉科技大学817运筹学2018--2020+答案考研真题

2018年全国硕士研究生招生考试初试自命题试题 科目名称：运筹学（□A卷?B卷）科目代码：817 考试时间：3小时 满分 150 分 可使用的常用工具：□无 ?计算器 ?直尺 □圆规（请在使用工具前打√） 注意：所有答题内容必须写在答题纸上，写在试题或草稿纸上的一律无效；考完后试题随答题纸交回。 一、 填空题(共 5 小题，每小题 3 分，共 15 分) 1、（ 3 分）人工变量的含义是 ________。 2、（ 3 分）假设某线性规划的可行解的集合为A，而其基本可行解的集合为B，那么B在集合A的 ________。 3、（ 3 分）线性规划问题MaxZ=CX；AX=b，X≥0（A为kxl的矩阵，且l>k）的基的最多个数为_______，基的可行解的最多个数为__________。 4、（ 3 分）线性规划问题的所有可行解构成的集合是________,它们有有限个_______,线性规划问题的每个基可行解对应可行域的________。 5、（ 3 分）运输问题的产销平衡表中有m个产地n个销地，其决策变量的个数有_ _______个，其数值格有________个。 二、判断题并改错 (共 5 小题，每小题 3 分，共 15 分) 1、（ 3 分）运输问题的基本可行解在运输表中可能包含闭回路。 2、（ 3 分）匈牙利法能求解所有的指派问题。 3、（ 3 分）如果对偶问题有可行解且目标值无界，则原问题可能存在可行解也可能不存在可行解。 4、（ 3 分）排队论中排队产生的前提是系统中服务率小于到达率。 5、（ 3 分）采用对偶单纯形法求解最大值的线性规划问题时，检验数可能会出现正值。 三、名词解释( 共 5 小题，每小题 4 分，共 20 分 ) 1、（ 4 分）可行流： 2、（ 4 分）欧拉圈： 第 22 页 共 26 页

3、（ 4 分）基矩阵： 4、（ 4 分）最小树： 5、（ 4 分）动态规划的决策： 四、计算题( 共 5 小题，共 80分) 1、（ 20 分）用单纯形法求解线性规划问题，并进行灵敏度分析：

minz?4x1?3x2?8x3?x1?x3?2?s.t?x2?2x3?5?x?0?i （1） 目标函数中变量x1的系数的变化范围，使其最优解保持不变。 （2）当约束条件右端常数项从（2，5）T变为（1，3）T时，讨论最优解的变化。 （3）当约束条件右端常数项从（2，5）T变为（2，1）T时，讨论最优解的变化。 （4）增加约束条件x1?x3?3，讨论最优解的变化。 2、（ 15 分） 用表上作业法求解下述运输问题的最优解，其产品的产地，销地，产销量及运价如下表所示（M为一无穷大值）： 产地 运价 销地 B1 A1 A2 A3 销量 8 5 6 25 B2 11 M 3 25 B3 3 8 9 20 B4 7 4 6 10 B5 5 7 8 20 产量 20 30 30 3、（ 15 分）求下列网络流图的最小费用最大流，弧旁数字为（bij，cij） （1,4）Vs（2,5）（3,5）（2,1）（1,1）（1,3）V2（3,3）V4Vt（4,2）（4,2）V3V1 第 22 页 共 26 页

4、（ 15 分）某公司下属A,B,C三个工厂，生产能力分别为每天30,20,10个单位，每天产品通过下图所示运输网络运到F,G,H三个仓库。工厂车队做出调度，安排了每条运输道路上的一天运输量。问能否完成全部产品的进库任务？为了完成进库任务，应如何调整各运输道路上的运输量？ A20B10101020C10G15E5F520D3020H10 5、（ 15 分）用单纯形表求解线性规划问题 MaxZ=2X1+5X2 X1≤4 2X1≤12 3X1+2X2≤18 X1,X2≥0 五、建模题( 共 1 小题，共 20分) 1、（ 20 分）某种钢材每根长度为3795mm，要将其截成423mm，1053mm，503mm三种长度的材料各90根，应如何安排，才能使消耗的钢材的根数最少？试建立模型。 第 22 页 共 26 页

：码号 证题考准写 要 不 内 线 封 密 ：业专考报 ：名姓

2018年全国硕士研究生招生考试初试自命题试题 科目名称：运筹学（□A卷?B卷）科目代码：817 考试时间：3小时 满分 150 分 可使用的常用工具：□无 ?计算器 ?直尺 □圆规（请在使用工具前打√） 注意：所有答题内容必须写在答题纸上，写在试题或草稿纸上的一律无效；考完后试题随答题纸交回。 二、 填空题(共 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、（ 3 分）错误，检验数只能是负值，表明对偶可行性。 三、名词解释( 共 5 小题，每小题 4 分，共 20 分 ) 1、（ 4 分）满足弧上的容量约束及起讫点流量守恒等条件的网络流。 2、（ 4 分）连通图G中，存在一个圈，这个圈过G的每边一次且仅一次，则该圈称为欧拉圈。 3、（ 4 分）线性规划问题中m行系数列向量里，m个线性无关列向量组成的矩阵。 4、（ 4 分）图的支撑树中，所有边的权重之和最小的树。 5、（ 4 分）一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策。 四、计算题( 共 5 小题，共 80分) 1、（ 20 分） 解：将原问题化为标准型 第 22 页 共 26 页

maxw??4x1?3x2?8x3?????x1?x3?x4?2x2?2x3?x5?5x1,x2,x3,x4,x5?0-4 -3 x2 0 1 0 0 1 0 -8 x3 x1 1 0 0 1 -2 -2 0 x4 -1 0 -4 -1 2 -2 0 x5 0 -1 -3 0 -1 -3 TCj CB -4 -3 -8 -3 XB x1 x2 x3 x2 b 2 5 -23 2 1 -19 [1] 2 2 1 0 0 检验数 检验数 因为检验数都不大于零，且b>0，此时得到最优解，X=(0，1，2，0，0)；minz=19。 （1）x1为非基变量 ?C1?(?4)??(?2),即C1?2 ?10??10??1??1?-11（2）、B=??21?，Bb=??21??3???1??0 ????????-1故此时最优基保持不变，最优解如下 X=(0，1，1，0，0) minz=11 T?1（3）、Bb=???2-1110??2??2????????0 1??1???3?T此时最优基改变，采用对偶单纯形法，得最后结果如下 X=(3/2，0，1/2，0，0) minz=10 （4）、将x1-x3≧3加入原最终表，并通过矩阵变换，使x3，x2，x6构成单位矩阵，求得最优解X=(3，5，0，1，0，0) minz=4*3+3*5+8*0=27 T 2、（ 15 分） 解：该题为产销不平衡问题，需增加产地A4，利用伏格尔法得如下解 第 22 页 共 26 页

利用位势法求得检验数，得检验数均大于0，故该解最优。 即A1运20到B3；A2运20到B1，运10到B4；A3运5到B1，25到B2； 运费=3*20+4*10+5*6+25*3+5*20=305 3、（ 15 分） 即f(2)为最大流，Wf(2)为最小费用最大流；总费用=1+3+2+3+4+4=17。 4、（ 15 分） 解：增加虚拟始点S和虚拟终点T，然后对其进行标号求其最大流，如下图所示 由图知，其最大流为50。由于每天进库量要求为60，所以当前运输量不足以完成产品入库任务。还差10个单位的运输链量。故调整方案：抽调弧（A，B）上的5个单位运输能力和弧（B，E）上的5各单位运输能力去加强关键弧（B，D），使CBD=20，CAB=15，CBE=5，就能完成入库任务。 第 22 页 共 26 页

5、（ 15 分） 解：化为标准型，然后利用单纯形法求解，如下 Cj CB 0 0 0 0 0 5 XB X3 X4 X5 X3 X4 X2 2 X1 1 2 3 2 1 2 1.5 -5.5 5 X2 0 0 [2] 5 0 0 1 0 0 X3 1 0 0 0 1 0 0 0 0 X4 0 1 0 0 0 1 0 0 0 X5 0 0 1 0 0 0 0.5 -2.5 b 4 12 18 4 12 9 检验数 检验数 由最终表可知，非基变量检验数小于零，且b≧0，故为最优解 X=(0,9,4,12,0)T，最大值Z=5*9=45 五、建模题( 共 1 小题，共 20分) 1、（ 20 分） 解：截断方案如下： 1053 503 423 余量 1053 503 423 余量 法1 3 1 0 133 法11 1 1 5 法2 3 0 1 213 1 0 6 法3 2 3 0 180 0 7 0 法4 2 2 1 260 0 6 1 法5 2 1 2 340 0 5 3 法6 2 0 3 420 0 4 4 法7 1 5 0 227 0 3 5 171 法8 1 4 1 307 0 2 6 251 法9 法10 1 3 2 387 0 1 7 331 1 2 4 44 0 0 8 411 法12 法13 法14 法15 法16 法17 法18 法19 法20 124 204 274 354 11 91 共20种截法，设每种截法对应的根数为xj minz?133x1?213x2?...?411x203x1?3x2?...?x12?90??x1?3x3?...?x19?90?? ?x2?x4?...?6x18?7x19?8x20?90?xj?0,且为整数? 第 22 页 共 26 页

：码号 证题考准写 要 不 内 线 封 密 ：业专考报 ：名姓

2019年全国硕士研究生招生考试初试自命题试题 科目名称：运筹学（?A卷□B卷）科目代码：817 考试时间：3小时 满分 150 分 可使用的常用工具：□无 ?计算器 ?直尺 ?圆规（请在使用工具前打√） 注意：所有答题内容必须写在答题纸上，写在试题或草稿纸上的一律无效；考完后试题随答题纸交回。 一、选择题(共 5 小题，每小题 2 分，共 10 分) 1、（ 2 分）关于线性规划的可行解和基解，下面（ ）叙述正确。 A．可行解必是基解； B．基解必是可行解； C．可行解必然是非基变量为0，基变量均非负； D．对应基，非基变量均为0得到的解均为基解。 2、（ 2 分）线性规划最优解不唯一是指( )。 A．可行解集合无界 ； B．存在某个检验数?k?0且aik?0(i?1,2...m)； C．可行解集合是空集； D．最优表中存在非基变量的检验数非零； 3、（ 2 分）使用人工变量法求解极大化线性规划问题时，当所有的检验数?j?0 在基变量中仍含有非零的人工变量，表明该线性规划问题 （ ） A．有唯一的最优解 B．有无穷多最优解 C．为无界解 D．无可行解 4、（ 2 分）?是关于可行流f的一条增广链，则在?上有( ) A．对任意?i,j????,f?ij?Cij B．对任意?i,j???,fij?Cij C．对任意?i,j????,fij?Cij D． 对任意?i,j????,fij?0 5、（ 2 分） 一个连通图的最小支撑树 ( ) 。 A. 是唯一存在的； B. 可能不唯一； C.可能不存在； D. 一定有多个。 第 22 页 共 26 页

二、填空题(共 5 小题，每小题 3 分，共 15 分) 1、（ 3 分）求最小生成树问题，常用的方法有： 。 2、（ 3 分）在用逆向解法求动态规划时，fk(sk)的含义是： 。 ?MaxZ?x1?x2?2x?x?6?122时均取得最优解，3、（ 3 分）若整数规划?, 在x1?0，?4x1?5x2?20??x1,x2?0且x1，x2为整数*则其最优解x? ，f(x*)? 。 4、（ 3 分）如果某一整数规划，所对应的线性规划（松弛问题）的最优单纯形表?x2?1/3x3?2/3x4?8/3中，约束方程为?，试写出割平面方x?1/6x?5/6x?5/334?1程： 。 5、（ 3 分）求解动态规划时，顺序法和逆序法的求解原则是： 。 三、判断题并改错 (共 10 小题，每小题2分，共 20 分) 1、（ 2 分）线性规划问题的每一个基解对应可行域的一个顶点。 2、（ 2 分）运输问题的可行解中基变量的个数一定遵循m＋n－1的规则。 3、（ 2 分）动态规划中运用图解法的顺推方法和网络最短路径的标号法是一致的。 4、（ 2 分）Dijkstra算法可以求解任何最短路问题。 5、（ 2 分）一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。 6、（ 2 分）若某种资源的影子价格等于k，当该种资源增加5个单位时，相应的目标函数值将增大5k。 7、（ 2 分）基变量中不再含有非零的人工变量，这表示原问题有可行解。 8、（ 2 分）影子价格反映了资源的稀缺性，影子价格等于零，则越稀缺。 9、（ 2 分）若线性规划无最优解则其可行域无界。 10、（ 2 分）原问题具有无界解，则对偶问题不可行。 四、计算题( 共 6小题，共 90分) 1、（ 20 分） 考虑如下线性规划问题 Max z=3x1+x2+4x3 s.t. 6x1+3x2+5x3≤9 3x1+4x2+5x3≤8 x1，x2， x3≥0 第 22 页 共 26 页

（1）求最优解； （2）直接写出上述问题的对偶问题及其最优解； （3）若问题中x2列的系数变为（3，2）T，问最优解是否有变化； （4）c2由1变为2，是否影响最优解，如有影响，将新的解求出。 2、（ 15 分）某部门有3个生产同类产品的工厂(产地)，生产的产品由4个销售点(销地)出售，各工厂的生产量，各销售点的销售量(单位.t)以及各工厂到各销售点的单位运价(元/t)示于下表中，要求研究产品如何调运才能使总运量最小？ 产 销 B1 4 2 8 18 B2 12 10 5 28 B3 4 3 11 28 B4 11 9 6 24 产量 32 20 44 98╲96

A1 A2 A3 销量 3、（ 15 分）甲乙丙丁四个人，A、B、C、D四项任务，不同的人做不同的工作效率不同，表中数据为时耗，如何指派不同的人去做不同的工作使效率最高？ 4、（ 15 分）求如图所示的网络的最大流和最小截集(割集)，每弧旁的数字是（cij , fij ）。 V1 (4,4 ) V3 (9,5) (6,3) VS (3,1) (3,0) (4,1) Vt (5,3) (7,5) V2 (5,4) V4 第 22 页 共 26 页

5、（ 10 分）用标号法求下列网络V1→V7的最短路径及路长。 4 V1 5 V 4 3 1 V6 7 V2 1 V3 5 3 6 1 3 V5 7 V7 6、（15分）某街区医院门诊部只有一个医生值班，此门诊部备有6张椅子供患者等候应诊。当椅子坐满时，后来的患者就自动离去，不进来。已知每小时有4名患者按Poisson分布到达，每名患者的诊断时间服从负指数分布，平均12分钟，求： （1）患者无须等待的概率； （2）门诊部内患者平均数； （3）有效到达率； （4）患者在门诊部逗留时间的平均值； （5）有多少患者因坐满而自动离去？ 五、建模题( 共 1 小题，共 15分) 1、（ 15 分） 某学校规定，运筹学专业的学生毕业时必须至少学习过两 门数学课、三门运筹学课和两门计算机课。这些课程的编号、名称、学分、所属类别和先修课要求如下表所示。那么，毕业时学生最少可以学习这些课程中哪些课程? 课程编号 1 2 3 4 5 6 7 8 9 课程名称 微积分 线性代数 最优化方法 数据结构 应用统计 计算机模拟 计算机编程 预测理论 数学实验 学分 5 4 4 3 4 3 2 2 3 所属类别 数学 数学 数学；运筹学 数学；计算机 数学；运筹学 计算机；运筹学 计算机 运筹学 运筹学；计算机 先修课要求 微积分；线性代数 计算机编程 微积分；线性代数 计算机编程 应用统计 微积分；线性代数 记i=1，2，…，9表示9门课程的编号。建立数学规划模型无需求解。 (1) 写出问题的目标函数？ (2) 每人至少学习过两门数学课、三门运筹学课和两门计算机课，如何表示此约束条件? (3) 某些课程有先修课要求，如何表示此约束条件? 第 22 页 共 26 页

：码号 证题考准写 要 不 内 线 封 密 ：业专考报 ：名姓

2019年全国硕士研究生招生考试初试自命题试题 科目名称：运筹学（?A卷□B卷）科目代码：817 考试时间：3小时 满分 150 分 可使用的常用工具：□无 ?计算器 ?直尺 □圆规（请在使用工具前打√） 注意：所有答题内容必须写在答题纸上，写在试题或草稿纸上的一律无效；考完后试题随答题纸交回。 一、选择题(共 5 小题，每小题 2 分，共 10 分) 1、（ 2 分） D 2、（ 2 分） D 3、（ 2 分） D 4、（ 2 分） A 5、（ 2 分） B 二、填空题(共 5 小题，每小题 3 分，共 15 分) 1、（ 3 分）破圈法和避圈法 2、（ 3 分）K阶段，状态Sk到终点的最优值 3、（ 3 分）x*? （0,4）,（2,2） ，f(x*)? 4 4、（ 3 分）X3+X3=2 5、（ 3 分）终到状态唯一，则用顺序法，起始状态唯一，则用逆序法 三、判断题并改错 (共 10 小题，每小题2分，共 20 分) 1、（ 2 分）错误，可行域的顶点只对应基本可行解。 2、（ 2 分）错误，产销不平衡问题的基变量个数不符合此规则。 3、（ 2分） 正确 4、（ 2 分） 错误，不能求解含负权值的最短路问题。 5、（ 2 分） 正确 6、（ 2 分）错误，如果增加资源导致最优基发生了变化，则不成立 7、（ 2 分）正确 8、（ 2分） 错误，影子价格越高，表明越稀缺 9、（ 2 分） 错误，也可能无可行解。 10、（ 2 分）正确 第 22 页 共 26 页

四、计算题( 共 5 小题，共 90分) 1、（ 20 分） 1）用单纯形法求解线性规划问题： Cj 3 CB XB b X1 0 X4 9 6 0 X5 8 3 Cj-Zj 3 0 X4 1 3 4 X3 8/5 3/5 Cj-Zj 3/5 3 X1 1/3 1 4 X3 7/5 0 Cj-Zj 0 最优解为X1=1/3,X3=7/5,Z=33/5 2)对偶问题为 Minw=9y1+8y2 6y1+3y2≥3 3y1+4y2≥1 5y1+5y2≥4 y1,y2≥0 根据对偶理论写出对偶问题最优解为y1=1/5,y2=3/5 3) 若问题中x2列的系数变为（3，2）T 则P2’=(1/3,1/5)T σ2=c2-CBB-1P2’=-4/5＜0 所以对最优解没有影响 4）c2由1变为2 σ2=-1＜0 所以对最优解没有影响 2、（ 15 分） 解：该运输问题为产销不平衡问题，故需增设一个产地，产量为2，运价均为0，用最小元素法求得初始解如下表示： A1 A2 A3 A4 销量 B1 16 2 18 B2 28 28 B3 24 4 28 B4 8 16 24 产量 32 20 44 2 98 1 X2 3 4 1 -1 4/5 -11/5 -1/3 1 -2 4 X3 5 5 4 0 1 0 0 1 0 0 X4 1 0 0 1 0 0 1/3 -1/5 -1/5 0 X5 0 1 0 -1 1/5 -4/5 -1/3 2/5 -3/5 利用位势法求非基变量检验数可知，A44检验数最小，为-8，故其为入基变量，调整如下， 第 22 页 共 26 页

A1 A2 A3 A4 销量 B1 18 18 B2 28 28 B3 26 2 28 B4 6 16 2 24 产量 32 20 44 2 98 利用位势法求非基变量检验数可知，只有A24检验数为-1，故其为入基变量，调整如下 A1 A2 A3 A4 销量 B1 18 18 B2 28 28 B3 28 28 B4 4 2 16 2 24 产量 32 20 44 2 98 利用位势法求非基变量检验数可知，其均大于0，故求得最优解 最小运费=28×4+4×11+18×2+2×9+28×5+10×6+2×0=446 3、（ 15 分） 解：（1）造0——各行各列减其最小元素 （2）圈0——寻找不同行不同列的0元素，圈之。 ? 所在行和列其它0元素划掉 （3）打?——无?的行打?，打?行上0列打? ，打?列上?行打?，打?行上0列打?，如下图示 （4）划线——无?行、打?列划线 （5）造0——直线未覆盖的元素，减去其最小值，交叉点上加最小元素，产生新的0元素，最后结果如下示 方案为：甲完成C,乙完成A，丙完成B，丁完成D 第 22 页 共 26 页

4、（ 15 分） 解：（1）通过标号法求得第一条增广链，Vs、V2、V4、V3、Vt，调整量为1，如下图 V1 (4,4 ) V3 (9,5) (6,4) VS (3,1) (3,0) (4,0) Vt (5,4) (7,5) V2 (5,5) V4 （2）通过第二次标号法得增广链，Vs、V1、V4、Vt，调整量为2，如下图 V1 (4,4) V3 (9,7) (6,4) (3,2) (4,0) Vs Vt (5,4) (7,7) V2 (5,5) V4 因无法找到增广链，故， 最大流＝11，能标上号的是Vs，V1，V2，V4，因此最小截集为{（V1，V3），（V4，Vt）} 5、（ 10 分） 解：用标号法求解最短路，如下图所示 (v1, 4) V2 (v3, 6) 5 V5 1 4 7 3 V2 3 V1 1 V7 (v6, 10) (v1, 3) 6 5 1 3 7 V6 (v5, 7) V4 (v1, 5) 最短路径：V1→V3→V5→V6→V7 最短路L=10 6、（ 15 分） 解：此问题可归结为Ｍ／Ｍ／１／７的模型，单位时间为小时 ??4,??5,?????0.8,K?7 第 22 页 共 26 页

（1）患者无须等待的概率： p0?1?0.81?0.88?0.2403； （2）门诊部内患者平均数： 0.88?0.88L???2.38781?0.81?0.8（人） （3）有效到达率： ????(1?P7)?4?(1?L2.387?0.6283.8 1?0.81?0.88?0.87)?3.8； （4）患者在门诊部逗留时间的平均值： W????=37.7(分钟) （5）患者因坐满而自动离去 P7? 1??1??8?7?0.0503?5.03% 六、建模题( 共 1 小题，共 15分) 1、（15 分） 解：设xi?1表示第i门课程选修，xi?0表示第i门课程不选 (1) minZ??xi

i?19 (2) x1?x2?x3?x4?x5?2 x3?x5?x6?x8?x9?3 x4?x6?x7?x9?2 (3) x3?x1,x3?x2 x4?x7 x5?x1,x5?x2 x6?x7 x9?x1,x9?x2 x8?x5 第 22 页 共 26 页

：码号证考 准题 写 要 不 内 线 封 密 ：业专考报 ：名姓生考

2020年全国硕士研究生招生考试初试自命题试题 （ A 卷) 科目代码： 817 科目名称： 运筹学

注意：所有答题内容必须写在答题纸上，写在试题或草稿纸上的一律无效；考完后试题随答题纸交回。 一、选择题(共 5 小题，每小题 2 分，共 10 分) 1、（2分）有m个产地n个销地的平衡运输问题模型具有特征（ ） A．有mn个变量m+n个约束 B．有m+n个变量mn个约束 C．有mn个变量m+n－1约束 D．有m+n－1个基变量，mn－m－n－1个非基变量 2、（2分）一个网络图的最大可行流 （ ） A. 是唯一存在的； B. 可能不唯一； C.可能不存在； D. 一定有多个 3、（2分）若线性规划问题的最优解同时在可行解域的两个顶点处达到，那么该线性规划问题最优解为（ ） A.两个 B.零个 C.无穷多个 D.有限多个 4、（2分）若运输问题已求得最优解，此时所求出的检验数一定是全部（ ） A、小于或等于零 B．大于零 C．小于零 D．大于或等于零 5、（2分）关于动态规划问题的下列命题中错误的是（ ） A、动态规划分阶段顺序不同，则结果不同 B、状态对决策有影响 C、动态规划中，定义状态时应保证在各个阶段中所做决策的相对性 D、动态规划的求解过程都可以用列表形式实现 第 22 页 共 26 页

二、名词解释(共 5 小题，每小题 2 分，共 10 分) 1、（ 2 分） 最小支撑树: 2、（ 2 分）最大流： 3、（ 2 分）饱和弧： 4、（ 2 分）零流弧： 5、（ 2分）线性规划标准型： 三、填空题(共 5 小题，每小题 3 分，共 15 分) 1、（ 3 分）用大M法求目标函数为极小值的线性规划问题时，引入的人工变量在目标函数中的系数应为（ ）。 2、（ 3 分）在单纯形迭代中，选出基变量时应遵循（ ）法则。 3、（ 3 分）若某种资源的影子价格等于k。在其他条件不变的情况下(假设原问题最优基不变)，当该种资源增加3个单位时。相应的目标函数值将增加（ ） 。 4、（ 3 分）在对偶单纯形法迭代中，若某<0，且所有的原问题（ ）。 ≥0 (j=1，2，…n)，则5、（ 3 分）已知最优基 ，CB=（4，5)，则对偶问题的最优解是（ ）四、判断题并改错 (共5 小题，每小题 2 分，共 10 分，对的打√，错的打×) 1、（ 2 分）增广链中，所有反向弧均为非饱和弧 2、（ 2 分）人工变量是人为添加的使约束条件从不等式变为等式的变量。 3、（ 2 分）单纯形表中，基矩阵的逆矩阵在松弛变量或剩余变量对应的系数列向量处取得。 4、（ 2 分）运输问题的基本可行解在运输表中可能包含闭回路。 5、（ 2 分）排队系统中，顾客等待时间的分布不受排队服务规则的影响。 五、计算题( 共 7小题，共 90分) 1、（ 15 分）用单纯形表求解下列线性规划问题 第 22 页 共 26 页

2、（ 10 分）已知运输问题的调运和运价表如下，求最优调运方案和最小费用。 地销产地1 2 3 销量 甲 10 16 5 5 乙 6 0 4 2 丙 7 5 10 4 丁 12 9 10 6 产量 4 9 4 3、（ 10 分）有四项工作要甲、乙、丙、丁四个人去完成．每项工作只允 许一人去完成。每个人只完成其中一项工作，已知每个人完成各项工作的时间如下表。问应指派每个人完成哪项工作，使总的消耗时间最少? 工作 人 甲 乙 丙 丁 I 15 19 6 19 Ⅱ 18 23 7 21 Ⅲ 2l 22 16 23 Ⅳ 24 18 19 17 4、（ 15 分）用割平面法求解下列整数规划问题 5、（ 10分） 求从V1到V8的最短路 第 22 页 共 26 页

6、（ 15 分）求下图的最小费用最大流，其中弧旁边的数字为容量和单位流量费用。 7、（ 15 分）某排队系统只有1名服务员，平均每小时有4名顾客到达，到达过程为Poisson流，，服务时间服从负指数分布，平均需6分钟，由于场地，系统内最多不超过3名顾客，求： （1）系统内没有顾客的概率； （2）系统内顾客的平均数； （3）排队等待服务的顾客数； （4）顾客在系统中的平均花费时间； （5）顾客平均排队时间。 六、建模题，不用求解( 共 1 小题，共 15分) 1、,需要某种物资的数量分别为d1,d1,（ 15 分）有n个城市｛1,2,…,n｝,dn，现计划要建造m座工厂。假设在城市j建厂，规模为Sj（指该厂的产量规模），而投资为Fj。从城市i到城市j的单位运价为Cij，问m个工厂应设在何处，使得既能满足需要，又使总投资最省。 第 22 页 共 26 页

：码号证考 准题 写 要 不 内 线 封 密 ：业专考报 ：名姓生考

2020年全国硕士研究生招生考试初试自命题试题 参（ A 卷) 科目代码： 817 科目名称： 运筹学

注意：所有答题内容必须写在答题纸上，写在试题或草稿纸上的一律无效；考完后试题随答题纸交回。 一、选择题(共 5 小题，每小题 2 分，共 10 分) 1、（2分）A 2、（2分）B 3、（2分）C 4、（2分）D 5、（2分）A 二、名词解释(共 5 小题，每小题 2 分，共 10 分) 1、（ 2 分）设G=（V，E）是一个无向连通网，生成树上各边的权值之和为该生成树的代价，在G的所有生成树中，代价最小的生成树就称为最小支撑树 2、（ 2 分）网络图中流量最大的可行流 3、（ 2 分）流量达到容量的弧 4、（ 2 分）流量为0的弧 5、（ 2分）满足四个条件：(1)目标函数为极大化类型；(2)所有的约束条件都是等式；(3)所数学规划有约束方程右端的常数都是非负的；(4)所有决策变量都是非负的 三、填空题(共 5 小题，每小题 3 分，共 15 分) 1、（ 3 分）M。 2、（ 3 分）最小比值θ 3、（ 3 分）3k 4、（ 3 分）无可行解 第 22 页 共 26 页

5、（ 3 分）（13，-3）T 四、判断题并改错 (共5 小题，每小题 2 分，共 10 分) 1、（ 2 分）错误，为非零流弧 2、（ 2 分）使大于等于的式子变为小于等于的变量 3、（ 2 分）错误，在松弛变量处取得 4、（ 2 分）错误，不含闭回路 5、（ 2 分）错误，受到排队规则和服务规则的影响 五、计算题( 共 7小题，共 90分) 1、（ 15 分） （得分标准：化为规范型得2分，单纯形表正确得10分，最后结果得3分。） 第 22 页 共 26 页

2、（ 10 分） （评分标准：最优调运方案（5分），算出最终最小总费用（5分）。） 3、（ 10 分）（评分标准：画图二得5分，画出图三得10分，写最终方案得满分15分） 。 4、（ 15 分） 第 22 页 共 26 页

（评分标准：求解第一个单纯形表得5分，写出割平面方程得5分，最终求解单纯形表得5分） 5、（ 10分） （得分标准：在图中用标号法标号正确得5分；用反向追踪法得出最短路得3分；求出最短路长得2分。） 第 22 页 共 26 页

6、 （得分标准：一个流量图和一个赋权有向图得5分。） 第 22 页 共 26 页

7、（ 15 分）解：单位时间为小时，??4,??10,?????0.4,K?3； （1）系统内没有顾客的概率：p0 （2）系统内顾客的平均数： ?1??1??4?1?0.41?0.44?0.616； 1??K?1 （3）排队等待服务的顾客数：Lq?L?(1?p0)?0.562?0.384?0.178（人）； 1?? （4）顾客在系统中的平均花费时间： L???(K?1)?K?10.44?0.44； ???0.562（人）41?0.41?0.40.562?0.146?8.8（分钟） 3?(1??p0)3.842 （5）顾客平均排队时间：Wq?W?1??0.146?0.1?0.046?2.8（分钟）。 W?L?（得分标准：每小题3分。） 六、建模题( 共 1 小题，共 15分) 解：设 设xij?1,若有一个工厂建在城市i，yi??城市i不建厂。?0, 为从城市i运到城市j的物资的数量，则 ??Cx?Fy??ijij?ii?i?i,j?n???xij?Siyi??(i?1,2,,n)j?1?n?xij?dj(j?1,2,,n)???i?1?n?yi?m??i?1?y?{0,1},x?0??(i,j?1,2,,n)ij?i mins..t 第 22 页 共 26 页