組み合わせ問題
提供: Internet Web School
(版間での差分)
| 7 行: | 7 行: | ||
| - | [[ファイル: | + | [[ファイル:ナップザック ページ 1.jpg|500px]] |
| 30 行: | 30 行: | ||
作成したデータは以下の通りである. | 作成したデータは以下の通りである. | ||
| - | [[ファイル: | + | [[ファイル:ナップザック ページ 2.jpg|500px]] |
| - | [[ファイル: | + | [[ファイル:ナップザック ページ 3.jpg|500px]] |
ソルバーのパラメータ 入力は以下の通りである. | ソルバーのパラメータ 入力は以下の通りである. | ||
| - | [[ファイル: | + | [[ファイル:ナップザック ページ 4.jpg|500px]] |
ソルバーによる結果は以下の通りである. | ソルバーによる結果は以下の通りである. | ||
| - | [[ファイル: | + | [[ファイル:ナップザック ページ 5.jpg|500px]] |
品物2,3,4,5 を詰め込んだときに値段の合計の最大値 700になる． | 品物2,3,4,5 を詰め込んだときに値段の合計の最大値 700になる． | ||
2020年11月27日 (金) 14:13時点における版
ナップサック問題
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になる．
