ヤマザキ 春の最適化まつり

「ヤマザキ　春のパンまつり」では、各パンに点数がついていて合計点数が28点を超えるとお皿を１枚もらえる、ということになっている。

 こうなると最適化の視点では当然のことながら「１枚もらえる最小金額がいくらだろうか ？」というのが気になってくる。

そこでサクッとJuliaで最適化を行ってみた。

[1] まずはデータが必要ということで

https://gameboku.com/archives/21020003.html

に纏めてくれてあるデータを使わせてもらうことにして

 【表1】全対象商品（338品） 点数・カロリー効率一覧

の表部分をExcel にコピー＆ペーストして UTF-8 の CSV として保存する。ファイル名については、今回はあまり深く考えずに Book1.csvとしておいた。

[2] 以下の Julia コードを実行する。

==========================

using CSV
using DataFrames
using JuMP
using GLPK
using LinearAlgebra

df = CSV.File("Book1.csv", header=true, delim=',') |> DataFrame

point = df.得点
price = df.価格
name = df.商品名
n = length(price)

model = Model()
set_optimizer(model, GLPK.Optimizer)
@variable(model, x[1:n]>=0, Int) # 商品は整数個
@constraint(model, dot(point, x) >= 28)  # 合計28点以上
@objective(model, Min, dot(price, x)) # 合計金額を最小化

optimize!(model)

x_value = Int.(value.(x)) # 最適解を得る
optimal_value = Int(objective_value(model)) # 最適値を得る

nz_index = findall(x_value .!= 0) # 0 個になっていないところのみを抜粋

println("--最適合計金額 = $(optimal_value)円")
println("--最適解--")
for index in nz_index
    print("$(name[index])")
    print("[$(point[index])ポイント, $(price[index])円]を")
    print("$(x_value[index])個購入する")
    println()
end

==========================

 [3] 結果を見る

プログラムにバグとかがなければ、これで求めることができる。

Julia を使うのが面倒であれば、Excel のソルバーを使っても同様に求めることができる。

ちなみに、点数が0.5,1.0,1.5,2.0,2.5と0.5点刻みとシンプルなので、最適解も結構シンプルな組合せになるようだ。