Wir teilen die dritte Zeile durch das Schlüsselelement gleich 5, wir erhalten die dritte Zeile der neuen Tabelle.

Basissäulen entsprechen Einzelsäulen.

Berechnung der restlichen Tabellenwerte:

"BP - Basisplan":

; ;

"x1": ; ;

"x5": ; .

Die Werte der Indexzeile sind nicht negativ, daher erhalten wir die optimale Lösung: , ; .

Antworten: Der maximale Gewinn aus dem Verkauf von Fertigprodukten in Höhe von 160/3 Einheiten wird durch die Freigabe nur von Produkten des zweiten Typs in Höhe von 80/9 Einheiten sichergestellt.

Aufgabe Nummer 2

Das Problem der nichtlinearen Programmierung ist gegeben. Finden Sie das Maximum und Minimum der Zielfunktion mit einer graphanalytischen Methode. Stellen Sie die Lagrange-Funktion auf und zeigen Sie, dass die hinreichenden Mindest- (Maximal-) Bedingungen an den Extrempunkten erfüllt sind.

weil die letzte Ziffer der Chiffre ist 8, dann ist A=2; B=5.

weil Die vorletzte Ziffer der Chiffre ist 1, dann sollten Sie die Aufgabennummer 1 wählen.

Entscheidung:

1) Lassen Sie uns den Bereich zeichnen, den das Ungleichungssystem definiert.

Dieser Bereich ist ein Dreieck ABC mit den Koordinaten der Eckpunkte: A(0; 2); B(4; 6) und C(16/3; 14/3).

Die Zielfunktionsniveaus sind Kreise, die um den Punkt (2; 5) zentriert sind. Die Quadrate der Radien sind die Werte der Zielfunktion. Dann zeigt die Abbildung, dass der Minimalwert der Zielfunktion im Punkt H erreicht wird, der Maximalwert entweder im Punkt A oder im Punkt C liegt.

Der Wert der Zielfunktion am Punkt A: ;

Der Wert der Zielfunktion am Punkt C: ;

Das bedeutet, dass der Maximalwert der Funktion am Punkt A(0; 2) erreicht ist und gleich 13 ist.

Lassen Sie uns die Koordinaten des Punktes H finden.

Betrachten Sie dazu das System:

ó

ó

Eine Gerade ist eine Tangente an einen Kreis, wenn die Gleichung eine eindeutige Lösung hat. Eine quadratische Gleichung hat eine eindeutige Lösung, wenn die Diskriminante 0 ist.

Dann ; ; - der Mindestwert der Funktion.

2) Erstellen Sie die Lagrange-Funktion, um die minimale Lösung zu finden:

Beim x 1 =2.5; x 2 =4.5 wir bekommen:

ó

Das System hat eine Lösung für , d.h. hinreichende Extrembedingungen erfüllt sind.

Wir bilden die Lagrange-Funktion zum Finden der maximalen Lösung:

Hinreichende Bedingungen für ein Extremum:

Beim x 1 =0; x 2 =2 wir bekommen:

ó ó

Das System hat auch eine Lösung, d.h. hinreichende Extrembedingungen erfüllt sind.

Antworten: das Minimum der Zielfunktion wird erreicht ; ; Die maximale Zielfunktion ist erreicht, wenn ; .

Aufgabe Nummer 3

Zwei Unternehmen werden Mittel in dieser Höhe zugeteilt d Einheiten. Bei Zuteilung an das erste Unternehmen für ein Jahr x Einheiten von Fonds, die es Einkommen liefert k 1 x Einheiten und bei Zuordnung zum zweiten Unternehmen j Einheiten von Fonds, es bietet Einkommen k 1 j Einheiten. Der Finanzierungssaldo am Ende des Jahres für das erste Unternehmen ist gleich nx, und zum zweiten mein. Wie verteilt man alle Gelder innerhalb von 4 Jahren so, dass die Gesamteinnahmen am größten sind? Lösen Sie das Problem durch dynamische Programmierung.

i=8, k=1.

A=2200; k 1 = 6; k2=1; n = 0,2; m=0,5.

Entscheidung:

Der gesamte Zeitraum von 4 Jahren ist in 4 Phasen unterteilt, die jeweils einem Jahr entsprechen. Nummerieren wir die Etappen ab dem ersten Jahr. Seien X k und Y k die den Unternehmen A bzw. B in der k-ten Stufe zugeteilten Mittel. Dann ist die Summe X k + Y k = a k der Gesamtbetrag der Mittel, die in der k – dieser Stufe verwendet wurden und von der vorherigen Stufe k – 1 übrig bleiben. In der ersten Stufe werden alle zugewiesenen Mittel verwendet und a 1 = 2200 Einheiten. das Einkommen, das in der k - Phase erzielt wird, wenn X k und Y k Einheiten zugeteilt werden, beträgt 6X k + 1Y k . Lassen Sie das maximale Einkommen in den letzten Phasen erhalten, beginnend mit dem k - diese Phase ist f k (a k) Einheiten. Lassen Sie uns die Bellman-Funktionsgleichung schreiben, die das Prinzip der Optimalität ausdrückt: Unabhängig vom Anfangszustand und der Anfangslösung muss die nachfolgende Lösung in Bezug auf den Zustand, der als Ergebnis des Anfangszustands erhalten wird, optimal sein:

Für jede Stufe müssen Sie den Wert X k und den Wert auswählen Y k= eink- Xk. In diesem Sinne finden wir Einkommen auf der k-ten Stufe:

