0. 『わくわく♪ でんこの職業体験！』
2024/5/8から開催されている駅メモのイベント『わくわく♪ でんこの職業体験！』は、アクセスによって“通貨”を集めて"軽食やお土産"と交換、手に入れた"軽食やお土産"の合計ポイントで報酬をゲットできるイベントである。
かつての「お腹も心もいっぱい♪秋のどきどきキャンプ！」や「星巡りの夜〜美子さん座を取り戻せ！〜」のイベント同様、このイベントは線形計画問題（最適化問題）であり、線形計画法で解くことにより報酬を最大化できる。
今回、Google ColaboratoryとPuLP（Pythonのライブラリー）で最適解を見つけることができると分かったので実践してみた。
なお、Qiitaで調べたところ、過去に同様のことをした先人がいた。
gg_hatano様 - 駅メモイベントで最適化
当該記事内のリンクページも参考にしながら、本記事を執筆する。
【Python】PuLPで線型計画法に入門する
1. 線型計画法とは
ある制約下で目的とする関数を最適化（最小もしくは最大）する変数の値を求める方法を数理計画法といい、そのうち制約条件や目的関数が線形の方程式で示されるものを線形計画法という。
今回の駅メモイベを、問題文として書き表すと下記のようになる。
問題）
９種類の"通貨"がある。
"通貨"を組み合わせて、５種類の“軽食”または“お土産”と交換できる。
５種類の“軽食”または“お土産”それぞれにポイント（価値）がある。
"通貨"と交換で入手した“軽食/お土産”の合計ポイントを最大化するための"通貨"の交換方法を見つけよ。
● "通貨"（イベント進捗により所持数は変化）
・銅貨：398枚
・銀貨：392枚
・金貨：88枚
・山盛りの紙幣：45個
・山盛りのコイン：47個
・山盛りの紙幣とコイン：27個
・青の紙幣：48枚
・赤の紙幣：58枚
・緑の紙幣：57枚
● "軽食""お土産"の価値と交換方法
・お菓子 ：価値=50pt, 必要通貨→銅貨/銀貨
・デザート ：価値=200pt, 必要通貨→銅貨/銀貨/山盛りのコイン
・お弁当 ：価値=300pt, 必要通貨→銅貨/金貨/青の紙幣
・まんじゅう：価値=700pt, 必要通貨→銀貨/山盛りの紙幣/山盛りのコイン/赤の紙幣
・ペナント ：価値=900pt, 必要通貨→銅貨/金貨/山盛りの紙幣とコイン/青の紙幣/赤の紙幣
2. 定式化
今回のイベントの場合、目的関数（合計ポイントを求める式）はお菓子の個数をx1，デザートの個数をx2，お弁当の個数をx3、としたまんじゅうの個数をx4、ペナントの個数をx5とした場合，以下の通りになる：
【目的関数】
50 \times x_1 + 200\times x_2 + 300\times x_3 + 700\times x_4 + 900\times x_5
また制約条件（満たさなければならない条件）は以下の通りになる：
【制約条件】
\begin{align}
銅貨の枚数制約&： x_1 + x_2 + x_3 + x_5 \leq 398 \\
銀貨の枚数制約&： x_1 + x_2 +x_4 \leq 392 \\
金貨の枚数制約&： x_3 + x_5 \leq 88 \\
山盛りの紙幣の個数制約&： x_4 \leq 45 \\
山盛りのコインの個数制約&： x_2 + x_4 \leq 47 \\
山盛りの紙幣とコインの個数制約&： x_5 \leq 27 \\
青の紙幣の枚数制約&： x_3 + x_5 \leq 48 \\
赤の紙幣の枚数制約&： x_4 \leq 58 \\
緑の紙幣の枚数制約&： x_5 \leq 57
\end{align}
$$ (注) イベント進捗によりアイテム数 (＝制約条件式の右辺) は変化する $$
これらの制約条件をすべて満たした上で，目的関数が最大になる$$ x_1,x_2,x_3,x_4,x_5 $$ の組み合わせを算出すれば良い。
3. Pythonに実装
ここまで記述してきた線形計画法をPuLPに記述すると下記の通りとなる。
pip install pulp
import pulp
# 問題の定義
prob = pulp.LpProblem("Sample Problem", pulp.LpMaximize)
# 変数の定義
x1 = pulp.LpVariable('x1', lowBound=0)
x2 = pulp.LpVariable('x2', lowBound=0)
x3 = pulp.LpVariable('x3', lowBound=0)
x4 = pulp.LpVariable('x4', lowBound=0)
x5 = pulp.LpVariable('x5', lowBound=0)
# 目的関数の設定
prob += 50*x1 + 200*x2 + 300*x3 + 700*x4 + 900*x5, "Objective Function"
# 制約条件の設定
prob += x1 + x2 + x3 + x5 <= 398, "Constraint 1" #銅貨
prob += x1 + x2 +x4 <= 392, "Constraint 2" #銀貨
prob += x3 + x5 <= 88, "Constraint 3" #金貨
prob += x4 <= 45, "Constraint 4" #山盛りの紙幣
prob += x2 + x4 <= 47, "Constraint 5" #山盛りのコイン
prob += x5 <= 27, "Constraint 6" #山盛りの紙幣とコイン
prob += x3 + x5 <= 48, "Constraint 7" #青の紙幣
prob += x4 <= 58, "Constraint 8" #赤の紙幣
prob += x5 <= 57, "Constraint 9" #緑の紙幣
# 問題の解決
prob.solve()
# 結果の表示
print("Status:", pulp.LpStatus[prob.status])
print("x1 =", pulp.value(x1))
print("x2 =", pulp.value(x2))
print("x3 =", pulp.value(x3))
print("x4 =", pulp.value(x4))
print("x5 =", pulp.value(x5))
print("Objective value =", pulp.value(prob.objective))
上記のスクリプトをGoogle Colaboratoryで実行すれば、下記の解を得られる。
Status: Optimal
x1 = 345.0
x2 = 2.0
x3 = 21.0
x4 = 45.0
x5 = 27.0
Objective value = 79750.0
最後の $79750$ が目的関数に最適な $ x_1,x_2,x_3,x_4,x_5 $ の組み合わせを代入した時の値。$79750$ $pt$ ということで、バージョンアップチップの入手が可能なレベルまでアイテムを集められているということが分かった。
現在イベントを進行中で、報酬を最大化したい方や、目標とする報酬のために不足するアイテムを確認したい方などは是非上記のスクリプトを実装して今回の駅メモイベントを攻略してほしい。
【完】