ExcelとPythonのソルバーを使っての線形最適化問題演習ー３ 支払い枚数最小化
『http://mt-soft.sakura.ne.jp/kyozai/excel_mid/160_simulation/25_solver_2/index.html』サイトに載っている問題を参考に、
ExcelとPythonのソルバーを使って問題を解いてみる。
（問題）
１２３，４５６円支払いがある
現在
一万円札 が １０枚、 五千円札 が １枚、 千円札 が ２枚、 五百円玉 が ２００個、 百円玉 が ２００個、
五十円玉 が ５００個、 十円玉 が ５００個、 五円玉 が １０００個、 一円玉 が １０００個
持っている。
支払い数の合計を最小にするには、それぞれ何個づつ支払らえればよいか？
まず、Excel のソルバーで解く
問題を表にまとめると以下のようになる
各セルに設定された式を表示
ソルバーを使えるようにする。（「ファイル」－「オプション」－「アドオン」－「ソルバーアドオン」をアクティブにする）
「データ」－「ソルバー」をクリックして、下記のように設定する
上記のように設定後、「解決」をクリックする
（解）
一万円札 １０枚、 五千円札 １枚、 千円札 ２枚、 五百円玉 ３２個、 百円玉 ４個、 五十円玉 １個、 五円玉 １個、 一円玉 １個
支払い数の合計は ５２ となる
次に、Python のソルバーで解を求める
ソルバーを使えるモジュール Pulp をインポートする（まだのときは、pip install pulp でインストールする）
jupyter notebook 上で作成する
# Python上で数理最適化問題を簡単にコーディングできるモデリングAPI、モデリング言語 pulp をインポート
import pulp
lp = pulp.LpProblem('lp-test3', pulp.LpMinimize)
# それぞれの手持ち数の設定
x10000 = pulp.LpVariable('x10000', 0, 10, 'Integer')
x5000 = pulp.LpVariable('x5000', 0, 1, 'Integer')
x1000 = pulp.LpVariable('x1000', 0, 2, 'Integer')
x500 = pulp.LpVariable('x500', 0, 200, 'Integer')
x100 = pulp.LpVariable('x100', 0, 200, 'Integer')
x50 = pulp.LpVariable('x50', 0, 500, 'Integer')
x10 = pulp.LpVariable('x10', 0, 500, 'Integer')
x5 = pulp.LpVariable('x5', 0, 1000, 'Integer')
x1 = pulp.LpVariable('x1', 0, 1000, 'Integer')
# 評価関数の設定
lp += x10000 + x5000 + x1000 + x500 + x100 + x50 + x10 + x5 + x1
# 制約条件の設定
lp += 10000 * x10000 + 5000 * x5000 + 1000 * x1000 + 500 * x500 + 100 * x100 + 50 * x50 + 10 * x10 + 5 * x5 + 1 * x1 == 123456
# 最適化問題の確認
print(lp)
# 求解
lp.solve()
sums = x10000.value() + x5000.value() + x1000.value() + x500.value() + x100.value() + x50.value() + x10.value() + x5.value() + x1.value()
sumen = 10000 * x10000.value() + 5000 * x5000.value() + 1000 * x1000.value() + 500 * x500.value() + 100 * x100.value() + 50 * x50.value() + 10 * x10.value() + 5 * x5.value() + 1 * x1.value()
# 結果
print('一万円札：%d 枚' % x10000.value())
print('五千円札：%d 枚' % x5000.value())
print('千円札：%d 枚' % x1000.value())
print('五百円玉：%d 個' % x500.value())
print('百円玉：%d 個' % x100.value())
print('五十円玉：%d 個' % x50.value())
print('十円玉：%d 個' % x10.value())
print('五円玉：%d 個' % x5.value())
print('一円玉：%d 個' % x1.value())
print('支払い数合計：%d 個' % sums)
print('')
print('支払い金額：{:,.0f} 円'.format(sumen))
「Shift」＋「Enter」で実行すると
lp-test3:
MINIMIZE
1*x1 + 1*x10 + 1*x100 + 1*x1000 + 1*x10000 + 1*x5 + 1*x50 + 1*x500 + 1*x5000 + 0
SUBJECT TO
_C1: x1 + 10 x10 + 100 x100 + 1000 x1000 + 10000 x10000 + 5 x5 + 50 x50
+ 500 x500 + 5000 x5000 = 123456
VARIABLES
0 <= x1 <= 1000 Integer
0 <= x10 <= 500 Integer
0 <= x100 <= 200 Integer
0 <= x1000 <= 2 Integer
0 <= x10000 <= 10 Integer
0 <= x5 <= 1000 Integer
0 <= x50 <= 500 Integer
0 <= x500 <= 200 Integer
0 <= x5000 <= 1 Integer
一万円札：10 枚
五千円札：1 枚
千円札：2 枚
五百円玉：32 個
百円玉：4 個
五十円玉：1 個
十円玉：0 個
五円玉：1 個
一円玉：1 個
支払い数合計：52 個
支払い金額：123,456 円
となり、Excelのソルバーと同じ結果を得る
