PuLPを使って線形計画問題を解く

LP計算に使えるsolver「PuLP」

最適化問題にはまっていてpythonで使えるsolverを探していたところで見つけたのがPuLP。有名なところだとgurobiとかだけど、有償なのでなかなか手が出ない。ということでいいよPuLP。PuLPいいよ。

問題

出典：線形計画法の例題（http://www.fujilab.dnj.ynu.ac.jp/lecture/system2.pdf ）

あるレストランで、手持ちの材料からハンバーグとオムレツを作って利益を最大にしたいと考えている。手持ちの材料は
　・ひき肉3800g
　・タマネギ2100g
　・ケチャップ1200g
であり、それぞれの品を作るのに必要な材料の量は
　・ハンバーグ１個あたり　ひき肉60g、タマネギ20g、ケチャップ 20g
　・オムレツ１個あたり　ひき肉40g、タマネギ30g、ケチャップ10g
であるとする。販売価格は
　・ハンバーグ 400円
　・オムレツ　300円
とする。総売り上げを最大にするには、それぞれハンバーグとオムレツを幾つずつ作ればよいか

モデル化

上記の問題をモデル化すると以下のようになる。変数zを総売り上げ、変数xをハンバーグの個数、変数yをオムレツの個数とする。

目的関数　：maximize z = 400x + 300y
制約条件　：60x + 40y <= 3800
　　　　　：20x + 30y <= 2100
　　　　　：20x + 10y <= 1200

制約条件をx、yが満たし、目的変数zが最大となる組み合わせを探す。例えばx=1、y=1の組み合わせは制約条件をすべて満たすが、それよりも目的変数zが大きくなる組み合わせがあるのは容易に想像ができる。また、変数xが60を超えると制約条件を満たすことができないこともわかる。この組み合わせを試してくれるのが今回のsolverである「PuLP」君ということだ。

インストール

PuLPをpipでインストール

pip install pulp

コーディング

上記コードを実行すると途中で変数をprintしているので、経過がわかる。

hamburg and omelet:
MAXIMIZE
400*x + 300*y + 0

SUBJECT TO
_C1: 60 x + 40 y <= 3800
_C2: 20 x + 30 y <= 2100
_C3: 20 x + 10 y <= 1200

VARIABLES
x free Integer
y free Integer

Optimal
Result
x 30.0
y 50.0
MAX VALUE 400 * 30 + 300 * 50 = 27000

MAXIMIZE以下でモデル化した内容が確認できる。VARIABLESで変数がとる値を確認。今回は整数値でどの値も許したが、インスタンスの作成時にとりうる範囲を制約条件とすることもできる

x = pulp.LpVariable('x', 0, 100, cat='Integer')$

上記のようにすることで変数xの取りうる数値が０から１００までの整数値と制約することができる。また今回は整数値：Integerとしたが"cat="の値に"連続値：Continuous"や"二値：Binary"を指定することもできる。
続けて"Optimal"が出たら計算完了の合図。いかにxとyの最適値と総売り上げの計算経過を出力した。

結果

ハンバーグ30個、オムレツ50個が最適値が示されたので
総売り上げ = 400 * 30 + 300 * 50 = 27000
と算出された。計算時間は以下の通りいいスペックではなくても0.1秒ほど。まぁ簡単な問題だしね。

real    0m0.165s
user    0m0.048s
sys     0m0.040s