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

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

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