运筹学试题及答案.doc

上传人:h**** 文档编号:1423534 上传时间:2019-02-25 格式:DOC 页数:11 大小:614.60KB
下载 相关 举报
运筹学试题及答案.doc_第1页
第1页 / 共11页
运筹学试题及答案.doc_第2页
第2页 / 共11页
运筹学试题及答案.doc_第3页
第3页 / 共11页
运筹学试题及答案.doc_第4页
第4页 / 共11页
运筹学试题及答案.doc_第5页
第5页 / 共11页
点击查看更多>>
资源描述

1、第 1 页 (共 页)班级: 学号:姓名: 茂名学院 2009 年成人学士学位主干课程考试卷专业:信息与计算科学 科目:运筹学题 号 一 二 三 四 五 六 七 八 九 总 分得 分阅卷人一、选择题(共 5 小题,每题 4 分)1、 如果一个线性规划问题有 n 个变量,m 个约束方程(mn),系数矩阵的数为 m,则基可行解的个数最为( C ) 。Am 个 Bn 个 C D 个mnnmC2、 在 求 最 大 流 量 的 问 题 中 , 已 知 与 起 点 相 邻 的 三 节 点 单 位 时 间 的 流 量 分 别 为 10,12,15, 则 终 点 单 位 时 间 输 出 的 最 大 流 量 为

2、 ( D )A. 等 于 27 B.大 于 或 等 于 37C.小 于 37 D.小 于 或 等 于 373、如下图中每条有向边上的数字为该边的容量限制,则从发点到收点的最大流是( C )A、18 B、11 C、12 D、16解析:用最大流标记法可得:4、用最小元素法求初始调运方案是,运输表中数字格的个数为(D)个。 A、m*n B、m+n C、m*n-1 D、m+n-15、若用 ESi表示结点 i 的最早开始时间,ES j表示结点 j 的最早开始时间,T i,j 表示活动第 2 页 (共 页)ij 的作业时间,LF i表示结点 i 的最迟完成时间,LF j表示结点 j 的最迟完成时间,则下述

3、公式中正确的是( A )A.ESj= B.ESj=max,ijiijTES min,jiijTESC.LFj= D.LFj=,ijiijLF ,ijiijLF二、填空题(共 5 小题,每题 4 分)1、求解运输问题时,常用的判断运输方案是否最优的方法,一个是闭合回路,另一个是_位势法_。2、若用三种时间估计法计算作业时间,则应先估计出最乐观时间、_悲观_时间和最可能时间。3、 Max z=3x 1+8x2+5x34x1+2x215S.t 3x1+x39线性规划问题 x 1、x 2、x 30 的标准形式是_ 答案: Max z=3x 1+8x2+5x3+0*x4+0*x54x1+2x2+x4=1

4、5S.t 3x1+x3+x5=9x1、x 2、x 3、x 4、x 504、写出线性规划问题 的对偶问题_ 0,564372.min32121xtsxZ答案: 0,04675232.5max321321yytsyu5、已知下表是制定生产计划问题的一张 LP 最优单纯形表(极大化问题,约束条件均为“”型不等式) ,其中 x4、x 5、x 6为松弛变量。XB b x 1 x 2 x 3 x4 x 5 x6x 1 2 1 1 0 2 0 1x 3 2/3 0 0 1 1 0 4第 3 页 (共 页)x5 1 0 -2 0 1 1 6Cj -Zj 0 0 0 -4 0 -9对偶问题的最优解:_答案:Y=

5、(4,0,9,0,0,0) T3、计算题(共 6 小题,每题 10 分)1、用单纯形法求线性规划问题 max z = 10x1 + 5x23x1 + 4x2 95x1 + 2x2 8x1,x20解:在问题的约束条件中分别加入松弛变量 x3,x 4,得该线性问题的标准型max z = 10x1 + 5x23x1 + 4x2 + x3 = 95x1 + 2x2 + x4 = 8x1,x2,x3,x40初始单纯形表x1 x2 x3 x4x3 9 3 4 1 0x4 8 5 2 0 1-z 0 10 5 0 0 x 1为进基变量,min9/3,8/5=8/5 x 4为出基变量以 x1代替 x4,进行旋

