〖探索python〗使用 Pyomo 解决复杂的问题（九）

5789

收藏 2015-04-07

来自IBM DEVELOPERWORKS

探索在 Python 中使用 Python Optimization Modeling Objects（Pyomo，一个开源工具）建模优化应用程序的方法。您可以使用 Pyomo 定义象征性的问题，创建具体的问题实例，并使用标准解算器解决这些实例。本系列文章将展示如何利用 Pyomo 的能力集成 Python 来建模优化应用程序。本系列的第一篇文章将介绍基础知识。第 2 部分将介绍如何添加更多工具和构建一种可伸缩的架构。第 3 部分将提供一些使用 IPython 和 pandas 进行投资分析和统计分析的实用示例。

简介

建模是一种解决复杂问题的强大方法。依据图书 Modeling Languages in Mathematical Optimization（参阅参考资料）的叙述，模型用于：

解释现象
进行预测
评估关键因素
识别极限
分析折衷方法

在业界，Microsoft® Excel 等电子表格软件常常是建模问题的首要选择。现在，电子表格通常非常直观，但它们在解决大型问题上存在着局限性。如果您是开发人员，那么您可能会发现编写脚本来解决建模问题会更有效，因为您可以轻松地将脚本集成到其他系统中。本文将介绍使用 Pyomo 库在 Python 应用中实现线性优化的基础知识。

入门

首先要安装 Pyomo。Pyomo 是 Coopr 的一个中心组件，而 Coopr 是 Python 软件包的集合。您可以下载 coopr_install 脚本，在使用 Python 解释器运行它时，它会创建一个 Python 虚拟环境。

创建一个名为 “coopr” 的相对目录：

复制代码

使用下面的命令启动 Pyomo，这会将该相对目录和它的可执行文件放在您的路径中：

复制代码

使用 Pyomo "--help 命令获取使用 pyomo 的帮助：

复制代码

您需要一个编译器来使用虚拟 Python 环境构建器 (virtualenv) 和 Pyomo。在 OS X 上，使用 XCode Developer Tools 命令行工具。在 Linux 上，使用 GNU Compiler Collection (GCC)。初始化这个虚拟环境后，可通过以下两种方式之一使用 Pyomo 解决问题：

使用 Pyomo 命令行工具：
复制代码
或者，将初始化代码嵌入您的脚本中，通过 Python 解释器运行它：清单 1. 在一个脚本中调用 Pyomo
复制代码

Pyomo 假设您至少安装了一个解算器 (solver)。GNU Linear Programming Kit (glpk) 是默认的解算器。请参阅您希望使用的解算器的安装说明。然后确保 Pyomo 能够在它的路径上找到此解算器。

建模策略

可通过两种方式使用 Pyomo 创建数据模型：抽象方式和具体方式。二者的关键区别在于是否将模型与数据分开。

在抽象模型中，模型与数据是分开的。
在具体模型中，是在模型本身中定义数据的。例如，在使用具体模型的 Pyomo 脚本中，所有内容都是在单个脚本文件中定义的。对于更简单的问题，尤其是教学问题，这可能是一种很高效的方法。但在另一方面，更大的问题通常是拥有更大的数据集，这使得将数据和处理该数据所需的代码嵌入同一个脚本中变得不切实际。

从总体上讲，Pyomo 模型由变量（variables）、目标（objectives）和约束（constraints）组成。

变量是在优化期间计算的值。
目标是获取数据和变量的 Python 函数，它要么是最大值，要么是最小值。
约束是定义表达式来限制变量可使用的值的一种方式。

在创建 Pyomo 模型时，需要了解表示代数表达式的 Python 方法。下面的摘要简单对比了电子表格、代数和 Python 中的表达式：

图 1. 符号对比表

Pyomo 应用程序示例：Wyndor

为了演示使用 Pyomo 时的一个简单的线性优化问题，我们以图书 Introduction to Management Science 中的一个产品组合问题为例（参阅参考资料）。Wyndor 工厂负责生产门窗，它的三个厂房有不同的营业时间，可以生产门或窗。要确定如何最大程度地提高有限生产时间内的可用利润，可以编写以下脚本。该脚本包含三个主要部分：模型、目标和约束。

模型（一个具体模型）实例化问题的数据，比如厂房的营业时间。
目标（可以是最大值或最小值）是最大的利润。
约束使用了一个 CapacityRule 函数，该函数使用一种称为列表推导式 的 Python 语言来编写。

以下是 Wyndor 优化问题的脚本：

清单 2. Wyndor Pyomo 基本示例

复制代码

让我们运行以下脚本：

复制代码

Pyomo 返回以下输出，该输出显示了一个可行的解决方案（可实现 3,600 美元的利润）：

清单 3. 一个可实现 3,600 美元的利润的可行解决方案

复制代码

我们看看您应生产的产品的比率。为此，对输出文件 results.json 运行 cat。结果如下：

复制代码

在输出中，可以看到生产 6 个窗子和 2 个门会得到 3,600 美元的最大利润。

解决该脚本的另一种方法是使用 Python，这得益于所添加的条件语句。这会在脚本内调用 Pyomo，而不是使用 Pyomo 调用脚本。

启发式优化：贪婪的随机流动推销员

Bill Cook 编写的图书 In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation 中包含一个优秀的问题示例，该问题并不总是像线性程序一样得到良好扩展。这个问题就是流动推销员问题或 TSP：在给定一个城市列表的情况下，找出仅访问每个城市一次并且最后回到最初的城市的最短路线。随着城市数量的增多，在最坏情况下，解决流动推销员问题的时间会呈指数级增长。

图 2 中的图表模拟了解决每种可能的路线所需的时间，假设只需几秒即可解决几个城市的问题。如您所见，在您的有生之年解决这个问题很快就会变得行不通。

图 2. 流动推销员问题的解决时间呈指数级增长