指定の金額に対してどの硬貨を何枚出すのかを、LP問題として、PuLPを用いて求めてみる

指定の金額に対してどの硬貨を何枚出すのか(小学生用の計算ドリルに載っていそうな問題)を、LP問題として、PythonライブラリPuLPを用いて求めてみました。

PuLP

PuLP: Pythonで線形最適化を行うライブラリ。
使用方法は、以下が詳しい。
https://docs.pyq.jp/python/math_opt/pulp.html

導入・バージョン確認・import

インストールは、Windowsのコマンドプロンプトを用いて、DOSコマンドでインストールする場合、

python.exe -m pip install pulp

Jupyter内でインストールする場合は、

pip install pulp

確認すると、

pip show pulp

Name: PuLP
Version: 2.3
Summary: PuLP is an LP modeler written in python. PuLP can generate MPS or LP files and call GLPK, COIN CLP/CBC, CPLEX, and GUROBI to solve linear problems.
Home-page: https://github.com/coin-or/pulp
Author: J.S. Roy and S.A. Mitchell
Author-email: [e-mail]
License: UNKNOWN
Location: D:\wpy64-3950\python-3.9.5.amd64\lib\site-packages
Requires: amply
Required-by: 
Note: you may need to restart the kernel to use updated packages.

インポートは、

import pulp

例題を用意

指定の金額に応じて、どの硬貨を何枚出すのかを求める問題を考える。1円玉が5枚、5円玉が4枚、10円玉が3枚、50円玉が2枚あるとして、金額、例えば73円を出す場合、

• 出す硬貨の枚数を最小にする場合 (→最も硬貨を出す手作業を軽減する場合)
• 出す硬貨の枚数を最大にする場合 (→最も財布の中の硬貨を減らす場合)

において、どの硬貨を何枚出すのか、以降で求める。

出す硬貨の数を最小にしたい場合

money = 73 # 金額

LP = pulp.LpProblem(sense=pulp.LpMinimize)
yen1 = pulp.LpVariable("1円玉", 0, 5, cat=pulp.LpInteger)
yen5 = pulp.LpVariable("5円玉", 0, 4, cat=pulp.LpInteger)
yen10 = pulp.LpVariable("10円玉", 0, 3, cat=pulp.LpInteger)
yen50 = pulp.LpVariable("50円玉", 0, 2, cat=pulp.LpInteger)
LP += 1*yen1 + 5*yen5 + 10*yen10 + 50*yen50 == money
LP += pulp.lpSum([yen1, yen5, yen10, yen50]) # 合計枚数最小

LP.solve()
print("求解の結果:", pulp.LpStatus[LP.status])

求解の結果: Optimal

print(f"""金額{money}円には、
  1円玉{pulp.value(yen1):.0f}枚、5円玉{pulp.value(yen5):.0f}枚、
  10円玉{pulp.value(yen10):.0f}枚、50円玉{pulp.value(yen50):.0f}枚""")

金額73円には、
  1円玉3枚、5円玉0枚、
  10円玉2枚、50円玉1枚

出す硬貨の数を最大にしたい場合

money = 73 # 金額

LP = pulp.LpProblem(sense=pulp.LpMaximize)
yen1 = pulp.LpVariable("1円玉", 0, 5, cat=pulp.LpInteger)
yen5 = pulp.LpVariable("5円玉", 0, 4, cat=pulp.LpInteger)
yen10 = pulp.LpVariable("10円玉", 0, 3, cat=pulp.LpInteger)
yen50 = pulp.LpVariable("50円玉", 0, 2, cat=pulp.LpInteger)
LP += 1*yen1 + 5*yen5 + 10*yen10 + 50*yen50 == money
LP += pulp.lpSum([yen1, yen5, yen10, yen50]) # 合計枚数最大

LP.solve()
print("求解の結果:", pulp.LpStatus[LP.status])

求解の結果: Optimal

