2022年《运筹学》期末考试试题及参考答案

1、学习资料收集于网络，仅供参考运筹学试题 参考答案一、填空题（每空 2 分，共 10 分）1、在线性规划问题中，称满足所有约束条件方程和非负限制的解为 可行解。2、在线性规划问题中，图解法适合用于处理 变量 为两个的线性规划问题。3、求解不平衡的运输问题的基本思想是 的标准形式。设立虚供地或虚需求点，化为供求平衡4、在图论中，称无圈的连通图为树。最小费用法、西北角法两5、运输问题中求初始基本可行解的方法通常有种方法。二、（每小题 5 分，共 10 分）用图解法求解下列线性规划问题：1）max z = 6x1+4x2102x 1x2x 1x28x27x 1，x20、解： 此题在“ 运筹学复习参考资

2、料.doc” 中已有，不再重复。2）min z =3x1+2x2 2 x 1 4 x 2 22 x 1 4 x 2 10 2 x 1 x 2 7 x 1 3 x 2 1 x 1 , x 2 0 、解：学习资料学习资料收集于网络，仅供参考可行解域为 abcda，最优解为 b 点。由方程组2x14x222解出 x1=11，x2=0 x 20X*=x 1=（11，0）Tx 2min z =311+2 0=33 三、（15 分）某厂生产甲、乙两种产品，这两种产品均需要 A、B、C 三种资源，每种产品的资源消耗量及单位产品销售后所能获得的利润值以及这三种资源的储备如下表所示：A B C甲 9 4 3 7

3、0乙 4 6 10 120360 200 3001）建立使得该厂能获得最大利润的生产计划的线性规划模型；（5 分）学习资料学习资料收集于网络，仅供参考 2）用单纯形法求该问题的最优解。 （10 分）解： 1）建立线性规划数学模型：设甲、乙产品的生产数量应为 润，则x1、x2，则 x1、x20，设 z 是产品售后的总利max z =70 x1+120 x2 s.t. 9x1x4x23604x16x22003x110 x2300 x1，202）用单纯形法求最优解：加入松弛变量 x3，x4，x5，得到等效的标准模型：max z =70 x1+120 x2+0 x3+0 x4+0 x5 s.t. 9x

4、14x22x3x53604x16x2x42003x110 x1 ,2 ,., 5300 xj,0j列表计算如下：学习资料学习资料收集于网络，仅供参考CBXBb 70 120 0 0 0 Lx1x2x3x4x50 x3360 9 4 1 0 0 90 0 x4200 4 6 0 1 0 100/3 0 x5300 3（10）0 0 1 30 0 0 0 0 0 400/13 70 1200 0 0 0 x3240 39/5 0 1 0 - 2/5 0 x420 （11/5 ）00 1 - 3/5 100/11 120 x230 3/1010 0 1/10 100 36 120 0 0 12 34

5、0 0 0 120 x31860/11 0 0 139/1119/11 70 x1100/11 100 5/11 - 3/11 120 x2300/11 01 0 - 3/22 2/11 4300070 120 0 170/11 30/11 X*=（100 ，1111 0 0 300 ，1860，0，0） T11 11100 +120300 = 4300011 11 110 -170/11 30/11max z =70四、（10 分）用大 M 法或对偶单纯形法求解如下线性规划模型：min z =5x12x24x33x 1xx22x34x 26x 135x 310 x 1,2,x 30学习资料学

6、习资料收集于网络，仅供参考 解：用大 M 法，先化为等效的 标准模型：max z / =5x12x24x3 s.t. 3x 1x222x 3x 4x 546x 13x5x 310yj0 ,j,12,., 5增加人工变量 x6、x7，得到：max z / =5x12x24x3M x6Mx7 s.t 3x 1x222x 3x 4x 5x 6x 746x 13x5x 310 xj0,j,12,., 7大 M 法单纯形表求解过程如下：学习资料学习资料收集于网络，仅供参考CBXBb 5 2 4 0 0 MMLx1x2x3x4x5x6x7Mx64 （3）1 2 1 0 1 0 4/3 Mx710 6 3

