运筹学学年期末考试题a卷及答案解析

1、WORD格式整理版运筹学2015年学年第二学期期末考试题（a卷）注意事项：1、答题前，考生务必将自己的姓名、班级填写在答题卡上2、答案用钢笔或圆珠笔写在答题卡上，答在试卷上不给分3、考试结束，将试卷和答题卡一并交回。单项选择题（每小题1分，共10分）1在卜面的数学模型中，属于线性规划模型的为（)max S 4X YminS3X Ymax SX2Y2 22min S 2XYA.s.t. XY 3B.s.t. 2X Y 1C. s.t. XY2D.s.t.XY3X,Y0X,Y0X,Y0X,Y02线性规划问题若有最优解，则一定可以在可行域的（）Z大到。A内点B顶点c 外点D几何点3在线性规划模型中，

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

3、数矩阵有mxn列C该问题的系数矩阵的 秩必为9:尖于动态规划问题的下列命题中错误的是（A、动态规 划分阶段顺序不同，则结果不同B、状态对决策有影响B、状态对决策有影响C、动态规划中，定义状态时应保证在各个阶段中所做决策的相对独立性D、动态规划的求解过程都可以用列表形式实现10 ：若P为网络g的一条流量增广链，则P中所有正向弧都为G的（）A 对边 B饱和边C -邻边D不饱和边二、 判断题（每小题1分，共10分）1 ：图解法和单纯形法虽然求解的形式不同，但从几何上理解，两者 是一致的。（厂）2:单纯形法的迭代计算过程是从一个可行解转换到目标函数值更大的另一个可行解。（x ）3:一旦一个人工变量在迭

4、代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计 算结果。（厂）4 :若线性规划问题中的bi,Cj值同时发生改变，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行基的情况。（X）5：若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有 无穷多最优解。（厂）6:运输问题的表上作业法实质上就是求解运输问题的单纯形法。（厂）7:对于动态规划问题，应用顺推或逆推解法可能会得出不同的最优解。（x ）8：动态规划的基本方程是将一个多阶段的决策问题转化为一系列具有递推尖系的单阶段的决策问题。（厂） 9:图论中的图不仅反映了研究对象之间的尖系，而且是真实图形的写照，因而对图

5、中点与点的相对位置、点 与点连线的长短曲直等都要严格注意。（x ） 10：网络最短路线问题和最短树问题实质上是一个问题。（x ）三、填空题（每空1分，共15分）1 :线性规划中，满足非负条件的基本解称为基本可行解，对应的基称为可行基2:线性规划的目标函数的系数是其对偶问题的右端常数 ；而若线性规划为最大化问题则对偶问题为最小化问题。3 :在运输问题模型中，m n 1个变量构成基变量的充要条件是不含闭回路。4 :动态规划方法的步骤可以总结为：逆序求解最优目标函数 ，顺序求最优策略、最优路线和最优目标函数值。5:工程路线问题也称为最短路问题，根据问题的不同分为定步数问题和不定步数问题；对不定步数问

6、题，用 迭代法求解，有函数迭代法和策略迭代法两种方法。6 :在图论方法中，通常用点表示人们研究的对象用边表示对象之间的某种联系。7 : 一个无圈且_连通的图称为树。四、计算题（每小题15分，45分）1 :考虑线性规划问题：max z 2xi 4x2 3x33xi 4x2 2X3 60 2xi X2 2X3 40 s.t.Xi 3x2 2x3 80X1,X2,X3O(a) 写出其对偶问题；(b) 用单纯形方法求解原问题；de)用对偶单纯形方法求解其对偶问题；(d)比较(b) ( c)计算结果。1 ：解a ):其对偶问题为minz 60yi 40y2 80y3 3yi 2y2 y3 2 s.t.4

7、yi y2 y3 42yi 2y2 2y3 3yb沖0分）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 )第二步(1 0 -1 )第三步(5/6，2/3，0，11/6，0，0)5分）又对偶问题的对偶即原问题，因（2d）:对偶问题的实质是将单纯形法应用于对偶问题的求解， 此（b）、（ c）的计算结果完全相同。分）2:某公司打算在三个不同的地区设置4个销

