lineare Optimierung

lineare Planungsrechnung, lineare Programmierung, Linear Programming.

Allgemein

1. Begriff: Teilgebiet des Operations Research (OR), das sich mit dem theoretischen Hintergrund, der Modellierung mit und der Lösung von mathematischen Optimierungssystemen der Form

Bild in Originalgröße zeigen

befasst. In dem linearen Optimierungsproblem (1)-(3) gehören die Parameter c₁, c₂, ... ,c_n, a₁₁, a₁₂, ... , a_mn, b₁, b₂, ... , b_{m zur} Zielfunktion, Koeffizientenmatrix bzw. "rechten Seite"; die Variablen x₁, x₂, ..., x_n sind so zu bestimmen, dass sämtliche Restriktionen von (2) erfüllt sind, und die Zielfunktion (1) maximiert oder minimiert wird.

Die Lösungsmenge beschreibt ein Polyeder. Jeder Lösung aus dieser Lösungsmenge ist durch die Zielfunktion eine Zahl x₀ (Zielfunktionswert) zugeordnet, die in Verbindung mit einer der Vorschriften von (3) (Zielvorschrift) eine Beurteilung der Güte der betreffenden Lösung erlaubt. Die Zielvorschrift x₀ → Max! besagt dabei, dass eine Lösung mit einem größeren Zielfunktionswert besser ist als jede andere Lösung mit einem kleineren Zielfunktionswert. Eine solche Lösung nennt man optimal.

Der Begriff linear erklärt sich dadurch, dass die Zielfunktion (1) und sämtliche Restriktionen (2) linear sind (lineare Zielfunktion, lineare Restriktionen).

Es ist bekannt, dass für ein lineares Optimierungsproblem genau eine der drei Alternativen gilt: (a) das Problem ist unbeschränkt, d.h. zu jeder zulässigen Lösung findet man stets eine zulässige Lösung mit besserem Zielfunktionswert, oder (b) das Problem ist unzuläassig, d.h. es existiert überhaupt keine Lösung, die alle Restriktionen erfüllt, oder (c) es existiert eine optimale Lösung mit endlichem Zielfunktionswert. Im Fall (c) wird der optimale Zielfunktionswert in einer Ecke des Lösungspolyeders angenommen, von denen es nur endlich viele gibt und was das sog. Simplexverfahren nahe legt.

Grundlegende Fragestellungen

1. Optimale Lösung: Im Zusammenhang mit linearen Optimierungsproblemen drängt sich die Frage auf, welche Lösung von (2) den durch (1) definierten Zielwert x₀ maximiert (oder minimiert) bzw. wie man ggf. erkennt, dass eine solche optimale Lösung nicht existiert. Zur Beantwortung derartiger Fragen wurden eine ganze Reihe von Verfahren (Simplexmethode, Innere-Punkte-Verfahren, Ellipsoid-Methode) entwickelt und in entsprechende Standardsoftware eingebettet, die geeignet ist, auch sehr große Probleme der Praxis (d.h. Probleme mit vielen Variablen und Restriktionen) zu lösen.

2. Beim Einsatz linearer Optimierungsprobleme in der Praxis besteht häufig Ungewissheit über die tatsächlichen numerischen Werte der Koeffizienten c₁, ..., c_n, a₁₁, ..., a_mn, b₁, ..., b_m; z.T. ist sogar unklar, ob bestimmte Restriktionen von (2) überhaupt auftreten. Wie man im Hinblick auf derartige Situationen – ausgehend von einer ersten optimalen Lösung – auf einem möglichst einfachen Wege Alternativrechnungen (postoptimale Rechnungen) durchführen kann, ist eine weitere Problemstellung.

3. Vor dem gleichen Hintergrund untersucht man im Rahmen von Sensitivitätsanalysen, wie sich bestimmte Koeffizienten (v.a. die Koeffizienten c₁, ..., c_n der Zielfunktion (1) bzw. die rechten Seiten b₁, ..., b_m der Restriktionen (2)) ändern dürfen, ohne dass eine gefundene optimale Lösung (bzw. eine gefundene kanonische Form des Optimierungssystems) die Eigenschaft der Optimalität verliert.

4. Die parametrische lineare Optimierung befasst sich mit der noch erweiterten Fragestellung, welche optimalen Lösungen sich jeweils ergeben, wenn gewisse Koeffizienten (Koeffizienten der Zielfunktion und/oder die rechten Seiten der Restriktionen) in Abhängigkeit von einem oder mehreren Parametern schwanken können.

