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.

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

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

Lösung:

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.

Finden Sie die Koordinaten des Punktes H.

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:

Bei 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:

Bei 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; k 2 = 1; n = 0,2; m=0,5.

Lösung:

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 die von der vorherigen Stufe k - 1 übrig blieben. 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);

KONTROLLARBEITEN ZUR DISZIPLIN:

"METHODEN OPTIMALER LÖSUNGEN"

Option Nummer 8

1. Lösen Sie ein lineares Programmierproblem mit einer grafischen Methode. Finden Sie das Maximum und Minimum der Funktion  unter gegebenen Bedingungen:

,

.

Lösung

Es ist notwendig, den Mindestwert der Zielfunktion und den Höchstwert unter dem System der Beschränkungen zu finden:

9x1 +3x2 ≥30, (1)

X1 + x2 ≤4, (2)

x1 + x2 ≤8, (3)

Konstruieren wir den Bereich der zulässigen Lösungen, d.h. Lösen Sie das Ungleichungssystem grafisch. Dazu konstruieren wir jede Gerade und definieren die durch die Ungleichungen gegebenen Halbebenen (die Halbebenen sind mit einem Strich gekennzeichnet).

Der Schnittpunkt der Halbebenen wird die Fläche sein, deren Koordinaten der Punkte die Bedingung für die Ungleichungen des Zwangsbedingungssystems des Problems erfüllen. Lassen Sie uns die Grenzen des Bereichs des Lösungspolygons bezeichnen.

Konstruieren wir eine Gerade, die dem Wert der Funktion F = 0 entspricht: F = 2x 1 + 3x 2 = 0. Der aus den Koeffizienten der Zielfunktion zusammengesetzte Gradientenvektor gibt die Richtung der Minimierung von F(X) an. Der Anfang des Vektors ist der Punkt (0; 0), das Ende ist der Punkt (2; 3). Lassen Sie uns diese Linie parallel verschieben. Da uns die Minimallösung interessiert, verschieben wir die Gerade bis zur ersten Berührung des bezeichneten Bereichs. In der Grafik ist diese Linie durch eine gepunktete Linie gekennzeichnet.

Gerade
schneidet die Region an Punkt C. Da Punkt C als Ergebnis des Schnittpunkts der Linien (4) und (1) erhalten wird, erfüllen seine Koordinaten die Gleichungen dieser Linien:
.

Nachdem wir das Gleichungssystem gelöst haben, erhalten wir: x 1 = 3,3333, x 2 = 0.

Wo finden wir den Minimalwert der Zielfunktion: .

Betrachten Sie die objektive Funktion des Problems.

Konstruieren wir eine Gerade, die dem Wert der Funktion F = 0 entspricht: F = 2x 1 + 3x 2 = 0. Der aus den Koeffizienten der Zielfunktion zusammengesetzte Gradientenvektor gibt die Maximierungsrichtung von F(X) an. Der Anfang des Vektors ist der Punkt (0; 0), das Ende ist der Punkt (2; 3). Lassen Sie uns diese Linie parallel verschieben. Da uns die maximale Lösung interessiert, bewegen wir die Gerade bis zur letzten Berührung des bezeichneten Bereichs. In der Grafik ist diese Linie durch eine gepunktete Linie gekennzeichnet.

Gerade
schneidet die Region an Punkt B. Da Punkt B als Ergebnis des Schnittpunkts der Linien (2) und (3) erhalten wird, erfüllen seine Koordinaten die Gleichungen dieser Linien:

.

Wo finden wir den Maximalwert der Zielfunktion: .

Antworten:
und
.

2 . Lösen Sie ein lineares Programmierproblem mit der Simplex-Methode:

.

Lösung

Lassen Sie uns das direkte Problem der linearen Programmierung mit der Simplex-Methode unter Verwendung der Simplex-Tabelle lösen.

Bestimmen wir den Minimalwert der Zielfunktion
unter folgenden Bedingungen-Einschränkungen:
.

Um den ersten Referenzplan zu erstellen, reduzieren wir das Ungleichungssystem auf ein Gleichungssystem, indem wir zusätzliche Variablen einführen.

In der 1. Bedeutungsungleichung (≥) führen wir die Basisvariable ein x 3 mit Minuszeichen. In der 2. Bedeutungsungleichung (≤) führen wir die Basisvariable ein x 4 . Bei der 3. Bedeutungsungleichung (≤) führen wir die Basisvariable x 5 ein.

