PRIVATE NORTHEAST UNIVERSITY

GRAN MARISCAL DE AYACUCHO

FACULTÄT FÜR INGENIEURWESEN

INGENIEURWESEN UND NATURRESSOURCEN SCHULE

NUCLEO MATURIN

EINFACHE MATRIXMETHODE

Professor Abiturient

Maturin, November 2020

 INDEX

1. SIMPLEX-MATRIXMETHODE …………………………………....Seite 1

1.1 Schritte zur Lösung des Problems ....................................................Seite 1

1.2 Einschränkungen………………………………………………………………..Seite 2
1.3 Tabellenformat mit der Matrix-Simplex-Methode…………………...Seite 3
1.4 Methoden, die sich aus der Matrize ableiten....................Seite 4-

8
 1. SIMPLEX-MATRIX-METHODEN

Für Probleme mit einer großen Anzahl von Variablen und Einschränkungen ist es kostspielig.
Finden Sie die Lösung manuell mit der algebraischen Methode oder der Simplexmethode.
es ist notwendig, ein Computerprogramm zu erstellen, das den Lösungsprozess beschleunigt, um
Hallo, das Problem wird matrixweise gelöst, da der Computer
effizient die Matrizenanordnungen. Diese Methode erfordert eine geringere Menge von
Berechnungen, da nur Berechnungen mit den Vektoren derjenigen Variablen durchgeführt werden, die nicht-

Grundlagen und speichert in den Speicher, was die grundlegenden Variablen betrifft, sowie alle Werte
Initialen.

1.1 SCHRITTE ZUR LÖSUNG DES PROBLEMS MIT DER METHODE

MATRIZIAL
Zuerst

Ausgehend von einem Problem der linearen Programmierung, das sich in der Standardform befindet, wird
Bestimmen Sie die Matrizen

A, b, B, Cj, CBy XB

Wo:

A ist die Koeffizientenmatrix der Variablen in den Beschränkungen, b ist die Seite
Recht der Einschränkungen (Begrenzungen)
B ist die Matrix, die die grundlegende zulässige Anfangslösung bereitstellt und besteht aus
durch die Spalten der Basisvariablen, d.h. diejenigen, die in der Lösung sind.
Cjsind die Koeffizienten der Variablen in der Zielfunktion
CBsind die Koeffizienten der Basisvariablen in der Zielfunktion.
XBEs sind die Werte der Grundvariablen, die die Lösung des Problems liefern.

Zweitens beginnen Sie mit der Iteration 1

S1
-Die grundlegenden Variablen X S 2 B=
definieren
S3

1
 -Bestimmen Sie die Variablen, die eingehen: in einem Minimierungsproblem ist gegeben durch

Der obere negative Wert, um ihn zu erhalten, muss die Ziel-funktion in

negativ erhält man den obersten negativen Wert. Je nachdem, welcher es ist,
Wählen Sie die Pivot-Spalte. Zum Beispiel.
Wenn die Zielfunktion Z = X ist1+4X2+2X3sein negativer Wert wäre -C= -1-4-2
Der höchste negative Wert ist -4, was X entspricht.2, indem ich diese Spalte nehme
als Pivot.
In einem Beispiel der Maximierung ist alles das Gegenteil, man nimmt den positiven Wert.
überlegen. Im obigen Fall wäre es 4. Und dann wird der gleiche Prozess fortgesetzt.
-Bestimmen Sie die Variablen, die herausfallen, indem Sie die Spalte b durch die
Pivot-Spalte, stammt aus jener Funktion, wo:

Wo r die Spalte der Variable entspricht, die in die Lösung eingeht

Drittens

Die Spalte der Variablen, die in die Lösung eingeht, muss die Spalte der
Identitätsmatrix. In der Matrix B die Spalte der Variable, die Min = X [Link]/Yir
Verlasse die Lösungsbasis und ersetze sie durch die Spalte der Variablen r.

Viertel

Zurück zu Schritt 2, bis das Optimierungskriterium erfüllt ist, berücksichtigt in

der Schritt 4.

1.2 Einschränkungen

Wie bei jedem Problem der linearen Programmierung werden die Einschränkungen durch die Aufgabe vorgegeben.

aber mit dieser Methode werden uns die Einschränkungen die Basisvariablen definieren, die...
in der Lösung der Übung verwenden. Diejenigen, die sind

A, b, B, Cj, CBy XB

Wo:

2
 A ist die Matrix der Koeffizienten der Variablen in den Einschränkungen, b ist die Seite
Recht der Einschränkungen (Beschränkungen)

B ist die Matrix, die die Grundlegende Machbare Anfangslösung liefert und besteht aus
durch die Spalten der Basisvariablen, d.h. derjenigen, die in Lösung sind.

CjEs sind die Koeffizienten der Variablen in der Ziel-Funktion.

CBsind die Koeffizienten der Basisvariablen in der Zielfunktion.

XBdas sind die Werte der grundlegenden Variablen, die die Lösung des Problems geben

1.3 Tabellenformat für die Matrix-Simplex-Methode

Das Tabellenformat variiert je nach Iteration, die gelöst wird, auf eine Weise
allgemein wäre dies das Format für die Iteration 1:

Koeffizient von
Basisvariableniteration Rechte Seite
z ursprüngliche Variablen Variablen Slacks
z 1 ( -c ) 0 0

1
XB 0 A Ich b

Für die Iterationen, die nicht die 1 sind, sondern ab der 2, verwenden Sie das folgende Format.
für die Tabelle:

3
 Koeffizient von
