GNU线性编程中的中间问题

本文将继续介绍有关 GNU 线性编程工具包（GNU Linear Programming Kit） 和 glpsol 客户机工具以及 GNU MathProg 语言的使用。在本文中，我们将从一个日常饮食问题入手来介绍怎么样表述一个简单的多类型变量，并声明二元参数。然后通过一个邮局资源分配问题来介绍 MathProg 表达式和只使用整型的决策变量。

本文是有关 GNU Linear Programming Kit（GLPK） 的 3 部分系列文章 中的第二篇。有关 GLPK 的介绍，请阅读本系列的第一部分 “GNU 线性编程工具包（GNU Linear Programming Kit），第 1 部分: 线性优化简介”。

日常饮食问题

这个问题来自于Wayne L. Winston 所著的 Operations Research: Applications and Algorithms, 4th Edition（Thomson，2004 年）；参阅后面 参考资料 中的链接。

我的日常饮食要求吃的所有食物都必须属于四种基本的食物：巧克力蛋糕、冰激凌、汽水饮料和芝士蛋糕。现在有 4 种食品可以选择：巧克力松糕、巧克力冰激凌、可乐和菠萝芝士蛋糕。每个巧克力松糕价值 0.50 美元，每份巧克力冰激凌价值 0.20 美元，每瓶可乐价值 0.30 美元，每片菠萝芝士蛋糕价值 0.80 美元。每天我必须摄取至少 500 卡路里能量、6 盎司巧克力、10 盎司糖，以及 8 盎司脂肪。每种食物的单位营养含量如下表所示。现在我想以最小成本满足自己的日常营养需求。

现在我们对这个问题的相关重要信息进行一下总结：

食物的单位成本

• 巧克力松糕： $0.50 （每片）
• 巧克力冰激凌：$0.20 （每份）
• 可乐： $0.30 （每瓶）
• 菠萝芝士蛋糕：$0.80 （每片）

每天的食物需求

• 500 卡路里
• 6 盎司巧克力
• 10 盎司糖
• 8 盎司脂肪

食物营养含量

• 巧克力松糕：400 卡路里能量，3 盎司巧克力，2 盎司糖，2 盎司脂肪
• 巧克力冰激凌（每份）：200 卡路里能量，2 盎司巧克力，2 盎司糖，4 盎司脂肪
• 可乐（每瓶）：150 卡路里能量，0 盎司巧克力，4 盎司糖，1 盎司脂肪
• 菠萝芝士蛋糕（1 片）：500 卡路里能量，0 盎司巧克力，4 盎司糖，5 盎司脂肪

建模

对这个日常饮食问题进行建模在解决过 第 1 部分中的 Giapetto 问题 之后应该就很容易了。下面让我们首先来确定一下决策变量。

此处的目标是以最小的成本满足日常营养需要。因此，决策变量应该是需要购买的每种食品的数量：

食品变量：

• x1：巧克力松糕片数
• x2：巧克力冰激凌的份数
• x3：可乐的瓶数
• x4：菠萝芝士蛋糕的片数

现在我们就可以使用这些决策变量来编写目标函数了。日常饮食的成本 z 需要最小化：

下一个步骤是为各个约束编写不等式。注意日常饮食的食物提供的卡路里、巧克力、糖和脂肪数量都有限制。这 4 种需要每个都是一个限制，因此约束可以如下所示：

注意菠萝芝士蛋糕和可乐中都不含巧克力。

最后，是一些符号约束：

试想一下这个问题的可行区域。这个问题有 4 个变量。因此，其解析域应该有 4 个轴。这很难绘制出来，因此我们需要使用自己的想象力。首先，解析域应该在一个 4 维空间中。使用每个约束，解析空间会逐渐收缩，最终看起来就像是一个多面体一样。

日常饮食问题的 GNU MathProg 解决方案

注意：清单 1 中的行号仅仅是为了引用方便而给出的。

清单 1. 日常饮食问题的 GNU MathProg 解决方案

 1      #
 2      # Diet problem
 3      #
 4      # This finds the optimal solution for minimizing the cost of my diet
 5      #
 6
 7      /* sets */
 8      set FOOD;
 9      set NEED;
10
11      /* parameters */
12      param NutrTable {i in FOOD, j in NEED};
13      param Cost {i in FOOD};
14      param Need {j in NEED};
15
16      /* decision variables: x1: Brownie, x2: Ice cream, x3: soda, x4: cake*/
17      var x {i in FOOD} >= 0;
18
19      /* objective function */
20      minimize z: sum{i in FOOD} Cost[i]*x[i];
21
22      /* Constraints */
23      s.t. const{j in NEED} : sum{i in FOOD} NutrTable[i,j]*x[i] >= Need[j];
24
25      /* data section */
26      data;
27
28      set FOOD := Brownie "Ice cream" soda cake;
29      set NEED := Calorie Chocolate Sugar Fat;
30
31      param NutrTable: Calorie        Chocolate       Sugar   Fat:=
32      Brownie          400            3               2       2
33      "Ice cream"      200            2               2       4
34      soda             150            0               4       1
35      cake             500            0               4       5;
36
37      param Cost:=
38      Brownie         0.5
39      "Ice cream"     0.2
40      soda            0.3
41      cake            0.8;
42
43      param Need:=
44      Calorie         500
45      Chocolate       6
46      Sugar           10
47      Fat             8;
48
49      end;