运筹学重点习题及答案

运筹学重点习题及答案 综合习题二 1、自己选用适当的方法，对下图求最小(生成)树。(12分) V V 5 24 5 6 4 2 V65 V1 3 2 3 V V 35 解:(1)最小树为图中双线所示 V5 V 24 5 6 4 V 5 6 V 12 3 2 V V 3 35 (2)最小树长14 2、用破圈法求下面网络的最短树 解:最小树如下图所示 由于q=5，p=6，则q=p-1，故已得最短树。 最小树长为12 2、用标号法求下列网络V1?V7的最短路径及路长。(12分) V2 5 V 5 7 4 1 3 V3 3 V V 171 6 1 3 5 V 6 7 V 4 解: , 4) (v1 V2(v, 6) 15 V 5 1 4 7 3 , 0) (v V13(v, 13) 1 3 V11 V 76 , 3) (v1 (v, 10) 65 1 3 7 V 6 (v, 9) 3 (v, 7) 5V 4(v, 5) 1 最短路径:v?v?v?v?v L=10 13567 4、解: 第一轮: (1) 在G中找到一个回路{v，v，v，v}; 1231 (2) 此回路上的边[v，v]的权数6为最大，去掉[v，v]。 1313 第二轮: (1)在划掉[v，v]的图中找到一个回路{v，v，v，v}; 132352 (2)去掉其中权数最大的边[v，v]。 25 第三轮: (1)在划掉[v，v]，[v，v]的图中找到一个回路{v，v，v，v，v} 132523542 (2)去掉其中权数最大的边[v，v]。 35 第四轮: (1)在划掉[v，v]，[v，v]，[v，v]的图中找到一个回路{ v，v，v，v} 1325354564 (2)去掉其中权数最大的边[v，v](或可以去掉边[v，v]，这两条边的权数都为最大)。 5646(2分) 在余下的图中已找不到任何一个回路了，此时所得图就是最小树，这个最小树的所有边 v v35 4 vv 3 61 5 4 v 22 v 4 的总权数为5+4+2+3+4=18，结果如下图所示，即按照下图设计网络路线，可使总的线路长度达到最短。 5、求下图的网络最大流，并写出最小割集。(12分) V 4 V 14 8 7 6 4 5 V9 V3 V3 V s 2 5 t 15 5 2 8 7 V 7 V 36 解:找增广链: f,4 V,V,V,V1s14t f,3 V,V,V,V2s25t (6分) V,V,V,Vf,7s36t3 (V,4) s V (4,4) V 14 (8,4) 7 6 4 (5,4) V(9,3) V(V,4)(3,3) V(3,3) V s 2 1 5 t (15,7) 5 2 8 (7,7) V (7,7) V36 (V,8) (3分) s *最小割集为:V={(V，V)，(V，V)，(V，V)} (1分) 362514*C(V，V)=14 (1分) *且V(f)=14 5、如下图，(1)求v1到v10的最大流及最大流量;(2)求最小割集和最小割量。 15 图6,44 【解】给出初始流如下 15 第一轮标号:得到一条增广链，调整量等于5，如下图所示 15 调整流量。 第二轮标号:得到一条增广链，调整量等于2，如下图所示 15 调整流量。 第三轮标号:得到一条增广链，调整量等于3，如下图所示 15 调整流量。 第四轮标号:不存在增广链，最大流量等于45，如下图所示 15 VvvvvvvvVvvv,,{,,,,,,},{,,}取 ，最小截集{(3,7),(4,7),(6,9),(8,10)，最小截1123456817910 量等于45。 6、用狄克斯拉算法求解下图所示最短路问题。 6 vv25 4 2 1 4 2 v4v 1v 4 7 1 1 5 2 v v 36 3 解:先将图的网络用矩阵形式表示出来: 反向追踪，得到最优路线: ,7、某蛋糕店有一服务员，顾客到达服从=30人/小时的Poisson分布，当店里只有一个顾客时，平均服务时间为1.5分钟，当店里有2个或2个以上顾客时，平均服务时间缩减至1分钟。两种服务时间均服从负指数分布。试求: (1)此排队系统的状态转移图; (2)稳态下的概率转移平衡方程组; (3)店内有2个顾客的概率; (4)该系统的其它数量指标。 [M/M/1]:[,/,/FCFS]【解】(1)此系统为排队模型，该系统的状态转移图如下: (2)由转移图可得稳态下的差分方程组如下: ,,P,P,011 ,,,,,P，P,(，)P,02211 ,,,,,P，P,(，)P12322, ,,P，,P,(,，,)P,n,12n，12n n23,,,, P,PP,PP,P？P,P20300n102n,1,,,,,,,1212121 11(3)已知 ,,30(人/小时),,,40(人/小时),,,60(人/小时)121.51 6060, 由P,1得 ,ii0,n,,P[1]1，,,0n,1,,n,112 ,1，，, ,,1,,,P,，10,,,1,,,2，，, ,,303301令 ，有 ,,,,,,,,,12404602,,12 3 ,,,1114P,，,，,[1][1]0.4011,,21, 2 nn,1,ppp,,,,n0120n,112,, 31则 ,,，，,,, PP0.40.15212042 (4)系统中的平均顾客数(队长期望值) ,,1n,,,,,,L,nP,nP,P(1，2，3，...),,1201023n00nn,, 131,,P,，0.4，,1.2(人)1022,(1,)4(1,0.5)2 在队列中等待的平均顾客数(队列长期望值) ,,, ,(,1),,LnPnPP,,,qnnn111n,n,n, ,p2n,1 10,,,,,,(1，，，...，，...),,LPL102221,,2 3，0.4 4,1.2,,0.4(人)11, 2 系统中顾客逗留时间 L1.2,,,小时 W0.04(),30系统中顾客等待时间 L0.4q,,,0.013(小时)W q,30 8某商店每天开10个小时，一天平均有90个顾客到达商店，商店的服务平均速度是每小时服务10个，若假定顾客到达的规律是服从Poisson分布，商店服务时间服从负指数分布，试求: (1)在商店前等待服务的顾客平均数。 (2)在队长中多于2个人的概率。 3)在商店中平均有顾客的人数。 ( (4)若希望商店平均顾客只有2人，平均服务速度应提高到多少。 [M/M/1]:[,/,/FCFS]【解】此题是属于系统，其中: ,=9(个/小时) =10(个/小时) ,,,/,=9/10 , 2L,,/(1,,),8.1(1) (个) q 3(2) P(N,2),,,0.729 L,,/(1,,),9(3) (个) L,,,,,,/()2(4) ,,，，2918 (个/小时) ,,,13.5,22 9、某产品中有一外购件，年需求量为10000件，单价为100元，由于该件可在市场采购，故订货提前期为零，并不允许缺货。已知每组织一次采购需2000元，每件每年的库存费为该件单价的20%，试求经济订货批量及每年最小的总费用。 解:根据题意，知D=10000，C=100*20%=20，C=100*2000=200000 13 2，10000，200000Q,,1414(件) 020 (元) C,2CCD,2，20，200000，10000,282842.7013 10、工厂每月需要甲零件3000件，每件零件120元，月存储费率为1.5%，每批订货费为150元，求经济订货批量及订货周期。 【解】模型4。D=3000，A=150，H=120×0.015,1.8，C=120 221503000AD，，Q,,,707()件H1.8 tQD,,/0.24()月 fHADCD,，,，，，，，,221.815030001203000361272.79()元则经济订货批量为707件，订货周期为0.24月。