Formen von linearen Optimierungsproblemen

Lineare Optimierungsprobleme können in verschiedenen Formen vorliegen. Darunter fallen beispielsweise die Standardform, die Normalform oder auch die kanonische Form. Was man darunter jeweils versteht, wird nachfolgend erläutert.

Standardform

Liegt ein lineares Optimierungsprobleme in folgender Form vor:

P: max cTx s.t. Ax ≤ b, x ≥ 0
dann spricht man von der Standardform. Dabei ist c =(c1, c2 ... cn)T der Vektor der Zielfunktionskoeffizienten, x= (x1, x2 ... xn)T den Vektor der Entscheidungsvariablen und b=(b1, b2 ... bn)T den Vektor der Werte der rechten Seite. Aus dem Satz von Weierstraß folgt, dass ein lineares Optimierungsproblem in Standardform einen optimalen Punkt besitzt, unter der Voraussetzung, dass die Zielmenge M nichtleer und beschränkt ist.

Normalform

Aus der Standardform eines linearen Optimierungsproblems kann man nun durch die Einführung von zusätzlichen Variablen, den sogenannten Schlupfvariablen, die Ungleichungsrestriktionen der Nebenbedingungen zu Gleichungsbedingungen überführen. Dies geht vor allem dann recht einfach, wenn bei den Ungleichungsrestriktionen nur Nichtnegativitätsbedingungen auftreten. Die original Variablen des Problems nennt man dann auch Strukturvariablen. Die Koeffizientenmatrix A wird dazu um die (m,m)-Einheitsmatrix Im zu einer (m, n+m)-Matrix à = (A, Im erweitert. Man spricht also von der Normalform, wenn das lineare Optimierungsproblem in folgender Form vorliegt:

P: max cTx s.t. Ãx ≤ b, x ≥ 0

Kanonische Form

Unter der kanonischen Form versteht man einfach die Normalform mit der zusätzlichen Bedingung b ≥ 0.