線形計画と最適化 想定問題 3
最適化について述べた次の（ア）～（エ）を，正しいものは○，誤っているものは×としたとき，その組合せとして最も適切なものはどれか。
（ア）2変数の線形計画問題では，目的関数の等高線が実行可能領域の1つの辺と平行になる場合でも，最適解は常にただ1つの頂点に定まる。
（イ）線形計画問題で，主問題が最適解をもつならば，その双対問題も最適解をもち，両者の目的関数の最適値は等しくなる。
（ウ）凸計画問題ではない非線形計画問題では，勾配法などで求めた解が局所的最適解にとどまり，大域的最適解であるとは限らない。
（エ）多目的最適化問題では，パレート解は一般にただ1つに定まり，その解ですべての目的関数が同時に最もよい値になる。
アイウエ
解説
ポイント
線形計画の最適解の性質，双対問題，局所的最適解，パレート解について，4つの記述の正誤を問う問題です。
考え方と解き方
最適化の用語の意味を，記述ごとに確かめます。
「常に」「ただ1つ」「同時に」のような言い切りは疑います。
ア：誤り。等高線と平行な辺が最適値をとる側にあれば，その辺の上のどの点も最適解になり，1つには定まりません。「常に」が誤りです。
イ：正しい。主問題に最適解があれば双対問題にも最適解があり，最適値は等しくなります（双対定理）。
ウ：正しい。凸でない問題には谷がいくつもあることがあり，勾配法（坂を下る方向に進む方法）で見つけた谷底が全体の最小とは限りません。
エ：誤り。パレート解は目的どうしがトレードオフになる解の集まりで，ふつうはたくさんあります。どの目的も同時に最もよくなる解があるなら，対立はありません。答えは ア ×，イ ○，ウ ○，エ ×
覚えておくこと
- 目的関数の等高線が最適側の辺と平行なら，その辺の上のどの点も最適解になり，1つに定まらない（テキスト・覚えること）
- 双対問題：制約条件と変数の役割を入れかえた，もう1つの問題。主問題に最適解があれば双対問題にもあり，最適値は等しい（双対定理）（テキスト・覚えること）
- 凸でない問題では，勾配法で求めた解が局所的最適解にとどまり，大域的最適解とは限らない（テキスト・覚えること）
- パレート解は1つではなく集まり。その中からどれを選ぶかは，意思決定する人が決める（テキスト・覚えること）
類似する過去問：令和元年度 基礎科目 I-1-1、令和元年度（再試験） 基礎科目 I-1-2
テキスト「線形計画と最適化」を読む