最全的运筹学复习题及答案

A—B3—C2—D2—E 13;

最优解:A―B2―C1―D1―E;A―B3―C1―D1―E;A―B3―C2―D2―E 最优值:13

(12)最小生成树问题

某大学准备对其所属的7个学院办公室计算机联网,这个网络的可能联通的途径如图所示,图中V1,……,V7表示7个学院办公室,图中的边为可能联网的途径,边上的所赋权数为这条路线的长度,单位为百米。请设计一个网络能联通7个学院办公室,并使总的线路长度为最短。

V2 3 V1 10 V6 3 3 4 V7 5 8 4 V5 2 1 V3 7 V1 V4 3 3 V2 3 4 V7 5 8 V5 2 1 V3 7 V4 G V6 4 G1 解:①在G中找到一个圈(V1,V7,V6,V1),并知在此圈上边[V1,V6]的权数10为最

大,在G中去掉边[V1,V6]得图G1 ,如上图所示

V2 3 V1 1 V6 3 3 4 4 V7 5 V5 2 1 V3 7 V1 V4 1 3 V6 4 V5 3 V2 3 4 V7 2 1 V3 7 V4 G2 G3

②在G1中找到一个圈(V3,V4,V5,V7,V3),去掉其中权数最大的边 [V4,V5], 得图G2 ,如上图所示

③在G2中找到一个圈(V2,V3,V5,V7,V2),去掉其中权数最大的边 [V5,V7],得图G3 ,如上图所示

V2 3 V1 1 V6 3 3 V5 4 V7 2 1 V3 7 V1 V4 1 3 V6 V5 3 V2 3 V7 2 1 V3 7 V4 G4 G5 ④在G3中找到一个圈(V3,V5,V6,V7,V3),去掉其中权数最大的边 [V5,V6],得图G4 ,如上图所示

最全的运筹学复习题及答案

⑤在G4中找到一个圈(V2,V3, V7,V2),去掉其中权数最大的边 [V3,V7],得图G5 ,如上图所示

⑥在G5中已找不到任何一个圈了,可知G5即为图G的最小生成树。 这个最小生成树的所有边的总权数为3+3+3+1+2+7=19

(13)某一个配送中心要给一个快餐店送快餐原料,应按照什么路线送货才能使送货时间最短。下图给出了配送中心到快餐店的交通图,图中V1,……,V7表示7个地名,其中V1表示配送中心,V7表示快餐店,点之间的联线表示两地之间的道路,边所赋的权数表示开车送原料通过这段道路所需要的时间(单位:分钟) (18,3) (4,1) (0,S) V1 (配送中心) 41218(16,2) V3 6V5 285(24,3) V2 16V4 7V6 (25,4) 6V7 (27,5) (快餐店) 解:①给起始点V1标号为(0,S) ②I={V1},J={ V2,V3,V4,V5,V6 ,V7} ,边的集合{[Vi,Vj] ︳Vi,Vj两点中一点属于I,而另一点属于J}={[ V1,V2],[ V1,V3]},并有

S12=L1+C12=0+4=4 ; S13=L1+C13=0+18=18

min (S12,S13)= S12 =4

给边[ V1,V2]中的未标号的点V2 标以(4,1),表示从V1 到V2 的距离为4,并且在V1到V2的最短路径上V2的前面的点为V1、

③这时I={V1 ,V2},J={V3,V4,V5,V6 ,V7},边的集合{[Vi,Vj] ︳Vi,Vj两点中一点属于I,而另一点属于J}={[ V1,V3],[ V2,V3],[ V2,V4]},并有

S23=L2+C23=4+12=16 ;S24=L2+C24=4+16=20 ;min (S23,S24 , S13)= S23 =16 给边[ V2,V3]中的未标号的点V3 标以(16,2)

④这时I={V1 ,V2 ,V3},J={V4,V5,V6 ,V7},边的集合{[Vi,Vj] ︳Vi,Vj两点中一点属于I,而另一点属于J}={[ V2,V4],[ V3,V4],[ V3,V5]},并有

S34=L3+C34=16+2=18 ; S35=L3+C35=16+6=22 ; S24=L2+C24=4+16=20

min (S34,S35,S24)= S34 =18

给边[ V3,V4]中的未标号的点V4 标以(18,3)

