spezielle Form eines linearen Programms. Probleme der linearen Optimierung schreibt man oft in Form eines linearen Programms

min p · x, NB A · x = b für x₁ ≥ 0, …, x_n ≥ 0.

Dabei ist A eine (m × n)-Matrix, p ∈ ℝⁿ und b = (b₁, …, b_m)^t mit b₁ ≥ 0, …, b_m ≥ 0. Gesucht ist dabei ein x = (x₁, …, x_n)^t mit x₁ ≥ 0, …, x_n ≥ 0, das den Nebenbedingungen genügt und die Zielfunktion minimiert. Man sagt, das lineare Programm sei in kanonischer Form, wenn es m Variablen x_i1, …, x_im gibt, die in jeweils genau einer Gleichung mit dem Koeffizienten 1 und in allen übrigen mit dem Koeffizienten 0 vorkommen, und wenn jede Gleichung eine solche Variable mit dem Koeffizienten 1 enthält. In diesem Fall läßt sich die Matrix A so umordnen, daß die m-reihige Einheitsmatrix als Untermatrix auftritt. Eine solche Darstellung der Matrix A ist von Bedeutung für die Durchführung des Simplexalgorithmus.