运筹学考试题b卷附标准答案

1、运筹学期末考试题（ b 卷）注意事项：1、答题前，考生务必将自己的姓名、班级填写在答题卡上。2、答案用钢笔或圆珠笔写在答题卡上，答在试卷上不给分。3、考试结束，将试卷和答题卡一并交回。一、 单项选择题 （每小题 1 分，共 10分） 1：下列关于运筹学的缺点中，不正确的是（ ）A. 在建立数学模型时，若简化不慎，用运筹学求得的最优解会因与实际相差大而失去意义B. 运筹学模型只能用借助计算机来处理C. 有时运筹学模型并不能描述现实世界D. 由于运筹学方法的复杂性使一些决策人员难以接受这些解决问题的方法 2：在下面的数学模型中，属于线性规划模型的为（）max S 4XYminS 3X YmaxS

2、X 2 Y2minS 2XYA.s.t. XY3 B.s.t.2X Y 1 C.s.t.XY2D. s.t.XY3X,Y0X,Y 0X,Y 0X,Y 03线性规划一般模型中，自由变量可以用两个非负变量的（）代换。A和 B 商 C积 D差4：以下关系中，不是线性规划与其对偶问题的对应关系的是（）。A. 约束条件组的系数矩阵互为转置矩阵B. 一个约束条件组的常数列为另一个目标函数的系数行向量C. 两个约束条件组中的方程个数相等D. 约束条件组的不等式反向 5对偶问题的对偶是 （）A原问题 B 解的问题 C其它问题 D基本问题 6：若原问题中 xi 0 ，那么对偶问题 中的第 i 个约束一定为 （）

3、A等式约束 B “”型约束 矚慫润厲钐瘗睞枥庑赖。C“”约束 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、动态规划中，定义状态时应保证在各个阶段中所

4、做决策的相对独立性D、动态规划的求解过程都可以用列表形式实现10：若 P为网络 G 的一条流量增广链，则 P中所有逆向弧都为 G 的（）A非零流弧 B饱和边 C零流弧 D 不饱和边 残骛楼諍锩瀨濟溆塹籟。二、 判断题（每小题 1 分，共 10分） 1：如线性规划问题存在最优解，则最优解一定对应可行域边界上的一个点。（ ）2：线性规划问题的每一个基解对应可行域的一个顶点（）3：若线性规划问题具有可行解，且其可行域有界，则该线性规划问题最多具有有限个数的 最优解（ ）4：对偶问题的对偶问题一定是原问题。 （ ） 5：任何线性规划问题存在并具有唯一的对偶问题。（ ）6：运输问题是一种特殊的线性规划模

5、型，因而求解结果也可能出现下列四种情况之一：有 唯一最优解，有无穷多最优解，无界解，无可行解。 （ ） 酽锕极額閉镇桧猪訣锥。7： 动态规划的最优性原理保证了从某一状态开始的未来决策独立于先前已做出的决策。（ ）8： 一个线性规划问题若转化为动态规划方法求解时，应严格按变量的下标顺序来划分阶段，如将决定 x1 的值作为第一阶段，决定 x2的值作为第二阶段等。9：在任意图中，当点集确定后，树是图中边数最少的连通图。 10：求网络最大流的问题可以归结为求解一个线性规划模型。 三、 填空题（每空 1 分，共 15分） 1：满足所有约束条件的一组值称为线性规划的 或最小值的解称为线性规划问题的 在单纯

6、形法中，初始基可能由 贸摄尔霁毙攬砖卤庑。，这些解中，使目标函数取得最大2：三种类型的变量组成。 彈3：4：5：6：7：若原始问题可行，则其目标函数无界的充要条件是对偶问题 界解，其原问题为 。謀荞抟箧飆鐸怼类蒋薔。在运输问题模型中，计算检验数的方法一般有 动态规划方法的步骤可以总结为：逆序求解 。厦礴恳蹒骈時盡继價骚。树的任意两个顶点之间有且只有一条；若对偶问题为无和两种方法。，顺序求 、网络中满足容量限制条件和中间点平衡条件的弧上的流称为 四、计算题（每小题 15 分，45 分）1：已知线性规划：max z 3x1 2 x2s.t.x1 2x2 43x1 x2 12x1 x2 3a）：b）

