最適化問題（線形計画・凸計画）

線形計画・凸計画・整数計画という最適化問題の種類と，それぞれの性質を問う問題です。

最適化問題は，決定変数（自分で決める数），目的関数（最大・最小にしたい量），制約条件（守る条件）の3つでできています。

種類ごとの「定義」と「解きやすさ」を思い出して，記述を1つずつ確かめます。

ア：誤り。線形計画問題は，目的関数だけでなく制約条件も一次式で書ける問題です。制約条件は線形でなくてよい，という部分が逆です。

イ：正しい。変数が2つなら，横軸と縦軸に変数をとり，制約で囲まれた領域と目的関数の等高線を描けば，最適な点が図から読み取れます。

ウ：正しい。凸計画問題は谷が1つしかない形なので，近くでいちばん良い点（局所的最適解）が，そのまま全体でいちばん良い点（大域的最適解）になります。

エ：正しい。整数計画問題は組合せの数が爆発的に増えるので，大きな問題は遺伝的アルゴリズムなどの近似的な方法で，だいたい良い答えを求めることがあります。答えは ア 誤，イ 正，ウ 正，エ 正

• 線形計画問題：目的関数も制約条件も一次式（2x＋3y のような形）
• 凸計画問題：局所的最適解がそのまま大域的最適解になる
• 整数計画問題：変数が整数だけ。大きな問題は厳密に解くのが難しく，ヒューリスティック（経験的・近似的な解き方）で近似解を求める
• 2変数の線形計画は図解法（実行可能領域と目的関数の等高線を描く）で解ける