Das Konzept des Sattelpunkts. Kuna Taque theorem. Das Wortlaut und den Beweis des Kuna-Takker-Satzes

Theorem 7.2.Für das Problem der konvexen Programmierung (7.4) - (7.6) ist der Satz von zulässigen Lösungen, von denen der Plan über eine Regularitätseigenschaft verfügt, der Plan ist der beste Plan und nur dann, wenn es einen solchen Vektor gibt
- der Sattelpunkt der Lagrange-Funktion.

Wenn wir davon ausgehen, dass die Zielfunktion angeht
und Funktionen dauerhaft und differenzierbar kann der KUND-THECKER-Satz mit analytischen Ausdrücken ergänzt werden, die den erforderlichen und ausreichenden Zustand für den Punkt bestimmen
es gab einen Sattelpunkt der Lagrange-Funktion, d. H. Er war ein Problem der konvexen Programmierung. Diese Ausdrücke haben das folgende Formular:

wo und - Die Werte der entsprechenden privaten Derivate von Lagrange-Funktionen, die im Sattelpunkt berechnet werden.

Der Kuna-Takker-Satz in der Theorie der nichtlinearen Programmierung nimmt einen zentralen Ort ein. Es gilt auch für die Aufgaben der sogenannten quadratischen Programmierung, d. H. wo Zielfunktion.
mit Einschränkungen:

.

Im Allgemeinen gibt es Lösungen für nichtlineare Programmierprobleme zur Bestimmung des globalen Extremma, es gibt keine wirksame Rechenmethode, wenn es nicht bekannt ist, dass ein lokales Extremum sowohl global ist. Somit ist in dem Problem der konvexen und quadratischen Programmierung viele gültige Lösungen konvex, wenn die Zielfunktion konkav ist, ein örtliches Maximum ist ebenfalls global.

Beispiel 7.3. Mit Hilfe des Kun-Takker-Theorems finden Sie
mit Einschränkungen.

Wir lösen grafisch (Abb. 7.2) und finden:
;
;
(Weitere Informationen finden Sie im Folgenden unten). Wir zeigen, dass es einen Vektor gibt Y. 0 0, in dem an der Stelle des Optimums die Bedingungen des COON-Tackers durchgeführt werden. Machen Sie eine Lagrange-Funktion:

Entscheidung
wir finden aus dem System:
. Aus der zweiten Gleichung
wir ersetzen in der ersten Gleichung des Systems. Unterscheidung in. :
. Im Ausdruck und wir ersetzen die Werte
und
. Werte von privaten Derivaten mit mehr Null, und durch Zustand sollte null sein, dann =0 und \u003d 0. Andererseits, kann nicht Nullwerte nehmen, weil
Von hier
; alles
jene. Kuna-Tacker-Bedingungen werden daher durchgeführt, daher ist dieser Punkt ein Extremumpunkt.

Fig. 7.2. Grafische Lösung des Problems nichtlinear

programmierbeispiel 7.3.

Erforderliche Bedingungsoptimalität Für das Problem der nichtlinearen Programmierung ist es möglich, wie folgt zu formulieren. Lassen
- Optimale Problemlösung (7.4) - (7.6) und Funktion
,
,
unterscheidet an diesem Punkt. Wenn ein
- Nicht-einzigartiger Punkt des zulässigen Satzes von Aufgaben (7.4) - (7.6), dann ist es der Punkt des Kuan-Tackers dieser Aufgabe.

Also, wenn das zulässige Satz
aufgaben (7.4) - (7.6) hat keine einzigartige Punkte und Funktionen F.(M),g. iCH. (M) (
) Differentiale an allen Punkten
Die optimale Lösung für diese Aufgabe sollte unter den Punkten des Kuna-Tackers durchsucht werden.

Wie aus der mathematischen Analyse bekannt ist, speziellen Punkten Sätze zulässiger Lösungen eines Systems linearer Gleichungen und Ungleichheiten des Formulars

d. H. Viele zulässige Lösungen

wenn an der Stelle
Linear abhängige Gradienten dieser Funktionen
was in sie appelliert . Beispielsweise,
- Sonderspitze des Sets

Ja wirklich,

Somit das linearabhängige System.

Gradientenfunktion
- Dies ist ein Vektor, dessen Koordinaten jeweils den Werten der privaten abgeleiteten Funktionen entsprechen
am Punkt M. 0. Dieser Vektor zeigt die Richtung des schnellsten Wachstums der Funktion.

Die erforderliche Optimalitätsbedingung ist ungeeignet, um die meisten Probleme der nichtlinearen Programmierung zu lösen, da Nur in seltenen Fällen ist es möglich, alle Punkte des Kuna-Tapeers des Problems der nichtlinearen Programmierung zu finden.

Eine ausreichende Bedingung für die Optimalität Für das Problem der nichtlinearen Programmierung: wenn
- der Sattelpunkt der Lagrange-Funktion für das Problem (7.4) - (7.6), dann
es ist die optimale Entwicklung dieser Aufgabe.

Diese Bedingung ist im Allgemeinen nicht erforderlich: Die Lagrange-Funktion hat möglicherweise keine Sattelpunkte, während gleichzeitig das anfängliche Problem der nichtlinearen Programmierung die beste Lösung hat.

Es ist bekannt, dass verschiedene Verfahren die optimale Lösung des Problems der nichtlinearen Programmierung angenähert werden. Diese Methoden ergeben jedoch nur eine ziemlich gute Annäherung an das Problem der konvexen Programmierung, in denen ein lokales Extremum sowohl global ist. Im Allgemeinen unter gradientmethoden verstehen die Verfahren, bei denen die Bewegung bis zum Punkt der optimalen Funktion mit der Richtung des Gradienten dieser Funktion zusammenfällt, d. H. Ab irgendwann
ein sequentieller Übergang zu einigen anderen Punkten wird durchgeführt, bis eine akzeptable Lösung der anfänglichen Aufgabe offenbart ist. In diesem Fall können Gradientenmethoden in 2 unterteilt werden gruppen.

