Linear programming — 線形計画法

線形計画法（せんけいけいかくほう; 英語: Linear Programming, LP）は、数理計画法の一分野であり、オペレーションズ・リサーチで広く利用される手法で、線形制約条件の下で線形関数の極値（最大値または最小値）を求める問題の解法に関する理論と手法を扱うものである。

LPは、経済学、経営、計画、物流、その他の分野における最適化問題を解決するための、最も強力かつ頻繁に利用されるツールの一つである。

主な目的と用途

線形計画法の主な課題は、目標と資源利用の制約がともに線形関係で表現できる場合に、ある目標を達成するために限られた資源を配分する最良（最適）の方法を見つけることである。

線形計画法は、次のような実用的な問題を解決することができる：

• 生産の最適計画。
• 輸送フローの最適化（輸送問題）。
• 投資の最適配分。
• 材料の最適裁断。
• 割当問題。

LP問題の数学的定式化

標準的な線形計画問題は次のように定式化される。

線形の目的関数を最大化または最小化する決定変数の値を見つけることが求められる。その際、決定変数は線形等式および／または線形不等式の系で表される制約条件を満たす必要がある。通常、決定変数には非負条件（変数の値がゼロ以上であること）が加えられるが、これは問題の物理的または経済的な意味合いによって要求されることが多いためである。

数学的には、これは線形関数と線形方程式・不等式の系を扱うことを意味する。

LPの基本概念

• 決定変数（制御変数）: 問題を解く過程で決定する必要がある値（例：各種製品の生産量、異なる目的に割り当てられる資源の量）。
• 目的関数: 最大化または最小化が求められる、決定変数の線形関数。問題の目標を定量的に表現する（例：総利益、総コスト）。
• 制約条件: 決定変数が満たすべき線形等式および／または線形不等式の系。資源の限度、技術的要件、計画目標など、問題の諸条件を反映する。
• 実行可能領域（Feasible Region）: 問題のすべての制約条件を満たす決定変数の値のすべての組の集合。幾何学的には、多次元空間において実行可能領域は凸多面体（ポリヘドロン）となり、非有界であるか空集合である可能性もある。
• 実行可能解（Feasible Solution）: 実行可能領域に属する任意の変数値の組。
• 最適解（Optimal Solution）: 目的関数がその極値（最大値または最小値）に達する実行可能解。最適解が存在する場合、それは常に実行可能領域の境界上にあり、少なくとも実行可能領域の凸多面体の一つの頂点に存在する（LPの基本定理）。

LP問題の解法

線形計画問題を解くための主要な手法がいくつか存在する。

• 図解法: 2つの決定変数を持つ問題に適用される。実行可能領域と目的関数を平面上に視覚的に描き、実行可能領域の頂点を分析するか、目的関数の等高線を移動させることによって最適解を見つけることができる。
• シンプレックス法: ジョージ・ダンツィグによって開発された汎用的な反復アルゴリズム。この方法は、実行可能領域のある頂点から隣接する頂点へと逐次的に移動し、各ステップで目的関数の値を改善しながら、最適解が見つかるまで続ける。LP問題を解くための古典的で最もよく知られた手法である。
• 内点法: シンプレックス法より後に登場した、代替的なアルゴリズム群。これらの手法は、実行可能領域の境界上ではなく内部を移動して最適解に向かう。特に非常に大規模なLP問題を解くのに効果的である。

線形計画法における双対性

各線形計画問題（主問題と呼ばれる）には、双対問題と呼ばれる別のLP問題を対応させることができる。主問題と双対問題は密接に関連している。

一方の問題を解くことは、もう一方の問題の解に関する情報を提供する。両問題の目的関数の最適値は（存在する場合）一致する。双対問題の変数は重要な経済的解釈を持ち、それらは資源のシャドープライス（または双対評価）に対応する。これは、対応する資源の制約がわずかに変化した場合に、主問題の目的関数の最適値がどれだけ変化するかを示す。

LPの応用

線形計画法は、以下の分野で広く応用されている：

• 経済学およびビジネス（生産計画、物流、金融、マーケティング）。
• 産業（生産プロセスの最適化、在庫管理、材料の裁断）。
• 運輸（経路の最適化、スケジュール作成）。
• 農業（作付面積の最適化、飼料配合）。
• エネルギー（発電設備の負荷最適化）。

参考文献

• ダンツィグ G. B. 線形計画法、その応用と一般化. 1966.
• ユージン D. B., ゴリシュテイン E. G. 線形計画法（理論、手法、応用）. 1969.
• Taha, H. A. Operations Research: An Introduction. 10th ed. Pearson, 2017.
• Hillier, F. S., Lieberman, G. J. Introduction to Operations Research. 11th ed. McGraw-Hill Education, 2021.