最新--运筹学期末考试试题及答案.pdf
学习 -好资料 更多精品文档 楚大 2012-2013上学期 经济信息管理及计算机应用系 运筹学期末考试试题及答案 班级：学号 一、单项选择题： 1、在下面的数学模型中，属于线性规划模型的为（A ） 。 0Y,X 1YX2. t . s YX3Smin .B 0Y,X 3XY. t . s YX4Smax .A 0Y,X 2YX. t . s YXSmax .C 22 0Y,X 3YX. t . s XY2Smin .D 2、线性规划问题若有最优解，则一定可以在可行域的（A）上 达到。 A顶点 B内点 C外点 D几何点 3、在线性规划模型中，没有非负约束的变量称为（C ） A多余变量B松弛变量C.自由变量D人工变量 4、若线性规划问题的最优解同时在可行解域的两个顶点处达到，那 么该线性规划问题最优解为（C ） 。 A.两个B.零个C.无穷多个D.有限多个 5、线性规划具有唯一最优解是指（B ） A最优表中存在常数项为零B最优表中非基变量检验数全部非零 C最优表中存在非基变量的检验数为零D可行解集合有界 6、设线性规划的约束条件为 学习 -好资料 更多精品文档 0, 422 3 41 421 321 xx xxx xxx 则基本可行解为（C ） 。 A(0, 0, 4, 3) B (3, 4, 0, 0) C(2, 0, 1, 0) D (3, 0, 4, 0) 7、若运输问题已求得最优解，此时所求出的检验数一定是全部 （ D ） A、小于或等于零B大于零C小于零D大 于或等于零 8、对于 m 个发点、 n 个收点的运输问题，叙述错误的是( D ) A该问题的系数矩阵有m×n 列B该问题的系数矩 阵有 m+n 行 C该问题的系数矩阵的秩必为m+n-1 D该问题的最优解 必唯一 9、关于动态规划问题的下列命题中错误的是（A ） A、动态规划分阶段顺序不同，则结果不同 B、状态对决策有影响 C、动态规划中，定义状态时应保证在各个阶段中所做决策的相对独 立性 D、动态规划的求解过程都可以用列表形式实现 10、若 P 为网络 G 的一条流量增广链，则P中所有正向弧都为G 的 （ D ） 学习 -好资料 更多精品文档 A对边B饱和边C邻边D不饱 和边 一、判断题。 1、图解法和单纯形法虽然求解的形式不同，但从几何上理解，两者 是一致的。（ T ） 2、单纯形法的迭代计算过程是从一个可行解转换到目标函数值更大 的另一个可行解。（ F ） 3、一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的 数字可以从单纯形表中删除，而不影响计算结果。（ T ） 4、若线性规划问题中的,ij b c值同时发生改变，反映到最终单纯形表 中，不会出现原问题与对偶问题均为非可行基的情况。（ F ） 5、若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有 无穷多最优解。（ T ） 6、运输问题的表上作业法实质上就是求解运输问题的单纯形法。 （ T ） 7、对于动态规划问题，应用顺推或逆推解法可能会得出不同的最优 解。 （ F ） 8、动态规划的基本方程是将一个多阶段的决策问题转化为一系列具 有递推关系的单阶段的决策问题。 （T ） 9、图论中的图不仅反映了研究对象之间的关系，而且是真实图形的 写照，因而对图中点与点的相对位置、点与点连线的长短曲直等都要 严格注意。（F ） 学习 -好资料 更多精品文档 10、网络最短路线问题和最短树问题实质上是一个问题。（F ） 二、填空题。 1、线性规划中，满足非负条件的基本解称为_基本可行解 _， 对应的基称为 _可行基 _。 2、线性规划的目标函数的系数是其对偶问题的_右端常数 _； 而若线性规划为最大化问题，则对偶问题为_最小化问题 _。 3、在运输问题模型中，1mn个变量构成基变量的充要条件是_ 不含闭回路 _。 4、动态规划方法的步骤可以总结为：逆序求解_最优目标函数 _，顺序求 _最优策略 _、_最优路线 _和_最优 目标函数值 _。 5、工程路线问题也称为最短路问题，根据问题的不同分为定步数问 题和不定步数问题；对不定步数问题，用迭代法求解，有_函数_ 迭代法和 _策略_迭代法两种方法。 6、在图论方法中，通常用_点_表示人们研究的对象，用_边 _表示对象之间的联系。 7、线性规划0, 84 ,62,max21212121xxxxxxxxZ的最优解是 (0， 6),它的第 1、2 个约束中松驰变量 （21,S S）= （(0,2) ） 8、运输问题的检验数ij的经济含义是（ xij增加一个单位总运费增 加 ij） 四、计算题。 1、考虑线性规划问题： 学习 -好资料 更多精品文档 123 123 123 123 123 6 max243 3420 40 80 22 . . 32 ,0, zxxx xxx xxx s t xxx x xx （a） 、写出其对偶问题； （b） 、用单纯形方法求解原问题； （c） 、用对偶单纯形方法求解其对偶问题； （d） 、比较（ b） （c）计算结果。 1：解a） 、其对偶问题为 123 123 123 123 123 min604080 32 4 . . 2 222 , 3 , 4 0 zyyy yyy yyy s t yyy yyy b） 、用单纯形方法求解原问题时每步迭代结果： 原问题解 第一步 第二步 第三步 （0，0，0，60，40，80） （0，15，0，0，25，35） （0，20/3，50/3，0，0，80/3） c） 、用对偶单纯形方法求解对偶问题时每步迭代结果： 对偶问题问题解 第一步 学习 -好资料 更多精品文档 第二步 第三步 （0，0，0，-2，-4，-3） （1，0，0，1，0，-1） （5/6，2/3，0，11/6，0，0） d） 、对偶问题的实质是将单纯形法应用于对偶问题的求解，又对偶问 题的对偶即原问题，因此（b） 、 （c）的计算结果完全相同。 五、证明题： 1、对问题 minf（x1,x2）=x12+25x22中的变量 x=(x1,x2)T作线性变 换：y1=x1,y2=5x2, 则原来的无约束优化问题变为： minF(y1,y2)=y12+y22 证明：从任意初始点y0 出发，用最速下降法问题（* *）迭代一轮 即可求得最优化解，从中你可以得到什么启示？ 证： 从任意初始点为y0=（y10,y20）T，令 P0=-f(y0),则代入 f(y)=(1+2t)2(y10)2+(y20)2,令 df/dt=0 学习 -好资料 更多精品文档 得 t0=-1/2,故 y1=y0+tp0=(0,0)T 为原问题的最优解，可知，若（UMP）具有 Minf(x)= Xi2 形式，用最速下降法迭代一次即可求得最优解。 3 i ),( k kkkk usgR 3 ),( ki kkkk usgR 3 ),( ki kkkk usgR
