<aside> 🧸 线性规划：单纯形法，内点法。
Understanding and Using Linear Programming
</aside>
$$ \min \bm c^T\bm x\\ s.t.A\bm x=\bm b,\bm x\ge0.\\ \bm c,\bm x,\bm b\in\mathbb R^n,A\in\mathbb R^{m\times n} $$
【标准型】
【约束集】M 例如
$$ M=\left\{x\in\mathbb R^n\mid Ax\le b,x\ge0\right\}. $$
约束集$\Omega$是凸多胞体Krein-Milman theorem 。H支撑超平面
(对应simplex https://en.wikipedia.org/wiki/Simplex)
在多面体上极大化或极小化线性函数。
M是紧集（有界，闭集），LP有解，可能不唯一
无界集，LP不确定有解
标准型
$$ \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. $$
【分块】
从方程组入手，将A按列分块，将极大无关组移至前m列。A被划分为基向量组（基矩阵）和非基向量组（非基矩阵） ，x划分为基变量和非基变量
$$ Ax=\begin{pmatrix}B&D\end{pmatrix}\begin{pmatrix}\bm x_B\\\bm x_D\end{pmatrix}=\bm b $$
B 是可逆方阵。特殊的$B$、$B^{-1}$可以有由$b\ge 0$将可行解推至基本可行解。
$$ \begin{pmatrix}\bm x_B\\\bm x_D\end{pmatrix}=\begin{pmatrix}B^{-1}\bm b-B^{-1}D\bm x_D\\\bm x_D\end{pmatrix} $$
【基本解】
basic solution 为非基变量为零的解
$$ \begin{pmatrix}\bm x_B\\\bm x_D\end{pmatrix}=\begin{pmatrix}\bm B^{-1}\bm b\\0\end{pmatrix} $$
【基本可行解】
b.f.s. 既满足方程组的特解，解又非负 (满足约束条件)。
【LP基本定理】
非空约束集必有基本可行解；
线形规划问题有最优解，则必有一个最优解是基本可行解。
【极点就是基本可行解】
$x$是凸多面体的极点（顶点）【极点】 ↔$x$是M的基本可行解。
【充分性←】基本可行解$x$至少$n-m$个零元，设$x$可以写成凸组合的形式
$$ x=\alpha y+(1-\alpha)z,x,y,z\in M $$
$$ Ax=b\to \sum_{i=1}^m\bm a_i( y_i- z_i)=0 $$
得出$y_i=z_i=x_i$。说明这个点就是极点（不能写成内点的凸组合的点）
【必要性→】p228
【相邻极点】
←几何，代数→他们的基向量组中只有一个不同
【整数约束⇒线性整数规划】
晶格动力学理论_（德）M.玻恩，黄昆编著_978-7-301-18958-0.pdf
The status of the P versus NP problem.pdf