网络优化的数学模型—1资料

网络优化的数学模型(1)



停 下

最小生成树及算法 旅行售货员问题 中国邮递员问题


停 下

1.最小生成树及算法
1) 树的定义与树的特征 定义 连通且不含圈的无向图称为树.常用T表示. 树中的边称为树枝. 树中度为1的顶点称为树叶. 孤立顶点称为平凡树.

v1
v2

v3

v4

v5

平凡树

定理2 设G是具有n个顶点的图,则下述命题等价:
1) G是树( G无圈且连通); ?

2) G无圈,且有n-1条边; 3) G连通,且有n-1条边; 4) G无圈,但添加任一条新边恰好产生一个圈; 5) G连通,且删去一条边就不连通了(即G为最 最小连通图); 6) G中任意两顶点间有唯一一条路.

2)图的生成树
定义 若T是包含图G的全部顶点的子图,它又是树, 则称T是G的生成树. 图G中不在生成树的边叫做弦.

定理3 图G=(V,E)有生成树的充要条件是图G是连 通的.
证明 必要性是显然的.
充分性 :任取 u1 ? V ,令集合V1 ? {u1},这时生成
(1) 树T 的边集 ET 为空集. 因为 G 是连通图, 点集V1与

V \ V1之间必有边相连,设 e1 ? u1u2为这样的边,

u1 属 于 V1 而 u2 属 于 V \ V1 . 则 得 V2 ? {u1, u2} ,
( 2) ET

? {e1}. 重复进行上述步骤,对于

(i ) i ? n(?| V |) , Vi ? {u1, u2 ,..., ui }, ET ? {e1, e2 ,..., ei ?1},

仍能找到边 ei 满足其一端在点集Vi ,另一端在点 集V \ Vi 中.
(i ) 由于 ei 有一端在Vi 之外,所以Vi 与 ET

中的边不构成圈. 当 i ? n 时,得到
( n) Vn ? {u1, u2 ,..., un } ? V , ET ? {e1, e2 ,..., en?1},

即图T

( n) ? (V , ET ) 有 n ? 1条边且无圈, 由定理 2 知,

这是一棵树,且为图 G 的一棵生成树.

(II)找图中生成树的方法
可分为两种:避圈法和破圈法 A 避圈法 : 深探法和广探法 B 破圈法

A 避圈法 定理3的充分性的证明提供了一种构造图的生 成树的方法. 这种方法就是在已给的图G中,每步选出一 条边使它与已选边不构成圈,直到选够n-1条边为 止. 这种方法可称为“避圈法”或“加边法” 在避圈法中,按照边的选法不同,找图中生 成树的方法可分为两种:深探法和广探法.

a) 深探法 例用深探法求出下图10的一棵生成树 步骤如下: i) 在点集V中任取一点u, 给以标号0. ii) 若某点v已得标号,检 图10 1 2 查一端点为v的各边,另一 8 7 端是否均已标号. 10 11 0 3 若有边vw之w未标号,则给 9 13 12 6 w以标号i+1,记下边vw.令 5 4 w代v,重复ii). 若这样的边的另一端均已有标号,就退到标号为 i-1的r点,以r代v,重复ii),直到全部点得到标号为止.

a) 深探法 例用深探法求出下图10的一棵生成树 步骤如下: i) 在点集V中任取一点u, 给u以标号0. ii) 若某点v已得标号,检 图10 查一端点为v的各边,另一 1 2 8 7 端是否均已标号. 10 11 3 若有边vw之w未标号,则给 0 9 13 12 w以标号i+1,记下边vw.令 6 5 4 w代v,重复ii). 若这样的边的另一端均已有标号,就退到标号为 i-1的r点,以r代v,重复ii),直到全部点得到标号为止.

b)广探法 例用广探法求出下图10的一棵生成树 步骤如下: i) 在点集V中任取一点u, 给u以标号0. ii) 令所有标号i的点集为 Vi,检查[Vi,V\Vi]中的边端点 是否均已标号. 对所有未标 号之点均标以i+1,记下这些 边. iii) 对标号i+1的点重复步 步骤ii),直到全部点得到 标号为止.
1 1

图10
0 1 2 2 3 3 4 3 2 2 2 1

图10

b)广探法 例用广探法求出下图10的一棵生成树 步骤如下: i) 在点集V中任取一点u, 给u以标号0. ii) 令所有标号i的点集为 Vi,检查[Vi,V\Vi]中的边端点 是否均已标号. 对所有未标 号之点均标以i+1,记下这些 边. iii) 对标号i+1的点重复步 步骤ii),直到全部点得到 标号为止.
1 1

图10
0 1 2 2 3 3 4 3 2 2 2 1

显然图10的生成树 不唯一.

