【Python】PuLPで最適化問題を解いてみる

PythonにはPuLPという数理最適化問題を解くことができるライブラリがあります。今回は簡単な線形計画問題を例にPuLPを使用してみたいと思います。

例題

材料AとBから合成できる製品PとQがある。 Pを1個作るのに、Aが3kg、Bが1kg必要でQを1個作るのに、Aが1kg、Bが2kg必要である。 また、Pの一個あたりの利益は300円でQの1個当りの利益は200円である。 材料Aは20kg、Bは14kgしかないときに、PとQの利益の合計が最大になるようにするには、 PとQをそれぞれどれだけ作成すればよいか。

定式化

上記の問題をPuLPで解く前にまずは定式化が必要です。

まず、それぞれPをx個、Qをy個作るとしたときに最大化させたい利益を目的関数とすると以下の式で表されます。

\( 目的関数 = 300*x +200 *y \)

次に制約条件を考えます。材料Aは20kgしかないので以下となります。

\( 3*x + y \leq 20 \)

材料Bは14Kgしかないので以下の式になります。

\( x + 2*y \leq 14 \)

以上で定式化は終わりです。

PuLPで書いてみる

まずはPython環境にPuLPをpipでインストールします。

pip install pulp

あとは先程定式化したものをPuLPのお作法通りに記載します。

from pulp import LpMaximize, LpProblem, LpVariable, value

m = LpProblem(sense=LpMaximize) # 線形計画問題の最大化問題とする
x = LpVariable("x", lowBound=0) # lowBound 変数の下限
y = LpVariable("y", lowBound=0) # lowBound 変数の下限
m += 300*x + 200*y # 目的関数の設定
m += 3*x + y <= 20 # 制約条件
m += x + 2*y <= 14 # 制約条件
m.solve()
print(value(x), value(y))

5.2 4.4

このように必要な関数をimportし、式を記述した後はm.solve()というメソッドで最適解を得ることができました。

なお、今回の例題では個数を求めるため、最後の結果の5.2,4,4という数字では現実的には使えません。このような場合は整数計画問題となります。

このような場合は次のようにLpIntegerを用いることで整数の解を得ることができます。

from pulp import LpMaximize, LpProblem, LpVariable, LpInteger, value #LpIntegerをimport

m = LpProblem(sense=LpMaximize)
# x = LpVariable("x", lowBound=0) 
# y = LpVariable("y", lowBound=0)
x = LpVariable("x", lowBound=0, cat=LpInteger) # catの引数にLpIntegerを入れておく
y = LpVariable("y", lowBound=0, cat=LpInteger) # catの引数にLpIntegerを入れておく
m += 300*x + 200*y
m += 3*x + y <= 20
m += x + 2*y <= 14
m.solve()
print(value(x), value(y))

5.0 4.0

まとめ

PuLPはpipだけでソルバーを含めてインストールすることができ、例題のような単純な線形計画問題の場合は非常に簡単に使用し、解を得ることができました。