单纯形算法 - 基本解决方案的重要性？

Question

单纯形算法中基本解的重要性？

Answer 1

如果所有变量（结构和逻辑）都是非负的（即 x>=0 和 slacks s>=0），那么所有非基本变量都等于零。由于它们固定为零，我们只需求解 m 个基本变量。

本质上我们必须解决

A x = b

不幸的是，这是一个非正方形方程组（添加松弛部分后，我们的列数总是多于行数）。在 LP 中，我们可以形成一个基本解决方案并将其划分为

B x_B + N x_N = b

设置 x_N = 0 后，我们只有一个线性方程组的解：

x_B = inv(B) b

有一个基本定理说我们可以将搜索限制为仅基本解决方案，即可以划分为基本和非基本变量的解决方案

x = [ x_B ]
    [ x_N ]

与 x_B >= 0 和 x_N = 0。

要了解更多信息，请打开一本关于线性规划的书；一个很好的是Vanderbei。