运筹学重点习题及答案.doc

综合习题二1、自己选用适当的方法，对下图求最小(生成)树。(12分)V1233524556V3V2V4V5V656V1V2V44353V3V5V6522解：（1）最小树为图中双线所示（2）最小树长142、用破圈法求下面网络的最短树解：最小树如下图所示 由于q=5，p=6，则q=p-1，故已得最短树。最小树长为12 V22、用标号法求下列网络V1V7的最短路径及路长。（12分）1754V53V3163V7V1315V67V4解：V2V5V7V6V3V4V1(v1, 0)(v1, 4)(v1, 6)(v1, 13)(v6, 10)(v3, 9)(v5, 7)(v1, 3)(v1, 5)431573175631最短路径：v1v3v5v6v7 L=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）去掉其中权数最大的边v5，v6（或可以去掉边v4，v6，这两条边的权数都为最大）。 （2分）v3v5v1v254234v4v6在余下的图中已找不到任何一个回路了，此时所得图就是最小树，这个最小树的所有边的总权数为5+4+2+3+4=18，结果如下图所示，即按照下图设计网络路线，可使总的线路长度达到最短。5、求下图的网络最大流，并写出最小割集。（12分） V1 4 V4 8 7 6 4 5Vs 9 V2 3 V5 3 Vt 15 5 2 8 7 V3 7 V6解：找增广链： （6分） (Vs,4) V1 (4,4) V4 (8,4) 7 6 4 (5,4)Vs ( 9,3) V2 (V1,4) (3,3) V5 (3,3) Vt (15,7) 5 2 8 (7,7) V3 (7,7) V6 (Vs,8) （3分）最小割集为：V*=（V3，V6），（V2，V5），（V1，V4） （1分）C*（V，V）=14 （1分）且V*（f）=14 5、如下图，（1）求v1到v10的最大流及最大流量；（2）求最小割集和最小割量。 图64415【解】给出初始流如下15第一轮标号：得到一条增广链，调整量等于5，如下图所示15调整流量。第二轮标号：得到一条增广链，调整量等于2，如下图所示15调整流量。第三轮标号：得到一条增广链，调整量等于3，如下图所示15调整流量。第四轮标号：不存在增广链，最大流量等于45，如下图所示15取 ，最小截集(3,7),(4,7),(6,9),(8,10)，最小截量等于45。6、用狄克斯拉算法求解下图所示最短路问题。4v1v2v3v4v6v5v722561413412解：先将图的网络用矩阵形式表示出来:反向追踪，得到最优路线：7、某蛋糕店有一服务员，顾客到达服从=30人/小时的Poisson分布，当店里只有一个顾客时，平均服务时间为1.5分钟，当店里有2个或2个以上顾客时，平均服务时间缩减至1分钟。两种服务时间均服从负指数分布。试求：（1）此排队系统的状态转移图；（2）稳态下的概率转移平衡方程组；（3）店内有2个顾客的概率；（4）该系统的其它数量指标。【解】（1）此系统为排队模型，该系统的状态转移图如下：（2）由转移图可得稳态下的差分方程组如下： （3）已知由得令 ，有则 （4）系统中的平均顾客数（队长期望值） 在队列中等待的平均顾客数（队列长期望值）系统中顾客逗留时间系统中顾客等待时间8某商店每天开10个小时，一天平均有90个顾客到达商店，商店的服务平均速度是每小时服务10个，若假定顾客到达的规律是服从Poisson分布，商店服务时间服从负指数分布，试求：（1）在商店前等待服务的顾客平均数。（2）在队长中多于2个人的概率。（3）在商店中平均有顾客的人数。（4）若希望商店平均顾客只有2人，平均服务速度应提高到多少。【解】此题是属于系统，其中：=9（个/小时） =10(个/小时) =9/10(1) （个）(2) (3) （个）(4) (个/小时)9、某产品中有一外购件，年需求量为10000件，单价为100元，由于该件可在市场采购，故订货提前期为零，并不允许缺货。已知每组织一次采购需2000元，每件每年的库存费为该件单价的20%，试求经济订货批量及每年最小的总费用。解：根据题意，知D=10000，C1=100*20%=20，C3=100*2000=200000(件) （元）10、工厂每月需要甲零件3000件，每件零