1 線形計画の基本概念
1.1 問題の定式化
1.1.1 目的関数
線形計画（LP）では、意思決定変数をまとめたベクトル \(x\) に対して、達成したい指標を線形形式で記述する。典型的には最大化または最小化のいずれかで、目的は \(c^\top x\) の形で与えられる。ここで \(c\) は係数ベクトルで、変数の単位変更に対する評価の重みを表す。目的関数の形が線形であるため、許容領域内での改善は、後述する幾何学的構造（凸性）と整合するかたちで解析できる。
1.1.2 制約条件（不等式・等式）
実行可能性は、変数に対する線形式の不等式および等式で定義する。一般に、係数行列 \(A\) と右辺 \(b\) を用いて \[ Ax \le b,\quad Ax=b,\quad \text{など} \] として表現される。実務では、能力上限・需要充足・物量保存・論理条件の近似など、多様な条件が線形不等式や等式としてモデル化される。制約は実行可能領域の形状を決めるため、モデル化の細部は解の存在性や計算効率に直結する。
1.1.3 非負条件と変数の扱い
線形計画の標準的な枠組みでは、変数に非負条件 \(x\ge 0\) を課すことが多い。これは量（資源配分、個数、投入量など）を表す場合に自然である。一方で、符号付きの変数を扱う必要がある場合は、差分表現によって非負変数へ変換する方法が用いられる。例えば \(x\) を自由変数とし、\(x=x^+-x^-\) のように表して \(x^+,x^-\ge 0\) とすることで、問題を非負条件の枠に揃えられる。
1.2 実行可能領域と幾何学的解釈
1.2.1 凸集合としての実行可能領域
実行可能領域は、制約を満たす変数の集合として定義される。線形不等式・等式の交わりとして得られるため、その集合は一般に凸である。凸性とは、任意の2点を結ぶ線分が全て実行可能領域に含まれる性質を指す。凸集合では、最適性が特定の境界構造と結びつきやすく、探索の方向や最適解の候補が理論的に制約される。
1.2.2 頂点解と最適解の関係
凸な実行可能領域の下で線形目的関数を最適化すると、最適解はしばしば領域の頂点（極点）に現れる。厳密には、最適値を与える点が頂点である場合と、目的関数がある稜線・面に沿って一定となるために無数の点が同一の最適値を共有する場合がある。いずれにせよ、解の探索は凸多面体の離散的構造（頂点やその近傍）に関連付けられる。
1.3 標準形・正準形
1.3.1 標準形への変換
標準形とは、LPをある代表的な書式に揃えることで比較・解析・実装を容易にする考え方である。典型的には、最大化か最小化を固定し、不等式の向きを統一し、等式を適切に扱える形へ整理する。さらに非負条件を確保するための変換も含めて、係数行列や右辺の表現を変更する。変換後も最適値と（必要に応じて）最適解の対応関係が保たれるように設計することが重要である。
1.3.2 正準形への変換
正準形は、計算アルゴリズムが扱いやすいように、変数と制約の役割をさらに揃えた形として定義されることが多い。例えば等式制約にまとめ、目的関数を特定の符号規約に合わせる、自由変数を非負変数に置き換える、といった作業が行われる。正準形への変換は、シンプレックス法における基底の概念や、内点法における障壁項の設計と密接に関わる。
2 解法アルゴリズム
2.1 シンプレックス法
2.1.1 基底と実行可能性
シンプレックス法は、頂点解をたどることで最適化を進める代表的手法である。基底とは、ある時点での頂点を特徴づける変数の選び方であり、基底変数に対して他方をゼロとすることで候補点を表す。実行可能性は、基底変数の値が非負条件を満たすかどうかで判定される。基底が変わるごとに、別の頂点へ移動するため、制約の交点としての幾何学的意味を保ちながら探索が進む。
2.1.1.1 ピボット操作の考え方
基底を更新する操作はピボット（pivot）として実装される。具体的には、ある制約の側で計算される方向に沿って変数を動かし、いずれかの変数がゼロになる瞬間に基底が入れ替わるように設計する。数値的には、ガウス消去に相当する行変換を用いて、基底に関する連立方程式の解を更新しながら次の候補点へ進む。
1.1.2 目的関数値の改善規則
シンプレックス法では、現在の頂点から目的関数が改善する方向を選ぶ規則が必要となる。改善が見込める変数（入る変数）を選定し、同時に実行可能性を壊さない範囲で最大限進むように出る変数（基底から抜ける変数）を決める。入出の選択は多様な実装規則で分岐するが、基本原理は「目的の非悪化からの改善」と「実行可能性の維持」を同時に満たすようにする点にある。
2.1.3 有限回での停止条件
理論上は、一般の条件下で有限回の遷移で停止することが示される場合があるが、退化（後述）などでは同一目的値の遷移が繰り返されることがあり、停止挙動は工夫を要する。実務的には、循環を避けるための選択規則（特定の順序付けなど）を導入することで有限性が確保される設計がある。停止は、改善可能な入変数が存在しないとき、つまり最適性条件が満たされたときに起こる。
2.2 内点法
2.2.1 バリア関数の発想
内点法は、実行可能領域の境界ではなくその内部を通って解へ近づく方針をとる。境界に近づくと数値的不安定が起こりやすいため、代わりに障壁（バリア）項を目的に加えることで境界回避を誘導する。代表的には、非負条件の下で変数がゼロに落ち込まないよう、対数障壁などの形で「内部でなければコストが急増する」構造を用いる。これにより連続最適化として扱いやすい形に変換される。
2.2.2 中心経路と収束
障壁パラメータを段階的に調整しながら、解の近傍へ向かう経路を「中心経路」と呼ぶ。パラメータを小さくするほど境界に近い解に漸近するが、その過程で適切な更新則が収束性を支える。収束判定は残差（実行可能性のずれ）や停留度（目的関数の変化や双対ギャップ）などに基づいて行う。線形計画では多くの場合、理論的に多項式時間の解析が可能であり、実装では反復回数と精度のバランスが重要になる。
2.2.3 実装上の要点
内点法の実装では、線形代数の計算負荷（行列分解や連立方程式の解法）が支配的になりやすい。さらにスケーリングや初期点の選び方が反復性能に影響する。実務的には、疎行列を活用した前処理、丸め誤差を抑えるための手当て、停止基準の設計が欠かせない。境界に非常に近い解では障壁の勾配が大きくなるため、適切なパラメータ更新則が安定性に関わる。
2.3 双対性に基づく解法の考え方
2.3.1 双対問題の導出
双対性は、与えた最適化問題（原問題）に対して、関連するもう一つの最適化問題（双対問題）を構成する考え方である。双対問題は、原問題の制約や目的係数と整合する形で定式化され、双対変数は原問題の制約に対する「限界的価値」を反映するように解釈される。導出は、ラグランジュ緩和や内積表現の整理を通じて行われることが多い。
2.3.2 相補性と最適性条件
双対性では、相補性（complementary slackness）が最適性の核心となる。原問題側の制約が厳密に等号で成立している場合、対応する双対変数が一定の符号や条件を満たす。一方、原問題側で制約に余裕がある場合、双対変数側の対応量は消える（あるいはゼロに近づく）という関係が成り立つ。線形計画ではこの条件が組み合わさることで、原問題と双対問題の目的値が一致した点が最適解であることを確認できる。
2.4 数値計算上の注意
2.4.1 有限精度と退化
有限精度の計算環境では、理論通りの厳密な演算ができず、誤差が蓄積する。退化とは、更新のたびに新しい基底へ移るものの、値の変化が実質的に小さい、またはゼロが同時に現れるなどにより、遷移が停滞する状態を指す。シンプレックス法では循環や遅い収束として現れやすく、内点法では停留的な挙動や数値誤差の増幅につながることがある。対策として、基底選択規則、正則化、精度管理などが用いられる。
2.4.2 スケーリングと前処理
モデルの係数が極端に大きい・小さい場合、数値計算の安定性が損なわれる。スケーリングは、行や列の大きさを調整して条件数を改善し、計算誤差の影響を減らすための操作である。前処理では、冗長制約の削除、変数の固定、明らかな非実行可能性の検出、疎構造の整理なども行われる。これらは理論的には同一性を保ちつつ、実装の頑健性を高める目的を持つ。
3 理論的性質
3.1 双対性定理
3.1.1 弱双対性
弱双対性は、原問題の任意の実行可能解に対し、双対問題の任意の実行可能解が与える目的値が、原問題の最適値を下から（または上から）抑える関係を述べる。具体的には、最小化・最大化の符号規約に応じて、双対目的値は原問題の目的値を一定方向に評価する。これにより、双対目的は下界（上界）として機能し、計算中の進捗指標として利用できる。
3.1.2 強双対性
強双対性は、適切な条件の下で原問題と双対問題の最適値が一致することを保証する。さらに、実行可能領域がうまく定義されている場合、相補性を満たす組（原・双対の最適点）が存在する。線形計画では、標準的な仮定のもとで強双対性が成立しやすく、理論の整合性とともに、アルゴリズムが達成すべき到達点を明確化する。
3.2 最適性条件
3.2.1 相補スラックの解釈
相補スラックは、原問題の制約残差（余裕）と双対変数の積がゼロになる関係として表される。制約がぴたりと成立しているとき、双対側には対応する評価が現れ、逆に制約に余裕があるときには、その評価が不要になる。幾何学的には境界上と内部での役割分担があり、解の「どの制約が効いているか」を読み解く道具になる。
3.2.2 KKT条件との関係（線形の場合）
KKT条件（Karush–Kuhn–Tucker条件）は一般の制約付き最適化における最適性の必要条件および十分条件を与える枠組みである。線形計画では目的関数と制約が線形であり、正則性が得られやすいため、KKT条件は双対性や相補性と整合する形で最適性を表現できる。結果として、原・双対の実行可能性と相補性が揃うことが、最適解の同定に直結する。
3.3 非有界・実行不能の扱い
3.3.1 実行可能性の判定
実行不能（infeasible）は、どの変数も制約を同時に満たせない状態である。これが起こると最適化は意味を持たないため、解法は実行可能性の判定を内部で行う必要がある。理論的には、双対問題の実行可能性や目的値の評価と関連して、原問題が実行不能であることを示す証明（証拠となる双対的な構成）が得られることがある。
3.3.2 非有界性の意味
非有界（unbounded）は、目的値を改善する方向へ無限に進め、制約を満たしたまま目的が限界なく発散する状況である。例えば最大化で目的が無制限に増えるなら非有界となる。非有界性はモデルの解釈にも直結し、制約の不足や前提の欠落が疑われる。双対側では実行可能性と目的値の整合の破れとして現れることがあり、アルゴリズムはこれを検出して停止する。
3.4 解の構造
3.4.1 複数最適解
最適解が一意でない場合、最適値を共有する点集合が広がる。凸集合のある面上で目的関数が一定になると、その面の全ての点が最適となることがある。複数解は現場では「実現可能な複数の配分が同じ性能をもつ」という意味を持ち、運用上は追加の基準（公平性、管理のしやすさ、整数性など）を別途設けることで具体化できる。
3.4.2 退化と同じ目的値の状況
退化は、基底の切替が起きても目的関数値が変化しない、あるいは同一値の頂点が連続するような挙動として観測される。結果として反復回数が増えやすく、数値誤差の影響も受けやすくなる。退化自体は珍しい現象ではなく、モデルの係数設計や制約の相関、同時成立する条件の多さが背景にあることが多い。
4 応用と拡張
4.1 応用分野
4.1.1 配合・製造計画
配合・製造計画では、原材料の投入量を決め、品質要件やコスト制約を満たすように設計する。成分含有量の線形関係や、供給能力・需要量、歩留まりを線形式で表せる場合、LPは効率的に最適配合を与える。さらに、在庫や段取りの単純化されたモデルも線形近似として取り込める。
4.1.2 輸送・配送計画
輸送・配送では、供給地から需要地へ物資を割り当て、総輸送費（または距離・時間の重み付き費用）を最小化する問題が典型例である。各地域の供給量と需要量の保存則、輸送経路の容量などが線形制約として表現できるため、LPは自然な枠組みとなる。解は「各経路にいく量」を示し、現場の運用手順に落とし込みやすい。
4.1.3 スケジューリングと割当
スケジューリングと割当では、作業やリソースを時間・単位に割り当て、処理能力や優先度を条件化する。時間を離散化したり、平均的な割当を表す変数を導入したりすることで、線形制約として表現できることがある。単純な枠ではLPで扱えるが、現実の締切や順序制約を厳密に反映するには整数要素が必要になる場合もある。
4.2 感度分析（パラメータの影響）
4.2.1 目的係数の変化
感度分析では、係数 \(c\) や \(b\) の変化が最適値・最適解に与える影響を評価する。目的係数の変更は、どの変数が相対的に有利になるかを変え、基底の入れ替えを引き起こすことがある。ある範囲内では同じ基底が維持され、最適値が線形に追従するという性質が観測されることが多い。
4.2.2 制約係数の変化
制約側の係数が変わると、実行可能領域の形状が変化し、最適点の移動が起こり得る。特定の制約がどれだけ「効くか」を支配するのは、双対変数や相補性に関連する情報である。感度分析により、どの制約が臨界的で、どの係数の誤差が結果に大きく影響するかを見積もれる。
4.2.3 シャドープライスの解釈
シャドープライスは、双対変数として現れる「制約の限界価値」を表す概念である。例えば資源制約を少しだけ緩めたとき、目的値がどれだけ改善するかの一次近似として解釈される。符号規約に依存するが、実務では「その制約を追加で1単位改善する価値」を見積もる指標として利用される。解釈の有効範囲は感度解析の範囲と対応しており、無制限ではない。
4.3 拡張問題
4.3.1 整数計画・混合整数計画
LPでは変数が連続であるのに対し、整数計画では変数が離散的な値を取り、計数としての意味が強くなる。実際の割当では「作業員を何人」や「設備を何台」のように整数が本質であることが多い。このため、整数制約を導入した混合整数計画（MIP）がよく用いられる。MIPの解法ではLP緩和や枝刈りなど、LPの理論と計算技術が基盤として活躍する。
4.3.2 制約付き最適化の一般化
LPは制約付き最適化の一種であり、一般には目的関数や制約が非線形、あるいは凸でない場合がある。凸最適化はLPと同じく幾何学的に扱いやすい性質を持ち、非線形へ拡張しても同様の理論が生きることが多い。一般化においては、双対性、KKT条件、収束解析などの枠組みが共通の軸として引き継がれる。
4.3.3 目的関数や変数定義の一般化（関連概念）
目的関数や制約の一般化は多岐にわたる。例えば目的を凸関数にし、変数の取り扱いに制約（ノルム制約、確率的要素など）を追加することで、意思決定の現実性を高められる。一方で計算難度は増しやすく、近似や分解、分布型データの扱いなど工学的な工夫が必要になる。LPの枠組みは、こうした拡張の出発点として概念的な整理を提供する。