GNU 线性编程工具包(线性优化简介)

GNU Linear Programming Kit 对于解决具有多种约束的数学问题来说是一个功能非常强大的工具。本文简要介绍了怎么样使用 GLPK（glpsol 客户机工具）和 GNU MathProg 语言来解决 Giapetto 的 Woodcarving 公司（一家玩具制造商）的作业优化问题。

简介

“线性编程是一个用来解决优化问题的工具。在 1947 年，George Dantzig 开发了一种效率方法 —— simplex 算法 —— 来解决线性编程的问题。由于 simplex 算法的出现，线性编程已经在工业界、银行界、教育界、林业、石油行业以及运输业界中广泛地用来解决优化问题。在对财富 500 强公司的调查中，85% 的被调查者都说他们已经使用了线性编程。”

引自 Operations Research: Applications and Algorithms, 4th Edition，Wayne L. Winston 著（Thomson，2004）；请参看下面 参考资料 中的链接。

有很多工具都可以用来解决线性编程的问题。尽管有些专用工具都非常出名，但是开放源码社区中的很多人可能并不了解免费的 GLPK 工具。

本系列文章一共 3 篇，将逐渐介绍 GLPK 的功能和用法；本文是其中的第 1 篇，在本文中，我们将对 GLPK 简要进行介绍，然后展示并应用 GLPK 中的 GNU MathProg Language。

如果我们仅仅从运筹学理论入手，希望学习进行建模和解决线性编程的问题，那么本文就是一个很好的指南。

GNU Linear Programming Kit

GNU Linear Programming Kit（GLPK）是一个使用了众所周知的运筹学算法来解决线性问题的程序库。这些程序实现了simplex 算法、branch and bound 算法、primal-dual interior point 算法以及很多其他算法。请查看 GLPK 下载包中所包含的 GLPK 手册以便了解更多的内容。（要下载 GLPK，请参看 参考资料 一节中给出的 gnu.org 上面 GLPK 页面的链接。）

GLPK 不是一个程序 —— 它无法运行，也没有 main() 函数。实际上，客户机需要将问题数据通过 GLPK API 提供给算法程序，并接收结果。GLPK 有一个默认的客户机，即 glpsol 程序，它可以与这个 API 进行交互。通常诸如 glpsol 之类的程序都被称为 solver，而不是客户机，因此从现在开始我们就会看到这个术语。

GNU MathProg 建模语言

GNU MathProg 建模语言非常简单，但却可以很好地声明线性问题。通常，问题的声明包括：

• 问题决策变量。
• 目标函数。注意目标（objective） 是一个名词，而不是一个形容词。这个名字是运筹学理论中的标准术语。
• 问题约束。
• 问题参数（数据）。

让我们从一个简单的两变量的例子入手：Giapetto 的 Woodcarving 公司。

Giapetto 的 Woodcarving 公司

这个问题引自于 Operations Research：

Giapetto 的 Woodcarving 公司生产两种木头制作的玩具：士兵和火车。一个士兵的销售价格为 27 美元，需要耗费价值 10 美元的原料。制造每个士兵需要耗费 Giapetto 的可变人力成本和间接成本一共 14 美元。一辆火车的销售价格为 21 美元，需要耗费价值 9 美元的原料。制造每辆火车需要耗费 Giapetto 的可变人力成本和间接成本一共 10 美元。这家木头士兵和火车的制造商需要两类熟练工人：木工和修整工。一个士兵需要 2 小时的修整工劳动和 1 小时的木工劳动。一辆火车需要 1 小时的修整工劳动和 1 小时的木工劳动。每周 Giapetto 可以获得所有必需的原料，但是只能提供 100 个修整工时和 80 个木工工时。市场对于火车的需求是无限的，但是每周最多可以销售 40 个士兵。Giapetto 希望能够使每周的收益（收入 - 成本）最大化。

下面我们对这个问题的重要信息和假设小结一下：

1. 有两种木制玩具：士兵和火车。
2. 一个士兵的销售价格为 27 美元，需要耗费价值 10 美元的原料，另外需要耗费可变人力成本和间接成本一共 14 美元。
3. 一辆火车的销售价格为 21 美元，需要耗费价值 9 美元的原料，另外需要耗费可变人力成本和间接成本一共 10 美元。
4. 一个士兵需要 2 小时的修整工劳动和 1 小时的木工劳动。
5. 一辆火车需要 1 小时的修整工劳动和 1 小时的木工劳动。
6. 每周最多可以获得 100 个修整工时和 80 个木工工时。
7. 每周对于火车的需求是无限的，但是最多可以销售 40 个士兵。

我们的目标是确定每周生产士兵和火车的数量，从而可以使每周的收益最大化。

建模

要对一个线性问题进行建模，必须首先确定决策变量，这是因为这些变量在每个 simplex 算法循环中都会变化，并决定了目标函数的值，这样才会产生优化解决方案。在 Giapetto 的商店中，目标函数是收益，这是一个每周生产的士兵和火车的函数。因此，这个问题中的两个决策变量是：

• x1：每周生产的士兵数量
• x2：每周生产的火车数量

确定了决策变量之后，这个问题的目标函数就简化为每个玩具的收入减去成本，这是 x1 和 x2 的一个函数。

请注意，收益线性依赖于 x1 和 x2 —— 这是一个线性问题。

乍一看，收益可以通过简单地增大 x1 和 x2 来实现最大化。然而，如果生活是如此简单，那就让我们都开始生产火车和士兵，并迁居到 Caribbean 好了！不幸的是，有很多约束会对可以选择的决策变量造成影响（否则这个模型很可能就是错的）。