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

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

1、运筹学运筹学 20152015 年学年第二学期年学年第二学期期末考试题期末考试题a a 卷卷注意事项：注意事项：1 1、答题前，考生务必将自己的、班级填写在答题卡上。、答题前，考生务必将自己的、班级填写在答题卡上。2 2、答案用钢笔或圆珠笔写在答题卡上，答在试卷上不给分。、答案用钢笔或圆珠笔写在答题卡上，答在试卷上不给分。3 3、考试结束，将试卷和答题卡一并交回。、考试结束，将试卷和答题卡一并交回。一、一、 单项选择题单项选择题( (每题每题 1 1 分，共分，共 1010 分分) )1：在下面的数学模型中，属于线性规划模型的为maxS 4X YminA.s.t.XY 3B.s.t.X,Y 0

2、maxS X2 Y2S 3X Ymin2X Y 1C.s.t.X Y 2D.s.t.X,Y 0X,Y 0S 2XYX Y 3X,Y 02线性规划问题假设有最优解，则一定可以在可行域的 上到达。A内点 B顶点 C外点 D几何点3：在线性规划模型中，没有非负约束的变量称为 A多余变量 B松弛变量 C.自由变量 D人工变量4：假设线性规划问题的最优解同时在可行解域的两个顶点处到达，那么该线性规划问题最优解为A.两个B.零个C.无穷多个D.有限多个5：原问题与对偶问题的最优相同。A解B目标值C 解结构D解的分量个数6：假设原问题中xi为自由变量，那么对偶问题中的第i个约束一定为 A等式约束 B“”型约

3、束 C“”约束 D无法确定7：假设运输问题已求得最优解， 此时所求出的检验数一定是全部 A小于或等于零B大于零C小于零D大于或等于零8：对于 m 个发点、n 个收点的运输问题，表达错误的选项是()A该问题的系数矩阵有mn 列B该问题的系数矩阵有m+n 行C该问题的系数矩阵的秩必为m+n-1D该问题的最优解必唯一9：关于动态规划问题的以下命题中错误的选项是A、动态规划分阶段顺序不同，则结果不同B、状态对决策有影响C、动态规划中，定义状态时应保证在各个阶段中所做决策的相对独立性D、动态规划的求解过程都可以用列表形式实现10：假设 P 为网络 G 的一条流量增广链，则P 中所有正向弧都为G 的A对边

4、B饱和边C邻边D不饱和边二、二、 判断题每题判断题每题 1 1 分，共分，共 1010 分分1：图解法和单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。 2： 单纯形法的迭代计算过程是从一个可行解转换到目标函数值更大的另一个可行解。 3：一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。 4：假设线性规划问题中的bi, cj值同时发生改变，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行基的情况。 5：假设线性规划的原问题有无穷多最优解， 则其对偶问题也一定具有无穷多最优解。 6：运输问题的表上作业法实质上就是求解运输问题的单

5、纯形法。 7：对于动态规划问题，应用顺推或逆推解法可能会得出不同的最优解。 8：动态规划的基本方程是将一个多阶段的决策问题转化为一系列具有递推关系的单阶段的决策问题。 9：图论中的图不仅反映了研究对象之间的关系，而且是真实图形的写照，因而对图中点与点的相对位置、点与点连线的长短曲直等都要严格注意。 10：网络最短路线问题和最短树问题实质上是一个问题。 三、三、 填空题每空填空题每空 1 1 分，共分，共 1515 分分1：线性规划中，满足非负条件的基本解称为_基本可行解_，对应的基称为_可行基_。2：线性规划的目标函数的系数是其对偶问题的_右端常数_；而假设线性规划为最大化问题，则对偶问题为_

6、最小化问题_。3：在运输问题模型中，m n1个变量构成基变量的充要条件是_不含闭回路_。4：动态规划方法的步骤可以总结为：逆序求解_最优目标函数_，顺序求_最优策略、_、_最优路线_和_最优目标函数值_。5：工程路线问题也称为最短路问题，根据问题的不同分为定步数问题和不定步数问题；对不定步数问题，用迭代法求解，有_函数_迭代法和_策略_迭代法两种方法。6：在图论方法中，通常用_点_表示人们研究的对象，用_边_表示对象之间的某种联系。7：一个_无圈_且_连通_的图称为树。四、计算题每题四、计算题每题 1515 分，分，4545 分分1：考虑线性规划问题：max z 2x1 4x23x33x1 4

7、x2 2x3 602x x 2x 40123s.t.x1 3x2 2x3 80 x1,x2,x3 0a ：写出其对偶问题；b ：用单纯形方法求解原问题；c ：用对偶单纯形方法求解其对偶问题；d ：比较b c计算结果。1：解a ：其对偶问题为min z 60y1 40y280y33y1 2y2y3 24y y y 4123s.t.2y1 2y2 2y3 3y1, y2, y3 0- 3 分b ：用单纯形方法求解原问题时每步迭代结果：第一步第二步第三步原问题解0，0，0，60，40，800，15，0，0，25，350，20/3，50/3，0，0，80/3- 5 分c ：用对偶单纯形方法求解对偶问题

8、时每步迭代结果：第一步第二步第三步对偶问题问题解0，0，0，-2，-4，-31，0，0，1，0，-15/6，2/3，0，11/6，0，0- 5 分d ：对偶问题的实质是将单纯形法应用于对偶问题的求解， 又对偶问题的对偶即原问题， 因此b 、 c的计算结果完全相同。-(2 分)2：某公司打算在三个不同的地区设置4 个销售点，根据市场预测部门的估计，在不同的地区设置不同数量的销售店， 每月可得到的利润如下表所示。 试问各个地区应如何设置销售店，才能使每月获得的总利润最大？其值是多少？利地销售店01234润区1230162530320121721220101416172：解该问题可以作为三段决策问题