Die funktionale Bellman-Gleichung sieht folgendermaßen aus:

Betrachten Sie alle Phasen, beginnend mit der letzten.

(da das Maximum der linearen Funktion am Segmentende bei x 4 = a 4 erreicht wird);

Bundesamt für Bildung

Staatliche Bildungseinrichtung

höhere Berufsausbildung

Staatliche Technische Universität Omsk

BERECHNUNG UND GRAFISCHE ARBEIT

nach Disziplin "THEORIE DER OPTIMALEN STEUERUNG »

zum Thema "OPTIMIERUNGSMETHODEN UND OPERATIONS RESEARCH »

Möglichkeit 7

Abgeschlossen:

Fernstudent

4. Jahrgang ZA-419

Name: Kuzhelev S. A.

Geprüft:

Devyaterikova M.V.

Omsk - 2012
^

Aufgabe 1. Grafische Methode zur Lösung linearer Programmierprobleme.

7) 7x 1 + 6x 2 → max 20x 1 + 6x 2 ≤ 15 16x 1 − 2x 2 ≤ 18 8x 1 + 4x 2 ≤ 20 13x 1 + 3x 2 ≤ 4 x 1 , x 2 ≥ 0.

Schritt 1. Erstellen eines gültigen Bereichs

Die Bedingungen der Nicht-Negativität von Variablen und Quadraten begrenzen den Bereich ihrer zulässigen Werte auf den ersten Quadranten. Jede der verbleibenden vier Beschränkungsungleichungen des Modells entspricht einer Halbebene. Der Schnittpunkt dieser Halbebenen mit dem ersten Quadranten bildet die Menge zulässiger Lösungen des Problems.

Die erste Einschränkung des Modells ist . Ersetzen wir darin das Zeichen ≤ durch das Zeichen =, erhalten wir die Gleichung . Auf Abb. 1.1 definiert eine Linie (1), die die Ebene in zwei Halbebenen teilt, in diesem Fall oberhalb und unterhalb der Linie. Zu wählen, welche die Ungleichung erfüllt , setzen wir die Koordinaten jedes Punktes ein, der nicht auf der gegebenen Linie liegt (z. B. den Ursprung X 1 = 0, X 2 = 0). Da wir den richtigen Ausdruck erhalten (20 0 + 6 0 = 0 ≤15), erfüllt die Halbebene, die den Ursprung enthält (mit einem Pfeil markiert), die Ungleichung. Ansonsten ein weiteres Halbflugzeug.

Analog verfahren wir mit den restlichen Nebenbedingungen des Problems. Der Schnittpunkt aller konstruierten Halbebenen mit dem ersten Quadranten bildet sich A B C D(siehe Abb. 1). Dies ist der gültige Umfang der Aufgabe.

Schritt 2. Aufbau einer Levelline Levelline Zielfunktion ist eine Menge von Punkten in der Ebene, an denen die Zielfunktion einen konstanten Wert annimmt. Eine solche Menge ist durch die Gleichung gegeben f ( x) = konst. Sagen wir zum Beispiel, konst = 0 und ziehen Sie eine Linie auf der Ebene f ( x) = 0, d. h. in unserem Fall direkt 7 x 1 + 6x 2 = 0.

Diese Gerade geht durch den Ursprung und steht senkrecht auf dem Vektor . Dieser Vektor ist der Zielfunktionsgradient bei (0,0). Der Gradient einer Funktion ist ein Vektor von Werten der partiellen Ableitungen einer bestimmten Funktion an dem betreffenden Punkt. Beim LP-Problem sind die partiellen Ableitungen der Zielfunktion gleich den Koeffizienten Cich, j = 1 , ..., n.

Der Gradient zeigt die Richtung des schnellsten Wachstums der Funktion. Verschieben der Linie der Zielfunktionsebene f ( x) = konst. Suchen Sie senkrecht zur Richtung des Farbverlaufs den letzten Punkt, an dem er sich mit der Fläche schneidet. In unserem Fall ist dies der Punkt D, der der maximale Punkt der Zielfunktion sein wird (siehe Abb. 2).

Sie liegt am Schnittpunkt der Linien (2) und (3) (siehe Abb. 1) und stellt die optimale Lösung ein.

^ Beachten Sie, dass, wenn es erforderlich ist, den Minimalwert der Zielfunktion zu finden, die Niveaulinie in die Richtung entgegengesetzt zur Richtung des Gradienten bewegt wird.

^ Schritt 3. Bestimmen der Koordinaten des maximalen (minimalen) Punktes und des optimalen Wertes der Zielfunktion

Um die Koordinaten des Punktes C zu finden, muss ein System gelöst werden, das aus den entsprechenden direkten Gleichungen besteht (in diesem Fall aus den Gleichungen 2 und 3):

16x 1 − 2x 2 ≤ 18

8x 1 + 4x 2 ≤ 20

Wir erhalten die optimale Lösung = 1,33.

^ Der optimale Wert der Zielfunktion f * = f (X*) = 7 * 0 + 6 * 1,33 = 7,8

Entscheidung: Finden Sie den maximalen und minimalen Wert der Funktion \(f (x, y)\) unter den folgenden Einschränkungen $$ f(x,y)=(x-4)^2 + (y-3)^2 \rightarrow max,min \ \ \begin(cases) 2x+3y\geq 6 \\ 3x-2y\leq 18\\ -x+2y\leq 8\\ x,y\geq0\end(cases) $$
Bei Aufgaben mit zwei Variablen, die symmetrisch geschrieben sind, sowie bei Aufgaben mit vielen Variablen empfiehlt sich die grafische Lösungsmethode, sofern deren kanonische Schreibweise nicht mehr als zwei freie Variablen enthält.

