NICHTLINEARE PROGRAMMIERUNG: METHODEN UND ÜBUNGEN - MATHE - 2025

Bei der nichtlinearen Programmierung wird eine Funktion optimiert, die von mehreren unabhängigen Variablen abhängt, die wiederum Einschränkungen unterliegen.

Wenn eine oder mehrere der Einschränkungen oder die zu maximierende oder zu minimierende Funktion (als Zielfunktion bezeichnet) nicht als lineare Kombination der Variablen ausgedrückt wird, liegt ein nichtlineares Programmierproblem vor.

Abbildung 1. Nichtlineares Programmierproblem (NLP). Dabei ist G die (nichtlineare) Funktion zur Optimierung im grünen Bereich, die durch die Einschränkungen bestimmt wird. Quelle: F. Zapata.

Daher können die Verfahren und Methoden der linearen Programmierung nicht verwendet werden.

Beispielsweise kann die bekannte Simplex-Methode nicht verwendet werden, die nur angewendet wird, wenn die Zielfunktion und die Einschränkungen alle lineare Kombinationen der Variablen im Problem sind.

Lineare Programmiermethoden

Bei nichtlinearen Programmierproblemen sind folgende Hauptmethoden zu verwenden:

1.- Grafische Methoden.

2. Lagrange-Multiplikatoren zur Untersuchung der Grenze des Lösungsbereichs.

3.- Berechnung des Gradienten zur Untersuchung von Extremen der Zielfunktion.

4.- Die Methode zum Absteigen von Schritten, um die Nullgradientenpunkte zu finden.

5.- Modifizierte Methode der Lagrange-Multiplikatoren (mit der Karush-Kuhn-Tucker-Bedingung).

Lösungsbeispiel mit grafischer Methode

Ein Beispiel für eine Lösung mit der grafischen Methode ist die in Abbildung 2 gezeigte:

Abbildung 2. Beispiel eines nichtlinearen Problems mit nichtlinearen Einschränkungen und seiner grafischen Lösung. Quelle: F. Zapata.

Übungen

- Übung 1 (Grafikmethode)

Der Gewinn G eines bestimmten Unternehmens hängt von der verkauften Menge des Produkts X und der verkauften Menge des Produkts Y ab. Außerdem wird der Gewinn durch die folgende Formel bestimmt:

G = 2 (X - 2) ² + 3 (Y - 3) ²

Es ist bekannt, dass die Beträge X und Y die folgenden Einschränkungen aufweisen:

X ≥ 0; Y ≥ 0 und X + Y ≤ 7

Bestimmen Sie die Werte von X und Y, die die maximale Verstärkung erzeugen.

Abbildung 3. Der Gewinn eines Unternehmens kann mithilfe nichtlinearer Programmierung mathematisch modelliert werden, um den maximalen Gewinn zu ermitteln. Quelle: Pixabay.

Lösung

In diesem Problem ist die Zielfunktion nicht linear, während die Ungleichungen, die die Einschränkungen definieren, sind. Dies ist ein nichtlineares Programmierproblem.

Zur Lösung dieses Problems wird die grafische Methode gewählt.

Zunächst wird der Lösungsbereich bestimmt, der durch die Einschränkungen gegeben ist.

Als X ≥ 0; Y≥0 muss die Lösung im ersten Quadranten der XY-Ebene gefunden werden, aber da es auch wahr sein muss, dass X + Y ≤ 7 ist, befindet sich die Lösung in der unteren Halbebene der Linie X + Y = 7.

Der Lösungsbereich ist der Schnittpunkt des ersten Quadranten mit der unteren Halbebene der Linie, was zu einem dreieckigen Bereich führt, in dem sich die Lösung befindet. Es ist das gleiche wie in Abbildung 1 gezeigt.

Andererseits kann die Verstärkung G auch in der kartesischen Ebene dargestellt werden, da ihre Gleichung die einer Ellipse mit Zentrum (2,3) ist.

Die Ellipse ist in Abbildung 1 für verschiedene Werte von G dargestellt. Je höher der Wert von G ist, desto größer ist die Verstärkung.

Es gibt Lösungen, die zur Region gehören, aber nicht den maximalen G-Wert angeben, während andere, wie z. B. G = 92,4, außerhalb der grünen Zone, dh der Lösungszone, liegen.

Dann entspricht der Maximalwert von G, so dass X und Y zum Lösungsbereich gehören:

G = 77 (maximale Verstärkung), gegeben für X = 7 und Y = 0.

Interessanterweise tritt der maximale Gewinn auf, wenn die Verkaufsmenge von Produkt Y Null ist, während die Menge von Produkt X ihren höchstmöglichen Wert erreicht.

- Übung 2 (Analysemethode: Lagrange-Multiplikatoren)

Finden Sie die Lösung (x, y), die die Funktion f (x, y) = x ² + 2y ² maximal im Bereich g (x, y) = x ² + y ² - 1 = 0 macht.

