みなさん、こんにちはこんばんは。S.Kと申します。
今回からNEXTシリーズの線形計画問題編をご紹介していきます。
最適化問題はあらゆる分野で使われてるわけですが、その中で線形計画問題に焦点を当てて解説していくシリーズになります。

なぜ、この線形計画問題について取り上げたかの理由ですが、コアの存在証明ところで線形計画問題の知識が必要な箇所がありまして、これをきっかけ入門レベルのことを話せればいいなと思った次第です。

また大事な大事な双対定理の話がしたかったんです。
すでにアップロード済みの動画第2回でしてます。

ちなみに私自身は大学の頃の専門の一つがOR（オペレーションズリサーチ）で、この手の話は現実に応用されてます。そのため、馴染み深く、数学と社会の橋渡ししてる感じでとても面白いと思います。その面白さが伝わればいいなぁ、と思います。

参考文献

まずは参考文献のご紹介から。タイトルの通り、これならわかります。

最近手で計算するのが面倒なので、最適化問題はPythonに解かせてます。
ただ、初回は手計算しましたけどね。PuLPという線形計画問題向けのライブラリがあります。

動画とスライド

では、まずは動画やスライドをご覧ください。

ニコニコ動画：

Youtube

スライドシェア

Pythonで実装（コード例とおまけの可視化）

上記スライド内の問題

これについて、動画はまだ作成できてませんが、PuLPを使って計算させてみました。
コード例：pulp使ってます。

from pulp import LpVariable, LpProblem, LpMaximize, LpMinimize, value
from fractions import Fraction
import numpy as np

#Primary problem
problem_0=LpProblem('Primary problem', LpMaximize)

x = LpVariable.dicts('x', ([0,1]), None, None,'Continuous') #変数名prefix, リスト, 最小値, 最大値, 連続
problem_0 += 10000*x[0]+20000*x[1]
problem_0 += 3*x[0]+2*x[1]<=18
problem_0 += 2*x[0]+8*x[1]<=52
problem_0 += x[0]>=0
problem_0 += x[1]>=0

print(problem_0)

status = problem_0.solve()
print(Fraction(x[0].value()).limit_denominator(10))
print(Fraction(x[1].value()).limit_denominator(10))
print(value(problem_0.objective))

結果：

Primary problem:
MAXIMIZE
10000*x_0 + 20000*x_1 + 0
SUBJECT TO
_C1: 3 x_0 + 2 x_1 <= 18

_C2: 2 x_0 + 8 x_1 <= 52

_C3: x_0 >= 0

_C4: x_1 >= 0

VARIABLES
x_0 free Continuous
x_1 free Continuous

2
6
140000.0

ちゃんと最適解が(2, 6)になってることが確認できます。最適値は140000。

おまけ：

別のライブラリで可視化してみてます。可視化した方がわかりやすいですからね。人に見せるときになんかできてる！ってインパクトを与えられます笑
赤線が目的関数、緑線、青線が制約条件式に該当します。(2, 6)のとこで接してるのかな・・・もう少しわかりやすくしますかね。今後の課題。

終わりに

いかがでしたでしょうか。まだまだ勉強中のPythonです。これからにご期待ください。しかしながら、このシリーズは終わりが見えてないです。コア編は4回くらいで終わるかなと思ってて、ちょうど4回で完結しましたが、こちらはわかリマセン。ですが、お付き合いいただければと思います。★別シリーズが始まりますけどね〜★

次回は双対問題も同じように実装して結果を眺めてみます。
では、また次回お会いしましょう。