ZU zuerstdie Gruppe enthält Methoden, wenn die Testpunkte verwendet werden, nicht über die Grenzen der zulässigen Lösungen des Problems hinausgehen. Die häufigsten solcher Methoden ist die Methode Frank-Wolf (Wulf). Die Methode dieser Methoden beinhaltet ein Verfahren entworfene Rosen-Gradienten, Methode zulässige Gebiete von Zoitenka.

KO. zweitedie Gruppe enthält Methoden, in denen die studierenden Punkte beide angehören können, und gehören nicht zum Bereich der zulässigen Lösungen. Infolge der Umsetzung des iterativen Prozesses besteht jedoch ein Punkt des Bereichs von zulässigen Lösungen, die eine akzeptable Lösung definieren.

Von diesen Methoden wird die Methode am häufigsten verwendet straffunktionen oder Methode. Arrow gurvitsa..

Bei der Lösung von Problemen mit Gradientenmethoden, einschließlich derjenigen, einschließlich derjenigen, wird der iterative Prozess bis zum Gradienten der Funktion durchgeführt
am nächsten Punkt
wird nicht null oder so weit sein
wo - Eine ausreichend kleine positive Zahl, die die Genauigkeit der erhaltenen Lösung kennzeichnet.

Die Lösung komplexer Probleme der nichtlinearen Programmierung mit Gradientenmethoden ist mit einem großen Berechnungsvolumen und angemessen nur mit Computern verbunden.

Im Beispiel zeigen wir die allgemeine Bedeutung der Gradientenmethoden zur Lösung der Probleme der nichtlinearen Programmierung.

Lassen Sie eine Funktion von zwei Variablen geben
. Lassen Sie die Anfangswerte der Variablen sein
und der Wert der Funktion
. Wenn ein
es ist kein Extremum, dann identifizieren Sie solche neuen Variablenwerte.
und
so dass die folgende Funktion
es stellte sich heraus, dass sich das Optimum an dem optimalen als dem vorherigen angeht.

Wie die Größe von Inkrementen ermittelt wird und ? Dazu an Punkte und die Richtung der Änderungen in der Funktion in Richtung Extremum wird unter Verwendung eines Gradienten bestimmt. Je größer der Wert des privaten Ableitungen ist, desto schneller ändert sich die Funktion in Richtung Extremum. Deshalb Inkrement und wählen Sie proportionale Werte von privaten Derivaten und an Punkten
und
. Auf diese Weise,
und
wo - ein Wert, der als Schritt bezeichnet wird, der den Umfang der Änderungen enthält und .

Beispiel 7.4.

Lassen Sie es notwendig sein, die Funktion zu maximieren

(Maximal am Punkt (3; 2))

.

Am Punkt
,
zum
haben

;
,

Lassen Sie uns eine weitere Iteration anziehen. Am Punkt
,
zum
haben

;
,

Fig. 7.3. Geometrische Interpretation von zwei Schritten

gradientenmethode zum Beispiel 7.4

In FIG. 7.3 zeigt eine Gradientenbewegung, die in durchgeführt wurde dieses Beispiel. Einstellung gibt die Richtung des Änderns der Funktion auf dem Maximum an. Wenn der Gradient mit einem Minuszeichen hergestellt wird, ziehen wir uns auf ein Minimum an.

Das spezifische Problem der Gradientenmethoden ist die Wahl des Schrittwerts t.. Wenn Sie einen kleinen Schritt setzen, suchen wir uns sehr lange an. Wenn Sie seinen Wert zu groß wählen, können Sie optimal "rutschen". Die Zwischenaufgabe zur Auswahl des optimalen Schrittschritts wird mit den entsprechenden Verfahren gelöst. Wenn Schritt t. Es wird ungefähr bestimmt, dann ist es in der Regel nicht auf dem Optimum, sondern in seiner Zone. Gradientenmethoden sorgen für die Definition des lokalen Optimums. Wenn Sie ein globales Optimum mit einem Gradienten finden, gibt es häufig ein Zweifel, dass das optimale gefundene gefunden ist. Dies ist ein Nachteil dieses Verfahrens, wenn Sie die Aufgaben der nicht ungültigen Programmierung lösen.

Fragen zum Selbsttest

Das Problem der nichtlinearen Programmierung einstellen.

Der Prozess der Suche nach einer Lösung für das Problem der nichtlinearen Programmierung mit seiner geometrischen Interpretation.

Algorithmus der Lagrange-Methode zur Lösung des Problems der nichtlinearen Programmierung.

Die Verwendung des Lagrange-Verfahrens zur Lösung des Problems der nichtlinearen Programmierung in dem Fall, wenn Kommunikationsbedingungen Ungleichheiten sind.

Die Hilfsdefinitionen und Theorems, die erforderlich sind, um den zentralen Satz der nichtlinearen Programmierung zu betrachten, sind der Kuna-Takker-Satz.

Kuna Taque theorem.

Erforderlich und ausreichend Optimalitätsbedingung für das Problem der nichtlinearen Programmierung.

Die allgemeine Bedeutung von Gradientenmethoden der ungefähren Lösung von nichtlinearen Programmierproblemen.

Gruppe von Gradientenmethoden der ungefähren Lösung von nichtlinearen Programmierproblemen.

Wir schreiben die Lagrange-Funktion: (4)
wo λ i, i \u003d 1..m unsichere Lagrange-Multiplikatoren sind; Z (x) und q i (x) - konvexe Up-Funktion.

Coon Tracker Theorem.. Damit der Plan x 0 eine Lösung des Problems (1) - (4) ist, ist es erforderlich, dass der Vektor λ 0 ≥ 0 so ist, dass das Paar (x 0, λ 0) für alle x ≥ 0 und λ ≥ 0.
L (x, λ 0) ≤ l (x 0, λ 0) ≤ l (x 0, λ)

Ernennung des Dienstes.. Online-Rechner wird verwendet, um eine Extremum-Funktion durch Lagrange-Multiplikatoren in zu finden onlinemodus Mit Überprüfung von Lösungen in MS Excel. Gleichzeitig werden folgende Aufgaben gelöst:

1. die Lagrange Lagrange-Funktion wird als lineare Kombination der Funktion f (x) und der Einschränkungen G i (x) erstellt;
2. es gibt private Derivate von Lagrange-Funktionen, ∂l / ∂x i, ∂l / ∂λ i;
3. ein System besteht aus (n + m) von Gleichungen, ∂l / ∂x i \u003d 0.
4. die Variablen X I und die Lagrange-Multiplizierer α I sind bestimmt.

