Lineare Optimierung

Lineare Optimierung Definition

Hat man eine lineare Funktion mit mehreren Variablen, möchte diese optimieren – je nachdem: maximieren (z.B. Gewinn) oder minimieren (z.B. Zeitaufwand, Kosten) – und gibt es Nebenbedingungen für die Variablen, liegt ein Problem für die lineare Optimierung vor.

Alternative Begriffe: Lineare Programmierung, lineares Optimierungsproblem, lineares Programm.

Beispiel

Die Grundidee an einem Beispiel:

Beispiel: Lineare Optimierung

Ein Kiosk verkauft zwei etwas seltsame Produkte:

  • den K-Becher: ein Becher mit Zucker (1 Becher, 2 Zuckerwürfel) für Kaffeetrinker und
  • den T-Becher: ein Becher mit mehr Zucker (1 Becher, 4 Zuckerwürfel) für Teetrinker.

Den Kaffee oder Tee müssen die Kunden selbst mitbringen. Der Gewinn je K-Becher sei 2 € und je T-Becher 3 €. Der Absatz sei unbeschränkt (die Leute stehen Schlange).

k sei die verkaufte Menge K-Becher, t die verkaufte Menge T-Becher.

Die (lineare) Zielfunktion ist:

Z(k, t) = k × 2 € + t × 3 €.

und diese soll maximiert werden.

Gäbe es keine Beschränkungen, müssten möglichst viel K- und T-Becher "produziert" und verkauft werden, mit jedem Becher steigt der Gewinn.

Aber es gibt natürlich Beschränkungen (in der Realität z.B. Kapazitäts- oder Absatzbeschränkungen) und diese werden als Nebenbedingungen mit Ungleichungen erfasst:

k × 1 + t × 1 <= 3 (es gibt nur 3 Becher)

k × 2 + t × 4 <= 8 (es gibt nur 8 Zuckerwürfel).

Zudem müssen k und t >= 0 sein (es können keine negativen Mengen hergestellt und verkauft werden).

In dem Beispiel kann man die möglichen Kombinationen aus verkauften K- und T-Bechern noch abzählen (die erste Zahl steht für die Anzahl der K-Becher, die zweite Zahl für die Anzahl der T-Becher):

(0, 0) Gewinn ist 0 €

(0, 1) Gewinn ist 3 €

(0, 2) Gewinn ist 6 €

(0, 3) geht nicht (3 T-Becher würden 12 Zuckerwürfel benötigen)

(1, 0) Gewinn ist 2 €

(2, 0) Gewinn ist 4 €

(3, 0) Gewinn ist 6 €

(4, 0) geht nicht (nur 3 Becher vorhanden)

(1, 1) Gewinn ist 5 €

(1, 2) geht nicht (würde 10 Zuckerwürfel benötigen)

(2, 1) Gewinn ist 7 € (es werden die maximale Anzahl von Bechern und Zuckerwürfeln verbraucht).

Der Gewinn ist bei 2 K-Bechern und 1 T-Becher mit 7 € maximal.

Das Beispiel hat 2 Besonderheiten: erstens ist es sehr einfach, zweitens sind nur ganzzahlige Lösungen sinnvoll (Anzahl Becher, nicht Gramm, Milliliter usw., wo es viel mehr Möglichkeiten gibt); deshalb ist es eigentlich ein Sonderfall der linearen Optimierung (sogenannte ganzzahlige Optimierung).

Deshalb kann man lineare Optimierungsprobleme normalerweise nicht durch Aufzählung, sondern nur grafisch oder mit einem mathematischen Verfahren (Simplex-Algorithmus) lösen.