7、：c）：3 年。已知对 Ax1, x2 0 用单纯形方法求解该线性规划问题的最优解和最优值； 写出线性规划的对偶问题； 求解对偶问题的最优解和最优值。2：今有 1000 台机床，要投放到 A 、B 两个生产部门，计划连续使用2部门投入 uA台机器时的年收益是 g（uA ） 4u2A（元），机器的完好率 a 0.5，相应的 B 部门的年收益是 h（uB） 2u2B（元），完好率 b 0.9。试求 3 年间总收益最大的年度机器分配方案。 茕桢广鳓鯡选块网羈泪。3：用破圈法和生长法求下图的最短树。五、问答题 （每小题 5 分，共 10分） 1简述动态规划建模的一般过程和最优性原理。2网络最短路线问题

8、的求解有多种方法，一般有狄克斯拉算法、海斯算法和福德算法。试 分析各自适用的范围和优缺点。 鹅娅尽損鹌惨歷茏鴛賴。期末考试参考答案及评分标准（b 卷）单项选择题 （ 每小题1 分，共 10 分 ）1.B2.B3.D 4.C5.A6.C7.D 8.B9.A10.A 籟丛妈羥为贍偾蛏练淨。判断题（每小题 1分，共 10 分）1.T2.F3.F 4.T5.T6.F7.T 8.F9.T10.T 預頌圣鉉儐歲龈讶骅籴。填空题（每空 1 分，共 15 分）1：可行解、最优解；2：决策变量、松弛变量、人工变量；3：没有可行解、无可行解； 4：闭回路法、位势法；5：最优目标函数、 最优策略、 最优路线、最优目

9、标函数值；6：初等链；7：可行流。 渗釤呛俨匀谔鱉调硯錦。 计算题（每小题 15 分，45 分） 1：解 a）:X*18,3,32,0,0555max z 3 18 2 3 1255b）：其对偶问题为c）：（ 5 分）min w 4y1 12y2 3y3y1 3y2 y3 3s.t. 2y1 2y2 y3 2y1, y2, y3 0 （ 5 分）Y 0,1,0 ，w* z* 4 0 12 1 3 0 12 。 (5 分)2：解 该问题可以作为三段资源分配问题， 每个年度是一个阶段。 k 阶段状态变量 xk 取为 该年度初完好的设备数， 决策变量 uk 取为该年度投入 A 活动的设备数， 则有

10、0 xk 1000 ， 0 uk xk 。状态转移方程为： xk 1 0.5uk 0.9(xk uk ) ；相应的动态规划基本方程为： fk(xk) max4 uk2 2(xk uk)2 fk 1(xk 1) 铙誅卧泻噦圣骋贶頂廡。uk其中： xk 1 0.5uk 0.9( xk uk) ( 3 分)擁締凤袜备訊顎轮烂蔷。首先逆序求解条件最有目标函数值集合和条件最有决策集合：22k 3时， 0 u3 x3, 注意到 f4(x4) 0 ，有 f3(x3) max4u32 2(x3 u3)2 。最大值 u3发生在 0, x3 的端点。2 2 2 2 2 2 u3 0时， 4u3 2(x3 u3)

