Practical Guided to Simplex

标准线性优化问题

$max{c}^{T}xmax\backslash \; c^Tx$

$s\mathrm{.}t\mathrm{.}Ax=b,A\in R^{m\ast n},n\ge ms.t.\backslash \; Ax=b,\backslash \; A\backslash in\; R^\{m*n\},n\backslash geq\; m$

$x\ge 0x\backslash geq\; 0$

S1：改写问题成标准型

1. 极大化目标问题；
2. 引入松弛变量转换不等式为等式；
3. 对任意取值的变量引入两个非负变量表示；

S2：写出单纯形表

1. 将约束方程组的系数按增广矩阵写出；
2. 最后一行写目标函数的系数，增广右侧为0；
3. 确定基变量（个数为约束方程组行数m）、非基变量（n-m），从基变量中选择pivot；
4. 理论上，一组基变量构成可行域内的一个点（符合约束方程组）；

S3：高斯消元

1. 将选为基变量的列通过高斯消元化为一个单位阵；
2. 目标函数的系数也跟着变化；
3. 通过高斯消元等价于让基变量的值可以通过增广右侧直接读出，而非基变量的值为0；
4. 当所有基变量都是非负的（符合变量非负条件），那么得到的基解是可行解；

S4：选择新变量

1. 表最后一行目标函数的系数如果存在负数，因为这可以通过选择相应的基变量使目标变小，选择最小的负数所在列为基变量（启发式最速变小），称为入基变量；

2. 确定完入基变量，选择出基变量，依据逐行计算增广最右列值与入基变量列的系数比值，选择系数最小的正比值，所在行的基变量即为出基变量（pivot的概念）；

   • 如果出基变量列的全部系数为负，则此规划问题无有限解

3. 如果确定入基变量和出基变量，则继续返回第3步，进行高斯消元，如此迭代；

4. 直到最后一行系数全部非负；

S5：写出最终解

1. 所有的非基变量为0，所有基变量对应的解参考增广最右列值；

Tricks

1. 如何确定初始的基变量
   • 如果松弛或剩余添加构成的矩阵是个满秩单位阵，直接采用；
   • 如果没有添加任何变量，则可以手动添加m个变量构成单位阵，且最后一行的系数取为很大的$\omega \backslash omega$；
2. 思考标准型是min或max对单纯性解法的影响；

Reference-Link