線形計画法とは？制約条件のもとで最適解を導く数理最適化手法
線形計画法は、線形の目的関数と制約条件のもとで最適な資源配分を求める数理最適化手法です。基本構造、シンプレックス法の実践手順、活用場面と注意点を解説します。
線形計画法とは
線形計画法（Linear Programming、LP）とは、線形の目的関数を線形の制約条件のもとで最大化または最小化する数理最適化手法です。限られた資源をどのように配分すれば最も効率的な結果が得られるかを数学的に求めることができます。
線形計画法は、1947年にアメリカの数学者ジョージ・ダンツィグが開発したシンプレックス法によって実用化されました。当初は米軍の物資輸送計画の最適化に用いられましたが、現在では生産計画、物流最適化、ポートフォリオ構成など、ビジネスのあらゆる領域で活用されています。
線形計画法の最大の強みは、制約条件が複雑であっても数学的に唯一の最適解を保証できる点です。経験や勘に頼らず、論理的に「これ以上の改善はない」と断言できる根拠を提供します。
コンサルティングの現場では、工場の生産ミックスの最適化、物流ネットワークの配送計画、人員シフトの最適配置など、資源配分の意思決定で活用されます。Excelのソルバー機能でも実行できるため、高度なプログラミングスキルがなくても取り組めます。
構成要素
線形計画法は以下の要素で構成されます。すべての関数が線形（一次式）であることが適用の前提条件です。
| 要素 | 説明 |
|---|---|
| 決定変数 | 最適化の対象となる変数（生産量、配送量、投資額など） |
| 目的関数 | 最大化または最小化したい指標を決定変数の一次式で表現したもの |
| 制約条件 | 決定変数が満たすべき条件を不等式や等式で表現したもの |
| 非負条件 | 決定変数が0以上であるという条件 |
| 実行可能領域 | すべての制約条件を満たす決定変数の値の集合 |
| 最適解 | 実行可能領域内で目的関数を最大化（または最小化）する点 |
標準形と双対問題
線形計画法の問題は標準形（すべての制約が不等式で、決定変数が非負）に変換して解きます。また、すべての線形計画問題には双対問題が存在し、主問題の最適解と双対問題の最適解は一致します。双対問題を分析すると、制約条件の緩和がどれだけ目的関数の改善につながるかという「影の価格」が分かります。
実践的な使い方
ステップ1: 意思決定の対象を決定変数として定義する
最適化したい対象を明確にし、決定変数として定義します。たとえば「製品Aの生産量をx1、製品Bの生産量をx2」のように設定します。決定変数は具体的かつ測定可能なものにしてください。
ステップ2: 目的関数を定式化する
最大化または最小化したい指標を決定変数の一次式で表現します。「利益 = 300x1 + 500x2 を最大化」のように記述します。目的関数が1つであることが線形計画法の前提です。
ステップ3: 制約条件を不等式で表現する
資源の上限、需要の下限、品質基準などの制約を不等式で表現します。「機械Aの稼働時間: 2x1 + 4x2 ≦ 100」のように記述します。現実の制約を漏れなく洗い出すことが重要です。
ステップ4: ソルバーで最適解を求める
Excelのソルバー、Python（PuLP、SciPy）、専用ソフトウェア（CPLEX、Gurobiなど）を使って最適解を計算します。小規模な問題であればExcelのソルバーで十分対応できます。
ステップ5: 感度分析で頑健性を検証する
最適解が得られたら、パラメータの変動に対する感度分析を行います。制約条件の右辺値や目的関数の係数がどの程度変わっても最適解が変わらないかを確認し、意思決定の頑健性を評価します。
活用場面
線形計画法は以下のような場面で効果を発揮します。
- 工場の生産計画で、複数製品の生産量を利益最大化の観点から決定したいとき
- 物流ネットワークで、複数拠点間の配送量を輸送コスト最小化の観点から最適化したいとき
- 人員配置で、スキルや勤務時間の制約のもとシフトを効率的に組みたいとき
- ポートフォリオ構成で、リスク制約のもとリターンを最大化する資産配分を求めたいとき
- 広告予算の配分で、予算制約のもと到達率を最大化するメディアミックスを決めたいとき
注意点
線形計画法は目的関数と制約条件がすべて線形（一次式）であることが前提です。規模の経済や閾値効果のような非線形な関係がある場合、線形近似の妥当性を慎重に検討してください。
線形性の前提を検証する
現実のビジネスでは「生産量が増えると単位コストが下がる」など非線形な関係が多く存在します。線形計画法を適用する前に、対象となる問題が線形近似で十分かどうかを確認してください。近似が不適切な場合は非線形計画法の検討が必要です。
定式化の精度が結果を左右する
制約条件の漏れや誤りは、実行不可能な解や非現実的な解につながります。現場の実態を正確に把握し、すべての制約を数式に落とし込むプロセスに十分な時間をかけてください。
整数制約が必要な場合は別手法を検討する
「工場を建てるか建てないか」のような0-1の意思決定や、「トラック3台」のような整数の制約がある場合、線形計画法では小数の解が出てしまいます。整数計画法への拡張が必要です。
まとめ
線形計画法は、線形の目的関数と制約条件のもとで最適な資源配分を数学的に求める手法です。ジョージ・ダンツィグが開発したシンプレックス法により実用化され、生産計画、物流最適化、人員配置など幅広い領域で活用されています。線形性の前提を検証し、制約条件を漏れなく定式化することで、経験や勘に頼らない最適な意思決定が可能になります。