線形計画法（2D）

2変数の線形計画法：実行可能領域と頂点最適化

計算例 — 線形計画法（2D）

最大化	3x + 2y

ページを開いたときに計算機が表示する値です。上の入力を変えると再計算されます。

インタラクティブシミュレーションを読み込んでいます...

実行可能領域は答えの保証ではない 🖖

頂点の規則には見落としやすい前提があります。そもそも最適解が存在しなければなりません。非有界のプリセット（x ≥ 0、y ≥ 0、x + y ≥ 2 のもとで 2x + y を最大化）を読み込むと、実行可能領域はまったく空ではないのに、最良の頂点は存在しません。北東へいくらでも歩き続けて改善できてしまうからです。ですからこのツールは一つではなく三つのうちいずれかの判定を返します。最適、実行不可能、非有界です。三番目は頂点を見つけられなかったからではなく、改善方向となる後退方向の有無を調べて判定しています。同じプリセットを最小化に切り替えれば、(0, 2) で有限の答えがすぐに現れます。実行可能性と可解性は別の問いなのです。

最適解は角に隠れている 🖖

平たく言えば、限られた資源を複数の制約のもとで同時にやりくりしており、各不等式が平面の一部を切り取ります。すべての制約が重なる部分が実行可能領域で、その内側の点はどれも有効な計画です。線形の目的関数は一方向へ増え続けるため、最良の計画は制約が交わる頂点に落ち着きます。要点は、最適化ではすべての点を調べる必要はなく、わずかな頂点だけを確認すればよいということです。

食事問題がシンプレックス法を先取りした話 🖖

1945年、経済学者ジョージ・スティグラーは、必要な栄養をすべて満たす最も安い食事を調べました。これは77品目からなる線形計画問題です。アルゴリズムがない中で巧みに推定し、年間およそ $39.93(1939年価格)を得ました。1947年にダンツィクのシンプレックス法が正確に解くと、真の最小値は $39.69 — スティグラーの手計算は年間わずか約24セントしか外していませんでした。地味な経済学が、線形計画法の草創期を代表する事例になったのです。

線形計画法 — なぜ隅だけを調べれば済むのか

あなたはどの線形計画のケースにいますか？

線形計画はいつも同じことを問います。直線で囲まれた領域の中で、直線の目的関数をどこまで押し進められるか。どちらも直線なので、最良の点は隅にしかなり得ません。だからこの方法は、隅を列挙して比べることに尽きます。どのケースかは、その領域が目的関数を閉じ込めているか、そして返ってきた隅が実際に使える数かどうかで決まります。

有界な領域 — 最適解は隅にある z = 10 → (2, 2)

最良の隅が分数 — それは別の問題 z = 24 → (8/3, 8/3)

非有界な領域に有界な答え min z = 13

有限の最適解がない — しかも隅を見ても気づけない z → ∞

有界な領域 — 最適解は隅にある

わかっていること: 最大化する目的関数と、領域を閉じるだけの ≤ 制約。実行可能集合は多角形になります。

確認すること: z = 10 → (2, 2)

計算例: x + y ≤ 4、x ≤ 2、y ≤ 3 のもとで 3x + 2y を最大化します。隅は (0,0)、(2,0)、(2,2)、(1,3)、(0,3) で、(2,2) の z = 10 がすべてを上回ります。

このケースを開く: 献立問題

有界な領域 — 最適解は隅にある. 目的の直線が右上へ滑っていき、多角形にただ一つの隅で触れるところで止まります。最大化する目的関数と、領域を閉じるだけの ≤ 制約。実行可能集合は多角形になります。 — 目的の直線が右上へ滑っていき、多角形にただ一つの隅で触れるところで止まります。

最良の隅が分数 — それは別の問題

わかっていること: 再び有界な領域ですが、目的関数が選ぶ隅は整数に乗りません。

確認すること: z = 24 → (8/3, 8/3)

