JuliaのJuMPで線形計画法
イントロダクション
線形計画法で使う場面に遭遇したので、Pythonで解いていました。 しかし、どうせなら勉強のために、とJuliaで解くことにしました。
目次
線形計画法とは
複数の1次関数をすべて満たす数値のうち、目的関数の解を最大または最小とする最適化法です。 このとき、いずれの関数も線形(1次式)とならなければなりません。
線形の問題ですので、組合せ最適化などに比べると容易に解が出ます。 簡単な線形計画問題は高校数学の領域の問題で出題されます。
導入
実行環境は以下の通りです。
PC: macbook Air OS: MacOS Mojave Julia: 1.1
JuliaにはJuMPという最適化用のパッケージがあります。
今回はJuMPで線形計画法を解きます。
インストールはaddモードでJuMPをaddするだけです。
ソルバーにはGLPKを採用しました。
(v1.1) pkg> add JuMP (v1.1) pkg> add GLPK
問題を解いてみる
適当に作った問題を解かせます。
たくみ君はお母さんからおつかいを頼まれました。内容は1000円で、1個8円のチョコを20個、1個17円のスナック菓子を10個買うというものでした。残ったお金でたくみ君のチョコとスナック菓子を買って良いと言われました。ただし、お店にはチョコが150個、スナック菓子が60個しかなく、お釣りはもらえません。チョコとスナック菓子を何個ずつ買えばよいでしょう？
チョコの個数をx、スナック菓子の個数をy、代金をzとすると、制限条件は以下のようになります。
目的条件は以下のようになり、このときzが最大となるxとyの組み合わせを考えます。
JuMPのexampleを参考にコードを組みました。
まず、計算モデル定義します。 今回はGLPKを使用しています。
model = Model(with_optimizer(GLPK.Optimizer))
次に制限の記述です。
個数や金額は整数型なので、Intも引数に入れます。
@variable(model, 20 <= x <= 150, Int) @variable(model, 10 <= y <= 60, Int)
目的関数の定義です。
最大化問題なので、Maxと記述します。
@objective(model, Max, 8x + 17y)
最大化したい値の制限条件も記述します。
@constraint(model, 8x + 18y <= 1000)
そして、実行。
JuMP.optimize!(model)
結果の取り出しはvalueを使います。
obj_value = JuMP.objective_value(model) x_value = JuMP.value(x) y_value = JuMP.value(y)
全体のコードは以下。
using JuMP, GLPK function takumi_LP(; verbose = true) model = Model(with_optimizer(GLPK.Optimizer)) @variable(model, 20 <= x <= 150, Int) @variable(model, 10 <= y <= 60, Int) @objective(model, Max, 8x + 17y) @constraint(model, 8x + 18y <= 1000) if verbose print(model) end JuMP.optimize!(model) obj_value = JuMP.objective_value(model) x_value = JuMP.value(x) y_value = JuMP.value(y) if verbose println("Objective value: ", obj_value) println("x: ", x_value) println("y: ", y_value) end end takumi_LP(verbose = true)
解は以下の通り。
Max 8 x + 17 y Subject to x integer y integer x ≥ 20.0 y ≥ 10.0 x ≤ 150.0 y ≤ 60.0 8 x + 18 y ≤ 1000.0 Objective value: 988.0 x: 98.0 y: 12.0
つまり、たくみ君はチョコを98個、スナック菓子を12個買うと、最大代金(988円)でお菓子を買えます。
上記のコードをGithubに載せます。
まとめ
JuMPを使うことでjuliaで線形計画問題を解くことができます。 JuMPには線形計画問題だけではなく、他の最適化計算ができるみたいなので、次回チャレンジします。