Lösung

Es ist eindeutig ein nichtlineares Programmierproblem, da sowohl die Zielfunktion f (x, y) als auch die Beschränkung g (x, y) = 0 keine lineare Kombination der Variablen x und y sind.

Es wird die Lagrange-Multiplikatormethode verwendet, bei der zunächst die Lagrange-Funktion L (x, y, λ) definiert werden muss:

L (x, y, λ) = f (x, y) - λg (x, y) = x ² + 2y ² - λ (x ² + y ² - 1)

Wobei λ ein Parameter ist, der als Lagrange-Multiplikator bezeichnet wird.

Um die Extremwerte der Zielfunktion f in dem durch die Restriktion g (x, y) = 0 gegebenen Lösungsbereich zu bestimmen, gehen Sie folgendermaßen vor:

-Finden Sie die partiellen Ableitungen der Lagrange-Funktion L in Bezug auf x, y, λ.

- Qualifizieren Sie jede Ableitung auf Null.

Hier die Reihenfolge dieser Operationen:

1. ∂L / ∂x = 2x - 2λx = 0
2. ∂L / ∂y = 4y - 2λy = 0
3. ∂L / ∂λ = - (x ² + y ² - 1) = 0

Mögliche Systemlösungen

Eine mögliche Lösung dieses Systems ist λ = 1, so dass die erste Gleichung erfüllt ist, in welchem ​​Fall y = 0, so dass die zweite erfüllt ist.

Diese Lösung impliziert, dass x = 1 oder x = -1 ist, damit die dritte Gleichung erfüllt wird. Auf diese Weise wurden zwei Lösungen S1 und S2 erhalten:

S1: (x = 1, y = 0)

S2: (x = -1, y = 0).

Die andere Alternative ist, dass λ = 2 ist, so dass die zweite Gleichung unabhängig vom y-Wert erfüllt ist.

In diesem Fall kann die erste Gleichung nur für x = 0 erfüllt werden. In Anbetracht der dritten Gleichung gibt es nur zwei mögliche Lösungen, die wir S3 und S4 nennen werden:

S3: (x = 0, y = 1)

S4: (x = 0, y = -1)

Um herauszufinden, welche oder welche dieser Lösungen die Zielfunktion maximieren, setzen wir f (x, y) ein:

S1: f (1, 0) = 1 ² + 2,0 ² = 1

S2: f (-1, 0) = (-1) ² + 2,0 ² = 1

S3: f (0, 1) = 0 ² + 2,1 ² = 2

S4: f (0, -1) = 0 ² + 2 (-1) ² = 2

Wir schließen daraus, dass die Lösungen, die f maximieren, wenn x und y zum Umfang g (x, y) = 0 gehören, S3 und S4 sind.

Die Wertepaare (x = 0, y = 1) und (x = 0, y = -1) maximieren f (x, y) im Lösungsbereich g (x, y) = 0.

- Übung 3 (Nullgradient)

Finden Sie Lösungen (x, y) für die Zielfunktion:

f (x, y) = x ² + 2 y ²

Sei maximal im Bereich g (x, y) = x ² + y ² - 1 ≤ 0.

Lösung

Diese Übung ähnelt Übung 2, aber der Lösungs- (oder Restriktions-) Bereich erstreckt sich auf den inneren Bereich des Umfangs g (x, y) = 0, dh auf den Kreis g (x, y) ≤ 0. Dies schließt ein zum Umfang und seinem inneren Bereich.

Die Lösung an der Grenze wurde bereits in Übung 2 festgelegt, aber die innere Region muss noch untersucht werden.

Dazu muss der Gradient der Funktion f (x, y) berechnet und gleich Null gesetzt werden, um Extremwerte im Lösungsbereich zu finden. Dies entspricht der Berechnung der partiellen Ableitungen von f in Bezug auf x bzw. y und der Einstellung auf Null:

∂f / ∂x = 2 x = 0

∂f / ∂y = 4 y = 0

Dieses Gleichungssystem hat die einzige Lösung (x = 0, y = 0), die zum Kreis g (x, y) ≤ 0 gehört.

Einsetzen dieses Wertes in die Funktion f ergibt:

f (0, 0) = 0

Zusammenfassend ist der Maximalwert, den die Funktion im Lösungsbereich annimmt, 2 und tritt an der Grenze des Lösungsbereichs für die Werte (x = 0, y = 1) und (x = 0, y = -1) auf. .

Verweise

1. Avriel, M. 2003. Nichtlineare Programmierung. Dover Publishing.
2. Bazaraa. 1979. Nichtlineare Programmierung. John Wiley & Sons.
3. Bertsekas, D. 1999. Nichtlineare Programmierung: 2. Auflage. Athena Scientific.
4. Nocedal, J. 1999. Numerical Optimization. Springer-Verlag.
5. Wikipedia. Nichtlineare Programmierung. Wiederhergestellt von: es.wikipedia.com