90. Jahresbericht des Bundes-Realgymnasiums Steyr 1972/73

8. Lineare Optimierung Die lineare Optimi erung (auch als l ineare Programmierung oder operations research bezeichnet) entstand aus pral<t ischen Problemste l lungen der Betriebs- und Volkswirtschaft. Es handelt sich darum, aus einer Vielzahl von Varianten der Produkt ion die ökonomi sch günstigste auszuwählen. Nachdem im Jahre 1939 von dem russischen Mathematiker Kantorowitsch erstmals eine mathema- tische Methode zur Lösung einer Klasse von Produktionsproblemen entw'ik- kelt wurde, ging die Entwick lung dieses modernen Teilgebietes der Mathe- matik rasch vor sich. Während des 2. Weltkrieges waren es in erster Linie militärische Aufgaben , nach dem Kriege gab 1947 Dantzig das klassisch e Verfahren zur Lösung von Optimierungsaufgaben an, die Si m p I ex- m et h o de. Im 2. Abschnitt dieser Arbeit werden nun einige der wichtigsten Grundlagen der Linearolanung behandelt. a) LINEARE UNGLEICHUNGSSYSTEME IN 2 VARIABLEN Jede Ungleichung in 2 Variablen läßt sich auf die Form bringen ax + by ;;;; c Dabei sind a, b, c E R und (a, b) =!= (0, 0) Die Grundmenge ist die Menge der ree ll en Zahlen . Zur gegebenen Ungl e i- chung gehört die Gleichung : ax + by = c Diese tei lt d ie x-y- Ebene in 2 Halbebenen. Die Lösungsmenge umfaßt alle Punkte einer Halbebene ohne bzw. mit Einschluß der Randgeraden , je nach- dem ax + by < c oder ax + by :;;; c. Um festzustellen, welche der beiden Halbebenen in Frage kommt, genügt es, einen Punkt, z. B. 0 (0, 0) einzu- setzen und die Erfüllung der Ungleichung zu prüfen . B e i s p i e 1: 2x - 3y :;;; 3 Die Lösungsmenge ist in diesem Fall die linke Halbebene denn das Einsetzen der Koordinaten des Ur- sprunges führt auf O < 3 (siehe nebenstehende Figur) . Wenn mehrere li neare Ur.gleichungen vorliegen , die gleichzeitig erfüllt sein sollen , sprechen wir von einem linearen Ungleichungssystem. Die allgemeine Form lautet: a,x + b,y :;;; c, a,x + b,y :;;; c2 Die Lösu ngsmenge desselben ist der Durchschnitt · · · · · der Lösungsmengen der einzelnen Ungleichungen. an x + b y :-::;: c Die verschiedenen Möglichkeiten, die dabei auftre- n - n ten können, sind in den nachstehenden Figuren für 3 Ungleichungen dargeste ll t, wobei die schraffierten Halbebenen jeweils die Lösungsmengen der einzelnen Ungleichungen sind. 19