运筹学课后答案2
更新时间:2024-05-18 02:37:01 阅读量: 综合文库 文档下载
运筹学(第2版) 习题答案 运筹学(第2版)习题答案2
第1章 线性规划 P36~40
第2章 线性规划的对偶理论 P68~69 第3章 整数规划 P82~84 第4章 目标规划 P98~100 第5章 运输与指派问题 P134~136 第6章 网络模型 P164~165 第7章 网络计划 P185~187 第8章 动态规划 P208~210 第9章 排队论 P239~240 第10章 存储论 P269~270 第11章 决策论 Pp297-298 第12章 博弈论 P325~326 全书360页
1
由于大小限制,此文档只显示第6章到第12章,第1章至第5章见《运筹学课后答案1》
习题六
6.1如图6-42所示,建立求最小部分树的0-1整数规划数学模型。
【解】边[i,j]的长度记为cij,设
?1边[i,j]包含在最小部分树内xij???0否则
数学模型为:
图6-42
minZ?cijxij??xij?5?i,j?x?x13?x23?2,x23?x24?x34?2?12?x34?x36?x46?2,x35?x36?x56?2??x12?x13?x24?x34?3 ?x?x?x?x?334354656??x23?x24?x46?x36?3??x12?x13?x24?x46?x36?4?x?x?x?x?x?4,2335244656??x12?x13?x24?x35?x46?x56?5??xij?1或0,所有边[i,j]
6.2如图6-43所示,建立求v1到v6的最短路问题的0-1整数规划数学模型。
图6-43
运筹学(第2版) 习题答案
【解】弧(i,j)的长度记为cij,设
2
?1弧(i,j)包含在最短路径中xij???0否则数学模型为:
minZ??ci,jijxij?x12?x13?1??x12?x23?x24?x25?0?x?x?x?x?013233435 ???,x24?x34?x45?x46?0?x?x?x?x?0354556?25?x46?x56?1???xij?1或0,所有弧(i,j)6.3如图6-43所示,建立求v1到v6的最大流问题的线性规划数学模型。
【解】 设xij为弧(i,j)的流量,数学模型为
minZ?x12?x13?x12?x13?x?x23?12??x13?x23?x?x34?24?x25?x35???0?xij?
?x46?x56?x24?x25?x34?x35?x45?x46?x45?x56cij,所有弧(i,j)
6.4求图6-41的最小部分树。图6-41(a)用破圈法,图6-41(b)用加边法。
图6-44
【解】图6-44(a),该题有4个解,最小树长为22,其中一个解如下图所示。
运筹学(第2版) 习题答案 3
图6-44(b),最小树长为20。最小树如下图所示。
6.5 某乡政府计划未来3年内,对所管辖的10个村要达到村与村之间都有水泥公路相通的目标。根据勘测,10个村之间修建公路的费用如表6-20所示。乡镇府如何选择修建公路的路线使总成本最低。
表6-20
1 2 3 4 5 6 7 8 9 10 【解】属于最小树问题。用加边法,得到下图所示的方案。
两村庄之间修建公路的费用(万元) 1 2 12.8 3 10.5 9.6 4 8.5 7.7 13.8 5 12.7 13.1 12.6 11.4 6 13.9 11.2 8.6 7.5 8.3 7 14.8 15.7 8.5 9.6 8.9 8.0 8 13.2 12.4 10.5 9.3 8.8 12.7 14.8 9 12.7 13.6 15.8 9.8 8.2 11.7 13.6 9.7 10 8.9 10.5 13.4 14.6 9.1 10.5 12.6 8.9 8.8 运筹学(第2版) 习题答案 4
最低总成本74.3万元。
6.6在图6-45中,求A到H、I的最短路及最短路长,并对图(a)和(b)的结果进行比较。
图6-45
【解】图6-45(a):
A到H的最短路PAH={A,B,F,H},{A,C,F,H}最短路长22;A到I的最短路PAI={A,B,F,I},{A,C,F,I}最短路长21。
对于图6-45(b):
运筹学(第2版) 习题答案 5
A到H的最短路PAH={A,C,G,F,H},最短路长21;A到I的最短路PAI={A,C,G,F,I},最短路长20; 结果显示有向图与无向图的结果可能不一样。
6.7已知某设备可继续使用5年,也可以在每年年末卖掉重新购置新设备。已知5年年初购置新设备的价格分别为3.5、3.8、4.0、4.2和4.5万元。使用时间在1~5年内的维护费用分别为0.4、0.9、1.4、2.3和3万元。试确定一个设备更新策略,使5年的设备购置和维护总费用最小。
【解】设点vj为第j年年初购置新设备的状态,(i,j)为第i年年初购置新设备使用到第j年年初,弧的权为对应的费用(购置费+维护费),绘制网络图并计算,结果见下图所示。
总费用最小的设备更新方案为:第一种方案,第1年购置一台设备使用到第5年年末;第二种方案,第1年购置一台设备使用到第2年年末,第3年年初更新后使用到第5年年末。总费用为11.5万元。
6.8图6-46是世界某6大城市之间的航线,边上的数字为票价(百美元),用Floyd算法设计任意两城市之间票价最便宜的路线表。
【解】教师可利用模板求解:data\\chpt6\\ch6.xls
L1 v1 v1 v2 v3 v4 v5 0 8.8 9 5.6 8 v2 8.8 0 10 5 100 v3 9 10 0 3 4.8 v4 5.6 5 3 0 12 v5 8 100 4.8 12 0 v6 6 4 14 100 9 图6-46
运筹学(第2版) 习题答案 6
v6 6 4 14 100 9 v1 0 L2
v2 8.8 0 8 5 13 4 v3 8.6 8 0 3 4.8 14 L3
v4 5.6 5 3 0 7.8 9 v5 8 13 4.8 7.8 0 9 v6 6 4 14 9 9 0 v1 v2 v3 v4 v5 v6 0 8.8 8.6 5.6 8 6 v1 v1 v2 v3 v4 v5 v6 0 8.8 8.6 5.6 8 6 v2 8.8 0 8 5 13 4 v3 8.6 8 0 3 4.8 12 v4 5.6 5 3 0 7.8 9 v5 8 13 4.8 7.8 0 9 v6 6 4 12 9 9 0 最优票价表:
v1 v1 v2 v3 v4 v5 v6
0 v2 8.8 0 v3 8.6 8 0 v4 5.6 5 3 0 v5 8 13 4.8 7.8 0 v6 6 4 12 9 9 0 v1、v2、?、v6到各点的最优路线图分别为:
运筹学(第2版) 习题答案 7
6.9 设图6-46是某汽车公司的6个零配件加工厂,边上的数字为两点间的距离(km)。现要在6个工厂中选一个建装配车间。
(1)应选那个工厂使零配件的运输最方便。
(2)装配一辆汽车6个零配件加工厂所提供零件重量分别是0.5、0.6、0.8、1.3、1.6和1.7吨,运价为2元/吨公里。应选那个工厂使总运费最小。 【解】(1)利用习题6.8表L3的结果
L?minmax?Lij??12.8
ij v1 v1 v2 v3 v4 v5 v6 选第1个工厂最好。
0 8.8 8.6 5.6 8 6 v2 8.8 0 8 5 13 4 v3 8.6 8 0 3 4.8 12 v4 5.6 5 3 0 7.8 9 v5 8 13 4.8 7.8 0 9 v6 6 4 12 9 9 0 Max 8.8 12.8 12 9 12.8 12 (2)计算单件产品的运价,见下表最后一行。计算单件产品的运费,见下表最后一列。 v1 v2 v3 v4 v5 v6 运价 选第4个工厂最好。
6.10 如图6-47,(1)求v1到v10的最大流及最大流量;(2)求最小割集和最小割量。 【解】给出初始流如下
图6-47
v1 0 8.8 8.6 5.6 8 6 1 v2 8.8 0 8 5 13 4 1.2 v3 8.6 8 0 3 4.8 12 1.6 v4 5.6 5 3 0 7.8 9 2.6 v5 8 13 4.8 7.8 0 9 3.2 v6 6 4 12 9 9 0 3.4 单件产品运费 84.88 89.16 82.16 71.96 81.92 82.2 运筹学(第2版) 习题答案 8
第一轮标号:得到一条增广链,调整量等于5,如下图所示
调整流量。
第二轮标号:得到一条增广链,调整量等于2,如下图所示
调整流量。
第三轮标号:得到一条增广链,调整量等于3,如下图所示
调整流量。
第四轮标号:不存在增广链,最大流量等于45,如下图所示
运筹学(第2版) 习题答案 9
取 V1?{v1,v2,v3,v4,v5,v6,v8},V1?{v7,v9,v10},最小截集{(3,7),(4,7),(6,9),(8,10),最小截量等于45。
6.11 将3个天然气田A1、A2、A3的天然气输送到2个地区C1、C2,中途有2个加压站B1、B2,天然气管线如图6-48所示。输气管道单位时间的最大通过量cij及单位流量的费用dij标在弧上(cij, dij)。求(1)流量为22的最小费用流;(2)最小费用最大流。
图6-48
【解】虚拟一个发点和一个收点
T6.11-1
得到流量v=22的最小费用流,最小费用为271。求解过程参看习题部分答案PPT文档。
运筹学(第2版) 习题答案 10
T6.11-13
最小费用最大流如下图,最大流量等于27,总费用等于351。
6.12如图6-46所示,(1)求解旅行售货员问题;(2)求解中国邮路问题。
图6-46
【解】(1)旅行售货员问题。
距离表C 1 2 3 4 5 1 ∞ 8.8 9 5.6 8 2 8.8 ∞ 10 5 ∞ 3 9 10 ∞ 3 4.8 4 5.6 5 3 ∞ 12 5 8 ∞ 4.8 12 ∞ 9 6 6 4 14 ∞ 9 ∞ ∞ 6 6 4 14 在C中行列分别减除对应行列中的最小数,得到距离表C1。 距离表C1 1 2 1 ∞ 2.8 2 3.2 ∞ 3 3.4 6 4 0 1 5 0.6 ∞ 6 0.4 0
运筹学(第2版) 习题答案 31
PN??N??N?11??N?1N?1?0.07N?1??N????0.07????(1?0.93?)?0.070.07
NN0.071?0.93?ln0.751?0.93?0.75?0.2314N?ln0.2314?5.087
则应设立4个座位供顾客排队。
9.4某服务部平均每小时有4个人到达,平均服务时间为6分钟。到达服从Poisson流,服务时间为负指数分布。由于场地受限制,服务部最多不能超过3人,求:
(1)服务部没有人到达的概率; (2)服务部的平均人数; (3)等待服务的平均人数;
(4)顾客在服务部平均花费的时间; (5)顾客平均排队的时间。
【解】依题意,这是[M/M/1]:[N/?/FCFS]排队系统。其中:
N=3,?=4,?=10,???/?=0.4
(1)P0?1?ρ1-ρN?1=(1-0.4)/[1-(0.4)4]=0.6158
(2)L?0.5616(人) (3)Lq?0.1616(人) (4)W?0.1404(小时) (5)Wq?0.0404(小时)
9.5某车间有5台机器,每台机器连续运转时间服从负指数分布,平均连续运转时间为15分钟。有一个修理工,每次修理时间服从负指数分布,平均每次12分钟。求该排队系统的数量指标,P0,Lq,L,Wq,
W和P5。
【解】由题意知,每台机器每小时出故障的平均次数服从泊松分布,故该排队系统为
[M/M/1]:[?/m/FCFS]系统,其中:
?=1/15,m=5,?=1/12,???/?=0.8
?1?55!k?P0??????0.0073
?k?0(5?k)!?1/15?1/12Lq?5?(1?0.0073)?2.766(台)
1/15L?Lq?(1?P0)?3.759(台) Wq?Lq(5?L)??33.43(分钟)
W?Wq?m!1??45.43(分钟)
5???5!5??P5?P?(0.8)(0.0073)?0.287 ??0(m?5)!???0!
9.6证明:一个[M/M/2]:[?/?/FCFS]的排队系统要比两个[M/M/1]:[?/?/FCFS]的排
运筹学(第2版) 习题答案
队系统优越。试从队长L这个指标证明。
32
【证】设[M/M/1]:[?/?/FCFS]的服务强度为?,则[M/M/2]:[?/?/FCFS]服务强度为2?。则
两个单服务台的系统 L1?两个服务台的系统 P0??1???2?1??1121
??(2?)2?1??21??1??
1?2??队长 L2?2???2?(2?)??2?(1??)22?1??1???2
由于0???1,?L1?2?1???L2?2?1??
即系统1的队长大于系统2 的队长,故单队2服务台的系统优于2队单服务对的系统。
9.7某博物馆有4个大小一致的展厅。来到该博物馆参观的观众服从泊松分布,平均96人/小时。观众大致平均分散于各展厅,且在各展厅停留的时间服从1/??15分钟的负指数分布,在参观完4个展厅后离去。问该博物馆的每个展厅应按多大容量设计,使在任何时间内观众超员的概率小于5%。 【解】此问题中服务员数量s??,属于M/M/?系统,每个展厅内:
??964?24人/小时,??6015?4人/小时,??i???6
Pi???i!e?? (i?0,1,2,?)
要确定展厅的容量n,使观众超过n的概率小于0.05,即有
?i?n6ii!e?6?0.05
由泊松累积分布表查得n?10。
故每个展厅应至少容纳10人,使在任何时间内观众超员的概率小于5%。
9.8两个技术程度相同的工人共同照管5台自动机床,每台机床平均每小时需照管一次,每次需一个工人照管的平均时间为15分钟。每次照管时间及每相继两次照管间隔都相互独立且为负指数分布。试求每人平均空闲时间,系统四项主要指标和机床利用率。
【解】由题意可知,该系统为[M/M/s]:[?/m/FCFS]系统,且:
s?2,m?5,??1台/小时,??60/15?4台/小时, s?/m??/??1/4,
?/m??/?s?1/8。
工人空闲率:
P0?1?5?0.25?5?4/2?0.25?0.316?2?5!?0.125n3?5!?2?0.1254?5!?2?0.1255??1
???(mPn????(m??计算得:
???????P0?0?n?2??n)!n!???m!m!n)!s!sn?s????????P0?3?n?5???n
Ls?P1?2P2?3P3?4P4?5P5?1.092台
Lq?P3?2P4?3P5?0.116台
运筹学(第2版) 习题答案 33
1工人平均空闲时间:1/2??2?n?Pn?0n?1/2?2P0?P1??0.5119
?c?1??5?1.092??3.908
Ws?Ls/?c?Wq?Lq/?c?1.0923.9080.1163.908?0.279(小时)=16.8(分钟) ?0.029(小时)=1.8(分钟)
机床利用率:1?Ls/m?1?1.092/5?78.016%
9.9某储蓄所有一个服务窗口,顾客按泊松分布平均每小时到达10人,为任一顾客办理存款、取款等业务的时间T服从N~(0.05,0.012)的正态分布。试求储蓄所空闲的概率及其主要工作指标。 【解】这是一个[M/G/1]:[?/?/FCFS]排队系统。由题意知:
??10人/小时,??20人/小时,???/??0.5,E(T)?0.05,Var(T)?0.01 储蓄所空闲的概率及其主要工作指标为:
2P0?1???0.5
Lq?0.5?10?0.012(1?0.5)L0.7610222?0.26(人)
L?Lq???0.76(人)
W?Wq??Lq?h?5(分钟)
9.10某检测站有一台自动检测机器性能的仪器,检测每台机器都需6分钟。送检机器按泊松分布到达,平均每小时4台。试求该系统的主要工作指标。
解:这是一个[M/D/1]:[?/?/FCFS]系统,且:
??0.2610h?2(分钟)
??4台/小时,1/??6分钟/台,???/??0.4Var(T)?0
各主要工作指标为:
Lq?0.422(1?0.4)815?215(台)
L?Lq???(台)
301W?Wq??8(分钟)
Wq?Lq??1h?2(分钟)
?9.11一个电话间的顾客按泊松流到达,平均每小时到达6人,平均通话时间为8分钟,方差为8分钟,直观上估计通话时间服从爱尔朗分布,管理人员想知道平均列队长度和顾客平均等待时间是多少。 解:该系统为[M/Ek/1]:[?/?/FCFS]排队系统,其中:
k?[E(T)]22Var(T)?8216?4,??6??2(人)
860?0.8
Lq?0.8?(4?1)2?4(1?0.8)运筹学(第2版) 习题答案 34
Wq?Lq
9.12对某服务台进行实测,得到如下数据: 系统中的顾客数(n) 记录到的次数(mn) ??26h?20(分钟)
0 1 2 3 161 97 53 34 平均服务时间为10分钟,服务一个顾客的收益为2元,服务机构运行单位时间成本为1元,问服务率为多少时可使单位时间平均总收益最大。
【解】该系统为[M/M/1]:[3/?/FCFS]系统,首先通过实测数据估计平均到达率?: 因为
PnPn?1mnmn?1??
可以用下式来估计?
^??13?3?13(0.6?0.55?0.64)?0.6
n?1由??6/小时,可得?的估计值为:
^^ ?????0.6?6?3.6人/小时
为求最优服务率,根据公式9.6.5,取:
N?3,
可得 ?故 ?*csG?12?0.5
?1.21
^*???*?3.61.2134?3
当??6人/小时时,总收益为:
z?2?3.6?1?0.61?0.6?1?6?0.485(元/小时)
当??3人/小时时,总收益为:
z?2?3.6?1?1.211?1.2134?1?6?1.858(元/小时)
单位时间内平均收益可增加1.373元。
9.13某检验中心为各工厂服务,要求进行检验的工厂(顾客)的到来服从Poisson流,平均到达率为
??48(次/天);工厂每次来检验由于停工造成损失6元;服务(检验)时间服务负指数分布,平均服务率为??25(次/天);每设置一个检验员的服务成本为每天4元,其他条件均适合
[M/M/s]:[?/?/FCFS]系统。问应设几个检验员可使总费用的平均值最少。
【解】已知cs?4,cw?6,??48,??25,???s?11.92P0????n?0n!n???1.92,设检验员数为s,则:
???(s?1)!(s?1.92)?1.92s?1
L?Lq???P01.92s?12(s?1)!(s?1.92)?1.92
*将s?1,2,3,4,5依次代入,得到下表。由于cs/cw?0.67落在区间(0.583,21.845)之间,故s当设3 个检验员时可使总费用z最小,最小值为:
?3,即
运筹学(第2版) 习题答案 35
*z(s)?z(3)?27.87(元)
检验员数 s 1 2 3 4 5
平均顾客数 L(s) ∞ 24.49 2.645 2.063 1.952 L(s)-L(s+1)~ L(s-1)-L(s) 21.845~∞ 0.582~21.845 0.111~0.582 总费用(元) z(s) ∞ 154.94 27.87 28.38 31.71 习题十
10.1某企业每月甲零件的生产量为800件,该零件月需求量为500件,每次准备成本50元,每件月存储费为10元,缺货费8元,求最优生产批量及生产周期。 【解】模型1。D=500,P=800,H=10,A=50,B=8
Q*?2ADHH?BBPP?DQ*=2?50?500?(10?8)?80010?8?(800?500)?173.21
t*?D?173.21500?0.346(月)
最优订货批量约为173件,约11天订货一次。
10.2某产品月需要量为600件,若要订货,可以以每天50件的速率供应。存储费为5元/(月·件),订货手续费为100元,求最优订货批量及订货周期。
【解】模型2。D=600,P=30×50=1500,H=5,A=100
Q*?2ADHt*?PP?DQ*D??2005002?100?600?15005?(1500?600)?200(件)
?0.333(月)=10(天)
最优订货批量约为200件,约10天订货一次。
10.3某公司预计年销售计算机2000台,每次订货费为500元,存储费为32元/(年·台),缺货费为100元/年·台。
试求:(1)提前期为零时的最优订货批量及最大缺货量;(2)提前期为10天时的订货点及最大存储量。
【解】模型3。D=2000,A=500,H=32,B=100, L=0.0274(年)
Q?2ADHH?BB?2?500?20003232?100100?287(台)
S?2ADB2ADHHH?BBH+B=2?500?20001002?500?2000323232?10010032?100?69(台)
Q1???218(台)
R=LD-S=0.0274×2000-69=55-69=-14(件)
(1)最优订货批量为287台,最大缺货量为69台;(2)再订货点为-14台,最大存储量为218台。
正在阅读:
运筹学课后答案205-18
施工安全风险辨识、评定表106-20
竞业限制合同05-25
基于数学核心素养的数学07-02
学校宣传片脚本框架08-10
各省军区独立师历史沿革04-25
公路工地建设标准化施工手册06-03
13春《马克思主义基本原理》作业105-29
QC小组活动记录本08-21
- 清真菜谱
- 我国国民经济和社会发展十二五规划纲要(全文)
- 高三物理机械振动和机械波复习2
- 浙江省公路山岭隧道机械化装备应用指导手册 doc - 图文
- 2018届高三数学文科二轮复习:专题检测(九) 导数的简单应用
- 2015年上海市公务员录用考试《行政职业能力测验》试卷(B类)
- 七年级道德与法制下册
- 大班户外游戏教案
- 病虫害预警 - 图文
- 某养鱼场为了提高经营管理水平
- 汉中市勉县尧柏余热汽机规程 10
- 烹饪试卷
- 事业单位考试公共基础知识专项分类题库训练
- 语文:第2课 走一步,再走一步 课堂导学案(人教版 七上)
- 天汉使用手册
- 人教版小学三年级数学下册教学计划
- 房地产销售管理完全操作手册122页
- 2009年评审通过具有中学高级教师专业技术资格人员名单...
- 《15秋公共关系学》作业1
- 2017最新版监理公司三标一体管理手册
- 运筹学
- 课后
- 答案
- 中国保健酒的市场营销现状及对策分析——以劲酒公司为例
- 存储&备份技术方案
- 中国地理学会会员(浙江省) - 图文
- 2018年泰州专业技术人员继续教育《沟通与协调能力》必过答案
- 2016-2017《证券市场基础知识》模拟试题1
- 山东省调整土地使用税税额标准通知
- 10kV配电网单相故障电流计算及跨步电压的分析
- 0629纯答案版-合规《每日一学》题库(1)
- solidworks实习报告
- 2017年6月四六级
- 2018届九年级下学期第一次模拟考试历史试卷
- 试论辛亥时期的军政分府
- 二年级语文下册教学计划
- 如何写融资商业计划书
- 2017年8月集圣中学高三年级月考卷
- 创建篮球特色学校 提升校园文化精神
- 放慢脚步,用心品味生活
- 七年级数学上册一元一次方程专项练习题88
- 机电学习题1
- 漏电报警系统技术方案