运筹学期末考试试题及答案

1、楚大2012 2 0 13上学期经济信息管理及计算机应用系运筹学期末考试试题及答案班级 学号一、单项选择题:1、在下面的数学模型中，属于线性规划模型的为（A ）。minS = 3X + YmaxS = 4X +YmaxS = X2 +Y2minS = 2XYs.t.2X-Y>-1 AJs.t.XY<3 C.<s.t.X-Y<2D/s.t.X + Y>3X,Y>0X.Y>0X,Y>0X,Y>02、线性规划问题若有最优解，则一定可以在可行域的（A ）上达到。A.顶点B.内点C.外点D.几何点3、在线性规划模型中，没有非负约束的变量称为（C ）A

2、. 多余变量B.松弛变量C.自由变量 D.人工变量4、若线性规划问题的最优解同时在可行解域的两个顶点处达到，那么 该线性规划问题最优解为（C ）oA.两个B.零个C.无穷多个D.有限多个5、线性规划具有唯一最优解是指（B ）A.最优表中存在常数项为零B.最优表中非基变量检验数全部非零C.最优表中存在非基变量的检验数为零D.可行解集合有界6、设线性规划的约束条件为X + x2 + x3 = 3< 2xj + 2x2 +x4 = 4丹,些>0则基本可行解为(C)oA. (0,0, 4, 3 )B.(3, 4,0,0)C(2, 0,1, 0 )D. (3,0,4,0)7、若运输问题己求得

3、最优解，此时所求出的检验数一定是全部(D )A、小于或等于零 B.大于零C.小于零D.大于或等于零弘、对于m个发点、n个收点的运输问题，叙述错误 的是(D )A.该问题的系数矩阵有mXn列-B.该问题的系数矩阵有m+n行C.该问题的系数矩阵的秩必为m+n-looD.该问题的最优解必唯一9、关于动态规划问题的下列命题中错误的是(A )A、动态规划分阶段顺序不同，则结果不同B、状态对决策有影响C、动态规划中，定义状态时应保证在各个阶段中所做决策的相对独 立性D、动态规划的求解过程都可以用列表形式实现1 0、若P为网络G的一条流量增广链，则P中所有正向弧都为G的（D ） »A.对边B.饱和

4、边C.邻边D .不饱和边一、 判断题。1、图解法和单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。（T ）2、单纯形法的迭代计算过程是从一个可行解转换到目标函数值更大 的另一个可行解。（F）3、一旦一个人工变量在迭代中变为非基变量后,该变量及相应列的数字可以从单纯形表中删除,而不影响计算结果。（T ）4、若线性规划问题中的c,值同时发生改变，反映到最终单纯形表 中，不会出现原问题与对偶问题均为非可行基的情况。（F）5、若线性规划的原问题有无穷多最优解,则其对偶问题也一定具有无 穷多最优解。（T ）6、运输问题的表上作业法实质上就是求解运输问题的单纯形法。（T ）7、对于动态规划问题，

5、应用顺推或逆推解法可能会得出不同的最优解。（F）8、动态规划的基本方程是将一个多阶段的决策问题转化为一系列具 有递推关系的单阶段的决策问题。（T ）9、图论中的图不仅反映了研究对象之间的关系，而且是真实图形的 写照，因而对图中点与点的相对位置、点与点连线的长短曲直等都要 严格注意。(F )10、网络最短路线问题和最短树问题实质上是一个问题。(F )二、填空题。1、线性规划中,满足非负条件的基木解称为 基本可行解，对应的基称为可行基。2、线性规划的目标函数的系数是其对偶问题的一右端常数一而若线性规划为最大化问题，则对偶问题为 最小化问题3、在运输问题模型中，m +个变量构成基变量的充要条件是 丕

6、含闭回路。4、动态规划方法的步骤可以总结为：逆序求解_最优目标函数,顺序求最优策略、最优路线和最优目标函数值。5、工程路线问题也称为最短路问题，根据问题的不同分为定步数问题和不定步数问题；对不定步数问题，用迭代法求解，有函数 迭代法和策略迭代法两种方法。6、在图论方法中，通常用点表示人们研究的对象，用边表示对象之间的联系。7、线性规划 max Z =-xf +x2t2xt +x2 < 6,4 +x2 S&xpx2 >0 的最优解是(0,6), 它的第1、2个约束中松驰变量(，屁)=(0 ,2) ) 8、运输问题的检验数入，丿的经济含义是(Xjj增加一个单位总运费增加入i j

7、)四、计算题。1、考虑线性规划问题：max z = 2x + 4x2 + 3x33x + 4x2 + 2x3 < 602xl + 2x3 < 40s. t. <+ 3x2 + 2x3 < 80Vpx2,x3 >o(a).写岀其对偶问题；(b )、用单纯形方法求解原问题；(c) 、用对偶单纯形方法求解其对偶问题；(d) 、比较(b) (c)计算结果。1：解 切、其对偶问题为min z, = 60” + 40+ 80y33)'】+2儿+儿$4牙+儿+3儿5 2巧+2力+2比b)、用单纯形方法求解原问题时每步迭代结果:原问题解第一步(0, 0 ,0, 6 0,4

8、 0 , 80)第二步(0 , 1 5,0, 0,25, 35)第三步( 0,2 0 /3,50 / 3,0,0 , 80/3 )c)、用对偶单纯形方法求解对偶问题时每步迭代结果:对偶问题问题解第一步(0,0,0, -2, -4 , -3 )第二步第三步(5/6,2/3, 0 ,/6, 0,0)d)、对偶问题的实质是将单纯形法应用于对偶问题的求解，又对偶问 题的对偶即原问题，因此(b )、(c)的计算结果完全相同。五、证明题：2、对问题m i nf (xl,x2 ) =xlA2+25x2A2 中的变量 x=(xl, x 2 )T 作线性变换:yl=xl, y2二5x2,则原来的无约束优化问题变为：证明:从任意初始点y 0出发，用最速下降法问题(*)迭代一轮即可求得最优化解，从中你可以得到什么启示？证：从任意初始点为y 0 =( y 1 0,y2A0) T,令P 0 =-f(y 0 ),则代入f