设为主页
 收藏本站
 

这些结果说明日常饮食最低成本（优化值）是 0.90 美元。哪些约束共同决定了这个解决方案呢？

这个报告的第二部分表明巧克力和糖的约束都是有下界的，因此这份日常饮食使用了最少的巧克力和糖。这个临界值告诉我们如果我们可以放松巧克力限制一个单位（变成 5 盎司，而不是 6 盎司），那么目标函数就可以改进 0.025（它会从 0.9 变成 0.875）。类似地，如果我们将糖约束放松一个单位，那么目标函数就会改进 0.075。道理是很显然的：吃得越少，我们花的钱也就越少。重要的一点是要对它们进行边界和数量的常规意义的考察。例如，如果我们被告知最好吃 200 磅的巧克力，但是不能摄取任何能量，那么我们就会对此表示怀疑（如果真能如此，我们倒是会感激不尽）。

报告的第三部分则给出了决策变量的优化值：3 份冰激凌和 1 瓶可乐。巧克力松糕和菠萝芝士蛋糕都有一个临界值，因为这些值受到了符号约束的限制。如果巧克力松糕变量的临界值可以是 -1，那么目标函数就还可以改进 0.275，但是对于这个问题的具体情况来说，这当然没什么用处。

邮件问题

这个问题引自于“Operations Research”：

一个邮局需要有不同数目的全职员工在每周的不同时间工作（总结如下）。联盟规定每个全职员工必须连续工作 5 天，然后休息 2 天。例如，在周一到周五工作的员工必须在周六和周日休息。邮局希望只雇佣全职员工来满足自己的日常需求，并且雇佣员工的人数要最少。

下面我们对这个问题的一些重要信息进行一下总结：

• 每个全职工人只能连续工作 5 天，然后就要休息 2 天
• 第一天（周一）：需要 17 个工人
• 第二天：需要 13 个工人
• 第三天：需要 15 个工人
• 第四天：需要 19 个工人
• 第五天：需要 14 个工人
• 第六天：需要 16 个工人
• 第七天（周日）：需要 11 个工人

邮局需要对满足自己需要的雇员数目实现最小化。

建模

下面让我们开始分析这个问题的决策变量。我们应该使用 7 个变量，一周中的每天都要使用一个变量，其值等于在当天工作的员工数目。尽管乍看起来这已经解决了这个问题，但是这不能实现一个员工每周只能工作 5 天的约束，因为在员工某天工作并不能要求该员工在下一天也工作。

正确的途径应该是确保在 i 天开始工作的员工在接下来的连续 4 天也会工作，因此正确的方法是使用 xi 表示从 i 天开始工作的员工数目。使用这种方法，强制这种连续约束就简单多了。决策变量就变成了：

• x1：从周一开始工作的员工数目
• x2：从周二开始工作的员工数目
• x3：从周三开始工作的员工数目
• x4：从周四开始工作的员工数目
• x5：从周五开始工作的员工数目
• x6：从周六开始工作的员工数目
• x7：从周日开始工作的员工数目

需要最小化的目标函数是所雇佣员工的数量，它可以这样给出：

那么，约束都是什么呢？一周中的每天都有一个约束，这是为了确保当天的工人数量最少。让我们以周一为例来看一下。哪些人在周一工作呢？在我脑海中浮现出来的第一个（片面）答案是 “那些在周一开始工作的人”。但是还有别人吗？有，那些要连续工作 5 天的员工中，周日开始工作的员工在周一时应该也在工作（回想一下问题的定义）。同理，我们可以推论那些周六、周五、周四开始工作的员工在周一也都在工作。

这个约束确保周一至少有 17 名员工在工作。

类似地：

当然，不要忘记了符号约束：

邮局问题的 GNU MathProg 解决方案

注意：清单 4 中的行号仅仅是为了参考方便而给出的。

清单 4. 邮局问题解决方案

 1      #
 2      # Post office problem
 3      #
 4      # This finds the optimal solution for minimizing the number of full-time
 5      # employees to the post office problem
 6      #
 7
 8      /* sets */
 9      set DAYS;
10
11      /* parameters */
12      param Need {i in DAYS};
13
14      /* Decision variables. x[i]: No. of workers starting at day i */
15      var x {i in DAYS} >= 0;
16
17      /* objective function */
18      minimize z: sum{i in DAYS} x[i];
19
20      /* Constraints */
21
22      s.t. mon: sum{i in DAYS: i<>'Tue' and i<>'Wed'} x[i] >= Need['Mon'];
23      s.t. tue: sum{i in DAYS: i<>'Wed' and i<>'Thu'} x[i] >= Need['Tue'];
24      s.t. wed: sum{i in DAYS: i<>'Thu' and i<>'Fri'} x[i] >= Need['Wed'];
25      s.t. thu: sum{i in DAYS: i<>'Fri' and i<>'Sat'} x[i] >= Need['Thu'];
26      s.t. fri: sum{i in DAYS: i<>'Sat' and i<>'Sun'} x[i] >= Need['Fri'];
27      s.t. sat: sum{i in DAYS: i<>'Sun' and i<>'Mon'} x[i] >= Need['Sat'];
28      s.t. sun: sum{i in DAYS: i<>'Mon' and i<>'Tue'} x[i] >= Need['Sun'];
29
30      data;
31
32      set DAYS:= Mon Tue Wed Thu Fri Sat Sun;
33
34      param Need:=
35      Mon             17
36      Tue             13
37      Wed             15
38      Thu             19
39      Fri             14
40      Sat             16
41      Sun             11;
42
43      end;