This is documentation for Mathematica 4, which was
based on an earlier version of the Wolfram Language.
View current documentation (Version 11.2)

 Documentation /  Mathematica /  Das Mathematica Buch /  Höhere Mathematik in Mathematica /  Numerische Operationen mit Funktionen /

Numerische MinimierungFortgeschrittenes Thema: Funktionen mit sensitiver Abhängigkeit von ihrer Eingabe

3.9.9 Lineare Optimierung

FindMinimum kann lokale Minima für beliebige Funktionen finden. Beim Lösen von Optimierungsaufgaben ist es jedoch häufig wichtig, globale Maxima und Minima ermitteln zu können.

Für lineare Funktionen läßt sich diese Aufgabe mit der linearen Optimierung lösen. Im englischen Sprachraum wird sie häufig auch als lineare Programmierung bezeichnet. Diese ermöglicht im allgemeinen, unter einem Satz Nebenbedingungen (Restriktionen), die durch lineare Ungleichungen definiert sind, das globale Minimum oder Maximum jeder linearen Funktion zu finden.

Für eine Funktion von Variablen definieren die Nebenbedingungen im Grunde ein zulässiges Gebiet im -dimensionalen Raum. Jede lineare Ungleichung beschreibt eine Ebene im -dimensionalen Raum, die eine Seitenfläche des Bereichs bildet.

Lösen von Aufgaben der linearen Optimierung

Die Funktionen ConstrainedMax und ConstrainedMin erlauben Ihnen, eine zu maximierende oder zu minimierende Zielfunktion sowie einen Satz linearer Nebenbedingungen für die Variablen anzugeben. Mathematica geht immer davon aus, daß die Variablen auf nichtnegative Werte eingeschränkt sind.

Der Maximalwert von wird in diesem Fall bei und angenommen.

In[1]:= ConstrainedMax[x + y, {x < 1, y < 2}, {x, y}]

Out[1]=

Mathematica geht davon aus, daß und auf nichtnegative Werte beschränkt sind.

In[2]:= ConstrainedMin[x + y, {x < 1, y < 2}, {x, y}]

Out[2]=

Dies ist ein etwas komplizierteres Problem der linearen Optimierung.

In[3]:= ConstrainedMax[17x - 20y + 18z,
{x - y + z < 10, x < 5, x + z > 20}, {x, y, z}]

Out[3]=

In Aufgaben der linearen Optimierung können Sie sowohl exakte als auch Gleitpunktzahlen als Koeffizienten eingeben. Sind die gegebenen Zahlen exakt, wird Mathematica immer Ergebnisse mit exakten rationalen Zahlen produzieren.

Sind die Koeffizienten in Ihrer Eingabe exakt, so wird Mathematica in der Ausgabe exakte rationale Zahlen verwenden.

In[4]:= ConstrainedMin[x + 3 y + 7 z,
{x - 3 y < 7, 2 x + 3 z >= 5, x + y + z < 10},
{x, y, z}]

Out[4]=

Mathematica erlaubt bei der Spezifizierung von Aufgaben der linearen Optimierung sowohl strenge Ungleichungen der Form a < b, als auch nicht-strenge Ungleichungen der Form a <= b zu verwenden. Wenn Sie mit Gleitpunktzahlen arbeiten, dann sind diese Ungleichungsarten nicht unterscheidbar. Wenn Sie jedoch mit exakten Zahlen arbeiten, dann können diese Ungleichungsarten im Prinzip zu unterschiedlichen Ergebnissen führen.

Es stellt sich heraus, daß die Lösung eines Problems der linearen Optimierung immer ein Punkt ist, der am Rand des für dieses Problem definierten Gebietes liegt. Bei nicht-strengen Ungleichungen liegt der Lösungspunkt sogar auf dem Rand. Bei strengen Ungleichungen liegt der Punkt jedoch im Prinzip infinitesimal innerhalb des Randes. Mathematica ignoriert diese Tatsache, wenn es exakte Ergebnisse für Probleme der linearen Optimierung angibt. Deshalb kann es sein, daß Mathematica ein Ergebnis wie x -> 1 liefert, obwohl x im Prinzip infinitesimal kleiner als 1 sein müßte.

Aufgrund dieses Phänomens können exakte Ergebnisse, die Sie mit Funktionen wie ConstrainedMax erhalten, die Eigenschaft haben, daß sie strengen Ungleichungen, die in den spezifizierten Nebenbedingungen auftauchen, nicht mehr genügen. Die Ergebnisse würden jedoch nicht-strenge Versionen derselben Ungleichungen erfüllen.

Das Ergebnis x -> 1 erfüllt x <= 1, aber nicht x < 1.

In[5]:= ConstrainedMax[x, {x < 1}, {x}]

Out[5]=

Mit ConstrainedMax und ConstrainedMin können Sie eine beliebige Liste mit Ungleichungen sowie mit Gleichungen angeben, um Nebenbedingungen zwischen Variablen zu spezifizieren. In einigen Fällen kann es sich herausstellen, daß diese Nebenbedingungen inkonsistent sind. In diesen Fällen springen ConstrainedMax und ConstrainedMin unevaluiert zurück.

Die hier gegebenen Nebenbedingungen sind inkonsistent.

In[6]:= ConstrainedMax[x, {x < 1, x > 2}, {x}]

Out[6]=

In den meisten praktischen Problemen der linearen Optimierung ist das angegebene Gebiet in allen Richtungen endlich. Es ist jedoch möglich, Ungleichungen anzugeben, die unendliche Gebiete spezifizieren. In derartigen Fällen kann es sein, daß es keine Schranke für die Zielfunktion gibt, und Mathematica wird unendliche oder unbestimmte Ergebnisse zurückgeben.

Das in diesem Fall spezifizierte Gebiet ist unbeschränkt.

In[7]:= ConstrainedMax[x, {x > 1}, {x}]

Out[7]=

In ConstrainedMax und ConstrainedMin werden die Zielfunktionen in symbolischer Form spezifiziert. Mitunter lassen sich Probleme der linearen Optimierung besser bearbeiten, wenn man Vektoren und Matrizen konstruiert, die geeignete Koeffizienten der vorkommenden linearen Funktion darstellen. Dies ist möglich mit LinearProgramming.

Lineare Optimierung in Matrix-Form

Hier ist ein Problem der linearen Optimierung in symbolischer Form.

In[8]:= ConstrainedMin[2x - 3y,
{x + y < 10, x - y > 2, x > 1}, {x, y}]

Out[8]=

Hier ist dasselbe Problem in Matrix-Form.

In[9]:= LinearProgramming[{2, -3},
{{-1, -1}, {1, -1}, {1, 0}}, {-10, 2, 1}]

Out[9]=

Numerische MinimierungFortgeschrittenes Thema: Funktionen mit sensitiver Abhängigkeit von ihrer Eingabe