こんにちは、代表のみでっとです！
今回は線形計画問題（語句の説明は後程）に対して、どのようにPythonでアプローチして解いていくかについて、具体例を交えながら説明していきます。
本記事では、もうすぐハロウィンということでハロウィンにちなんだ例題を考えてみました！
なお、今回は分かりやすさを重視した初級編なのでプログラミングしなくても簡単に解けちゃいますが、その点はご了承ください（現在、上級編を執筆中です）。
それでは、早速今日も勉強を進めていきましょう！
線形計画問題とは？
線形計画問題というのは、読んで字のごとく、線形的（1次元、グラフにしたときに直線が描ける、例えばy=ax+C）ないくつかの条件で書き表された最適化問題のことです(入門記事であるため、詳細な数式は省きます)。
…。
これだけだといまいちピンと来ませんね(笑)
そこで、今回は以下の問題を例にとって学習を進めていきます！
ー問題ー
あなたは地元のケーキ屋さんの店員です。
季節に合わせたケーキは売上が伸びるので、もうすぐ迎えるハロウィン🎃に向けて新しいケーキを2種類作る担当になりました。
そこで、あなたはハロウィン限定のレシピとして2種類のレシピを考えました。それぞれ1個作るのに必要な原材料、販売価格は以下の通りです。
かぼちゃのムース：かぼちゃ 100 g、生クリーム 60ｇ、300円
パンプキンプリン：かぼちゃ 40 g、生クリーム 80g、400円
現在の在庫：かぼちゃ、生クリームそれぞれ2 kg(2000 g)
作ったケーキは全て売れると仮定したとき、 総売り上げを最大にするにはそれぞれ何個作ればよいでしょうか。
ーーーーー
これが今回取り組んでいく問題です。
アメリカに住んでいたときはハロウィンにはかぼちゃを買ってきて中身をスプーンで取り出して被り物を作って遊んでいて印象深かったので、かぼちゃのケーキを作ることにしてみました(笑)
それでは早速解いていきましょう！
制約条件の立式
まず初めに、簡単に今回の問題を整理してみましょう。
最終的に何がしたいのか？ → 総売り上げを最大にしたい！
じゃあ総売り上げを最大にするには？ → 作るべきケーキの個数が知りたい！
ということで、まず初めに求めたいパラメータ（今回はケーキの個数）を文字で置きかえてみます。
x：かぼちゃのムースの個数、y：パンプキンプリンの個数
次に、このxとyが満たさなければならない制約条件を文章中から読み取ります。今回の場合、以下の2式が立式できますね。
100x + 60y <= 2000
40x + 80y <= 2000
また、当たり前ですが作るケーキの個数は負の値にはならないので、以下の式も立てられます。
x >= 0, y >= 0
これらの制約条件を満たしながら、総売り上げが最大になるxとyを求めていくことになります♪
目的関数の立式
目的関数とは、線形計画問題を解いた結果最大化、もしくは最小化したい関数の事を指します。
今回の場合は総売り上げを最大化したいので、目的関数は以下のようになりますね。（よくわからなかった場合は、もう一度問題に戻って考えてみて下さい！）
f(x,y)=300x + 400y
今回用いる式
まとめると、以下が今回解きたい線形計画問題の式になります。
100x + 60y <= 2000
40x + 80y <= 2000
x >= 0, y >= 0
f(x,y)=300x + 400y
ここで式の形に注目してもらいたいのですが、上記の式はグラフにしたときに直線が描けることに気づきましたか？
冒頭で述べたように、このように線形的な条件式で表され、ある値を最適化していく問題のことを線形計画問題と呼びます。
覚えておきましょう！
解法
使用するライブラリ
今回は、線形計画問題を解くにあたってpulpと呼ばれているライブラリを用います！
pulpは線形計画問題を解くためのライブラリで、数多くの文献がネットにあるので、詳しく知りたい方はそちらを参考にしてみて下さい。
GitHub上で公開されているコードはこちら
※GoogleColaboratory上で実装を行いました。Google Colaboratoryって何？という方は、以下の記事も合わせて学習してみて下さい！
いつも通り、pip install～コマンドを用いてまずはパッケージのインストールを行いましょう。
pip install pulp続いて、使用するライブラリのインポートを行います。
import pulp実装例
初めに、作成したコードを掲載します。
import pulp
#線形計画問題オブジェクトの作成(今回は総売り上げを最大にすることが目的)
problem = pulp.LpProblem("Halloween", pulp.LpMaximize)
#変数の定義
mousse = pulp.LpVariable("mousse", 0, 50, "Integer")
pudding = pulp.LpVariable("pudding", 0, 50, "Integer")
#目的関数の定義
problem += 300 * mousse + 400* pudding
#制約条件の定義
problem += 90 * mousse + 60 * pudding <= 2000
problem += 40 * mousse + 80 * pudding <= 2000
#線形計画問題を解く
status = problem.solve()
print(pulp.LpStatus[status])
print(problem)
#結果の表示、出力
print("-"*5 + "結果" + "-"*5)
print("かぼちゃのムースの個数:",int(mousse.value()))
print("パンプキンプリンの個数:",int(pudding.value()))
print("-"*14)また、出力結果は以下のようになりました。
Optimal
Halloween:
MAXIMIZE
300*mousse + 400*pudding + 0
SUBJECT TO
_C1: 90 mousse + 60 pudding <= 2000
_C2: 40 mousse + 80 pudding <= 2000
VARIABLES
0 <= mousse <= 50 Integer
0 <= pudding <= 50 Integer
-----結果-----
かぼちゃのムースの個数: 8
パンプキンプリンの個数: 21
--------------Pythonに解いてもらったところ、かぼちゃのムースは8個、パンプキンプリンは21個つくれば売り上げが最大になることが分かりました！
パンプキンプリンは400円という強気の値段設定をしたことが大きく効いていそうです(笑)
実際には全部売れるかどうかは分からないので、もっと制約条件を追加していくことも出来ますが、今回は簡単にということでこれが最適解ということになります。
それでは、コードの解説をしていきます！
コードの詳細な解説
#線形計画問題オブジェクトの作成(今回は総売り上げを最大にすることが目的)
problem = pulp.LpProblem("Halloween", pulp.LpMaximize)まず初めに、解きたい線形計画問題の大枠となるオブジェクトを作成します。
ここで、2つ目の引数は目的関数を最大化したい場合にはpulp.LpMaximize、最小化したい場合にはpulp.LpMinimizeを使用します。
場面によって使い分けましょう。
#変数の定義
mousse = pulp.LpVariable("mousse", 0, 50, "Integer")
pudding = pulp.LpVariable("pudding", 0, 50, "Integer") 続いて、変数の定義を行います。
ここでは、mousse（ムース）と、pudding（プリン）の2つの最適化したい変数を定義しました。引数には、順番に以下の情報を入力してください。
pulp.LpVariable(変数の名前, 変数の最小値, 変数の最大値, データの種類)
なお、データの種類はケーキの個数が小数点になることはないので“Integer”を選択しましたが、他に2値変数（0と1）の“Binary”、float型の連続変数の“Continuous”が設定できます。
#目的関数の定義
problem += 300 * mousse + 400* pudding続いて、目的関数の定義を行います。
目的関数や制約条件を追加していきたい場合、作成したオブジェクトに+=するだけで追加できてしまいます。
とても便利ですし、直感的で分かりやすい…！
今回は総売り上げを最大化したかったので、総売り上げを表す式を記述しました。
#制約条件の定義
problem += 90 * mousse + 60 * pudding <= 2000
problem += 40 * mousse + 80 * pudding <= 2000
目的関数と同様、制約条件も定義します。
なお、制約条件を表すときには、
==(左右の数式が等しい)
>=(左の数式の方が大きいか等しい)
<=(右の数式の方が大きいか等しい)
しか使えないので、注意しましょう。
#線形計画問題を解く
status = problem.solve()
print(pulp.LpStatus[status])
print(problem)定義が終わったら、problem.solve()を実行し、線形計画問題を解きます。
print(pulp.LpStatus[status])を実行し、“Optimal”と表示されれば問題なく問題が解けた証明になります。忘れずに実行するようにしましょう。
その後、print(problem)で解いた問題の全体を確認することが出来ます。きちんと設定した制約条件や目的関数が表示されていることを確認しておきましょう。
#結果の表示、出力
print("-"*5 + "結果" + "-"*5)
print("かぼちゃのムースの個数:",int(mousse.value()))
print("パンプキンプリンの個数:",int(pudding.value()))
print("-"*14)
最後に結果の出力を行っています。変数.value()でfloat型の値の出力ができますが、今回は整数個のケーキの個数を出力したかったのでint()で整数型に変換を行いました。（8.0 → 8）
まとめ
いかがだったでしょうか？
比較的短いコードで記述出来ていて、かつ、数式を解けるpulpの有能さ。利用方法と、線形計画問題について理解を深めていただけていればよかったなと思います！
次回は上級編ということで、今や懐かしいセンター試験で高得点を取るための勉強計画を、様々な制約条件を加味しながら立案していこうと思っています。
そちらもよろしければご覧になってください！
それではまた次の記事でお会いしましょう！
ここまで読んでくださりありがとうございました～！
みでっと
P.S. 最近はメンバー全員が講義や研究活動で忙しく、投稿頻度が落ちてしまっていてすみません💦
無理のない範囲で、今後もプログラミング初心者向けの記事の投稿を続けていくので、勉強のお供としてご覧いただければ幸いです！