Lineare Optimierung, Simplex Algorithmus richtig anwenden und Kontrollrechnung durchführen

Question

Hallo, es geht um folgende Aufgabe die mit dem Simplex Algorithmus gelöst werden soll.

Ermitteln Sie mit Hilfe des Simplex–Algorithmus die optimalen Lösungen der folgenden
Standard–Maximum–Probleme:
max z = 30x₁ + 40x₂

Nebenbedingungen:

x₁ ≤ 8
x₂ ≤ 16
2x₁ + x₂ ≤ 24
Nichtnegativitätsbedingungen x₁, x₂ ≥ 0

Mein Ansatz:

Ich habe erst einmal das Tableau aufgestellt, welches bei mir folgendermaßen aussieht:

(1).  1          0        1     0     0     8     --> +(2)

(2)   0          1        0     1     0     16   --> −(3)

(3)   2          1        0     0     1     24   --> −(2)

(4)  -30     -40       0     0      0      0   --> + 40•(2)

Die rote 0 ist mein Pivotelement. Alles über und unter dem Pivotelement muss ja =0 sein und das Pivotelement selbst die 1. Ich habe das ganze dann umgeformt (s. Rechenschritte hinter jeweiligen Zeile) und komme auf:

(1).  1          1        1      1      0       24     
(2)  -2          0        0      1      -1      -8 
(3)   2          0        0      1       1       8  
(4)  50         0        0     40      0       640

Ist das bis dahin richtig? Eigentlich müsste ich doch jetzt schon fertig sein, da in der letzten Zeile alle Werte positiv sind, oder? Wie kann ich die Lösung dann entsprechend ablesen für x₁ und x₂ und mit der Proberechnung (einsetzen in die o.g. Zielfunktion) kontrollieren?

und ein schönes Wochenende

Answer 1

Die Null ist ganz sicher KEIN Pivotelement - macht sich schlecht beim Dividieren...

Der erste Schritt führt auf das Tableau

\(\small\left(\begin{array}{rrrrrr}1&0&1&0&0&8\\0&1&0&1&0&16\\2&0&0&-1&1&8\\-30&0&0&40&0&640\\\end{array}\right)  \)

und dann

[spoiler]

\(\small \left(\begin{array}{rrrrrr}0&0&1&\frac{1}{2}&-\frac{1}{2}&4\\0&1&0&1&0&16\\1&0&0&-\frac{1}{2}&\frac{1}{2}&4\\0&0&0&25&15&760\\\end{array}\right)  \)

[/spoiler]

Comments

Hallo,

wie kommst du denn darauf? Kannst du mir die Schritte bitte erklären?

Welches ist dann das entsprechende Pivotelement?

Wie kann ich das Ergebnis am Schluss mit der Kontrollrechnung kontrollieren?

---

Wie Du anhand des Tableau sehen kannst ist die Pivotspalte 2 bestimmt durch das kleinste neg. Element der Zielfunktion - die Pivotzeile 2 ergibt sich aus min

b-Vektorspalte/Pivotspalte=\(\small \left(\begin{array}{r}?\\16\\24\\\end{array}\right)\)

und Kontrolle durch grafische Lösung

https://www.geogebra.org/m/weyhrbrq

Answer 2

Zur Kontrolle
Ich habe mit der einfacheren halbgrafischen Lösung
x1 = 4, x2 = 16
max = 760 heraus

Die Aufgabe dient wohl dazu das Simplex-Verfahren
anzuwenden.

Comments

Hallo :)

Danke für deine Antwort! :) Ja, es ist das Simplex-Verfahren (hatte ich in der Aufgabenstellung geschrieben :)).

Auf das Ergebnis komme ich nach langem hin und her auch endlich. Mir fehlte die Info, dass eine 0 bei der Wahl der Pivotzeile nicht berücksichtigt wird. :D

LG und ein schönes Wochenende