組み合わせ問題

UNIQ255d3ca544970a66-MathJax-2-QINU2 による版

(差分) ←前の版 | 最新版 (差分) | 次の版→ (差分)

ナップサック問題

5個の品物UNIQ6935b94029615e13-MathJax-9-QINUがあり,それぞれの重さと値段は表3の通りである．これをナップサックに詰めたいが, これには10㎏までしか詰め込めない．

値段の合計が最大となる品物選ぶにはどうすれば良いか．

品物UNIQ6935b94029615e13-MathJax-10-QINUをナップサックに入れるか入れないかによって

値UNIQ6935b94029615e13-MathJax-11-QINUを取る変数UNIQ6935b94029615e13-MathJax-12-QINU を導入すると,この問題は

制約条件

UNIQ6935b94029615e13-MathJax-13-QINU

のもとに

UNIQ6935b94029615e13-MathJax-14-QINU

を最大化する問題になる.　この問題はナップザック問題と呼ばれる組み合わせ最適化問題に属する.

ファイル:ナップザック.pdfにMicrosoft Excelの　ソルバーを用いた解法例を示す.

作成したデータは以下の通りである.

ソルバーのパラメータ　入力は以下の通りである.

ソルバーによる結果は以下の通りである.

品物2,3,4,5 を詰め込んだときに値段の合計の最大値 700になる．