計算例: 2x + y ≤ 8、x + 2y ≤ 8、x ≤ 4、y ≤ 4 のもとで 5x + 4y を最大化します。最適解は (8/3, 8/3)、およそ (2.67, 2.67) で z = 24 です。

このケースを開く: 工場の生産量

最良の隅が分数 — それは別の問題. 二つの有効な制約が格子線から外れて交わるので、最良の隅の座標は分数になります。再び有界な領域ですが、目的関数が選ぶ隅は整数に乗りません。 — 二つの有効な制約が格子線から外れて交わるので、最良の隅の座標は分数になります。

非有界な領域に有界な答え

わかっていること: ≥ 制約のもとでの最小化。実行可能領域は無限に伸びますが、目的関数には床があります。

確認すること: min z = 13

計算例: x + y ≥ 6、x ≥ 2、y ≥ 1 のもとで 2x + 3y を最小化します。領域は無限でも、最小値は (5,1) の z = 13 です。

このケースを開く: 最小費用

非有界な領域に有界な答え. 領域は原点から限りなく遠ざかりますが、目的関数は原点に近い隅で最小になります。 ≥ 制約のもとでの最小化。実行可能領域は無限に伸びますが、目的関数には床があります。 — 領域は原点から限りなく遠ざかりますが、目的関数は原点に近い隅で最小になります。

有限の最適解がない — しかも隅を見ても気づけない

わかっていること: 制約が決してふさがない向きに沿って目的関数が改善します。最良の点は存在しません。

確認すること: z → ∞

計算例: x + y ≥ 2、x ≥ 0、y ≥ 0 のもとで 2x + y を最大化します。x を増やす方向へ永遠に進めば目的関数も永遠に増え、答えは非有界です。

隅を調べるという処方が罰せられるのがこのケースです。領域には (0,2) と (2,0) という隅があり、比べるといかにも確からしい z = 4 が出ます。これは端的に誤りで、(2,0) から x の大きい方へ歩けば限りなく上回れるからです。隅の比較が正しいのは、目的関数が有界だとわかってからで、それは別の確認になります。すなわち後退方向、領域の中を永遠に進みながら改善し続ける道を探すことです。この道具はどの隅を信じるより先に、まさにそれを探して向きを走査します。実務では、非有界という結果はほぼ必ず制約を書き忘れた印であって、無限の利益が取れる印ではありません。

このケースを開く: 非有界

有限の最適解がない — しかも隅を見ても気づけない. 塗られた領域は右上へ開いていて、目的関数はその方向へ果てしなく改善し続けます。制約が決してふさがない向きに沿って目的関数が改善します。最良の点は存在しません。 — 塗られた領域は右上へ開いていて、目的関数はその方向へ果てしなく改善し続けます。

参考文献 (3)

The diet problem in the history block: Stigler, G. J. (1945). "The Cost of Subsistence." Journal of Farm Economics 27(2), 303.
Simplex, and the vertex theorem it relies on: Dantzig, G. B. Linear Programming and Extensions. Princeton University Press, 1963.
Unboundedness and recession directions, the tool’s third verdict: Boyd, S. & Vandenberghe, L. Convex Optimization. Cambridge University Press, 2004, §2.5. ISBN 978-0-521-83378-3.

全プロセスの詳細解説

Z = 3x + 2y を最大化する食事問題 5 ステップ
どの頂点が最適となり、その隣の頂点にはどのような価値があるか？ これはダイエット問題である。x と y がともに 0 以上で、x + y ≤ 4、x ≤ 2、y ≤ 3 という制約条件のもとで、Z = 3x + 2y を最大化する。
1. 任意の 2 つの実行可能点を選び、それらを結ぶ線分上を進むことを考える。この移動における線形目的関数の値は両端点での値の加重平均となり、加重平均がどちらか大きい方の端点の値を超えることは決してない。そのため、他の 2 点の真の内点となる点が唯一の最適解になることはなく、これをあらゆる方向において順次適用していくと、最適解はいずれかの頂点に追いやられることになる。
  
  $Z (λ A + (1 - λ) B) = λ Z (A) + (1 - λ) Z (B) \leq max {Z (A), Z (B)}, 0 \leq λ \leq 1$
