线性规划习题(29)

6 V

V5

5 V （24,3）

2

V7 （27,5） （快餐店）

一点属于 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 6 5 6 10 6 5

V5

12

V4

V1

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

V4

5→

V1

6 0 5