5

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

这是一个示例(采用 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

当然,有一种方法可以找到替代解决方案,但我真的更喜欢使用现有的库而不是制作我自己的单工代码。

我使用 Python 作为我的编程语言,并希望lp_solveGLPK的 C API 中有一些方法可以做到这一点。

谢谢。

4

1 回答 1

3

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

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

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

但是,(幸运的是!)不需要编写自己的单工代码:您可以使用 glpk 库访问当前基础的内部结构,也可能使用 lpsolve。

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

  1. 更好的方法是为此使用另一个库,例如PPL。假设您有以下形式的问题:

    min cx; subject to: Ax <= b
    

    首先用 glpk 解决您的问题,这将为您提供V问题的最佳值。至此,您可以使用 PPL 来获得最优值的多面体的描述:

    cx = V and Ax <= b
    

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

  2. 您可以(可能)使用 glpk simplex 例程。一旦获得最佳 BFS,您就可以使用例程获得与所有非基本列相关的降低成本glp_get_row_dual(变量的基本状态可以通过 获得glp_get_row_stat),因此您可以找到成本为零的非基本变量. 然后,我认为您可以使用函数glp_set_row_stat来更改此列的基础状态,使其进入基础。(然后,只要避免循环,您就可以重复此过程。)

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

于 2015-02-17T15:18:41.900 回答