print(f"""金額{money}円には、
  1円玉{pulp.value(yen1):.0f}枚、5円玉{pulp.value(yen5):.0f}枚、
  10円玉{pulp.value(yen10):.0f}枚、50円玉{pulp.value(yen50):.0f}枚""")

金額73円には、
  1円玉3枚、5円玉4枚、
  10円玉0枚、50円玉1枚

得られた結果

金額73円は、

• 1円玉3枚、5円玉0枚、10円玉2枚、50円玉1枚、の最小6枚で作ることが出来、また、
• 1円玉3枚、5円玉4枚、10円玉0枚、50円玉1枚、の最大8枚で作ることが出来る。

手持ちの硬貨の枚数を倍にした場合

1円玉が5枚、5円玉が4枚、10円玉が3枚、50円玉が2枚あったものから、
1円玉が10枚、5円玉が8枚、10円玉が6枚、50円玉が4枚に条件を変えて、再度、以降で求めてみる。

出す硬貨の数を最小にしたい場合

money = 73 # 金額

LP = pulp.LpProblem(sense=pulp.LpMinimize)
yen1 = pulp.LpVariable("1円玉", 0, 10, cat=pulp.LpInteger)
yen5 = pulp.LpVariable("5円玉", 0, 8, cat=pulp.LpInteger)
yen10 = pulp.LpVariable("10円玉", 0, 6, cat=pulp.LpInteger)
yen50 = pulp.LpVariable("50円玉", 0, 4, cat=pulp.LpInteger)
LP += 1*yen1 + 5*yen5 + 10*yen10 + 50*yen50 == money
LP += pulp.lpSum([yen1, yen5, yen10, yen50]) # 合計枚数最小

LP.solve()
print("求解の結果:", pulp.LpStatus[LP.status])

求解の結果: Optimal

print(f"""金額{money}円には、
  1円玉{pulp.value(yen1):.0f}枚、5円玉{pulp.value(yen5):.0f}枚、
  10円玉{pulp.value(yen10):.0f}枚、50円玉{pulp.value(yen50):.0f}枚""")

金額73円には、
  1円玉3枚、5円玉0枚、
  10円玉2枚、50円玉1枚

同じ結果となる。

出す硬貨の数を最大にしたい場合

money = 73 # 金額

LP = pulp.LpProblem(sense=pulp.LpMaximize)
yen1 = pulp.LpVariable("1円玉", 0, 10, cat=pulp.LpInteger)
yen5 = pulp.LpVariable("5円玉", 0, 8, cat=pulp.LpInteger)
yen10 = pulp.LpVariable("10円玉", 0, 6, cat=pulp.LpInteger)
yen50 = pulp.LpVariable("50円玉", 0, 4, cat=pulp.LpInteger)
LP += 1*yen1 + 5*yen5 + 10*yen10 + 50*yen50 == money
LP += pulp.lpSum([yen1, yen5, yen10, yen50]) # 合計枚数最大

LP.solve()
print("求解の結果:", pulp.LpStatus[LP.status])

求解の結果: Optimal

print(f"""金額{money}円には、
  1円玉{pulp.value(yen1):.0f}枚、5円玉{pulp.value(yen5):.0f}枚、
  10円玉{pulp.value(yen10):.0f}枚、50円玉{pulp.value(yen50):.0f}枚""")

金額73円には、
  1円玉8枚、5円玉7枚、
  10円玉3枚、50円玉0枚

枚数がかなり増加する。

得られた結果

(1円玉が10枚、5円玉が8枚、10円玉が6枚、50円玉が4枚の場合)、金額73円は、

• 1円玉3枚、5円玉0枚、10円玉2枚、50円玉1枚、の最小6枚で作ることが出来、また、
• 1円玉8枚、5円玉7枚、10円玉3枚、50円玉0枚、の最大18枚で作ることが出来る。

(小学生の頃、変数の数が数個で＆条件式は1つだけですが、簡単なLP問題を、皆解いていたということか... いや違うか... 単にスケール可能な問題としてコンピュータで解く場合はこうなりますということか。)