11、2x3，而 u3 x3时， 4u3 2(x3 u3) 4x32可知：f3(x3) 4x3 ，u 3(x3) x3 ( 3 分)贓熱俣阃歲匱阊邺镓騷。k 2时， 0 u2 x2, 注意到 x3 0.5u2 0.9( x2 u2 ) 和上面求出的 f3 (x3) ，有22f2(x2) max4 u22 2(x2 x2)2 f3 (0.5u2 0.9(x2 u2)u2max4 u22 2(x2 x2)2 40.5u2 0.9( x2 u2)2u2最大值发生在 0, x2 的端点。比较 u2 0 和 u2 x2 时 内的值可知：2f2(x2) 5.24x22 , u2(x2) 0 ( 3 分)k 1时

12、， 0 u1 x1, 注意到 x2 0.5u1 0.9( x1 u1 )和上面求出的 f2 (x2)，有22f1(x1) max4 u12 2(x1 x1)2 f2 (0.5u1 0.9( x1 u1)u1max4 u12 2(x1 x1)2 5.240.5u1 0.9(x1 u1)2u1最大值发生在 0, x1 的端点。比较 u1 0 和 u1 x1 时 内的值可知：f1(x1) 6.24444 x12 , u1(x1) 0 (3 分)由于 x1 1000已知，因此条件最优目标函数值f1(x1) 就是整个计划周期内的最大收益 R ，其值为：R* f1(x1) 6.2444 10002 624

13、4400u1 u 1 (1000) 0,x*2 0.5u1* 0.9(x1* u1* ) 900,u2 u 2 (900) 0,x3* 0.5u2* 0.9(x2 u*2) 810, u3 u 3 (810) 810, x*4 0.5u3* 0.9(x3* u3* ) 405, 最优分配方案时第一年把 1000 设备全部投放到部门 B ，阶段收入为 200 万元，年末完好设 备 900 台；第二年把 900 台完好设备全部全部投入部门 B ，年收入 162 万元， 年末完好设备 810台；第三年把 810台完好设备全部投入部门 A ，年收入为 262.44 万元，年末完好设备为 405台。三年

14、总收入最大为 624.44万元。 (3 分)坛摶乡囂忏蒌鍥铃氈淚。3：解 破圈法(1)：取圈 v1, v2 , v3 , v1 ，去掉边 v1,v3 。(2)：取圈 v2,v4,v3,v2 ，去掉边 v2,v4。(3)：取圈 v2, v3 , v5, v2 ，去掉边 v2, v5 。( 4)：取圈 v3 , v4 ,v5, v5 ,v3 ，去掉边 v3,v4 。在图中已无圈，此时，p 6 ，而 q p 1 5 ，因此所得的是最短树。结果如下图，其6 分)树的总长度为 12 。 蜡變黲癟報伥铉锚鈰赘。3 分)生长法根据生长法的基本原理，得以下计算表v2 v3 v4 v5 v6S126v2389S

15、2389v353S353v51S451v63S53据此也得到与破圈法相同的最短树。 .（6 分）買鲷鴯譖昙膚遙闫撷凄。简答题 （每小题 10 分，共 20分）1：动态规划建模应完成如下工作：（ 1）：确定阶段与阶段变量， 阶段的划分一般是按照决策进行的时间或空间上的先后顺 序划分的，阶段数等于多段决策过程中从开始到结束所需要作出决策的数目，阶段变量用 k 表示。 綾镝鯛駕櫬鹕踪韦辚糴。（ 2）：明确状态变量和状态可能集合。 状态变量必须包含在给定的阶段上确定全部允许 决策所需要的信息。（3）：确定决策变量和决策允许集合。（ 4）：确定状态转移方程。（5）：明确阶段效应和目标。最优化原理： “最优策略具有的基本性质是：无论初始状态和初始决策如何，对于前面 决策所造成的某一状态而言，下余的决策序列比构成最优策略。 ” 驅踬髏彦浃绥譎饴憂锦。最优化原理的含义就是， 最优策略的任何一部分子策略， 也是相应初始状态的最优策略。 每个最优策略只能由最优子策略构成。 猫虿驢绘燈鮒诛髅貺庑。2：狄克斯拉算法适用的问题是所有满足lij 0 的网络，算法能求出 v1到所有其他点的最短距离，特别的，经过有限次迭代（不超过 n 次）则可求出 v1到 vn的最短距离。 锹籁饗迳 琐筆