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

di

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

这是一个示例(采用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中有某种方法可以做到这一点。

谢谢。

尼古拉斯·格里比(Nicolas grebille)

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

什么是确实容易找到一个其他的基本解决方案,一旦你与单纯形法,这并不意味着它很容易全部列出来达到最优。

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

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

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

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

    min cx; subject to: Ax <= b
    

    首先使用glpk解决您的问题,这将为您提供问题的最佳价值V从这一点出发,您可以使用PPL获得最佳值的多面体的描述:

    cx = V and Ax <= b
    

    作为其极限点的凸包,对应于您要寻找的BFS。

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

注意,我自己没有尝试任何一种解决方案。我认为第一个到目前为止是最好的,尽管这需要您学习PPL API。如果您想进行第二篇文章,我强烈建议您向glpk维护者发送一封电子邮件(或查看源代码),因为我真的不确定它是否能照常工作。

本文收集自互联网,转载请注明来源。

如有侵权,请联系[email protected] 删除。

编辑于
0

我来说两句

0条评论
登录后参与评论

相关文章

来自分类Dev

如何获得拓扑排序的所有解决方案

来自分类Dev

将现有的edmx文件,实体类,上下文添加到新解决方案中

来自分类Dev

角路由的基本解决方案

来自分类Dev

现有的TCP中继解决方案

来自分类Dev

通过加载代码将列表项添加到组合框的基本解决方案

来自分类Dev

使用文件将现有项目添加到解决方案

来自分类Dev

是否有工具/解决方案来编程仅在每个X迭代中检查一次条件的循环?

来自分类Dev

如何使用VisualSVN Server将现有的Visual Studio解决方案置于源代码控制之下?

来自分类Dev

将捆绑软件添加到现有的ASP.NET Webforms解决方案中

来自分类Dev

有没有现有的解决方案来制作可移植的有序位字段?

来自分类Dev

试图在python中使用Z3查找布尔公式的所有解决方案

来自分类Dev

从现有的2-SAT生成解决方案

来自分类Dev

如何使一个递归解决方案返回所有可能的解决方案?

来自分类Dev

使用minisat查找SAT的所有解决方案

来自分类Dev

Chrome进程占用了我所有的带宽,尝试了所有可能的解决方案

来自分类Dev

如何使用C#在Visual Studio 2010中以编程方式将现有项目添加到当前解决方案中

来自分类Dev

Visual Studio-如何根据现有的解决方案/项目(包括Web服务和使用这些Web服务的Web)创建解决方案?

来自分类Dev

使用VB.NET,如何将现有解决方案中的现有项目引入新解决方案中,从而使其完全驻留在新解决方案中?

来自分类Dev

角路由的基本解决方案

来自分类Dev

用R软件进行线性编程的解决方案

来自分类Dev

通过加载代码将列表项添加到组合框的基本解决方案

来自分类Dev

使用文件将现有项目添加到解决方案

来自分类Dev

是否有工具/解决方案来编程仅在每个X迭代中检查一次条件的循环?

来自分类Dev

Xcode 7无法找到.dylib没有现有的解决方案对我有用

来自分类Dev

Xcode 7无法找到.dylib没有现有的解决方案对我有用

来自分类Dev

遍历数组以查找匹配项并返回所有可能的解决方案

来自分类Dev

C#VisualStudio 2015如何从现有解决方案到新解决方案中使用代码

来自分类Dev

如何使用JOptimizer仅获得一个可行的解决方案,以解决具有多个或无限数量的解决方案的线性规划问题?

来自分类Dev

在 R 中使用 lpSolveAPI 的所有可行解决方案

Related 相关文章

  1. 1

    如何获得拓扑排序的所有解决方案

  2. 2

    将现有的edmx文件,实体类,上下文添加到新解决方案中

  3. 3

    角路由的基本解决方案

  4. 4

    现有的TCP中继解决方案

  5. 5

    通过加载代码将列表项添加到组合框的基本解决方案

  6. 6

    使用文件将现有项目添加到解决方案

  7. 7

    是否有工具/解决方案来编程仅在每个X迭代中检查一次条件的循环?

  8. 8

    如何使用VisualSVN Server将现有的Visual Studio解决方案置于源代码控制之下?

  9. 9

    将捆绑软件添加到现有的ASP.NET Webforms解决方案中

  10. 10

    有没有现有的解决方案来制作可移植的有序位字段?

  11. 11

    试图在python中使用Z3查找布尔公式的所有解决方案

  12. 12

    从现有的2-SAT生成解决方案

  13. 13

    如何使一个递归解决方案返回所有可能的解决方案?

  14. 14

    使用minisat查找SAT的所有解决方案

  15. 15

    Chrome进程占用了我所有的带宽,尝试了所有可能的解决方案

  16. 16

    如何使用C#在Visual Studio 2010中以编程方式将现有项目添加到当前解决方案中

  17. 17

    Visual Studio-如何根据现有的解决方案/项目(包括Web服务和使用这些Web服务的Web)创建解决方案?

  18. 18

    使用VB.NET,如何将现有解决方案中的现有项目引入新解决方案中,从而使其完全驻留在新解决方案中?

  19. 19

    角路由的基本解决方案

  20. 20

    用R软件进行线性编程的解决方案

  21. 21

    通过加载代码将列表项添加到组合框的基本解决方案

  22. 22

    使用文件将现有项目添加到解决方案

  23. 23

    是否有工具/解决方案来编程仅在每个X迭代中检查一次条件的循环?

  24. 24

    Xcode 7无法找到.dylib没有现有的解决方案对我有用

  25. 25

    Xcode 7无法找到.dylib没有现有的解决方案对我有用

  26. 26

    遍历数组以查找匹配项并返回所有可能的解决方案

  27. 27

    C#VisualStudio 2015如何从现有解决方案到新解决方案中使用代码

  28. 28

    如何使用JOptimizer仅获得一个可行的解决方案,以解决具有多个或无限数量的解决方案的线性规划问题?

  29. 29

    在 R 中使用 lpSolveAPI 的所有可行解决方案

热门标签

归档