线性规划问题的基可行解求解

Question

如题所述

Answer 1

域为凸集。参考二维问题的图解法，其可行域是由几个线条围起来的区域，所以肯定是凸集。那么，求解最优解就在这个凸集里搜索。由目标函数等值线的移动来搜索解，则最优解肯定在其凸集的边缘达到最优值，而该凸集的边缘要么是线段要么是顶点，因此线性规划问题的最优解肯定是在可行域的顶点上。
🔍求解AX=b
求解模型的关键在于求解AX=b。
🔍求解非奇异子矩阵B
必须在A矩阵中找出m×m的非奇异子矩阵B，即满足｜B｜不等于零（行列式不为零），从而可求得BX＝b的唯一解。
🔍基变量和非基变量
对应于矩阵B的决策变量称为基变量，其余为非基变量。X中基变量取值为BX＝b的解，非基变量取值为零，则该X即为问题的基（可行）解，即对应于可行域的顶点的解。