<aside> 🧸 本文简单说明了如何用轮椅找到最有路径跑路。
</aside>
矩阵行初等变换：初等矩阵
标准型 行满秩矩阵$A\in\R^{m\times n}_m$，列数小于行数，有无穷解
$$ Ax=b,rank (A)=m\\\left(I_B\ D\right)x=b \\\to \bm x=\begin{pmatrix}\bm x_B\\\bm x_D\end{pmatrix}=\begin{pmatrix}\bm b\\0\end{pmatrix} $$
初等变换得到行简化阶梯型矩阵$B^{-1}Ax=B^{-1}b$，不妨取为$\left(I_B\ D\ b\right)$，前b列为一个极大无关组$I_B$，对应一个b.f.s. 基本可行解$x$
<aside> 📢
对线形方程组做行初等变换，即可从一个基本可行解得到新的基本可行解。
</aside>
【初始基本可行解】
可行解：单位矩阵（行阶梯型）(自然基)，$b\ge 0$（自然基⇒$x\ge 0$基本可行解）.
【转轴元素，换基运算】选转轴元素$a_{kl}$变为1，同列元素变为0。
取第$l$列的转轴元素，只需$k$行化为1，再将$i$行减到零，得
$$ b_k^\prime=\frac{b_k}{a_{kl}},\\b_{i}^\prime=b_i-\frac{b_k}{a_{kl}}a_{il} $$
要求基本解仍是非负，$\bm b$>0：$b_k^\prime$要求$a_{kl}>0$,$b_i^\prime$要求$\frac{b_k}{a_{kl}}$在同列中最小，进而：
$$ \boxed{a_{kl}=\min_{k}\frac{b_k}{a_{kl}}, a_{kl}>0.} $$
要求同样的b除以a越小越好。
<aside> 📢
从LP标准型出发
$$ \min c^Tx\\ s.t.Ax=b,x\ge0\\A\in\mathbb R^{m\times n}_m，b\ge0 $$
</aside>
【判别数】
$$ \boxed{r_D=c_D^T-c_B^TB^{-1}D\ge 0} $$
$c_D$ 自由未知量所对应的目标函数系数
$c_B$余下的目标函数系数
判别数非负，则找到的$z_0$是最优值，单纯形法结束；
判别数有负分量，换基运算让目标函数下降。单纯形法继续迭代。
【单纯形表中的判别数】单位矩阵下为零时（基向量组总可以转化为单位矩阵，进而形成行阶梯型），非基向量所在列的最后一行才对应判别数。
<aside> 📢
单纯性法的矩阵表示。 选取转轴元素、换基运算、计算判别数都体现在单纯形表中。
</aside>
【单纯形表】
$$ \begin{pmatrix}A&b\\c^T&0\end{pmatrix}\overset{分块}\to \begin{pmatrix}B&D_{对应非基变量所在列}&b\\c_B^T&c_D^T&0\end{pmatrix}\overset{\begin{pmatrix}I_B&0\\-c_B^T&1\end{pmatrix}\begin{pmatrix}B^{-1}&0\\0&1\end{pmatrix}}\to \begin{pmatrix}I&B^{-1}D_{获得非基变量所在列}&B^{-1}b_{最优点}\\0&\underline{c_D^T-c_B^TB^{-1}D}{r_D^T{判别数}}&-\underline{c_B^TB^{-1}b}{最优值}\end{pmatrix} $$
第一步迭代需要一个初始基本可行解。
<aside> 📢
修正方法 找到初始基本可行解，或者不用找初始基本可行解(进而跳出标准型限制)。
</aside>
【两阶段法】用线形规划找极大无关组(自然基)
$$ \min y_1+y_2+\cdots+y_m=\bm e^T\bm y\\ s.t. \ \begin{pmatrix}A&I_m\end{pmatrix}\begin{pmatrix}x\\y \end{pmatrix}=b,x,y\ge0 $$
称P1问题。和原始问题P0的约束集在$y=0$时相同。
$$ \begin{pmatrix}A&I&b\\ 0&e^T&0\end{pmatrix}\to \begin{pmatrix}A(\bm x)^\prime&D(\bm y)^\prime&b^\prime\\ r^\prime \ge0&s^\prime \ge0&-f^*=-\bm c^T_BB^{-1}\bm b\end{pmatrix} $$
P1问题能直接找到初始基本可行解。
单纯形法迭代到最小值$e^Ty^=c_B^TB^{-1}b=0$时，极值点$\bm x^$可作为P0问题的初始基本可行解。
$f^*=c_B^TB^{-1}b<0$ P1问题无解。
$f^*=c_B^TB^{-1}b>0$ P0问题无解$M_{P0}=\empty$。
$f^*=c_B^TB^{-1}b=0$, 两阶段法成功，$A$被线形变换到出现“明显的”自然基。
寻找P1问题迭代出的单纯性表中的极大无关组
极大无关组都在$A(\bm x)^\prime$中 ，P0问题的初始化单纯性表可写为
$$ \begin{pmatrix}A(\bm x)^\prime&b^\prime\\ c^T&0\end{pmatrix} $$
直接将P1判别数换为P0问题目标函数的系数$c^T$
$D(\bm y)^\prime$中仍有基变量
若同$i$行的$x$所在列元素$a_{ij},j=1,\cdots,n$都为零，删除单纯形表第$i$行，极大无关组就都在$A(x)^{\prime\prime}$中了；
否则继续P1问题的单纯形法，以$a_{ij}\ne 0$做转轴元素，将基换到$x$所在列。
【大M方法】
$$ \min \bm c^T\bm x+M\bm e^T\bm y\\s.t.\ \begin{pmatrix}A&I_m\end{pmatrix}\begin{pmatrix}\bm x\\\bm y\end{pmatrix}=\bm b,\bm x,\bm y\ge 0 $$
$M>0$是任意大的数
【对偶单纯形法】
动机：初始单纯形表要求苛刻$\bm b\ge 0,\exist I$，
判别数已经非负$\sigma_l\ge 0$，存在$b_k<0$，只需要选择一个$a_{kl}<0$做转轴元素，满足与单纯形法相反的条件$\frac{\sigma_l}{a_{kl}}=\max j\{\frac{\sigma_j}{a{kj}}\mid a_{kj}<0\}$,依此迭代调整至最终单纯形表
$$ b_k^\prime =\frac{b_k}{a_{kl}},\sigma_j^\prime=\sigma_j-\frac{a_{kj}}{a_{kl}}\sigma_l,j=m+1,\cdots,n $$