まえがき
太郎さんは八百屋に行きました。
そこでは
Aセット:みかん4個とりんご1個で400円、
Bセット:みかん2個とりんご3個で500円
の二種類のセット販売がありました。
太郎さんはお母さんに「たくさん買ってきてね」と言われていました。
可能な限りお金を使う買い方を考えましょう。
ただし八百屋さんの在庫にはみかん100個、りんご70個しかありません。
数式にしてみましょう
これは線形計画問題と言われる問題です。
Aセットをx個、
Bセットをy個買うとします。
最大化したい関数は値段なので、
$$ 400 x + 500 y $$
という式になります。
さらにみかん100個、りんご70個という在庫の制約があるため
4x + 2y \leq 100 \\
x + 3y \leq 70
が条件に加わります。
ついでに$x,y \geq 0$も条件。
まとめてこう書きます。
\mathrm{Maximize}~~~400 x + 500 y\\
\mathrm{Subject~to} ~~~ 4x + 2y \geq 100\\
~~~~~~~~~~~~~~~~~~x + 3 y \geq 70\\
~~~~~~~x \leq 0 \\
~~~~~~~y \leq 0
(整数じゃなきゃダメじゃね？みたいなツッコミは禁止とします。)
Pythonで解いてみよう
scipy.optimize.linprogという関数を利用します。
以下の形を標準形とします。
\mathrm{Minimize}~~~c^Tx\\
\mathrm{Subject~to} ~~~ Gx \geq h\\
~~~~~~~~~~~~~~~~~~Ax = b\\
$c,G,h,A,b$の5つを引数に設定できます。これは最小化の関数ということに注意。
問題の式を一般形に当てはめると
\mathrm{Minimize}~~~ \left(
\begin{array}{ccc}
-400 \\
-500
\end{array}
\right)^T
\left(
\begin{array}{ccc}
x \\
y
\end{array}
\right)\\
\mathrm{Subject~to} ~~~ \left(
\begin{array}{ccc}
4 & 2 \\
1 & 3 \\
-1 & 0\\
0 & -1
\end{array}
\right)
\left(
\begin{array}{ccc}
x \\
y
\end{array}
\right)\leq
\left(
\begin{array}{ccc}
100 \\
70 \\
0\\
0
\end{array}
\right)
「最小化」の関数にするために、値段をひっくり返してます。
ここから
c = \left(
\begin{array}{ccc}
-400 \\
-500
\end{array}
\right),G = \left(
\begin{array}{ccc}
4 & 2 \\
1 & 3 \\
-1 & 0\\
0 & -1
\end{array}
\right) ,h = \left(
\begin{array}{ccc}
100 \\
70 \\
0\\
0
\end{array}
\right)
この三つの引数を入れて関数を使ってみましょう。
import numpy as np # npという名前でimportする慣習。
from scipy import optimize
c = np.array([-400,-500])
G = np.array([[4,2],[1,3],[-1,0],[0,-1]])
h = np.array([[100,70, 0, 0]])
sol = optimize.linprog(c, G, h)
print(sol.x)
print(sol.fun)
# [16. 18.]
# -15400.0
つまりAセットを16個、Bセットを18個買って15400円。
これが最大となります。
まとめ
数理最適化問題は、関数に一般化して入れればいい。
線形計画問題を解くための関数は色々あるらしいですが、その一例を示しました。
この関数だって上限下限の設定とかデータ型とかもうちょっと行儀のいい書き方あるけど無視。
『機械学習のエッセンス』という本を参考にしました。
この本についてまとめていきます。
前回:数値範囲に気をつけよう:
https://qiita.com/NNNiNiNNN/items/2f17f874f8a234bd10ad
次回:最小二乗法 $y = ax$型
https://qiita.com/NNNiNiNNN/items/4fd5367f9ead6e5905a9