PythonでPuLPを利用し線形計画を解く方法を現役エンジニアが解説【初心者向け】
初心者向けにPythonでPuLPを利用する方法について現役エンジニアが解説しています。PuLPとは、線形計画問題を解くためのPythonライブラリです。線形計画問題とは、利益が最大になる組み合わせを求めたり、パズルを解くなどの場合に使います。今回はナップザック問題の解法について解説します。
テックアカデミーマガジンは受講者数No.1のプログラミングスクール「テックアカデミー」が運営。初心者向けにプロが解説した記事を公開中。現役エンジニアの方はこちらをご覧ください。 ※ アンケートモニター提供元：GMOリサーチ株式会社 調査期間：2021年8月12日～8月16日 調査対象：2020年8月以降にプログラミングスクールを受講した18～80歳の男女1,000名 調査手法：インターネット調査
PythonでPuLPを利用する方法について、TechAcademyのメンター（現役エンジニア）が実際のコードを使用して、初心者向けに解説します。
Pythonについてそもそもよく分からないという方は、Pythonとは何なのか解説した記事を読むとさらに理解が深まります。
なお本記事は、TechAcademyのオンラインブートキャンプ、Python講座の内容をもとに紹介しています。
今回は、Pythonに関する内容だね！
どういう内容でしょうか？
PythonでPuLPを利用する方法について詳しく説明していくね！
お願いします！
PuLPとは
PuLPとは、線形計画問題を解くためのPythonライブラリです。線形計画問題とは、目的関数と制約条件が1次式で表される最適化問題のことをいいます。
例えば次のようなパターンが線形計画問題 の一つです。
- コストと利益が異なるいくつかの製品を、決まった数量作るときに、利益が最大になるような量の組み合わせを見つける
- パズルを解く
Pulpライブラリの主要な関数
次にPulpライブラリで使われる関数を紹介します。
- pulp.LpProblem：線形計画問題のオブジェクトを定義します。引数には問題の名前と目的関数を最小化するか最大化するかを書きます。（最小化するときは、pulp.LpMinimize、最大化するときは、pulp.LpMaximize）
- pulp.LpVariable：線形計画で使う変数を定義します。引数には変数名、変数の最小値、変数の最大値、変数の種類を指定します
- problem.solve：pulp.LpProblemで定義した問題を解く関数です。
実際に使ってみよう
それでは、実際にPulpを使って線形計画問題を解いてみましょう。まずは、ライブラリのインストールを行います。pipでインストールできますので、以下の1行を実行します。
pip install pulp
続いてサンプルの以下のサンプルコードを任意のフォルダに保存します。
今回は最適化問題で有名なナップザック問題というものを解いていきます。ナップザック問題とは、ナップザックの中にはいる限度内で荷物の価値を最大になる組み合わせを求める問題です。冒頭で紹介した利益を最大になる組み合わせを求めることと同じです。
というわけで、問題は「以下の表の荷物が存在するとき、重さが10を超えず価値が最大となる組み合わせを求める」というものです。
| 重さ | 価値 |
|---|---|
| 2 | 3 |
| 1 | 2 |
| 3 | 6 |
| 2 | 1 |
| 1 | 3 |
| 4 | 8 |
コレをPulpで解く場合は以下のコードになります。
from pulp
# 重さ
w = [2, 1, 3, 2, 1, 4]
# 価値
v = [3, 2, 6, 1, 3, 8]
# 限度：10kg
W = 10
r = range(len(w))
# 数理モデル
m = pulp.LpProblem(sense=pulp.LpMaximize)
# 変数
x = [pulp.LpVariable('x%d'%i, cat=pulp.LpBinary) for i in r]
# 目的関数
m += pulp.lpDot(v, x)
# 限度を設定し、問題を解く
m += pulp.lpDot(w, x) <= W
m.solve()
print('最大価値:{} / 組み合わせ:{}'.format(pulp.value(m.objective), [i for i in r if pulp.value(x[i]) > 0.5]))
このソースコードを実行すると、以下の実行結果が出力されます。最適な組み合わせのリスト番号とその最大価値を出力しています。
最大価値:20.0 / 組み合わせ:[0, 2, 4, 5]
まとめ
今回は最適化問題を解くためのライブラリであるPulpを紹介しました。
最適化問題は一からアルゴリズムを実装すると複雑で処理に時間がかかりますが、Pulpならシンプルなコーディングで短時間で処理を行うので、Pythonで最適化問題を解く際にはおすすめです。
監修してくれたメンター
| メンター三浦
モバイルゲームを運用している会社のエンジニアをしています。趣味でWEB開発やクラウドコンピューティングもやっており、ソフトもハードもなんでもやります。 TechAcademyジュニアではPythonロボティクスコースを担当しています。好きな言語はPython, Node.js。 |
内容分かりやすくて良かったです！
ゆかりちゃんも分からないことがあったら質問してね！
分かりました。ありがとうございます！
TechAcademyでは、初心者でも、Pythonを使った人工知能（AI）や機械学習の基礎を習得できる、オンラインブートキャンプを開催しています。
また、現役エンジニアから学べる無料体験も実施しているので、ぜひ参加してみてください。
