Processing math: 100%

組み合わせ問題

提供: Internet Web School

(版間での差分)
29 行: 29 行:
<math>100x_1+200x_2+150x_3+250x_4 + 100x_5</math>
<math>100x_1+200x_2+150x_3+250x_4 + 100x_5</math>
-
を最大化する問題になる.[[ファイル:ナップザック.pdf]]
+
を最大化する問題になる.[[ファイル:ナップザック.pdf]]にMicrosoft Excelの ソルバーを用いた解法例を示す.

2020年11月23日 (月) 16:47時点における版

ナップサック問題

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

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

                           表3

品物   1  2  3  4  5

重さ   5  3  2  4  1

値段   250  200  150  250  100


解 法 

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

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

制約条件

5x1+3x2+2x3 +4x4 +1x510

のもとに

100x1+200x2+150x3+250x4 +100x5

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

個人用ツール