In diesem Fall eine Aufgabe mit zwei Variablen.

Algorithmus zur Lösung des Problems "geometrische Interpretation eines linearen Programmierproblems":

1. Konstruieren wir den Definitionsbereich zulässiger Lösungen auf der xOy-Ebene.
2. Wählen Sie den Bereich der nicht negativen Lösungen aus.

4. Konstruieren wir eine Familie von Zielfunktionen.
5. Finden Sie den maximalen (minimalen) Wert der Zielfunktion.

1. Wir konstruieren den Definitionsbereich zulässiger Lösungen des Problems \(D\).

So bauen Sie den Bereich der machbaren Lösungen auf:
1) Wir bauen Grenzlinien:
wir verwandeln die Ungleichungen in Gleichheiten und dann in die Gleichung einer geraden Linie in Segmenten auf den Achsen der Form \(\frac(x)(a)+\frac(y)(b) = 1\), dann \ (x=a\) ist ein auf der Ox-Achse abgeschnittenes Segment, \(y=b\) - auf der Oy-Achse $$ \begin(cases) 2x+3y = 6 \\ 3x-2y = 18\\ - x+2y = 8 \end(cases) => \begin(cases) \frac(x)(3)+\frac(y)(2) = 1 \\ \frac(x)(8)-\frac( y)(9) = 1 \\ -\frac (x)(6)+ \frac(y)(4) = 1 \end(cases) $$ Lege für jede Linie Segmente auf den Achsen beiseite und verbinde sie. Wir haben die richtigen Linien.

2) Wir finden Halbebenen, die die gegebenen Ungleichungen erfüllen:
Für die Ungleichung \(2x+3y\geq 6\) ist die Halbebene, die über der Geraden \(2x+3y = 6\) liegt. Direkte Klimaanlage
Denn die Ungleichung \(3x-2y\leq 18 => -3x+2y \geq -18\) ist eine Halbebene, die über der Geraden \(3x-2y = 18\) liegt. Direkt CB
Für die Ungleichung ist \(-x+2y\leq 8\) die Halbebene, die unterhalb der Geraden \(-x+2y = 8\) liegt. Direkt AB

Der Bereich zulässiger Lösungen ist definiert als der gemeinsame Teil der drei Halbebenen, die den gegebenen Ungleichungen entsprechen. Dieser Bereich ist ein Dreieck \(ABC\)

Die Region \(D\) ist das Dreieck \(ABC\) siehe Abb.

2. Wählen Sie den Bereich der nicht negativen Lösungen aus.

Der Bereich nicht negativer Lösungen liegt im ersten Viertel und ist ein gemeinsamer Teil aller fünf Halbebenen, von denen drei der aus Ungleichungen gewonnene Bereich \(D\) sind und zusätzlich zwei Ungleichungen \(x \geq 0\ ) - die obere Halbebene (I- und II-Viertel) und \(y \geq 0\) - die rechte Halbebene (I- und IV-Viertel), die die Bedingung der Nicht-Negativität der Variablen \(x; y\). Erhalten Sie den gewünschten Bereich nicht negativer Lösungen \(DEBFG\)

3.Finden Sie die Koordinaten der Scheitelpunkte der Region.
Die Koordinaten der vier Eckpunkte sind bereits bekannt (das sind die Schnittpunkte der Geraden mit den Achsen).
Schreiben wir diese Koordinaten auf:
\(D(0;2)\), \(E(0;4)\), \(F(6;0)\), \(G(3;0)\)
Ermitteln Sie die Koordinaten des Punktes \(B\) als Schnittpunkte der Linien \(-x+2y = 8\) und \(3x-2y = 18\). Löse das Gleichungssystem und finde die Koordinaten dieses Punktes $$\begin(cases) -x+2y = 8\\ 3x-2y = 18\end(cases)=> \begin(cases) 2x = 26\\ 3x -2y = 18 \end(cases)=> \begin(cases) x = 13\\ y =10.5\end(cases)$$
Wir haben die Koordinaten des Punktes \(B(13;10.5)\)

4. Wir bauen eine Familie von Zielfunktionen auf.
Die Gleichung \(f(x,y)=(x-4)^2 + (y-3)^2 \rightarrow max,min\) definiert auf der xOy-Ebene eine Familie konzentrischer Kreise, deren Mittelpunkt der Punkt mit den Koordinaten \ (Q(4 ;3)\), die jeweils einem bestimmten Wert des Parameters \(f\) entsprechen. Wie Sie wissen, ist für die Kreisgleichung der Parameter \(f=R^2\).

Stellen wir im selben Koordinatensystem eine Schar konzentrischer Kreise \(f\) und eine Schar von Geraden dar. Das Problem, den maximalen (minimalen) Punkt des Punktes \(f\) zu bestimmen, wird darauf reduziert, im zulässigen Bereich den Punkt zu finden, durch den der Kreis der Familie \(f=const\) verläuft, der für die verantwortlich ist größter (kleinster) Wert des Parameters \(f\).

5. Finden Sie den maximalen (minimalen) Wert der Zielfunktion.

Minimaler Zielfunktionswert: Indem wir den Radius des Kreises allmählich vergrößern, haben wir erreicht, dass der erste Scheitelpunkt, durch den der Kreis verläuft, der Punkt \(G(3;0)\) ist. Die Zielfunktion an diesem Punkt ist minimal und gleich \(f(3,0)=(3-4)^2 + (0-3)^2 = 10\)

