組み合わせ最適化1 (ナップザック問題)

 組み合わせ最適化は、基本的に説明変数が整数値をとり最適化を行います。説明変数は0または1をとるときも多いです。典型的な例でナップザック問題をやってみます。

ナップザック問題の定式化

例題として、お菓子を値段制限があるなかで、どれだけ満足度を高められるか考えます。(Pythonで始めるプログラミング入門 コロナ社 P127 プログラム10-2 を改変)

name = ['チョコ', 'ポテトチップス', 'クッキー', 'ラムネ', 'ガム']

weight = [130, 120, 80, 30, 20] #お菓子の価格

value = [18, 15, 12, 4, 2] #お菓子の満足度

capacity = 300 #お菓子の値段合計上限

プログラムは再帰呼び出しを利用して、最大の満足度になるように計算をしています。途中、リストに入っている場合はcontinueをしているので、お菓子の重複が無いようにしています。定式化でも重複が無い式になっています。

ソースコード

ソースコードの一番下に、ソルバーを使った場合のナップザック問題を入れているので、それも実行してみると同様の答えが得られます。

今回のプログラムは少ないお菓子でしたので、総当たりで計算ができますが、商品数が増えるととても計算が終わりません。その場合は、分枝限定法やメタヒューリスティックの方法で解いていきます。

復習として、下記も参考にしてください。

・線形計画法1

・非線形計画法1(無制約)

・非線形計画法2(制約付き)

2021/09/06 ナップサック問題をdeapを使ったものを上記のソースコードに追加。遺伝アルゴリズムのフレームワークで、形式的に利用できるが、カスタマイズをするにはそれなりに内容を理解しないと使いこなせないものです。