我必须找到一些微小线性规划问题的所有基本解决方案。
这是一个示例(采用 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 http://mat.gsia.cmu.edu/classes/QUANT/NOTES/chap7/node5.html寻找替代解决方案,但我真的更喜欢使用现有的库,而不是编写自己的简单代码。
我使用Python作为我的编程语言,希望有一些方法lp_solve http://lpsolve.sourceforge.net/5.5/ or GLPK https://www.gnu.org/software/glpk/的C API 可以做到这一点。
Thanks.
没有常规方法可以做到这一点glpk
;恕我直言,任何现实世界的求解器都不太可能实现类似的东西,因为它在实践中不是很有用,而且它肯定不是一个简单的问题。
确实很容易找到什么one一旦使用单纯形算法达到最优,这并不意味着很容易将它们全部列出。
考虑一个 LP,其域具有维度n
;集合S
最优解是一个凸多面体,其维度m
可以是任何来自0
to n-1
。
你想要一个方法来列出问题的所有基本解决方案,即所有顶点S
: 立刻m
大于 2,当您从一种基本解决方案转向另一种基本解决方案时,您需要小心避免循环。
然而,(幸运的是!)不需要编写自己的单纯形代码:您可以使用 glpk 库(也可能使用 lpsolve)访问当前基础的内部结构。
编辑:两种可能的解决方案
-
更好的方法是使用另一个库,例如PPL http://bugseng.com/products/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
),这样你就可以找到一个非基本变量,其成本降低为空。然后,I think你可以使用函数glp_set_row_stat
更改该列的基础状态,使其进入基础。
(然后,只要避免循环,您就可以重复此过程。)
请注意,我自己没有尝试过任何这些解决方案;我认为第一个是迄今为止最好的,尽管它需要您学习 PPL API。如果您想选择第二个,我强烈建议您向 glpk 维护者发送一封电子邮件(或查看源代码),因为我真的不确定它是否会按原样工作。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)