linear-programming - 使用现有的线性规划工具找到所有替代的基本解决方案

Question

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

这是一个示例(采用 lp_solve 格式):

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

所有 2 个基本解决方案:

x1 = 0.2, x2 = 0.8

x1 = 0.8, x2 = 0.2

当然还有a way寻找替代解决方案，但我真的更喜欢使用现有的库而不是制作我自己的单纯形代码。

我使用 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

首先用glpk解决您的问题，这将为您提供最佳值V的问题。从这点，你可以用 PPL 得到最优值的多面体的描述:

cx = V and Ax <= b

作为其极值点的凸包，对应于您正在寻找的 BFS。

您可以(可能)使用 glpk 单纯形例程。获得最佳 BFS 后，您可以使用例程 glp_get_row_dual 降低与所有非基本列相关的成本。 (变量的基础状态可以通过 glp_get_row_stat 获得)，所以你可以找到一个零成本降低的非基础变量。然后，我认为你可以使用函数 glp_set_row_stat更改此列的基础状态以使其进入基础。
(然后，只要避免循环，就可以迭代此过程。)

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