使用现有的线性编程工具查找所有替代基本解决方案

Question

我必须找到一些微小的线性编程问题的所有基本解决方案。

这是一个示例（采用lp_solve格式）：

max: x1 + x2;
x1 + x2 <= 1;
x1 <= 0.8;
x2 <= 0.8;

所有2种基本解决方案：

当然，有一种寻找替代解决方案的方法，但是我真的更喜欢使用现有的库，而不是精心设计自己的单纯形代码。

我使用Python作为编程语言，希望lp_solve或GLPK的C API中有某种方法可以做到这一点。

谢谢。

Answer 1

没有常规方法可以做到这一点glpk；恕我直言，任何现实世界的求解器都不太可能实现类似的东西，因为它在实践中不是很有用，而且它肯定不是一个简单的问题。

一旦使用单纯形算法达到最优，确实很容易找到另一种基本解决方案，但这并不意味着很容易将它们全部列出。

考虑一个 LP，其域具有维度n；S最优解集是一个凸多面体，其尺寸m可以是从0到的任何值n-1。您需要一种方法来列出问题的所有基本解决方案，即的所有顶点S：一旦m大于 2，当您从一个基本解决方案移动到另一个基本解决方案时，您将需要小心避免循环。

然而，（幸运的是！）不需要编写自己的单纯形代码：您可以使用 glpk 库（也可能使用 lpsolve）访问当前基础的内部结构。

编辑：两种可能的解决方案

更好的方法是使用另一个库，例如PPL。假设您遇到以下形式的问题：
```
min cx; subject to: Ax <= b
```
Run Code Online (Sandbox Code Playgroud)
首先用 glpk 解决你的问题，这会给你V问题的最优值。从这一点上，您可以使用 PPL 来获得最优值多面体的描述：
```
cx = V and Ax <= b
```
Run Code Online (Sandbox Code Playgroud)
作为其极值点的凸包，对应于您正在寻找的 BFS。
您（可能）可以使用 glpk 单纯形例程。一旦获得最佳 BFS，您就可以使用例程获得与所有非基本列相关的减少成本glp_get_row_dual（可以使用获得变量的基本状态glp_get_row_stat），因此您可以找到具有空减少成本的非基本变量。那么，我认为可以使用函数glp_set_row_stat来改变该列的基础状态，使其进入基础。（然后，只要避免循环，您就可以重复此过程。）

请注意，我自己没有尝试过任何这些解决方案；我认为第一个是迄今为止最好的，尽管它需要您学习 PPL API。如果您想选择第二个，我强烈建议您向 glpk 维护者发送一封电子邮件（或查看源代码），因为我真的不确定它是否会按原样工作。