运筹学考试题a卷及答案.doc

1、运筹学期末考试题（a卷）注意事项：1、答题前，考生务必将自己的姓名、班级填写在答题卡上。2、答案用钢笔或圆珠笔写在答题卡上，答在试卷上不给分。3、考试结束，将试卷和答题卡一并交回。一、单项选择题（每小题1分，共10分）1：在下面的数学模型中,属于线性规划模型的为m ax S 4X Ym h S 3Xm axS 2XYA . s.t XY 3B. s.t 2X YC.s.t.X,Y上达到。.几何点.人工变量2.线性规划问题若有最优解，则一定可以在可行域的A.内点B .顶点C .外点3：在线性规划模型中，没有非负约束的变量称为A.多余变量 B .松弛变量C. 自由变量4：若线性规划问题的最优解同时

2、在可行解域的两个顶点处达到，那么该线性规划问题最优 解为（）A.两个B.零个5：原问题与对偶问题的最优（C.无穷多个 ）相同。D.有限多个D.解的分量个数6：若原问题中Xi为自由变量，那么对偶问题中的第i个约束一定为（）A.等式约束B. y”型约束 C.“2”约束 D .无法确定7：若运输问题已求得最优解，此时所求出的检验数一定是全部（）A .小于或等于零B.大于零C.小于零D.大于或等于零8：对于m个发点、n个收点的运输问题，叙述错误的是（）A .该问题的系数矩阵有mXn列B.该问题的系数矩阵有m+n行C.该问题的系数矩阵的秩必为m+n-1D.该问题的最优解必唯一9：关于动态规划问题的下列命

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

4、线性规划问题中的 bi, cj值同时发生改变，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行基的情况。5：若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解。（）6：运输问题的表上作业法实质上就是求解运输问题的单纯形法。（）7：对于动态规划问题，应用顺推或逆推解法可能会得出不同的最优解。（）8：动态规划的基本方程是将一个多阶段的决策问题转化为一系列具有递推关系的单阶段的 决策问题。（）9：图论中的图不仅反映了研究对象之间的关系，而且是真实图形的写照，因而对图中点与 点的相对位置、点与点连线的长短曲直等都要严格注意。（）10：网络最短路线问题和最短树问题实质上是一个问

5、题。（）三、填空题（每空1分，共15分）1：线性规划中，满足非负条件的基本解称为 ,对应的基称为。2：线性规划的目标函数的系数是其对偶问题的 ；而若线性规划为最大化问题，则对偶问题为o3：在运输问题模型中，m n 1个变量构成基变量的充要条件是 。4：动态规划方法的步骤可以总结为：逆序求解 ,顺序求、和5：工程路线问题也称为最短路问题，根据问题的不同分为定步数问题和不定步数问题；对不定步数问题，用迭代法求解，有 迭代法和迭代法两种方法。6：在图论方法中，通常用 表示人们研究的对象，用 表示对象之间的某联系。7： 一个且的图称为树。四、计算题（每小题 15分,45分）1：考虑线性规划问题：m a

6、x z 2 xi 4x2 3x33xi 4x2 2x3 602 xi X2 2x340s. t.xi 3x2 2x3 80xi , X2 , X3 0（a）：写出其对偶问题；（b）:用单纯形方法求解原问题；（c）：用对偶单纯形方法求解其对偶问题；（d）：比较（b） （ c）计算结果。2：某公司打算在三个不同的地区设置4个销售点，根据市场预测部门的估计，在不同的地区 设置不同数量的销售店，每月可得到的利润如下表所示。试问各个地区应如何设置销售店，才能3：对下图中的网络，分别用破圈法和生长法求最短树。V2五、简答题（每小题10分，共 1.试述单纯形法的计算步骤， 多最优解和无有限最优解。20分）并

7、说明如何在单纯形表上判断问题是具有唯一最优解、无穷2 .简述最小费用最大流问题的提法以及用对偶法求解最小费用最大流的原理和步骤。 甘肃政法学院2008- 2009学年度第一学期运筹学期末考试参考答案及评分标准单项选择题（每小题1分，共10分）a卷)1.B.D判断题2.B9.A(每小题3.C10.D分，共10分)4.C5.B6.A7.Dl.T2.F3.T4.F5.T7.F.T填空题9.F10.F（每空1分,共15分）1：基本可行解、可行基； 2：右端常数、 最优策略、最优路线、最优目标函数值； 计算题（每小题15分，45分）最小化问题;3：5：函数、策略;不含闭回路; 6：点、边；4：最优目标函

