我试图找出“算法简介，第 3 版”一书中的单纯形算法。“Initial-Simplex”程序以标准形式为输入，检查标准形式是否存在初始基本可行解。伪代码如下：
在第 2 行，它检查数组 b 中的最小变量是否大于或等于 0。如果不是，则构造一个 Laux 并执行一个枢轴以消除 b 中的负变量。然后在第 9 行，它显示基本解决方案对于 Laux 是可行的。问题是，如果最初在数组 b 中，有多个负变量怎么办？例如原点 b 是 [-2, -1, 3, 1]，那么在第 1 行，我们有 b[k]=-2，所以 k=0。但是执行完第4行到第9行后，b内还有一个负变量-1。在这种情况下，我们不能说基本的解决方案对 Laux 来说是可行的。总之，没有检查b中的所有变量是否为非负的机制，并且第4行到第9行不在循环内。该算法是否假设最初小于一个负变量在 b 内？
我再次检查了算法，我想我知道原因了。对于下面的例子，由于-4是数组b中的最小变量，经过一个pivot后，它变成了4。即使b本来可能还有其他负变量，它们也不能小于-4，因为-4是最小的. 我们用另一个变量替换x0后，x0对应的bx0值为4，我们有|4| 大于或等于任何其他 |bi| 在 bi < 0 的数组中。因此，在枢轴之后，新的 bi 必须是非负数。对于标准表格
maximize 2x1 - x2
subject to
2x1-x2 <= -2
x1 - 5x2 <= -4
x1, x2 >= 0
松弛形式是
z = -x0
2x1 - x2 - x0 <= -2
x1 - 5x2 - x0 <= -4
x1, x2, x0 >= 0
在一个支点之后，
x0 = 4 + x1 - 5x2 + x4
x3 = -2 - 2x1 -x2 + (4 + x1 - 5x2 + x4)
我们可以看到 -2 + 4 大于 0。b 中不会有任何负变量。