注意输出结果现在显示已经找到一个整型优化解决方案，在找到这个解决方案之前，GLPK 已经对放松限制下的问题（不要求变量是整数）计算了优化解决方案。
Problem: post
Rows: 8
Columns: 7 (7 integer, 0 binary)
Non-zeros: 42
Status: INTEGER OPTIMAL
Objective: z = 23 (MINimum) 22.33333333 (LP)
No. Row name Activity Lower bound Upper bound
------ ------------ ------------- ------------- -------------
1 z 23
2 mon 18 17
3 tue 13 13
4 wed 15 15
5 thu 19 19
6 fri 14 14
7 sat 16 16
8 sun 20 11
No. Column name Activity Lower bound Upper bound
------ ------------ ------------- ------------- -------------
1 x[Mon] * 1 0
2 x[Tue] * 2 0
3 x[Wed] * 3 0
4 x[Thu] * 7 0
5 x[Fri] * 1 0
6 x[Sat] * 3 0
7 x[Sun] * 6 0
End of output
|
第一部分说明所找到的解决方案是整型优化的，为目标函数找到的最小值是 23。这个邮局需要雇佣 23 名全职员工才能满足自己的需求。放松限制的目标函数（不将决策变量当作整数考虑）的优化值同时也给出来了。
让我们暂时跳过这个报告的第二部分。第三部分给出了决策变量的值。这些值都是能使整个问题的目标函数最小化的整数值。
现在，让我们来讨论一下有关第二部分的问题。它给出了约束的行为。有些是有下界的，现在我们可能会期望一个临界值或影子价格。不过，讨论整型问题的临界值并没有意义。整型问题的可行域并不是一个连续区域。换而言之，可行域不是一个多面体；它是由这个多面体或放松限制问题的实际多面体边界中的一些整数（x1、x2、...、 xn）对。这意味着可行域是由这个空间中的一些离散点构成的，因此放松某个限制可能会在新的多面体中获得更好的解决方案，也可能并不能获得更好的解决方案。
要更好地理解此处讨论的问题，让我们来了解一下这个简单的可行域：
使用 x 表示的蓝点是一些整数（x1,x2）对。这是一个 x1 X x2 两维空间的整数可行域，其约束为 x1 >= 0、x2 >= 0 和 x1 + x2 <= 4。如果这种简单情况的目标函数是 maximize z = x1 - x2，那么显然优化解决方案就是 (2,0)，这个约束刚好是边界约束（因为优化解决方案就在约束规则这条线上）。
如果这个约束放松一个单元，x1 + x2 <= 5，可行域现在就不同了。
优化解决方案仍然是整数点 (2,0)，不过现在可行域中有更多整数点了。
因此，整型问题的约束放松并不一定会改进解决方案，因为可行域是离散的，而不是连续的。
您可能会问的另外一个问题是：“整型问题的优化解决方案与放松限制问题的优化解决方案有关联吗？”答案要看 simplex 算法背后采用的代数关系，但是有关它是怎么样工作的解释已经超出了本文的范围。我们只需要知道非整型问题的优化解决方案通常都是一个多面体的顶点就好了。通常这都是正确的！
在上面的第一个可行域中，优化解决方案是解析空间中的右顶点，而这个解析空间是一个由所有约束构成的三角形。在目标函数延伸的这个方向上，目标函数会逐渐改进。在这个简单的情况中，x1 - x2 的方向延伸是 (1,-1)。因此，优化解决方案是从轴的原点沿 (1,-1) 方向作为方向向量指向多面体边界的最远点。由于整型解决方案可能会在一个边界上，也可能在多面体内部，因此最佳的情况是采用一个顶点上的整型解决方案。在这种特例中，整型和非整型的优化解决方案是相同的，但是并非所有情况都是如此。为什么呢？因为这个整数点距离原点的距离可能不如放松限制的解决方案点那样远。对于其他非最佳情况来说，最好的整数点就在多面体中，目标函数自然比放松限制的问题的的性能要差，这我们在邮局问题中就已经注意到了。
记住这个分析使用了一个简单的两变量最大化问题。对于最小化问题的相同分析会查找可以将目标函数最小化的点，是最靠近原点的地方（沿着目标函数延伸方向的反方向）。
在日常饮食问题中，我们看到了怎么样对一个简单的多变量问题进行建模，怎么样在 GNU MathProg 中声明二维参数，以及怎么样解释最小化问题的结果。
邮局问题中引入了 MathProg 表达式和只使用整型的决策变量。我们学习了怎么样分析整型问题的