Anzahl der Einschränkungen, G i (x) 1 2 3 4
Einschränkungen x i ≥ 0 sind angegeben.

.

Zur Funktion von zwei Vektorvariablen (4) hatten einen Sattelpunkt, es ist notwendig und reicht aus, um das Folgende auszuführen cuna-Teeter-Bedingungen:
(5)
(6)
(7)
(8)

Wenn die Aufgabe gelöst ist minimierung, dann gibt es einen SERGPOINT (x 0, y 0), wenn die Beziehungen durchgeführt werden
L (x, λ 0) ≤ l (x 0, y 0) ≤ l (x 0, y)
Die Bedingungen des Kun-Tackers der Existenz des Sattelpunkts der Lagrange-Funktion ändern das Anmelden (5) und (7) auf das Gegenteil.

Beispiel. Überprüfen Sie die Erfüllung der Coon-Tankgeräte. Finden Sie den optimalen Punkt der linearen Programmieraufgaben mit Einschränkungen:
f (x) \u003d x 1 2 -x 2 → min
g 1 (x) \u003d x 1 - 1 ≥ 0
g 2 (x) \u003d 26 - x 1 2 -x 2 2 ≥ 0
h 1 (x) \u003d x 1 + x 2 - 6 \u003d 0

Entscheidung:
Lagrange function: l (x, λ) \u003d x 1 2 -x 2 - λ 1 (1-× 1) + λ 2 (26- (x 1 2 + x 2 2)) + λ 3 (6- (x 1 + x 2))
Voraussetzung für das Extremum der Lagrange-Funktion ist die Gleichheit Null seiner privaten Derivate in variablen I- und Unbestimmten Multiplizierungen λ.
Überprüfen Sie die Erfüllung der Coon-Tankgeräte. Berechnen Sie die Matrizen der zweiten Derivate zielfunktion und Restriktionsfunktionen.

Die Hessen-Matrix H f ist bei allen Werten x positiv halbiert, daher f (x) - konvexe Funktion.
Die Grenze G 1 (X) ist eine lineare Funktion, die gleichzeitig konvex und konkav ist.
Die Hessen-Matrix für die Funktion G 2 (X) hat das Formular:

Δ 1 \u003d -2, δ 2 \u003d 4.
Da die Matrix H G 2 negativ bestimmt ist, dann ist G 2 (X) konkav.
Die Funktion H 1 (X) ist in der linearen Einschränkung in Form von Gleichheit enthalten. Folglich sind die Bedingungen (A), (B) und (C) des Satzes 1 erfüllt. Wir finden jetzt den Punkt des optimalen X *.
Wir haben:


Die Gleichung nimmt das folgende Formular an:

Für j \u003d 1 und j \u003d 2 können Sie die folgenden Ausdrücke erhalten:
j \u003d 1, 2x 1-u 1 + 2x 2 μ 2 + λ 1 \u003d 0
j \u003d 2, -1 + 2x 2 μ 2 + λ 1 \u003d 0
Somit lauten die COON-TAKKER-Bedingungen für unser Beispiel wie folgt:
2x 1-u 1 + 2x 2 μ 2 + λ 1 \u003d 0
-1 + 2x 2 μ 2 + λ 1 \u003d 0
x 1 + x 2 - 6 \u003d 0
μ 1 (x 1 -1) \u003d 0
μ 2 (26 - x 1 2 - x 2 2) \u003d 0
μ 1, μ 2 ≥ 0

Aus der dritten Gleichung finden wir: x 1 \u003d 6-x 2. Wir ersetzen den Wert von x 1 an die anderen Gleichungen, wir erhalten:
2 (6-× 2) - μ 1 + 2μ 2 (6-× 2)
-1 + 2x 2 μ 2 + λ 1 \u003d 0
μ 1 (6-× 2 -1) \u003d 0 → x 2 \u003d 5, x 1 \u003d 1
μ 2 (26 - (6-× 2) 2 - x 2 2) \u003d 0
Ersatz x 2 \u003d 5 in der ersten und zweiten Gleichung:

Aus der zweiten Gleichung, Express λ und Ersatz in der ersten Gleichung:
3 - μ 1 - 8μ 2 \u003d 0
Sei μ 1 \u003d 0,1 ≥ 0, dann μ 2 \u003d 2,2 ≥ 0. Somit ist der Punkt x * \u003d ein Mindestpunkt.

Im vorherigen Abschnitt werden COON-Bedingungen erstellt-Ker für bedingte Optimierungsaufgaben. Mit Hilfe der Lagrange Multipliziermethode, einer intuitiven Idee, dass die Bedingungen des COON - der Tanker - der Tanker eng mit den erforderlichen Bedingungen für die Optimalität zusammenhängen. Dieser Abschnitt diskutiert strikte Formulierungen der notwendigen und ausreichenden Bedingungen für die Optimalität der Lösung des Problems der nichtlinearen Programmierung.

Theorem 1. Die Notwendigkeit von COON TAKKER

Betrachten Sie das Problem der nichtlinearen Programmierung (0) - (2). Lassen Sie differenzierbare Funktionen und X * - die zulässige Lösung dieser Aufgabe sein. Stellen. Als nächstes lass es linear unabhängig. Wenn X * die optimale Lösung für das Problem der nichtlinearen Programmierung ist, gibt es ein solches Paar von Vektoren, was die Lösung des Koon-Tacker-Problems (3) - (7) ist.

Die Bedingung, nach der sich linear unabhängig sein muss, ist es als ein Zustand der linearen Unabhängigkeit bekannt und stellt im Wesentlichen einen bestimmten Zustand der Regelmäßigkeit des zulässigen Bereichs dar, der fast immer für Optimierungsaufgaben durchgeführt wird. Im Allgemeinen ist das Überprüfen der Erfüllung des Zustands der linearen Unabhängigkeit jedoch sehr schwierig, da dies erforderlich ist, da die optimale Lösung des Problems im Voraus bekannt ist. Gleichzeitig wird der Zustand der linearen Unabhängigkeit immer für nichtlineare Programmieraufgaben mit den folgenden Eigenschaften durchgeführt.