8、数、7：无圈、连通。1：解a）：其对偶问题为60 yi40 Y280y33yi4 yi s. t2 yi2 V2Y3Y2Y3yi,Y2 , Y32 Y30（3分）b）：用单纯形方法求解原问题时每步迭代结果:原问题解第一步(0, 0, 0, 60, 40, 80)第二步(0, 15, 0, 0, 25, 35)第；：步(0, 20/3, 50/S, 0, 0, 80/3)（5分）c）：用对偶单纯形方法求解对偶问题时每步迭代结果:对偶问题问题解第一步(0, 0, 0, 2 4,)第二步(1, 0, 0, 1, 0, -1)第三步(5/6, 2/3, 0, 11/6, 0, 0)d)此:对偶问题的实

9、质是将单纯形法应用于对偶问题的求解,(b)、（C）的计算结果完全相同。（5 分）又对偶问题的对偶即原问题，因Q分）2：该问题可以作为三段决策问题，对1, 2, 3地区分别设置销售店形成1, 2, 3三个阶段。Xk表示给地区k设置销售店时拥有分配的数量，Uk表示给地区k设置销售店的数量。状态转移方程为：Xk 1 Xk Uk;阶段效应题中表所示；目标函数：max3R gk (uk )；k 1其中gk Mk ）表示在k地区设置Uk个销售店时的收益;（3分）首先逆序求解条件最有目标函数值集合和条件最有决策集合:k 3时,0 X34,U3 X3 ，m axg3(113)U3其中 f4(X4 ) 0于是有

10、:f3 (0)g3 (0)0,U 3(0)0,6 (1) g3(1)10,U 3 (1)14,6 (3) g3(3)16,u 3 (3)g3 (4)17,(4)3分）k 2时,X24, 0U2m axg2 12 )0 u 2 X2(X3 ),于是有:f2 (0)m ax(g2(U2 )0 U2 00, u(0)f (1)2m axg ® )0 U2 122(x)312, u(1)2m axg2 )0 U2 2&3 )22, u1,fe (3)m ax(g 2 标2 ) 0 U2 327, u 2 (3)(4)m axg2(L12 )0 U2 4后(X3 )31, u2 2 o

11、r3.3分）3时, k xi4,0 uiXI 4, 于是有:f (4)1m ax g M )0 ui 41f(X )2247, u (4)12.3分）因此，最优的分配方案所能得到的最大利润位47,分配方案可由计算结果反向查出得:U*1 (4) 2, u*2(2) 1, u* 3 (1) 1o即为地区1设置两个销售店，地区 2设置1各销售店，地区3设置1个销售店。3：解破圈法（3分）(1)：取圈 VI, V2 , V3 , VI ,去掉边vi ,V3 o ( 2)：取圈 V2 , V4 , V3 ,V2 ，去掉边v2 ,V4 。(3):取圈 V2 , V3 , V5 , V2 ,去掉边V2 ,

12、V5 o ( 4):取圈 V3 , V4 ,V5 , V5 ,¥3 ，去掉边艮3 , V4。（6分）在图中已无圈，此时， P 6，而q p 15 ,因此所得的是最短树。结果如下图，其树的总长度为12。（3分）生长法根据生长法的基本原理，得以下计算表V2V3V4V5V6S126V2389S2389V353S353V51S451V63S53据此也得到与破圈法相同的最短树。.（6分）简答题（每小题10分,共20分）1：单纯形法的计算步骤第一步：找出初始可行解，建立初始单纯形表。第二步：判断最优，检验各非基变量Xj的检验数 C B iP C o(1) 若所有的j 0 ,则基B为最优基，相应的

13、基可行解即为基本最优解，计算停止。(2) 若所有的检验数j 0，又存在某个非基变量的检验数所有的k 0 ,则线性规划问题有无穷多最优解。(3) 若有某个非基变量的检验数j 0,并且所对应的列向量的全部分量都非正，则该线性规划问题的目标函数值无上界，既无界解，停止计算。第三步：换基迭代(1) 当存在 k 0,选xk进基来改善目标函数。若检验数大于 0的非基变量不止一 个，则可以任选其中之一来作为进基变量。(2) 进基变量xk确定后，按最小比值原则选择出基变量 xro若比值最小的不止一个， 选择其中之一出基。(3) 做主元变换。反复进行上述过程就可以找到最优解或判断出没有有限最优解。2：最大流问题

14、就是在一定条件下，要求流过网络的物流、能量流或信息流等流量最大的问 题。如果已知流过弧 &i, Vj)的单位流量要发生cu的费用，要求使总费用为最小的最大流流m h XijCij o这种问题称量分配方法。即在上述最大流问题上还应增加关于费用的目标: 为最小费用最大流问题。模型可以描述为:m hm ax ffi sX s . t . jX0 小采用对偶法求解最大流最小费用问题，Xj 0i s, t)f i tb V其原理为：用福德一富克逊算法求出网络的最大 流量，然后用Foxd算法找出从起点vs到终点vt的最短增广链。在该增广链上，找出最大调整量，并调整流量，得到一个可行流。则此可行流的费用最小。如果此时流量等于最大流 量