这是一个最小成本的网络流问题。如下构建网络。您尚未指定$i$和$j$的范围，但我假设我们$i=1, 2, \ldots, m$和$j=1, 2, \ldots, n$。

• 一个源节点源单位的流。$s$$n$
• $m$个节点 ,。$u_{i}$$i=1, 2, \ldots, m$
• 到的弧，容量，。$s$$u_{i}$$c_{i}$$i=1, 2, \ldots m$
• $n$节点 ,。$v_{j}$$j=1, 2, \ldots, n$
• 弧，对于所有，每个容量为 1。$(u_{i},v_{j})$$i,j$
• 一个节点，它是单位流的汇。$t$$n$
• 从到的弧线，容量为。 $v_{j}$$t$$j=1, 2, \ldots, n$
• 到的弧上的权重 } 。其余弧的权重为 0。$W_{j,i}$$u_{i}$$v_{j}$

该图上的任何可行流都对应于上述问题的 LP 松弛的解决方案。由于 LP 的约束矩阵是完全单模的，因此任何最优 BFS 对于所有变量都具有整数值。 $X_{i,j}$

您可以使用单纯形法或使用专门的算法来解决此问题，以解决最小成本网络流问题。