R로 선형계획문제 푸는 법

R로 선형계획문제 푸는 법

How to Solve Linear Programming Problem using 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

같이보기


  1. https://towardsdatascience.com/linear-programming-in-r-444e9c199280 ↩︎

댓글