python - python中的线性规划？

Question

我需要建立一个线性规划模型。这是我正在使用的不等式（例如）：

6x + 4y <= 24
x + 2y <= 6
-x + y <= 1
y <= 2

我需要找到这些不等式所描述的区域，并在图形中对其进行着色，并跟踪该区域边界线的顶点，并以不同的颜色绘制边界线。有关我正在寻找的示例，请参见下图。

交点的图像 .

我正在使用 Python 3.2、numpy 和 matplotlib。Python中有更好的线性编程模块吗？

score 69 · Accepted Answer

更新：在过去的 4 年里，答案已经有些过时了，这里有一个更新。你有很多选择：

如果您不必使用Python，那么在建模语言中执行此操作会容易得多，请参阅Any good tools to solve integer programs on linux？
这些天我个人通过它的 Python API使用Gurobi 。它是一个商业的、封闭源代码的产品，但对学术研究是免费的。
使用PuLP，您可以创建MPS和LP 文件，然后通过其命令行界面使用 GLPK、COIN CLP/CBC、CPLEX 或 XPRESS 解决它们。这种方法有其优点和缺点。
Google的OR-Tools是一个用于优化的开源软件套件，专为解决世界上最棘手的车辆路线规划、流程、整数和线性规划以及约束规划问题而调整。
Pyomo是一种基于 Python 的开源优化建模语言，具有多种优化功能。
SciPy 提供线性编程：scipy.optimize.linprog。（我从未尝试过这个。）
显然，CVXOPT为 GLPK提供了Python 接口，我不知道。我已经使用GLPK 8 年了，我强烈推荐 GLPK。CVXOPT的例子和教程看起来很不错！
您可以在GLPK/Python下的 Wikibook 中找到其他可能性。请注意，其中许多不一定仅限于 GLPK。

score 20 · Accepted Answer

我推荐使用cvxopt包来解决 Python 中的凸优化问题。此处的 cvxopt 文档中有一个用于线性程序的 Python 代码的简短示例。

score 7 · Accepted Answer

其他答案在提供求解器列表方面做得很好。然而，只有 PuLP 被提到作为一个 Python 库来制定 LP 模型。

另一个不错的选择是Pyomo。像 PuLP 一样，您可以将问题发送给任何求解器，然后将解决方案读回 Python。您还可以操纵求解器参数。我和一位同学在 2015 年比较了 PuLP 和 Pyomo 的性能，我们发现 Pyomo 生成相同问题的 .LP 文件的速度比 PuLP 快几倍。

score 6 · Accepted Answer

唯一一次使用图来解决线性程序是用于家庭作业问题。在所有其他情况下，线性规划问题通过矩阵线性代数解决。

至于 Python，虽然有一些纯 Python 库，但大多数人使用带有 Python 绑定的本机库。有大量用于线性规划的免费和商业库。有关详细列表，请参阅Wikipedia 中的线性规划或 OR/MS Today 中的线性规划软件调查。

免责声明：我目前在 Gurobi Optimization 工作，之前曾在提供 CPLEX 的 ILOG 工作。

score 4 · Accepted Answer

为了解决线性规划问题，您可以使用 SciPy 中的scipy.optimize.linprog模块，该模块使用 Simplex 算法。

score 1 · Accepted Answer

我会推荐使用PuLP python 包。它有一个很好的界面，你可以使用不同类型的算法来解决 LP。

score 0 · Accepted Answer

0

lpsolve 对我来说是最简单的。无需安装单独的求解器。它包含在包装中。

于 2014-11-02T18:04:39.857 回答

7 回答 7