运筹学常用模型

By Z.H. Fu
切问录 www.fuzihao.org

建模

Transportation

从\(i\)运输到\(j\)的费用为\(c_{ij}\)\(i\)地有资源\(s_i\),\(j\)地需要资源\(d_j\),运输量为待求\(x_{ij}\) \[\begin{aligned} \min &\ \ \ Z=\sum_{i=1}^m\sum_{j=1}^nc_{ij}x_{ij} \\ s.t.& \sum_{j=1}^nx_{ij}=s_i \ \ \ (i=1,2,\cdots,m) \\ & \sum_{i=1}^mx_{ij}=d_j\ \ \ (j=1,2,\cdots,n)\end{aligned}\] 有可行解充要条件:\(\sum_{i=1}^m s_i=\sum_{j=1}^n d_i\)。当产大于销或者销大于产时,引入dummy destination, dummy source

Assignment

把第\(i\)个人指派到第\(j\)个任务,\(c_{ij}\)为花费 : \[\begin{aligned} \min \ \ \ &Z=\sum_{i=1}^n\sum_{j=1}^nc_{ij}x_{ij}\\ s.t. &\sum_{j=1}^nx_{ij}=1 \ \ \ (i=1,2,\cdots,n)\\ &\sum_{i=1}^mx_{ij}=1\ \ \ (j=1,2,\cdots,n)\end{aligned}\]如果一个指派对象被指派多余一项任务,那么可以将其分解为多个相同指派对象;

Network

Shortest-path Problem

求两个节点间的最短路径: \[\begin{aligned}\min \ \ \ &z=\sum_{i=1}^n\sum_{j=1}^n c_{ij}x_{ij}\\ s.t. &\sum_{j=1}^nx_{1j}-\sum_{j=1}^nx_{j1}=1;\\ &\sum_{j=1}^nx_{ij}-\sum_{j=1}^nx_{j}=0,for\ 2\le i\le n-1;\\ &\sum_{j=1}^nx_{nj}-\sum_{j=1}^nx_{jn}=-1\end{aligned}\] #### The minimum spanning tree Prim: 选未连接节点中与已连接节点距离最小的,加边,并加入已连接节点。 Kruskal: 每次选最短的edge连接,如果它把两棵不同的树连接,则加入,否则跳过。 #### Maxium Flow 给定source和sink,限制有向图每条边的流量,求最大流量。如果有多个source和sink,则添加一个虚拟的source和sink; \[\begin{aligned}\max \ \ \ &z=\sum_{j=2}^Nx_{ij}\\ s.t. \ \ \ &\sum_{j=1,j\ne i}^Nx_{ij}-\sum_{j=1,j\ne i}^Nx_{ji}=0,for\ i=2,3,\cdots,N-1; \\&0\le x_{ij} \le c_{ij}, (c_{ij}=0\text{ if (i, j) is not a branch})\end{aligned}\]

  • min-cut:cut定义为一个集合,任意从source到sink的路径都至少有一个arc属于这个集合。其实就是把图按source和sink切成两半。cut value是这个cut中arc capacity的总和,一个图的max-cut等于min-cut。

  • 写成 Minimum Cost Flow Problem:选一个一定比最大流大的safe upper bound \(\bar{F}\),令source的\(b_i=\bar{F}\),sink的\(b_i=-\bar{F}\),把所有arc的cost设成0,再添加一条直接从source到sink的边,把这条边的cost设成大M,上限设为\(\infty\),这样\(\bar{F}\)会尽可能地从普通节点流到sink,而多余的部分则从新加的这条边流过。

Minimum Cost Flow Problem

是运输、指派、最短路径、最大流的抽象形式: \[\begin{aligned} \min \ \ \ &Z=\sum_{i=1}^n\sum_{j=1}^nc_{ij}x_{ij}\\ s.t. \ \ \ &\sum_{j=1}^nx_{ij}-\sum_{j=1}^nx_{ji}=b_i \ \ \ (\forall i=1,2,\cdots,n); 0\le x_{ij} \le u_{ij}\end{aligned}\] - 若arc \(i\rightarrow j\)不存在,则\(u_{ij}=0\); - \(b_i\)是节点\(i\)的净流出量,流出-流入=净流出; - 存在可行解的必要条件是\(\sum_{i=1}^nb_i=0\),若不满足,可以增加一个虚拟的source/sink使满足条件; - 若\(b_i,u_{ij}\)都有整数解,那么BFS也是整数解;

Dijkstra

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
DIJKSTRA(G,w,s)
{
InitialSingleSource(G,S);
S=phi;
Q=G.V;
while (Q is not $\phi$) {
u=Extract-Min(Q);
S=S$\cup${u};
for (each vertex v $\in$ G.Adj[u]){
Relax(u,v,w);
}
}
}

HEAP-EXTRACT-MIN(A)
{
if (A.heap-size < 1){
error “heap underflow”}
min=A[1];
A[1]= A[A.heap-size];
A:heap-size -= 1;
MIN-HEAPIFY(A,1);
return min;
}

RELAX(u, v, w){
if(v.d > u.d + w(u, v)){
v.d += w(u, v);
v.parent = u;
}
}