Practical Guided to Simplex
标准线性优化问题
S1：改写问题成标准型
- 极大化目标问题；
- 引入松弛变量转换不等式为等式；
- 对任意取值的变量引入两个非负变量表示；
S2：写出单纯形表
- 将约束方程组的系数按增广矩阵写出；
- 最后一行写目标函数的系数，增广右侧为0；
- 确定基变量（个数为约束方程组行数m）、非基变量（n-m），从基变量中选择pivot；
- 理论上，一组基变量构成可行域内的一个点（符合约束方程组）；
S3：高斯消元
- 将选为基变量的列通过高斯消元化为一个单位阵；
- 目标函数的系数也跟着变化；
- 通过高斯消元等价于让基变量的值可以通过增广右侧直接读出，而非基变量的值为0；
- 当所有基变量都是非负的（符合变量非负条件），那么得到的基解是可行解；
S4：选择新变量
-
表最后一行目标函数的系数如果存在负数，因为这可以通过选择相应的基变量使目标变小，选择最小的负数所在列为基变量（启发式最速变小），称为入基变量；
-
确定完入基变量，选择出基变量，依据逐行计算增广最右列值与入基变量列的系数比值，选择系数最小的正比值，所在行的基变量即为出基变量（pivot的概念）；
- 如果出基变量列的全部系数为负，则此规划问题无有限解
-
如果确定入基变量和出基变量，则继续返回第3步，进行高斯消元，如此迭代；
-
直到最后一行系数全部非负；
S5：写出最终解
- 所有的非基变量为0，所有基变量对应的解参考增广最右列值；
Tricks
- 如何确定初始的基变量
- 如果松弛或剩余添加构成的矩阵是个满秩单位阵，直接采用；
- 如果没有添加任何变量，则可以手动添加m个变量构成单位阵，且最后一行的系数取为很大的；
- 思考标准型是min或max对单纯性解法的影响；
查看30道真题和解析