• 1. Alle Einschränkungen in Form von Gleichungen und Ungleichheiten enthalten lineare Funktionen.
• 2. Alle Einschränkungen in Form von Ungleichheiten enthalten konkave Funktionen, alle Gleichstellungsbeschränkungen sind lineare Funktionen und existiert auch mindestens einen zulässigen Punkt X, der sich im inneren Teil des durch Ungleichungen definierten Bereichs befindet. Mit anderen Worten, es gibt einen solchen Punkt x das

Wenn der Zustand der linearen Unabhängigkeit am Optimum nicht ausgeführt wird, kann die Kunde-Tacker-Task möglicherweise keine Lösungen haben.

Minimieren

mit Einschränkungen.

In FIG. 1 zeigt den Bereich der zulässigen Lösungen, die über der nichtlinearen Aufgabe formuliert sind. Es ist klar, dass die optimale Lösung dieser Aufgabe ist. Wir zeigen, dass der Zustand der linearen Unabhängigkeit nicht am Optimum durchgeführt wird.

Feige.

Es ist leicht zu sehen, dass die Vektoren linear abhängig sind, d. H. Der Zustand der linearen Unabhängigkeit an der Stelle wird nicht durchgeführt.

Wir schreiben die Bedingungen des Kuna-Tackers und prüfen, ob sie an der Stelle (1, 0) durchgeführt werden. Die Bedingungen (3), (6) und (7) nutzen das folgende Formular;

Mit der Gleichung (11) folgt, dass der optimale Punkt, während die Gleichung (14) daher nicht ein Punkt des Fahrzeugtanks ist.

Beachten Sie, dass der Verstoß gegen den Zustand der linearen Unabhängigkeit nicht notwendigerweise bedeutet, dass der Punkt des Tank-Tanks nicht existiert. Um dies zu bestätigen, ersetzen Sie die Zielfunktion aus dieser Beispielfunktion. In diesem Fall wird das Optimum an dem Punkt (1,0) noch erreicht, in dem der Zustand der linearen Unabhängigkeit nicht durchgeführt wird. Kuna-Tacker-Bedingungen (12) - (16) bleiben unverändert, und die Gleichung (11) dauert

Es ist leicht zu überprüfen, ob der Punkt ein Punkt von Kuna-Takker ist, d. H. Erfüllt die Bedingungen von Coon-Tacker.

Der Satz mit dem Bedarf an COON-THEADER-Bedingungen ermöglicht es Ihnen, nicht optimale Punkte zu identifizieren. Mit anderen Worten, Theorem 1 kann verwendet werden, um zu beweisen, dass der angegebene zulässige Punkt, der den Zustand der linearen Unabhängigkeit erfüllt, nicht optimal ist, wenn er die Bedingungen des Kun-Takker nicht erfüllt. Wenn dagegen der Zustand der KUN-THEADER durchgeführt wird, gibt es dagegen nicht garantiert, dass die optimale Lösung der nichtlinearen Aufgabe gefunden wird. Berücksichtigen Sie als Beispiel die folgende Aufgabe der nichtlinearen Programmierung.

Der folgende Theorem legt die Bedingungen fest, wenn der KUNA-TAKKER-Punkt automatisch der optimalen Lösung des Problems der nichtlinearen Programmierung entspricht.

Theorem 2. Gut ausreichend Coon-Tracker-Bedingungen

Betrachten Sie das Problem der nichtlinearen Programmierung (0) - (2). Lassen Sie die Zielfunktion konvex, alle Einschränkungen in Form von Ungleichheiten enthalten konkave Funktionen, und die Einschränkungen in Form von Gleichungen enthalten lineare Funktionen. Wenn dann eine Lösung vorhanden ist, die die Bedingungen des Kun-Tacker (3) - (7) erfüllt, ist X * die optimale Lösung für das Problem der nichtlinearen Programmierung.

Wenn die Bedingungen des Satzes 2 durchgeführt werden, bietet der Punkttierpunkt des Kuna-Takkers die optimale Lösung für das Problem der nichtlinearen Programmierung.

Theorem 2 kann auch verwendet werden, um die Optimalität zu erweisen. diese Lösung Nelineare Programmieraufgaben. Als Illustration werden wir das Beispiel in Betracht ziehen:

Minimieren

mit Einschränkungen.

Mit Hilfe von Theorem 2 beweisen wir, dass die Lösung optimal ist. Haben

Da die Matrix für alle x positiv halbiert ist, stellt sich die Funktion als konvex heraus. Die erste Einschränkung in Form von Ungleichheit enthält lineare Funktiondas ist gleichzeitig konvex und konkav. Zum

um zu zeigen, dass die Funktion konkav ist, berechnen Sie

Da die Matrix negativ definiert ist, ist die Funktion konkav. Die Funktion ist in einer linearen Einschränkung in der Ebene der Videie enthalten. Folglich sind alle Bedingungen des Satzes 2 erfüllt; Wenn wir das zeigen - der Punkt des Kun-Takkers, etablieren Sie dann wirklich die Optimalität der Lösung. Kuna-Tacker-Bedingungen für Beispiel 2 sind

Der Punkt erfüllt die Einschränkungen (24) - (26) und ist daher zulässig. Gleichungen (22) und (23) nutzen das folgende Formular:

Setzen, wir bekommen und. Somit erfüllt die Lösung x * \u003d (1, 5) die Bedingungen des Kun-Takkers. Da die Bedingungen der Satz 2 erfüllt sind, ist die optimale Lösung des Problems aus Beispiel 3. Beachten Sie, dass auch andere Werte vorhanden sind, die das System (22) - (29) erfüllen.

Bemerkungen

