2022年运筹学2015学年期末考试题A卷及答案 .pdf

《2022年运筹学2015学年期末考试题A卷及答案 .pdf》由会员分享，可在线阅读，更多相关《2022年运筹学2015学年期末考试题A卷及答案 .pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运筹学 2015 年学年第二学期期末考试题 a 卷注意事项：1、答题前，考生务必将自己的、班级填写在答题卡上。2、答案用钢笔或圆珠笔写在答题卡上，答在试卷上不给分。3、考试结束，将试卷和答题卡一并交回。一、 单项选择题 ( 每题 1 分，共 10 分) 1：在下面的数学模型中，属于线性规划模型的为0Y,X3XY. t . sYX4Smax.A0Y,X1YX2. t . sYX3Smin.B0Y,X2YX. t . sYXSmax.C220Y,X3YX. t . sXY2Smin.D2线性规划问题假设有最优解，则一定可以在可行域的上到达。A内点 B顶点 C外点 D几何点3：在线性规划模型中，没有

2、非负约束的变量称为A多余变量 B松弛变量 C.自由变量 D人工变量4：假设线性规划问题的最优解同时在可行解域的两个顶点处到达，那么该线性规划问题最优解为A.两个B.零个C.无穷多个D.有限多个5：原问题与对偶问题的最优相同。A解B目标值C 解结构D解的分量个数6：假设原问题中ix为自由变量，那么对偶问题中的第i个约束一定为A等式约束 B“”型约束 C“”约束 D无法确定7：假设运输问题已求得最优解，此时所求出的检验数一定是全部A小于或等于零B大于零C小于零D大于或等于零8：对于 m 个发点、 n 个收点的运输问题，表达错误的选项是( ) A该问题的系数矩阵有mn 列B该问题的系数矩阵有m+n

3、行精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 8 页C该问题的系数矩阵的秩必为m+n-1 D该问题的最优解必唯一9：关于动态规划问题的以下命题中错误的选项是A、动态规划分阶段顺序不同，则结果不同B、状态对决策有影响C、动态规划中，定义状态时应保证在各个阶段中所做决策的相对独立性D、动态规划的求解过程都可以用列表形式实现10：假设 P 为网络 G 的一条流量增广链，则P 中所有正向弧都为G 的A对边B饱和边C邻边D不饱和边二、 判断题每题1 分，共 10 分1：图解法和单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。2：单纯

4、形法的迭代计算过程是从一个可行解转换到目标函数值更大的另一个可行解。3：一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。 4：假设线性规划问题中的,ijb c值同时发生改变，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行基的情况。5：假设线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解。6：运输问题的表上作业法实质上就是求解运输问题的单纯形法。7：对于动态规划问题，应用顺推或逆推解法可能会得出不同的最优解。8：动态规划的基本方程是将一个多阶段的决策问题转化为一系列具有递推关系的单阶段的决策问题。9：图论中的图不仅反

5、映了研究对象之间的关系，而且是真实图形的写照，因而对图中点与点的相对位置、点与点连线的长短曲直等都要严格注意。10：网络最短路线问题和最短树问题实质上是一个问题。三、 填空题每空1 分，共 15 分1：线性规划中， 满足非负条件的基本解称为_基本可行解 _，对应的基称为_可行基_。2：线性规划的目标函数的系数是其对偶问题的_右端常数 _；而假设线性规划为最大化问题，则对偶问题为_最小化问题 _。3：在运输问题模型中，1mn个变量构成基变量的充要条件是_不含闭回路 _。4：动态规划方法的步骤可以总结为：逆序求解_最优目标函数 _，顺序求 _最优策略、 _、_最优路线 _和_最优目标函数值_。5：

6、工程路线问题也称为最短路问题，根据问题的不同分为定步数问题和不定步数问题；对不定步数问题，用迭代法求解，有_函数 _迭代法和 _策略 _迭代法两种方法。6：在图论方法中，通常用_点_表示人们研究的对象，用_边_表示对象之间的某种联系。7：一个 _无圈 _且_连通 _的图称为树。四、计算题每题15 分， 45 分1：考虑线性规划问题：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 8 页1231231231231236max2433420408022. .32,0,zxxxxxxxxxs txxxx xxa ：写出其对偶问题；b ：用单纯

7、形方法求解原问题；c ：用对偶单纯形方法求解其对偶问题；d ：比较 b c计算结果。1：解a ：其对偶问题为123123123123123min604080324. .2222,3,40zyyyyyyyyys tyyyyyy-3 分b ：用单纯形方法求解原问题时每步迭代结果：原问题解第一步第二步第三步0，0，0，60，40，800，15，0，0，25，350，20/3，50/3，0，0，80/3-5 分c ：用对偶单纯形方法求解对偶问题时每步迭代结果：对偶问题问题解第一步第二步第三步0，0，0，-2，-4，-31，0，0， 1，0，-15/6， 2/3，0，11/6，0，0-5 分d ：对偶问

8、题的实质是将单纯形法应用于对偶问题的求解，又对偶问题的对偶即原问题，因此b 、 c的计算结果完全相同。-(2 分) 2：某公司打算在三个不同的地区设置4 个销售点，根据市场预测部门的估计，在不同的地区设置不同数量的销售店，每月可得到的利润如下表所示。试问各个地区应如何设置销售店，才能使每月获得的总利润最大？其值是多少？0 1 2 3 4 销售店利润地区精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 8 页1 2 30 16 25 30 32 0 12 17 21 22 0 10 14 16 17 2：解该问题可以作为三段决策问题，对1，