Lassen Sie uns künstliche Variablen einführen : in der 1. Gleichheit führen wir eine Variable ein x 6 ;

Um die Aufgabe auf ein Minimum zu reduzieren, schreiben wir die Zielfunktion wie folgt: .

Für die Verwendung von künstlichen Variablen, die in die Zielfunktion eingeführt werden, wird eine sogenannte Strafe von M auferlegt, eine sehr große positive Zahl, die normalerweise nicht angegeben wird.

Die resultierende Basis wird als künstlich bezeichnet, und die Lösungsmethode wird als künstliche Basismethode bezeichnet.

Darüber hinaus beziehen sich künstliche Variablen nicht auf den Inhalt der Aufgabe, sondern ermöglichen es Ihnen, einen Ausgangspunkt zu erstellen, und der Optimierungsprozess zwingt diese Variablen dazu, Nullwerte anzunehmen und die Zulässigkeit der optimalen Lösung sicherzustellen.

Aus den Gleichungen drücken wir künstliche Variablen aus: x 6 \u003d 4-x 1 -x 2 +x 3, die wir in die Zielfunktion einsetzen: oder.

Koeffizientenmatrix
Dieses Gleichungssystem hat die Form:
.

Lösen wir das Gleichungssystem nach den Grundvariablen: x 6 , x 4 , x 5.

Unter der Annahme, dass die freien Variablen 0 sind, erhalten wir die erste Grundlinie:

X1 = (0,0,0,2,10,4)

Eine Basislösung heißt zulässig, wenn sie nichtnegativ ist.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 4
x 5

Die aktuelle Basislinie ist nicht optimal, da positive Koeffizienten in der Indexzeile vorhanden sind. Wir wählen die Spalte, die der Variablen x 2 entspricht, als führende Spalte, da dies der größte Koeffizient ist. Berechnen Sie die Werte D ich und wähle die kleinste davon: min(4: 1 , 2: 2 , 10: 2) = 1.

Daher ist die 2. Zeile führend.

Das Auflösungselement ist gleich (2) und befindet sich am Schnittpunkt der führenden Spalte und der führenden Zeile.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 4
x 5

Wir bilden den nächsten Teil der Simplex-Tabelle. Anstelle der Variablen x 4 enthält Plan 1 die Variable x 2 .

Die Linie, die der Variablen x 2 in Plan 1 entspricht, wird erhalten, indem alle Elemente der Linie x 4 von Plan 0 durch das Freigabeelement RE = 2 dividiert werden. Anstelle des Auflösungselements erhalten wir 1. In die verbleibenden Zellen der Spalte x 2 schreiben wir Nullen.

Somit sind im neuen Plan 1 Zeile x 2 und Spalte x 2 gefüllt. Alle anderen Elemente des neuen Plans 1, einschließlich der Elemente der Indexzeile, werden durch die Rechteckregel bestimmt.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 2
x 5
		1 1/2 +1 1/2 M

Die aktuelle Basislinie ist nicht optimal, da positive Koeffizienten in der Indexzeile vorhanden sind. Wir wählen die Spalte, die der Variablen x 1 entspricht, als führende Spalte, da dies der größte Koeffizient ist. Berechnen Sie die Werte D ich nach Zeilen als Quotient der Division: und von ihnen wählen wir die kleinste: min (3: 1 1 / 2, -, 8: 2) = 2.

Daher ist die 1. Zeile führend.

Das Auflösungselement ist gleich (1 1/2) und befindet sich am Schnittpunkt der führenden Spalte und der führenden Zeile.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6		1 1 / 2
x 2
x 5
		-1 1 / 2 +1 1 / 2 M

Wir bilden den nächsten Teil der Simplex-Tabelle. Anstelle der Variablen x 6 wird die Variable x 1 in Plan 2 aufgenommen.

Wir erhalten eine neue Simplex-Tabelle:

		x 1	x 2	x 3	x 4	x 5	x 6
x 1
x 2
x 5

Keiner der Indexzeilenwerte ist positiv. Daher bestimmt diese Tabelle den optimalen Aufgabenplan.

Die endgültige Version der Simplex-Tabelle:

		x 1	x 2	x 3	x 4	x 5	x 6
x 1
x 2
x 5

