《运筹学》期末考试试题及参考答案.pdf

第 1 页 共 11 页 运筹学试题参考答案 一、填空题每空 2 分共 10 分 1、在线性规划问题中称满足所有约束条件方程和非负限制的解为 可行解 。 2、在线性规划问题中图解法适合用于处理 变量 为两个的线性规划问题。 3、求解不平衡的运输问题的基本思想是 设立虚供地或虚需求点化为供求平衡 的标准形式 。 4、在图论中称 无圈的 连通图为树。 5、运输问题中求初始基本可行解的方法通常有 最小费用法 、 西北角法 两 种方法。 二、 每小题 5 分共 10 分用图解法求解下列线性规划问题 1max z = 6x1+4x2 0 7 8 102 21 2 21 21 xx x xx xx 解此题在“运筹学复习参考资料.doc”中已有不再重复。 2min z =3x1+2x2 0, 13 72 104 2242 21 21 21 21 21 xx xx xx xx xx 解 、 、 第 2 页 共 11 页 可行解域为 abcda最优解为 b 点。 由方程组 0 2242 2 21 x xx 解出 x1=11x2=0 X*= 2 1 x x =110T min z =311+20=33 三、 15 分某厂生产甲、乙两种产品这两种产品均需要 A、B、C 三种资源 每种产品的资源消耗量及单位产品销售后所能获得的利润值以及这三种资源的储 备如下表所示 A B C 甲 9 4 3 70 乙 4 6 10 120 360 200 300 1建立使得该厂能获得最大利润的生产计划的线性规划模型 5 分 第 3 页 共 11 页 2用单纯形法求该问题的最优解。 10 分 解1建立线性规划数学模型 设甲、乙产品的生产数量应为 x1、x2则 x1、x20设 z 是产品售后的总利 润则 max z =70x1+120x2 s.t. 0 300103 20064 36049 21 21 21 21 xx xx xx xx 2用单纯形法求最优解 加入松弛变量 x3x4x5得到等效的标准模型 max z =70x1+120x2+0 x3+0 x4+0 x5 s.t. 5,.,2 , 1,0 300103 20064 36049 521 421 321 jx xxx xxx xxx j 列表计算如下 第 4 页 共 11 页 CB XB b 70 120 0 0 0 L x1 x2 x3 x4 x5 0 x3 360 9 4 1 0 0 90 0 x4 200 4 6 0 1 0 100/3 0 x5 300 3 10 0 0 1 30 0 0 0 0 0 70 120 0 0 0 0 x3 240 39/5 0 1 0 - 2/5 400/13 0 x4 20 11/5 0 0 1 - 3/5 100/11 120 x2 30 3/10 1 0 0 1/10 100 36 120 0 0 12 34 0 0 0 12 0 x3 1860/11 0 0 1 39/11 19/11 70 x1 100/11 1 0 0 5/11 - 3/11 120 x2 300/11 0 1 0 - 3/22 2/11 11 43000 70 120 0 170/11 30/11 0 0 0 -170/11 30/11 X*= 11 100 11 300 11 1860 00T max z =70 11 100 +120 11 300 = 11 43000 四、 10 分用大 M 法或对偶单纯形法求解如下线性规划模型 min z =5x12x24x3 0, 10536 423 321 321 321 xxx xxx xxx 第 5 页 共 11 页 解用大 M 法先化为等效的标准模型 max z/ =5x12x24x3 s.t. 5,.,2 , 1, 0 10536 423 5321 4321 jy xxxx xxxx j 增加人工变量 x6、x7得到 max z/ =5x12x24x3Mx6Mx7 s.t 7,.,2 , 1, 0 10536 423 75321 64321 jx xxxxx xxxxx j 大 M 法单纯形表求解过程如下 第 6 页 共 11 页 CB XB b 5 2 4 0 0 M M L x1 x2 x3 x4 x5 x6 x7 M x6 4 3 1 2 1 0 1 0 4/3 M x7 10 6 3 5 0 1 0 1 5/3 9M 4M 7M M M M M 9M5 4M2 7M4 M M 0 0 5 x1 4/3 1 1/3 2/3 1/3 0 1/3 0 M x7 2 0 1 1 2 1 2 1 1 5 -M5/3 -M10/3 -2M+5/3 M 2M5/3 -M 0 M1/3 M2/3 2M5/3 M 3M+5/3 0 5 x1 5/3 1 1/2 5/6 0 1/6 0 1/6 10/3 0 x4 1 0 1/2 1/2 1 1/2 1 1/2 2 5 5/2 25/6 0 5/6 0 5/6 0 1/2 1/6 0 5/6 M M+5/6 5 2 x1 2/3 1 0 1/3 1 1/3 1 1/3 x2 2 0 1 1 2 1 2 1 3 22 5 2 11/3 1 1/3 1 1/3 0 0 1/3 1 1/3 M+1 M+1/3 x*= 3 2 2000T 最优目标函数值 min z =max z/ = 3 22 = 3 22 五、 15 分给定下列运输问题 表中数据为产地Ai到销地Bj的单位运费 第 7 页 共 11 页 B1 B2 B3 B4 si A1 A2 A3 1 2 3 4 8 7 6 5 9 10 11 9 10 80 15 dj 8 22 12 18 1用最小费用法求初始运输方案并写出相应的总运费 5 分 2用 1得到的基本可行解继续迭代求该问题的最优解。 10 分 解用“表上作业法”求解。 1先用最小费用法最小元素法求此问题的初始基本可行解 B1 B2 B3 B4 Si A1 1 2 3 4 10 8 2 A2 8 7 6 5 20 2 18 A3 9 10 11 9 30 20 10 dj 8 22 12 18 60 60 初始方案 Z=18+22+62+518+1020+1110=424 2 18 B3 B4 A2 20 10 B2 B3 A3 销 地 费 用 产 地 8 2 B1 B2 A1 第 8 页 共 11 页 2用闭回路法求检验数 B1 B2 B3 B4 Si A1 1 2 3 0 4 2 10 8 2 A2 8 4 7 2 6 5 20 2 18 A3 9 0 10 11 9 1 30 20 10 dj 8 22 12 18 60 60 34 =10其余 j 0 选 34 x作为入基变量迭代调整。 用表上闭回路法进行迭代调整 B1 B2 B3 B4 Si A1 1 2 3 1 4 3 10 8 2 A2 8 3 7 1 6 5 20 12 8 A3 9 0 10 11 1 9 30 20 10 dj 8 22 12 18 60 60 调整后从上表可看出所有检验数 j 0已得最优解。 最优方案为 销 地 费 用 产 地 销 地 费 用 产 地 第 9 页 共 11 页 最小运费 Z=18+22+612+58+1020+910=414 六、 8 分有甲、乙、丙、丁四个人要分别指派他们完成 A、B、C、D 四项不同的工作每 人做各项工作所消耗的时间如下表所示 A B C D 甲 2 10 9 7 乙 15 4 14 8 丙 13 14 16 11 丁 4 15 13 9 问应该如何指派才能使总的消耗时间为最少 解用 “匈牙利法”求解。 效率矩阵表示为 913154 11161413 814415 79102 59110 0532 410011 5780 54120 0)0(32 45)0(11 528)0( * * 54120 0)0(32 45)0(11 528)0( * * 行约简 12 8 B3 B4 A2 20 10 B2 B4 A3 8 2 B1 B2 A1 标号 列约简 第 10 页 共 11 页 3210)0( )0(034 45)0(13 3)0(60 * * 至此已得最优解 0001 1000 0010 0100 使总消耗时间为最少的分配任务方案为 甲C乙B丙D丁A 此时总消耗时间 W=9+4+11+4=28 七、 6 分计算下图所示的网络从 A 点到 F 点的最短路线及其长度。 此题在“运筹学参考综合习题 我站搜集信息自编.doc”中已有。 解此为动态规划之“最短路问题” 可用逆向追踪“图上标号法”解决如下 4 3 7 3 5 1 9 1 2 5 7 9 6 2 4 2 4 4 6 8 5 1 5 4 5 4 A B1 B2 B3 C1 C