9、 2，3 地区分别设置销售店形成1，2，3 三个阶段。kx表示给地区k 设置销售店时拥有分配的数量，ku表示给地区k 设置销售店的数量。状 态 转 移 方 程 为 ：1kkkxxu； 阶 段 效 应 题 中 表 所 示 ； 目 标 函 数 ：31max()kkkRgu； 其中()kkgu表示在k 地区设置ku个销售店时的收益；- 3 分首先逆序求解条件最有目标函数值集合和条件最有决策集合：3k时，333333334400()max(4,)(,)uxgxfuxxuf， 其中44()0fx于是有：333(0)(0)0,(0)0fgu, 333(1)(1)10,(1)1fgu, 333(2)(2)1

10、4, (2)2fgu, 333(3)(3)16, (3)3fgu, 333(4)(4)17, (4)4fgu.-3 分2k时，22222222233000()max(4)(),uxxgxuxufxf, 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 8 页于是有：222332020(0)max()()0,(0)0ufgufxu, 222022331(1)max()()12,(1)1ufgufxu, 222022332(2)max()()22,(2)1ufgufxu, 222022333(3)max()()27,(3)2ufgufxu,

11、222022334(4)max()()31,(4)23ufgufxuor. - 3 分3k时，111,404,xux于是有：111122014(4)max()()47,(4)2.ugufxuf.- 3 分因此， 最优的分配方案所能得到的最大利润位47，分配方案可由计算结果反向查出得：123*(4)2,(2)1,(1)1uuu。 即为地区1 设置两个销售店，地区 2 设置 1 各销售店，地区3设置 1 个销售店。3：对以下图中的网络，分别用破圈法和生长法求最短树。3：解破圈法1 ：取圈3121,v vv v，去掉边13,v v。 2 ：取圈2432,vvvv，去掉边24,vv。3 ：取圈2352

12、,vvv v，去掉边25,vv。 4 ：取圈34553,vvvvv，去掉边34,v v。在图中已无圈， 此时，6p，而15qp，因此所得的是最短树。结果如以下图，其树的总长度为12。.- 6分精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 8 页.-3 分生长法根据生长法的基本原理，得以下计算表2v3v4v5v6v1S2 6 2v3 8 9 2S3 8 9 3v5 3 3S5 3 5v1 4S5 1 6v3 5S3 据此也得到与破圈法相同的最短树。.- 6 分五、简答题 ( 每题 10 分，共 20 分)1试述单纯形法的计算步骤，并说明

13、如何在单纯形表上判断问题是具有唯一最优解、无穷多最优解和无有限最优解。解： 1：单纯形法的计算步骤第一步：找出初始可行解，建立初始单纯形表。第二步：判断最优，检验各非基变量jx的检验数1jBjjC B PC。假设所有的0j，则基 B 为最优基，相应的基可行解即为基本最优解，计算停止。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 8 页假设所有的检验数0j，又存在某个非基变量的检验数所有的0k，则线性规划问题有无穷多最优解。假设有某个非基变量的检验数0j，并且所对应的列向量的全部分量都非正，则该线性规划问题的目标函数值无上界，既无界解，

14、停止计算。第三步：换基迭代当存在0k，选kx进基来改善目标函数。假设检验数大于0 的非基变量不止一个，则可以任选其中之一来作为进基变量。进基变量kx确定后，按最小比值原则选择出基变量rx。假设比值最小的不止一个，选择其中之一出基。做主元变换。反复进行上述过程就可以找到最优解或判断出没有有限最优解。- 3 分 2 简述最小费用最大流问题的提法以及用对偶法求解最小费用最大流的原理和步骤。解： 2：最大流问题就是在一定条件下，要求流过网络的物流、能量流或信息流等流量最大的问题。如果已知流过弧(,)ijv v的单位流量要发生ijc的费用，要求使总费用为最小的最大流流量分配方法。即在上述最大流问题上还应

15、增加关于费用的目标：minijijx c。这种问题称为最小费用最大流问题。模型可以描述为：minmax0,. .0ijijijjiijjijjx cffisxxis ts tfixbt采用对偶法求解最大流最小费用问题，其原理为： 用福德富克逊算法求出网络的最大流量，然后用Ford 算法找出从起点sv到终点tv的最短增广链。在该增广链上，找出最大调整量，并调整流量，得到一个可行流。则此可行流的费用最小。如果此时流量等于最大流量，则目前的流就是最小费用最大流，否则应继续调整。对偶法的步骤归纳如下：第 0 步：用最大流方法找出网络最大流量maxf，并以 0 流作为初始可行流。第一步：对于当前可行流，绘制其扩展费用网络图。第二步：用Ford 算法求出扩展费用网络图中从sv到tv的最短路。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 8 页第三步：在最短路线对应的原网络中的增广链上，调整流量，得到新的可行流。第四步：绘制可行流图。假设可行流的流量等于最大流量maxf，则已找到最小费用最大流，算法结束；否则从第一步开始重复上述过程精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 8 页