最適化問題
与えられた制約条件の下で、ある目的関数を最大または最小にする解を求めること
ナップサック問題
数理計画分野では有名な「ナップサック問題（Knapsack problem）」を例に挙げて説明をしてみましょう。
ナップサック問題とは、「何個かの価値や容量、重量などがわかっている品物があります。ナップサックには容量や強度の制限があり、それを超えないように品物を詰めなくてはなりません。ナップサックに入れた品物の価値の和が最大になるようにするにはどの品物を選べばよいでしょうか」という問題です。
https://gyazo.com/6c717afb21f7decb1023481d968009c5
これを最適化問題として解いてみましょう。
制約条件は重量の合計が3,000以下、変化させるのは採択の有無で、採用なら1、採用しなければ0です。この価値の合計を最大化する組み合わせを計算してみてください。組み合せは2の8乗＝256通りあります(品物は8種類)。これほど単純なモデルでもこれだけの計算をしてみなくてはいけないので、とても大変です。
実際に最適化ツールを使って計算してみたものが以下の表です。
ナップサックに3,000しか入らないときには、「置物」と「絵画」を盗むのがよいようです。しかし、3,200入るナップサックだったとすれば、置物も絵画も採用せず、「金塊」「指輪」「ネックレス」「現金」を盗むのが、価値の最大化になるわけです。
https://gyazo.com/971bcf310666d723bf310d952dd95b96
このように、組み合せが多すぎて自分では計算できないときに、最適な組み合せを導出するのが最適化問題です。