第 4 章

最適解はなぜ頂点に現れるか

可行領域の頂点で目的値を採点し、標準ケースの最適点と、多重最適解が起きる条件を掴む。

目的関数の直線を平行移動していくと、最後に触れる点が最適解になります。

目的関数は「等高線の束」として見る

目的関数 z = 3x + 5y は、値を固定すると 3x + 5y = 定数 という直線になります。定数を大きくすると、直線は平行のまま右上へ押し出されます。

可行領域からはみ出さない範囲で一番遠くまで押し出したとき、最後に接している点が最適解です。

傾きの意味

目的関数の直線の傾きは −c_x / c_y です。係数比が変わると、押し出す向きが変わります。

なぜ頂点で触れるのか: 目的関数が線形（直線）であり、可行領域も直線で囲まれた凸多角形だからです。直線を平行移動して凸多角形に最後に触れる位置は、ほぼ必ず角（頂点）になります。例外は、目的関数の直線がたまたま可行領域のある辺と平行になっている場合だけで、このときは辺全体で同時に触れます（多重最適解）。

標準ケースでは頂点を採点すればよい

第 3 章で求めた交点 (6, 4) と、軸上の切片を合わせると、可行領域の主な頂点は次の 4 つです（交点の計算は再掲しません）。

頂点	意味
`(0, 0)`	何も作らない
`(8, 0)`	切断工程いっぱいまで A を作る
`(6, 4)`	2 本の工程制約が同時に効く交点（第 3 章で計算済み）
`(0, 7)`	仕上工程いっぱいまで B を作る

2 変数の入門では、これらの頂点の目的値を直接比べる方法がもっとも理解しやすいです。

理解チェック 1 — 主要な頂点を採点する

可行領域の主な頂点 (0,0)、(8,0)、(6,4)、(0,7) を採点し、最適点を数で選びます。

Q1. 目的関数 z = 3x + 5y で、頂点 (8, 0) の目的値はいくつですか。

万円

Q2. 頂点 (6, 4) の目的値を求めてください。

万円

Q3. 頂点 (0, 7) の目的値を求めてください。

万円

Q4. 標準ケースの最適点 (x, y) の x を入力してください。

Q5. 同じ最適点の y を入力してください。

多重最適解は「平行」で起きる

目的関数の傾きが可行領域の辺とぴったり一致すると、1 点だけではなく辺全体で同じ目的値になります。

2x + y = z は 2x + y = 16 と平行
x + 2y = z は x + 2y = 14 と平行

このときは「どの頂点が最適か」ではなく、「どの辺が最適か」と考える必要があります。

実務上の意味

多重最適解が出るということは、辺の上のどの点を選んでも利益（目的値）は同じだということです。たとえば「製品 A をたくさん作っても、製品 B に振り替えても利益が変わらない」状態を意味します。数学だけでは順位がつかないので、生産ラインの安定性、在庫リスク、納期、顧客との関係といった目的関数に書かれていない別の判断基準でどの点を選ぶかを経営判断で決められます。多重最適解は「決めかねる」ではなく「自由度がある」と読むと建設的です。

理解チェック 2 — 多重最適解を見抜く

目的関数の傾きが制約辺と一致すると、1 点ではなく辺全体で同じ目的値になります。

Q1. 目的関数を maximize z = 2x + y に変えたとき、最適値はいくつですか。

Q2. 同じ z = 2x + y のとき、最適解の種類はどれですか。

1 点辺全体

第 4 章のまとめ

2 変数の LP では、可行領域の頂点を採点すると最適解を見つけやすい。
標準ケースでは (6, 4) が最適で、目的値は 38。
目的関数が制約辺と平行になると、多重最適解が起きる。