2

単純な線形計画法の問題を解決するために、linprog R パッケージの solveLP を使用しています。

minimize -x1-x2 
subject to 2*x1+x2+x3    =12
           x1+2*x2   +x4 = 9
           x1,x2,x3,x4 >=0

二重の同等物があります：

maximize 12*y1+9*y2 
subject to 2*y1+y2 <= -1
           y1+2*y2 <= -1
           y1,y2 <=0

問題を原始形式で述べると、正しい結果 (5,2,0,0) が得られます。しかし、双対形式で問題を説明すると、最初の 2 つの制約は単純に無視されます。明らかに (2*y1+y2 <= -1 および y1+2*y2 <= -1) に違反する結果 (0,0) が得られましたが、不足している追加の設定またはパラメーターはありますか? 以下のコードを見て、ご意見をお聞かせください。

require(linprog)
objVec <- c(-1,-1,0,0) 
rhsConstr <- c(12, 9,0,0,0,0) 
Amat <- rbind( c( 2, 1, 1, 0 ),
               c( 1, 2, 0, 1 ),
               c( 1, 0, 0, 0 ),
               c( 0, 1, 0, 0 ),
               c( 0, 0, 1, 0 ),
               c( 0, 0, 0, 1 ))
res <- solveLP( objVec, rhsConstr, Amat, maximum=FALSE, const.dir = c("==","==",">=",">=",">=",">=") , lpSolve=TRUE)
res$solution

# dual problem - this is where the problem is
objVec <- c(12,9) 
rhsConstr <- c(-1.0,-1.0,0,0) 
Amat <- rbind( c( 2, 1),
               c( 1, 2), 
               c( 1, 0),
               c( 0, 1))
res <- solveLP( objVec, rhsConstr, Amat, maximum=TRUE, const.dir = rep("<=",length(rhsConstr)))
res$solution

正の空間では、双対問題は正しい答え (1/3,1/3) を与えます。

objVec <- c(12,9); 
rhsConstr <- c(1,1,0,0); 
Amat <- rbind( c( 2, 1), c( 1, 2), c( 1, 0), c( 0, 1)); 
res <- solveLP( objVec, rhsConstr, Amat, maximum=FALSE, const.dir = rep(">=",length(rhsConstr)) , lpSolve=TRUE); 
res$solution;
4

1 に答える 1

5

多くの線形計画法ライブラリと同様に、暗黙的な非負の制約y>=0があります。実行可能な解決策はありません (ただし、これを示すことを期待res$statusしています)。

solveLPは負の解を許可していないようです: 問題を非負の値のみを持つように変換する (y1をu1-v1にy2置き換えるu2-v2) か、負の値を許可する別のパッケージを使用することができます。

library(Rglpk)
objVec <- c(12,9) 
rhsConstr <- c(-1.0,-1.0,0,0) 
Amat <- rbind( c( 2, 1),
               c( 1, 2), 
               c( 1, 0),
               c( 0, 1))
Rglpk_solve_LP( 
  objVec, Amat, rep("<=",4), rhsConstr,
  bounds = list( lower = list( ind=c(1L,2L), val=c(-Inf,-Inf) ),
                 upper = list( ind=c(1L,2L), val=c( Inf, Inf) ) ), 
  max=TRUE
)
于 2013-12-29T02:50:25.143 に答える