Der Maximalwert der Zielfunktion: Indem wir den Radius des Kreises weiter vergrößern, haben wir erreicht, dass der letzte Scheitelpunkt, durch den der Kreis verläuft, der Punkt \(B(13;10.5)\) ist. Die Zielfunktion an diesem Punkt ist maximal und gleich \(f(13,10,5)=(13-4)^2 + (10,5-3)^2 = 137,25\)

Sie können die Richtigkeit der Lösung überprüfen, indem Sie die Koordinaten der verbleibenden Scheitelpunkte in die Zielfunktionsgleichung einsetzen:
am Scheitelpunkt \(D(0;2)\) ist der Wert der Zielfunktion gleich \(f(0,2)=(0-4)^2 + (2-3)^2 = 17\)
am Scheitel \(E(0;4)\) ist der Wert der Zielfunktion gleich \(f(0,4)=(0-4)^2 + (4-3)^2 = 17\)
am Scheitelpunkt \(F(6;0)\) ist der Wert der Zielfunktion \(f(6,4)=(6-4)^2 + (0-3)^2 = 13\)
Verstanden

Antworten:
der Minimalwert der Zielfunktion \(f_(min) = 10\)
der Maximalwert der Zielfunktion \(f_(max) = 137,25\)

Zielfunktion- reelle oder ganzzahlige Funktion mehrerer Variablen, die einer Optimierung (Minimierung oder Maximierung) unterzogen werden, um ein Optimierungsproblem zu lösen. Der Begriff wird in der mathematischen Programmierung, Operations Research, linearen Programmierung, statistischen Entscheidungstheorie und anderen Bereichen der Mathematik verwendet, hauptsächlich angewandter Natur, obwohl das Ziel der Optimierung auch die Lösung eines mathematischen Problems selbst sein kann. Neben der Zielfunktion können im Optimierungsproblem Variablen Restriktionen in Form eines Systems von Gleichheiten oder Ungleichungen unterliegen. Im allgemeinen Fall können die Zielfunktionsargumente auf beliebigen Mengen angegeben werden.

Beispiele

Glatte Funktionen und Gleichungssysteme

Das Problem, ein beliebiges Gleichungssystem zu lösen

