Rで線形計画問題を解く方法

概要

lpSolve パッケージを使えばよい¹。行列の形で表示された 線形計画問題 の$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

関連リンク

• エクセルで線形計画問題を解く方法
• ジュリアで線形計画問題を解く方法 JuMP.jl
• パイソンで線形計画問題を解く方法 scipy
• マットラボで線形計画問題を解く方法 Optimization Toolbox
• Rで線形計画問題を解く方法 lpSolve