$$ \min c^Tx\\ s.t.Ax=b,x\ge0\\A\in\mathbb R^{m\times n}_m，b\ge0 $$

标准型进一步要求：目标函数取最小值$\min$，矩阵$A$为行满秩矩阵，系数$b$非负(方便化归、找b.f.s.).

$$ M=\{x\in\mathbb R^n\mid A\bm x=\bm b,\bm x\ge 0\}. $$

如何化归

• 引入松弛变量，拆分变量为两个非负变量之差。利用系数$b$非负。

  $$ Ax+z=b,x\ge 0\to\begin{pmatrix}A&I_m\end{pmatrix}\begin{pmatrix}x\\z\end{pmatrix}=b,x\ge 0,z\ge 0. $$