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 x1 ≥ 0, …, xn ≥ 0.
Dabei ist A eine (m × n)-Matrix, p ∈ ℝn und b = (b1, …, bm)t mit b1 ≥ 0, …, bm ≥ 0. Gesucht ist dabei ein x = (x1, …, xn)t mit x1 ≥ 0, …, xn ≥ 0, das den Nebenbedingungen genügt und die Zielfunktion minimiert. Man sagt, das lineare Programm sei in kanonischer Form, wenn es m Variablen xi1, …, xim 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.
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.