久しぶりの「勝手に回答」シリーズ。今回はTeratailの 複数の制約があるなかでの価値最大化。(ナップサック問題応用) です。
質問では「Pythonで」ということでしたがPythonはよく分からないので， 自分のためのJuliaのJuMPの勉強としてJulia言語で実装してみます。
幸いにしてJuMPのサイトにはナップサック問題の例があるので， これに対してうんうん悩みながら条件を追加していきます。
実装例は次のような感じです。 もうちょっと簡単にできるのかもしれないですけど， あまりコーディング能力がない自分が初めて書いたにしては上出来かなと思います。
using JuMP, HiGHS 価格 = Float64[5, 6, 12, 3, 4, 4, 5, 6, 5, 6, 10] # 円 体積 = Float64[2, 2, 9, 2, 5, 4, 3, 7, 2, 4, 8] # リットル 可黄袋 = Float64[0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1] # 黄&白のボールが可能 可青袋 = Float64[0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1] # 青&白のボールが可能 可赤袋 = Float64[1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1] # 赤&白のボールが可能 可白袋 = Float64[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] # 全色のボールが可能 const n = length(価格) キャパ = 10.0 # リットル model = Model(HiGHS.Optimizer) @variable(model, x[1:n, ["黄", "青", "赤", "白"]], Bin) # 容量制限 @constraint(model, cキャパ, sum(体積[i] * sum(x[i, :]) for i in 1:n) ≤ キャパ) # 各色袋に可能なボール @constraint(model, c黄[i = 1:n], x[i, "黄"] ≤ 可黄袋[i]) @constraint(model, c青[i = 1:n], x[i, "青"] ≤ 可青袋[i]) @constraint(model, c赤[i = 1:n], x[i, "赤"] ≤ 可赤袋[i]) @constraint(model, c白[i = 1:n], x[i, "白"] ≤ 可白袋[i]) # 各色袋毎にボール一つずつの条件 @constraint(model, c袋[f = ["黄", "青", "赤", "白"]], sum(x[i, f] for i in 1:n) ≤ 1.0) # 各ボールは一度に複数の袋に入らない条件 @constraint(model, c[i = 1:n], sum(x[i, :]) ≤ 1.0 ) # 価格最大化 @objective(model, Max, sum(価格[i] * sum(x[i, :]) for i in 1:n)) # 最適化 optimize!(model) # 結果表示 for i in 1:n, j in ["黄", "青", "赤", "白"] if value(x[i, j]) > 0.5 println("$(i)番目のボール($(j)袋))") end end
出力結果は次の通りです。 Julia言語はあくまでラッパーで，HiGHSのSolverのお蔭といえるかもしれません。
Running HiGHS 1.7.0 (git hash: 50670fd4c): Copyright (c) 2024 HiGHS under MIT licence terms
Coefficient ranges:
Matrix [1e+00, 9e+00]
Cost [3e+00, 1e+01]
Bound [1e+00, 1e+00]
RHS [1e+00, 1e+01]
Presolving model
13 rows, 21 cols, 60 nonzeros 0s
6 rows, 15 cols, 43 nonzeros 0s
6 rows, 10 cols, 26 nonzeros 0s
Objective function is integral with scale 1
Solving MIP model with:
6 rows
10 cols (10 binary, 0 integer, 0 implied int., 0 continuous)
26 nonzeros
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
0 0 0 0.00% 34 -inf inf 0 0 0 0 0.0s
S 0 0 0 0.00% 34 14 142.86% 0 0 0 0 0.0s
R 0 0 0 0.00% 20 19 5.26% 0 0 0 6 0.0s
40.0% inactive integer columns, restarting
Solving report
Status Optimal
Primal bound 19
Dual bound 19
Gap 0% (tolerance: 0.01%)
Solution status feasible
19 (objective)
0 (bound viol.)
0 (int. viol.)
0 (row viol.)
Timing 0.00 (total)
0.00 (presolve)
0.00 (postsolve)
Nodes 0
LP iterations 6 (total)
0 (strong br.)
0 (separation)
0 (heuristics)
2番目のボール(赤袋))
4番目のボール(黄袋))
7番目のボール(青袋))
9番目のボール(白袋))
質問で示された種類とは別解がでていますが，違いは体積と価格が同じボール(白袋なので色はどうでもいい) なので多分合っているだろうということは分かります。
条件の記述をまとめて表現出来るのはJulia言語ならではでしょうか。
