《2022年运筹学学年期末考试题A卷及答案.docx》由会员分享，可在线阅读，更多相关《2022年运筹学学年期末考试题A卷及答案.docx（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选学习资料 - - - - - - - - - 运筹学 2022 年学年其次学期 期末考试题 a 卷留意事项：1、答题前,考生务必将自己的、班级填写在答题卡上；2、答案用钢笔或圆珠笔写在答题卡上,答在试卷上不给分；3、考试终止,将试卷和答题卡一并交回；一、 单项挑选题 每题 1 分,共 10 分 1：在下面的数学模型中,属于线性规划模型的为X2Y2minS,2XYmaxS4 XYminS3XYmaxSA.t.sXY3B .t.s2XY1C .t.sXY2D.t.sXY3X,Y0X,Y0X,Y0XY02线性规划问题假设有最优解,就肯定可以在可行域的上到达；A内点 B顶点 C外点 D几何点3：在
2、线性规划模型中,没有非负约束的变量称为人工变量A余外变量 B放松变量 C.自由变量 D4：假设线性规划问题的最优解同时在可行解域的两个顶点处到达,那么该线性规划问题最名师归纳总结 优解为m+n 行第 1 页,共 8 页A.两个B.零个C.无穷多个D.有限多个5：原问题与对偶问题的最优相同；A解B目标值C 解结构D解的重量个数6：假设原问题中ix 为自由变量,那么对偶问题中的第i 个约束肯定为A等式约束 B“ ”型约束 C“ ”约束 D无法确定7：假设运输问题已求得最优解,此时所求出的检验数肯定是全部A小于或等于零B大于零C小于零D大于或等于零8：对于 m 个发点、 n 个收点的运输问题,表达错
3、误的选项是 A该问题的系数矩阵有m n 列B该问题的系数矩阵有- - - - - - -精选学习资料 - - - - - - - - - C该问题的系数矩阵的秩必为m+n-1 D该问题的最优解必唯独9：关于动态规划问题的以下命题中错误的选项是A、动态规划分阶段次序不同,就结果不同B、状态对决策有影响C、动态规划中,定义状态时应保证在各个阶段中所做决策的相对独立性D、动态规划的求解过程都可以用列表形式实现10：假设 P 为网络 G 的一条流量增广链,就P 中全部正向弧都为G 的A对边B饱和边C邻边D不饱和边二、 判定题每题1 分,共 10 分1：图解法和单纯形法虽然求解的形式不同,但从几何上懂得
4、,两者是一样的；2：单纯形法的迭代运算过程是从一个可行解转换到目标函数值更大的另一个可行解；3：一旦一个人工变量在迭代中变为非基变量后,该变量及相应列的数字可以从单纯形表中删除,而不影响运算结果； 4：假设线性规划问题中的b c 值同时发生转变,反映到最终单纯形表中,不会显现原问题与对偶问题均为非可行基的情形； 5：假设线性规划的原问题有无穷多最优解,就其对偶问题也肯定具有无穷多最优解； 6：运输问题的表上作业法实质上就是求解运输问题的单纯形法； 7：对于动态规划问题,应用顺推或逆推解法可能会得出不同的最优解；8：动态规划的基本方程是将一个多阶段的决策问题转化为一系列具有递推关系的单阶段的决策
5、问题；9：图论中的图不仅反映了讨论对象之间的关系,而且是真实图形的写照,因而对图中点与点的相对位置、点与点连线的长短曲直等都要严格留意；10：网络最短路线问题和最短树问题实质上是一个问题；三、 填空题每空 1 分,共 15 分1：线性规划中, 满意非负条件的基本解称为 _基本可行解 _,对应的基称为 _可行基_；2：线性规划的目标函数的系数是其对偶问题的_右端常数 _；而假设线性规划为最大化问题,就对偶问题为_最小化问题 _；_不含闭回路 _；3：在运输问题模型中,mn1 个变量构成基变量的充要条件是4：动态规划方法的步骤可以总结为：逆序求解_最优目标函数 _,次序求 _最优策略、 _、_最优
6、路线 _和_最优目标函数值 _；5：工程路线问题也称为最短路问题,依据问题的不同分为定步数问题和不定步数问题；对不定步数问题,用迭代法求解,有 _函数 _迭代法和 _策略 _迭代法两种方法；6：在图论方法中,通常用 _点_表示人们讨论的对象,用 _边_表示对象之间的某种联系；7：一个 _无圈 _且_连通 _的图称为树；四、运算题每题 15 分, 45 分1：考虑线性规划问题：名师归纳总结 - - - - - - -第 2 页,共 8 页精选学习资料 - - - - - - - - - maxz2x 14x 23 x 3s t . .3 x 14x 2x 32x 36 02x 1x 22x 34
7、0x 13x 22x 380x x 2,0a：写出其对偶问题；b：用单纯形方法求解原问题；c：用对偶单纯形方法求解其对偶问题；d：比较 b c运算结果；1：解a：其对偶问题为minz60y 140y 280y 3s t . .3y 12y 2y 324y 1y 2y 342y 12y22y 33y 1,y 2,y 30-3 分b：用单纯形方法求解原问题时每步迭代结果：原问题解 第一步0,0,0,60,40,80其次步0,15,0,0,25,35第三步0,20/3,50/3,0,0,80/3-5 分c：用对偶单纯形方法求解对偶问题时每步迭代结果：对偶问题问题解 第一步0,0,0,-2,-4,-3
8、其次步1,0,0, 1,0,-1第三步5/6, 2/3,0,11/6,0,0-5 分d：对偶问题的实质是将单纯形法应用于对偶问题的求解,又对偶问题的对偶即原问题,因 此b、c的运算结果完全相同；-2 分 2：某公司准备在三个不同的地区设置4 个销售点,依据市场猜测部门的估量,在不同的地区设置不同数量的销售店,每月可得到的利润如下表所示；试问各个地区应如何设置销售店,才能使每月获得的总利润最大？其值是多少？地利区销售店0 润1 2 3 4 名师归纳总结 - - - - - - -第 3 页,共 8 页精选学习资料 - - - - - - - - - 1 0 2 16 3 25 30 32 0 1
9、2 17 21 22 0 10 14 16 17 2：解 该问题可以作为三段决策问题,对 1, 2,3 地区分别设置销售店形成 1,2,3 三个阶段；x 表示给地区 k 设置销售店时拥有安排的数量,u 表示给地区k 设置销售店的数量；状 态 转 移 方 程 为 ：xk1x kkuk； 阶 段 效 应 题 中 表 所 示 ； 目 标 函 数 ：3guk表示在k 地区设置u 个销售店时的收益；maxRgkuk； 其中k1- 3 分第一逆序求解条件最有目标函数值集合和条件最有决策集合：k3时,0x 34 ,0u 3x 3,xf 3x 3max u 3g3 u 3f4x 4, 其中f440于是有：f3
10、f32g32f30g300,u 300, , , f31g3110,u 31114,u 223g3316,u 33, 4.-f34g3417,u 4-3 分名师归纳总结 k2时,0x 24 ,0u 2x 2,f2x 20 max u 2 x 2g 2 u 2f3x 3, 第 4 页,共 8 页- - - - - - -精选学习资料 - - - - - - - - - 于是有：f200 max u 2 0g2u2g2f3x 3f30,u200, 2or3. f21max 0 u 2 1g2u2f3x 312,u211, f220 max u 2 2g2u2f3x 322,u221, f230 m
11、ax u 2 3g2u2f3x 327,u232, f24max 0 u 2 4u 2x 331,u24- 3 分kf3 时,x 14,10u 1f2x 124,于是有：2.- 3 分140 max u 1 4gu 1x47,u 14因此, 最优的安排方案所能得到的最大利润位 出得：47,安排方案可由运算结果反向查u*142,u*221,u*311；即为地区 1 设置两个销售店,地区 2 设置 1 各销售店,地区3 设置 1 个销售店；3：对以下图中的网络,分别用破圈法和生长法求最短树；3：解 破圈法1：取圈 v v 2 , v v ,去掉边 v v 3 ；2：取圈 v 2 , v 4 , v
12、 3 , v ,去掉边 v 2 , v 4 ；3：取圈 v 2 , v 3 , v v ,去掉边 v 2 , v 5 ；4：取圈 v 3 , v 4 , v 5 , v 5 , v ,去掉边 v v 4 ；在图中已无圈, 此时,p 6,而 q p 1 5,因此所得的是最短树；结果如以下图,其树的总长度为 12；.- 6分名师归纳总结 - - - - - - -第 5 页,共 8 页精选学习资料 - - - - - - - - - .- 3 分生长法依据生长法的基本原理,得以下运算表2v3vv4v56vS 12 6 8 9 1 3 v23 8 9 S 25 3 v35 3 S 3v5S 45 1
13、 v63 .- 6 分3 S 5据此也得到与破圈法相同的最短树；五、简答题 每题 10 分,共 20 分1试述单纯形法的运算步骤,并说明如何在单纯形表上判定问题是具有唯独最优解、无穷多最优解和无有限最优解；解： 1：单纯形法的运算步骤第一步：找出初始可行解,建立初始单纯形表；名师归纳总结 其次步：判定最优,检验各非基变量jx的检验数j1 C B P B jC ；第 6 页,共 8 页假设全部的j0,就基 B 为最优基,相应的基可行解即为基本最优解,运算停止；- - - - - - -精选学习资料 - - - - - - - - - 假设全部的检验数j0,又存在某个非基变量的检验数全部的k0,就
14、线性规划问题有无穷多最优解；假设有某个非基变量的检验数j0,并且所对应的列向量的全部重量都非正,就该线性规划问题的目标函数值无上界,既无界解,停止运算；第三步：换基迭代当存在k0,选x 进基来改善目标函数；假设检验数大于0 的非基变量不止一个,就可以任选其中之一来作为进基变量；进基变量x 确定后,按最小比值原就挑选出基变量rx；假设比值最小的不止一个,选择其中之一出基；做主元变换；反复进行上述过程就可以找到最优解或判定出没有有限最优解；- 3 分 2 简述最小费用最大流问题的提法以及用对偶法求解最小费用最大流的原理和步骤；解： 2：最大流问题就是在肯定条件下,要求流过网络的物流、能量流或信息流
15、等流量最大的问题；假如已知流过弧 v v j 的单位流量要发生 ijc的费用,要求使总费用为最小的最大流流量安排方法；即在上述最大流问题上仍应增加关于费用的目标：min x c ；这种问题称为最小费用最大流问题；模型可以描述为：min x c ijmax ff i sx ij x ji 0 i s ts t . . j jf i t0 x ij b ij采纳对偶法求解最大流最小费用问题,其原理为： 用福德富克逊算法求出网络的最大流量,然后用 Ford 算法找出从起点 v 到终点 tv的最短增广链；在该增广链上,找出最大调整量,并调整流量,得到一个可行流；就此可行流的费用最小；假如此时流量等于最
16、大流量,就目前的流就是最小费用最大流,否就应连续调整；对偶法的步骤归纳如下：第 0 步：用最大流方法找出网络最大流量fmax,并以 0 流作为初始可行流；第一步：对于当前可行流,绘制其扩展费用网络图；名师归纳总结 其次步：用Ford 算法求出扩展费用网络图中从v 到tv 的最短路；第 7 页,共 8 页- - - - - - -精选学习资料 - - - - - - - - - 第三步：在最短路线对应的原网络中的增广链上,调整流量,得到新的可行流；第四步：绘制可行流图；假设可行流的流量等于最大流量fmax,就已找到最小费用最大流,算法终止；否就从第一步开头重复上述过程名师归纳总结 - - - - - - -第 8 页,共 8 页