( F 1 (x 1 , x 2 , … , x M) = 0 F 2 (x 1 , x 2 , … , x M) = 0 … F N (x 1 , x 2 , … , x M) = 0 ( \displaystyle \left\((\begin(matrix)F_(1)(x_(1),x_(2),\ldots ,x_(M))=0\\F_(2)(x_(1),x_ (2),\ldots ,x_(M))=0\\\ldots \\F_(N)(x_(1),x_(2),\ldots ,x_(M))=0\end(matrix) )\Rechts.)

kann als Problem der Minimierung der Zielfunktion formuliert werden

S = ∑ j = 1 N F j 2 (x 1 , x 2 , … , x M) (1) (\displaystyle S=\sum _(j=1)^(N)F_(j)^(2)( x_(1),x_(2),\ldots ,x_(M))\qquad(1))

Wenn die Funktionen glatt sind, kann das Minimierungsproblem durch Gradientenverfahren gelöst werden.

Für jede glatte Zielfunktion kann man die partiellen Ableitungen in Bezug auf alle Variablen mit 0 (\displaystyle 0) gleichsetzen. Die optimale Zielfunktion wird eine der Lösungen eines solchen Gleichungssystems sein. Im Fall von Funktion (1) (\displaystyle (1)) ist dies ein Gleichungssystem der kleinsten Quadrate (LSM). Jede Lösung des ursprünglichen Systems ist eine Lösung des Systems der kleinsten Quadrate. Wenn das Originalsystem inkonsistent ist, ermöglicht das LSM-System, das immer eine Lösung hat, eine Näherungslösung des Originalsystems. Die Anzahl der Gleichungen des LSM-Systems stimmt mit der Anzahl der Unbekannten überein, was manchmal die Lösung gemeinsamer Anfangssysteme erleichtert.

Lineares Programmieren

Ein weiteres bekanntes Beispiel einer Zielfunktion ist eine lineare Funktion, die bei linearen Programmierproblemen auftritt. Im Gegensatz zur quadratischen Zielfunktion ist die Optimierung einer linearen Funktion nur möglich, wenn Restriktionen in Form eines Systems linearer Gleichheiten oder Ungleichungen vorliegen.

Kombinatorische Optimierung

Ein typisches Beispiel für eine kombinatorische Zielfunktion ist die Zielfunktion des Problems des Handlungsreisenden. Diese Funktion ist gleich der Länge des Hamilton-Zyklus im Diagramm. Sie ist auf dem Permutationssatz n − 1 (\displaystyle n-1) der Scheitelpunkte des Graphen angegeben und wird durch die Kantenlängenmatrix des Graphen bestimmt. Die genaue Lösung solcher Probleme läuft oft auf die Aufzählung von Optionen hinaus.

Kapitel 1. Erklärung des Hauptproblems der linearen Programmierung

1. Lineares Programmieren

Die lineare Programmierung ist ein Zweig der mathematischen Programmierung, der Methoden zur Lösung extremaler Probleme untersucht, die durch eine lineare Beziehung zwischen Variablen und einem linearen Kriterium gekennzeichnet sind. Solche Aufgaben finden umfangreiche Anwendungen in verschiedenen Bereichen der menschlichen Tätigkeit. Eine systematische Untersuchung solcher Probleme begann 1939–1940. in den Werken von L.V. Kantorowitsch.

Zu den mathematischen Problemen der linearen Programmierung gehört die Untersuchung spezifischer Produktions- und Wirtschaftssituationen, die in der einen oder anderen Form als Probleme der optimalen Nutzung begrenzter Ressourcen interpretiert werden.

Die Palette der Problemstellungen, die mit Methoden der linearen Programmierung gelöst werden können, ist sehr breit, beispielsweise sind dies:

das Problem des optimalen Ressourceneinsatzes in der Produktionsplanung;

das Problem der Mischungen (Planung der Zusammensetzung von Produkten);

das Problem, die optimale Kombination verschiedener Arten von Produkten für die Lagerung in Lagern zu finden (Bestandsverwaltung oder);

Transportaufgaben (Analyse des Standorts des Unternehmens, Warenverkehr).

Die lineare Programmierung ist der am weitesten entwickelte und am weitesten verbreitete Teil der mathematischen Programmierung (zusätzlich dazu gehören: ganzzahlige, dynamische, nichtlineare, parametrische Programmierung). Dies wird wie folgt erklärt:

mathematische Modelle einer Vielzahl ökonomischer Probleme sind linear in Bezug auf die erforderlichen Variablen;

Diese Art von Problemen wird derzeit am besten untersucht. Für ihn wurden spezielle Methoden entwickelt, mit deren Hilfe diese Probleme gelöst werden, und die entsprechenden Computerprogramme;

Viele Probleme der linearen Programmierung haben nach ihrer Lösung breite Anwendung gefunden;

Einige Probleme, die in der ursprünglichen Formulierung nicht linear sind, können nach einer Reihe zusätzlicher Einschränkungen und Annahmen linear werden oder auf eine solche Form reduziert werden, dass sie durch lineare Programmiermethoden gelöst werden können.

Das ökonomische und mathematische Modell jedes linearen Programmierproblems beinhaltet: eine objektive Funktion, deren optimaler Wert (Maximum oder Minimum) gefunden werden muss; Beschränkungen in Form eines Systems linearer Gleichungen oder Ungleichungen; Erfordernis der Nicht-Negativität von Variablen.

Im Allgemeinen wird das Modell wie folgt geschrieben:

Zielfunktion

(1.1) unter den Beschränkungen

(1.2) Nicht-Negativitätsanforderungen

(1.3) wo x j– Variablen (Unbekannte);

- Koeffizienten des Problems der linearen Programmierung.

Das Problem besteht darin, den optimalen Wert der Funktion (1.1) unter den Bedingungen (1.2) und (1.3) zu finden.

Das System der Nebenbedingungen (1.2) wird als funktionale Nebenbedingungen des Problems bezeichnet, und die Nebenbedingungen (1.3) werden als direkte Nebenbedingungen bezeichnet.

Ein Vektor, der die Nebenbedingungen (1.2) und (1.3) erfüllt, wird als zulässige Lösung (Plan) eines linearen Programmierproblems bezeichnet. Der Plan, für den die Funktion (1.1) ihren maximalen (minimalen) Wert erreicht, wird als optimal bezeichnet.

1.2. Simplex-Verfahren zur Lösung linearer Programmierprobleme

Das Simplex-Verfahren wurde 1947 von dem amerikanischen Mathematiker J. Danzig entwickelt und erstmals zur Problemlösung angewendet.

Zweidimensionale Probleme der linearen Programmierung werden grafisch gelöst. Für den Fall N=3 können wir einen dreidimensionalen Raum betrachten und die Zielfunktion erreicht ihren optimalen Wert an einem der Eckpunkte des Polyeders.

Eine zulässige Lösung (ein zulässiger Plan) eines LP-Problems in Standardform ist eine geordnete Menge von Zahlen (x1, x2, ..., xn), die die Nebenbedingungen erfüllen; ein Punkt im n-dimensionalen Raum ist.

Die Menge der zulässigen Lösungen bildet den Bereich der zulässigen Lösungen (SDR) des LP-Problems. ODR ist ein konvexes Polyeder (Polygon).

Wenn N-Unbekannte an dem Problem beteiligt sind, können wir allgemein sagen, dass der durch das System der Randbedingungen festgelegte Bereich der zulässigen Lösungen durch ein konvexes Polyeder im n-dimensionalen Raum und den optimalen Wert des Ziels dargestellt wird Funktion wird an einem oder mehreren Eckpunkten erreicht.

Eine Lösung heißt einfach, wenn alle freien Variablen gleich Null sind.

Eine Referenzlösung ist eine basische nicht negative Lösung. Die Trägerlösung kann nicht degeneriert und degeneriert sein. Eine Stützlösung heißt nicht entartet, wenn die Anzahl ihrer Nicht-Null-Koordinaten gleich dem Rang des Systems ist, andernfalls ist sie entartet.

Eine zulässige Lösung, bei der die Zielfunktion ihren Extremwert erreicht, heißt optimal und wird bezeichnet .

Es ist sehr schwierig, diese Probleme grafisch zu lösen, wenn die Anzahl der Variablen mehr als 3 beträgt. Es gibt einen universellen Weg, um Probleme der linearen Programmierung zu lösen, die so genannte Simplex-Methode.

Die Simplex-Methode ist eine universelle Methode zur Lösung von LP-Problemen, die ein iterativer Prozess ist, der mit einer Lösung beginnt und sich auf der Suche nach der besten Option entlang der Eckpunkte des Bereichs der machbaren Lösungen bewegt, bis er den optimalen Wert erreicht .

Es kann verwendet werden, um jedes Problem der linearen Programmierung zu lösen.

Die Simplex-Methode basiert auf der Idee der sukzessiven Verbesserung der resultierenden Lösung.

Die geometrische Bedeutung der Simplex-Methode besteht darin, sich nacheinander von einem Scheitelpunkt des Beschränkungspolyeders zum benachbarten zu bewegen, in dem die Zielfunktion den besten (oder zumindest nicht den schlechtesten) Wert annimmt, bis die optimale Lösung gefunden ist - der Scheitelpunkt wo der optimale Wert ist die erreichte Zielfunktion (wenn das Problem ein endliches Optimum hat).

Wenn man also ein auf die kanonische Form reduziertes System von Beschränkungen hat (alle funktionalen Beschränkungen haben die Form von Gleichheiten), findet man jede grundlegende Lösung dieses Systems, wobei man nur darauf achtet, sie so einfach wie möglich zu finden. Hat sich die zuerst gefundene Basislösung als machbar herausgestellt, wird sie auf Optimalität geprüft. Ist sie nicht optimal, so wird auf eine andere, zwingend zulässige Grundlösung übergegangen. Das Simplex-Verfahren garantiert bei dieser neuen Lösung, dass sich die Zielfunktion, wenn sie das Optimum nicht erreicht, diesem annähert (oder sich zumindest nicht davon entfernt). Mit einer neuen zulässigen Basislösung wird so lange verfahren, bis eine optimale Lösung gefunden ist.

Der Prozess der Anwendung der Simplex-Methode umfasst die Implementierung ihrer drei Hauptelemente:

ein Verfahren zum Bestimmen einer anfänglichen praktikablen Basislösung für das Problem;

die Übergangsregel zur besten (genauer gesagt nicht zur schlechtesten) Lösung;

Kriterium zur Überprüfung der Optimalität der gefundenen Lösung.

Das Simplex-Verfahren umfasst eine Reihe von Schritten und kann als klarer Algorithmus formuliert werden (eine klare Anweisung zur Durchführung sequentieller Operationen). Dadurch können Sie es erfolgreich auf einem Computer programmieren und implementieren. Probleme mit einer kleinen Anzahl von Variablen und Nebenbedingungen können mit der Simplex-Methode manuell gelöst werden.

6.1 Einführung

Optimierung. Teil 1

Optimierungsmethoden ermöglichen es Ihnen, aus allen möglichen Optionen die beste Designoption auszuwählen. Diesen Methoden wurde in den letzten Jahren viel Aufmerksamkeit geschenkt, und als Ergebnis wurden eine Reihe von hocheffizienten Algorithmen entwickelt, die es ermöglichen, die optimale Designoption mit einem digitalen Computer zu finden. Dieses Kapitel umreißt die Grundlagen der Optimierungstheorie, betrachtet die Prinzipien, die der Konstruktion von Algorithmen für optimale Lösungen zugrunde liegen, beschreibt die bekanntesten Algorithmen und analysiert ihre Vor- und Nachteile.

6.2 Grundlagen der Optimierungstheorie

Der Begriff "Optimierung" in der Literatur bezieht sich auf einen Prozess oder eine Abfolge von Operationen, die es Ihnen ermöglichen, eine verfeinerte Lösung zu erhalten. Obwohl das ultimative Ziel der Optimierung darin besteht, die beste oder "optimale" Lösung zu finden, muss man sich normalerweise damit begnügen, bekannte Lösungen zu verbessern, anstatt sie zu perfektionieren. Daher ist Optimierung eher als Streben nach Perfektion zu verstehen, die möglicherweise nicht erreicht wird.

Wenn wir ein beliebiges System betrachten, das durch m Gleichungen mit n Unbekannten beschrieben wird, können wir drei Haupttypen von Problemen unterscheiden. Wenn m=n , heißt das Problem algebraisch. Für ein solches Problem gibt es normalerweise eine Lösung. Ist m > n, so wird das Problem neu definiert und hat in der Regel keine Lösung. Schließlich für m

Bevor wir mit der Diskussion von Optimierungsfragen fortfahren, führen wir eine Reihe von Definitionen ein.

Design-Parameter

Dieser Begriff bezeichnet unabhängige variable Parameter, die das zu lösende Entwurfsproblem vollständig und eindeutig definieren. Designparameter sind unbekannte Größen, deren Werte während des Optimierungsprozesses berechnet werden. Als Auslegungsparameter können beliebige Grund- oder abgeleitete Größen dienen, die der quantitativen Beschreibung des Systems dienen. Es können also unbekannte Werte für Länge, Masse, Zeit, Temperatur sein. Die Anzahl der Designparameter charakterisiert den Komplexitätsgrad dieses Designproblems. Üblicherweise wird die Anzahl der Designparameter mit n bezeichnet und die Designparameter selbst mit x mit den entsprechenden Indizes. Somit werden n Entwurfsparameter dieses Problems mit bezeichnet

X1, x2, x3,...,xn.

Zielfunktion

Dies ist der Ausdruck, dessen Wert der Ingenieur maximieren oder minimieren möchte. Mit der Zielfunktion können Sie zwei alternative Lösungen quantitativ vergleichen. Aus mathematischer Sicht beschreibt die Zielfunktion eine (n+1)-dimensionale Fläche. Sein Wert wird durch die Designparameter bestimmt

M=M(x 1 , x 2 , ..., x n).

Beispiele für die in der Ingenieurpraxis häufig anzutreffende Zielfunktion sind Kosten, Gewicht, Festigkeit, Abmessungen, Effizienz. Wenn es nur einen Designparameter gibt, kann die Zielfunktion durch eine Kurve auf einer Ebene dargestellt werden (Abb. 6.1). Bei zwei Designparametern wird die Zielfunktion durch eine Fläche im dreidimensionalen Raum dargestellt (Abb. 6.2). Bei drei oder mehr Designparametern werden die durch die Zielfunktion spezifizierten Flächen als Hyperflächen bezeichnet und können nicht dargestellt werden.

zheniya konventionelle Mittel. Die topologischen Eigenschaften der Zielfunktionsfläche spielen im Optimierungsprozess eine wichtige Rolle, da davon die Wahl des effizientesten Algorithmus abhängt.

Die Zielfunktion kann in einigen Fällen die unerwartetsten Formen annehmen. Zum Beispiel ist es nicht immer möglich, es auszudrücken

Abb. 1. Eindimensionale Zielfunktion.

Abb.6.2.Zweidimensionale Zielfunktion.

geschlossene mathematische Form, in anderen Fällen schon

eine stückweise glatte Funktion sein. Eine objektive Funktion kann manchmal eine technische Datentabelle (z. B. eine Dampfzustandstabelle) erfordern oder es kann notwendig sein, ein Experiment durchzuführen. In einigen Fällen nehmen Entwurfsparameter nur ganzzahlige Werte an. Ein Beispiel wäre die Anzahl der Zähne in einem Zahnrad oder die Anzahl der Schrauben in einem Flansch. Manchmal haben Designparameter nur zwei Werte - ja oder nein. Qualitative Parameter wie Kundenzufriedenheit, Zuverlässigkeit, Ästhetik sind im Optimierungsprozess nur schwer zu berücksichtigen, da sie kaum zu quantifizieren sind. Unabhängig davon, in welcher Form die Zielfunktion dargestellt wird, muss es sich jedoch um eine einwertige Funktion der Entwurfsparameter handeln.

Bei einer Reihe von Optimierungsproblemen ist die Einführung von mehr als einer Zielfunktion erforderlich. Manchmal kann einer von ihnen mit dem anderen inkompatibel sein. Ein Beispiel ist das Design von Flugzeugen, wenn es gleichzeitig auf maximale Festigkeit, minimales Gewicht und minimale Kosten ankommt. In solchen Fällen muss der Konstrukteur ein System von Prioritäten einführen und jeder Zielfunktion einen dimensionslosen Multiplikator zuweisen. Als Ergebnis erscheint eine „Kompromissfunktion“, die es ermöglicht, eine zusammengesetzte Zielfunktion im Optimierungsprozess zu verwenden.

Minimum und Maximum finden

Einige Optimierungsalgorithmen sind zum Auffinden des Maximums geeignet, andere zum Auffinden des Minimums. Unabhängig von der Art des zu lösenden Extremumproblems kann jedoch derselbe Algorithmus verwendet werden, da das Minimierungsproblem leicht in ein Maximumproblem umgewandelt werden kann, indem das Vorzeichen der Zielfunktion in das Gegenteil geändert wird. Diese Technik ist in Abbildung 6.3 dargestellt.

Raum gestalten

Dies ist der Name des Bereichs, der durch alle n Entwurfsparameter definiert wird. Der Gestaltungsspielraum ist nicht so groß, wie es scheinen mag, da er normalerweise auf eine Anzahl beschränkt ist

Bedingungen, die mit der physikalischen Essenz des Problems verbunden sind. Einschränkungen können so stark sein, dass die Aufgabe keine hat

Abb. 6.3 Wechsel des Vorzeichens der Zielfunktion in das Gegenteil

Die maximale Aufgabe wird zur minimalen Aufgabe.

zufriedenstellende Lösung. Beschränkungen werden in zwei Gruppen unterteilt: Beschränkungen - Gleichheiten und Beschränkungen - Ungleichheiten.

Einschränkungen - Gleichheit

Einschränkungen – Gleichheiten – sind die Abhängigkeiten zwischen Konstruktionsparametern, die bei der Lösungsfindung berücksichtigt werden müssen. Sie spiegeln Naturgesetze, Ökonomie, Rechte, vorherrschende Geschmäcker und die Verfügbarkeit der notwendigen Materialien wider. Die Anzahl der Einschränkungen - Gleichheiten können beliebig sein. Sie sehen aus wie

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

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

..................

C j (x 1 , x 2 , ..., x n)=0.

Wenn eine dieser Beziehungen in Bezug auf einen der Konstruktionsparameter aufgelöst werden kann, können Sie diesen Parameter aus dem Optimierungsprozess ausschließen. Dies reduziert die Anzahl der Dimensionen des Bauraums und vereinfacht die Lösung des Problems.

Einschränkungen - Ungleichheiten

Dies ist eine spezielle Art von Beschränkung, die durch Ungleichungen ausgedrückt wird. Im allgemeinen Fall können es beliebig viele sein, und alle haben die Form

z 1 r 1 (x 1 , x 2 ,...,x n) Z 1

z 2 r 2 (x 1 , x 2 ,...,x n) Z 2

.......................

z k r k (x 1 , x 2 ,...,x n) Z k

Es ist zu beachten, dass sehr oft aufgrund von Einschränkungen der optimale Wert der Zielfunktion nicht erreicht wird, wenn ihre Oberfläche eine Steigung von Null hat. Oft liegt die beste Lösung an einer der Grenzen der Designdomäne.

Lokales Optimum

So heißt der Punkt im Entwurfsraum, an dem die Zielfunktion den größten Wert im Vergleich zu ihren Werten an allen anderen Punkten in ihrer unmittelbaren Nachbarschaft hat.

Abb. 6.4: Eine beliebige Zielfunktion kann mehrere haben

lokale Optima.

Auf Abb. Abbildung 6.4 zeigt eine eindimensionale Zielfunktion, die zwei lokale Optima hat. Oft enthält der Entwurfsraum viele lokale Optima, und es muss darauf geachtet werden, dass das erste nicht mit der optimalen Lösung des Problems verwechselt wird.

Globales Optimum

Das globale Optimum ist die optimale Lösung für den gesamten Designraum. Es ist besser als alle anderen Lösungen, die lokalen Optima entsprechen, und das ist es, wonach der Designer sucht. Der Fall mehrerer gleicher globaler Optima, die sich in verschiedenen Teilen des Entwurfsraums befinden, ist möglich. Wie sich das Optimierungsproblem stellt, lässt sich am besten an einem Beispiel verdeutlichen.

Beispiel 6.1

Es sei erforderlich, einen rechteckigen Behälter mit einem Volumen von 1 m zu entwerfen, der für den Transport von unverpackten Fasern ausgelegt ist. Es ist wünschenswert, dass für die Herstellung solcher Behälter so wenig Material wie möglich aufgewendet wird (bei einer konstanten Wandstärke bedeutet dies, dass die Oberfläche minimal sein sollte), da dies billiger ist. Um den Container bequem mit einem Gabelstapler aufnehmen zu können, muss seine Breite mindestens 1,5 m betragen.

Lassen Sie uns dieses Problem in einer für die Anwendung des Optimierungsalgorithmus geeigneten Form formulieren.

Entwurfsparameter: x 1 , x 2 , x 3 .

Die Zielfunktion (die minimiert werden muss) ist die Fläche der Seitenfläche des Behälters:

A=2(x 1 x 2 + x 2 x 3 + x 1 x 3), m2.

Einschränkung - Gleichheit:

Volumen \u003d x 1 x 2 x 3 \u003d 1m3.

Einschränkung - Ungleichheit:

Probleme der linearen Programmierung

Lineare Programmierung (LP) ist einer der Bereiche der mathematischen Programmierung - einer Disziplin, die extreme (Optimierungs-)Probleme untersucht und Methoden zu deren Lösung entwickelt.

Optimierungsproblem ist ein mathematisches Problem, das darin besteht, den optimalen (d. h. maximalen oder minimalen) Wert der Zielfunktion zu finden, und die Werte der Variablen müssen zu einem bestimmten Bereich zulässiger Werte (ODV) gehören.

Im Allgemeinen besteht die Formulierung eines Extremalproblems der mathematischen Programmierung darin, den größten oder kleinsten Wert der aufgerufenen Funktion zu bestimmen Zielfunktion, unter den Bedingungen (Einschränkungen) , wobei und gegebene Funktionen und gegebene Konstanten sind. Gleichzeitig bestimmen Einschränkungen in Form von Gleichheiten und Ungleichungen die Menge (Region) zulässiger Lösungen (ODS) und werden aufgerufen Design-Parameter.

Je nach Art der Funktionen und Probleme der mathematischen Programmierung werden diese in eine Reihe von Klassen eingeteilt (lineare, nichtlineare, konvexe, ganzzahlige, stochastische, dynamische Programmierung usw.).

BEIM Gesamtansicht Das LP-Problem hat folgende Form:

, (5.1)

, , (5.2)

, , (5.3)

wobei , , gegebene Konstanten sind.

Funktion (5.1) heißt Zielfunktion; Systeme (5.2), (5.3) - durch ein System von Beschränkungen; Bedingung (5.4) ist die Bedingung der Nicht-Negativität der Entwurfsparameter.

Der Satz von Designparametern, der die Nebenbedingungen (5.2), (5.3) und (5.4) erfüllt, wird aufgerufen akzeptable Lösung oder planen.

Die optimale Lösung oder optimal planen Das LP-Problem wird als zulässige Lösung bezeichnet, bei der die Zielfunktion (5.1) den optimalen (maximalen oder minimalen) Wert annimmt.

Standardaufgabe LP heißt das Problem, den maximalen (minimalen) Wert der Zielfunktion (5.1) unter der Bedingung (5.2) und (5.4) zu finden, wobei , , d.h. jene. Einschränkungen nur in Form von Ungleichungen (5.2) und alle Designparameter erfüllen die Nicht-Negativitätsbedingung, und es gibt keine Bedingungen in Form von Gleichheiten:

,

, , (5.5)

.

Kanonische (Haupt-)Aufgabe Das LP heißt das Problem, den maximalen (minimalen) Wert der Zielfunktion (5.1) unter der Bedingung (5.3) und (5.4) zu finden, wobei , , d.h. jene. Einschränkungen nur in Form von Gleichheiten (5.3) und alle Designparameter erfüllen die Nicht-Negativitätsbedingung, und es gibt keine Bedingungen in Form von Ungleichungen:

,

.

Das kanonische LP-Problem kann auch in Matrix- und Vektorform geschrieben werden.

Die Matrixform des kanonischen LP-Problems hat die folgende Form:

Vektorform des kanonischen LP-Problems.