《运筹学考试题b卷及答案》由会员分享，可在线阅读，更多相关《运筹学考试题b卷及答案（7页珍藏版）》请在金锄头文库上搜索。
1、运筹学期末考试题（b卷）注意事项：1、答题前，考生务必将自己的姓名、班级填写在答题卡上。2、答案用钢笔或圆珠笔写在答题卡上，答在试卷上不给分。3、考试结束，将试卷和答题卡一并交回。一、单项选择题（每小题1分，共10分） 1：下列关于运筹学的缺点中，不正确的是（）A. 在建立数学模型时，若简化不慎，用运筹学求得的最优解会因与实际相差大而失去意义B. 运筹学模型只能用借助计算机来处理C. 有时运筹学模型并不能描述现实世界D. 由于运筹学方法的复杂性使一些决策人员难以接受这些解决问题的方法2：在下面的数学模型中，属于线性规划模型的为（）max S = 4X + Ymin S = 3X + Ymax
2、S = X2 + Y2minS = 2XYA.s.t.XY -1C.s.t. X Y 3X,Y0X,Y0X,Y0X,Y03线性规划一般模型中，自由变量可以用两个非负变量的（ ）代换。A. 和B.商C.积D.差4：以下关系中，不是线性规划与其对偶问题的对应关系的是（）。A. 约束条件组的系数矩阵互为转置矩阵B. 一个约束条件组的常数列为另一个目标函数的系数行向量C. 两个约束条件组中的方程个数相等D. 约束条件组的不等式反向5.对偶问题的对偶是（ ）A.原问题 B.解的问题 C.其它问题D.基本问题6：若原问题中X 0,那么对偶问题中的第i个约束一定为（）iA.等式约束B. “型约束C.、仑约束
3、D.无法确定7：若运输问题已求得最优解，此时所求出的检验数一定是全部（）A.小于或等于零B.大于零C.小于零D.大于或等于零8：考虑某运输问题，其需求量和供应量相等，且供应点的个数为m,需求点的个数是n。若以西北角法求得其初始运输方案，则该方案中数字格的数目应为（ ）A. （m+n）个B. （m+n-1）个C. （m-n）个D. （m-n+1）个9：关于动态规划问题的下列命题中错误的是（）A、动态规划分阶段顺序不同，则结果不同B、状态对决策有影响C、动态规划中，定义状态时应保证在各个阶段中所做决策的相对独立性D、动态规划的求解过程都可以用列表形式实现10：若P为网络G的一条流量增广链，则P中所
4、有逆向弧都为G的（）C.零流弧D.不饱和边A.非零流弧B.饱和边二、判断题（每小题1分，共10分） 1：如线性规划问题存在最优解，则最优解一定对应可行域边界上的一个点。（ ） 2：线性规划问题的每一个基解对应可行域的一个顶点（ ） 3：若线性规划问题具有可行解，且其可行域有界，则该线性规划问题最多具有有限个数的 最优解（ ）4：对偶问题的对偶问题一定是原问题。（ ） 5：任何线性规划问题存在并具有唯一的对偶问题。（ ） 6：运输问题是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之一：有 唯一最优解，有无穷多最优解，无界解，无可行解。（ ）7： 动态规划的最优性原理保证了从某一状态
5、开始的未来决策独立于先前已做出的决策（。 ） 8：一个线性规划问题若转化为动态规划方法求解时，应严格按变量的下标顺序来划分阶段，如将决定x的值作为第一阶段，决定x的值作为第二阶段等。（） 129：在任意图中，当点集确定后，树是图中边数最少的连通图。（ ） 10：求网络最大流的问题可以归结为求解一个线性规划模型。（ ）三、填空题（每空1分，共15分）1：满足所有约束条件的一组值称为线性规划的，这些解中，使目标函数取得最大或最小值的解称为线性规划问题的。2：在单纯形法中，初始基可能由、和三种类型的变量组成。3：若原始问题可行，则其目标函数无界的充要条件是对偶问题；若对偶问题为无界解，其原问题为。4
6、：在运输问题模型中，计算检验数的方法一般有和两种方法。5：动态规划方法的步骤可以总结为：逆序求解 ，顺序求、和6：树的任意两个顶点之间有且只有一条。7：网络中满足容量限制条件和中间点平衡条件的弧上的流称为。四、计算题（每小题15分，45分）1：已知线性规划：max z = 3x + 2x12x + 2 x W 41 23 x +2 x 12S. t.彳 12x 一 x 012（a）：用单纯形方法求解该线性规划问题的最优解和最优值；（ b ）：写出线性规划的对偶问题；（c）：求解对偶问题的最优解和最优值。2：今有1000台机床，要投放到A、B两个生产部门，计划连续使用3年。已知对A部门投入u台机
7、器时的年收益是g（u ） = 4u2 （元），机器的完好率a = 0.5，相应的B部A A A门的年收益是h（u ） = 2u2 （元），完好率b = 0.9。试求3年间总收益最大的年度机器分配BB3：用破圈法和生长法求下图的最短树。也 8耳五、问答题（每小题5分，共10分）1. 简述动态规划建模的一般过程和最优性原理。2. 网络最短路线问题的求解有多种方法，一般有狄克斯拉算法、海斯算法和福德算法。试 分析各自适用的范围和优缺点。期末考试参考答案及评分标准（b卷）单项选择题（每小题1分，共10分）1.B2.B3.D4.C5.A6.C7.D8.B9.A10.A判断题（每小题1分，共10分）1.T
8、2.F3.F4.T5.T6.F7.T8.F9.T10.T填空题（每空1分，共15分）1：可行解、最优解；2：决策变量、松弛变量、人工变量；3：没有可行解、无可行解；4： 闭回路法、位势法；5：最优目标函数、最优策略、最优路线、最优目标函数值；6：初等链; 7：可行流。计算题（每小题15分，45分）1： 解 a）:18,3,32,0,05 5 5318 丄 2312max z = 3 x丄 2 x = 1255（5分）b）：其对偶问题为min w = 4 y +12 y + 3 y1 23一 y+3 y + y 3123s.t. 2123y ,y , y 0J 123（5分）c）：Y * = 0
9、,1,0，2：解该问题可以作为三段资源分配问题，每个年度是-个阶段。k阶段状态变量-取为 该年度初完好的设备数，决策变量作取为该年度投入A活动的设备数，则有0 - 1000，0 u x。状态转移方程为：x = 0.5u + 0.9(x - u )；相应的动态规划基本方程为: k kk +1kk kf (x ) = max4u2 + 2(x 一u )2 + f (x )k kkk kk +i k +iuk其中：x = 0.5u + 0.9(x 一 u )k +ikk k首先逆序求解条件最有目标函数值集合和条件最有决策集合：k = 3 时，0 u x ,注意到 f (x ) = 0，有f (x )
10、 = max4u2 + 2(x 一 u )2。最大值3333u333443 分)发生在0, x3的端点。u = 0 时,34u2 + 2(x 一 u )2 = 2x2，而 u3 3 3 3 3=x 时，4u2 + 2(x 一 u )2 = 4x23 3 3 3 3可知：f (x ) = 4 x 2，u (x ) = x3 3 3 3 3 33 分)k 二 2 时，0 u x ,注意到x二0.5u + 0.9(x - u )和上面求出的f (x )，有2 3 2 2 2 3 3f (x ) = max4u2 + 2(x 一 x )2 + f (0.5u + 0.9(x 一 u )2 2 2 2
11、2 3 2 2 2 u2=max4u2 + 2(x 一 x )2 + 405u + 0.9(x 一 u )22 2 2 2 2 2 u2最大值发生在0, x2的端点。比较u2二0和u2二=时内的值可知:f (x ) = 5.24x2, u (x ) = 02 2 2 2 23 分)k 二 1 时，0 ui xi,注意到 x2 二 0叫 + .9(xi 一 S 和上面求出的 f2(x2)，有f (x ) = max4u2 + 2(x 一 x )2 + f (0.5u + 0.9(x 一 u )1 1 1 1 1 2 1 1 1 u1=max4u2 + 2(x 一 x )2 + 5.240.5u
12、+ 0.9(x 一 u )21 1 1 1 1 1 u1最大值发生在0,xi的端点。比较ui二0和ui二xi时内的值可知:f (x ) = 6.24444x2, u (x ) = 01 1 1 1 13 分)由于x二1000已知，因此条件最优目标函数值f (x )就是整个计划周期内的最大收益R*，1 1 1其值为：R* = f (x ) = 6.2444 x 10002 = 6244400i iu* = u (1000) = 0,1 ix* = 0.5u* + 0.9(x* -u*) = 900,2 1 1 1u* = u (900) = 0,2 2x* = 0.5u* + 0.9(x -u*
13、) = 810,3 222u* = u (810) = 810,3 3x* = 0.5u* + 0.9(x* -u*) = 405,4 333最优分配方案时第一年把1000设备全部投放到部门B,阶段收入为200万元，年末完好设 备900台；第二年把900台完好设备全部全部投入部门B，年收入162万元，年末完好设备 810台；第三年把810台完好设备全部投入部门A,年收入为262.44万元，年末完好设备为 405台。三年总收入最大为624.44万元。(3分)3：解破圈法(1)：取圈 v ,v ,v ,v，去掉边v ,v 。(2)：取圈 v ,v ,v ,v，去掉边v ,v 。123113243224(3)：取圈v2, v3, v5, v2，去掉边v2,叮。：取圈v3, v4,仔叮，去掉边心忍。在图中已无圈，此时，P = 6，而q = p -1 = 5，因此所得的是最短树。结果如下图，其树的总长度为12。. (6分).-(3分)生长法根据生长法的基本原理，得以下计算表vvvvv23456S126888v23898S23898v3538S3538vS4vS5g15133据此也得到与破圈法相同的最短树。 .（6 分）简答题（每小题10分，共20分）1：动态规划建模应完成如下工作：（1）：确定阶段与阶段变量，阶
