gnu 线性编程工具包

《gnu 线性编程工具包》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、GNU线性编程工具包（GNULinearProgrammingKit），第1部分:线性优化简介为复杂数学问题寻找最佳解决方案文档选项未显示需要JavaScript的文档选项级别：中级RodrigoCeron(rceron@br.ibm.com),资深软件工程师,IBM2006年9月04日GNULinearProgrammingKit对于解决具有多种约束的数学问题来说是一个功能非常强大的工具。本文简要介绍了如何使用GLPK（glpsol客户机工具）和GNUMathProg语言来解决Giapetto的Woodcarving公司（一家玩具制造商）的作业优化问

2、题。简介“线性编程是一个用来解决优化问题的工具。在1947年，GeorgeDantzig开发了一种效率方法——simplex算法——来解决线性编程的问题。由于simplex算法的出现，线性编程已经在工业界、银行界、教育界、林业、石油行业以及运输业界中广泛地用来解决优化问题。在对财富500强公司的调查中，85%的被调查者都说他们已经使用了线性编程。”引自OperationsResearch:ApplicationsandAlgorithms,4thEdition，WayneL.Winston著（Thomson，2004）；请参看下面参考资料中的链接。有很

3、多工具都可以用来解决线性编程的问题。尽管有些专用工具都非常出名，但是开放源码社区中的很多人可能并不了解免费的GLPK工具。本系列文章一共3篇，将逐渐介绍GLPK的功能和用法；本文是其中的第1篇，在本文中，我们将对GLPK简要进行介绍，然后展示并应用GLPK中的GNUMathProgLanguage。如果我们仅仅从运筹学理论入手，希望学习进行建模和解决线性编程的问题，那么本文就是一个很好的指南。GNULinearProgrammingKitGNULinearProgrammingKit（GLPK）是一个使用了众所周知的运筹学算法来解决线性问题的程序库。这

4、些程序实现了simplex算法、branchandbound算法、primal-dualinteriorpoint算法以及很多其他算法。请查看GLPK下载包中所包含的GLPK手册以便了解更多的内容。（要下载GLPK，请参看参考资料一节中给出的gnu.org上面GLPK页面的链接。）GLPK不是一个程序——它无法运行，也没有main()函数。实际上，客户机需要将问题数据通过GLPKAPI提供给算法程序，并接收结果。GLPK有一个默认的客户机，即glpsol程序，它可以与这个API进行交互。通常诸如glpsol之类的程序都被称为solver，而不是客户机，

5、因此从现在开始我们就会看到这个术语。回页首GNUMathProg建模语言GNUMathProg建模语言非常简单，但却可以很好地声明线性问题。通常，问题的声明包括：·问题决策变量。·目标函数。注意目标（objective）是一个名词，而不是一个形容词。这个名字是运筹学理论中的标准术语。·问题约束。·问题参数（数据）。让我们从一个简单的两变量的例子入手：Giapetto的Woodcarving公司。回页首Giapetto的Woodcarving公司这个问题引自于OperationsResearch：Giapetto的Woodcarving公司生产两种木头制

6、作的玩具：士兵和火车。一个士兵的销售价格为27美元，需要耗费价值10美元的原料。制造每个士兵需要耗费Giapetto的可变人力成本和间接成本一共14美元。一辆火车的销售价格为21美元，需要耗费价值9美元的原料。制造每辆火车需要耗费Giapetto的可变人力成本和间接成本一共10美元。这家木头士兵和火车的制造商需要两类熟练工人：木工和修整工。一个士兵需要2小时的修整工劳动和1小时的木工劳动。一辆火车需要1小时的修整工劳动和1小时的木工劳动。每周Giapetto可以获得所有必需的原料，但是只能提供100个修整工时和80个木工工时。市场对于火车的需求是无限的

7、，但是每周最多可以销售40个士兵。Giapetto希望能够使每周的收益（收入-成本）最大化。下面我们对这个问题的重要信息和假设小结一下：1.有两种木制玩具：士兵和火车。2.一个士兵的销售价格为27美元，需要耗费价值10美元的原料，另外需要耗费可变人力成本和间接成本一共14美元。3.一辆火车的销售价格为21美元，需要耗费价值9美元的原料，另外需要耗费可变人力成本和间接成本一共10美元。4.一个士兵需要2小时的修整工劳动和1小时的木工劳动。5.一辆火车需要1小时的修整工劳动和1小时的木工劳动。6.每周最多可以获得100个修整工时和80个木工工时。7.每周对

8、于火车的需求是无限的，但是最多可以销售40个士兵。我们的目标是确定每周生产士兵和火车的数量，从