计算科学 - 网络流问题中的可拆分流和不可拆分流 - 吾爱随笔录

我正在研究一个多商品流问题，其中的图表 $G=(V, E)$ ，一些流被允许拆分，一些流应该严格遵循一条路径。我将这个问题表述如下。

问题表述

min \sum_{(i, j) \in E} \sum_{f \in F} c_{i j}^{f} x_{i j}^{f}

$\min \sum_{(i,j) \in E} \sum_{f \in F} c_{ij}^fx^f_{ij}$

\sum_{j \in V} x_{i j}^{f} - \sum_{j \in V} x_{j i}^{f} = {\begin{cases} d_{f} & , & i = s_{f} \\ - d_{f} & , & i = t_{f} \\ 0 & , & otherwise \end{cases}

$\sum_{j \in V}x^f_{ij} - \sum_{j \in V}x_{ji}^f = \begin{cases} d_f &, & i = s_f \\ -d_f&, & i = t_f\\ 0 &,& \text{otherwise} \end{cases}$

x_{i j}^{f} \geq {\begin{cases} 0 & , & f \in S \\ d_{f} & , & f \in N S \end{cases} \forall (i, j) \in E

$x_{ij}^f \ge \begin{cases} 0 & , & f \in S\\ d_f & , & f \in NS\\ \end{cases} \quad \forall (i, j) \in E$

\sum_{i, j \in E} x_{i j}^{f} \leq u_{i j}

$\sum_{i,j \in E} x_{ij}^f \le u_{ij}$

其中是流量的需求。是允许拆分的是不可拆分的流的集合。是边的容量。 $d_f$ $f$ $S$ $NS$ $u_{ij}$ $(i, j)$

我是线性规划的新手。在纸上，使用两个简单的图表，这个公式似乎工作得很好。

如果有人能指出这个提法是否有任何问题，我将不胜感激。