线性规划的对偶性和最大流最小割定理
目录线性规划及对偶形式最大流最小割定理线性规划及对偶形式线性规划即mincTxs.t.Ax⩾bx⩾0\begin{aligned}\min\quad&c^Tx \\s.t. \quad &Ax\geqslant b \\&x\geqslant 0\end{aligned}mins.t.cTxAx⩾bx⩾0对偶形式为maxbTys.t.Ay⩽cy⩾0\begin{al
·
线性规划及对偶形式
线性规划即
min c T x s . t . A x ⩾ b x ⩾ 0 \begin{aligned} \min\quad &c^Tx \\ s.t. \quad &Ax\geqslant b \\ &x\geqslant 0 \end{aligned} mins.t.cTxAx⩾bx⩾0
对偶形式为
max b T y s . t . A y ⩽ c y ⩾ 0 \begin{aligned} \max \quad &b^Ty \\ s.t. \quad &Ay\leqslant c \\ &y\geqslant 0 \end{aligned} maxs.t.bTyAy⩽cy⩾0
总有 b T y = x T A T y ⩽ c T x b^T y = x^TA^Ty \leqslant c^Tx bTy=xTATy⩽cTx
最大流最小割定理
该定理是线性规划对偶性的很好应用，Wiki写的很好，直接贴Wiki最大流最小割定理
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
1
0- 0
已为社区贡献3条内容
所有评论(0)