B 破圈法
相对于避圈法,还有一种求生成树的方法叫做 “破圈法”. 这种方法就是在图G中任取一个圈, 任意舍弃一条边,将这个圈破掉,重复这个步骤 直到图G中没有圈为止. 取一圈{v1e1v2e3v3e2v1},去掉 e3 ; 例 用破圈法求出 取一圈{v1e1v2e4v4e5v3e2v1},去掉 e5 ; 下图的一棵生成树. 取一圈{v2e4v4e7v5e6v2},去掉e7 ;
取一圈{v1e1v2e6v5e8v3e2v1},去掉 e6 .

B 破圈法
例 用破圈法求出下图的另一棵生成树.
取一圈{v1e1v2e3v3e2v1}, 去掉 e3 ; 取一圈{v1e1v2e4v4e5v3e2v1},去掉 e4 ; 取一圈{v1e1v2e6v5e8v3e2v1},去掉 e8 ;

取一圈{v1e1v2e6v5e7v4e5v3e2v1}去掉 e6 ; 得到另一颗生成树.

不难发现,图 的生成树不是 唯一的 .

3) 最小生成树与算法
定义 13 设T ? (V , E1) 是赋权图 G ? (V , E ) 的一棵生 成树, 称T 中全部边上的权数之和为生成树的权, 记为
w(T ) ,即 w(T ) ?
e?E1 *

? w(e) .

如果生成树T 的权 w(T * ) 是 G 的所有生成树的权中最 小者,则称 T * 是 G 的 最小生成树 ,简称为最小树,即
w(T * ) ? ? min{w(T )},式中取遍 G 的所有生成树T .
T

介绍最小树的两种算法: Kruskal算法(或避圈法)和破圈法.

A Kruskal算法(或避圈法)

步骤如下: 1) 选择边e1,使得w(e1)尽可能小; 2) 若已选定边 e1, e2 ,..., ei ,则从 E \ {e1, e2 ,..., ei } 中选取ei ?1 ,使得: i) G[{e1, e2 ,..., ei ?1}] 为无圈图,
ii) w(ei ?1) 是满足i)的尽可能小的权, 3) 当第2)步不能继续执行时,则停止. 定理4 由Kruskal算法构作的任何生成树 T * ? G[{e1, e2 ,..., e? ?1}] 都是最小树.

例10用Kruskal算法求下图的最小树.
在左图中 {e1, e2 ,..., e8}权值 最小的边有 e1, e5 , 任取一条e1, 在 {e2 , e3 ,..., e8} 中选取权值 最小的边 e5 , {e2 , e3 , e4 , e6 , e7 , e8} : 中权值最小边有 e3 , e7, 从中选 任取一条边 e3 ; {e2 , e4 , e6 , e7 , e8} 中选取在中选取 e7 , 在{e2 , e4 , e6 , e8}中选取 e4 , e8 . 但 e4与 e8都 会与已选边构成圈,故停止,得

B破圈法

例11用破圈法求下图的最小树.

算法2 步骤如下: 1) 从图G中任选一棵树T1. 2) 加上一条弦e1,T1+e1中 立即生成一个圈. 去掉此 圈中最大权边,得到新 树T2,以T2代T1,重复2)再 检查剩余的弦,直到全 部弦检查完毕为止. 再加上弦 先求出上图的一棵生成树 e7,得到圈 v4v5v2v4 ., 加以弦 e2,得到的圈 v1v3v2v1, 去掉最大的权边 e6,得到一棵 新树;如此重复进行,直到全 去掉最大的权边 e2,得到一棵新 树仍是原来的树; 全部的弦均已试过,得最小树.

e2

e7 2

例:最短运输路线问题
如图的交通网络,每条弧上的数字代表车辆在该路段行 驶所需的时间,有向边表示单行道,无向边表示可双向 行驶。若有一批货物要从 1 号顶点运往11号顶点,问运 货车应沿哪条线路行驶,才能最快地到达目的地?

2

3 5

3
6

5 6

4

8 1 7 7 8
8

1

12

9
9

2
3

5 10 11

9

7 2 10

2

例:最廉价航费表的制定
某公司在六个城市C1,C2,C3,C4,C5,C6都有分公司, 公司成员经常往来于它们之间,已知从Ci到Cj的直达航 班票价由下述矩阵的第 i 行,第 j 列元素给出( ? 表示无 直达航班),该公司想算出一张任意两个城市之间的最 廉价路线航费表。 ? 0 50 ? 40 25 10? ?50 0 15 20 ? 25? ? ? ? ? 15 0 10 20 ? ? ? ? 40 20 10 0 10 25 ? ? ?25 ? 20 10 0 55? ? ? ?10 25 ? 25 55 0 ?

练习 求图中任意两点间的最短路及最小生成树.

