运筹学2015学年期末考试题A卷及复习资料

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

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

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

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

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

6、优目标函数值 。5:工程路线问题也称为最短路问题，根据问题的不同分为定步数问题和不定步数问题；对 不定步数问题，用迭代法求解，有 函数 迭代法和 策略 迭代法两种方法。6:在图论方法中，通常用 点 表示人们研究白对象，用 一边 表示对象之间的某种联系。7: 一个 无圈 且 连通 的图称为树。四、计算题（每小题 15分，45分）1:考虑线性规划问题：max z 2xi 4x2 3x33xi 4x2 2x3602% x2 2x340s.t.x1 3x2 2x3 80K,x2,& 0(a)：写出其对偶问题；(b)：用单纯形方法求解原问题；(c)：用对偶单纯形方法求解其对偶问题；(d)：比较(

7、b) (c)计算结果。1：解 a)：其对偶问题为min z 60yl 40y2 80y33y1 2y2y3 2x 4yiV2y3 4s.t.2yi 2y2 2y33yi,y2,y30(3 分)b）:用单纯形方法求解原问题时每步迭代结果:原问题解第T(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/

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

9、数：3max Rgk（uk）；其中gk（uk）表示在k地区设置uk个销售店时的收益；k 1（3 分）首先逆序求解条件最有目标函数值集合和条件最有决策集合：k 3时，0 X3 4, 0 U3 X3, f3（X3） maxg3（U3） f/xj,其中U3f4 （x4 ） 0于是有：f3（0） g3（0） 0,U3（0） 0,f3（1） g3（1） 10,U3（1） 1,f3（2）g3（2） 14,u 3 （2）2f3（3） g3（3） 16,u3（3） 3,f3（4）g3（4）17,u3（4）4.（3 分）k 2时，0 x24, 0U2 x2, f2 （x2）maxg2（u2）£3（x3

10、）,0 U2 x2于是有:f2（o）0m既的2（必）f2（1） maxg2（U2）f2（2）muaxg2（U2）f2（3）muaNgzU）f3（X3）0, U2（0）0£3（X3）12, U2（1） 1,_'£3（X3）22, U2（2） 1£3（X3）27, U2（3）2f2（4）max g2（U2） £3（X3）31,0 U2 4u2（4） 2 or 3.（3分）k 3时，X) 4, 0 u1 X) 4,于是有:"4)犯3%®)£2(X2)47, U1 2.(3分)因此，最优的分配方案所能得到的最大利润位47,分

11、配方案可由计算结果反向查出得：* ，八_* .*,.、 .u 1(4)2, u 2(2) 1, u 3(1) 1。即为地区1设置两个销售店,3:解破圈法(1)：取圈”2,丫3,必，去掉边 v1”3。(2)：取圈 V2,V4,V3,V2 ,去掉边V2,v4L地区2设置1各销售店，地区 3设置1个销售店。（3）：取圈 v2,v3,v5,v2,去掉边 v2,v5。（4）：取圈 v3,v4,v5,v5,v3 ,去掉边匕,储。在图中已无圈，此时，p 6,而q p 1 5,因此所得的是最短树。结果如下图，其树的总长度为12。.(6分)J4（3分）生长法根据生长法的基本原理，得以下计算表V2V3V4V5V6

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

13、变量的检验数j 0 ，并且所对应的列向量的全部分量都非正，则该线性规划问题的目标函数值无上界，既无界解，停止计算。第三步：换基迭代当存在k 0 ，选 xk 进基来改善目标函数。若检验数大于0 的非基变量不止一个，则可以任选其中之一来作为进基变量。进基变量xk 确定后，按最小比值原则选择出基变量xr 。若比值最小的不止一个，选择其中之一出基。做主元变换。反复进行上述过程就可以找到最优解或判断出没有有限最优解。 ( 3 分)2 简述最小费用最大流问题的提法以及用对偶法求解最小费用最大流的原理和步骤。解：2：最大流问题就是在一定条件下，要求流过网络的物流、能量流或信息流等流量最大的问题。如果已知流过弧(vi ,vj ) 的单位流量要发生cij 的费用，要求使总费用为最小的最大流流量分配方法。即在上述最大流问题上还应增加关于费用的目标：minxij cij 。这种问题称为最小费用最大流问题。模型可以描述为：minxij cijmax f采用对偶法求解最大流最小费用问题，s.t. j xijxji0 xijbijf is0 i s, tf it其原理为：用福德富克逊算法求出网络的最大流量，然后用Ford算法找出从起点vs到终点vt的最短增广链。在该增广链上，找出最大调整量 ，并调整流量，得到一个可行流。则此可行流的费用最小。如果此时流量等于最大流量，则目前的