줄리아로 선형계획문제 푸는 법

줄리아로 선형계획문제 푸는 법

How to Solve Linear Programming Problem using julia

개요

JuMP 패키지를 사용하면 된다.1 JuMPJulia 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

같이보기


  1. https://jump.dev/JuMP.jl/stable/ ↩︎

댓글