• 1. Für diejenigen, die in der Praxis von Aufgaben auftreten, wird der Zustand der linearen Unabhängigkeit in der Regel durchgeführt. Wenn die Aufgabe alle differenziellen Funktionen ist, sollte der Kun-Tacker-Punkt als möglicher Optimum angesehen werden. Somit werden viele der Methoden der nichtlinearen Programmierung an den Punkt des Kuna-Tackers zusammengedrückt. (Hier ist es angemessen, mit dem Fall einer bedingungslosen Optimierung eine Analogie zu erstellen, wenn Sie den entsprechenden Algorithmen ermöglichen, einen stationären Punkt zu definieren.)
• 2. Wenn die Bedingungen von Satz 2 erfüllt sind, erscheint der Kuna-Takker-Punkt gleichzeitig ein globaler Mindestpunkt. Leider ist die Inspektion der ausreichenden Bedingungen sehr schwierig, und außerdem haben die anliegenden Aufgaben oft nicht die erforderlichen Eigenschaften. Es sei darauf hingewiesen, dass das Vorhandensein von mindestens einer nichtlinearen Begrenzung in Form von Gleichheit zu einer Verletzung der Annahmen von Theorem 2 führt.
• 3. Ausreichende Bedingungen, die von Satz 2 festgelegt wurden, können im Falle von Aufgaben mit Nicht-Trennungsfunktionen verallgemeinert werden, die in den Einschränkungen in Form von Ungleichheiten, Nicht-Trennen von Zielfunktionen und nichtlinearen Gleichstellungsbeschränkungen enthalten sind. Dies verwendet solche Verallgemeinerungen von konvexen Funktionen als Quasi-Knochen- und Pseudo-Schnalle-Funktionen.

Der zentrale Ort in der Theorie der nichtlinearen Programmierung nimmt den Kuna-Takker-Theorem ein. Lassen Sie die Aufgabe der nichtlinearen Programmierung gegeben werden:

finden Sie die maximale Funktion Z.=f.(x 1., x 2., ..., x n.) Mit Einschränkungen.

Wir werden eine Lagrange-Funktion für diese Aufgabe bilden:

(4.2)

Wenn eine Regelmäßigkeitsbedingung erfüllt ist (mindestens einen Punkt X. für das g I.(X.)\u003e 0 für alle iCH.), dann findet der folgende Theorem statt.

Satz.Vektor X. (0) Wenn und nur dann ist die optimale Lösung des Problems (4.1), wenn ein solcher Vektor λ (0) ist, der für alle

Punkt ( X (0), Λ (0)) rief sadlovapunkt zur Funktion F.(X., Λ) und der theorem wird genannt theorest am Sattelpunkt.Wir beweisen die Genauigkeit der Bedingungen (4.3).

Beweise. Lassen X. (0)\u003e 0 und λ (0)\u003e 0 - Sedlovaya-Funktionen F.(X., Λ). Wenn in (4.3) stattdessen F.(X., Λ) Ersetzen Sie seinen Wert (4.2), dann erhalten wir

zum .

Die rechte Ungleichheit trifft sich daher zu

Dann kommen Sie von der linken Ungleichheit

Wie zur gleichen Zeit

das f.(X (0))>f.(X.).

So der Punkt X (0)erfüllt (4.1) und an allen anderen Punkten, die (4.1) erfüllt (4.1), nimmt die Funktion den Wert weniger an als in X (0).

Diese Anweisung führt zur Lösung der NLP-Aufgabe, um die Sattelpunkte der Lagrange-Funktion zu finden F.(X.,Λ).

Der Nachweis der Bedarfsbedürfnisse (4.3) aufgrund seiner Komplexität wird nicht berücksichtigt.

Wenn ein f.(X.) ICH. g I.(X.) -Differenzierende Funktionen, dann sind die Bedingungen (4.3) den folgenden örtlichen Bedingungen von Kuna-Takker entspricht:

Ausdruck

bedeutet, dass der Wert des privaten Ableitungen der Lagrange-Funktion an der Stelle aufgenommen wird ( X (0), Λ (0)), wo

X (0)=(x 1. (0) , x 2. (0) , ..., x n. (0)), λ (0) \u003d (λ 1 (0) , λ 2 (0) , ..., λ N. (0)).

Diese Bedingungen können in Vektorform geschrieben werden:

Beispiel. Finde Max. Z.=-x. 1 2 -x. 2 2 während der Einschränkungen

Wir zeigen, dass es λ (0) 0 gibt, an dem die Kuna-Tacker-Bedingungen (4.4) (4.5) am optimalen Punkt (4.5) für die Funktion durchgeführt werden F.(X.,Λ):

F.(X.,Λ)=- x. 1 2 -x. 2 2 + λ 1 (2 x. 1 +x. 2 -2) + λ 2 (8-2 x. 1 -x. 2) + λ 3 (6- x. 1 -x. 2).

Gemäß den Bedingungen (4.5) λ 2 und λ 3 müssen die Nullwerte dauern, weil ersetzt x. 1 \u003d 0,8 und x. 2 \u003d 0,4 in Ausdrücken

haben Werte, großer Null, aber durch Zustand

Gemäß der Bedingung λ 1 kann es den Wert nicht Null nehmen, da

Gemäß (2.16) Derivat

muss Nullwerte als Koordinaten des Vektors annehmen X (0)anders von null. Wir finden λ 1 \u003d 0,8. Daher an der Stelle ( X (0), Λ (0)) Die Gehäuse-Tacker-Bedingungen werden durchgeführt, und es ist in der Tat ein Extremumpunkt.

Betrachten Sie die Bedingungen des Coon-Trekers in einer etwas anderen Form.

Lassen Sie uns das Problem der Optimierung mit Einschränkungen in Form von Gleichungen haben:

z.= f.(x. 1 , x. 2 , …, xn.) → min

unter Bedingungen:

g 1 ( x. 1 , x. 2 , ... , x n.) = 0,

g 2 ( x. 1 , x. 2 , ... , x n.) = 0,

g. N.(x. 1 , x. 2 , . . . , x n.) = 0.

Bedingte Mindestpunktfunktion f. Stimmt mit dem Sattelpunkt der Lagrange-Funktion zusammen:

Gleichzeitig sollte der Sattelpunkt ein Minimum an ihren Variablen bereitstellen. x I.und maximale Variable λ j..

Die notwendigen Bedingungen des stationären Punktes sind die Gleichheit Null der privaten Derivate der ersten Reihenfolge aller Alternativen:

Beachten Sie, dass aus der zweiten Gleichung folgt, dass nur zulässige Punkte die erforderlichen Bedingungen erfüllen werden.

