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

回想一下我们对这个问题的 假设。前三条确定了决策变量和目标函数。第 4 个假设和第 6 个假设说完成士兵的制造需要耗费一定的木工和修整工工时。此处的约束是 Giapetto 并没有无限的木工和修整工工时。这就是约束！下面我们来分析并澄清这个问题。

一个士兵需要 2 小时的修整工时劳动，Giapetto 每周最多有 100 小时的修整工劳动力，因此每周就不能生产超过 50 个士兵。类似地，木工工时的约束也使它不能每周生产超过 80 个士兵。注意第一个约束比第二个约束更为严格。第一个约束实际上是第二个约束的一个子集，因此第二个约束实际上是冗余的。

上面这段描述展示了怎么样对优化问题进行建模，但这只是不完全的一个分析，因为所有必需的变量都还没有充分考虑。这尚不是 Giapetto 问题的彻底解决方案。那么我们应该怎么样解决这个问题呢？

我们首先通过分析约束因素来发现所有的约束条件。首先，到底是什么约束的修整工时？由于士兵和火车都需要修整时间，因此它们都需要考虑在内。假设要制造 10 个士兵和 20 辆火车。这所需要的修整工时是 10 乘以 2 小时（用来生产士兵）加上 20 乘以 1 小时（用来生产火车），总共是 40 小时的修整劳动力。按照决策变量的术语来说，通用的约束为：

有很多 (x1,x2) 对能够满足这个不等式，因此它无法确定 Giapetto 商店的最佳组合。

现在我们已经知道了修整工时的约束，同样也可以得出木工工时的约束：

非常不错！这个问题只剩下一个约束了。记得每周对士兵的需求么？根据问题描述，每周最多可以生产 40 个士兵：

对于火车的需求是无限的，因此对它就没有什么约束了。这个模型就完成了，它包括以下等式：

注意最后一个约束。它确保决策变量的值都是正数。问题并没有显式地说明这一点，但它却非常重要（也很显然）。

现在 GLPK 可以解析这个模型了（由于 GLPK 很擅长解决线性优化问题）。

一点理论知识

下面我们来了解以下问题的解析空间。有了这两个决策变量，它就有了两个维度。

图 1. Giapetto 的极大域

(x1,x2) 超出第一象限（其中所有值都为正数）的结果都已经被舍弃了。然而，我们需要注意这个解析空间仍然是无限的（这依然可能 成为我希望移居 Caribbean 的一种情况！）

正如我们给出的约束一样，这个无限的解析空间达到了边界。有了上面的 不等式 6，结果就更加有趣了。

图 2. Giapetto 考虑修整约束时的解析域

这个解析空间包含了 (x1,x2) 在第一象限的所有可能值，它们可以满足修整工时约束。

在加上 不等式 7 之后，结果就收缩了。

图 3. Giapetto 考虑修整约束和木工约束时的解析域

注意，这个解析空间更小。这意味着其中只有更少的 (x1,x2) 值。在应用不等式 8 之后，结果还会进一步变小。

图 4. Giapetto 的可行域

这样解析空间更小了。这个可以满足所有约束的解析空间称为可行域（feasible region）。图 4 给出了 Giapetto 商店的可行域。这个区域中任何 (x1,x2) 对都是这个问题的一个可能解决方案。

现在的问题是：哪个值能够使得 Giapetto 的收益最大化呢？

使用 GLPK 来解析模型

GLPK 对于解析这个问题来说是一个很好的工具。Giapetto 问题中的数学公式需要使用 GNU MathProg 语言进行编写。需要声明的关键内容有：

• 决策变量
• 目标函数
• 约束
• 问题数据集

下面的代码显示了怎么样使用 MathProg 来解决 Giapetto 问题。代码中的行号都不是代码本身的一部分。添加这些行号只是为了能够方便地对代码进行引用。

清单 1. Giapetto 问题的第一个解决方案：giapetto.sol

 1  #
 2  # Giapetto's problem
 3  #
 4  # This finds the optimal solution for maximizing Giapetto's profit
 5  #
 6
 7  /* Decision variables */
 8  var x1 >=0;  /* soldier */
 9  var x2 >=0;  /* train */
10
11  /* Objective function */
12  maximize z: 3*x1 + 2*x2;
13
14  /* Constraints */
15  s.t. Finishing : 2*x1 + x2 <= 100;
16  s.t. Carpentry : x1 + x2 <= 80;
17  s.t. Demand    : x1 <= 40;
18
19  end;