数理最適化とは③

基本的用語についてもう少し理解をはっきりさせておきたいので、「目的関数」「変数」「制約条件」について例を交えてまとめたいと思います。

おさらい

数理最適化とは①で、↓のようにまとめました。

• 目的関数：最大化あるいは最小化したい関数

• 決定変数(変数)：目的関数を最適化するために決めたい変数

• 制約条件：最適化するうえで満たさないといけない条件

これを、具体的な例を当てはめてみていきます。
例は、わかりやすく「ナップサック問題」を使います。

ナップサック問題

ナップサック問題の例です。
ナップサック問題とは、ナップサックに入れる物の最適な組み合わせを見つける問題です。

• ナップサックには複数の品物を入れることができる

• ナップサックのサイズ制限：1500以下

• ナップサックの重量制限：1000以下

• ナップサックに入れた品物の総額を最も高くしたい

品物一覧

目的関数

今回の場合は最大化問題で、最大化したいものは、品物の値段です。
そのため、目的関数は、「ナップサックに入れる品物の総額」になります。
計算式で表すと、以下のようになります。
　　総額　＝　　( 金塊の個数　　　　×　金塊の値段 )
　　　　　　＋　( 彫刻の個数　　　　×　彫刻の値段 )
　　　　　　＋　( ネックレスの個数　×　ネックレスの値段 )
　　　　　　＋　( 指輪の個数　　　　×　指輪の値段 )
　　　　　　＋　( ダイヤの個数　　　×　ダイヤ計の値段 )
　　　　　　＋　( 腕時計の個数　　　×　腕時計の値段 )
　　　　　　＋　( 絵画の個数　　　　×　絵画の値段 )

変数

何をどれくらいナップサックに入れるのかによって、品物の総額が決まります。
そのため、変数は、「それぞれの品物の個数」になります。
この場合の撮り得る範囲は、「0以上、上限数以下の整数」です。

制約条件

条件は、「ナップサックの許容量」と、「それぞれの品物の個数の範囲」です。
これらの制約条件をまとめると、以下のようになります。

• サイズ上限：1500以下

• 重量上限：1000以下

• 品物の個数：0以上、上限個数以下

まとめ

• 目的関数：ナップサックに入れる品物の総額

• 変数：それぞれの品物の個数

• 制約条件：ナップサックの許容量と、品物の個数の範囲