Finishing_hours、
Carpentry_hours 和
Demand_toys。这些参数构成了这个问题的数据矩阵，并用来计算约束，正如我们稍后会看到的一样。
我们以 Finishing_hours 参数为例来看一下这个问题。它是在 TOY 集合上定义的，因此 TOY 集合中的每种玩具都有一个 Finishing_hours 值。记住每个士兵需要 2 小时的修整工作，每辆火车需要 1 小时的修整时间。现在请看一下第 33、34 和 35 行的内容。这是对每种玩具的修整工时的定义。实际上，这些行的内容声明 Finishing_hours[soldier]=2，Finishing_hours[train]=1。因此 Finishing_hours 就是一个 1 行 2 列的矩阵。
木工工时和需求参数都是类似地进行声明的。注意对于火车的需求是无限的，因此在 43 行上我们使用了一个很大的值作为上界。这个值看起来够大么？
第 17 行声明了一个变量 x，对于 TOY 中的每个 i（即 x[soldier] 和 x[train]），我们都要限制它们大于或等于 0。有了这些集合之后，声明变量就变得非常简单了，不是么？
第 20 行声明了对象函数是 z 的最大值，这是每种玩具的总体收益（一共有两种玩具：火车和士兵）。例如，对于士兵来说，收益是士兵个数乘以每个士兵的收益。
第 23、24 和 25 行上的约束也是类似地进行声明的。以修整工时约束为例：它是每种玩具的修整工时乘以所生产的这种玩具的数量之积的总和。对于这两种玩具（火车和士兵）来说，这必须小于或等于 100。类似地，木工工时综合也应该小于或等于 80。
需求约束与上面两个约束有所不同，因为它是为每种玩具而定义的，而不是为所有玩具类型总和进行定义的。因此，我们需要两个约束：一个用于火车，另外一个用于士兵，正如我们在第 25 行中看到的一样。注意索引变量（{i in TOY}）都是在 : 之前出现的。这告诉 GLPK 为 TOY 中的每种玩具类型都创建一个约束，每个约束的等式都在 : 之后出现。在本例中，GLPK 会创建
Dem[soldier] : x[soldier] <= Demand[soldier]
Dem[train] : x[train] <= Demand[train]
解析这个新模型必须产生相同的结果：
清单 5. 使用数据段来解答 Giapetto 问题：giapetto2.sol
Problem: giapetto2
Rows: 5
Columns: 2
Non-zeros: 8
Status: OPTIMAL
Objective: z = 180 (MAXimum)
No. Row name St Activity Lower bound Upper bound Marginal
------ ------------ -- ------------- ------------- ------------- -------------
1 z B 180
2 Fin_hours NU 100 100 1
3 Carp_hours NU 80 80 1
4 Dem[soldier] B 20 40
5 Dem[train] B 60 6.02e+23
No. Column name St Activity Lower bound Upper bound Marginal
------ ------------ -- ------------- ------------- ------------- -------------
1 x[soldier] B 20 0
2 x[train] B 60 0
Karush-Kuhn-Tucker optimality conditions:
KKT.PE: max.abs.err. = 0.00e+00 on row 0
max.rel.err. = 0.00e+00 on row 0
High quality
KKT.PB: max.abs.err. = 0.00e+00 on row 0
max.rel.err. = 0.00e+00 on row 0
High quality
KKT.DE: max.abs.err. = 0.00e+00 on column 0
max.rel.err. = 0.00e+00 on column 0
High quality
KKT.DB: max.abs.err. = 0.00e+00 on row 0
max.rel.err. = 0.00e+00 on row 0
High quality
End of output
|
请注意约束和决策变量现在在 TOY 后面是怎么样命名的，这样看起来非常清晰，而且组织良好。非常不错。我们已经对 Giapetto 的收益进行了最大化！
结束语
我们已经看到了怎么样为一个简单的两变量线性问题写出公式。接下来我们了解了怎么样使用一个简单的 MathProg 程序来使用集合、参数、约束、决策变量和目标函数来解答这个问题。这个程序使用了集合和一个参数数据段。最后，我们学习了怎么样解释最大化问题的结果。
这个三篇系列文章的下一部分将介绍怎么样在不利情况中实现最佳的优化。
原文链接：http://www-128.ibm.com/developerworks/cn/linux/l-glpk1/index.html
如果您对本文有任何疑问或者建议，请到讨论区发表您的意见:
>>
论坛入口 <<
上一篇：
程序员眼中的qmail(qmail源代码分析) 下一篇：
用新的PHP插件实现MySQL为基础的事务
【文章评论】
【收藏本文】
【推荐好友】
【打印本文】
【我要投稿】 【论坛讨论】