7、5 0 1 0 1 5/3 5 x19M4M7MMMMMMM4M 2 0 0 9M 57M 4 0 1/3 1/3 0 4/3 1 1/3 2/3 Mx72 01 1 （ 2）1 2 1 1 5 5- M 5/3-M 10/3-2 M +5/3M2M 5/3- M10/3 0M 1/3M 2/32M 5/3 M3M +5/30 x15/3 1 1/2 5/60 1/6 0 1/6 0 x41 0 （1/2 ）1/2 11/2 1 1/2 2 5 x15 5/2 25/6 05/6 0 5/60 1/2 1/6 0 5/6 MM+5/62/3 1 0 1/3 1 1/3 1 1/32 x22 0

8、 11 2 1 2 1225 2 11/3 1 1/3 1 1/3 30 0 1/3 1 1/3 M+1 M+1/3 2x*=（ 3，2，0，0，0）T学习资料学习资料收集于网络，仅供参考最优目标函数值min z =max z/=（ 22 ）= 3223五、（15 分）给定下列运输问题： （表中数据为产地 A i 到销地 Bj 的单位运费）B1 B2 B3 B4 siA 1 1 2 3 4 10 A 2 8 7 6 5 80 A 3 9 10 11 9 15 dj 8 22 12 18 1）用最小费用法求初始运输方案，并写出相应的总运费；（5 分）2）用 1）得到的基本可行解，继续迭代求该问题

9、的最优解。（10 分）解：用“ 表上作业法” 求解。1）先用最小费用法 （最小元素法） 求此问题的初始基本可行解：费销地1B182B223B34B4Si用产地10A1A2887226122518182091011930A3201060 dj60 初始方案：学习资料 A18 B1A22 B3A320 B22 B218 B410 B3学习资料收集于网络，仅供参考Z=1 8+2 2+6 2+5 18+10 20+11 10=424 2）用 闭回路法 ，求检验数：费销B223B30 4B42Si产用地B1地A118210A28 4722261225181820119A39010130201060 dj

10、860 34 =10，其余j 0 选x 作为入基变量迭代调整。用 表上闭回路法 进行迭代调整：费销地1B182B223B31 4B43Si用产地A110A28 371612 5820A390102011191030学习资料学习资料收集于网络，仅供参考dj822121860 60 调整后，从上表可看出，所有检验数最优方案为：j 0，已得最优解。A18 B1A212 B3A320 B22 B28 B410 B4最小运费 Z=1 8+2 2+6 12+5 8+10 20+9 10=414 六、（8 分）有甲、乙、丙、丁四个人，要分别指派他们完成 人做各项工作所消耗的时间如下表所示：A、B、C、D 四

11、项不同的工作，每甲A B C D 2 10 9 7 乙15 4 14 8 丙13 14 16 11 丁4 15 13 9 问：应该如何指派，才能使总的消耗时间为最少？解：用 “ 匈牙利法” 求解。效率矩阵表示为：21097行约简0875列约简154148110104标号13141611235041513901195学习资料学习资料收集于网络，仅供参考(0 )8* 02)65(0 )3(0)82511(0)5411(0 )5423(00*23(0 )0* 012450*124513(0)051443* 0(0 )(0)102300至此已得最优解：010000011000使总消耗时间为最少的分配任务方案为：甲C，乙 B，丙 D，丁 A 此时总消耗时间 W=9+4+11+4=28 七、（6 分）计算下图所示的网络从A 点到 F 点的最短路线及其长度。此题在“ 运筹学参考综合习题 （我站搜集信息自编） .doc” 中已有。A 3 5 B1 9 C1 1 D1 4 E1 1 F5 5 2 4 8 6 4 B2 3 C2 4 D2 9 E2 2 5 6 B3 1 4 4 7 5 7 C3 2 D3 学习资料学习资料收集于网络，仅供参考解：此为动态规划之“ 最短路问题”学习资料，可用逆向追踪“ 图上标