5. 旅行售货员问题
定义设G=(V,E)是连通无向图,包含图G的每个 顶点的路称为G的哈密尔顿路(Hamilton路或H路). 包含图G的每个顶点的圈,称为G的哈密尔顿圈 (或Hamilton圈或H圈). 含Hamilton圈的图称为哈密尔顿图(或Hamilton 图或H图).

旅行售货员问题或货郎担问题.
一个旅行售货员想去访问若干城镇,然后回 到出发地.给定各城镇之间的距离后,应怎样计划 他的旅行路线,使他能对每个城镇恰好经过一次 而总距离最小? 它可归结为这样的图论问题:在一个赋权完 全图中,找出一个最小权的H圈,称这种圈为最优圈.

但这个问题是NP-hard问题,即不存在多项式 时间算法.也就是说,对于大型网络(赋权图),目前还 没有一个求解旅行售货员问题的有效算法,因此 只能找一种求出相当好(不一定最优)的解.

一个可行的办法 :
是先求一个H圈,然后适当 修改,以得到具有较小权的另 一个H圈.
设找到一个初始 H 圈 C ? v1v2 ?vnv1,则对所 有适合1 ? i ? 1 ? j ? ? 的 i 和 j , 总可得到一个新的 H 圈: Cij ? v1v2 ?vi v j v j ?1 ?vi ?1v j ?1v j ? 2 ?vnv1 ,它是 由 C 删去边 vi vi ?1和 v j v j ?1, 以及添加边 vi v j 和 vi ?1v j ?1 而得到,如右图所示。

定义 若对于某一对i和j,有 w(vi v j ) ? w(vi ?1v j ?1) ? w(vi vi ?1) ? w(v j v j ?1) 则圈Cij将是圈C的一个改进. 二边逐次修正法: 在接连进行一系列修改之后,最后得一个圈,不能 再用此方法改进了,这个最后的圈可能不是最优的 , 但是它是比较好的,为了得到更高的精度,这个

程序可以重复几次,每次都以不同的圈开始. 这种 方法叫做二边逐次修正法.

例对下图16的K6,用二边逐次修正法求较优H圈.

较优H圈: C3 ? v1v4v5v6v2v3v1 其权为W(C3)=192

分析: 找出的这个解的好坏可用最优H圈的权 的下界与其比较而得出.即利用最小生成树可得最 优H圈的一个下界,方法如下: 设C是G的一个最优H圈,则对G的任一顶点v, C-v是G-v的路,也G-v是的生成树.如果T是G-v的 最小生成树,且e1是e2与v关联的边中权最小的两条 边,则w(T)+w(e1)+w(e2)将是w(C)的一个下界. 取v=v3,得G-v3的一 最小生成树(实线),其 权w(T)=122,与v3关联 的权最小的两条边为 v1v3和v2v3,故w(C) ? w(T)+w(v1v3)+w(v2v3) =178.故最优H圈的权 应满足178 ? w(C)? 192.

6. 中国邮递员问题
? 七桥问题 Seven Bridges Problem ? 18世纪著名古典数学问题之一。在哥尼斯堡的 一个公园里,有七座桥将普雷格尔河中两个岛 以及岛与河岸连接起来(如图)。问是否可能从 这四块陆地中任一块出发,恰好通过每座桥一 次,再回到起点?

? 欧拉于1736年研究并解决了此问题, 他用点表示 岛和陆地,两点之间的连线表示连接它们的桥, 将河流、小岛和桥简化为一个网络,把七桥问题 化成判断连通网络能否一笔画的问题。之后他发 表一篇论文,证明了上述走法是不可能的。并且 给出了连通网络可一笔画的充要条件这一著名的 结论。

一笔画问题
? 一笔画问题:从某一点开始画画,笔不离纸,各 条线路仅画一次,最后回到原来的出发点。

想一想:
a

v1

b 图1

c

v2

v3 图2

v4

? 图1和图2当中哪一个图满足:从图中任何一点出发, 途径每条边,最终还能回到出发点? ? 由此试想一下:一个图应该满足什么条件才能达到 上面要求呢?

一笔画问题
? 凡是能一笔画出的图,奇点的个数最多有两个。 始点与终点重合的一笔画问题,奇点的个数必是0。 ? 在一个多重边的连通图中,从某个顶点出发,经 过不同的线路,又回到原出发点,这样的线路必 是尤拉图,即能一笔画出的图必是尤拉图。

中国邮递员问题
? 一个邮递员送信,要走完他负责投递的全部街道, 投完后回到邮局,应该怎样走,使所走的路程最 短? ? 这个问题是我国管梅谷同志1962年首先求出来的, 因此在国际上通称为中国邮递员问题。在物流活 动中,经常会遇到这样的问题,如:每天在大街 小巷行驶的垃圾车、洒水车、各售货点的送货车 等都需要解决一个行走的最短路程问题。 ? 这个问题就是一笔画问题。

