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で最適化問題を解く際にはおすすめです。
実は私も！？独学で損する人の特徴
「スクールは高いから独学で成功する」という気持ちの方は多いと思います。
もちろんその方が金額は低く抑えられるでしょう。
ただ
独学には向き不向きがあり、実はスクールが向いている人も大勢います。
そんな方のために参考として、
テックアカデミー卒業生がスクールを選んだ理由
をご紹介します。
- ・困って挫折しそうなときに、質問や相談できる相手がいる環境で学んでいきたいなと思った
- ・わかった気になっているだけだったので、自分を追い込む環境に置いた方がいいと感じた
- ・スクールのカリキュラムで市場に求められるスキルを学ぶべきと思った
少しでも当てはまる部分があれば、
スクールが向いているかもしれません。
お試しのつもりで、まずは一度
無料相談
に参加してみませんか？
現役エンジニア・デザイナーに何でも気軽に相談できる30分
を
すべて無料で
できます。
無理な勧誘は一切ない
ので、お気軽にご参加ください。
監修してくれたメンター
| メンター三浦
モバイルゲームを運用している会社のエンジニアをしています。趣味でWEB開発やクラウドコンピューティングもやっており、ソフトもハードもなんでもやります。 TechAcademyジュニアではPythonロボティクスコースを担当しています。好きな言語はPython, Node.js。 |
内容分かりやすくて良かったです！
ゆかりちゃんも分からないことがあったら質問してね！
分かりました。ありがとうございます！
TechAcademyでは、初心者でも、Pythonを使った人工知能（AI）や機械学習の基礎を習得できる、オンラインブートキャンプを開催しています。
また、現役エンジニアから学べる無料体験も実施しているので、ぜひ参加してみてください。
プログラミングを独学していて、このように感じた経験はないでしょうか？
- ・調べてもほしい情報が見つからない
- ・独学のスキルが実際の業務で通用するのか不安
- ・目標への学習プランがわからず、迷子になりそう
テックアカデミーでは、このような
学習に不安を抱えている方へ、現役エンジニア講師とマンツーマンで相談できる機会を無料で提供
しています。
30分間、オンラインでどんなことでも質問し放題です。
「受けてよかった」と感じていただけるよう
厳しい試験を通過した講師
があなたの相談に真摯に向き合います。
「ただ気になることを相談したい」
「漠然としているがプロの話を聞いてみたい」
こんな気持ちでも大丈夫です。
無理な勧誘は一切ありません
ので、まずはお気軽にご参加ください。
※体験用のカリキュラムも無料で配布いたします。（1週間限定）