6、转运算,得x1 x2 x3 x4x3 21/5 0 14/5 1 -3/5x1 8/5 1 2/5 0 1/5-z -80/5 0 1 0 -2 x 2为进基变量,min 21/5/14/5 , 8/5/2/5 =3/2 x 3为出基变量以 x2代替 x3,进行旋转运算,得x1 x2 x3 x4x2 3/2 0 1 5/14 -3/14x1 1 1 0 -1/7 2/5-z -35/2 0 0 -5/14 -25/14 最优解 x = (1,3/2,0,0)T第 4 页 (共 页) 目标函数的最大值 z = 35/22、用动态规划的方法求出 AD 的最短路径。答案:最短路径为 AB3C1D 为

7、 213、已知线性规划问题Max z=2x1+x2+5x3+6x4 对偶变量2x1 +x3 +x48 y12x1+2x2 + x3 +2x412 y2Xj0, j=1,2.。 。 。4其对偶问题的最优解为 y1* =4, y 2*=1,试应用对偶问题的性质,求原问题的最优解。第 5 页 (共 页)4、用标号法求如图下所示网络的最大流和最小截集(割集),每弧旁的数字是( ) 。ijijfc,V1 (4,2) V3(6,6) (6,4)VS (3,1) (3,0) (4,1) Vt(5,3) (7,5)V2 (4,4) V4解:(1)标号过程首先给 Vs 标上(0,+) 。检查 Vs,在弧(Vs,

8、V1)上,fs1=Cs1=6,不满足标号条件。在弧(Vs,V2)上,fs2Cs2,给 V2 标号(Vs,l(V2) )l(V2)=minl(Vs) , (Cs2-fs2)=min+,2=2检查 V2,在弧(V2,V4)上,f24=C24=3,不满足标号条件。在弧(V1,V2)上,f12C12,给 V1 标号(-V2,l(V1) )l(V1)=minl(V2),f12=min2,1=1检查 V1,在弧(V1,V3)上,f13C13,给 V3 标号(V1,l(V3) )l(V3)=minl(V1),(C13-f13)=min1,2=1在弧(V1,V4)上,f14C14,给 V4 标号(V1,l(V

9、4) )第 6 页 (共 页)L(V4)=minl(V1),(C14-f14)=min1,3=1在 V3,V4 中任选一个进行检查,例如,在弧(V4,Vt)上,f4tC4t,给 Vt 标号(V4,l(Vt) )L(Vt)=minl(V4),(C4t-f4t)=min1,2=1(2)调整过程按点的第一个标号找到一条增广链,如下图双箭头V1(-V2,1) (4,2) V3(V1,1)(6,6) (6,4)(0,+)V S (3,1) (3,0) (4,1) Vt(V4,1)(5,3) (7,5)V2 (Vs,2) (4,4) V4(V1,1)易见 u+=(Vs,V2),(V1,V4),(V4,Vt

10、)u-=(V1,V2)按 =1 在 u 上调整 f。u+上:fs2+ =3+1=4f14+ =0+1=1f4t+ =5+1=6 u上:f12- =1-1=0 其余 fij 不变。调整后得到下图所示可行流V1 (4,2) V3(6,6) (6,4)(0,+)V S (3,0) (3,1) (4,1) Vt(5,4) (7,6)V2(Vs,1) (4,4) V4重复上述步骤:开始给 Vs 标以(0,+) ,于是检查 Vs,给 V2 标以(Vs,1) ,检查 V2,弧(V2,V4)上,f24=C24,弧(V1,V2)上,f12=0,均不符合条件,标号过程无法继续下去,算法结束。最大流为:V(f)=f

11、s1+fs2=f3t+f4t=10最小截集:(V1, )=(Vs,V1),(V2,V4)=101第 7 页 (共 页)5、某地区有 4 个化肥厂,估计每年可供应的数量为 A1 -20 万吨、A 2 -30 万吨、A 3 -40 万吨、 A4-60 万吨,销往 5 个城市,每年每个地区的需求量为 B1- 25 万吨、B 2-15 万吨、B3-35 万吨、B 4-45 万吨、B 5-30 万吨。已知从各化肥厂到各城市的每吨化肥的运价如下表所示(单位:万元) 。 销地产地B1 B2 B3 B4 B5 产量A1 6 9 4 8 5 20A2 10 6 12 8 7 30A3 6 5 9 20 9 40

