線形計画法
線形計画法は、線形式の目的関数を最大化または最小化し、係数が定数の線形な制約条件の下で意思決定変数の最適解を求める数理最適化の基礎的手法である。可行領域は凸多面体で表され、最適解が極点（頂点）に存在するという特徴をもつ。この性質により大規模な計画・設計・生産管理・ロジスティクスなどで計算効率よく解が得られる。製造現場では原材料・人員・設備の配分やスケジューリング、品質・コスト・納期のバランス設計などに活用される。さらに感度分析や双対理論により、制約の「影の価格」や設計余裕の評価にも応用できる。
基本概念
線形計画法では、目的関数は係数ベクトル
数学的定式化
標準形の例を挙げる。
最大化：maximize
制約：
一般形
幾何学的解釈
可行領域は半空間の共通部分でできる多面体である。目的関数の等高線
解法の代表例
線形計画法には頂点間を移動する方法と内部を進む方法がある。問題規模や構造により使い分けるのが実務的である。
シンプレックス法
基本変数と非基本変数を入れ替えながら多面体の隣接頂点へ移動し、目的値を単調増加（または減少）させる。初期可行解はビッグM法や2段階法で構成する。退化によるサイクリングはBland則などで回避する。
内点法
障壁関数を用い可行領域の内部を滑らかに進む。理論的には多項式時間で解け、大規模疎行列問題に強い。実務パッケージでは前処理・再スケーリング・事後リファインメントが併用される。
双対問題と影の価格
任意の実行可能な主問題には双対問題が対応し、弱双対性
感度分析と実務指標
右辺
モデリング技法
等式・不等式の統一化、スラック/サープラス変数、ビッグM法での論理条件の線形化、区分線形近似、上限・下限の設定、バランス制約、フロー保存則などを活用する。係数のスケーリングと無次元化は数値安定性の観点で重要である。
応用例（生産計画）
複数製品P1,P2,…の1期間利潤最大化を考える。目的関数は総利益の和、制約は原材料・加工時間・在庫容量で与える。
- 意思決定変数：各製品の生産数量
- 目的関数：総利益最大化
- 制約：原材料消費、ライン別工数、需要上限、安全在庫
小規模ならExcel、規模拡大時は専用ソルバが有効である。
実装とソフトウェア
実務ではExcel SolverやPythonのPuLP、OR-Tools、SciPy、商用のGurobi、CPLEXが広く用いられる。モデルは
拡張：整数計画・混合整数計画
一部変数に整数性を課すと混合整数線形計画（MILP）となり、厳密解には分枝限定法、カット法、ヒューリスティクスが用いられる。輸送問題・割当問題・ネットワーク流など特殊構造には専用アルゴリズム（例：network simplex）が有効である。
注意点（数値とモデル品質）
係数の桁スケール不一致は条件数を悪化させ解の信頼性を損なう。非現実的な大きなM、過度に相関の高い制約、冗長制約は避ける。データ誤差を考慮し、感度分析・ロバスト化を併用すると現場適合性が高まる。モデルは定期的に実績データでリキャリブレーションする。
工学・製造分野での位置づけ
線形計画法は最適化問題の入門であり、目的関数・制約条件の明確化、単位整合、物理・工程上の論理を線形表現に落とし込む訓練となる。設計段階での資源配分、生産段取り、在庫・輸送計画、エネルギーマネジメントなどで即効性が高い。さらに双対解の解釈は価格付けやコスト配賦、ボトルネック特定に直結する。