線型計画法
の下、次式
c 1 x 1 + c 2 x 2 {\displaystyle c_{1}x_{1}+c_{2}x_{2}\ }
の最大値およびそれを実現する x 1 {\displaystyle x_{1}\ } と x 2 {\displaystyle x_{2}\ } を求める問題が、典型的な線型計画問題である。
3変数 x 1 {\displaystyle x_{1}\ } 、 x 2 {\displaystyle x_{2}\ } 、 x 3 {\displaystyle x_{3}\ } の場合、3次元座標空間上に描かれた立体図形を切るような平面のうち、 x 3 {\displaystyle x_{3}\ } 切片(平面と x 3 {\displaystyle x_{3}\ } 軸との交点)の値が最大あるいは最小となるような平面を求めることになる。
最適解の取り得る範囲を整数に限定した線型計画法は、整数計画法と呼ばれる。
幾何学的には線型(不)等式制約は実行可能領域(英語版)と呼ばれる凸多面体を定義する。目的関数も線型なので、全ての局所最適解はおのずと(大域的)最適解になる。線型な目的関数であることによって、必然的に最適解は実行可能領域の境界上のみに現れる。
最適解が見つからない状況が2つある。1つは互いに矛盾のある制約(例えば、 x ≥ 2 {\displaystyle x\geq 2} と x ≤ 1 {\displaystyle x\leq 1} )ならば実行可能領域は空になり、最適解は存在しえない。最適解が得られないのでこの場合はLPは実行不能と呼ばれる。
もう1つの状況は、多面体が目的関数の向きに境界を持たない場合(例:最大化: x 1 + 3 x 2 {\displaystyle x_{1}+3x_{2}\ } 制約: x 1 ≥ 0 , x 2 ≥ 0 , x 1 + x 2 ≥ 10 {\displaystyle x_{1}\geq 0,x_{2}\geq 0,x_{1}+x_{2}\geq 10} )である。この場合、目的関数はいくらでも大きい値を取り得る。
これらの2つの正常ではない条件(これらは多くの場合は上限を設けるなど問題の不可欠な制約によって除外される)がなければ、最適解は必ず多面体の頂点(正確には最小次元面)にある。しかしながら最適解は唯一とは限らない。多面体の辺や面が最適解の集合となる事があるし、最適解が多面体の全体となる(目的関数が一律に0に等しいときに現れる)ことすらある。