运筹学 - 张伯生 - 2011~2012学年第一学期考试试卷
更新时间:2024-01-03 08:38:01 阅读量: 教育文库 文档下载
- 运筹学推荐度:
- 相关推荐
+
(勤奋、求是、创新、奉献)
2010~2011学年第二学期考试试卷
主考教师:___张伯生___
学院 ________________ 班级 __________ 姓名 __________ 学号 ___________
(本卷考试时间 120 分钟)
题号 一 题分 得分 15 二 15 三 10 四 10 五 15 六 15 七 10 八 10 九 十 总得分 一、辨析题(本题共5小题,每小题3分,共15分)
1、线性规划模型中,设系数矩阵A=(aij)3?6,则X=(0,0,2,3,4,0)T有无可能是A的基可行解? 有可能(1分)。基可行解中非零值的个数不超过m,(题中m=3),给定解中X有3个非零值分量。(2分)
2、m个发点和n个收点的运输问题中,有m+n个相互独立的约束条件。 错(1分)。相互独立的约束条件有m+n-1(2分)。 3、一个赋权图的最小生成树是否唯一?为什么?
不是唯一的。(1分)因为可以该赋权图中边的所赋权可能是相同的,在这种情况下得到的最小生成树可能就不唯一的。(2分) 4、用单纯形法求解极大化问题的线性规划问题时,?J?0与对应的变量都可以被选为换入变量吗?为什么? 答:可以。(1分)因为检验数大于零,把xj作为换入变量,仍然可以改进目标函数值。(2分)
5、已知网络上某条链如下图,问:x为何值时,该链是增流链,为什么?
答:x=0(1分)。此时后向边不为零边,不符合增流链定义(2分)。
二、某工厂拥有A、B、C三种类型的设备,生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数,每件产品可以获得的利润以及三种设备可利用的时数如下表所示。(15分)
vs(3,1)v1(1,x)v3(4,2)vt(1)写出问题的数学模型 (2)求获最大利润的方案。
甲 设备A 设备B 设备C 3 2 0 乙 2 1 3 2500 设备能力 65 40 75 利润(元/件) 1500
解:设甲、乙产品分别生产x1,x2件,线性规划模型为
maxZ?1500x1?2500x2?3x1?2x2?65??2x1?x2?40s.t.??3x2?75??x1,x2?0
利用单纯形法进行求解为 CB 0 0 0 0 0 2500 1500 0 Cj xB x3 x4 x5 r x3 X4 X2 r X1 X4 1500 x1 3 2 0 1500 (3) 2 0 1500 1 0 0 0 2500 x2 2 1 (3) 2500 0 0 1 0 1 0 0 0 1/3 -2/3 0 1 0 x3 1 0 0 0 0 1 0 0 0 x4 0 1 0 0 0 x5 0 0 1 0 -2/3 -1/3 1/3 -833.3 -0.2222 5 0.1111 5 b 65 40 75 0 15 15 25 8 ? 32.5 40 25 5 7.5 2500 x2 r 0 0 1 0 0 -500 0 0 1/4 -500 25
最优解为:X*=(5, 25, 0, 5, 0)T, 目标函数最优值70000.
三、用图解法找出以下目标规划问题的满意解。(10分)
minz?P1?d1?d??1??P?2d2????1?2??2d??3x1?10x2?d1?d3x1?5x2?d2?d8x1?6x2?d3?d????50?203?100
x1,x2,di,di?0,i?1,2,3
满意解为(50,0) d1+=0,d1-=0,d2+=130,d2-=0,d3+=300,d3-=0 四、对于线性规划模型:(10分)
max f =x1+2x2+3x3+4x4 s.t. x1+2x2+2x3+3x4?20 2x1+x2+3x3+2x4?20 x1?0,x2?0,x3?0,x4?0
已知其对偶问题的最优解U*=(6/5,1/5),利用互补松弛性求解原问题的解。
解:原问题的对偶问题为
min z =20u1+20u2 s.t. u1+2u2?1 (1) 2u1+u2?2 (2) 2u1+3u2?3 (3) 3u1+2u2?4 (4)
u1?0,u2?0 (5分) 将U=(6/5,1/5)代入对偶问题,(1)、(2)式为严格不等式,则有因为u1?0,u2?0?
*
x1?0,x2?0
???,所以有
2x3+3x4=20
3x3+2x4=20
解得
x3?4*,x4?4。(5
*分)
五、现在有线性规划问题(15分) max z=-5X1+5X2+13X3
??X1?X2?3X3?20??12X1?4X2?10X3?90?X,X,X?023?1
的最优单纯形表如下: 5 0 Cj X2 X5 r -5 -1 16 0 1 0 0 5 13 3 -2 -2 1 -4 -5 0 0 1 0 0 b 20 10 -100 (1)约束条件2的右端常数由90变为了70,对最优基、最优解有何影响?如果有影响请求出最优解。
B?1?1????4?0??1???20??1'b?Bb????10????
对最优基、最优解有影响. 13 3 -2 1 -4 -5 -5 2 -1 0 0 1 0 3/2 -1/2 -1 0 b 20 -10 -100 5 5 90
5 0 5 13 Cj X2 X5 r X2 X3 r -5 -1 16 0 23 -8 -16 1 0 5 0 1 0 0 -2 0 1 0 X=(0,5,5,0,0) z=90 (2)目标函数中X3的系数由13变为8,对最优基、最优解有何影响?如果
有影响请求出最优解。
r3?8??5?3?0????2????7?0??
对最优基、最优解没有影响.
六、若发点A1,A2及收点B1,B2,B3的有关数据如下表所示。假定A1,A2处
允许物资存储,(本题共15分)
A1 A2 B1 B2 B3 供应量 200 200 存储费 5 4 4 6 8 6 2 4 50 100 100 需求量 (1) 写出运输问题的数学模型; (2) 用最小元素法找出初始基本可行解;
(3) 求出初始基本可行解的检验数,找出闭回路,确定调整量; (4) 求出最优运输方案和最小总运费。 解:
设Ai→Bj的运输量为xij,则由新的运输问题可以得到:
?6x12?8x13?5x1?6x2?12x?4x?2411422 min f?4x 3xx11?x12?x13?200x21?x22?x23?200x11?x21?50x12?x22?100x13?x23?100 xij?0,i?1,2,j?1,2,3
xij?0,i?1,2.j?1,2,3,4. (5分) (2)解:该运输问题为产>销的问题,虚拟销地B4,形成新的问题: A1 A2 B1 B2 B3 B4 供应量 200 200 4 6 8 5 6 2 4 4 50 100 100 150 需求量
(2分) 使用最小元素法得到初始解: A1 A2 B1 B2 B3 B4 供应量 200 200 50 100 50 100 100 50 100 100 150 需求量
(2分)
(3)使用位势法,得到检验数为: A1 A2 vjB1 B2 B3 B4 ui 0 3 0 0 3 0 -3 0 4 3 8 5 0 -1 增加A2→B3的运输量,得到新的解为: A1 A2 B1 B2 B3 B4 供应量 200 200 50 0 150 100 100 50 100 100 150 需求量 (2分)
使用位势法,得到检验数为: A1 A2 vjB1 B2 B3 B4 ui 0 0 0 0 6 0 0 3 4 6 8 5 0 -4 (4)因此可知: A1 A2 B1 B2 B3 B4 供应量 200 200 50 0 150 100 100 50 100 100 150 需求量 为该运输问题的最优解。 F=1050(4分)
七、有4个工人,要指派他们分别完成4项工作,每人做各项工作所消耗的时间如下表1:(10分) 表1 工作 A B C D 工人 甲 15 18 21 乙 19 23 22 丙 26 17 16 丁 19 21 23 问指派哪个人去完成哪项工作,可使总的消耗时间为最小?
解:用匈牙利法求解过程如下:得最优指派:
?0??1X1??0??0?100000100??0?0??1???1??0??0??0?000100100??1?0??0??
24 18 19 17 X2最少的耗时数z=15+18+16+21=70。
八、用标号法求出图中v1至各点的最短路(10分)
V21V49V12734588V63V710V37V5
解:V1-V2 9 V1-V3 8(2分) V1-V2-V4 10(2分) V1-V2-V4-V5
或V1-V2-V6-V5 14(2分) V1-V2-V6 11(2分) V1-V2-V4-V7 13(2分)
正在阅读:
运筹学 - 张伯生 - 2011~2012学年第一学期考试试卷01-03
高三化学二轮复习 原创押题卷五11-07
刍议提高市政工程管理的有效措施06-06
GCP试题+答案04-13
我国旅游资源的类型 教案.jsp09-05
2018年湖北省恩施州中考化学试卷07-09
美德教师事迹材料05-13
音乐鉴赏答案 - 周海宏12-05
- exercise2
- 铅锌矿详查地质设计 - 图文
- 厨余垃圾、餐厨垃圾堆肥系统设计方案
- 陈明珠开题报告
- 化工原理精选例题
- 政府形象宣传册营销案例
- 小学一至三年级语文阅读专项练习题
- 2014.民诉 期末考试 复习题
- 巅峰智业 - 做好顶层设计对建设城市的重要意义
- (三起)冀教版三年级英语上册Unit4 Lesson24练习题及答案
- 2017年实心轮胎现状及发展趋势分析(目录)
- 基于GIS的农用地定级技术研究定稿
- 2017-2022年中国医疗保健市场调查与市场前景预测报告(目录) - 图文
- 作业
- OFDM技术仿真(MATLAB代码) - 图文
- Android工程师笔试题及答案
- 生命密码联合密码
- 空间地上权若干法律问题探究
- 江苏学业水平测试《机械基础》模拟试题
- 选课走班实施方案
- 运筹学
- 试卷
- 年第
- 学期
- 考试
- 张伯生
- 2011
- 2012
- 现代推销学(第四版)吴建安版课后答案之考试重点版
- 附件1:中国南方电网有限责任公司基建项目安全管理业务指导书
- 2016届高三语文人教版一轮复习:课时作业二十四
- C练习 - 数据类型运算符及表达式 - 选择题-答案
- 关于提高初中生地理读图能力方法的结题报告
- 小学科学实验操作考核试题及评分表
- 在全县农村信用社改革试点工作会议上的讲话
- 基于PLC的电梯控制系统设计文献综述
- 黑龙江省大庆市2017 - -2018年中考地理试题含答案
- 教学研究与成果凝练(田锋社) - 图文
- 2015年人教版一年级数学上册期中试卷
- illustrator课程标准
- 山西省平遥中学09-10学年高一10月质检(数学)
- 水处理生物学课后题答案
- 2009年浙江高考理科综合试题版
- 最新人教版七年级(上册)期末数学综合检测试题
- 2017年最新环境影响评价工程师法律法规模拟试题及答案
- 流水施工作业题
- 幼儿园安全隐患排查情况总结
- 庆祝教师节演讲稿