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

1、运筹学2015年学年第二学期期末考试题（a卷）注意事项：1、答题前，考生务必将自己的姓名、班级填写在答题卡上2、答案用钢笔或圆珠笔写在答题卡上，答在试卷上不给分3、考试结束，将试卷和答题卡一并交回单项选择题（每小题1分，共10分）maxS X2Y2minS 2XYC. s.t.X Y2D. st.X Y 3X,Y0X,Y 0maxS 4XYminS 3XYA. st.XY3B. s.t.2X Y1X,Y0X,Y0）上达到。1：在下面的数学模型中，属于线性规划模型的为（）2线性规划问题若有最优解，则一定可以在可行域的（.几何点A. 内点 B.顶点C .外点D3:在线性规划模型中，没有非负约束的变

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

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

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

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

6、题也称为最短路问题，根据问题的不同分为定步数问题和不定步数问题；对不定步数问题，用迭代法求解，有 函数迭代法和策略迭代法两种方法。6:在图论方法中，通常用 点表示人们研究的对象，用 边表示对象之间的某种联系。7: 一个无圈_且连通的图称为树。四、计算题（每小题 15分，45 分）1:考虑线性规划问题：max z2为4X23x33xi4X22x3602xiX22X340s. t.Xi3冷2X380X1,X2,X30(a) ：写出其对偶问题；(b) :用单纯形方法求解原问题；(c) ：用对偶单纯形方法求解其对偶问题;(d) :比较(b) ( c)计算结果。1：解 a)：其对偶问题为min z60%

7、40y280y33y12y2y32s. t.4y1y2y342y12y22y33Yi,y2,Y30(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)第二步(1, 0 , 0 , 1 , 0 , -1)第三步(5/6 , 2/3 , 0 , 11/6 , 0 , 0)(5分)d)：对偶问题的实质是将单纯形

8、法应用于对偶问题的求解，又对偶问题的对偶即原问题， 因此(b)、(c)的计算结果完全相同。(2分)2:某公司打算在三个不同的地区设置4个销售点，根据市场预测部门的估计，在不同的地区设置不同数量的销售店，每月可得到的利润如下表所示。试问各个地区应如何设置销2:解 该问题可以作为三段决策问题，对1, 2, 3地区分别设置销售店形成1 ,2, 3三个阶段。Xk表示给地区k设置销售店时拥有分配的数量，Uk表示给地区k设置销售店的数量。状态转移方程为：Xk 1XkUk ；阶段效应题中表所示；目标函数：3max Rgk(uk)；其中gk(uk)表示在k地区设置uk个销售店时的收益;k 1k 3时，0 X3

9、4, 0 U3 X3,3（X3） max（U3）U3f4 （X4 ）0于是有：f3（0）g3（0）0,U3 （0）0,f3（1）g3（1）10,U3（1）1,f3（2）g3（2）14,U3 （2）2f4(Xj,其中(3 分)首先逆序求解条件最有目标函数值集合和条件最有决策集合:f3（3）g3（3） 16,u3（3）3,016253032012172122010141617f3（4）g3（4）17, u3（4）（3 分）k 2 时，0 X24, 0 U2 X2,f2 （X2 ）maxg2（U2） f3（X3）,0 U2 X2于是有:f2（0）0叫3侶（吐）f3（X3）0, U2（0）0,f2（1

10、）max.g2（U2）f3（X3）12,U2（1）1,f2（2）magu）f3（X3）22,U2 （2）1 ,f2（3）max）f3（X3）27,u2 （3）2,f2 （4） max0 U2 492（氏）3（X3）31,u 2（4）2 or 3-（3 分）k 3时，为4,0U1x（4,于是有：hmax.g1（U1）f2（X2）47, U12.（3 分）因此，最优的分配方案所能得到的最大利润位47,分配方案可由计算结果反向查出得：u；（4）2, u*2（2）1, u*3（1） 1。即为地区1设置两个销售店,地区2设置1各销售店，地区 3设置1个销售店。3:对下图中的网络，分别用破圈法和生长法求最

11、短树。3:解（1）：取圈 WN2N3M，去掉边，3】。（2）：取圈 V2,V4,V3,V2，去掉边V2,V4。（3）：取圈 V2，V3，V5,V2，去掉边V2，V5。（ 4）:取圈 V3，V4,V5,V5,V3，去掉边也皿。在图中已无圈，此时，p 6，而q p 1 5，因此所得的是最短树。结果如下图，其树的总长度为12。.（6分）4（3 分）生长法根据生长法的基本原理，得以下计算表V2V3V4V5vSi26V2389S2389V353S353v1S451V63S53据此也得到与破圈法相同的最短树。- （6分）五、简答题（每小题10分，共20分）1 试述单纯形法的计算步骤，并说明如何在单纯形表上

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

13、中之一来作为进基变量。进基变量Xk确定后，按最小比值原则选择出基变量Xr。若比值最小的不止一个，选择其中之一出基。做主元变换。 反复进行上述过程就可以找到最优解或判断出没有有限最优解。 （ 3 分）2 简述最小费用最大流问题的提法以及用对偶法求解最小费用最大流的原理和步骤。解： 2：最大流问题就是在一定条件下，要求流过网络的物流、能量流或信息流等流量 最大的问题。如果已知流过弧（v,vj）的单位流量要发生Cij的费用，要求使总费用为最小的最大流流量分配方法。即在上述最大流问题上还应增加关于费用的目标：min Xijcij 。这种问题称为最小费用最大流问题。模型可以描述为：minXij cijmaX ffisXijXji0i s, ts.t. jjjfit0 Xijbij采用对偶法求解最大流最小费用问题，其原理为：用福德富克逊算法求出网络的最大流量，然后用Ford算法找出从起点Vs到终点Vt的最短增广链。在该增广链上，找出最大调 整量 ，并调整流量，得到一个可行流。则此可行流的费用最小。如果此时流量等于最大流 量，则目前的流就是最小费用