处理ε最优解

上一节考虑了多个（真实）最优解的情况。当我们有几个 $$\varepsilon$$ -最佳解决方案？更具体地说，考虑一下

$$\begin{array}{lrrl}\max&\varepsilon x+y&\vec{c}=&（\varepsilon，1）\\s.t\leq 0&A{3\cdot}=&（0，-1）\&y\leq 1&A{4\cdot}=&（0,1）。\\\end{array}$$

从图形上看，这可以描述为

$\缩放框{1.0}{\includegraphics[width=4in]{refman_misc/codedraw6.pdf}$

如果 $$\varepsilon$$ 如果为零，则我们处于前面描述的情况。然而，请注意，目标向量的微小扰动可能导致 $x^1$

或

被报告为最优。公差在这里起着重要作用。如果 $$\varepsilon$$ 比如说，是否定的 $x^1$

将是数学上的最佳结果，但由于最优性公差，我们可以得出这样的结论 $x^2$

这是最优的。更准确地说，如果 $$\varepsilon$$ 小于的默认最优性公差 $$10^{-6}$$ ，则单纯形可以自由声明任一最优解（在公差范围内）。

无论何时，上述陈述都是正确的距离之间 $x^1$ 和 $x^2$ 不是太大。要看到这一点，考虑一下当我们改变右手边时会发生什么情况。 $$A_{4\cdot}$$ 从1到 $10^6$ . 然后可行区域将是一个很长的矩形框，带有顶点 $（0,0）$ , $（0,1）$ , $（10^6,1）$ 和 $（10^6,0）$ . 也许有点奇怪，如果 $$\varepsilon$$ 低于双重容忍度，单纯形可考虑最佳，即使其目标值为 $$1-10^6\varepsilon$$ ，这可能与最终目标值非常相关。

请注意，这两种情况都有一个共同点：目标函数（几乎）平行于可行区域的一侧。在第一种情况下，这一侧相对较短，因此从 $x^2$ 到 $x^1$ 转化为目标值的微小变化。在第二种情况下，与目标函数几乎平行的一侧很长，现在从到可对最终目标函数产生重大影响。

如果去掉这两个成分中的任何一个，即目标向量几乎平行于约束，或者边由于这个近似平行的约束很长，所以这个问题就不会出现。由于本节开头讨论的原因，目标函数通常与一个或多个约束接近平行。因此，避免这种情况的最佳方法是避免第二种情况。最简单的方法是确保变量的范围不要太大。请参阅缩放比例这方面的指导。