分类：
2008-10-16 18:21:37
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 建模语言非常简单，但却可以很好地声明线性问题。通常，问题的声明包括：
让我们从一个简单的两变量的例子入手：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 希望能够使每周的收益（收入 - 成本）最大化。
下面我们对这个问题的重要信息和假设小结一下：
我们的目标是确定每周生产士兵和火车的数量，从而可以使每周的收益最大化。
建模
要对一个线性问题进行建模，必须首先确定决策变量，这是因为这些变量在每个 simplex 算法循环中都会变化，并决定了目标函数的值，这样才会产生优化解决方案。在 Giapetto 的商店中，目标函数是收益，这是一个每周生产的士兵和火车的函数。因此，这个问题中的两个决策变量是：
确定了决策变量之后，这个问题的目标函数就简化为每个玩具的收入减去成本，这是 x1 和 x2 的一个函数。
请注意，收益线性依赖于 x1 和 x2 —— 这是一个线性问题。
乍一看，收益可以通过简单地增大 x1 和 x2 来实现最大化。然而，如果生活是如此简单，那就让我们都开始生产火车和士兵，并迁居到 Caribbean 好了！不幸的是，有很多约束会对可以选择的决策变量造成影响（否则这个模型很可能就是错的）。
回想一下我们对这个问题的 假设。前三条确定了决策变量和目标函数。第 4 个假设和第 6 个假设说完成士兵的制造需要耗费一定的木工和修整工工时。此处的约束是 Giapetto 并没有无限的木工和修整工工时。这就是约束！下面我们来分析并澄清这个问题。
一个士兵需要 2 小时的修整工时劳动，Giapetto 每周最多有 100 小时的修整工劳动力，因此每周就不能生产超过 50 个士兵。类似地，木工工时的约束也使它不能每周生产超过 80 个士兵。注意第一个约束比第二个约束更为严格。第一个约束实际上是第二个约束的一个子集，因此第二个约束实际上是冗余的。
上面这段描述展示了如何对优化问题进行建模，但这只是不完全的一个分析，因为所有必需的变量都还没有充分考虑。这尚不是 Giapetto 问题的彻底解决方案。那么我们应该如何解决这个问题呢？
我们首先通过分析约束因素来发现所有的约束条件。首先，到底是什么约束的修整工时？由于士兵和火车都需要修整时间，因此它们都需要考虑在内。假设要制造 10 个士兵和 20 辆火车。这所需要的修整工时是 10 乘以 2 小时（用来生产士兵）加上 20 乘以 1 小时（用来生产火车），总共是 40 小时的修整劳动力。按照决策变量的术语来说，通用的约束为：
有很多 (x1,x2) 对能够满足这个不等式，因此它无法确定 Giapetto 商店的最佳组合。
现在我们已经知道了修整工时的约束，同样也可以得出木工工时的约束：
非常不错！这个问题只剩下一个约束了。记得每周对士兵的需求么？根据问题描述，每周最多可以生产 40 个士兵：
对于火车的需求是无限的，因此对它就没有什么约束了。这个模型就完成了，它包括以下等式：
注意最后一个约束。它确保决策变量的值都是正数。问题并没有显式地说明这一点，但它却非常重要（也很显然）。
现在 GLPK 可以解析这个模型了（由于 GLPK 很擅长解决线性优化问题）。
[1]