9、，对1，2，3 地区分别设置销售店形成1，2，3 三个阶段。xk表示给地区 k 设置销售店时拥有分配的数量，uk表示给地区k 设置销售店的数量。状态转移方程为：xk1 xkuk；阶段效应题中表所示；目标函数：max R gk(uk)； 其中gk(uk)表示在 k 地区设置uk个销售店时的收益；k13-3 分首先逆序求解条件最有目标函数值集合和条件最有决策集合：k 3时，0 x3 4, 0 u3 x3,f3(x3) maxg3(u3) f4(x4)， 其中u3f4(x4) 0于是有：f3(0) g3(0) 0,f3(1) g3(1)10,u3(0) 0,u3(1)1,f3(2) g3(2) 14

10、,f3(3) g3(3) 16,f3(4) g3(4) 17,-3 分u3(2) 2u3(3) 3,u3(4) 4.-k 2时，0 x2 4, 0 u2 x2,f2(x2) maxg2(u2) f3(x3),0u2x2于是有：f2(0) maxg2(u2) f3(x3) 0, u2(0) 0,0u20f2(1) maxg2(u2) f3(x3)12, u2(1)1,0u21f2(2) maxg2(u2) f3(x3) 22, u2(2) 1,0u22f2(3) maxg2(u2) f3(x3) 27, u2(3) 2,0u23f2(4) maxg2(u2) f3(x3) 31, u2(4) 2

11、 or 3.0u24-3 分k 3时，x1 4, 0 u1 x1 4,于是有：f1(4) maxg1(u1) f2(x2) 47, u1(4) 2.-3 分0u14因此，最优的分配方案所能得到的最大利润位47，分配方案可由计算结果反向查出得：u*1(4) 2, u*2(2) 1, u*3(1)1。 即为地区 1 设置两个销售店，地区 2 设置 1 各销售店，地区 3 设置 1 个销售店。3：对以下图中的网络，分别用破圈法和生长法求最短树。3：解破圈法1 ：取圈3 ：取圈v1,v2,v3,v1v2,v3,v5,v2，去掉边v1,v3。 2 ：取圈v2,v4,v3,v2，去掉边v2,v4。，去掉边

12、v2,v5。 4 ：取圈v3,v4,v5,v5,v3，去掉边v3,v4在图中已无圈， 此时，p 6，而q p 1 5，因此所得的是最短树。 结果如以下图，其树的总长度为 12。.-6分生长法根据生长法的基本原理，得以下计算表.-3 分v2v3v4v5v62633S1v28855993311S2v3S3v5533S4v6S5据此也得到与破圈法相同的最短树。.-6 分五、简答题五、简答题( (每题每题 1010 分，共分，共 2020 分分) )1 1试述单纯形法的计算步骤，并说明如何在单纯形表上判断问题是具有唯一最优解、无试述单纯形法的计算步骤，并说明如何在单纯形表上判断问题是具有唯一最优解、无

13、穷多最优解和无有限最优解。穷多最优解和无有限最优解。解：1：单纯形法的计算步骤第一步：找出初始可行解，建立初始单纯形表。第二步：判断最优，检验各非基变量假设所有的xj的检验数j CBB1PjCj。j 0，则基 B 为最优基，相应的基可行解即为基本最优解，计算停止。假设所有的检验数j 0，又存在某个非基变量的检验数所有的k 0，则线性规划问题有无穷多最优解。假设有某个非基变量的检验数j 0，并且所对应的列向量的全部分量都非正，则该线性规划问题的目标函数值无上界，既无界解，停止计算。第三步：换基迭代当存在k 0，选xk进基来改善目标函数。假设检验数大于0 的非基变量不止一个，xkxr则可以任选其中

14、之一来作为进基变量。进基变量确定后，按最小比值原则选择出基变量。假设比值最小的不止一个，选择其中之一出基。做主元变换。反复进行上述过程就可以找到最优解或判断出没有有限最优解。-3 分 2 2简述最小费用最大流问题的提法以及用对偶法求解最小费用最大流的原理和步骤。简述最小费用最大流问题的提法以及用对偶法求解最小费用最大流的原理和步骤。解：2：最大流问题就是在一定条件下，要求流过网络的物流、能量流或信息流等流量最大的问题。如果已知流过弧(vi,vj)的单位流量要发生cij的费用，要求使总费用为最小的最大流流量分配方法。即在上述最大流问题上还应增加关于费用的目标：种问题称为最小费用最大流问题。模型可

15、以描述为：minxijcij。这minxijcijmax f fxijxji0s.t.jj f0 xij bijvsvti si s, ti t采用对偶法求解最大流最小费用问题， 其原理为： 用福德富克逊算法求出网络的最大流量，然后用 Ford 算法找出从起点到终点的最短增广链。在该增广链上，找出最大调整量，并调整流量，得到一个可行流。则此可行流的费用最小。如果此时流量等于最大流量，则目前的流就是最小费用最大流，否则应继续调整。对偶法的步骤归纳如下：第 0 步：用最大流方法找出网络最大流量fmax，并以 0 流作为初始可行流。第一步：对于当前可行流，绘制其扩展费用网络图。第二步：用 Ford 算法求出扩展费用网络图中从vs到vt的最短路。第三步：在最短路线对应的原网络中的增广链上，调整流量，得到新的可行流。第四步：绘制可行流图。假设可行流的流量等于最大流量大流，算法结束；否则从第一步开始重复上述过程fmax，则已找到最小费用最