杂记

    最近在最优化方法课上讲到单纯型法，尽管陆老师给出了很详细的公式推导，但是自己脑子实在太笨对着大段公式反应不过来。于是惯例花了些时间想了想这堆公式自己的理解。如果有理解错误的地方请读者指出。

    首先抛开单纯型法，如果最暴力的方法去找LP问题的最优解应该如何做呢？由于每个基本可行解对应着一个极点，而LP问题被证明最优解一定在极点处取到。同时每个基本可行解一定对应有一个基矩阵，那么直接枚举基矩阵就得到一个指数级的算法。实际上单纯型法最坏的复杂度确实是指数的。

    下面说下单纯型法中几个概念自己的直观理解：

    1.本质上单纯型法就是对上述暴力算法的优化算法，通过选择最大检验数迅速收敛到最优解。

    2.检验数的理解：检验数就是表示 非基变量 在变化时引起的函数值的变化程度。从检验数的形式化表示来看$z_j - c_j = c_BB^{-1}P_j - c_j$, 很容易发现$c_BB^{-1}P_j$中的$B^{-1}P_j$就是变量$x_j$系数在基$B$下的坐标。那么当$x_j$变化时，反应在基$B$下的变化会通过$c_B$影响到函数值，因为第一项为$c_BB^{-1}P_j$，同时由于本身的$c_j$还会对函数结果造成影响，并且两者在推导中符号相反，因此得到检验数的表达为：$c_B$乘该变量系数在当前基下的坐标减去原本的$c_j$

    3.进基出基的理解：由于某个非基变量$x_j$在每变化1时，$x_B$减少的一个单位的其在基$B$下的系数，而函数结果减少一个单位的检验数。因此非基变量增加值为$min\{\frac{\bar{b_i}}{y_{ik}}|y_{ik}>0\}$

    4.为什么在单纯型表里刚好就是高斯消元的结果：其实一句话就能说清楚了，单纯型本质就是一个换基的过程，原基$B$换到新基$B'$时，相当于对系数矩阵施加$B'^{-1}$, 所以结果就是高斯消元的结果。同理最后一行检验数和函数值本质也是一个换基的结果，但是好像没有系数矩阵那么直观了。