-
Notifications
You must be signed in to change notification settings - Fork 43
/
23Networkoptimizationmodels.Rmd
139 lines (85 loc) · 6.81 KB
/
23Networkoptimizationmodels.Rmd
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
---
title: "网络优化模型"
author: "魏依洋"
date: "2021/10/20"
output: word_document
---
#1.简介
网络优化即研究如何有效的计划、管理和控制网络系统，使之发挥最大的社会和经济效益。由于网络优化模型可用网络图表示，这种可视性为直观解释数学规划理论和方法提供了很好的途径，网络优化就是研究与（赋权）图有关的最优化模型，与图论有一定的联系。
#2.典型模型
典型模型包括最短路径问题、最大流问题、最小生成树问题(MST)、旅行商问题(TSP)等.
##2.1 最短路径问题
###2.1.1 定义
最短路径问题旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。简单的问题为：在一个图上，求一个点到其他点的最短距离，即单源最短路。
###2.1.2 算法
最短路的算法有很多，如Dijkstra，floyd，bellman-ford等。
Diikstra算法寻找从给定源顶点到网络中其他顶点的最短距离，这样做时要考虑到边的长度，它的工作原理是保存目前为止它找到的每个顶点的最短距离的记录，并在找到更短的记录时更新该记录。在算法的最后，找到的到每个顶点的最短距离实际上是任何路径可能的最短距离。具体算法如下：
1.找到网络中到s的估计距离最小的顶点v，我们并不确定这是与什么有关的一段最小距离。
2.标记这个距离是确定的。
3.计算从s通过v到v的每个邻居的距离，方法是把v到每个邻居的边的长度加上s到v的距离。如果得到的距离有小于到同一邻居的当前估计距离，则新距离将取代旧距离。
4.我们重复第一步，直到所有的顶点都被标记为确定的。
##2.2最大流问题
###2.2.1 定义
最大流问题就是要讨论如何充分利用装置的能力，使得运输的流量最大，以取得最好的效果，网络中一个可行流f*，使其流量v(f)达到最大， 这种流f称为最大流，最大流问题可以建立如下形式的线性规划数学模型：
$$\begin{array}{cl}
\max V=f^{*} & \\
s . t\left\{\begin{array}{ll}
\sum f_{i j}-f_{j i}=0 & (i \neq s, t) \\
\sum f_{s j}-f_{j s}=v(f) & (i=s) \\
\sum f_{i j}-f_{j i}=-v(f) & (i=t)
\end{array}\right.
\end{array}$$
###2.2.2最大流最小割定理
如果$f$是具有源点$s$和汇点$t$的流网络$G=(V,E)$中的一个流,则下列条件是等价的：
(1)$f$是$G$的一个最大流。
(2)残留网络$G_{f} $不包含增广路径。
(3)对$G$的某个割$(S, T)$，有$|f|=c(S, T)$。
###2.2.3 算法
解决最大流问题用到增广路径算法即Fold-Fulkerson算法。
增广路径算法基本思想：我们首先使用宽度优先搜索算法找到一条从源$s$到目标t的路径，这“耗尽"了网络中的一些边，将它们填满，使它们无法承载更多的流量。然后在剩余的边中寻找从$s$到$t$的另一条路径，重复这个过程，直到找不到其他路径。最大流最小割定理将说明在算法终止时，这一过程可产生出最大流。
##2.3最小生成树问题
### 2.3.1 定义
连通的无向图$G$的一个生成树是图G的一个子图，该子图是包含图$G$所有顶点的一个树。尽管每个生成树的边数相同，然而每个生成树的边的权值之和未必相同，其中权值之和最小的生成树就称为最小生成树。
### 2.3.2 算法
解决最小生成树问题共有两种算法：prim算法与Kruskal算法
假设$G=(V,E,W)$是一个具有$N$个顶点的连通图，$T=（U,TE)$为欲构造的最小生成树。
Prim算法和Kruskal算法的基本思想如下：
Prim算法:初始时，$U=\left \{u_{0}\right\}$为图G中任一顶点,$TE$为空集。在所$u\in U,v\in V-U$ 有的边中，选择一条权值最小的边$\left ( u,v \right )$ 加人边集$TE$,同时将顶点加人点集$U$。重复这一操作，直到$U=V$，即包含图$G$中的全部顶点为止。
Kruskal算法:初始时，$U=V$,$TE$为空集。将图$G$中的边按权值从小到大的顺序依次选取，若选取的边使生成树不形成圈，则把它加人$TE$中;若选取的边使生成树形成圈，则将其舍弃，如此进行下去，直到$TE$中包含$N-1$条边为止。
Prim算法适合于计算边稠密的网络的最小生成树。Kruska算法适合于计算边稀疏的网络的最小生成树。
##2.4旅行商问题
假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径长度为所有路径之中的最小值。
解决办法主要有遗传算法、模拟退火法、蚁群算法、禁忌搜索算法、贪婪算法和神经网络等。
#3.模型综合应用
制作一个有向图，求从顶点0到顶点7的最大流量(此时图中各条边上的数字代表容量限制)；找出该连通图的最小生成树；求出该图中任意两顶点之间的最短路程(考虑方向)。
##3.1 R语言代码实现
```{r}
library(igraph) #载入包
e<-matrix(nc=3,byrow=TRUE,c(1,2,6, 1,3,6, 1,4,3, 2,5,5,
2,6,3, 3,6,3, 3,7,2, 4,7,2, 5,2,5, 5,8,4, 6,8,3, 7,8,4))
g = add.edges(graph.empty(8), t(e[,1:2]), weight = e[,3]) #构造图
tkplot(g,vertex.color="yellow") #绘制网络图
graph.maxflow(g,1,8,capacity=E(g)$weight)#最大流
mst = minimum.spanning.tree(g) #最小生成树
tkplot(mst,vertex.color="yellow") #绘制最小生成树
(tree_min = sum(E(mst)$weight)) #计算并输出最小生成树的权
shortest.paths(g, mode = "out") #最短路矩阵
```
##3.2 结果
最大流为11，最小生成树的权为20，生成的最短路矩阵为
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
[1,] 0 6 6 3 11 9 5 9
[2,] Inf 0 Inf Inf 5 3 Inf 6
[3,] Inf Inf 0 Inf Inf 3 2 6
[4,] Inf Inf Inf 0 Inf Inf 2 6
[5,] Inf 5 Inf Inf 0 8 Inf 4
[6,] Inf Inf Inf Inf Inf 0 Inf 3
[7,] Inf Inf Inf Inf Inf Inf 0 4
[8,] Inf Inf Inf Inf Inf Inf Inf 0
#4.总结和反思
在某些类型的网络中，结构优化是一种重要的网络形成机制。在某些情况下，如在运输网络或分销网络中，网络是专门设计来实现一个或多个特定目标的，如在全国投递邮件包裹或将航空旅客运送到目的地，网络的结构对实现目标的效率有很大的影响
在这些情况下，网络的结构不是由生长机制来解释的，而是由网络被设计来优化某些特性这一事实来解释的。网络优化模型有时并不能找到全局最优解，所以人们不得不使用近似最优值。
本文并没有对网络优化模型下的具体模型做具体的解释，存在很大的不足。
#5.参考文献
[1]M.E.J.Newman.Networks An Introduction[M].2010
[2]汪小帆，李翔，陈关荣.网络科学导论[M].2012