Um eine ausreichende Bedingung für das Vorhandensein eines Minimums zu erhalten, ist es erforderlich, das Anforderungen der positiven Definition der hessischen Zielfunktion hinzuzufügen.

Erwägen allgemeines Die Aufgabe der mathematischen Programmierung:

Z \u003d. f.(X) → min,

unter Bedingungen:

Einschränkungen in Form von Ungleichheiten können in Form von Gleichungen in Einschränkungen in Form von Gleichungen umgewandelt werden, indem zu jedem von ihnen hinzugefügt werden schwächen Variablen

Wir bilden eine Lagrange-Funktion:

Dann nehmen die erforderlichen Mindestbedingungen das Formular aus:

Die zweite Gleichung kann durch Ablehnen von Schwächungsvariablen umgewandelt werden und zu Ungleichheiten einschränken. Wir erhalten Einschränkungen der ursprünglichen Aufgabe. Die dritte Gleichung kann multipliziert werden ui/ 2 und ersetzen Sie Schwächungsvariablen, indem Sie sie aus der zweiten Systemgleichung ausdrücken.

Es gibt eine andere Bedingung, die auf einem Mindestpunkt durchgeführt werden muss. Diese Bedingung: λ ICH.\u003d 0, was eine Folge der Analyse der physikalischen Bedeutung der Koeffizienten der Lagrange-Funktion ist.

Sie können das zeigen

Lagrange-Koeffizient an einem Mindestpunkt;

f.* - der optimale Wert der Funktion.

Offensichtlich, wenn b ICH. Der zulässige Bereich ist erweitert, dh der minimale Wert kann nur abnehmen, dh das Derivat muss negativ sein (Inseminat). Daher ist es an der Stelle des bedingten Minimums

Wir erhalten endlich die notwendigen Bedingungen für bedingt minimum:

Ausdrücke in der zweiten Zeile stellen sicher, dass der optimale Punkt zulässig ist.

Die dritte Zeile enthält die folgenden Informationen: Wenn die Grenze aktiv ist (d. H. Die Expression in Klammern Null ist), ist der entsprechende Lagrange-Koeffizient streng positiv. Die Positivität des Lagrange-Koeffizienten bedeutet die Aktivität der entsprechenden Einschränkung, d. H. Die Tatsache, dass diese Einschränkung mangelhaft ist, dh es ist das, dass die Zielfunktion weiter verbessert wird. Wenn die Grenze nicht aktiv ist (d. H. Die Expression in Klammern nicht Null ist), muss der entsprechende Lagrange-Koeffizient Null sein, d. H. Diese Einschränkung ist nicht zerstreut, es beeinträchtigt nicht die weitere Verbesserung der Zielfunktion.

Für den Punkt des bedingten Maximums ändern sich die Lagrange-Koeffizienten das Zeichen auf das Gegenteil (da der optimale Wert der Zielfunktion am Punkt des bedingten Maximums zunehmen sollte).

Bedingungen sind gleichwertig cOON TREKER Satz. Und beziehen sich oft auf das gleiche.

Eine ausreichende Bedingung für ein Minimum (Maximum) ist die Konvexität (konkav) der Zielfunktion in einem stationären Punkt. Dies bedeutet, dass der Hessian positiv (negativ) definiert ist.

Die konsistente Darstellung des Materials dieses Kapitels kann in zwei Präsentationen angezeigt werden:

datei "nichtlineare Programmierung";

datei "Kuna-Takker Theorem".

An den Folien von 10-14 zeigt die Präsentation des "Kuna-Takker theorem" ein Beispiel, um das Problem des Kuna-Takker-Problems zu lösen.

4.5. Kontrollfragen

(Entwickelt von Afanasyev M.YU. und SUVOROV B.P.)

Frage 1. Dana Gültiger Funktion. f.(h. S. \u003d. Lassen h. 1 I. h. 2 - Punkte dieses Segments und 0 £ l £ 1.

Welche der Ungleichheit ist der Zustand der Konvexität der Funktion?

Antworten Optionen:

Frage 2. Dana Gültiger Funktion. f.(x.) Definiert auf dem Segment gültige Zahlen S \u003d.. Lassen x. 1 I. x. 2 - Punkte dieses Segments und 0 £ l £ 1.

Welche der Ungleichheit ist die Bedingung für die strikte Zufügung der Funktion?

Antworten Optionen:

Frage 3. Funktion

1) konvex;

2) streng konvex;

3) konkav;

4) streng konkav;

5) konvex und konkav.

Frage 4. Funktion

3) konkav; 4) streng konkav;

5) konvex und konkav.

Frage 5. Funktion

1) konvex; 2) weder konvex noch konkav;

3) streng konvex; 4) konkav:

5) konvex und konkav.

Frage 6. Das neue Modell des Hochgeschwindigkeitsmotorrads "Schnecke" wird vom Unternehmen zum Preis (30 - 2) verkauft x.) Tausend Dollar ein Stück wo h.- Anzahl der verkauften Motorräder. Variable Produktionskosten machen 6 Tausend Dollar pro Stück, Fixkosten - 30 Tausend Dollar. Maximieren Sie den Gewinn des Unternehmens pro Woche.

Angenommen, das letzte (Steuern) infolge der Änderung des Umsatzsteuersatzes betrugen auf weitere 4 Tausend Dollar. Für jedes Motorrad verkaufte.

Wie ändert sich die optimale Produktion von Motorrädern im Vergleich zur ursprünglichen Situation?

(Lösen Sie die Lagrange-Funktion.)

Antworten Optionen:

1) Erhöhung 2 ; 2) nimmt ab 2 ;

3) ändert sich nicht; 4) wird zunehmen 1 ;

5) nimmt ab 1 .

Frage 7. Angenommen, Sie haben 2 Wochen (14 Tage) Urlaub, die Sie auf den Kanarischen Inseln und in Nizza ausgeben können. Lassen Sie Ihre Dienstprogrammfunktion 2 angezeigt werden KN -3Zu 2 -4N 2,wo ZUund N - Die Anzahl der Tage, die Sie auf den Kanarischen Inseln und in Nizza verbringen.

