运筹学重点习题及答案

运筹学重点习题及答案

ID:12404533

大小:1.95 MB

页数:8页

时间:2018-07-16

运筹学重点习题及答案_第1页
运筹学重点习题及答案_第2页
运筹学重点习题及答案_第3页
运筹学重点习题及答案_第4页
运筹学重点习题及答案_第5页
资源描述:

《运筹学重点习题及答案》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、综合习题二1、自己选用适当的方法,对下图求最小(生成)树。(12分)V1233524556V3V2V4V5V656V1V2V44353V3V5V6522解:(1)最小树为图中双线所示(2)最小树长142、用破圈法求下面网络的最短树解:最小树如下图所示由于q=5,p=6,则q=p-1,故已得最短树。最小树长为12V22、用标号法求下列网络V1→V7的最短路径及路长。(12分)1754V53V3163V7V1315V67V4解:V2V5V7V6V3V4V1(v1,0)(v1,4)(v1,6)(v1,13)(v6,10)(v3,9)(v5,7)(v1,3)(v1,5)43157317

2、5631最短路径:v1→v3→v5→v6→v7L=104、解:第一轮:(1)在G中找到一个回路{v1,v2,v3,v1};(2)此回路上的边[v1,v3]的权数6为最大,去掉[v1,v3]。第二轮:(1)在划掉[v1,v3]的图中找到一个回路{v2,v3,v5,v2};(2)去掉其中权数最大的边[v2,v5]。第三轮:(1)在划掉[v1,v3],[v2,v5]的图中找到一个回路{v2,v3,v5,v4,v2}(2)去掉其中权数最大的边[v3,v5]。第四轮:(1)在划掉[v1,v3],[v2,v5],[v3,v5]的图中找到一个回路{v4,v5,v6,v4}(2)去掉其中权数最

3、大的边[v5,v6](或可以去掉边[v4,v6],这两条边的权数都为最大)。(2分)v3v5v1v254234v4v6在余下的图中已找不到任何一个回路了,此时所得图就是最小树,这个最小树的所有边的总权数为5+4+2+3+4=18,结果如下图所示,即按照下图设计网络路线,可使总的线路长度达到最短。5、求下图的网络最大流,并写出最小割集。(12分)V14V487645Vs9V23V53Vt155287V37V6解:找增广链:(6分)(Vs,4)V1(4,4)V4(8,4)764(5,4)Vs(9,3)V2(V1,4)(3,3)V5(3,3)Vt(15,7)528(7,7)V3(7,

4、7)V6(Vs,8)(3分)最小割集为:V*={(V3,V6),(V2,V5),(V1,V4)}(1分)C*(V,V)=14(1分)且V*(f)=145、如下图,(1)求v1到v10的最大流及最大流量;(2)求最小割集和最小割量。图6-4415【解】给出初始流如下15第一轮标号:得到一条增广链,调整量等于5,如下图所示15调整流量。第二轮标号:得到一条增广链,调整量等于2,如下图所示15调整流量。第三轮标号:得到一条增广链,调整量等于3,如下图所示15调整流量。第四轮标号:不存在增广链,最大流量等于45,如下图所示15取,最小截集{(3,7),(4,7),(6,9),(8,10

5、),最小截量等于45。6、用狄克斯拉算法求解下图所示最短路问题。4v1v2v3v4v6v5v722561413412解:先将图的网络用矩阵形式表示出来:反向追踪,得到最优路线:7、某蛋糕店有一服务员,顾客到达服从=30人/小时的Poisson分布,当店里只有一个顾客时,平均服务时间为1.5分钟,当店里有2个或2个以上顾客时,平均服务时间缩减至1分钟。两种服务时间均服从负指数分布。试求:(1)此排队系统的状态转移图;(2)稳态下的概率转移平衡方程组;(3)店内有2个顾客的概率;(4)该系统的其它数量指标。【解】(1)此系统为排队模型,该系统的状态转移图如下:(2)由转移图可得稳态

6、下的差分方程组如下:(3)已知由得令,有则(4)系统中的平均顾客数(队长期望值)在队列中等待的平均顾客数(队列长期望值)系统中顾客逗留时间系统中顾客等待时间8某商店每天开10个小时,一天平均有90个顾客到达商店,商店的服务平均速度是每小时服务10个,若假定顾客到达的规律是服从Poisson分布,商店服务时间服从负指数分布,试求:(1)在商店前等待服务的顾客平均数。(2)在队长中多于2个人的概率。(3)在商店中平均有顾客的人数。(4)若希望商店平均顾客只有2人,平均服务速度应提高到多少。【解】此题是属于系统,其中:=9(个/小时)=10(个/小时)=9/10(1)(个)(2)(3

7、)(个)(4)(个/小时)9、某产品中有一外购件,年需求量为10000件,单价为100元,由于该件可在市场采购,故订货提前期为零,并不允许缺货。已知每组织一次采购需2000元,每件每年的库存费为该件单价的20%,试求经济订货批量及每年最小的总费用。解:根据题意,知D=10000,C1=100*20%=20,C3=100*2000=200000(件)(元)10、工厂每月需要甲零件3000件,每件零件120元,月存储费率为1.5%,每批订货费为150元,求经济订货批量及订货周期。【解】模型4。D

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。