5. Die Dualitätstheorie der linearen Optimierung untersucht den Zusammenhang zwischen gewissen Paaren von linearen Optimierungssystemen. Ihre Erkenntnisse sind für die Entwicklung von Rechenverfahren von Bedeutung.

6. Die bei Anwendung in der Praxis vorkommenden linearen Optimierungssysteme sind i.d.R. sehr groß (Millionen Variablen, hundertausende Restriktionen), lassen sich aber i.A. relativ schnell optimal lösen. 

Spezielle Strukturen

Optimierungssysteme der Praxis zeichnen sich i.d.R. nicht nur durch dünn besetzte Koeffizientenmatrizen aus (d.h. nur verhältnismäßig wenige von null verschiedene Koeffizienten), diese sind außerdem oft nach einem gewissen Schema angeordnet, z.B. weil nicht alle Variablen in allen Restriktionen auftauchen. Derartige speziell strukturierte Systeme ergeben sich etwa bei der mathematischen Formulierung von Transportproblemen und Zuordnungsproblemen, von Wege- und Flussproblemen in Graphen (Netzplantechnik). Sie lassen sich mit traditionellen Simplexmethoden lösen, daneben gibt es aber Lösungsverfahren, die durch eine Ausnutzung der jeweiligen speziellen Koeffizientenstruktur erhebliche Vorteile in Bezug auf Rechenzeit und Speicherbedarf erzielen.

Erweiterungen

Durch bestimmte Umformungen und Techniken lassen sich die Methoden der linearen Optimierung z.T. auch zur Untersuchung von Fragen über solche Optimierungssysteme einsetzen, deren Struktur nur unvollständig mit der des Systems ((1), (2)) übereinstimmt:

1. Gewisse (d.h. mind. eine, möglicherweise aber auch alle) Variablen dürfen nur ganze Zahlen (ganzzahliges Optimierungsproblem) bzw. nur die Werte Null oder Eins annehmen (binäres Optimierungsproblem).

2. Gewisse Probleme der nicht-linearen Optimierung lassen sich ebenfalls mit linearen bzw. geringfügig modifizierten linearen Methoden lösen. Hierzu gehört u.a. die Bestimmung von optimalen Lösungen für quadratische Optimierungsprobleme und bestimmte separable Optimierungsprobleme.

3. Im Rahmen der linearen Optimierung bei mehrfacher Zielsetzung stehen solche linearen Optimierungssysteme im Mittelpunkt, bei denen den Lösungen des Restriktionssystems (2) anhand verschiedener Zielfunktionen gleichzeitig mehrere Zielwerte zugeordnet sind. Nur in ganz seltenen Ausnahmefällen existiert jetzt noch eine Lösung, die im Hinblick auf alle Zielfunktionen und -vorschriften gleichzeitig optimal ist. Die für diese Optimierungssysteme entwickelten Verfahren bezwecken deshalb nicht die Ableitung einer in diesem Sinn idealen Lösung, sondern es geht vielmehr um die Ableitung von allen oder einigen effizienten Lösungen bzw. bei interaktiven Verfahren um die Ermittlung einer für den Entscheidungsträger akzeptablen Kompromisslösung.

Ökonomische Anwendung

Von allen Methoden des Operations Research haben diejenigen der linearen Optimierung (neben denen der Netzplantechnik) die weiteste Verbreitung in der ökonomischen Praxis gefunden und sich bewährt. Empirischen Untersuchungen zufolge liegen ihre Einsatzschwerpunkte in der Grundstoff-, der chemischen, der Eisen- und Stahl- sowie der Nahrungs- und Genussmittelindustrie. Bez. der betrieblichen Funktionsbereiche sind in erster Linie Anwendungen im Produktionsbereich (zur Lösung von Problemen der Produktionsprogrammplanung, Produktionssteuerung und Zuschnittplanung), im Absatzbereich (Transportproblem), in der Lagerhaltung (Bestimmung optimaler Lagerbestände) sowie im Beschaffungsbereich (Transportproblem, Mischungsproblem, Bestellmengenproblem) anzuführen.

In stärkerem Maße setzen sich schließlich auch integrierte Modelle zur simultanen Planung verschiedener Funktionsbereiche (Produktions- und Absatzbereichs) durch.