Lineare Programmierung

Der Bedarf und die verfügbaren Kapazitäten werden durch ein System von Gleichungen und Unglei­chungen mit entsprechenden Randbedingungen beschrieben. Das bekannteste Verfahren, das eine itera­tive Vorgehensweise benutzt, ist unter dem Begriff Simplex-Methode bekannt.

(LP). Verfahren des Operations Research zur Berechnung von Extremwerten (Maxima, Minima) einer linearen Funktion, wobei Nebenbedingungen in Form linearer Ungleichungen vorgegeben sind. Beispiele sind die Bestimmung des maximalen Gewinns bei der Verteilung von Finanzmitteln auf verschiedene Verwendungen oder die kostengünstigste Belegung einer Maschine. Beispiel für die L. bei zwei Variablen: Zur Fertigung zweier Produkte P1 und P2 müssen 4 Maschinen A, B, C, D benutzt werden. Die zur Herstellung für eine Einheit benötigten Maschinenzeiten (in Stunden) seien in der nachfolgenden Tabelle zusammengestellt. In der letzten Spalte sind ferner die insgesamt zur Verfügung stehenden Maschinenstunden (Kapazität) angegeben.            


Von dem Produkt P1 sollen x1 Einheiten, von P2 insgesamt x2 Einheiten hergestellt werden. Wg. der begrenzten Maschinenkapazitäten müssen für die Mengen x1 und x2 folgende Ungleichungen erfüllt sein: 1)      2x1 +   3x2 £ 180; 2)      2x1 + 1,5x2 £ 150; 3)                  3x2 £ 120; 4)                  2x1 £ 190; 5)             x1 ³ 0; x2 ³ 0  (Nichtnegativitätsbedingungen). Wählt man in 1) - 4) das Gleichheitszeichen, so erhält man die 4 Geraden g1, g2, g3, g4. Alle Punkte, die alle Ungleichungen erfüllen, müssen unterhalb oder auf den Geraden g1, g2, g3, links von g4 und wg. 5) im ersten Quadranten liegen. Als Lösungsmenge von
(1) erhält man das in der Abb. schraffierte Fünfeck, den sog. zulässigen Bereich Z.                        


Eine Mengeneinhheit des Produkts P1 soll 200 EUR, eine Einheit von P2 dagegen 500 EUR Gewinn bringen. Dann ist die Gewinnfunktion             z = f(x1, x2) = 200x1 + 500x2                       
(2) linear in x1 und x2. Zur Bestimmung des maximalen Gewinns sind unter allen Punkten aus dem zulässigen Bereich Z diejenigen zu bestimmen, für welche die sog. Zielfunktion
(2) maximal wird. Alle Punkte, für die der Gesamtgewinn 10000 EUR beträgt, erfüllen die Gleichung          200x1 + 500x2 = 10.000 Diese Gerade ist in Bild 1 eingezeichnet. Alle Punkte mit z=c (konstanter Gewinn c) liegen auf Geraden, die zu dieser eingezeichneten Geraden parallel sind. Parallelverschiebung dieser Geraden nach oben bedeutet Gewinnvergrößerung. Somit muß diese Gerade so weit nach oben parallel verschoben werden, bis sie den zulässigen Bereich Z gerade noch berührt. Als Lösung erhält man den Punkt P3 als Schnittpunkt der Geraden g1 und g3. Für seine Koordinaten gelten die Bestimmungsgleichungen             2x1 + 3x2 = 180                     3x2 = 120 mit den Lösungen             x1 = 30; x2 = 40 Der maximale Gewinn beträgt z = 200 * 30 + 500 * 40 = 26.000 EUR Da dieser Punkt auf den Geraden g1 und g3 liegt, müssen die Kapazitäten der Maschinen A und C voll ausgenutzt werden, die Kapazitäten von B und D dagegen nicht.