Basisvariable Iteration Rechte Seite
z originale Variablen Variablen Slacks
z 1 ( CBB^-1 A - C ) CB B^-1 CB B^-1 b

Jeder
XB 0 B^-1 A B^-1 B^-1 b

Zum Beispiel für eine Tabelle mit folgendem Ziel- und Beschränkungsfunktion:

Z = X1+4X2+2X3

Beschränkungen

2X1+X2< 20
2X1+X3< 15
X1+4X2+2X3<40

Wir hätten die folgende Tabelle in der Iteration 1

X1 X2 X3 S1 S2 S3 b
A 2 2 0 1 0 0 20
1 0 3 0 1 0 15
1 eins 2 0 0 1 40

In Bezug auf die nächsten Iterationen hätten wir folgendes Ergebnis, nachdem wir die
entsprechende Berechnungen.

X1 X2 X3 S1 S2 S3 B
Ein 1 1 0 1/2 0 0 10
1 0 3 0 1 0 15
0 0 2 -1/2 0 1 30

1.4 Methoden, die sich aus der Matriz ableiten

Überarbeitetes Simplex-Verfahren

4
Es basiert auf den gleichen Prinzipien wie das Simplexverfahren, aber in jeder Iteration wird nicht alles berechnet.

die Tabelle, und die Informationen, die benötigt werden, um von einer grundlegenden machbaren Lösung zu einer anderen überzugehen

wird direkt aus den ursprünglichen Gleichungen abgeleitet.

Die überarbeitete Simplexmethode behält die gleichen Eigenschaften wie die Simplexmethode bei:

1) Die Entscheidungsvariablen müssen größer als null sein.

2) Die Einschränkungen müssen die Form <= haben.

Der Unterschied zwischen der normalen Simplexmethode und der überarbeiteten besteht darin, dass die Mehrheit der

Zahlen, die in der Tabelle der normalen Methode erscheinen, werden in der Tat nicht verwendet in den

Iterationen, weshalb im überarbeiteten Verfahren nur die notwendigen Werte berechnet werden.
die optimale Lösung durch Matrizen finden.

Dieser Ansatz erfordert jedoch viele Matrixoperationen und hört auf zu sein
so strukturiert wie die Simplexmethode, weshalb es sehr leicht ist, sich währenddessen zu verwirren

die Iterationen

Bevor man die Methode anwendet, ist es notwendig, das aufgestellte Modell zu seinen

Standardmatrixform:

max z=Cx
Ax=b
x>=0

Wo:

C ist ein Vektor mit n Zeilen, dessen Elemente alle Werte der Funktion sind.
Ziel.
x, das ein Vektor mit n Spalten ist, dessen Werte alle Variablen von x sind, die
erscheinen in der Zielsetzung
A ist eine Matrix, die alle Koeffizienten repräsentiert, die sich auf der Seite befinden
links von den Gleichungen, einschließlich der Schlupfvariablen.

5
 b ist ein Vektor, der alle Entsprechungen der Gleichungen auf der Seite hat
Links, weshalb die Anzahl der Spalten von A und gleich ist

Die Schritte zur Findung der optimalen Lösung sind die gleichen wie beim Simplexverfahren. aber
Jetzt werden verschiedene Formeln verwendet:

1) Wir beginnen damit, die Anfangslösung und die Vektoren der Matrizen zu bestimmen:

Wo B eine Matrix ist, die die entsprechenden Koeffizienten der Variablen enthält
von Entscheidung in den Einschränkungen

2) Wir berechnen die Eingangsvariable

Mit dem, was die Reihe Zj-Cj wäre, wenden wir jedoch diese Formel an:

Zj-Ch=(Cb)(B^-1)(aj)-Cj
Wo

Cb sind die Werte der nicht grundlegenden Variablen in der Zielfunktion

aj ist eine Matrix, die den Werten in den Einschränkungen entspricht.
die den nicht Grundlagenvariablen entsprechen
Cj sind die Werte der nicht grundlegenden Variablen in der Zielfunktion

Es wird dasselbe Kriterium wie bei der Simplexmethode verwendet: Wir wählen den kleinsten Wert, wenn

Wir müssen die Funktion maximieren oder die größte, wenn wir minimieren müssen.

3) Der neue Wert der Basisvariablen wird berechnet:

Um die Ausgangsvariable zu berechnen, verwenden wir die folgende Formel:

Yi=(B^-1)(ai)
Wo

6
 ai ist ein Vektor, der den Werten der Einschränkungen der Variablen entspricht.
Eingang

Dann muss das gleiche Kriterium verwendet werden, um die Ausgabeveriable zu wählen wie bei e.
Das Simplexverfahren:

Wo Xb der Vektor mit den aktuellen Lösungen der Gleichungen ist

4) Schließlich muss der neue Wert der Basisvariablen berechnet werden.

Dafür muss die Matrix B geändert werden, da sich der Vektor der Basisvariablen geändert hat, was dazu
es gibt viel zu ändern an den Elementen der Matrix B, damit sie den Werten entsprechen
die Einschränkungen in ihrer entsprechenden Basisvariablen.

Wenn ich die Matrix B ändere, muss ich die Matrix B^-1 ändern.

Wir müssen den neuen Wert von Xb mit der folgenden Formel berechnen:

Xb=B^-1(b)
Wo b der Wert sein muss, den der Vektor Xb vorher hatte.

Es wird zu Schritt 2 zurückgekehrt, bis keine Eingangsvariable mehr vorhanden ist.

Auf diese Weise werden die Lösungen dargestellt.

In der ersten Iteration

In den anderen Iterationen

7
8