12、A4 2 13 6 14 3 60销量 25 15 35 45 30请用伏格尔法求出其运费最少的方案。答案:销地产地B1 B2 B3 B4 B5 行差额A1 6 9 4 8 5 1A2 10 6 12 8 7 1A3 6 5 9 20 9 1A4 2 13 6 14 3 1列差额 4 1 2 0 2销地产地B1 B2 B3 B4 B5 产量(剩)A1 20A2 30A3 40A4 25 60(35)销量 25 15 35 45 30销地产地B1 B2 B3 B4 B5 行差额A1 6 9 4 8 5 1A2 10 6 12 8 7 1A3 6 5 9 20 9 4A4 2 13 6 14 3

13、3列差额 4 1 2 0 2第 8 页 (共 页)销地产地B1 B2 B3 B4 B5 产量(剩)A1 20A2 30A3 15 40(25)A4 25 60(5)销量 25 15 35 45 30销地产地B1 B2 B3 B4 B5 行差额A1 6 9 4 8 5 1A2 10 6 12 8 7 1A3 6 5 9 20 9 0A4 2 13 6 14 3 3列差额 4 1 2 0 2销地产地B1 B2 B3 B4 B5 产量(剩)A1 20A2 30A3 15 40(25)A4 25 30 60(5)销量 25 15 35 45 30销地产地B1 B2 B3 B4 B5 行差额A1 6 9

14、 4 8 5 4A2 10 6 12 8 7 4A3 6 5 9 20 9 11A4 2 13 6 14 3 8列差额 4 1 2 0 2销地产地B1 B2 B3 B4 B5 产量(剩)A1 20第 9 页 (共 页)A2 30A3 15 25 40(0)A4 25 30 60(5)销量 25 15 35 45 30销地产地B1 B2 B3 B4 B5 行差额A1 6 9 4 8 5 4A2 10 6 12 8 7 4A3 6 5 9 20 9 11A4 2 13 6 14 3 8列差额 4 1 2 0 2销地产地B1 B2 B3 B4 B5 产量(剩)A1 20A2 30A3 15 25 4

15、0(0)A4 25 5 30 60(0)销量 25 15 35 45 30销地产地B1 B2 B3 B4 B5 行差额A1 6 9 4 8 5 4A2 10 6 12 8 7 4A3 6 5 9 20 9 11A4 2 13 6 14 3 8列差额 4 1 8 0 2销地产地B1 B2 B3 B4 B5 产量(剩)A1 5 20(15)A2 30A3 15 25 40(0)A4 25 5 30 60(0)销量 25 15 35 45 30第 10 页 (共 页)销地产地B1 B2 B3 B4 B5 行差额A1 6 9 4 8 5 8A2 10 6 12 8 7 8A3 6 5 9 20 9 1

16、1A4 2 13 6 14 3 8列差额 4 1 8 0 2销地产地B1 B2 B3 B4 B5 产量(剩)A1 5 15 20(0)A2 30 30(0)A3 15 25 40(0)A4 25 5 30 60(0)销量 25 15 35 45 30令 u1=0,则 u2=0、u3=5、u4=2、v1=0、v2=0、v3=4、v4=8、v5=1销地产地B1 B2 B3 B4 B5 uiA1 4 8 u1=0A2 8 u2=0A3 5 9 u3=5A4 2 6 3 u4=2vj v1=0 v2=0 v3=4 v4=8 v5=1得出(u i+vj):销地产地B1 B2 B3 B4 B5 uiA1 0 0 4 8 1 u1=0A2 0 0 4 8 1 u2=0A3 5 5 9 13 6 u3=5A4 2 2 6 10 3 u4=2vj v1=0 v2=0 v3=4 v4=8 v5=1检验数 Cij - (ui+vj)都大于 0,所以为最优解。Cij - (ui+vj):

展开阅读全文
相关资源
相关搜索
资源标签

当前位置:首页 > 教育教学资料库 > 试题真题

Copyright © 2018-2021 Wenke99.com All rights reserved

工信部备案号浙ICP备20026746号-2  

公安局备案号:浙公网安备33038302330469号

本站为C2C交文档易平台,即用户上传的文档直接卖给下载用户,本站只是网络服务中间平台,所有原创文档下载所得归上传人所有,若您发现上传作品侵犯了您的权利,请立刻联系网站客服并提供证据,平台将在3个工作日内予以改正。