線形計画法とは
線形計画法（LP：Linear Programming）とは、いくつかの制約条件がある中で、利益を最大にしたり、コストを最小にしたりするための最適な組み合わせを数学的に導き出す手法です。主にビジネスの意思決定や工場の生産管理などで使われます。
「線形」とは、グラフに描くと直線になるような関係（比例関係）を意味します。例えば「製品Aを1個作ると利益が100円、製品Bを1個作ると利益が150円」といった関係です。ここに「材料の量に上限がある」「作業時間に限界がある」といった複数の制約を一次方程式（直線）で表し、それらの直線で囲まれた範囲の中から、利益が最も大きくなる組み合わせ（交点）を計算によって見つけ出します。
具体例
あるパン屋さんが、食パン（利益200円、小麦粉100g使用）とクロワッサン（利益150円、小麦粉50g使用）を作るとします。使える小麦粉が全部で10kg（10,000g）まで、作業時間が合計で8時間までという制限がある中で、「それぞれ何個ずつ作れば、最も売り上げを高くできるか」を割り出すときに線形計画法が使われます。
もう少し詳しく
線形計画法において、制約条件と目的関数（最大化または最小化したい利益やコストを表す式）は、すべて一次方程式または一次不等式（線形）で表されます。変数（例えば製品の製造個数など）が2つの場合は、二次元のグラフ上に制約条件を示す直線を書き、それらの共通部分として得られる多角形（実行可能領域）の頂点（交点）のいずれかで目的関数が最大または最小になるという性質を利用して解くことができます。しかし、変数が3つ以上になるとグラフで視覚的に解くことが難しくなるため、数学的なアルゴリズムである「シンプレックス法（単体法）」などが用いられます。シンプレックス法は、実行可能領域の頂点を順に探索し、最も条件の良い頂点へ効率的にたどり着く手法であり、現代のコンピュータによる大規模な最適化計算の基礎となっています。
試験でのポイント
試験では、与えられた文章題から適切な不等式（制約条件）と等式（目的関数）を組み立てる能力が問われます。また、グラフが示され、実行可能領域のどの交点が最適解（利益が最大になる点など）であるかを判定させる問題もよく出題されます。注意すべき点として、変数が「製品の個数」などの場合は整数でなければならない（整数計画法と呼ばれる別の分野になる）のですが、基本情報や応用情報の範囲では一般的な実数としての線形計画法として出題されることが多いです。ただし、問題文の条件（「製品Aは最大でも〇個までしか売れない」といった隠れた制約）を見落とさないように注意深く数式を立てる必要があります。
関連する用語
線形計画法に関連する最適化手法としては、変数が整数に限定される「整数計画法」や、目的関数や制約条件に非線形（二次式など）の式が含まれる「非線形計画法」があります。また、プロジェクトの工程管理で最短経路やクリティカルパスを求める「PERT（アローダイアグラム）」や、限られた資源を最適に配分する意思決定モデル全般を扱う「オペレーションズ・リサーチ（OR）」も、線形計画法を包含する重要な関連分野です。