使用现有线性规划工具找到所有备选基本解

Question

5

我需要找到一些微小线性规划问题的基本解。

以下是一个例子（以lp_solve格式）：

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

所有的2个基本解：

当然，有一种方法可以找到替代解，但我更喜欢使用现有的库而不是自己编写单纯形代码。

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

谢谢。

- tdihp

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Nicolas Grebille · Accepted Answer

没有现成的方法可以使用 glpk 来实现这个功能；我认为在实际情况中，任何真正的求解器都不可能实现这样的功能，因为它在实践中并不十分有用，而且这绝对不是一个简单的问题。

当你使用单纯形算法达到最优解后，确实很容易找到另一个基本解，但这并不意味着很容易列出所有基本解。

考虑一个LP问题，其定义域的维度为n；最优解集合S是一个凸多面体，其维度m可以是从0到n-1的任何值。你想要一种方法来列出问题的所有基本解，也就是S的所有顶点：当m大于2时，你需要仔细避免在从一个基本解移动到另一个基本解时出现循环。

然而，幸运的是！你不需要编写自己的单纯形代码：你可以通过glpk库以及可能的lpsolve来访问当前基础的内部结构。 编辑：两种可能的解决方案

The better way would be to use another library such as PPL for this. Assume that you have a problem of the form:
```
min cx; subject to: Ax <= b
```
First solve your problem with glpk, this will give you the optimal value V of the problem. From this point, you can use PPL to get the description of the polyedron of optimal values:
```
cx = V and Ax <= b
```
as the convex hull of its extreme points, which correspond to the BFSs you are looking for.
You can (probably) use the glpk simplex routines. Once you get an optimal BFS, you can get the reduced cost associated with all non-basic columns using the routine glp_get_row_dual (the basis status of the variable can be obtained with glp_get_row_stat), so you can find a non-basic variables with a null reduced cost. Then, I think that you can use function glp_set_row_stat to change the basis status of this column in order to have it enter the basis. (And then, you can iterate this process as long as you avoid cycling.)

请注意，我自己没有尝试过这些解决方案；我认为第一个是最好的，虽然它需要你学习PPL API。如果你想选择第二个，我强烈建议你发送电子邮件给glpk维护者（或查看源代码），因为我真的不确定它是否可以直接使用。