运筹学重点习题及答案

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

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