組み合わせ問題

提供: Internet Web School

2020年11月27日 (金) 14:07時点における版

ナップサック問題

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

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

品物$i\ (i=1,2,3,4,5)$をナップサックに入れるか入れないかによって

値$1,0$を取る変数$x_i$ を導入すると,この問題は

制約条件

$5x_1+3x_2+2x_3\ +4x_4　+ 1x_5 \leq 10$

のもとに

$100x_1+200x_2+150x_3+250x_4　+ 100x_5$

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

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

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