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分か60分お好きな時間が選べて、かつ3回まで
すべて無料で
ご利用できます。
無理な勧誘は一切ない
ので、お気軽にご参加ください。
監修してくれたメンター
| メンター三浦
モバイルゲームを運用している会社のエンジニアをしています。趣味でWEB開発やクラウドコンピューティングもやっており、ソフトもハードもなんでもやります。 TechAcademyジュニアではPythonロボティクスコースを担当しています。好きな言語はPython, Node.js。 |
内容分かりやすくて良かったです！
ゆかりちゃんも分からないことがあったら質問してね！
分かりました。ありがとうございます！
TechAcademyでは、初心者でも、Pythonを使った人工知能（AI）や機械学習の基礎を習得できる、オンラインブートキャンプを開催しています。
また、現役エンジニアから学べる無料体験も実施しているので、ぜひ参加してみてください。
プログラミングを独学で学習していて、このように感じた経験はないでしょうか？
- ・調べてもほしい情報が見つからない
- ・独学のスキルが実際の業務で通用するのか不安
- ・目標への学習プランがわからず、迷子になりそう
テックアカデミーでは、このような
学習に不安を抱えている方へ、マンツーマンで相談できる機会を無料で提供
しています。
30分間、オンラインでどんなことでも質問し放題です。
「受けてよかった」と感じていただけるよう
カウンセラーやエンジニア・デザイナー
があなたの相談に真摯に向き合います。
「自分に合っているか診断してほしい」
「漠然としているが話を聞いてみたい」
こんなささいな悩みでも大丈夫です。
無理な勧誘は一切ありません
ので、まずはお気軽にご参加ください。
※体験用のカリキュラムも無料で配布いたします。（1週間限定）
