《运筹学期末考试试卷B卷》由会员分享,可在线阅读,更多相关《运筹学期末考试试卷B卷(13页珍藏版)》请在金锄头文库上搜索。
1、福建农林大学考试试卷 ( B )卷 学年 第 学期课程名称: 运 筹 学 考试时间 120分钟 专业 年级 班 学号 姓名 题号一二三四五六七八九总得分得分评卷人签字复核人签字得分一、填空题(每空2分,共10分)1. 目标规划模型中,目标约束中的称为 目标值 。2. 线性规划问题的单纯形法中,有最优解的判别准则是 所有检验数非负且最优值为常数 。3. 如果流中所有,则称是 零 流。4. 如果,为最优基,则为。5. 无向图中的环是 端点重合的边 。得分二、单项选择题(选择正确答案的字母填入空格处,每小题2分,共10分)1.线性规划的非对称形式的原问题和对偶问题数学模型中,互补松弛性的描述式为 C
2、 。A. B. C. D2. 若为最大截集,则 C 。A. 为最小截量 B. 为最大流流量C. 为的截量 D. 为最小截量3. 最短路求解的主要内容是 D 。A. 关键路线 B. 最短路线C. 最短路长 D. 最短路线和最短路长4. 线性规划问题的价值系数变化后,当最优表中 B 不发生变化。A. 非基变量检验数 B. 限定常数、技术系数和基变量检验数C. 检验数 D. 目标函数值的相反数5. 网络计划中关键工序aij的TFij C 。A.0 B.0C.=Lj-Ei-Tij D.=Lj得分三、判断题(正确打“”;错误打“”;每小题2分,共10分)1. 在增广链上确定的流量调整量只能是负的。( )
3、2. 目标规划模型中必须有目标约束。( )3. 线性规划问题有最优解。( )4. 网络计划中,非关键路线上工序的施工时间延长可能导致工期延长。( )5. 树中可能存在环。( )得分四、问答题(每小题5分,共20分)1. 闭回路的定义及应用。mn表可以划分为mn个格,一个格也可以称为一个点,在不同的mn表中,格或点代表不同的含义。取产销平衡表来介绍闭回路定义。在产销平衡表中取偶数个点,若这些点满足 或满足 则称这些点构成一条闭回路。闭回路用来进行方案调整,计算检验数,判断可行解是否基本解等等。2. 最大流问题的线性规划模型。3. 线性规划模型的特点。略。4. 目标规划模型中目标约束的结构。略。得
4、分五、(第一小题5分,第二小题3分,第三小题2分,共10分)对:要求:1.,用单纯形法求解;2.画出可行域;3.指出变动下的最优解。解: 单纯形法求解如下:cj-1 -1 0 0 -McBxBbx1 x2 x3 x4 x50-Mx3x51051 1 1 0 0 -1 0 -1 110/15/1z5 M-1+ M -1- M 0 -M 0cj-1 -1 0 0 -McBxBbx1 x2 x3 x4 x50-1x3x1550 2 1 1 -1 -1 0 -1 110/15/1z5 0 -2 0 -1 1-M。2.可行域如下:x2x1o551010ABDP3. 变动下的最优解。序号最优解12345
5、6说明:。得分六、(10分)用破圈法或避圈法求图1的最大生成树,并指出其权重和(10分) 15V6443121597163V35V7V2V1V4V5V8154104图1解:避圈法:首先确定应选的边数为顶点数减1,即应选7条边。所选的边染上红色,旁边标明选边序号,结果如下图所示。15V6443121597163V35V7V2V1V4V5V8154104图1最大生成树权为85.避圈法略。得分七、(10分)对,要求1求解2给出一个合理的实际意义。解:单纯形法求解过程见下表,据下表得 0 0 P1 P1 0 P2 P110 1 1 1 1 0 01005 2 0 0 1 15P1P2100 1 1 0
6、 2 0 0 0 0 0 0 0 1 0 0 P1 P1 0 P2 P15 0 1 1 1 1 505 1 2 0 0 1 1P1P250 0 1 0 2 1 1 0 0 0 0 0 1P25 0 1 1 1 1 010 1 1 1 1 0 0P1P205 0 0 1 1 0 0 0 1 1 1 1 0图解法 相关图形见图2。 考虑硬约束,可行域为第一限象; 考虑P1,最优解在直线AB上; 考虑P2,最优解在点A上。 因此,略。得分八、(10分)(教材P155例7)有某种机床,可以在高低两种不同的负荷下进行生产,在高负荷下生产时,产品的年产量为g,与年初投入生产的机床数量u1的关系为g=g(u
7、1)=8u1,这时,年终机床完好台数将为au1,(a为机床完好率,0a1,设a=0.7).在低负荷下生产时,产品的年产量为h,和投入生产的机床数量u2的关系为h=h(u2)=5u2,相应的机床完好率为b(0b1,设b=0.9),一般情况下ab。假设某厂开始有x=1000台完好的机床,现要制定一个五年生产计划,问每年开始时如何重新分配完好的机床在两种不同的负荷下生产的数量,以使在5年内产品的总产量为最高。 解:首先构造这个问题的动态规划模型。 变量设置 设阶段变量k表示年度,因此,阶段总数n=5。 状态变量sk表示第k年度初拥有的完好机床台数,同时也是第k-1年度末时的完好机床数量。决策变量uk
8、,表示第k年度中分配于高负荷下生产的机床台数。于是sk- uk便为该年度中分配于低负荷下生产的机床台数。 这里uk与uk均取连续变量,当它们有非整数数值时可以这样理解:如sk0.6,就表示一台机器在k年度中正常工作时间只占6/10;uk=0.4时,就表示一台机床在k年度只有4/10的时间于高负荷下工作。 状态转移方程为 允许决策集合, 目标函数。设vk(sk,uk)为第k年度的产量,则vk(sk,uk)=8uk+5(sk-uk),因此,目标函数为 递推方程。 令fk(sk)表示由第k年的状态sk出发,采取最优分配方案到第5年度结束这段时间的产品产量,根据最优化原理有以下递推关系: 边界条件:
9、s11000,s60。分阶段求解见下表。58413.6317.522020.7681023.6912由表5可得最优策略:。目标函数最优值:个。得分九、(10分)对表1,用表上作业法求解。表1销地产地产量(万吨)A631275 B43956C910135需求(万吨)455不限解:根据产销平衡可知表1中不限应取为2,应取为M,因此问题的基础数据表等价与表2:表2销地产地产量(万吨)A631275 B43956C91013M5需求(万吨)4552关于的计算用伏格尔法确定差额表1销地产地行差额A61273 B43951C91013M1列差额2032差额表2销地产地行差额A61273 -B4391 1C91013M