Rで線形計画問題を解く方法
概要
lpSolveパッケージを使えばいいんだ1。行列形で表された線型計画問題の$A, \mathbf{b}, \mathbf{c}$を入れて使うんだ。
コード
$$ \begin{matrix} \text{Maximize} & & x_{1} & + & x_{2} \\ \text{subject to} &-& x_{1} & + & x_{2} & \le & 1 \\ & & x_{1} & & & \le & 3 \\ & & & & x_{2} & \le & 2 \end{matrix} $$
簡単な例として、$x_{1} , x_{2} \ge 0$にある最大化問題を解いてみよう。生エビ寿司屋はこの問題をシンプレックス・メソッドを使って手で解いて、その答え$\left( x_{1}^{\ast}, x_{2}^{\ast} \right) = (3,2)$を知ってるんだ。この線型計画問題は
$$ \begin{matrix} \text{Optimize} & \mathbf{c}^{T} \mathbf{x} \\ \text{subject to} & A \mathbf{x} \le \mathbf{b} \end{matrix} $$
$\mathbf{c} = (1,1)$、$A = \begin{bmatrix} -1 & 1 \\ 1 & 0 \\ 1 & 0 \end{bmatrix}$、$\mathbf{b} = (1,3,2)$があるから、次のように書いて解けるんだ。f.objは$\mathbf{c}$、f.conは$A$、f.rhsは$\mathbf{b}$だ。
library(lpSolve)
f.obj <- c(1, 1)
f.con <- matrix(c(-1, 1,
1, 0,
0, 1), nrow = 3, byrow = TRUE)
f.dir <- c("<=",
"<=",
"<=")
f.rhs <- c(1,
3,
2)
lp("max", f.obj, f.con, f.dir, f.rhs)
lp("max", f.obj, f.con, f.dir, f.rhs)$solution
그 결과는 우리가 이미 알고 있던 것처럼 $\left( x_{1}, x_{2} \right) = \left( 3,2 \right) =$3 2다.
> lp("max", f.obj, f.con, f.dir, f.rhs)
Success: the objective function is 5
>
> lp("max", f.obj, f.con, f.dir, f.rhs)$solution
[1] 3 2
環境
- OS: Windows
- R: v4.1.2
- lpSolve v5.6.15