Java教程

线性规划转对偶网络流问题小记?

本文主要是介绍线性规划转对偶网络流问题小记?,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

二元线性规划问题转网络流:对于 \(n\) 个变量 \(x_i\),限制形如 \(x_i-x_j\ge b\)\(x_i\ge b\)\(x_i\le b\),求 \(\sum c_ix_i\) 的最小值,可以转化成上下界最大费用流求解。

首先重温线性规划问题的一般形式(之一):

\[\begin{aligned} &\textbf{minimize }c^Tx, \texttt{ where } Ax\ge b\\ \iff&\textbf{maximize }y^Tb, \texttt{ where } yA\le c^T \end{aligned} \]

当所有限制都形如 \(x_i-x_j\ge b\) 的时候,矩阵 \(A\) 的每一行都至多有一个 \(+\) 和一个 \(-\)。设向量 \(x\) 的长度为 \(n\),矩阵 \(A\) 的大小为 \(m\times n\)

考虑构造一个 \(n\) 个点 \(m\) 条边的网络流图(不包括源汇),令 \(y_i\) 表示第 \(i\) 条边流过的流量。那么 \(\textbf{maximize }y^Tb\) 的条件就代表第 \(i\) 条边的费用是 \(b_i\),即连一条 \((u,v,+\infty,b_i)\) 的边,然后求最大费用流。

对于 \(yA\le c^T\),可以发现 \(y\) 乘上 \(A\) 的每一列的信息可以视为关于那个节点的信息,\(+\) 代表从这个节点流出,\(-\) 表示流入。那么,如果 \(c_i\ge 0\),条件即为 \(out-in\le c_i\),可以用 \((S,i,c_i,0)\)\((i,T,+\infty,0)\) 表示;如果 \(c_i< 0\),条件即为 \(in-out\ge -c_i\),可以用 \((i,T,[-c_i,+\infty),0)\) 表示。

这篇关于线性规划转对偶网络流问题小记?的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!