R中的对偶单纯形线性规划

Question

我有一个线性规划问题正试图在 R 中解决。我用过 lpSolve 包。 lpSolve 默认使用原始单纯形算法来获得解决方案。如果我想将算法更改为对偶单纯形怎么办？两种算法的结果差异很大。是否有任何其他软件包可以帮助使用对偶单纯形算法解决以下问题。

library("lpSolve")

f.obj <- c(rep(1,12),rep(0,4))
f.cons <- matrix(c(1,-1,0,0,0,0,0,0,0,0,0,0,1,-1,0,0,
                   0,0,1,-1,0,0,0,0,0,0,0,0,1,0,-1,0,
                   0,0,0,0,1,-1,0,0,0,0,0,0,1,0,0,-1,
                   0,0,0,0,0,0,1,-1,0,0,0,0,0,1,-1,0,
                   0,0,0,0,0,0,0,0,1,-1,0,0,0,1,0,-1,
                   0,0,0,0,0,0,0,0,0,0,1,-1,0,0,1,-1),nrow=6,byrow=T)

f.dir <- rep("=",6)

f.rhs <- c(-1.0986,1.6094,-1.0986,1.94591,1.3863,-1.7917)

g <- lp ("min", f.obj, f.cons, f.dir, f.rhs,compute.sens=TRUE)
g$solution

R中使用lpSolve的Primal Simplex如下：

0 0 0 0 0 0.91630 0.0 0.76209 0.47 0 0 0 1.60940 2.70800 0 1.79170

使用Lingo软件和SAS的Dual Simplex如下：

0 0.76214 0 0 1.23214 0 0 0 0.15415 0 0 0 0.8473 1.9459 0 1.7918

两个算法的objective函数相同2.14839

Answer 1

使用 lpSolveAPI，您可以微调求解器：

lprec <- make.lp(0, ncol=16) 
set.objfn(lprec, obj=c(rep(1,12), rep(0,4)))

add.constraint(lprec, xt=c(1,-1,1,-1), indices=c(1, 2, 13, 14), type="=", rhs=-1.0986)
add.constraint(lprec, xt=c(1,-1,1,-1), indices=c(3, 4, 13, 15), type="=", rhs=1.6094)
add.constraint(lprec, xt=c(1,-1,1,-1), indices=c(5, 6, 13, 16), type="=", rhs=-1.0986)
add.constraint(lprec, xt=c(1,-1,1,-1), indices=c(7, 8, 14, 15), type="=", rhs=1.94591)
add.constraint(lprec, xt=c(1,-1,1,-1), indices=c(9, 10, 14, 16), type="=", rhs=1.3863)
add.constraint(lprec, xt=c(1,-1,1,-1), indices=c(11, 12, 15, 16), type="=", rhs=-1.7917)

lp.control(lprec, simplextype="dual", pivoting="dantzig", verbose="detailed")
solve(lprec)
get.variables(lprec)
#  [1] 0.00000 0.00000 0.76209 0.00000 0.00000 0.15421 0.00000 0.00000 1.23209
# [10] 0.00000 0.00000 0.00000 0.84731 1.94591 0.00000 1.79170

有关详细信息，请参阅 ?lp.control.options。但是，我无法重现 LINGO/SAS.

给出的解决方案

R中的对偶单纯形线性规划

linear programming with dual simplex in R

r

linear-programming

simplex-algorithm