r - lpsolve - 不可行的解决方案，但我有 1 的例子

Question

我正在尝试在 LPSolve IDE 中解决这个问题:

/* Objective function */
min: x + y;

/* Variable bounds */
r_1: 2x = 2y;
r_2: x + y = 1.11 x y;
r_3: x >= 1;
r_4: y >= 1;

但我得到的回应是:

Model name:  'LPSolver' - run #1
Objective:   Minimize(R0)

SUBMITTED
Model size:        4 constraints,       2 variables,            5 non-zeros.
Sets:                                   0 GUB,                  0 SOS.

Using DUAL simplex for phase 1 and PRIMAL simplex for phase 2.
The primal and dual simplex pricing strategy set to 'Devex'.

The model is INFEASIBLE
lp_solve unsuccessful after 2 iter and a last best value of 1e+030

当x=1.801801802和y=1.801801802是这里可能的解决方案时，为什么会发生这种情况？

Answer 1

如何找到解决方案

让我们做一些数学计算。

您的问题是:

min x+y
s.t. 2x = 2y
     x + y = 1.11 x y
     x >= 1
     y >= 1

第一个约束2x = 2y可以简化为x=y 。我们现在将整个问题替换为:

min 2*x
s.t. 2*x = 1.11 x^2
     x >= 1

并重新排列:

min 2*x
s.t. 1.11 x^2-2*x=0
     x >= 1

从几何学我们知道1.11 x^2-2*x绘制一条向上开口的抛物线，其最小值小于零。因此，正好有两点。这些由二次方程给出:200/111 和 0。

其中只有一个满足第二个约束:200/111。

为什么我无法使用求解器找到此约束

最简单的方法就是说这是因为 x^2项(替换之前的 x*y 是非线性的)。但它比这更深入一些。只要非线性问题是凸的，就可以容易解决。一个convex problem是一种约束形成单个连续空间的空间，使得在该空间中的两点之间绘制的任何线都保持在该空间的边界内。

你的问题不是凸的。约束1.11 x^2-2*x=0定义无限多个点。这些点中的任何两个点都不能通过位于约束定义的空间中的直线连接，因为该空间是弯曲的。如果约束是 1.11 x^2-2*x<=0那么这个空间将是凸的，因为所有点都可以用留在其内部的直线连接。

非凸问题属于更广泛的一类问题的一部分，称为 NP-Hard 。这意味着没有(也许不可能)任何简单的方法来解决这个问题。我们必须聪明。

可以处理 mixed-integer programming (MIP/MILP) 的求解器可以有效地解决许多非凸问题，其他技术也可以，例如 genetic algorithms 。但是，在幕后，这些技术都依赖于美化的猜测和检查。

因此，您的求解器会失败，因为问题是非凸的，并且您的求解器既不够聪明，无法使用 MIP 来猜测并检查其解的方式，也不够聪明，无法使用二次方程。

那我该如何解决这个问题呢？

在这个特殊的例子中，我们能够使用数学来快速找到解决方案，因为尽管问题是非凸的，但它是一类特殊情况的一部分。数学家的深入思考为我们提供了处理此类的简单方法。

但考虑一下问题的一些概括:

(a) a x^3+b x^2+c x+d=0
(b) a x^4+b x^3+c x^2+d x+e =0
(c) a x^5+b x^4+c x^3+d x^2+e x+f=0

(a) 有必须检查的三个潜在解(精确解为 tricky )，(b) 有四个 ( trickier )，(c) 有五个。 (a) 和 (b) 的公式比二次公式复杂得多，数学家已经证明有 no formula对于(c)，可以使用“初等运算”来表达。相反，我们必须诉诸美化的猜测和检查。

因此，我们用来解决您的问题的技术并不能很好地概括。这就是生活在非凸和 NP 困难领域的意义，也是资助数学、计算机科学和相关领域研究的充分理由。