每本关于线性优化的书都将单纯形法解释为一个两阶段算法：第一个用于找到可行的角点作为起点，第二个用于找到最优值。第一个使用对偶问题。例如，看看D. Bertsimas 和 JN Tsitsiklis：“线性优化简介”。

需要两阶段方法的原因是，通常很难找到任何可行点——在高维空间中，可行集与单位框相比非常小。从您的问题来看，您似乎有另一种方法可以找到至少一个可行点，在这种情况下，可能会从该点生成可行多面体的顶点。一个想法是使用以下方法：每个不等式约束代表一个由超平面分隔的半空间。给定一个可行点$x^\ast$， 找出$n+1$最接近的超平面$x^\ast$并采取他们的路口。直觉上，这个顶点应该是可行的，尽管我承认需要更多地考虑这一点。

不幸的是 Wolfgang Bangerth 的解决方案不能保证有效：

你可以这样做：选择一个方向，然后沿着它移动，直到你碰到一个超平面。沿着超平面选择一个方向并沿着它移动，直到碰到另一个方向。沿着两个超平面的交点选择一个方向......之后$i$步骤，您将拥有$i$活动约束，您将沿着$(n-i)$维零空间。后$n$步骤，您将到达一个顶点（假设可行集是有界的）。

单纯形法中的第一阶段实际上有许多不同的方法。特别是，存在使用原始单纯形单纯形迭代的 I 阶段算法和使用对偶单纯形迭代的其他 I 阶段算法。这是一种非常通用的方法，可以很容易地适应使用已知的可行解决方案。这个版本在第一阶段使用对偶单纯形法，在第二阶段使用原始单纯形法，但有一个变体在第一阶段使用原始单纯形迭代，在第二阶段使用对偶单纯形迭代，我将在最后提到。我将在这里描述的方法在许多关于线性规划的教科书中都有讨论。例如，参见Robert Vanderbei 的文本。

假设我们正在解决

$\max cx$

受制于

$Ax=b$

$l \leq x \leq u$

其中大小为乘以。为简单起见，假设的行是线性独立的（这可以通过显示因式分解的秩来实现。）$A$$m$$n$$A$

1. 选择一个初始基础。这是的相应列形成非奇异矩阵。剩余的非基本变量可以设置为它们的上限或下限（如果变量根本没有边界，则为零。） $m$$A$$B$

从您的初始解决方案中执行此操作的一种简单方法是选择那些在已知可行解决方案中离它们的界限最远的变量作为基本变量，然后验证是非奇异的。您可能必须修改基础以使非奇异。这里的重点是有许多可能的基础，但是这个基础变量作为基本变量，这些变量似乎来自您的可行解决方案。 $B$$B$

求解方程以获得基本变量的值。 $Ax=b$

2. 从某些原始变量超出其界限的意义上说，您获得的基本解决方案可能是原始不可行的。从某种意义上说，它也可能是双重不可行的，因为非基本变量的一些降低成本具有错误的符号（例如，下限的非基本变量具有正降低的成本或上限的非基本变量具有负降低的成本。）

我们将通过将目标函数更改为对偶可行的函数来克服这个问题。对于下限的每个非基本变量，从目标函数系数中对于每个位于其上限的非基本变量，将一个大的正数添加到系数中。这确保了字典是双重可行的。 $M$$M$

目标函数的这种修改的重点是努力朝着最初的可行性努力，但也朝着原始目标函数的最优性前进。您希望足够大以具有双重可行性，但您希望尽可能多地保留原始目标函数的影响。 $M$

3. 执行对偶单纯形法以获得一个基本解决方案，该解决方案既是原始可行的（边界内的所有基本变量）又是对偶可行的（所有降低的成本都具有所需的符号）。该解决方案对于第一阶段问题是最优的。

4. 将修改后的第一阶段目标函数替换为原始目标函数。现在您将有一个基本可行的基本解决方案（更改目标函数不会影响这一点）但双重不可行。执行原始单纯形迭代以恢复最优。

这种方法的一个明显替代方案是在第一阶段开始修改右手边 b，在第一阶段使用原始单纯形迭代以获得最优性，然后将原始右手边放回第二阶段并使用对偶单纯形迭代在第二阶段。

我正在寻找类似问题的解决方案：对于一个非常大的稀疏线性程序，只有单纯形法测试工作，但只有在默认的 0 解决方案可行时。似乎第一阶段算法（如 Matlab 的 linprog 中）很糟糕。并且第一阶段的源代码非常复杂，无法用遗传算法等其他算法替代，因此一种变通方法是对原始问题进行线性变换，使得在新变量中提供的初始可行解为 0，而这0 将被第一阶段使用，而不使用它自己的方法来寻找不同的起点。

在测试该方法时，通过 linprog.m、simplex.m、simplexpresolve.m 和 simplexphaseone.m 逐步测试，在仅使用不等式约束的情况下，确认原始变量将使用默认 0，其中松弛变量将产生差异。所以线性变换可以将 x0 偷偷变成单纯形，从而故意阻止用户提供 x0。然后您可以看到“默认起点可行，跳过阶段 1”的消息。另一方面，通常 GA 可以通过使用两倍或三倍的时间找到接近线性规划的解，达到 0.01%，因此可能不值得对这些约束、目标和界限进行线性变换，特别是在人为创建约束时.