Ermittlung der Normalform

Ist eine Ecke von M bekannt, dann kann eine Normalform des linearen Optimierungsproblems wie folgt ermittelt werden. Man wählt eine zur Ecke gehörende Basis aus m Spalten von Im Normalfall sind diese Spalten durch die positiven Komponenten der Ecke festgelegt. Die Basisvariablen werden zum Vektor und die Nichtbasisvariablen zum Vektor zusammengefaßt. Die zur Basis gehörenden Spalten bilden die Basismatrix A, die restlichen Spalten die Matrix Dann gilt

Die Matrix ist regulär und besitzt die Inverse die sogenannte Basisinverse. Multiplikation von (18.9) mit und Umstellung der Zielfunktion nach den Nichbasisvariablen liefert eine kanonische Form des Linearen Optimierungsproblems:

Beispiel

Im obigen Beispiel ist eine Ecke. Somit ist

und

Es ergibt sich das System

Aus erhält man durch Subtraktion der mit 3 multiplizierten ersten Nebenbedingung eine auf Nichtbasisvariablen umgerechnete Zielfunktion