줄리아로 선형계획문제 푸는 법
개요
JuMP 패키지를 사용하면 된다1. JuMP는 Julia Mathematical Programming의 준말이다. 다른 언어와 비교해보자면 줄리아에서의 코딩은 거의 수식을 있는 그대로 옮겨적는 수준으로 직관적이다.
코드
$$ \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)$ 를 알고 있다. 이 선형계획문제는 다음과 옮겨 적고 풀 수 있다.
전체코드
using JuMP
using GLPK
model = Model(GLPK.Optimizer)
@variable(model, x₁ ≥ 0)
@variable(model, x₂ ≥ 0)
@objective(model, Max, x₁ + x₂)
@constraint(model, c1, - x₁ + x₂ ≤ 1)
@constraint(model, c2, x₁ ≤ 3)
@constraint(model, c3, x₂ ≤ 2)
print(model)
optimize!(model)
@show objective_value(model)
@show value(x₁)
@show value(x₂)
Model(), GLPK.Optimizer
julia> using JuMP
julia> using GLPK
julia> model = Model(GLPK.Optimizer)
A JuMP Model
Feasibility problem with:
Variables: 0
Model mode: AUTOMATIC
CachingOptimizer state: EMPTY_OPTIMIZER
Solver name: GLPK
Model()을 통해 선형계획문제를 만들고, 그 최적화 알고리즘으로써 GLPK.Optimizer을 사용한다. 어쨌든 GLPK도 독립적인 패키지기 때문에 별도로 설치해야한다.
@variable(), @objective(), @constraint()
julia> @variable(model, x₁ ≥ 0)
x₁
julia> @variable(model, x₂ ≥ 0)
x₂
julia> @objective(model, Max, x₁ + x₂)
x₁ + x₂
julia> @constraint(model, c1, - x₁ + x₂ ≤ 1)
c1 : -x₁ + x₂ <= 1.0
julia> @constraint(model, c2, x₁ ≤ 3)
c2 : x₁ <= 3.0
julia> @constraint(model, c3, x₂ ≤ 2)
c3 : x₂ <= 2.0
@variable()로 변수를 추가하고, @objective()로 목적 함수를 정하고, @constraint()로 제약조건을 추가한다. 솔직히 수식을 그대로 적은 것과 마찬가지다. 이 모델을 출력해보면 다음과 같이 거의 수식 그대로 문제가 정의되었음을 확인할 수 있다.
julia> print(model)
Max x₁ + x₂
Subject to
c1 : -x₁ + x₂ <= 1.0
c2 : x₁ <= 3.0
c3 : x₂ <= 2.0
x₁ >= 0.0
x₂ >= 0.0
optimize!(), @show
julia> optimize!(model)
julia> @show objective_value(model)
objective_value(model) = 5.0
5.0
julia> @show value(x₁)
value(x₁) = 3.0
3.0
julia> @show value(x₂)
value(x₂) = 2.0
2.0
optimize!(model) 메소드를 통해 최적화하고, @show를 통해 결과를 출력한다. 그 결과는 우리가 이미 알고 있던 것처럼 x₁$=x_{1} = 3$, x₂$=x_{2} = 2$ 이다.
환경
- OS: Windows
- julia: v1.7.0
- JuMP v0.21.5