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

1、WORD格式整理版学习好帮手运筹学2015年学年第二学期期末考试题（a卷）注意事项：1、答题前，考生务必将自己的姓名、班级填写在答题卡上2、答案用钢笔或圆珠笔写在答题卡上，答在试卷上不给分D .无法确定3、考试结束，将试卷和答题卡一并交回。单项选择题（每小题1分，共10分）1:在下面的数学模型中，属于线性规划模型的为（)max S =4X +YminS=3X 十丫max2 2S = X2 +Y2minS=2XYA. st.XY 3B.s.t.2X -丫 工一1C. s.t.X Y 兰 2D.st.X +Y 33X,Y A0X, Y X01X,Y Z0X,Y 02.线性规划冋题若有最优解,则定可

2、以在可行域的（）上达到。A.内点B顶点C.外点D.几何点3:在线性规划模型中，没有非负约束的变量称为()A.多余变量B.松弛变量C.自由变量D.人工变量A.两个B.零个C.无穷多个D.有限多个5:原问题与对偶问题的最优（）相同。A.解B目标值C.解结构D.解的分量个数6:若原冋题中Xi为自由变量，那么对偶问题中的第i个约束定为 （）4:若线性规划问题的最优解同时在可行解域的两个顶点处达到，那么该线性规划问题最优 解为（）A.等式约束B .“W ”型约束 C”约束7:若运输问题已求得最优解，此时所求出的检验数一定是全部（ ）A.小于或等于零 B .大于零C .小于零D大于或等于零&对于m个发点、

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

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

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

6、优策略、 最优路线和最优目标函数值 。5： 工程路线问题也称为最短路问题，根据问题的不同分为定步数问题和不定步数问题；对不定步数问题，用迭代法求解，有 函数迭代法和策略迭代法两种方法。6:在图论方法中，通常用 点表示人们研究的对象，用 边表示对象之间的某种联系。7: 一个无圈_且连通的图称为树。四、计算题（每小题 15分，45 分） 1:考虑线性规划问题：max z = 2x 4x2 3x33X! +4x2 +2x3 兰 602音 + x2 +2x3 兰 40 s. t.捲+ 3冷+ 2x3兰80为，X2,x3 _0（a）:写出其对偶问题；（b）：用单纯形方法求解原问题；（c）:用对偶单纯形方

7、法求解其对偶问题；（d）：比较（b）（ c）计算结果。1：解a ）：其对偶问题为mins. t. z=60y）+40y2 +80y3 ”3% +2y? + y3 X24% + y 3y 42% +2y2 +2y3 2 3y1,y2,y0分）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）第三步（

8、5/6，2/3，0，11/6，0，0）（5分）d）：对偶问题的实质是将单纯形法应用于对偶问题的求解，又对偶问题的对偶即原问题，因此（b）、（c）的计算结果完全相同。（2分）2:某公司打算在三个不同的地区设置4个销售点，根据市场预测部门的估计，在不同的地区设置不同数量的销售店，每月可得到的利润如下表所示。试问各个地区应如何设置销区341021632530320121721220101416172:解该问题可以作为三段决策问题，对1, 2, 3地区分别设置销售店形成1 , 2,3三个阶段。xk表示给地区k设置销售店时拥有分配的数量，uk表示给地区k设置销售店的数量。状态转移方程为：Xk+=Xk-U

9、k ；阶段效应题中表所示；目标函数：3max R=：Z gk（Uk）；其中gk（uQ表示在 k地区设置Uk个销售店时的收益；k=1（3 分）首先逆序求解条件取有目标函数值集合和条件取有决策集合：k=3时，0 兰X3 兰 4, 0 兰 U3 兰怡，f3（X3）=maxg3（U3）+ f4（xj，其中u3f4（X4）=0于是有：f3（o）=g3（o）=o,u3（o）=o,f3（i） = g3（i） = io,u3（i） = i.f3（2） =g3（2） =14,u3（2） =2,f3（ 3） =g3 （3） =16,u3 （3） =3,f3=g3 =17,u3（4）=4.-（3 分）k =2时，0

