哥尼斯堡的七座桥
运筹学 经典 重要
旅行商问题(TSP-traveling salesman problem) 最短路问题(SPP-shortest path problem)
图的基本概念
$n$ 图 $G=(V,E)$ $V$ 顶点集 $E$ 边集
$e\in E$ 有向图 $e\in E$ 无向图 混合图
相邻 起点 终点 端点 自环 $G$ 重边 简单图
$v$ 度 $v$ 出度 $v$ 入度
图的邻接矩阵(adjacency matrix)表示法
$G=(V,E)$ $C=(c_{ij})$
\[c_{ij}=\begin{cases} 1 , (v_i,v_j)\in E \\
0 , (v_i,v_j)\notin E
\end{cases}
\]
$V$ $|V|=n$ $E$ $|E|=m$ $n\times n$ $m$ 赋权图
例 1 .
\[\begin{pmatrix}
0 & 1 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 \\
0 & 1 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 \\
0 & 0 & 1 & 1 & 0 \\
\end{pmatrix}
\]
$n^2$ $m$
关联矩阵表示法(incidence matrix)
$G=(V,E)$ $B=(b_{ij})$
\[b_{ij}=\begin{cases}
1 , & \exists v_k\in V, s.t. e_j=(v_i, v_k)\in E \\
-1 ,& \exists v_k\in V, s.t. e_j=(v_k, v_i)\in E \\
0, & otherwise \\
\end{cases}
\]
$v_i$ $e_j$ $b_{ij}=1$ $b_{ij}=-1$ $b_{ij}=0$
$1$ $-1$
例 2 .
\[\begin{pmatrix}
1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
-1 & 0 & 1 & -1 & 0 & 0 & 0 & 0 \\
0 & -1 & 0 & 1 & -1 & 0 & -1 & 0 \\
0 & 0 & -1 & 0 & 1 & 1 & 0 & -1 \\
0 & 0 & 0 & 0 & 0 & -1 & 1 & 1 \\
\end{pmatrix}
\]
弧表表示
邻接表表示法
最短路问题
问题如下
$G$ $V$ $G$ $E$ $G=(V,E)$ $G$ $e$ $w(e)$ $e$ $G$ $W=(w_{ij})$ $v_i$ $v_j$ $w_{ij}=\infty$
$G$ $u_0$ $v_0$ $u_0$ $v_0$ 最短路 $u_0$ $v_0$ $d(u_0,v_0)$
迪克斯特拉(Dijkstra)算法
Floyd算法
迪克斯特拉(Dijkstra)算法
$l( u_0 ) = 0$ $v \neq u_0$ $l ( v ) = \infty$ $S_0=\{u_\}, i=0$ $v\in \bar S_i$ $\bar S_i = V \\ S_i$
\[\min\{l(v), l(v)+w(uv)\}
\]
$l ( v )$ $w(uv)$ $u$ $v$ $\min \{ l ( v )\}$ $u_{i+1}$ $S_{i+1}=S_i\cup\{u_{i+1}\}$ $i = | V | − 1$ $i < | V | − 1$ $i + 1$ $i$
例 3 . $c_1,c_2,\cdots,c_6$ $c_i$ $c_j$ $(i,j)$ $\infty$ $c_1$
\[\begin{pmatrix}
0 & 50 & \infty & 40 & 25 & 10 \\
50 & 0 & 15 & 20 & \infty & 25 \\
\infty & 15 & 0 & 10 & 20 & \infty \\
40 & 20 & 10 & 0 & 10 & 25 \\
25 & \infty &20 & 10 & 0 & 55 \\
10 & 25 & \infty & 25 & 55 0
\end{pmatrix}
\]
import networkx as nx
# create a undirected graphs.
G = nx.Graph ()
G .add_node(1 ,name= " 1 " )
G .add_node(2 )
G .add_node(3 )
G .add_node(4 )
G .add_node(5 )
G .add_node(6 )
# add edges with weight: price
G .add_edge(1 , 2 , price= 50 )
G .add_edge(1 , 4 , price= 40 )
G .add_edge(1 , 5 , price= 25 )
G .add_edge(1 , 6 , price= 10 )
G .add_edge(2 , 3 , price= 15 )
G .add_edge(2 , 4 , price= 20 )
G .add_edge(2 , 6 , price= 25 )
G .add_edge(3 , 4 , price= 10 )
G .add_edge(3 , 5 , price= 20 )
G .add_edge(4 , 5 , price= 10 )
G .add_edge(4 , 6 , price= 25 )
G .add_edge(5 , 6 , price= 55 )
#
sp= nx.dijkstra_path(G ,1 ,4 , weight= ' price ' )
print (sp)
Python
networkx.dijkstra_path
Uses Dijkstra’s Method to compute the shortest weighted path between two nodes in a graph
例 4 . 渡河问题
模型
$(0,1,1,0)$
\[\begin{aligned}
(1,1,1,1), (1,1,1,0), (1,1,0,1), (1,0,1,1), (1,0,1,0) \\
(0,1,0,1), (0,1,0,0), (0,0,1,0), (0,0,0,1), (0,0,0,0)
\end{aligned}
\]
$(1,1,1,1)$ $(0,0,0,0)$
['1111', '0101', '1101', '0001', '1011', '0010', '1010', '0000']import networkx as nx
# create a undirected graphs.
G = nx.Graph ()
# add edges with weight: price
G .add_edge(" 1111 " ," 0101 " , weight= 1 )
G .add_edge(" 1110 " ," 0010 " , weight= 1 )
G .add_edge(" 1110 " ," 0100 " , weight= 1 )
G .add_edge(" 1101 " ," 0001 " , weight= 1 )
G .add_edge(" 1101 " ," 0101 " , weight= 1 )
G .add_edge(" 1101 " ," 0100 " , weight= 1 )
G .add_edge(" 1011 " ," 0001 " , weight= 1 )
G .add_edge(" 1011 " ," 0010 " , weight= 1 )
G .add_edge(" 1010 " ," 0000 " , weight= 1 )
G .add_edge(" 1010 " ," 0010 " , weight= 1 )
sp= nx.dijkstra_path(G ,' 1111 ' ,' 0000 ' )
print (sp)
$W=v_0e_1v_1e_2\cdots e_kv_k$ $e_i\in E$ $v_j\in V$ $e_i=(v_{j-1},v_j)$ $W$ $G(V,E)$ 道路 $k$ $v_0$ $v_k$ 迹 轨道 $P(v_0,v_k)$ 圈 连通图
树 $T$ 叶子顶点
$G=(V_G,V_E)$ $T=(V_T,E_T)$ $V_G=V_E$ $E_T\subset E_G$ $T$ $G$ 生成树
$G$ $G$
最小生成树
最小生成树
例 5 . $i$ $j$ $c_{ij}$
networkx.minimum_branching(G, attr='weight', default=1, preserve_attrs=False)[source]
Returns a minimum branching from G.
maximum_flow(flowG, _s, _t, capacity='capacity', flow_func=None, **kwargs)[source]
Find a maximum single-commodity flow.
最大流问题
例 6 . $s$ $t$ $v_1$ $v_2$ $v_3$ $v_4$ $s$ $t$
(14, {'s': {1: 7, 3: 7}, 1: {2: 5, 3: 2}, 2: {'t': 5, 3: 0}, 3: {4: 9}, 4: {'t': 9, 2: 0}, 't': {}})import networkx as nx
# create a undirected graphs.
G = nx.DiGraph ()
# add edges with weight: capacity
G .add_edge(' s ' , 1 , capacity= 8 )
G .add_edge(' s ' , 3 , capacity= 7 )
G .add_edge(1 , 3 , capacity= 5 )
G .add_edge(1 , 2 , capacity= 9 )
G .add_edge(2 , 3 , capacity= 2 )
G .add_edge(3 , 4 , capacity= 9 )
G .add_edge(4 , 2 , capacity= 6 )
G .add_edge(2 , ' t ' , capacity= 5 )
G .add_edge(4 , ' t ' , capacity= 10 )
#
sp= nx.maximum_flow(G ,' s ' ,' t ' )
print (sp)
$G=(V,E)$ $V$ $v_s$ $v_t$ $(v_i,v_j)\in E$ $c(v_i,c_j)\geq 0$ $c_{ij}$ 容量 网络 $D=(V,E,C)$ $C=\{c_{ij}\}$
流 $E$ $f=\{f_{ij}\}=\{f(v_i,v_j)\}$ $f_{ij}$ $(v_i,v_j)$ 流量
标号法
流
$0\leq f_{ij}\leq c_{ij}$
\[\sum_{j:(v_i,v_j)\in E} f_{ij}-\sum_{j:(v_j, v_i)\in E} f_{ji}=0
\]
$v_s$ $v(f)$
\[\sum_{j:(v_s,v_j)\in E} f_{sj}-\sum_{j:(v_j, v_s)\in E} f_{js}=v(f)
\]
$v_t$
\[\sum_{j:(v_t,v_j)\in E} f_{tj}-\sum_{j:(v_j, v_t)\in E} f_{jt}=-v(f)
\]
最小费用最大流问题
$D=(V,E,C)$ $c_{ij}$ $b_{ij}\geq0$ 最小费用最大流量问题 $v_s$ $v_t$
\[\displaystyle\sum_{(v_i,v_j)\in E} b_{ij}f_{ij}
\]
例 7 .
(205, {1: {2: 7, 3: 1}, 2: {3: 2, 't': 5}, 3: {4: 9}, 's': {1: 8, 3: 6}, 4: {2: 0, 't': 9}, 't': {}})import networkx as nx
# create a undirected graphs.
G = nx.DiGraph ()
# add edges with weight: capacity
G .add_node(' s ' , demand = -14 ) # 最大流出量是14
G .add_node(' t ' , demand = 14 ) # 收点流量是14
G .add_edge(' s ' , 1 , capacity= 8 , weight= 2 )
G .add_edge(' s ' , 3 , capacity= 7 , weight= 8 )
G .add_edge(1 , 3 , capacity= 5 , weight= 5 )
G .add_edge(1 , 2 , capacity= 9 , weight= 2 )
G .add_edge(2 , 3 , capacity= 2 , weight= 1 )
G .add_edge(3 , 4 , capacity= 9 , weight= 3 )
G .add_edge(4 , 2 , capacity= 6 , weight= 4 )
G .add_edge(2 , ' t ' , capacity= 5 , weight= 6 )
G .add_edge(4 , ' t ' , capacity= 10 , weight= 7 )
sp= nx.capacity_scaling(G )
print (sp)
capacity_scaling(G, demand='demand', capacity='capacity', weight='weight', heap=<class 'networkx.utils.heaps.BinaryHeap'>)[source]
Find a minimum cost flow satisfying all demands in digraph G.
人员分派问题
例 8 . 人员分派问题 $X=\{x_1,x_2,\cdots,x_n\}$ $n$ $Y=\{y_1,y_2,\cdots,y_n\}$
模型 $X\cup Y$ $x_i$ $y_j$ $(x_i,y_j)\in E$ $G=(X\cup Y, E)$ $E$
定义 1 . $M\subset E(G)$ $\forall e_i,e_j\in M$ $e_i$ $e_j$ $i\neq j$ $M$ $G$ 对集 $M$ $M$ 相配 $M$ $M$ 许配 $G$ $M$ $M$ 完美对集 $G$ $| M' | > | M |$ $M'$ $M$ 最大对集
人员分派问题
最优分派问题
数学模型 $G$ $w(x_i,y_j)\geq 0$ $x_i$ $y_j$ $G$
旅行商(TSP)问题
例 9 . (Traveling Salesman Problem ) 旅行商问题
定义 2 . $G$ Hamilton(哈密顿)轨 Hamilton圈 H圈 Hamilton 图
$C$ $C$ 改良圈算法
openopt.TSP .solvedwave_networkx.algorithms.tsp.traveling_salesman — D -Wave NetworkX 0.7 .1 documentation
pip install dwave_networkx
例 10 .
[0, 2, 1, 5, 4, 3]
has a distance of
211
distances= []
#go through each type of cycle we can have (1-7)
for i in range(len(G )): #range(1,8): #1-8 because range is not inclusive
for path in nx.all_simple_paths(G , source= 0 , target= i, cutoff= len(G )):
if (len(path)==len(G )):
distance= 0
for j in range(len(G )-1 ):
distance= distance+G [path[j]][path[j+1 ]][' weight ' ]
distance= distance+G [0 ][i][' weight ' ]
#add these to a list
distances.append((distance,path))
min_dist= distances[0 ][0 ];
min_path= []
#find the min distance
for dist in distances:
if (dist[0 ]<=min_dist):
min_dist= dist[0 ]
min_path= dist[1 ]
print (min_path)
中国邮递员问题
例 11 . (Chinese Postman Problem )
定义 3 . $G$ $G$ Euler 迹 Euler 回路 E回路 Euler 图
networkx.eulerian_circuit
Returns an iterator over the edges of an Eulerian circuit in G .
An Eulerian circuit is a closed walk that includes each edge of a graph exactly once.
计划评审方法和关键路线法
计划评审方法 关键路线法
统筹方法
例 12 .
工作 事件 计划网络图
$x_i$ $i$ $1$ $n$ $x_n-x_1$ $t_{ij}$ $( i , j )$ $i$ $j$
规划问题
目标 $\min(x_n-x_1)$
约束
\[\begin{cases}
x_j\geq x_i+t_{ij} , (i,j)\in E, i,j\in V \\
x_i\geq 0, i\in V
\end{cases}
\]
$V$ $E$
51
[0 , ' b ' , ' g ' , 1 , ' k ' ]关键路线
$x_{ij}$ $0-1$ $(i, j)$
目标 $\displaystyle\max \sum_{(i,j)\in E}t_{ij}x_{ij}$
约束
\[\begin{aligned}
\sum_{j=1,(i,j)\in E}^n x_{ij}-\sum_{j=1,(j,i)\in E}^n x_{ji}=\begin{cases} 1, & i=1 \\ -1, & i=n \\ 0, & i\neq 1,n \end{cases} \\
x_{ij}=0\ \mbox{or}\ 1, (i,j)\in E
\end{aligned}
\]
例 13 .
$x_i$ $i$ $t_{ij}$ $(i,j)$ $m_{ij}$ $(i,j)$ $y_{ij}$ $(i,j)$ $c_{ij}$ $(i,j)$
\[x_j-x_i \geq t_{ij}-y_{ij}, 0\leq y_{ij}\leq t_{ij}-m_{ij}
\]
$d$ $1$ $n$ $x_n-x_1\leq d$
规划问题
目标 $\displaystyle\min\sum_{(i,j)\in E}c_{ij}y_{ij}$
约束
\[\begin{cases}
x_j-x_i+y_{ij} \geq t_{ij} , (i,j)\in E, i,j\in V \\
x_n-x_1\leq d \\
0\leq y_{ij}\leq t_{ij}-m_{ij}, (i,j)\in E, i,j\in V \\
\end{cases}
\]
钢管订购和运输
例 14 . $A_1\to A_2\to\cdots\to A_{15}$ $S_1,\cdots,S_7$
$A_1$ $A_2$ $\cdots$ $A_{15}$
$S_i$ $s_i$ $p_i$
$s_i$ $p_i$
模型的建立与求解 $i$ $s_i$ $i$ $j$ $c_{ij}$ $l_j$ $j$ $x_{ij}$ $i$ $j$ $y_j$ $j$ $z_j$ $j$
$S_i$ $A_j$ $c_{ij}$ $c_{ij}$ $c_{ij}$ $S_i$ $A_j$ $i = 1 , 2 , \cdots , 7$ $j = 1 , 2 , \cdots , 15$ $A_{j}A_{j+1}$ $j = 1 , 2 , \cdots , 14$
$S_i$ $A_j$ $c_{ij}$
先算铁路运输费用
$G_1 = ( V , E_1 , W_1 )$
\[V = \{ S_1,\cdots,S_7,A_1,\cdots,A_{15}, B_1,\cdots, B_{17} \}
\]
$W_1=(w_{ij})$ $V$ $i$ $j$ $w_{ij}$ $d^1_{ij}$ $w_{ij}=\infty$
$c^1_{ij}$
算公路运输费用
$G_2 = ( V , E_2 , W_2 )$
\[V = \{ S_1,\cdots,S_7,A_1,\cdots,A_{15}, B_1,\cdots, B_{17} \}
\]
$W_2=(w^2_{ij})$ $V$ $i$ $j$ $w^2_{ij}$ $d^2_{ij}$ $w^2_{ij}=\infty$
$c^2_{ij}$
计算任意两点间的最小运输费用
$G=(V,E,W)$ $W=(w_{ij})=(\min(c^1_{ij},c^2_{ij}))$ $G$ $S_i$ $A_j$ $\bar c_{ij}$ $S_i$ $A_j$ $c_{ij}$
目标
\[\min \sum_{i=1}^7\sum_{j=1}^{15}c_{ij}x_{ij}
+\frac{0.1}2\sum_{j=1}^{15}[z_j(z_j+1)+y_j(y_j+1)]
\]
约束
\[\begin{cases}
\sum_{j=1}^{15}x_{ij}\in\{0\}\cup[500,s_i] , i=1,2,\cdots,7 \\
\sum_{j=1}^7x_{ij}=z_j+y_j , j=1,2,\cdots,15 \\
y_{j+1}+z_j=l_j , j=1,2,\cdots,14 \\
x_{ij}\geq 0, z_j\geq 0, y_j\geq 0, i=1,2,\cdots,7, j=1,2,\cdots, 15 \\
y_1=0, z_{15}=0
\end{cases}
\]
$A_j$ $x_{ij}$ $i$ $z_j$ $y_j$ $y_{j+1}$ $z_j$ $A_jA_{j+1}$ $l_j$ $A_j$ $A_j A_{j-1}$ $1 + \cdots + y_j = y_j ( y_j + 1 ) / 2$
