GNU 线性编程工具包.docVIP

GNU 线性编程工具包（GNU Linear Programming Kit），第 1 部分: 线性优化简介 为复杂数学问题寻找最佳解决方案  文档选项 未显示需要 JavaScript 的文档选项级别： 中级 HYPERLINK /developerworks/cn/linux/l-glpk1/index.html#authorRodrigo Ceron (HYPERLINK mailto:rceron@?subject=%E7%BA%BF%E6%80%A7%E4%BC%98%E5%8C%96%E7%AE%80%E4%BB%8Brceron@), 资深软件工程师, IBM 2006 年 9 月 04 日 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）；请参看下面 HYPERLINK /developerworks/cn/linux/l-glpk1/index.html#resources参考资料 中的链接。 有很多工具都可以用来解决线性编程的问题。尽管有些专用工具都非常出名，但是开放源码社区中的很多人可能并不了解免费的 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，请参看 HYPERLINK /developerworks/cn/linux/l-glpk1/index.html#resources参考资料 一节中给出的 上面 GLPK 页面的链接。） GLPK 不是一个程序 —— 它无法运行，也没有 main()函数。实际上，客户机需要将问题数据通过 GLPK API 提供给算法程序，并接收结果。GLPK 有一个默认的客户机，即 glpsol 程序，它可以与这个 API 进行交互。通常诸如 glpsol 之类的程序都被称为 solver，而不是客户机，因此从现在开始我们就会看到这个术语。  HYPERLINK /developerworks/cn/linux/l-glpk1/index.html#main回页首 GNU MathProg 建模语言 GNU MathProg 建模语言非常简单，但却可以很好地声明线性问题。通常，问题的声明包括： 问题决策变量。 目标函数。注意目标（objective） 是一个名词，而不是一个形容词。这个名字是运筹学理论中的标准术语。 问题约束。 问题参数（数据）。 让我们从一个简单的两变量的例子入手：Giapetto 的 Woodcarving 公司。  HYPERLINK /developerworks/cn/linux/l-glpk1/index.html#main回页首Giapetto 的 Woodcarving 公司 这个问题引自于 Operations Research： Giapetto 的 Woodcarving 公司生产两种木头制作的玩具：士兵和火车。一个士兵的销