線形計画法ソルバー

単体法（シンプレックス法）を使用して線形計画問題をオンラインで解決します。目的関数の最大化または最小化、混合制約（≤/≥/=）、最大8つの決定変数に対応しています。2変数のLP（線形計画法）については、すべての頂点と最適解をハイライトしたインタラクティブな実行可能領域プロットを表示します。

線形計画法ソルバー

Embed 線形計画法ソルバー Widget

線形計画法ソルバー

線形計画法ソルバーは、一連の線形不等式または等式に制約された線形目的関数の最大値または最小値を求めるオンライン電卓です。単体法（シンプレックス法）のBig-M法バリアントを使用しているため、<=, >=, = の制約を自由に混ぜることができ、2変数の問題については、すべての頂点と最適値を強調したインタラクティブな可能領域プロットを描画します。

線形計画法とは何ですか？

線形計画（LP）問題は以下のように定義されます：

最大化（または最小化）: Z = c₁ x₁ + c₂ x₂ + … + c_n x_n 制約条件: a₁₁ x₁ + … + a_1n x_n (≤, ≥, or =) b₁ a₂₁ x₁ + … + a_2n x_n (≤, ≥, or =) b₂ … a_m1 x₁ + … + a_mn x_n (≤, ≥, or =) b_m x₁, x₂, …, x_n ≥ 0

すべての制約を満たす点の集合は可能領域（または実行可能領域）と呼ばれ、凸多面体となります。線形計画法の基本定理によれば、LPに有限の最適解がある場合、それは必ずこの多面体の頂点（極点）で達成されます。これが、頂点から頂点へと移動するシンプレックス法が非常に効果的である理由です。

シンプレックス法の仕組み

実行可能な頂点から開始し、シンプレックス法はより良い値を持つ隣接する頂点へピボットを繰り返すことで目的関数を改善します。主な手順は以下の通りです：

標準形: LPを Ax = b, x ≥ 0 の条件下での max c^Tx に変換します。<= 制約にはスラック変数を加え、>= 制約には剰余変数を引き、さらに大きなペナルティ −M を持つ人工変数を加えます。等号制約には人工変数を加えます。
初期表: スラック変数と人工変数を基底とすることで、明らかな開始頂点が得られます。
進入変数: 縮小費用 $ c_j - z_j $ が最大の非基底変数を選びます。そのような変数が存在しない場合、現在の解が最適です。
退出変数: 進入列から最小比テストを行います。各行のRHSをその進入列の正の要素で割り、最小の比率を持つ行を選びます。正の要素が存在しない場合、LPは非有界です。
ピボット: ガウスの消去法を使用して、進入列を単位ベクトル（退出行を1とする）にします。
停止条件が満たされるまで繰り返します。

終了時に人工変数が正の値で基底に残っている場合、元のLPは実行不能です。

グラフィカルな方法（2変数の場合）

2変数の問題の場合、可能領域は2次元の凸多角形になります。最適解は常に頂点にあるため、すべての頂点を列挙して目的関数を評価すれば十分です。この電卓は、すべての制約境界の交点を算出し、他のすべての制約を満たす交点のみを保持し、視覚化のためにそれらを反時計回りにソートすることでこの列挙を実行します。

入力構文

最初の行に目的関数を書き、その後、1行につき1つの制約条件を書きます。変数名は任意の識別子（x, y, x1, profitなど）が使えます。演算子は <=, >=, = です。非負制約は x, y >= 0 のようにショートカットで記述できます。

Maximize 3x + 5y x + y <= 10 2x + y <= 16 x + 3y <= 18 x, y >= 0

空行および # で始まるコメントは無視されます。このソルバーは最大8つの決定変数と20の制約条件を受け入れます。

計算例