Wie viele Tage sollten Sie in Nizza verbringen, um Ihre Utility-Funktion zu maximieren?

(Um die Funktion von Lagrange zu lösen. Das Ergebnis ist auf das nächste Ganze gerundet. Prüfen Sie, ob die Bedingungen für die Optimalität der KUNA durchgeführt werden - TAKKER.)

Antworten Optionen:

1) 3 ; 2) 4 ; 3) 5 ; 4) 6 ; 5) 7 .

Frage 8. Für die Aufgabe der Frage 7 finden Sie den Wert der doppelten Grenzwertbewertung.

(Das Ergebnis ist auf das nächste Ganze gerundet.)

Antworten Optionen:

1) 41 ; 2) 34; 3) 29 ; 4) 39 ; 5) 44 .

Frage 9. Der Monopolist plant das Produktionsprogramm und den Produktumsatz für den nächsten Zeitraum. Preise: r. 1 = 14 – 0,25x. 1 (für das Produkt 1); r. 2 = 14 – 0,5h. 2 (für das Produkt 2), wo x. 1 I. h. 2 - Produktverkäufe. Angenommen, alle hergestellten Produkte sind implementiert. Maximaler Gesamtumsatz - 57.

Was ist die optimale Version des Produkts 2?

Antworten Optionen:

1) 36,4 ; 2) 30,7 ; 3) 26,3 ; 4) 20,6 ; 5) 41,8 .

Frage 10. Der Besitzer eines kleinen Unternehmens hat 100ausend Rubel für den nächsten Monat, den er für einen Anstieg des Anlagevermögens ausgeben kann ZU (Beschaffung von Geräten) zu einem Preis von 1 tausend Rubel pro Einheit oder zusätzliche Arbeitskraft L. zu einem Preis von 50 Rubel / h. Der Anstieg der fertigen Produkte, die bei 10.000 Rubel verkauft werden können. pro Einheit, bestimmt durch die Produktionsfunktion F (k, l) \u003d l 2/7 bis 2/5.

Wie viele Fonds sollten für einen Anstieg des Anlagevermögens ausgegeben werden?

Antworten Optionen:

1) 74.36 Tausend. reiben.; 2) 58,33 tausend Rubel.; 3) 63,44 Tausend Rubel.;

4) 45,66 Tausend Rubel.; fünf) 39,77 Tausend Rubel.

Antworten auf Fragen:

1 -4,2 - 1,3 -4,4 - 5,

5 -2, 6 -5,7- 4,8- 2,9- 4,10- 2.

Coon-Tacker-Theorems - ein generischer Name für die Behauptungen von sich

lagrange theorem im Falle von Optimierungsaufgaben mit Einschränkungen in Form von Ungleichheit, d. H. Aufgaben

nächster Typ:

gJ (x)\u003e 0, j \u003d 1 ,.

M, (?)

x \u003d (x1, ..., xn) 2 x.

Hier f: x 7! R - (gemäß der etablierten Terminologie) Zielfunktion, Gr: x 7! R,

r \u003d 1 ,. . . , m, - Grenzfunktionen, x _ rn ist ein offener Satz.

Theorem 196 (John Theorem in den Bedingungen von Sedlova):

Lassen Sie die Funktionen f (), G1 () ,. . . , Gn () ist konkav und? X - Lösen des Problems (?), Was? X 2 intx.

Dann gibt es Lagrange Multipliziers _j\u003e

X ist eine Lösung für das Problem

Wir präsentieren diese Anweisungen für den Fall, wenn die Funktionen F, GR differenzierbar sind (Ku-Theorems

auf Tacker in Differentialform).

Erinnern Sie sich an die Funktion

L (x, _) \u003d _0f (x) +

nannte die Funktion von Lagrange (Lagrangian) dieses Problems und den Koeffizienten _j - Multiplikatoren

Lagrange

Es gibt die folgende Anweisung.

Theorem 197 (John Theorem für Differentialfunktionen):

Lassen Sie das Problem lösen (?), Soweit? X 2 Intx und Funktionen F (), G1 () ,. . . , Gn () unterscheiden sich

zirkulas am Punkt? X.

Dann gibt es Lagrange Multipliziers _j\u003e 0, j \u003d 0 ,. . . , m, nicht alle gleich Null, so dass das

die folgenden Verhältnisse (KUNA-TAKKER-Bedingungen) werden durchgeführt:

0, i \u003d 1 ,. . . , N.

J \u003d 0 (Ergänzungsbedingungen ergänzend)

linderung).

Beachten Sie, dass die Ergänzungsbedingungen der Ergänzungszwecke als geschrieben werden können

gj (· x) _j \u003d 0, j \u003d 1 ,. . . , m.

Von diesen Bedingungen folgt, dass, wenn der Lagrange-Multiplizierer positiv ist (_J\u003e 0), dann die entsprechenden

die Einschränkung bei der Lösung des Problems (mit x \u003d × x) wird als Gleichheit ausgeführt (d. H. GJ (? X) \u003d 0). Andere

worte, diese Einschränkung ist aktiv. Andererseits, in dem Fall, wenn GJ (· x)\u003e 0, dann die entsprechenden

lagrange Multiplizierer _j ist Null.

Wenn in dem Problem (?) Teil der Einschränkungen die Form von Einschränkungen auf Nicht-Negativität von einigen Xi hat,

dann können Sie für sie keine Lagrange-Multiplikatoren eingeben, indem Sie solche Einschränkungen separat schreiben:

gJ (x)\u003e 0, j \u003d 1 ,. . . , m, (??)

xi\u003e 0, i 2 p _ (1, ..., n). Im inneren Punkt (im Sinne von That1 & x 2 intx) Bedingungen der ersten Ordnung für I 2 P

wird folgendes haben:

Für I / 2 P hier, wie bei der Darstellung der Aufgabe in der Form (?) Das Derivat der Lagrange-Funktion

durch diese Variable ist das Formular @L (? X, _)

Auch die Bedingungen sind ebenfalls abgeschlossen

Von der zweiten dieser Bedingungen folgt, dass wann? Xi\u003e 0 (i 2 p) gemacht wird

