运筹学中的线性规划问题

在线性规划中，因为约束都是线性函数，所以可行域是凸集。参考二维问题的图解法，它的可行域是几条线围成的区域，所以一定是凸集。然后，在这个凸集中搜索最优解。如果通过目标函数等值线的移动来搜索解，那么最优解必然在其凸集的边上达到最优值，而凸集的边要么是线段，要么是顶点，所以线性规划问题的最优解必然在可行域的顶点上。

实际上，这些顶点就是线性规划问题的基本可行解。

那么如何从模型中得到这些顶点(基本可行解)？

求解模型的关键是求解ax = b。

因为一个矩阵是m×n矩阵，所以不能得到上述约束方程的唯一解。m×m的非奇异子矩阵b必须在A矩阵中找到，即满足| b |不等于零(行列式不为零)，才能得到bx = b的唯一解。此时矩阵B对应的决策变量称为基变量，其余为非基变量。在X中，如果基变量取BX = B的值，非基变量取零的值，那么X就是问题的基(可行)解，即可行域顶点对应的解。

这是根据我的理解写的，希望有帮助。