線形計画法、さまざまな制約を受けたときに線形関数が最大化または最小化される数学的モデリング手法。この手法は、ビジネスプランニング、産業工学、そして程度は低いが社会科学や物理科学において、定量的な決定を導くのに役立ちました。
最適化：線形計画法
現在、日常の意思決定問題を解決するために広く使用されていますが、線形計画法は1947年までは比較的知られていませんでした。
。
線形計画問題の解法は、線形式（目的関数と呼ばれる）の最適値（問題に応じて最大または最小）を見つけることになります。
不等式として表される一連の制約の対象：
a、b、およびcは、問題の容量、ニーズ、コスト、利益、およびその他の要件と制限によって決定される定数です。この方法を適用する際の基本的な前提は、需要と可用性の間のさまざまな関係が線形であることです。つまり、x iは1以外の累乗にはなりません。この問題の解を得るには、線形不等式のシステム（つまり、n個の値のセット）の解を見つける必要があります。すべての不等式を同時に満たす変数x i）。次に、fを定義する方程式にx iの値を代入して目的関数を評価します。
線形計画法の適用は、1930年代後半にソビエトの数学者レオニードカントロビッチとアメリカの経済学者ワシリーレオンティエフによって製造スケジュールと経済学の分野でそれぞれ真剣に最初に試みられましたが、彼らの研究は数十年間無視されました。第二次世界大戦中、コストや可用性などの特定の制限の対象となる輸送、スケジューリング、リソースの割り当てを処理するために、線形計画法が広く使用されました。これらのアプリケーションは、この方法の受容性を確立するために多くのことを行い、1947年にアメリカの数学者George Dantzigのシンプレックス法の導入によりさらなる推進力を得て、線形計画問題の解決を大幅に簡素化しました。
しかし、より多くの変数を含むますます複雑な問題が試行されるにつれて、必要な操作の数は指数関数的に拡大し、最も強力なコンピューターの計算能力を超えました。その後、1979年に、ロシアの数学者Leonid Khachiyanが多項式時間アルゴリズムを発見しました。これにより、計算ステップの数は指数関数的ではなく変数の数の累乗として増加します。これにより、これまでアクセスできなかった問題の解決が可能になります。ただし、実際に適用された場合、Khachiyanのアルゴリズム（楕円体法と呼ばれる）は、シンプレックス法よりも低速でした。1984年にインドの数学者Narendra Karmarkarは、シンプレックス法との競争力を証明する別の多項式時間アルゴリズムである内点法を発見しました。
