运筹学重点习题及答案

1、自己选用适当的方法，对下图求最小(生成)树。(12分)

V1 2 V3

6 5

3 V5

V2 5 V4

5 4

2

3

V6

解：（1）最小树为图中双线所示

V1 2 V3 3 V5 V2 6

5

5 4

V4

5 2

3 V6 （2）最小树长14

2、用破圈法求下面网络的最短树

解：最小树如下图所示

由于q=5，p=6，则q=p-1，故已得最短树。 最小树长为12

2、用标号法求下列网络V1→V7的最短路径及路长。（12分）

V2

5 V

5

V1

4 3 1 1 V3

3 6

1

7

V7

3

5 V4

7

V6

解：

(v1, 4)

V2 (v1, 6)

5 V5

1 4 7 3 V3 (v1, 13) (v1, 0) 3 V1 1 V7

6 (v1, 3)

5 1 3 (v6, 10)

7 V6 (v3, 9)

(v5, 7)

V4 (v1, 5)

最短路径：v1→v3→v5→v6→v7 L=10 4、解：

第一轮：

（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分）

在余下的图中已找不到任何一个回路了，此时所得图就是最小树，这个最小树的所有边

v3 v1

5 v 4

v5 3 4

v6

的总权数为5+4+2+3+4=18，结果如下图所示，即按照下图设计网络路线，可使总的线路长度达到最短。

5、求下图的网络最大流，并写出最小割集。（12分）

V1 4 V4

8 7 6 4 5 Vs 9 V2 3 V5 3 Vt

15 5 2 8 7

V3 7 V6

解：找增广链：

VsV1V4Vt f14 VsV2V5Vt f23

VsV3V6Vt f37 （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）求最小割集和最小割量。

15

图6－44

【解】给出初始流如下

15

第一轮标号：得到一条增广链，调整量等于5，如下图所示

15

调整流量。

第二轮标号：得到一条增广链，调整量等于2，如下图所示

15

调整流量。

第三轮标号：得到一条增广链，调整量等于3，如下图所示

15

调整流量。

第四轮标号：不存在增广链，最大流量等于45，如下图所示

15

取 V1{v1,v2,v3,v4,v5,v6,v8},V1{v7,v9,v10}，最小截集{(3,7),(4,7),(6,9),(8,10)，最小截量等于45。

6、用狄克斯拉算法求解下图所示最短路问题。

6 v2 2 4 4 2 v1 1 5 v3 3 v4 1 2 v6 v5 1 4 v7

解：先将图的网络用矩阵形式表示出来:

反向追踪，得到最优路线：

7、某蛋糕店有一服务员，顾客到达服从=30人/小时的Poisson分布，当店里只有一个顾客时，平均服务时间为1.5分钟，当店里有2个或2个以上顾客时，平均服务时间缩减至1分钟。两种服务时间均服从负指数分布。试求： （1）此排队系统的状态转移图； （2）稳态下的概率转移平衡方程组； （3）店内有2个顾客的概率； （4）该系统的其它数量指标。 【解】（1）此系统为[M/M/1]:[//FCFS]排队模型，该系统的状态转移图如下：

（2）由转移图可得稳态下的差分方程组如下：

P01P1PP()P02211 P12P3(2)P2Pn12Pn1(2)Pn23nP1P0 P2P0 P3P0 PnP0 2n11121212（3）已知30（人/小时）1＝11 ＝40（人/小时）2＝＝60（人/小时）1.516060由

P1得

ii0nP0[1]1n1n1121P0112303301令 1＝＝＝,2＝＝＝，有

140426021

3P0[11]1[14]10.41121

2nn1pnpp0012n112则 P212P0310.40.15 42（4）系统中的平均顾客数（队长期望值）

LnPnn12n1P01P0(12233...)

n0n0311P00.41.2(人)22(12)4(10.5)Lq(n1)PnnPnPnn1n1n11

在队列中等待的平均顾客数（队列长期望值）

L1P0(1222...2n1...)L30.441.20.4(人)112系统中顾客逗留时间

1p012

W系统中顾客等待时间

L1.20.04(小时) 30

8某商店每天开10个小时，一天平均有90个顾客到达商店，商店的服务平均速度是每小时服务10个，若假定顾客到达的规律是服从Poisson分布，商店服务时间服从负指数分布，试求：

（1）在商店前等待服务的顾客平均数。 （2）在队长中多于2个人的概率。 （3）在商店中平均有顾客的人数。

（4）若希望商店平均顾客只有2人，平均服务速度应提高到多少。 【解】此题是属于[M/M/1]:[//FCFS]系统，其中：

0.4Wq0.013(小时)

30Lq=9（个/小时） =10(个/小时) /=9/10

(1) Lq/(1)8.1（个）

230.729

(3) L/(1)9（个） (4) L/()2

291813.5(个/小时) (2) P(N2)229、某产品中有一外购件，年需求量为10000件，单价为100元，由于该件可在市场采购，

故订货提前期为零，并不允许缺货。已知每组织一次采购需2000元，每件每年的库存费为该件单价的20%，试求经济订货批量及每年最小的总费用。 解：根据题意，知D=10000，C1=100*20%=20，C3=100*2000=200000

Q02100002000001414(件)

20C02C1C3D22020000010000282842.7（元）

10、工厂每月需要甲零件3000件，每件零件120元，月存储费率为1.5%，每批订货费为150元，求经济订货批量及订货周期。

【解】模型4。D=3000，A=150，H=120×0.015＝1.8，C=120

2AD21503000707(件)H1.8tQ/D0.24(月)Qf2HADCD21.815030001203000361272.79(元)

则经济订货批量为707件，订货周期为0.24月。