Eigenschaften linearer Optimierungsprobleme

An Hand des obigen Beispiels können einige Eigenschaften linearer Optimierungsprobleme graphisch veranschaulicht werden. Dazu kann auf die Einführung von Schlupfvariablen verzichtet werden.

1. Eine Gerade a₁x₁ + a₂x₂ = b teilt die x₁,x₂-Ebene in zwei Halbebenen. Somit liegen alle Punkte , die die Ungleichung erfüllen, auf dieser Geraden bzw. in einer der Halbebenen. Die graphische Darstellung der Punktmenge in einem kartesischen Koordinatensystem erfolgt durch Einzeichnen der trennenden Geraden, und die Halbebene, die die Lösungsmenge der Ungleichung enthält, wird mit Pfeilen gekennzeichnet. Die Ausführung der graphischen Darstellung aller Nebenbedingungen liefert eine Menge von Halbebenen, deren Durchschnitt den zulässigen Bereich M bildet (s. Abbildung).
   

   

   Im Beispiel oben bilden die Punkte von M eine Polygonfläche. Es kann auch vorkommen, daß M unbeschränkt oder leer ist. Treffen in einer Ecke des Polygons mehr als zwei begrenzende Geraden aufeinander, dann spricht man von einer entarteten Ecke (s. folgende Abbildung).

   

2. Alle Punkte in der x₁,x₂-Ebene, die der Beziehung f(x) = 20x₁ + 60x₂ = c₀ genügen, liegen auf einer gemeinsamen Geraden, der Niveaulinie zum Funktionswert . Bei verschiedener Wahl von c₀ wird eine Schar paralleler Geraden definiert, auf denen der Zielfunktionswert jeweils konstant ist. Geometrisch sind alle diejenigen Punkte Lösungen des Optimierungsproblems, die sowohl zum zulässigen Bereich M als auch zu einer Niveaulinie 20x₁ + 60x₂ = c₀ mit einem maximalen c₀ gehören. Im konkreten Fall ergibt sich auf der Niveaulinie 20x₁ + 60x₂ = 2600 der Maximalpunkt (x₁,x₂) = (25;35). Die Niveaulinien sind in der folgenden Abbildung dargestellt, wobei die Pfeile in die Richtung wachsender Funktionswerte zeigen.
   

   

   Man erkennt, daß bei beschränktem zulässigen Bereich M das Maximum in mindestens einer Ecke von M eingenommen wird. Dagegen ist bei unbeschränktem M denkbar, daß der Zielfunktionswert gegen unendlich strebt.