2. 頂点とは 2 本の境界線が交差する場所であるため、候補は 5 本の直線から 2 本ずつを選ぶことで得られる。組み合わせは 10 組あり、そのうち 2 組は平行で、残る 8 組のうち交点を構成している直線以外の制約条件を満たすのは 5 組だけである。例えば x + y = 4 と x = 0 の交点は (0, 4) となるが、これは y ≤ 3 に違反する。
  
  ${x + y = 4, x = 2} \Rightarrow (2, 2); {x + y = 4, y = 3} \Rightarrow (1, 3); (0, 0), (2, 0), (0, 3)$
3. 5 回の代数的な計算と 1 回の比較を行えば探索は終了する。検証すべき内部も、辿るべき辺も残されていない。
  
  $Z = 3 x + 2 y : 0, 6, 10, 9, 6 ⟹ (x^{*}, y^{*}) = (2, 2), Z^{*} = 10$
4. 最適解となる頂点では、x + y = 4 と x = 2 の両方の制約が有効（等号が成立）になっており、y = 2 は上限である 3 よりちょうど 1 単位下にある。余裕のある制約は何の制限にもなっていないため、それを緩和しても何も変化しない。残る 2 つの制約については、資源量をそれぞれ 1 単位増やして解き直してみる価値がある。
  
  $b_{1} : 4 \to 5 \Rightarrow (2, 3), Z = 12, y_{1} = 2; b_{2} : 2 \to 3 \Rightarrow (3, 1), Z = 11, y_{2} = 1; y^{*} = 2 < 3 \Rightarrow y_{3} = 0$
5. これら 3 つの価格のそれぞれに、問題で与えられた該当資源の量を掛け合わせて重み付けを行う。
  
  $b_{1} y_{1} + b_{2} y_{2} + b_{3} y_{3} = 4 (2) + 2 (1) + 3 (0) = 10 = Z^{*}$
解答

ツールは 5 つの頂点における値の 3 番目である x* = 2、y* = 2、および Z* = 10 を出力する。ステップ 4 で得られた数値 — 2、1、0 — は潜在価格（シャドウ・プライス）であり、図からは読み取れない問いに答えてくれる。すなわち、x + y の予算をさらに 1 単位増やすことの価値は x を 1 単位増やすことの 2 倍であり、y を 1 単位増やしても価値は全く生じない。ステップ 5 は強い双対性を示しており、これは今回の数値による偶然ではない。供給量で重み付けされた価格は常に最適値を再現するのであり、これこそがそれらを「価格」たらしめている理由に他ならない。潜在価格には適用限界も存在する。x + y の予算がもたらす 1 単位あたり 2 の価値は 5 までしか維持されず、その時点で頂点は (2, 3) に達し、他の 2 つの制約が有効になって Z は 12 で頭打ちとなる。その点を超えると価格は 0 となり、追加で購入した分はすべて無駄になる。

$max {c^{⊤} x : A x \leq b, x \geq 0} = min {b^{⊤} y : A^{⊤} y \geq c, y \geq 0} = 10$

42Math チーム · 更新 2026-08-17

公表された資料と照合しています。訂正のご指摘を歓迎します。編集方針 · 訂正

統計・ファイナンスのレッスン一覧 →

例題

献立問題 - 古典的な有界最大化問題:最適解は実行可能領域の頂点で得られる。
工場の生産量 - 交差する容量制約により、多角形の実行可能領域が形成される。
最小費用 - 下限制約下での最小化では、目的関数の方向に対して原点に最も近い実行可能な頂点が選ばれる。
非有界 - 実行可能領域が非有界になる場合があり、目的関数が有限の最適値を持たないことがある。