ジュリアで線形計画問題を解く方法
Overview
To solve optimization problems, one can use the JuMP package[^1]. JuMP stands for Julia Mathematical Programming. Compared to other languages, coding in Julia is almost like directly transcribing mathematical formulas, which is very intuitive.
Code
$$ \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} $$
As a simple example, let’s solve the maximization problem described in $x_{1} , x_{2} \ge 0$. At the shrimp sushi restaurant, this problem was solved manually using the simplex method, and the solution $\left( x_{1}^{\ast}, x_{2}^{\ast} \right) = (3,2)$ is known. This linear programming problem can be transcribed and solved as follows.
Full Code
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
By using Model(), one can create a linear programming problem and use GLPK.Optimizer as the optimization algorithm. Note that GLPK is also an independent package and needs to be installed separately.
@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
Variables are added with @variable(), the objective function is set with @objective(), and constraints are added with @constraint(). Honestly, it’s almost like directly writing down the equations. If we print out this model, we can see that the problem is defined almost exactly as the formulas.
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
The optimize!(model) method is used to perform the optimization, and @show is used to display the results. The results are, as we already knew, x₁$=x_{1} = 3$, x₂$=x_{2} = 2$.
Environment
- OS: Windows
- julia: v1.7.0
- JuMP v0.21.5
See Also
- How to solve linear programming problems with Excel
- How to solve linear programming problems in Julia with
JuMP.jl - How to solve linear programming problems in Python with
scipy - How to solve linear programming problems in MATLAB with
Optimization Toolbox - How to solve linear programming problems in R with
lpSolve
概要
JuMPパッケージを使えばいい[^1]。JuMPは Julia Mathematical Programmingの略だ。他の言語と比べた場合、Juliaでのコーディングはほぼそのまま数式を移して書くレベルで直感的だ。
コード
$$ \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
関連項目
- エクセルで線形計画問題を解く方法
- Juliaで線形計画問題を解く方法
JuMP.jl - Pythonで線形計画問題を解く方法
scipy - MATLABで線形計画問題を解く方法
Optimization Toolbox - Rで線形計画問題を解く方法
lpSolve