运筹学常用模型

By Z.H. Fu https://fuzihaofzh.github.io/blog/

在运筹学中，建模是解决实际问题的第一步，而常用的数学模型可以帮助我们更好地理解和解决各种复杂的管理和决策问题。本文将介绍一些运筹学中常用的数学模型，涵盖了运输问题、指派问题、网络问题以及它们的具体应用和求解方法。通过深入了解这些模型，您将能够更有效地处理与资源分配、路径规划和流量优化等相关的挑战。以下我们将一起探索这些有趣且实用的数学模型，为运筹学的应用提供更多的启发和帮助。

建模

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

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;
  }
}