基本的な実行可能な解

以下の定義では、まず線形計画問題をいわゆる等式形式で示します。

最大化${\textstyle \mathbf {c^{T}} \mathbf {x} }$

対象${\displaystyle A\mathbf {x} =\mathbf {b} }$そして${\displaystyle \mathbf {x} \geq 0}$

どこ：

• ${\displaystyle \mathbf {c^{T}} }$そして${\displaystyle \mathbf {x} }$これらはサイズn（変数の数）のベクトルです。
• ${\displaystyle \mathbf {b} }$はサイズmのベクトル（制約の数）です。
• ${\displaystyle A}$これはm × n行列です。
• ${\displaystyle \mathbf {x} \geq 0}$これは、すべての変数が非負であることを意味します。

線形計画問題は、スラック変数を追加することで等式形式に変換できます。

予備的なクリーンアップ手順として、以下の点を確認します。

• システム${\displaystyle A\mathbf {x} =\mathbf {b} }$少なくとも1つの解が存在する（そうでなければ、線形計画問題全体に解がなく、それ以上何もすることがない）。
• 行列のすべてのm行${\displaystyle A}$は線形独立である、つまりランクはmである（そうでなければ、LPを変更せずに冗長な行を削除するだけでよい）。

線形計画法の実行可能な解は任意のベクトルである${\displaystyle \mathbf {x} \geq 0}$そのため${\displaystyle A\mathbf {x} =\mathbf {b} }$少なくとも1つの実行可能な解が存在すると仮定します。m = nの場合、実行可能な解は1つだけです。通常、m < nなので、システムは${\displaystyle A\mathbf {x} =\mathbf {b} }$線形計画問題には多くの解があり、そのような解はそれぞれ線形計画問題の実行可能解と呼ばれます。

LPの基底は、Aの非特異部分行列であり、すべての行がmで、列はm < nのみである。

場合によっては、「基底」という用語は部分行列自体ではなく、その列のインデックスの集合に対して使用されます。Bを{1,..., n }からのm個のインデックスの部分集合とします。${\displaystyle A_{B}}$m列からなる正方m × m行列${\displaystyle A}$Bでインデックス付けされています。${\displaystyle A_{B}}$は非特異であり、 Bでインデックス付けされた列は列空間の基底である。${\displaystyle A}$この場合、BをLPの基底と呼びます。

ランク以来${\displaystyle A}$mの場合、少なくとも 1 つの基底を持ちます。${\displaystyle A}$n列あり、最大${\displaystyle {\binom {n}{m}}}$基地。

基底Bが与えられたとき、実行可能な解は${\displaystyle \mathbf {x} }$は、そのすべての非ゼロ変数がBでインデックス付けされている場合、基底 B を持つ基本実行可能解である。つまり、すべての に対して${\displaystyle j\not \in B:~~x_{j}=0}$。

In practice, the easiest way to find an optimal BFS is to use the simplex algorithm. It keeps, at each point of its execution, a "current basis" B (a subset of m out of n variables), a "current BFS", and a "current tableau". The tableau is a representation of the linear program where the basic variables are expressed in terms of the non-basic ones:^[1]:65$${\displaystyle {\begin{aligned}x_{B}&=p+Qx_{N}\\z&=z_{0}+r^{T}x_{N}\end{aligned}}}$$where ${\displaystyle x_{B}}$ is the vector of m basic variables, ${\displaystyle x_{N}}$ is the vector of n non-basic variables, and ${\displaystyle z}$ is the maximization objective. Since non-basic variables equal 0, the current BFS is ${\displaystyle p}$, and the current maximization objective is ${\displaystyle z_{0}}$.

If all coefficients in ${\displaystyle r}$ are negative, then ${\displaystyle z_{0}}$ is an optimal solution, since all variables (including all non-basic variables) must be at least 0, so the second line implies ${\displaystyle z\leq z_{0}}$.

If some coefficients in ${\displaystyle r}$ are positive, then it may be possible to increase the maximization target. For example, if ${\displaystyle x_{5}}$ is non-basic and its coefficient in ${\displaystyle r}$ is positive, then increasing it above 0 may make ${\displaystyle z}$ larger. If it is possible to do so without violating other constraints, then the increased variable becomes basic (it "enters the basis"), while some basic variable is decreased to 0 to keep the equality constraints and thus becomes non-basic (it "exits the basis").

If this process is done carefully, then it is possible to guarantee that ${\displaystyle z}$ increases until it reaches an optimal BFS.

最悪の場合、シンプレックス法は完了までに指数関数的に多くのステップを必要とする可能性があります。楕円体法のように、線形計画問題を弱多項式時間で解くアルゴリズムも存在しますが、それらは通常、基本解ではない最適解を返します。

しかし、LPの任意の最適解が与えられた場合、基本でもある最適実行可能解を見つけるのは容易である。^{[ 2 ]：以下の「外部リンク」も参照。}

LP の基底Bは、解が${\displaystyle \mathbf {y_{B}} ={A_{B}^{T}}^{-1}\cdot c}$ は双対線形計画問題の最適解であり、すなわち、を最小化する。${\textstyle \mathbf {b^{T}} \mathbf {y} }$一般に、主問題最適基底は必ずしも双対問題最適基底とは限らず、双対問題最適基底も必ずしも主問題最適基底とは限らない（実際、主問題最適基底の解は双対問題では実行不可能な場合があり、その逆もまた然りである）。

両方${\displaystyle \mathbf {x_{B}} ={A_{B}}^{-1}\cdot b}$は主問題LPの最適BFSであり、${\displaystyle \mathbf {y_{B}} ={A_{B}^{T}}^{-1}\cdot c}$が双対LPの最適BFSである場合、基底BはPD最適と呼ばれます。最適解を持つすべてのLPにはPD最適基底があり、それはシンプレックス法によって見つけられます。ただし、最悪の場合、その実行時間は指数関数的になります。ニムロッド・メギドは次の定理を証明しました。^{[ 2 ]}

• 主問題である線形計画問題の最適解と双対問題である線形計画問題の最適解を入力として受け取り、最適基底を返す、非常に多項式時間で動作するアルゴリズムが存在する。
• 主LP（または双対LP）の最適解のみを入力として最適基底を返す強力な多項式時間アルゴリズムが存在するならば、任意の線形計画問題を解くための強力な多項式時間アルゴリズムが存在する（後者は有名な未解決問題である）。

メギドのアルゴリズムは、シンプレックス法と同様に、タブローを使用して実行できます。メギドはベリングと共同で、高速行列乗算アルゴリズムを使用する高速アルゴリズムも提案しました。^{[ 3 ]}