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

《2022年《运筹学》期末考试试题及参考答案 .pdf》由会员分享，可在线阅读，更多相关《2022年《运筹学》期末考试试题及参考答案 .pdf（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、 =3x1+2x20,137210422422121212121xxxxxxxxxx解：、名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 1 页，共 11 页 - - - - - - - - - 可行解域为 abcda ，最优解为 b 点。由方程组02242221xxx解出 x1=11，x2=0 X*=21xx=（11，0）Tmin z =3 11+20=33 三、 （15 分）某厂生产甲、乙两种产品，这两种产品均需要A、B、C 三种资源，每种产品的资源消耗量及单位

3、产品销售后所能获得的利润值以及这三种资源的储备如下表所示：ABC甲94370乙46101203602003001）建立使得该厂能获得最大利润的生产计划的线性规划模型；（5 分）名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 2 页，共 11 页 - - - - - - - - - 2）用单纯形法求该问题的最优解。 （10 分）解：1）建立线性规划数学模型：设甲、乙产品的生产数量应为x1、x2，则 x1、x20，设 z 是产品售后的总利润，则max z =70 x1+

4、120 x2s.t. 0300103200643604921212121xxxxxxxx，2）用单纯形法求最优解：加入松弛变量 x3，x4，x5，得到等效的标准模型：max z =70 x1+120 x2+0 x3+0 x4+0 x5s.t. 5,.,2,1,03001032006436049521421321jxxxxxxxxxxj列表计算如下：名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 3 页，共 11 页 - - - - - - - - - CBXBb 7

5、0 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 70 1200 0 0 0 x3240 39/5 0 1 0 - 2/5 400/13 0 x420 （11/5 ）00 1 - 3/5 100/11 120 x230 3/1010 0 1/10 100 36 120 0 0 12 340 0 0 120 x31860/11 0 0 139/1119/11 70 x1100/11 100 5/11 - 3/11 120 x2300/11 01 0

6、 - 3/22 2/11 114300070 120 0 170/11 30/11 0 0 0 -170/11 30/11X*=（11100，11300，111860，0，0）Tmax z =7011100+12011300=1143000四、 （10 分）用大 M 法或对偶单纯形法求解如下线性规划模型：min z =5x12x24x30,10536423321321321xxxxxxxxx名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 4 页，共 11 页 - -

7、 - - - - - - - 解：用大 M 法，先化为等效的 标准模型：max z/ =5x12x24x3s.t. 5,.,2 , 1,01053642353214321jyxxxxxxxxj增加人工变量 x6、x7，得到：max z/ =5x12x24x3Mx6Mx7s.t 7,.,2 , 1,0105364237532164321jxxxxxxxxxxxj大 M 法单纯形表求解过程如下：名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 5 页，共 11 页 - -

8、 - - - - - - - CBXBb 5 2 4 0 0 MMLx1x2x3x4x5x6x7Mx64 （3）1 2 1 0 1 0 4/3 Mx710 6 3 5 0 1 0 1 5/3 9M4M7MMMMM9M54M27M4MM0 0 5 x14/3 1 1/3 2/3 1/3 0 1/3 0 Mx72 01 1 （2）1 2 1 1 5- M 5/3-M10/3-2M+5/3M2M 5/3- M0M1/3M2/32M 5/3M3M +5/305 x15/3 1 1/2 5/60 1/6 0 1/6 10/3 0 x41 0 （1/2 ）1/2 11/2 1 1/2 2 5 5/2 25

9、/6 05/6 0 5/60 1/2 1/6 0 5/6 MM+5/65 2 x12/3 1 0 1/3 1 1/3 1 1/3x22 0 11 2 1 2 13225 2 11/3 1 1/3 1 1/3 0 0 1/3 1 1/3 M+1 M+1/3 x*=（32，2，0，0，0）T最优目标函数值min z =max z/=（322）=322五、 （15 分）给定下列运输问题： （表中数据为产地Ai到销地Bj的单位运费）名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - -

10、 第 6 页，共 11 页 - - - - - - - - - B1B2B3B4siA1A2A31 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）先用最小费用法（最小元素法）求此问题的初始基本可行解：B1B2B3B4SiA112341082A2876520218A3910119302010dj822121860 60 初始方案：Z=18+22+62+518+1020+1110=424 2

11、18 B3B4A220 10 B2B3A3销地费用产地8 2 B1B2A1名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 7 页，共 11 页 - - - - - - - - - 2）用闭回路法，求检验数：B1B2B3B4SiA11230 421082A284726520218A390101191302010dj822121860 60 34=10，其余j0 选34x作为入基变量迭代调整。用表上闭回路法进行迭代调整：B1B2B3B4SiA11231 431082A2

12、8371652012 8A390101119302010dj822121860 60 调整后，从上表可看出，所有检验数j0，已得最优解。最优方案为：销地费用产地销地费用产地名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 8 页，共 11 页 - - - - - - - - - 最小运费 Z=18+22+612+58+1020+910=414 六、 （8 分）有甲、乙、丙、丁四个人，要分别指派他们完成A、B、C、D 四项不同的工作，每人做各项工作所消耗的时间如下表所示

13、：A B C D 甲2 10 9 7 乙15 4 14 8 丙13 14 16 11 丁4 15 13 9 问：应该如何指派，才能使总的消耗时间为最少？解：用 “匈牙利法”求解。效率矩阵表示为：91315411161413814415791025911005324100115780541200)0(3245)0(11528)0(*541200)0(3245)0(11528)0(*行约简12 8 B3B4A220 10 B2B4A38 2 B1B2A1标号列约简名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - -

14、 - - - - - - - - - 第 9 页，共 11 页 - - - - - - - - - 3210)0()0(03445)0(133)0(60*至此已得最优解：0001100000100100使总消耗时间为最少的分配任务方案为：甲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

15、 5 1 5 4 5 4 A B1 B2 B3 C1 C2 C3 D1 D2 D3 E1 E2 F名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 10 页，共 11 页 - - - - - - - - - 最佳策略为： AB2C1D1E2F 此时的最短距离为5+4+1+2+2=14 1 7 3 4 3 2 0 1 2 5 7 9 6 2 4 2 4 4 6 8 5 1 5 4 5 4 A B1 B2 B3 C1 C2 C3 D1 D2 D3 E1 E2 F5 9 1 4 7 7 11 8 5 9 12 14 14 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 11 页，共 11 页 - - - - - - - - -