テーブルと椅子を作る家具工房を考えてみましょう。テーブル1台の利益は$3で、木材1ユニットと労働2ユニットが必要です。椅子1台の利益は$5で、木材1ユニット、労働1ユニット、ニス3ユニットが必要です。利用可能なリソース：木材10、労働16、ニス18。x = テーブル、y = 椅子とすると、LPは以下の通りです：

Maximize Z = 3x + 5y x + y <= 10 (木材) 2x + y <= 16 (労働) x + 3y <= 18 (ニス) x, y >= 0

可能領域は五角形になります。各頂点でZを評価すると：

頂点 (x, y)	Z = 3x + 5y	実行可能か？
(0, 0)	0	はい
(8, 0)	24	はい
(6, 4)	38 ← 最適	はい
(0, 6)	30	はい

したがって、工房はテーブル6台と椅子4脚を製作することで、最大利益 $38 を得ることができます。木材と労働の制約は 有効（Binding） です（最適点で左辺が右辺と等しくなります）。ニスもスラックが0（この場合は有効）であり、3つのリソースすべてが使い切られていることを意味します。

よくある落とし穴と検出される問題

状況	症状	修正方法
非有界なLP	ソルバーが「非有界」と報告	不足している上限を追加してください。可能領域が改善方向に無限に伸びているため、目的関数が際限なく増大します。
実行不能なLP	ソルバーが「実行不能」と報告	制約が互いに矛盾しています（例：`x >= 10` かつ `x <= 5`）。すべての境界条件を見直してください。
代替最適解	警告バッジ；最適頂点は一意だが、辺に沿って同じZが達成される	目的関数のベクトルが有効な辺と平行な場合に発生します。その辺上の2つの頂点の任意の凸結合も最適解となります。
退化 / 巡回	Zが改善されずにシンプレックス反復が続く	教科書的な問題では稀ですが、ブランドのルールや摂動法で解決可能です。この電卓は無限ループを避けるため反復回数を制限しています。

応用例

製品ミックスと生産計画 — リソースの制限下で最大の利益を得るために、各製品をいくつ作るか。
食事と配合問題 — 栄養基準を満たしつつ、食事や飼料のコストを最小化する。
輸送と割り当て — 供給と需要のバランスを保ちつつ、輸送コストを最小化する。
ポートフォリオの最適化 — リスクやエクスポージャーの制約下で期待収益を最大化する（線形化された場合）。
ネットワークフロー — 最大流問題や最小費用流問題は、全ユニモジュラ係数行列を持つLPに帰着します。
スケジューリング — シフト要件や総労働時間の制限下での人員配置。

この電卓の使い方

テキストボックスにLPを入力します。最初の行は Maximize または Minimize で始める必要があります。続く行に1行1つずつ制約条件を入力します。
ショートカット x, y >= 0 を使用して、リストされたすべての変数の非負制約を一度に宣言できます。
「線形計画問題を解く」をクリックします。ソルバーは最適値 Z、各決定変数の最適値、有効制約のリストを報告し、2変数のLPについてはインタラクティブな可能領域プロットを表示します。
プロット上の頂点にマウスを合わせると、その座標とZ値が表示されます。最適点は星印で強調されます。
シンプレックス表を確認して、各ピボットと目的関数Zが改善されていく過程を追跡します。進入列は琥珀色、退出行は赤色で強調されます。

よくある質問

線形計画問題とは何ですか？

線形計画（LP）問題とは、一連の線形不等式または等式を満たす決定変数の集合において、線形目的関数の最大値または最小値を求める問題です。実行可能集合は凸多面体となり、最適値は常にその頂点のいずれかで達成されます。これがシンプレックス法が利用する重要な事実です。

シンプレックス法はどのように機能しますか？

シンプレックス法は、実行可能多面体の頂点に沿って移動します。各ステップ（「ピボット」）で基底変数を入れ替え、目的関数が厳密に改善される隣接する頂点へと移動します。ピボットによってZを改善できなくなった時点で、現在の頂点が最適となります。このツールは <=, >=, = 制約を混在させるためにBig-M法を使用しています。