《运筹学》模拟试题及参考答案

《运筹学》模拟试题及参考答案 一、 判断题(在下列各题中，你认为题中描述的内容为正确者，在题尾括号 内写“ 错误者写“X”。) 1. 图解法提供了求解线性规划问题的通用方法. ( 2. 用单纯形法求解•般线性规划时，当目标函数求最小值时，若所有的检验数C「Zj NO,则问题达到最优。 ( 3. 在单纯形表中，基变量对应的系数矩阵往往为单位矩阵。 ( 4. 满足线性规划问题所有约束条件的解称为基本可行解。 ( 5. 在线性规划问题的求解过程中，基变量和非基变量的个数是固定的。 ( 6. 对偶问题的目标函数总是与原问题日标函数相等。 ( 7. 原问题与对偶问题是一一对应的。 ( 8. 运输问题的可行解中基变量的个数一定遵循m+n-1的规则。 ( 9. 指派问题的解中基变量的个数为m+n。 ( 10. 网络最短路径是指从网络起点至终点的一条权和最小的路线。 ( 11. 网络最大流量是网络起点至终点的一条增流链上的最大流量。 ( 12. 工程计划网络中的关键路线上事项的最早时间和最迟时间往往不相等。( 13. 在确定性存贮模型中不许缺货的条件下，当费用项目相同时，生产模型的间隔 时间比订购模型的间隔时间长。 ( 14. 单目标决策时，用不同方法确定的最佳方案往往是一致的。 ( 15. 动态规划中运用图解法的顺推方法和冋络最短路径的标号法上是一致的。 ( 二、 简述题 1. 用图解法说明线性规划问题单纯形法的解题思想。 2. 运输问题是特殊的线性规划问题，但为什么不用单纯形法求解。 3. 建立动态规划模型时，应定义状态变量，请说明状态变量的特点。 三、 填空题 1. 图的组成要素 : 。 2. 求最小树的方法有 、 。 3. 线性规划解的情形有 、 4. 求解指派问题的方法是 。 5. 按决策环境分类，将决策问题分为 6. 树连通，但不存在 四、下列表是线性规划单纯形表（求Zg、），请根据单纯形法原理和算法。 1. 计算该规划的检验数 Cj Ci 2 4 1-0-10 2 3 3.5 2 -2 0 1 1 1/2 0 2. 计算对偶问题的目标函数值 3. 确定上表中输入，输出变量 五、己知一个线性规划原问题如下, 请写出对应的对偶模型 S =6x + x max I x +x <7 I 2 2x +3x > 16 I 2六、下图为动态规划的一个图示模型，边上的数字为两点间的距离，请用逆推 法求岀S至F点的最短路径及最短路长。 七、自己选用适当的方法，对下图求最小（生成）树。 九、下图是某一工程施工网络图（统筹图），图中边上的数字为工序时间（天）, 请求出各事项的最早时间和最退时间，求出关键路线，确定计划工期。 3 5 十、某企业生产三种产品A】、Ar A3。每种产品在销售时可能出现销路 好(Sp,销路一般(SJ和销路差(S3)三种状态，每种产品在不同销售状态的获利情 况(效益值)如表1所示，请按乐观法则进行决策，选取生产哪种产品最为合适。 w态 S! S2 S3 A. 30 10 -6 A, 20 12 9 % 15 13 12 （表1） 十一、己知运输问题的运价表和发量和收量如表2所示，请用最小元素法求出 运输问题的一组可解释。 B, B, b4 Ai 2 9 12 7 9 A2 1 3 5 2 4 A3 10 4 2 6 5 3 5 4 6 俵2) 十二、下列表3是一个指派问题的效率表(工作时间表)，其中A .为工作人员(i=l, 2,3,4)、Bj为工作项目3,4),请作工作安排，使总的工作时间最小。 A\ A2 A3 A4 B1 B2 B3 B4 参考答案 一、 判断题 ⑴ X (2)V (3)V (4)X (5)J (6)X (7) V (8) V (9)X (10) V (11)X (12) X (13) V (14)X (15) X 二、 简述题 1、 在可行域内先确定一个基本可行解，然后通过迭代计算，逐步使目标函数增大(求Z(n.), 求岀新解，计算出方案机会成本后，得出相应检验数，当所有的Cj-ZjW0时即得最优解。 2、 运输问题可以用单纯形求解，但由于虚设的变量多，运算复杂，十分不合算，所以不用 单纯形法求解，而用简单的表上作业法求解。 3、 由于动态规划的求解过程是一个多段决定过程，其状态变量必须满足无后效性和可知性 的特征要求。 三、 填空题 1 .树 2. 破圈法和避圏法 3. 可行解、退化解、无界解、多重解 4. 匈牙利法 5. 确定性决策，不确定性决策，风险性决策。 6. 圈。 四、 1. C. 3 2 0 0 0 0 q X。 b X| x2 % \ X5 X6 (3) x. 3 1 0 ip 1 n IP (2) X2 4 0 1 1 1/2 -1 0 z 3 2 7/2 -2 -2 3/2 C厂Zj 0 0 (-7/2) (2) 2 -3/2 3.X4输入，*输出。 五、zmax=-7yi+,6y2 -y, +2y2 <6 -七+3)撰1 (16) 六、 s—A —B(—C —F 32 七、 选方案气 十一、 （表3） 《运筹学》试题参考答案 ♦ • 一、填空题（每空2分，共10分） 1、 在线性规划问题中，若存在两个最优解时，必有相邻的顶点是最优解。 2、 树图中，任意两个顶点间有且仅有一条链。 3、 线性规划的图解法适用于决策变量为 两个 线性规划模型。 4、 在线性规划问题中，将约束条件不等式变为等式所引入的变量被称为松弛变 5、 求解不平衡的运输问题的基本思想是设立虚供地或虚需求点，化为供求平衡 的标准形式。 6、 运输问题中求初始基本可行解的方法通常有 最小费用法 与 西北角法 两 种方法。 7、 称无圈的连通图为树，若图的顶点数为p,则其边数为p—1 。 二、(每小题5分，共10分)用图解法求解下列线性规划问题： 1) max z = 6X]+4x2 ⑴ 2x +x <10 (2) 1 2 x +x <8 (3) • I 2 x <7 (4) 2 气，X >0 (5)、(6) 2) minz=2X|+x° -x +4x <24 1 2 X +x >S ⑷、(5) ⑹ 50 2 解: 从上图分析，可行解域为abcde,最优解为e点。 由方程组 x +x =8 解出 X]=5, x2=3 -I 2 x =5 I 、 X ・.・X*= 1 = (5, 3) T 丿 :.min z =Z*= 2x5+3=13 三、(15分)一家工厂制造甲、乙、丙三种产品，需要三种资源一一技术服务、劳 动力和行政管理。每种产品的资源消耗量、单位产品销售后所能获得的利润值以 及这三种资源的储备量如下表所示： 技术服务 劳动力 行政管理 单位利润 甲 1 10 2 10 乙 1 4 2 6 丙 1 5 6 4 资源储备量 100 600 300 1） 建立使得该厂能获得最大利润的生产计划的线性规划模型；（5分） 2） 用单纯形法求该问题的最优解。（10分） 解：1）建立线性规划数学模型： 设甲、乙、丙三种产品的生产数量应为X］、x2. X3,则X］、X?、X3NO,设z 是产品售后的总利润，则 max z =10xj+6x74-4x3 s.t. x +x +x <100 1 2 3 lOx +4x +5x <600 - 1 2 3 2x +2x +6x < 300 1 2 3 x, x f x >0 1 2 3 2）用单纯形法求最优解： 加入松弛变量x4, x , 得到等效的标准模型： max z =10x.+6x+4x+0 x+0 x+0 x, 12 3 4 5 6 S.t. x +x +x =100 12 3 4 lOx +4x +5x +x =600 . 12 3 5 2x +2x +6x +x =300 1 2 3 6 x > o,y = 1,2, j 列表计算如下: 10 6 4 0 0 0 c B X B b X 1 x2 X 3 X 4 X5 X 6 9 L 0 X 4 100 1 1 1 1 0 0 100 0 X 5 600 (10) 4 5 0 1 0 60 0 X 6 300 2 2 6 0 0 1 15() 0 0 0 0 0 0 10 t 6 4 0 0 0 0 X 4 40 0 (3/5) 1/2 1 -1/10 0 200/3 10 X 1 60 1 2/5 1/2 0 1/10 0 150 0 X 6 180 0 6/5 5 0 -1/5 1 150 10 4 5 0 1 0 0 2 t -1 0 -1 0 6 X 2 200/3 0 1 5/6 5/3 -1/6 0 10 X 1 100/3 1 0 1/6 -2/3 1/6 0 0 X 6 100 0 0 4 -2 0 1 2200 10 6 20/3 10/3 2/3 0 3 0 0 -8/3 -10/3 -2/3 0 ・ v / WO 200 n ..X*= ( ， ， 0, 3 3 0, 0, 100) T max z =1OX 1 °°MX 200 _2200 3 3 3 四、（10分）用大M法或对偶单纯形法求解如下线性规划模型: min z =540X] +450x2+720x3 & +5x +9x >70 1 2 3 <9x +5x +3x >30 I 2 3 x 9x ,x > 0 I 1 2 3 解：用大M法，先化为等效的标准模型： max zj =—540X］一450乂2—720乂3 s.t. 3x +5x +9x -x =70 12 3 4 < 9x +5x +3x -x =30 12 3 5 >* 2 0,丿= 1,2,..., 5 J 增加人工变量Xq x ,得到： max 7J=—540x, —450x,—720x — Mx,—Mxn 1 2 3 6 7 3x +5x +9x -x +x =70 1 2 3 4 6 9x +5x +3x -x + +x =30 1 2 3 5 7 x > 0, j = 1,2,..., 5 j 大M法单纯形表求解过程如下: C B X B