Das Standardwerk:

Lineare Optimierung

Ein Rezeptbuch

2 Aufgabenstellung

Dem Leser, der Leserin dürfte bekannt sein, dass die praktische Anwendung der Mathematik darin besteht, Lösungen für Probleme zu finden, die sich der unmittelbaren Anschauung entziehen. Diese Probleme werden in die Symbolsprache der Mathematik übersetzt. Es entstehen Gleichungen -- oder unangenehmer: Un-Gleichungen. Die Un-Gleichungen werden dann nach bestimmten logischen (und damit beweisbaren) Gesetzen umgeformt, so dass sie eine Form annehmen, aus der die Lösung des Problems ablesbar wird. Konsequentes Befolgen der Regeln dieses Denksystems ist, eben wegen der im Allgemeinen fehlenden Anschaulichkeit, unabdingbare Voraussetzung zur Lösung der Aufgaben.

Nicht jedes Problem hat genau eine Lösung. Für manche Probleme gibt es nur eine leere (umgangssprachlich: 'keine') Lösung, Andere wiederum haben mehrere Lösungen. So kann z.B. die Frage 'mit welchem Transportmittel bewege ich mich von Ort A nach Ort B?' (auch ohne mathematische Behandlung), auf verschiedenerlei Art beantwortet werden. In Betracht kämen etwa ein Fahrrad oder ein Auto. Aber nicht jede Antwort ist gleichermaßen 'gut'. Das Fahrrad wäre sicher die billigere, das Auto (bei großen Entfernungen) die schnellere Lösung. Es taucht also die Frage auf: 'Was ist gut, was ist besser?' In diesem Beispiel mag die Forderung lauten, möglichst schnell, das heißt: in kurzer Zeit zum Ziel zu kommen. Hier gibt es eine mathematisch beschreibbare Größe (die Fahrzeit), die den Besten aller möglichen Werte (das Optimum) annehmen soll. Da die Fahrzeit von vielen Einflüssen abhängt, also veränderlich (variabel) ist, und es das Ziel sein soll, diese Größe möglichst optimal werden zu lassen, heißt die, diese Größe beschreibende Gleichung: Zielfunktion.

Doch damit nicht genug: Die 'beste' Fahrzeit wäre sicher die Fahrzeit Null. In dieser Zeit ist aber der Zielort nicht zu erreichen. Eine wesentliche Forderung ist es, eben diesen Ort anzufahren. Eine bestimmte Entfernung ist zurückzulegen. Möglicherweise existieren mehrere Wege von Ort A zum Ort B mit unterschiedlichen Längen. Es könnte sein, dass der Weg mit kürzester Fahrzeit (Schnellstraße) der längste Weg ist. Besteht nur die Forderung, eine möglichst kurze Fahrzeit zu erreichen, gibt es keinen Zweifel über die richtige Wegentscheidung. Aber eine Zusatzforderung könnte sein, höchstens eine bestimmte Menge Kraftstoff zu verbrauchen. Der Kraftstoffverbrauch steigt mit zunehmender Geschwindigkeit, so dass eventuell die Schnellstraße nicht, oder nur teilweise befahren werden kann. Die Frage nach der Besten aller Lösungen ist also nur sinnvoll, wenn es Einschränkungen bezüglich der Entscheidungsmöglichkeiten gibt.

Das heißt: Ein Optimierungsproblem besteht immer aus zwei Grundelementen: Der Gleichung für die zu optimierende Größe (Zielfunktion) und den Einschränkungen, die zusammen ein Un-Gleichungssystem bilden. Hinzu kommen noch, durch die mathematische Methodik bedingte Forderungen bezüglich der Struktur des Systems von Un-Gleichungen. Für das in diesem Buch beschriebene Verfahren gelten die Forderungen:

• jede veränderliche Größe (Variable) muss positiv oder Null sein (Nichtnegativitätsbedingung)
• alle Un-Gleichungen müssen linear sein

Die Nichtnegativitätsbedingung ist immer erreichbar (siehe Abschnitt 3.2).

Der Begriff der Linearität soll hier noch kurz (und etwas vereinfacht) erläutert werden: Kommen in einer Un-Gleichung nur die Operationen +; -; * vor, so heißt diese Un-Gleichung linear. Eine variable Größe steht also z.B. niemals im Nenner eines Bruches oder unter einer Wurzel, hingegen kann sie mit beliebigen unveränderlichen (konstanten) Ausdrücken multipliziert oder zu ihnen addiert werden. Ein konstanter Bruch darf also mit einer Variablen multipliziert werden, jedoch darf die Variable nicht selbst Teil des Bruches sein. Wird eine Variable mit einem konstanten Ausdruck multipliziert, ändert sich je nach Größe der Konstanten, die 'Wichtigkeit' dieser Variablen. Ein konstanter Faktor vor einer Variablen heißt, da er zusammen mit der Variablen wirkt: Koeffizient.

Da der Name einer Variablen (z.B.: x₂) natürlich keinen Einfluss auf die Lösung der gestellten Aufgabe hat, kommt es bei Berechnungen ausschließlich auf die Größe der Koeffizienten an. Die Struktur des linearen Un-Gleichungssystems ist stets die Gleiche, daher lässt sich ein allgemeines Schema (ein Algorithmus) zum Lösen solcher Un-Gleichungssysteme angeben. In diesem Algorithmus brauchen dann nur die Koeffizienten betrachtet werden.

Unter Berücksichtigung beschränkter Ressourcen, Transport- oder Produktionskapazitäten o.Ä. soll eine über eine lineare Gleichung gegebene Größe, z.B. Gewinn, Transportmenge, optimiert werden. Gesucht ist also entweder ein Maximum oder ein Minimum.

Es existieren Einschränkungen bezüglich einer bestimmten Anzahl variabler Größen (im Folgenden mit x₁... x_n bezeichnet), die im Allgemeinen in Un-Gleichungsform vorliegen.

Alle Variablen sind positiv oder Null (Nichtnegativitätsbedingung).

Die zu optimierende Größe (im Folgenden mit z bezeichnet) ist eine Funktion (Zielfunktion) der Variablen x₁... x_n.

Das Un-Gleichungssystem hat also stets die Form:

2.1.1 Maximum-Optimierung:

2.1.2 Minimum-Optimierung:

Letzte Änderung 2007-08-18