r - R 中 lpSolve 中的绝对值约束

Question

我想用以下附加约束进一步约束下面的系统，它使用绝对值运算符:

abs(x1)+abs(x2)+abs(x3) <= 10

是否有可行的方法在 R 中实现这些额外的绝对值约束？

方程组:

maximize: x1 + 9x2 + x3;

subject to:

x1 + 2x2 + 3x3 <= 9

3x1 + 2x2 + 2x3 <= 15

R代码:

require(lpSolve)
# objective function, constants, constraints
obj = c(1,9,1)
con = matrix(c(1,2,3,3,2,2), nrow=2, byrow=TRUE)
rel = c("<=", "<=")
rhs = c(9,15)

解决方法:

my.lp = lp("max", obj, con, rel, rhs)
my.lp$objval
my.lp$solution

很明显这是一个简单的例子来说明我在网上搜索后拉的问题。 lp_solve 本身似乎有一种方法，如 here 所证明的那样在 lp_solve 在线帮助指南中。但是，如果可能的话，我更愿意将问题框定在 R 中。

Answer 1

要在 LP 中为 |x| 建模，您通常会创建两个新变量，x^- 和 x^+。将它们都约束为非负数:

x^-, x^+ >= 0

然后每次模型中有 x 时，将其替换为 x^+ - x^-，并且每次有 |x|，将其替换为 x^+ + x^-。请注意，这仅在您使用基于单纯形的 LP 求解器而不是内点法时才有效。 lp_solve 使用单纯形。

这样做的原因是:假设在最优解中 x = 10。然后求解器将设置 x^+ = 10 和 x^- = 0 以获得

 x  = x^+ - x^- = 10
|x| = x^+ + x^- = 10.

如果在最优解中x = -10，则x^+ = 0，x^- = 10，

 x  = x^+ - x^- = -10
|x| = x^+ + x^- =  10.

(求解器不会选择 x^+ = 50 和 x^- = 40 来得到 x = 10 因为单纯形法总是选择极值点解。)

如果您对模型中的三个 abs 分别执行此技巧，它应该会起作用。