你可以通过更加雄心勃勃来规避选择小的$\epsilon>0$$\mathbf{x}$使得$\mathbf{Ax}\leq \mathbf{b}$$\mathbf{x}$中的最小条目{x}是最大的可能。

为此，引入一个新变量

$$\mathbf{y} = \begin{bmatrix} \mathbf{x}\\ \epsilon\end{bmatrix}\in\mathbb{R}^{n+1}$$ （如果$\mathbf{x}$在$\mathbb{R}^n$ ) 并通过 LP-solver $$\max_y [0 \dots 0\ 1]\cdot \mathbf{y}\quad \text{s.t.}\quad [A\ \mathbf{0}]\mathbf{y}\leq\mathbf{b}\quad \text{and}\quad \mathbf{0}\leq \begin{bmatrix}1 & 0 & \cdots & 0 & -1 \\ 0 & 1 & \cdots & 0 & -1 \\ & \ddots & &\vdots \\ 0 & \cdots & & 1 & -1 \end{bmatrix}\mathbf{y}.$$

这是对以下问题的重新表述：

$$\max \epsilon \quad\text{s.t}\quad \mathbf{Ax\leq b}\quad\text{and}\quad \mathbf{x}\geq\epsilon\mathbf{1}.$$

对于 LP 可行性问题，我不会使用标准单纯形法。标准的原始（或对偶）单纯形算法只会访问原始（或对偶）问题的可行集的顶点。

让你实际想要解决的问题的可行集为，并假设您要解决问题（）：$F = \{\mathbf{x}: \mathbf{Ax} \leq \mathbf{b}, \mathbf{x} > \mathbf{0}\}$$F_{\varepsilon}$

$$\begin{alignat}{1} & \min_{\mathbf{x}} \quad 0 \\ \textrm{s.t.} & \quad \mathbf{Ax} \leq \mathbf{b} \\ & \quad \mathbf{x} \geq \varepsilon \cdot \mathbf{1}. \end{alignat}$$

您要解决的问题的最接近近似值是，它承认的点太多了。问题是正正数的边界（即集合可以使的可行集的边界的一部分。我们想排除这些点。这样做的一种方法是按照 Aron 的建议进行操作，即将设置为一些小的正值，然后使用任何标准的 LP 算法。这种策略是一个很好的策略，并且可能适用于各种情况。但是，如果不可行，它将失败。我们知道$F_{0}$$B = \{\mathbf{x}: \mathbf{x} \geq 0, \exists{i}: x_{i} = 0\}$$F_{0}$$\varepsilon$$F_{\varepsilon}$$F_{0} \subset F \subset F_{\varepsilon}$对于所有（滥用符号并通过其相应问题引用可行集），即使您选择的小正值，LP 求解器也可能表明您的 LP 不可行。$\varepsilon > 0$$\varepsilon$

对于 LP 求解器，我会为 LP 使用任何内部点算法，该算法以可行点开始并保持可行，这是排除中的点的另一种方法。您不必为这些算法提供可行的点；标准求解器将为您完成。仿射缩放、电位缩减和障碍方法等方法设置了辅助 LP，它们将找到可行的解决方案，并且这些算法的迭代遍历可行区域的内部。您只需要在您的可行域中定位一个点，因此只要 LP 求解器使用的辅助问题为您的问题找到一个可行点，并且该可行点是严格正的，您应该没问题。如果求解的小正值失败$B$$F_{\varepsilon}$$\varepsilon$，您仍然可以使用这些方法在中定位一个严格正的可行点。$F_{0}$

但是，不要使用单纯形，因为它只会探索的顶点，而这正是您要避免做的事情。$F_{\varepsilon}$

可行性问题是一个比一般线性问题稍微棘手的游戏，您已经注意到了。如果您正在近似求解（通过使用方程和约束系统的浮点表示），要求是合法的，其中是一些非常小的数值，大到足以确保实际上生活在中，但足够小以至于不考虑边界上的解决方案。$x_i >= \epsilon$$\epsilon$$x_i$$\Re_+$

您可能需要调整，并且您的解决方案将有资格“在的一个因素内”，但这对于许多情况来说已经足够了。$\epsilon$$\epsilon$

aeismail给出的答案要仔细阅读，看lp

$\max( x_1 + x_2)$

英石

$x_1 + x_2 \le 1$

$x_1,x_2 \ge 0$

它有解和以及其他解（退化）。问题的普遍性意味着这些情况也需要处理。$(1,0)$$(0,1)$

由于您可以选择目标函数，因此您可以尝试迭代地修改它。例如，从所有变量的所有系数都等于 1 开始，检查您是否获得了适当的解决方案。如果一个变量为零，则增加它的系数并重新开始......

虽然我不能给出数学证明这是有效的（或者一个定义明确的过程如何修改目标函数）。我希望这有帮助 ：）