? 解决这样的问题,可以采用奇偶点图上作业法: 如果在配送范围内,街道中没有奇点,那么他 就可以从配送中心出发,走过每条街道一次, 且仅一次,最后回到配送中心,这样他所走的 路程也就是最短的路程。

? 对于有奇点的街道图,该怎么办呢? ? 这时就必须在每条街道上重复走一次或多次。

? 如果在某条路线中,边[vi,vj]上重复走几次,我们就在 图中vi,vj之间增加几条边,令每条边的权和原来的权相 等,并把所增加的边,称为重复边,于是这条路线就是 相应的新图中的尤拉图。 ? 原来的问题可以叙述为在一个有奇点的图中,要求增加 一些重复边,使新图不含奇点,并且重复边的总权为最 小。 ? 我们把使新图不含奇点而增加的重复边简称为可行(重 复边)方案,使总权最小的可行方案为最优方案。

? 现在的问题是第一个可行方案如何确定? ? 在确定一个可行方案后,怎么判断这个方案是否 为最优方案? ? 若不是最优方案,如何调整这个方案?

案例
? 车辆从某配送中心(v1) 出发,给街道边上的超 市 (v2,v3,v4,v5,v6,v7,v8, v9)送货,如图4-8所示。
v1 5 6 2 v8 4 v7 3 4

3

v2 5

v9

v6

4 9 4 v4 图1

4

v3

v5

? 显然街区图上有奇点(4个),不满足“一 笔画”的条件,则必然有一些街道要被重复 走过(添加重复边)才能回到原出发点。此 时得到的图就无奇点。 ? 那么该怎样添加重复边,使得图中全为偶点 呢? ? 其实可以通过连接匹配的奇点得到!

第一步:确定初始可行方案
v1 5 2 v8

4

v7 3

3

v2 5

6

v9

4

v6

4 9

4

4
v4 图2 v5

v3

? 这样就得到初始方案.在这个图中,没有奇点,故 称它为欧拉图。对应于这个可行方案,重复边总 权为51。

想一想
? 这样的可行方案是不是只有一种呢? ? 在确定一个可行方案后,怎么判断这个方案是否 为最优方案? ? 若不是最优方案,如何调整这个方案?

第二步:调整可行方案
? 最优方案必须满足以下(1)(2)两个条件: ? (1)在最优方案中,图的每一边最多有一条重 复边 ? (2)在最优方案中,图中每个圈上的重复边的 总权不大于该圈总权的一半。 为什么?

第二步:调整可行方案
? 首先,去掉多余的重复边,使图中每一边 最多有一条重复边。见图3

v 1 5 v 2 5 v 3

2

v 8 3 v 9

4

v 7 3 v 6

6

4

4 9 v 4
图3

4 4 v 5

第二步:调整可行方案
? 其次,如果把图中某个圈上的重复边去掉,而给 原来没有重复边的边上加上重复边,图中仍然没 有奇点。因而如果在某个圈上重复边的总权数大 于这个圈的总权数的一半,像上面所说的那样做 一次调整,将会得到一个总权下降的可行方案。

第二步:调整可行方案
? 在图4-10中,圈(v2,v3,v4, v9,v2)的总长度为 24,但圈上重复边总权为14,大于该圈总长度的 一半,因此可以做一次调整,以[v2,v9],[v9,v4] 上的重复边代[v2,v3],[v3,v4]上的重复边,使重 复边总长度下降为17。见图4

v 1 5 v 2 5 v 3

2

v 8 3 v 9

4

v 7 3 v 6

6

4

4 9 v 4
图4

4 4 v 5

? 检查图4中圈(v1,v2, v9, v6,v7, v8,v1)的总长 度为24,但圈上重复边总权为13,大于该圈总长 度的一半,因此可以做一次调整,使重复边总长 度下降为15。见图5。

v1 5 v2 5 v3

2

v8 3 v9 4

4

v7 3

6

4

v6 4

9

v4

4

v5

图5

? 检查图5,均满足条件(1)和(2),于是得到最 优方案。图5中的任一欧拉圈都是汽车的最优配送 路线。 ? 如:v1-v2-v9-v8-v1-v8-v7-v6-v5-v4-v9-v6-v9-v4v3-v2-v1是汽车的一条最优配送路线。


相关文档

  • 网络优化的数学模型—1分析
  • 网络优化(数学建模资料)
  • 网络优化的数学模型—2资料
  • 数学建模网络优化
  • 网络优化的数学模型—2
  • 网络优化的数学模型—3
  • 数学建模之网络优化与优化算法
  • 基于数学模型的网络优化方法研究
  • 网络优化数学建模论文实例
  • 数学建模网络优化 钢管运输
  • 电脑版