8、售点，根据市场预测部门的估计，在不同的地区设置不同数量的销售店，每月可得到的利润如下表所示。试问各个地区应如何设置销 售店，才能使每力获得的总利润最大？其値是多少？2 :解该问题可以作为三段决策问题，对1，2，3地区分别设置销售店形成1，2，0162530320121721220101416173三个阶段。Xk表示给地区k设置销售店时拥有分配的数量，Uk表示给地区k设 置销售店的数量。状态转移方程为：XkiXkUk :阶段效应题中表所示；目标函数3max R gk（Uk）踽g2k）表示在k地区设置 山个销售店时的收益；k1-（3 分）首先逆序求解条件最有目标函数值集合和条件最有决策集合：k 3

9、 时0 X34, 0 U3X3, f3（X3）maxg3（U3）f4（x，其中临f4（X4）0于是有：fs（o）g3（0） o,U3（0） 0 ,f3（i）g3（i）io,U3（1）1,f3（2） g3 14,U3（2）2,fs（3） g3）16,u *3 （3） 3,f3（4） g3 17,u3 4 （3分）k 2 时,0 X24, 0 U2X2, f2（X2）maxg2（U2）f3（X3）,0 U2 X2于是有：f2（0） omuaxo g2（U2）f3（X3） 0,112（0）0 ,f2（1） omuaxig2（U2）f3（X3） 12, U2（1） 1,f2（2） omuax2 g2（

10、U2）f3（X3） 22, u 2 （2） 1,f2（3） max g2（U2）f3（X3） 27, U2（3） 2,0 U2 3f2（4） omuax4（ g2 （112） f3（X3） 31,112 （4） 2 or 3.0 U2 4（3分）k 3 时，X1 4, 0 U1 X1 4,于是有：fi(4) omuax4 gi(ui ”2(x2) 47, ui(4) 2(3分)因此，最优的分配方案所能得到的最大利润位47，分配方案可由计算结果反向查出得：u 1(4) 2, u 2(2) 1, U3(1) 1 0即为地区1设置两个销售店，地区2设置地区3设置1个销售店。3:对下图中的网络，分别用

11、破圈法和生长法求最短树。3 :解破圈法D ：nua V1 v2v3 1 .去畑 M-v3J （2）：nua V2V4V3V2 去她 陀唧3）B v2-v3-v5 v2 ：I*2-v51 4） V3，V45，V5，V3鼻唤】在图中已无圈，此时，卩6，而qp，因此所得的是最短树。结果如下图，其树的总长度为1 2。(6分)分）生长法根据生长法的基本原理，得以下计算表V2V3V4V5V6Si26V2389S2389V353s353V51s451v63s53据此也得到与破圈法相同的最短树。（6分）五、简答题（每小题10分，共20分）1试述单纯形法的计算步骤，并说明如何在单纯形表上判断问题是 具有唯一最优

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

13、比值最小的不止一个，选择其中之一出基。做主元变换。反复进行上述过程就可以找到最优解或判断出没有有限最优解。-（3 分）2简述最小费用最大流问题的提法以及用对偶法求解最小费用最大流的原理和步骤。解：2：最大流问题就是在一定条件下，要求流过网络的物流、能量流或信息流等流量最大的问题。如果已知流过弧叭”的单位流量要发生a的费用，要求使总费用为最小的最大流流量分配方法。即在上述最大流 问题上还应增加尖于费用的目标：min xjj cy种问题称为最小费用最大流问题。模型可以描述为：min Xij cymax ffXijXji 0,sst jji s, t it0 xo by采用对偶法求解最大流最小费用问题，其原理为：用福德一富克逊算法求出网络的最大流量，然后用 Ford算法找出从起点到终点w的最短增广链。在该增广链上，找出最大调整量，并调整流量，得到一个可 行流。则此可行流的费用最小。如果此时流量等于最大流量，则目前的流就是最小费用