10、 辽 x2 4, Q u2 乞 x2, f2（x2） = maxg2（u2） f3（x3）,0虫2纟2于是有：f2（0muax gzU） f3（X3） =0, u 2（0） =0 ,f2（i）=肿气92（氏）f3（x3） =12, U2（i）=i,f2（2）二 muaxg2（u2） f?%） =22, u2=i,f2 （3）max g2（U2） f3（X3） = 27, u2 （3） =2,0 2 3f2（4） =maxg2（U2）3（X3） =31, u2（4） =2 or 3.02超（3 分）k = 3时，为=4, 0_山_为=4, 于是有：办二maxgi（5） f2（x2” =47, u

11、=2.（3分）因此，最优的分配方案所能得到的最大利润位47,分配方案可由计算结果反向查出得：口1（4） =2, u 2（2） =1, u 3 （1）=1。即为地区1设置两个销售店,地区2设置1各销售店，地区 3设置1个销售店。3:对下图中的网络，分别用破圈法和生长法求最短树。3:解破圈法（1）：取圈 WMWV1，去掉边vz。（2）：取圈 V2,V4,V3,V2，去掉边V2,V4（3）：取圈 V2,V3,V5,V2，去掉边V2,V5。（ 4）:取圈 V3,V4,V5,V5,V3，去掉边V3,V4。在图中已无圈，此时，p=6，而qnp15，因此所得的是最短树。结果如下图,其树的总长度为 12。（6

12、分）(3生长法根据生长法的基本原理，得以下计算表V2V3V4V5VSi26COO0O0V2389QOS2389QOV353QOS353QOV5QO1S451V63S53据此也得到与破圈法相同的最短树。-（6分）五、简答题（每小题10分，共20分）1 试述单纯形法的计算步骤，并说明如何在单纯形表上判断问题是具有唯一最优解、无 穷多最优解和无有限最优解。解：1:单纯形法的计算步骤第一步：找出初始可行解，建立初始单纯形表。第二步：判断最优，检验各非基变量Xj的检验数匚j =CBB Pj c若所有的Cr0，则基B为最优基，相应的基可行解即为基本最优解，计算停止。若所有的检验数- 0，又存在某个非基变量

13、的检验数所有的二k = 0，则线性规划问题有无穷多最优解。若有某个非基变量的检验数 0，并且所对应的列向量的全部分量都非正，则该线性规划问题的目标函数值无上界，既无界解，停止计算。第三步：换基迭代当存在二k 0，选Xk进基来改善目标函数。若检验数大于0的非基变量不止一个，则可以任选其中之一来作为进基变量。进基变量Xk确定后，按最小比值原则选择出基变量Xr。若比值最小的不止一个，选择其中之一出基。做主元变换。反复进行上述过程就可以找到最优解或判断出没有有限最优解。（3 分）2 简述最小费用最大流问题的提法以及用对偶法求解最小费用最大流的原理和步骤。解：2:最大流问题就是在一定条件下，要求流过网络的物流、能量流或信息流等流量minE XjCij。这最大的问题。如果已知流过弧（V ,Vj）的单位流量要发生Cij的费用，要求使总费用为最小的最大流流量分配方法。即在上述最大流问题上还应增加关于费用的目标:种问题称为最小费用最大流问题。模型可以描述为：min、% cmax fF 卩送対送勺才0s.tj jj0 Xj bj采用对偶法求解最大流最小费用问题，其原理为：用福德一富克逊算法求出网络的最大 流量，然后用Ford算法找出从起点Vs到终点Vt的最短增广链。在该增广链上，找出最大调 整量；，并调整流量，得到一个可行流。则此可行流的费用最小。如果此时流量等于最大流 量，