ExcelとPythonのソルバーを使っての線形最適化問題演習ー3 支払い枚数最小化

『http://mt-soft.sakura.ne.jp/kyozai/excel_mid/160_simulation/25_solver_2/index.html』サイトに載っている問題を参考に、
ExcelとPythonのソルバーを使って問題を解いてみる。


(問題)
123,456円支払いがある
現在
 一万円札 が 10枚、 五千円札 が 1枚、 千円札 が 2枚、 五百円玉 が 200個、 百円玉 が 200個、
 五十円玉 が 500個、 十円玉 が 500個、 五円玉 が 1000個、 一円玉 が 1000個
持っている。

支払い数の合計を最小にするには、それぞれ何個づつ支払らえればよいか?

まず、Excel のソルバーで解く
問題を表にまとめると以下のようになる


各セルに設定された式を表示


ソルバーを使えるようにする。(「ファイル」-「オプション」-「アドオン」-「ソルバーアドオン」をアクティブにする)
「データ」-「ソルバー」をクリックして、下記のように設定する


上記のように設定後、「解決」をクリックする


(解)
   一万円札 10枚、 五千円札 1枚、 千円札 2枚、 五百円玉 32個、 百円玉 4個、 五十円玉 1個、 五円玉 1個、 一円玉 1個
   支払い数の合計は 52 となる

次に、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のソルバーと同じ結果を得る

コメントを残す

メールアドレスが公開されることはありません。