⑤这时I={V1 ,V2 ,V3 ,V4},J={V5,V6 ,V7},边的集合{[Vi,Vj] ︳Vi,Vj两点中一点属于I,而另一点属于J}={ [ V4,V6],[ V4,V5],[ V3,V5]},并有

S46=L4+C46=18+7=25 ; S45=L4+C45=18+8=26 ;min (S46,S45 ,S35)= S35 =24 给边[ V3,V5]中的未标号的点V5 标以(24,3)

⑥这时I={V1 ,V2 ,V3 ,V4 ,V5 },J={ V6 ,V7},边的集合{[Vi,Vj] ︳Vi,Vj两点中一点属于I,而另一点属于J}={[ V5,V7],[ V4,V6] },并有 S57=L5+C57=22+5=27 ;min (S57,S46)= S46 =25 给边[ V4,V6]中的未标号的点V6 标以(25,4)

⑦这时I={V1 ,V2 ,V3 ,V4 ,V5 ,V6 },J={ V7},边的集合{[Vi,Vj] ︳Vi,Vj两点中一点属于I,而另一点属于J}={[ V5,V7],[ V6,V7] },并有

S67=L6+C67=25+6=31 ;min (S57,S67)= S57 =27 给边[ V5,V7]中的未标号的点V7 标以(27,5)

最全的运筹学复习题及答案

⑧此时I={V1 ,V2 ,V3 ,V4 ,V5 ,V6 ,V7},J=空集,边集合{[Vi,Vj] ︳Vi,Vj两点中一点属于I,而另一点属于J}=空集,计算结束。

⑨得到最短路。从V7 的标号可知从V1 到V7 的最短时间为27分钟。 即:配送路线为: V1 →V2 →V3 →V5 →V7 (14)最小生成树问题

某电力公司要沿道路为8个居民点架设输电网络,连接8个居民点的道路图如图所示,其中V1,……,V8表示8个居民点,图中的边表示可架设输电网络的道路,边上的赋权数为这条道路的长度,单位为公里,请设计一个输电网络,联通这8个居民点,并使总的输电线路长度为最短 。

V2 4 V1 2 V3 G V4 2 4 6 V5 7 5 V8 2 3 2 5 V6 3 V7

①在图中找到一个圈(V1,V2,V5,V3),并知在此圈上边[V1,V2]与 [V3,V5]的权数4为最大,在图中去掉边[V1,V2] ;

②在图中找到一个圈(V3,V4,V8 ,V5 ,V3, V1),去掉其中权数最大的边 [V4,V8];

③在图中找到一个圈(V3,V4, V5,V3),去掉其中权数最大的边 [V4,V5]; ④在图中找到一个圈(V5,V2,V6,V7 ,V5),去掉其中权数最大的边 [V2,V6];

⑤在图中找到一个圈(V5,V7, V8,V5),去掉其中权数最大的边 [V5,V8]。 ⑥在图中已找不到任何一个圈了,可知此即为图G的最小生成树。 这个最小生成树的所有边的总权数为2+2+4+2+3+3+2=18 (15)最大流问题

某地区的公路网如图所示,图中V1,……,V6为地点,边为公路,边上所赋的 权数为该段公路的流量(单位为千辆/小时),请求出V1 到V6 的最大流量。

最全的运筹学复习题及答案

V2 8 4 V5 12 5 6 V1 6 10 6 5 V4 6 V6 V3 解:第一次迭代:

选择路为V1 →V3 →V6 。弧(V3 ,V6)的顺流流量为5,决定了pf=5,改进的网络流量图如图所示:

V2 0 6 8 4 0 6 10 5 5 0 6 5 0 0 0 5 0 0 V5 12 0 5→

V4 V1 6 0 5 0 V6 →5 第一次迭代 后的总流量 V3 第二次迭代:

选择路为V1 →V2 →V5 →V6 。弧(V1 ,V2)的顺流流量为6,决定了pf=6,改进的网络流量图如图所示:

V2 6 0 6 0 6 5 5 6 0 第二次迭代 后的总流量 0 0 0 8 4 5 2 0 0 6 V5 12 6 0 6 5 0 6 11→ V4 V1 V6 →11 V3 第三次迭代:选择路为V1→V4 →V6 。弧(V1 ,V4)的顺流流量为6, 决定了pf=6,改进的网络流量图如图所示: