问题描述
多商品网络流问题（Multicommodity Network Flow, MCNF）是指在一个图网络中，多个商品从各自起点运输到各自终点的问题。
更具体的，给定一个图网络 G = ( V , A ) G=(V, A) G=(V,A)：
K K K：表示商品的集合；
( s k , t k , d k ) (s_k,t_k, d_k) (sk,tk,dk)：表示商品 k k k的起点、终点和需求量；
u i j u_{ij} uij：弧段 ( i , j ) ∈ A (i, j) \in A (i,j)∈A的容量；
c i j k c_{ij}^k cijk：商品 k k k在弧段 ( i , j ) ∈ A (i, j) \in A (i,j)∈A上流动的单位成本。
MCNF问题的目标就是在图网络中，找到一条使得总运输成本最低，且能满足各个商品需求量的路径。
数学建模
变量：
x
i
j
k
x_{ij}^k
xijk：商品
k
k
k在弧段
(
i
,
j
)
(i, j)
(i,j)上运输的货量；
m i n ∑ ( i , j ) ∈ A ∑ k ∈ K c i j x i j s . t . ∑ j x i j − ∑ j x j i = { d k , i = s k , k ∈ K − d k , i = t k , k ∈ K 0 , e l s e , ∀ i ∈ V , k ∈ K , i ≠ s k , j ≠ t k ∑ k ∈ K x i j k ≤ u i j , ∀ ( i , j ) ∈ A min \sum_{(i, j)\in A}\sum_{k \in K}c_{ij}x_{ij}\\ s.t. \sum_jx_{ij} - \sum_jx_{ji} =\begin{cases} d_k, i=s_k,k\in K\\ -d_k, i=t_k, k\in K\\ 0, else, \forall i \in V, k \in K, i \neq s_k, j \neq t_k \end{cases}\\ \sum_{k\in K} x_{ij}^k \leq u_{ij}, \forall (i,j) \in A min(i,j)∈A∑k∈K∑cijxijs.t.j∑xij−j∑xji=⎩ ⎨ ⎧dk,i=sk,k∈K−dk,i=tk,k∈K0,else,∀i∈V,k∈K,i=sk,j=tkk∈K∑xijk≤uij,∀(i,j)∈A
目标函数表示最小化运输成本；
第一个约束为流量平衡约束，对于每个商品，分别对于其起点、终点和途径点做了约束（起点：流出-流入=需求量，终点：流出-流入= -需求量，途径点：流出-流入=0）；
第二个约束对网络中的每条边的流量做了约束，不得超过最大容量。
性质
当MCNF中的决策变量可以为小数时，该问题为一个线性规划问题；当MCNF中的决策变量仅能取整数时，该问题是一个NP-complete（也是NP-hard）问题。todo: 补一篇文章梳理一下NP-hard、NP-complete的含义。
问题求解
todo：python代码补充
参考资料
- 运筹优化常用算法、模型及案例实战：Python+Java 实现. 刘兴禄，熊望祺，臧永森，段宏达，曾文佳，陈伟坚.