Wenn andererseits, wenn @l (@ X, _) / @ XI eine andere Modifikation des Satzs mit dem Vorhandensein von Einschränkungen in Form von Gleichungen zusammenhängt. Bezeichnen

mit vielen relevanten Indizes bis E. Die Aufgabe hat das folgende Formular:

gj (x)\u003e 0, j 2 (1, ..., m) \\ E,

gJ (x) \u003d 0, j 2 e, (???)

xi\u003e 0, i 2 p _ (1, ..., n).

Gleichzeitig wird der Zustand im John Theorem entfernt, dass alle Lagrange-Multiplizierer nicht negativ sind -

lagrange Multiplizierer _J bei J 2 E können ein beliebiges Zeichen haben.

Der John Theorem garantiert nicht, dass der verzögerte Multiplizierer der Zielfunktion _0 von Null abweicht.

Wenn jedoch _0 \u003d 0 ist, zeichnen sich jedoch die Bedingungen des Kuan-Takkers nicht durch die Entscheidung des unter Berücksichtigung des Problems aus und

die Struktur einer Vielzahl von Einschränkungen an der Stelle? X und der Satz sind nicht direkt mit verbunden

wir Aufgabe zum Maximieren der Funktion f (), da der Gradient der Funktion f (). Fällt. von

coon-Taker abdecken.

Daher ist es wichtig, die Bedingungen zu charakterisieren, die das _0\u003e 0 garantieren.

Solche Bedingungen werden als Regelmäßigkeitsbedingungen bezeichnet.

In dem Fall, wann das unter Berücksichtigung des Betrags konvex ist, einer der Regularitätsbedingungen -

der sogenannte Slateterzustand - hat das Formular:

Wenn die Zielfunktion und Einschränkungen des Problems differenziert sind, werden einfach

die Regelmäßigkeitsbedingung wird in Bezug auf Gradienten von Einschränkungsfunktionen formuliert und hat das Formular:

gradienten aktiver Einschränkungen an der Stelle? X ist linear unabhängig. (In der Anzahl der begrenzten

einschränkungen für Nicht-Negativität sollten ebenfalls enthalten sein.)

Bezeichnen Sie durch eine Reihe von Indizes dieser Einschränkungen, die an der Stelle von Optimum? X aktiv sind

(einschließlich der Indizes aller Einschränkungen in Form von Gleichungen), d. H.

gJ (? x) \u003d 0, j 2 A.

Dann, wenn die Gradienteneinschränkungen - Vektoren

linear unabhängig, dann _0\u003e 0. Dieser Zustand wird als Bedingung der Regelmäßigkeit des Kun-Takker bezeichnet.

Beachten Sie, dass, wenn _0\u003e 0, dann _0 \u003d 1, der normalerweise ohne Verlust der Allgemeinheit erfolgt, in Betracht gezogen werden kann.

Der entsprechende Theorem wird eigentlich (Direct) Kun-Tank-Satz genannt. Theorem 198 (direkter kun-takker theorem, voraussetzung Optimalität):

Lassen Sie die Funktionen f (), G1 () ,. . . , gn () unterscheidet, und? x - Lösen des Problems (?), so dass das

X 2 INTX und der Zustand der Regelmäßigkeit des Kunnel-Tackers ist erfüllt.

Dann gibt es Lagrange Multipliziers _j\u003e 0, j \u003d 1 ,. . . , m, so dass bei _0 \u003d 1 durchgeführt werden

die folgenden Verhältnisse:

0, i \u003d 1 ,. . . , N.

Es ist leicht, diesen Satz für Aufgaben (??) und (???) umformulieren. Hier brauchst du das gleiche

bedingungen von COON-TAKKER-Bedingungen, wie in John Theorem.

0, i \u003d 1 ,. . . , N.

sie können in der Form neu schreiben:

Dieses Verhältnis zeigt, dass der Gradient der Zielfunktion am Punkt des Optimums ein lineares ist

bination von Anti-Anzeigen von Einschränkungen und allen Koeffizienten dieser linearen Kombination

tstenna. Feige. 17.1 zeigt diese Eigenschaft. Intuitiv ist die Idee dieser Eigenschaft das

wenn eine Art linearer Kombinationskoeffizient negativ war, wäre es möglich

erhöhen Sie den Wert der Zielfunktion und bewegen Sie sich entlang dieser Einschränkung. Eine der Optionen des umgekehrten Satzes des Kuna-Takker behauptet, dass, wenn die Funktionen stimmt

f (), (gk ()) führen diese Bedingungen in der zulässigen Lösung aus? X (d. H. Der Punkt, der das Limit erfüllt

nekies) in einigen Lagrange-Multiplikatoren, die den Anforderungen des direkten Satzes entsprechen,

garantiert das? X ist eine Lösung für das Problem.

Theorem 199 (Reverse Theorem Kuna-Tracker / ausreichende Bedingungen für Optimalität /):

Sei f () eine differenzierbare konkave Funktion, G1 () ,. . . , GN () - Differential

quasi-gebackene Funktionen, Set x Convex und Point? X ist in einer Aufgabe (?) Und? X 2 erlaubt

LAGEN gibt es zusätzlich Lagrange Multipliziers _j\u003e 0, j \u003d 1 ,. . . , m, so dass

0 \u003d 1 Die folgenden Verhältnisse werden erfüllt:

0, i \u003d 1 ,. . . , N.

Dann ist X die Lösung des Problems (?).

Der Satz kann offensichtlich für Aufgaben (??) reformuliert und (???). Zur Aufgabe (???)

einschränkungen in Form von Gleichungen können nur linear sein (dies ist darauf zurückzuführen, dass die Einschränkung in der Form

gleichheit, GJ (X) \u003d 0, sollte mit zwei Einschränkungen in Form von Ungleichheiten, GJ (X)\u003e 0 eingereicht werden

und? GJ (X)\u003e 0, von denen jede von einer quasi-Biege-Funktion eingestellt ist; Das kann nur sein, wenn

lineare Grenze).

In einer anderen Ausführungsform sind ausreichende Bedingungen die Optimalität der Annahme des Konkavitätsziels

funktionen werden durch die Annahme der Quasi-Bindung durch den Zusatz des Zustands von RF (· x) 6 \u003d 0 ersetzt.