Da es in der optimalen Lösung keine künstlichen Variablen gibt (sie sind gleich Null), ist diese Lösung zulässig.

Der optimale Plan kann wie folgt geschrieben werden: x 1 \u003d 2, x 2 \u003d 2:.

Antworten:
,
.

3. Das Unternehmen "Three Fat Men" befasst sich mit der Lieferung von Fleischkonserven aus drei Lagerhäusern in verschiedenen Stadtteilen an drei Geschäfte. In der Transporttabelle werden die in den Lagern verfügbaren Bestände an Konserven sowie das Bestellvolumen der Filialen und die Lieferraten (in herkömmlichen Geldeinheiten) dargestellt.

Finden Sie einen Transportplan, der die geringsten Barkosten bietet (führen Sie den ursprünglichen Transportplan mit der Methode "Nordwestecke" durch).

Lösung

Prüfen wir die notwendige und hinreichende Bedingung für die Lösbarkeit des Problems:

= 300 + 300 + 200 = 800 .

= 250 + 400 + 150 = 800.

Die Gleichgewichtsbedingung ist erfüllt. Aktien gleich Bedürfnisse. Daher ist das Transportproblemmodell geschlossen.

Geben wir die Anfangsdaten in die Verteilungstabelle ein.

Bedürfnisse

Mit der Methode der Nordwestecke konstruieren wir den ersten Grundplan des Transportproblems.

Das Ausfüllen des Plans beginnt in der oberen linken Ecke.

Das gewünschte Element ist 4. Für dieses Element beträgt der Bestand 300, der Bedarf 250. Da das Minimum 250 beträgt, ziehen wir es ab: .

			300 - 250 = 50
250 - 250 = 0

Das gewünschte Element ist 2. Für dieses Element beträgt der Bestand 50, der Bedarf 400. Da das Minimum 50 beträgt, ziehen wir es ab: .

			50 - 50 = 0
	400 - 50 = 350

Das gewünschte Element ist 5. Für dieses Element beträgt der Bestand 300, der Bedarf 350. Da das Minimum 300 beträgt, ziehen wir es ab:

			300 - 300 = 0
	350 - 300 = 50

Das gewünschte Element ist 3. Für dieses Element beträgt der Bestand 200, der Bedarf 50. Da das Minimum 50 beträgt, ziehen wir es ab:

			200 - 50 = 150
	50 - 50 = 0

Das gewünschte Element ist 6. Für dieses Element beträgt der Bestand 150, der Bedarf 150. Da das Minimum 150 beträgt, ziehen wir es ab:

			150 - 150 = 0
		150 - 150 = 0

Bedürfnisse

Finden Sie mit einer grafischen Methode das Maximum der Zielfunktion

F= 2x 1 + 3x 2 ® max

Mit Einschränkungen

Lösung mithilfe von Excel-Tabellen

Lassen Sie uns zunächst eine Lösung für das System der Ungleichungen in einer Excel-Tabelle erstellen.

Betrachten Sie die erste Ungleichung.

Konstruieren wir eine Grenzlinie aus zwei Punkten. Bezeichnen Sie die Zeile mit (L1) (oder Row1). Koordinaten X 2 rechnen wir nach den Formeln:

Wählen Sie zum Erstellen ein Streudiagramm aus

Auswahl von Daten für eine gerade Linie

Ändern Sie den Namen der Zeile:

Wählen Sie ein Diagrammlayout aus. Namen der Koordinatenachsen ändern:

Gerade (L1) auf dem Diagramm:

Die Lösung der strikten Ungleichung kann mit einem einzigen Testpunkt gefunden werden, der nicht zur Linie (L1) gehört. Verwenden Sie zum Beispiel den Punkt (0; 0)W(L1).

0+3×0< 18 или 0 < 18 .

Die Ungleichung ist wahr, daher ist die Lösung der Ungleichung (1) die Halbebene, in der sich der Testpunkt befindet (in der Abbildung unter der Linie L1).

Dann lösen wir die Ungleichung (2) .

Konstruieren wir die Grenzlinie 2 aus zwei Punkten. Bezeichne die Linie mit (L2).

Gerade Linie (L2) auf dem Diagramm:

Die Lösung der strengen Ungleichung 2 kann unter Verwendung des einzigen Testpunkts gefunden werden, der nicht zur Linie (L2) gehört. Zum Beispiel mit Hilfe des Punktes (0; 0)W(L2).

