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

1、楚大20122013上学期经济信息管理及计算机应用系运筹学期末考试试题及答案学号班级:一、单项选择题:1、在下而的数学模型中，属于线性规划模型的为（A ）22?maxS?X?YniinS?Y2XYmaxS?4XYniin?XS?3?2tX?Y?Cs3t?YXD?XY3stAslt?Y2X?sB?XX,Y?0Y?00?XY0Y?X?2、线性规划问题若有最优解，则一定可以在可行域的（A）上达到。A.顶点B.内点C.外点D.儿何点3、在线性规划模型中，没有非负约束的变量称为（A.多余变量B.松弛变量C. iM由变量D.人丄变量4、A俩个B零个C无穷多个D有限多个若线性规划问题的最优解同时在可行解域的

2、两个顶点处达到，那么该线性规划问题最优解为（C ）o5、线性规划具有唯一最优解是指（B ）A.最优表中存在常数项为零B.最优表中非基变量检验数全部非零C.最优表中存在非基变星的检验数为零D.可行解集合有界、设线性规划的约束条件为6.X?X?X?3?312?4?x?x?2x2?q?x“x?0?w 则基本可行解为（C ）。A. 0,4,3)B. 34,0,0)c. (2,040)D. 0,4,0)7、若运输问题己求得最优解，此时所求出的检验数一定是全部（D ）A、小于或等于零B.大于零C小于零D.大于或等于零8、对于m个发点.n个收点的运输问题，叙述错误的是（D ）A.该问题的系数矩阵有mXn列-

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

4、变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。（T ）4、若线性规划问题中的值同时发生改变，反映到最终单纯形表cb中，不会岀现原问题与对偶问题均为非可行基的情况。（F ） 5、若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解。（T ）6、运输问题的表上作业法实质上就是求解运输问题的单纯形法。（T ）7、对于动态规划问题，应用顺推或逆推解法可能会得岀不同的最优解。（F ） 8、动态规划的基本方程是将一个多阶段的决策问题转化为一系列具有递推关系的单阶段的决策问题。（T ） 9、图论中的图不仅反映了研究对象之间的关系，而且是真实图形的写照

5、，因而对图中点与点的相对位置、点与点连线的长短曲直等都F （严格注意。.）10、网络最短路线问题和最短树问题实质上定一个问题。（F填空题。二,1、线性规划中，满足非负条件的基木解称为_基本可行解对应的基称为可行基.;2、线性规划的目标函数的系数是其对偶问题的右端常数而若线性规划为最大化问题，则对偶问题为_最小化问题个变量构成基变星的充要条件是3、在运输问题模型中，Inm?不含闭回路最优目标函数4、动态规划方法的步骤可以总结为：逆序求解.和_最优.最优路线，顺序求_最优策略目标函数值5、工程路线问题也称为最短路问题，根据问题的不同分为定步数问题和不定步数问题;对不定步数问题,用迭代法求解，有 函

6、数迭代法和策略迭代法两种方法。6、在图论方法中，通常用点表示人们研究的对象，用_边表示对象之间的联系。7s 线性规划的最优解是(0, Ox，x,?x?2x?x6,4x?8x?maxZ?x?0U2m(O,2)=）个约束中松驰变量它的第6）,1、2 （） SS0X增加一个单位总运费增X8、运输问题的检验数的经济含义是（丽加入 四、计算题。、考虑线性规划问题：1.max?z?2x?4x?3xji:3x?4x?2x?60?3i3?40?2x2x?x?i2Js.t.?x?3x?2x?80?3i2?XAx?0?ni (a) 写出其对偶问题;(b)、用单纯形方法求解原问题;（C）、用对偶单纯形方法求解其对偶

7、问题;(d)、比较（b）（C）计算结果。1：解a）.其对偶问题为mui?z?60y?40y?80yM23y?2y?y?2?32i? 4y?y?y?4?32ts?3y?2y?22y?3u?0y?yy?mb)、用单纯形方法求解原问题时每步迭代结果：JXi_I原问题解(0, 0 0, 60 第一步，40,80)(0, 15 第二步，0, 0, 25,(0, 20/3, 50/3, 0,第三步0, 80/3)C）、用对偶单纯形方法求解对偶问题时每步迭代结果:Ii 、Eb *- 阳$ P WH对偶问题问题解(0, 0, 0, -2, -4, -3) 第一步)-1, 0, b 0, 0, 1 (第二步第三511/d）.对偶问题的实质是将单纯形法应用于对偶问题的求解，又对偶问题的对偶即原问题，因此（b）、（C）的计算结果完全相同。五.证明题:1、对问题minf (xl,x2) =x：l八2+25x2八2中的变量x=(x1a2)T作线性变换：yl=xl,y2=5x2,则原来的无约束优化问题变为:minF(yl,y2)=ylA2+y2A2证明：从任意初始点yo出发，用最速下降法问题(* *)迭代一轮 即可求得最优化解，从中你可以得到什么启示?证: 从任意初始点为yO= (y0,y2A0) T,令PO=-f(yO),