分类： LINUX
2006-12-26 19:32:58
GNU 线性编程工具包（GNU Linear Programming Kit），第 3 部分: 高级问题和最佳解决方案香水利润的最大化和更好篮球队的组建 |  |
|
级别: 中级
Rodrigo Ceron (), 资深软件工程师, IBM
2006 年 12 月 26 日
GNU 线性编程工具包（GNU Linear Programming Kit，GLPK）是一个功能强大的工具，被证明可以很好地解决具有多限制的数值问题。本文是 3 部分系列文章 中的第 3 篇，阐述如何使用 GLPK 和 glpsol 客户端工具结合 GNU MathProg 语言来解决香水生产问题和篮球阵容问题。
本文是 有关使用 GNU 线性编程工具包 的 3 部分系列文章中的第 3 篇。有关 GLPK 的简介，请阅读本系列文章的第 1 部分 “ GNU 线性编程工具包（GNU Linear Programming Kit），第 1 部分：线性优化简介”。
[样例问题中所有的公司和产品名都是虚构的。 -Ed.]
这个问题来自于 Wayne L. Winston 所著的 Operations Research: Applications and Algorithms, 4th Edition（Thomson，2004 年）；请参阅 参考资料 中的链接。
Rylon 公司生产 Brute 和 Chanelle 香水。生产每种香水所需要的原料的购买价格是每磅 3 美元。处理每磅原料需要 1 小时的劳动时间。每磅原料可以生产 3 盎司的 Regular Brute Perfume 和 4 盎司的 Regular Chanelle Perfume。Regular Brute 的售价为每盎司 7 美元，Regular Chanelle 的售价为每盎司 6 美元。Rylon 公司还可以对 Regular Brute 和 Regular Chanelle 进行再加工来生产 Luxury Brute，其售价为每盎司 18 美元；以及 Luxury Chanelle，其售价为每盎司 14 美元。再加工每盎司 Regular Brute 还需要 3 小时的劳动时间和 4 美元的处理成本，才可以生产 1 盎司的 Luxury Brute。再加工每盎司 Regular Chanelle 还需要 2 小时的劳动时间和 4 美元的处理成本，才可以生产 1 盎司的 Luxury Chanelle。每年 Rylon 公司一共有 6000 小时的劳动时间，最多可以购买 4000 磅原料。请实现 Rylon 公司利润的最大化。
现在我们对这个问题的相关重要信息进行一下总结：
在对这个问题进行建模之前，让我们首先来看一下从原料到最终产品的转化过程：
图 1 说明所有的原料都被转换成了中间产品（图中用中间的球表示）。中间上边这个球表示 Regular Brute 产品。有些 Regular Brute 可以再加工生成 Luxury Brute，因此这个球分成了两部分：被销售的 Regular Brute （绿色）和被再加工生成 Luxury Brute 的 Regular Brute（蓝色）。Chanelle 的情况也是如此。请注意这两个中间的球中只有蓝色的部分（而且蓝色部分会全部）会进行再加工。
|
这个特定问题的决策变量需要包括所有的香水和原料：
x1：每年销售 Regular Brute 的磅数x2：每年销售 Luxury Brute 的磅数x3：每年销售 Regular Chanelle 的磅数x4：每年销售 Luxury Chanelle 的磅数x5：每年购买的原料的磅数目标函数是要根据这些决策变量实现 Rylon 公司利润的最大化：
这个问题中有几个小约束是有关处理原料所需的劳动时间的。Rylon 需要一些时间来加工自己购买的原料，其值由 x5 给出。将 Regular Brute 和 Chanelle 再加工成 Luxury Brute 和 Chanelle 是需要时间的，因此总共的时间取决于 x2 和 x4 加上 x5：
Rylon 公司可以购买的原料的最大值也是一个约束：
同样，符号约束也非常重要：
如果这个模型被转换成 GNU MathProg 并使用 glpsol 进行分析，那么它会报告这个问题是无界的： Rylon 生产的产品越多，它的获利也就越多。要是公司能迁移到加勒比海，这倒是个不错的业务，但很明显这不太可能。那么问题出在什么地方呢？
原
材料需要制造成 Regular Brute 和 Chanelle，它们又可以进一步再制造成 Luxury
版本的香水。这两个变量应该怎样进行转换呢？原材料到 Chanelle 和 Brute 的转换并不是 1 对 1
的，这一点在问题描述中可以看到。每磅原材料可以产生 3 盎司的 Regular Brute 和 4 盎司的 Regular
Chanelle（一共可以产生 7 盎司香水）。可以将这种转换过程看作是一个黑盒。如果将 1 磅原材料放到这个黑盒中，就可以从这个盒子中拿出
3 盎司 Regular Brute 和 4 盎司 Regular Chanelle。如果加工 N 磅原材料，那么 图 1 中中间上面的这个球就一定是 3N。这是 Regular 加上 Luxury Brute 的数量。
请记住 1 盎司 Regular Brute 和 Chanelle 香水都可以生产 1 盎司的 Luxury Brute 和 Chanelle 香水。另外，中间下面的这个球中的 Regular 和 Luxury Chanelle 总共应是 4N 盎司。Rylon 公司不能使用 N 磅原材料来生产 2N 盎司的 Regular Brute 和 Luxury Brute 及 5N
盎司的 Regular Chanelle 和 Luxury Chanelle。1 比 3 的 Brute 转换比例和 1 比 4 的
Chanelle 转换比例必须要保持不变，这与 Brute 和 Chanelle 产品中 Regular 和 Luxury 的比例无关。
所生产的香水必须一直由原材料生成。如果没有保持这种平衡，结果就可能是错误的。因此必须要遵守下面的约束：
这 个公式说明所生产的所有 Brute（所销售的 Regular Brute 加上进行再生产所使用的 Regular Brute）除以 3 必须等于原材料的单位数量。这听起来对么？前面提到过加工一个单位的原材料（1 磅）可以生成 3 个单位（3 盎司）的 Regular Brute，而 1 个单位的 Regular Brute 可以转换成 1 盎司的 Luxury 产品。请再次注意 Regular Brute 加上 Luxury Brute 的单位（盎司）总数必须是所加工的原材料单位数的 3 倍。因此，这个约束看来没什么问题。因为 GLPK 需要所有决策变量都在等式相同的一边，所以需要将上面的公式改写成下面的形式：
类似地，我们还有下面的公式：
这个公式看起来正确么？一个单位的原材料可以生成 4 盎司的 Chanelle（ Regular 加上 Luxury 产品），因此这也是正确的。在 GLPK 中，需要把这个公式中的决策变量都放到左边：
现在，整个问题已经全部解决了。下面让我们为这个问题编写一个 GNU MathProg 程序。
|
glpsol 的下面代码可以解决 Rylon 问题（行号不是代码的一部分，添加这些代码只是为了简化后面对代码的引用）。
1 # |
应该注意上面这段代码中所有的声明，为了完整起见，下面我们来快速浏览一下这些内容。
第 7 行声明了一个名为 PROD 的集合，它的元素是 Brute 和 Chanelle 产品。第 29 行定义了产品。这 4 个简写分别代表 Regular Brute、Luxury Brute、Regular
Chanelle 和 Luxury Chanelle，最后一个元素是原材料。原材料也作为一个产品列出来，这样所有的决策变量都可以在一个集合中了。
第 10、11 和 12 行声明了几个参数：收入、成本和劳动时间。其参数是在第 31 行到 50 行中定义的。工作时间表明了处理 1 磅原材料以及将 Regular Brute 和 Chanelle 再加工成 Luxury 版本（每盎司）需要多少时间。成本包含每磅原材料的成本以及再加工每磅 Regular Brute 和 Chanelle 的成本。
第 14 行定义了决策变量，这是一个包含 5 个元素的 PROD 集合的数组。
第 20 行定义了目标函数，它是 Rylon 公司的利润（收入 - 成本）。
最后，第 23 到 26 行声明了这个问题的约束，这在前面已经讨论过了。
清单 2 给出了输出结果：
Problem: brute |
第一部分显示解是最佳的，目标函数约等于 172667。第三部分给出了每个决策变量的值。第二部分给出了约束。注意数量守恒约束通常在 bound 列中都有一个 = 号。它们的边界值不能进行分析，因为使用一个具有等式约束的边界值没有任何意义。这一点您同意吗？如果您有不同的观点，请给我发邮件。
下面让我们来进行一个简要的分析。Rylon 已经处理了 4000 磅原材料。根据数量守恒（黑盒按照一定的比例将原材料转换成 Chanelle 和 Brute），需要确保 N 磅的原材料可以生产 3N 盎司的 Brute（Regular 加上 Luxury）和
4N
盎司的 Chanelle（Regular 加上 Luxury）。这里有 16000 盎司的 Regular Chanelle 以及 0 盎司的
Luxury Chanelle。因此对于 Chanelle 的比例是 1（4000 磅）比 4（16000 盎司）。类似地，对于 Brute
的比例是 1（4000 磅）比 3（11333.333 盎司加上 666.667 盎司）。很好，我们现在接触到实际问题了。
如果没有这种数量守恒约束，glpsol 就会将下面的错误打印到 stdout 上：
Reading model section from brute-production2.mod... |
结果表明这个问题没有对偶的可行方案，不过这是什么意思呢？每个问题都有对偶性。例如，最大化问题可以重写为一个最小化问题。在这个意义上最大化问题会被称为初始问题，最小化问题就称为对偶问题。如果初始问题是一个最小化问题，那么其对偶问题就是一个最大化问题。通俗地说，对偶问题就意味着是次要问题或可选问题，而原始问题则意味着主要问题。
无解的原始问题就会有一个无界的对偶问题。无界的原始问题也会有一个不可行的对偶问题。由于 glpsol 断言对偶问题不可行，因此原始问题就是无界的（这就是我们前面谈到的加勒比海岛的情况）。
|
本节将介绍一个具有多种最佳解的简单问题。本系列文章到目前为止所给出的所有问题都只有一个最佳解。具有多个解的问题在其可行域中有多个点可以实现问题的最大化或最小化。不管怎样，这些关键点的目标函数是相同的。下面是一个例子。
|
最大化下面的目标函数：
并遵守下面两个约束：
这个特定问题的可行域如图 2 中的灰色区域所示。
在为这个问题寻找最佳解而编写 GNU MathProg 程序之前，需要对其稍微进行一下分析。在本系列文章 第 2 部分 中曾经介绍过目标函数朝最大化问题的发展方向。最佳解通常都是其可行域所构成的多面体的一个顶点。当目标函数的方向导数与这个多面体（由约束构成）的一个面垂直时，此多面体上的这个面上的所有点对于这个目标函数来说都具有相同的值，因为它们都在同一个 iso-quanta 上。
iso-quanta 是由具有相同目标函数值的点所构成的空间中的一条线。在这个问题中，x1+x2=1 就是一个 iso-quanta，
x1+x2=2 是另外一个 iso-quanta，依此类推。如果约束线是沿这个目标函数的方向导数距离最远的一条线，并且与该导数垂直，那么这个可行域边界上所有的点都可以使这个目标解达到最佳值。
|
下面是 GNU MathProg 对多解问题的解决方案：
1 # |
这个非常简单的程序声明了两个决策变量：约束和目标函数。
清单 5 给出了结果：
Problem: multiple |
这个解是最佳的，目标函数的值是 5。这个报告的第二部分说明这个约束是有界的，其边界值是 1。
在第三部分中，变量 x2 在其下界上，并具有一个边界值。这个边界值显示为 epsilon 通常用来说明这是一个非常小的数字，eps 是 epsilon 的缩写）。比最小精度再小的数字可能就是 0 了。因此，如果 x2 变量还可以再变化，那么目标函数的值只会变化 0。换而言之，当约束使用新的 (x1, x2) 对时，x2 的变化不会引起目标函数值的变化。因此在这个可行域中有多个点对于目标函数来说会产生相同的值。这个问题具有多个解！
请记住不论何时只要 glpsol 报告一个变量的边界值是
|
集合覆盖问题涉及的是二元决策变量；也就是说，它们的值只能是 0 或 1、yes 或 no。
篮 球教练想要组建自己的球队来参加一场比赛。这个球队含 7 个球员，其中 5 个球员可以在场上比赛。每个球员在助攻、防守、投篮和篮板方面的能力可以被评价为 1（较差）到 3（很好）。他们在球场中的位置有 3 个：后场（B）、中场（M）和前场（F）。每个球员在球场中的位置及其能力如表 1 所示。
| 球员 | 位置 | 助攻 | 投篮 | 篮板 | 防守 |
|---|---|---|---|---|---|
| 1 | B | 3 | 3 | 1 | 3 |
| 2 | M | 2 | 1 | 3 | 2 |
| 3 | BM | 2 | 3 | 2 | 2 |
| 4 | MF | 1 | 3 | 3 | 1 |
| 5 | BF | 1 | 3 | 1 | 2 |
| 6 | MF | 3 | 1 | 2 | 3 |
| 7 | BF | 3 | 2 | 2 | 1 |
所选择的 5 个球员必须能够一起满足下面的约束条件：
目标是在这场比赛中实现防守能力的最大化。
|
首先，要决定使用哪些决策变量。整个球队中有 7 个球员。但是哪 5 个球员应该上场比赛呢？7 个二元变量会确定每个球员 i 会上场比赛（决策变量为 1）还是不上场比赛（0）：
目标函数是寻找所有球员的防守能力的最大值。
并不需要将目标函数除以 5 来获得平均值，因为 f(x) 最大化的条件与 f(x) 除以 CONSTANT 最大化的条件是相同的。换而言之，除法并不会改变目标函数最大化的方向。
接下来分析一下各个约束。第一个约束要求至少有 3 个球员必须能够打后场的位置。只有球员 1、3、5、7 能够打这个位置：
因此，这个约束可以确保这 4 个二元变量中至少有 3 个为 1。
类似地，对于中场这个位置来说，球员 2、3、4 和 6 中必须有一个要上场：
前场位置需要球员 4、5、6、7 中的两个。
助攻、篮板、防守和投篮的平均能力必须至少为 2：
第 5 个约束要求如果球员 3 上场比赛，那么球员 6 就不能上场比赛，反之亦然。因此这两个球员只有一个能上场比赛：
对于这个公式来说，如果 y3=1，那么这个约束会强制 y6 是 0，反之亦然。这个约束强制球员 1 或 6 必须在这个球队中参加比赛。这与教练的意图并不完全相同。他们偶尔也可能都不参加比赛，上述公式没有考虑到这一点。
现在，如果 y3=1，那么 y6=0，因为其和不能大于 1。如果 y6=1，那么 y3=0。如果 y3 和 y6 都为 0 ，那么这个公式也是对的。
第 6 个约束声明当球员 1 上场比赛时，球员 4 和 5 也必须上场比赛（可能这已经签订到他们的合同中了）。因此当 y1=1 时，y4 和
y5 也必须是 1：
这个不等式有些技巧。如果 y1=0，那么
y4 >= 0。这意味着如果球员 1 没有上场比赛，那么球员 4 可能就在场上比赛。然而，如果球员 1 在场上比赛，那么
y4 >= 1，因此 y4 就等于 1。当球员 1 在场上比赛时，球员 4 也在场上比赛。对于球员 5 也会强制采用相同的不等式。
最后一个约束要求球员 2 或 3 必须要上场比赛。请注意它们不能同时上场参加比赛：
还记得有关球员 3 和 6 的约束的第一个尝试么？这个约束强制球员 2 或 3 上场参加比赛，但不能同时上场。
这里还有一个隐藏约束：一个篮球队在场上最多只能有 5 名球员。因此：
为了确保决策变量都是二元的，它们应该声明为只能是二元集合中的一个值：
由于这个问题实际上是选择决策变量来满足一些约束，因此把它称为集合覆盖问题。
|
同上，代码中的行号也不是代码本身的一部分。增加这些行号只是为了稍后引用代码方便。
1 # |
它有 4 个参数：
skill 是一个二维表，其中 i 表示球员，j 列出他们的技能。这个表的值是以数字形式表示的球员 i 的技能 j。position 是一个二维二元表，i 表示球员，j 列出位置。这个表决定了球员 i 是否可以打位置 j （该值是否为 1）。min_in_position 是在 POSITIONS 集合上定义的，用来定义可以打位置 i 的最少球员个数。min_skill_average 是在 SKILLS 集合上定义的，用来定义针对技能 i，上场球员所必须具有的技能最小平均值。在本例中对于所有运动员这个平均值是相同的，但是在教练需要调整球队实力的情况下，它应该单独进行声明。这个问题的核心是将决策变量声明成二元变量。这与将它们声明为整型变量一样容易。只需要向声明中添加一个 binary，如 20 行所示。
输出结果如下：
Problem: basketball |
请注意所有的决策变量都是 0 或 1，这与我们期望的一样。
|
本系列文章一共分析了 6 个问题，每个问题都引入了一个新的概念，我们对这些问题都进行了建模，也都采用 GNU MathProg 语言以一种简单优雅的方式编写了相应的程序以便 GLPK 能够解决该问题，另外我们还对结果进行了分析。
使用线性编程和运筹学理论来寻找最佳解并不限于本系列文章中所介绍的这些问题，诸如石油、化学、食物和金融之类的领域都可以充分利用线性方法和运筹学理论。
我鼓励大家使用并共享此处讨论的概念，这样就会有更多人可以了解到线性编程和运筹学的强大功能。我希望这些资料对大家有所帮助。
Rodrigo Ceron Ferreira de Castro 是 IBM Linux Technology Center 的一名资深软件工程师。他在 2004 年毕业于 State University of Campinas（UNICAMP）。毕业时他获得了 State Engineering Institute 奖和 Engineering Council Certification of Honor 的荣誉。他在巴西和其他国家举办的开放源码会议上进行过多次演讲。 | ||