Durch Ersetzen der Koordinaten des Punktes (0; 0) erhalten wir die Ungleichung

2×0 + 0< 16 или 0 < 16 .

Die Ungleichung ist wahr, daher ist die Lösung der Ungleichung (2) die Halbebene, in der sich der Testpunkt befindet (in der Abbildung unten die Linie L2).

Dann lösen wir die Ungleichung (3) .

Konstruieren wir eine Grenzlinie aus zwei Punkten. Bezeichne die Linie mit (L3).

Gerade (L3) auf dem Diagramm:

Die Lösung der strengen Ungleichung 2 kann unter Verwendung des einzigen Testpunkts gefunden werden, der nicht zur Linie (L3) gehört. Verwenden Sie zum Beispiel den Punkt (0; 0)W(L3).

Durch Ersetzen der Koordinaten des Punktes (0; 0) erhalten wir die Ungleichung

Die Ungleichung ist wahr, daher ist die Lösung der Ungleichung (3) die Halbebene, in der sich der Testpunkt befindet (in der Abbildung unten, Linie L3).

Dann lösen wir die Ungleichung (4) .

Konstruieren wir eine Grenzlinie aus zwei Punkten. Bezeichne die Linie mit (L4).

Daten zu Excel-Tabelle hinzufügen

Gerade (L4) auf dem Diagramm:

Lösung der strengen Ungleichung 3 X 1 < 21 можно найти с помощью единственной пробной точки, не принадлежащей прямой (L4). Например, с помощью точки (0; 0)Ï(L4).

Durch Ersetzen der Koordinaten des Punktes (0; 0) erhalten wir die Ungleichung

Die Ungleichung ist wahr, daher ist die Lösung der Ungleichung (4) die Halbebene, in der sich der Testpunkt befindet (links von der Linie L4 in der Figur).

Durch Lösen zweier Ungleichungen (5) und (6)

ist das 1. Viertel, das durch die Koordinatenlinien und begrenzt wird.

Das Ungleichungssystem ist gelöst. Die Lösung für das Ungleichungssystem (1) - (6) in diesem Beispiel ist ein konvexes Polygon in der unteren linken Ecke der Figur, begrenzt durch die Linien L1, L2, L3, L4 und die Koordinatenlinien und . Sie können sicherstellen, dass das Polygon richtig gewählt wird, indem Sie einen Versuchspunkt, zum Beispiel (1; 1), in jede Ungleichung des ursprünglichen Systems einsetzen. Durch Ersetzen des Punktes (1; 1) erhalten wir, dass alle Ungleichungen, einschließlich der natürlichen Beschränkungen, wahr sind.

Betrachten Sie nun die Zielfunktion

F= 2x 1 + 3x 2 .

Lassen Sie uns Ebenenlinien für Funktionswerte erstellen F=0 und F=12(Zahlenwerte sind willkürlich gewählt). Daten zu Excel-Tabelle hinzufügen

Niveaulinien auf dem Chart:

Konstruieren wir einen Richtungsvektor (oder einen Gradienten) (2; 3). Die Vektorkoordinaten stimmen mit den Koeffizienten der Zielfunktion überein F.

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, unter dem die Funktion (1.1) ihren maximalen (minimalen) Wert erreicht, wird als optimal bezeichnet.

1.2. Simplex-Verfahren zur Lösung linearer Programmierprobleme

Die Simplex-Methode wurde 1947 von dem amerikanischen Mathematiker J. Dantzig 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 zulässiger Lösungen bildet den Bereich zulässiger 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, wird als optimal bezeichnet und 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 überprü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 zumindest nicht davon wegbewegt). 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 wird Optimierung eher als das Streben nach Perfektion verstanden, 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). Wenn es zwei Designparameter gibt, 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 eine wichtige Rolle im Optimierungsprozess, da die Wahl des effizientesten Algorithmus von ihnen 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 begrenzt 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 - das ist die Abhängigkeit zwischen Designparametern, 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 bestimmt 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 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 etc.).

BEI 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 ist das Problem, den maximalen (minimalen) Wert der Zielfunktion (5.1) unter den Bedingungen (5.2) und (5.4) zu finden, wobei , , d.h. diese. 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 den Bedingungen (5.3) und (5.4) zu finden, wobei , , d.h. diese. 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.