令和元年度 I-1-1

解説

この問題で問われていること

最適化問題に関する4つの記述(ア)〜(エ)の正誤の組合せを選ぶ問題。

解き方

① 線形計画=目的関数も制約条件も両方とも線形。凸計画は局所的最適解=大域的最適解。整数計画は難しく、大規模なら遺伝的アルゴリズムなどで近似解
② ア「制約条件が線形かは問わない」が誤 → ③④⑤。イ(2変数なら図解法)・ウ・エは正
③ 誤・正・正・正(⑤)

正解が正しい理由

(ア)線形計画問題は、目的関数だけでなく制約条件も決定変数の線形式(一次式)で表される問題であり、「制約条件が線形式であるか否かは問わない」は誤り。(イ)決定変数が2つなら、2軸の平面上に実行可能領域と目的関数の等高線を描いて最適解を求める図解法が使え、正しい。(ウ)凸計画問題では、局所的最適解が必ず大域的最適解になるという性質があり、正しい。(エ)決定変数が整数値に限られる整数計画問題は、組合せの数が膨大になって厳密解を求めにくいことが多く、規模が大きい場合は遺伝的アルゴリズムなどのヒューリスティックな方法で近似解を求めることがあり、正しい。したがって誤・正・正・正の⑤が正しい。

各選択肢について

• ① ウ・エを誤としている点が誤り。
• ② アを正、イ・エを誤としている点が誤り。
• ③ ウを誤としている点が誤り。凸計画問題では局所的最適解が大域的最適解になる。
• ④ イを誤としている点が誤り。2変数なら図解法を使える。
• ⑤ 誤・正・正・正の組合せが正しく、これが正答。

覚えるべきポイント

線形計画問題は目的関数と制約条件の両方が線形。凸計画問題では局所的最適解=大域的最適解。整数計画問題は難しい問題が多く、大規模なものはヒューリスティックな方法で近似解を求める。