我试图通过遵循此 text 来理解具有 n 变量和 m 技术约束的问题的单纯形迭代.我非常理解迭代的几何解释 - 在相邻顶点之间移动。
但是，我无法理解代数直觉。现在我们在相邻的基本可行解 = bfs 之间旋转 到AX + IS = b 的标准形式, X,S >= 0 :
- 为什么 bfs 必须有
n变量等于 0？ - 为什么其余的变量应该形成一个
基础？基不是一组跨越子空间的线性独立向量吗？我们在这里跨越什么，我们只是在寻找一个顶点，不是吗？
谢谢!
最佳答案
BFS 应该正确地将
n-m非基本变量设置为0。一些m基本变量本身可能是0，但这是退化的解决方案。基础确实是跨越向量
b的最小线性独立变量集。请注意，b是一个m-vector。因此，m个变量对应的向量可以组成一个BFS。变量总数为n。因此碱基数是指数级的n选择m。
从一个顶点旋转或移动到另一个顶点只不过是将一个非基本变量(关联的列向量)替换为基础并从基础中删除一个预先存在的变量。因此，基础将始终具有 m(列)向量。
在任何一个时间点，将 A 划分为基本变量和非基本变量，例如 A = [B|N]，则 Bx = b 和因此，x 变量是 B 范围内的系数，它给出了 b。
有界线性约束线性规划的可行多面体的每个顶点对应于基本解，反之亦然，这是线性规划的一个基本结果。引用:https://press.princeton.edu/titles/413.html
关于algorithm - 单纯形 - 规范形式基础背后的代数直觉，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/53246360/