線形計画法：理論、手法、応用

数理的定式化と幾何学

標準形では、線形計画問題は、Ax ≤ b および x ≥ 0 という条件の下で c・x を最大化することを求める。ここで、x は変数ベクトル、c は目的関数の係数ベクトル、A は制約係数の行列、b は上限・下限を表すベクトルである。幾何学的には、線形計画問題の実行可能解の集合は、ユークリッド空間における凸多面体であり、有界の場合にはポリトープとなる。最適解が存在する場合、それはこの領域の極点、すなわち頂点で得られる。この結び付きにより、次元が小さい場合には幾何学的な直観や視覚的手法を利用できる。多面体の概念については多面体を、モデル化の方法については幾何学的最適化を参照されたい。

アルゴリズムと計算上の側面

実用的な線形計画法では、二つのアルゴリズム群が中心的な役割を果たす。ジョージ・ダンツィーグが開発した単体法は、実行可能多面体の頂点をたどって目的関数を改善する方法であり、最悪の場合の時間計算量は指数的であるにもかかわらず、実際にはしばしば非常に高速である。内点法は、実行可能領域の内部を通る経路に沿って最適解へ近づく手法であり、多項式時間の最悪時保証と、大規模な疎な問題における優れた性能で知られる。問題の規模が非常に大きい場合や構造をもつモデルでは、改訂単体法、バリア法、専用の分解手法も用いられる。異なる定式化やアルゴリズムの理論的複雑性は、計算複雑性およびアルゴリズム研究の文献で扱われている。

双対性、感度、拡張

すべての線形計画問題には対応する双対問題があり、その最適値は元の主問題の目的値に境界を与える。緩やかな条件の下では、両者の値は一致する。双対性理論は、経済学的な解釈である影の価格、最適性の証明、およびデータが摂動したときに解がどのように変わるかを示す感度分析のための手段を与える。線形計画法は凸最適化の特殊な場合であり、整数性制約を加えた整数計画法および混合整数計画法の基礎となる。他分野や他手法との関連は、線形不等式を扱う文献や凸解析の文献・概説に示されている。

歴史と発展

現代的な線形計画法は20世紀半ばに形づくられた。レオニード・カントロヴィチによる初期の理論研究は広範な採用に先行しており、ジョージ・ダンツィーグは資源配分問題に取り組む中で「線形計画法」という用語を普及させ、単体法を開発した。「プログラミング」という名称はコンピュータのコードではなく、計画と配分を意味していた。第二次世界大戦後の電子計算機の発展により、大規模な問題を数値的に解くことが可能になった。こうした発展の背景は、カントロヴィチおよびダンツィーグに関する歴史的概説と伝記によって理解できる。

応用、ツール、主な特徴

線形計画法は、輸送・物流、生産計画、労働力スケジューリング、ポートフォリオ最適化、ネットワークフローなど、線形モデルが適切な多くの分野で応用される。実務での実装は、単体法や内点法を実装した専用ソルバーに依存している。現代のパッケージは大規模で疎な連立系を扱い、速度向上のために問題の構造を活用する。入門的な解説とソフトウェアに関する参照先として、単体法、オペレーションズ・リサーチのガイド、内点法のアルゴリズム概説がある。モデル化の実践と多面体理論については、計算最適化の集成にある幾何学や、応用最適化の文献における複雑性も参照できる。

• 主な長所：明確な理論的基盤、広い適用範囲、充実したソルバー環境。
• 限界：扱えるのは線形関係に限られ、多くの実務問題では整数または非線形への拡張を必要とする。
• 関連分野：整数計画法、凸最適化、ネットワーク最適化。入門的な参考文献として線形不等式、歴史的説明として用語の由来を参照。