Simplex Algorithmus < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:55 Fr 17.02.2012 | | Autor: | Norman |
Halli Hallo,
Ich versuche eine Aufgabe mit Hilfe der Tableau Methode des Simplex Algorithmus zu lösen. Ok, eigentlich habe ich die Aufgabe schon gelöst, möchte es aber mit einem Verfahren was hier (![[]](/images/popup.gif) PDF) beschrieben ist lösen.
Die Aufgabe:
[mm] max(x_1 [/mm] + [mm] x_2)
[/mm]
Nebenbedingung:
[mm] x_1 [/mm] + [mm] x_2 \le [/mm] 44
[mm] 2x_1 [/mm] + [mm] x_2 \le [/mm] 64
[mm] 9000x_1 [/mm] + [mm] 5000x_2 \le [/mm] 300000
Ich weis was herauskommen muss aber wenn ich die 2te Tabelle aufstelle. Ist bei mir schon die Abbruchbedingung erreicht und das Ergebnis ist dann nicht optimal.
Schritt (1):
Ich habe neue Variablen eingeführt um die Ungleichungen als Gleichungen schreiben zu können.
[mm] x_1 [/mm] + [mm] x_2 [/mm] + [mm] x_3 [/mm] = 44
[mm] 2x_1 [/mm] + [mm] x_2 +x_4 [/mm] = 64
[mm] 9000x_1 [/mm] + [mm] 5000x_2 [/mm] + [mm] x_5 [/mm] = 300000
Schritt (2)
Die Erste Tabelle sieht dann wie folgt aus. (Nach dem in der PDF beschriebenen Schema)
Tabelle 1
2 ist hier das Pivot Element da die Erste Spalte in der Kopfzeile negativ ist und ich nach Berechnung des Quotienten am niedrigsten ist. (Ergebnisspalte / sich selbst also 64 / 2 = 32)
Schritt(3) : Neue Tabelle aufstellen. Da hakt es jetzt gleich!
Tabelle 2
Ich habe jetzt nur die Werte eingetragen von denen ich weiß das sie Stimmen + die 5000 die Falsch sein muss. Da ich jetzt in der ersten Zeile nur positive Werte habe. Damit ist der Alg terminiert und das darf er ja nicht.
[mm] x_1 [/mm] und [mm] x_4 [/mm] habe ich vertauscht und die Spalte wo das Pivotelement war berechnet mit (-Element_alt / Pivot_alt).
Das Pivot_neu = 1 / Pivot_alt.
Die Zeile wo das Pivot Element war ist Element_neu = Element_alt / Pivot_alt
Ist der in der PDF angegebene Weg falsch oder übersehe ich irgend etwas ? Ich habe schon zig mal neu angefangen aber komme immer wieder auf das Gleiche.
Die Lösung wäre [mm] x_1 [/mm] = 20 und [mm] x_2 [/mm] = 24
Dateianhänge:
Anhang Nr. 1 (Typ: jpg) [nicht öffentlich]
Anhang Nr. 2 (Typ: jpg) [nicht öffentlich]
|
|
| |
|
> Halli Hallo,
>
> Ich versuche eine Aufgabe mit Hilfe der Tableau Methode des
> Simplex Algorithmus zu lösen. Ok, eigentlich habe ich die
> Aufgabe schon gelöst, möchte es aber mit einem Verfahren
> was hier (PDF)
> beschrieben ist lösen.
>
> Die Aufgabe:
>
> [mm]max(x_1[/mm] + [mm]x_2)[/mm]
Wohl eher nach deinem Tableau
[mm]30000x_1+20000x_2\rightarrow\max [/mm]
u.d.N. [mm]\left( \begin{array}{ccccc}1&1&1&0&0 \\
2&1&0&1&0 \\
9000&5000&0&0&1 \\
\end{array}\right)\vec{x}=\left( \begin{array}{ccc}44 \\
64 \\
30000\end{array}\right)[/mm]
>
> Nebenbedingung:
>
> [mm]x_1[/mm] + [mm]x_2 \le[/mm] 44
> [mm]2x_1[/mm] + [mm]x_2 \le[/mm] 64
> [mm]9000x_1[/mm] + [mm]5000x_2 \le[/mm] 300000
>
>
> Ich weis was herauskommen muss aber wenn ich die 2te
> Tabelle aufstelle. Ist bei mir schon die Abbruchbedingung
> erreicht und das Ergebnis ist dann nicht optimal.
>
> Schritt (1):
>
> Ich habe neue Variablen eingeführt um die Ungleichungen
> als Gleichungen schreiben zu können.
>
> [mm]x_1[/mm] + [mm]x_2[/mm] + [mm]x_3[/mm] = 44
> [mm]2x_1[/mm] + [mm]x_2 +x_4[/mm] = 64
> [mm]9000x_1[/mm] + [mm]5000x_2[/mm] + [mm]x_5[/mm] = 300000
>
> Schritt (2)
>
> Die Erste Tabelle sieht dann wie folgt aus. (Nach dem in
> der PDF beschriebenen Schema)
>
Ich habe nicht ganz dein Schema (nur anders formatiert) und erhalte
[mm]\begin{tabular}{|c||c|c|c|c|c||c|c|} \hline &x_1&x_2&y_1&y_2&y_3&b_i &q_i \\
\hline y_1 & 1 & 1 & 1 & 0 & 0 & 44 & \\
\hline y_2 & 2 & 1 & 0 & 1 & 0 & 64 & \\
\hline y_3 & 9000 & 5000 & 0 & 0 & 1 & 30000 & \\
\hline F & -30000 & -20000 & 0 & 0 & 0 & 0 & \\
\hline \end{tabular}[/mm]
> Tabelle 1
>
> 2 ist hier das Pivot Element da die Erste Spalte in der
> Kopfzeile negativ ist und ich nach Berechnung des
> Quotienten am niedrigsten ist. (Ergebnisspalte / sich
> selbst also 64 / 2 = 32)
Nein [mm]\frac{30000}{9000}\approx 3.3[/mm] Also ist das Pivotelement in der 1. Spalte und 3. Zeilen.
[mm]q_{i}=\frac{b_i}{a_{it}}=\frac{b_i}{a_{i1}}[/mm]
[mm]q_{1}=\frac{b_1}{a_{11}}=\frac{44}{1}=44[/mm]
[mm]q_{2}=\frac{b_2}{a_{21}}=\frac{64}{2}=32[/mm]
[mm]q_{3}=\frac{b_3}{a_{31}}=\frac{30000}{9000}=3.33[/mm]
Und tragen diese in das Tableau ein
[mm]\begin{tabular}{|c||c|c|c|c|c||c|c|} \hline &$x_1$&$x_2$&$y_1$&$y_2$&$y_3$&$b_i$ &$q_i$ \\ \hline $y_1$ & 1 & 1 & 1 & 0 & 0 & 44 & 44 \\ \hline $y_2$ & 2 & 1 & 0 & 1 & 0 & 64 & 32 \\ \hline $y_3$ & 9000 & 5000 & 0 & 0 & 1 & 30000 & 3.33 \\ \hline F & -30000 & -20000 & 0 & 0 & 0 & 0 & \\ \hline \end{tabular} [/mm]
Wir bestimmen nun das folgende Minimum
[mm]q_s=\min_{i} \{q_{i}\quad | \quad a_{it}>0\}=3[/mm]
Umformungen
Nun wenden wir normal die Umformungen an.
Wir tauschen die Nichtbasisvariable [mm]$y_3$[/mm] (Zeile 3) gegen die Basisvariable [mm]$x_1$[/mm](Spalte 1)
[mm]\begin{tabular}{|c||c|c|c|c|c||c|c|} \hline &$x_1$&$x_2$&$y_1$&$y_2$&$x_1$&$b_i$ &$q_i$ \\ \hline $y_1$ & 1 & 1 & 1 & 0 & 0 & 44 & 44 \\ \hline $y_2$ & 2 & 1 & 0 & 1 & 0 & 64 & 32 \\ \hline $x_1$ & 9000 & 5000 & 0 & 0 & 1 & 30000 & 3.33 \\ \hline F & -30000 & -20000 & 0 & 0 & 0 & 0 & \\ \hline \end{tabular} [/mm]
Normieren die Pivotzeile 3 durch Multiplikation mit 0, sodass das Pivotelement 1 ist, d.h.
[mm]9000\mapsto 1[/mm]
[mm]\begin{tabular}{|c||c|c|c|c|c||c|c|} \hline &$x_1$&$x_2$&$y_1$&$y_2$&$x_1$&$b_i$ &$q_i$ \\ \hline $y_1$ & 1 & 1 & 1 & 0 & 0 & 44 & \\ \hline $y_2$ & 2 & 1 & 0 & 1 & 0 & 64 & \\ \hline $x_1$ & 1 & 0.56 & 0 & 0 & 0 & 3.33 & \\ \hline F & -30000 & -20000 & 0 & 0 & 0 & 0 & \\ \hline \end{tabular} [/mm]
Alle Einträge in der Pivotspalte sollen nun Null werden (außer in Pivotzeile).
Wir betrachten Zeile 1 und addieren zu ihr das folgende Vielfache von der Pivotzeile
[mm]- \frac{1}{1}=-1[/mm]
Das neue Tableau sieht so aus
[mm]\begin{tabular}{|c||c|c|c|c|c||c|c|} \hline &$x_1$&$x_2$&$y_1$&$y_2$&$x_1$&$b_i$ &$q_i$ \\ \hline $y_1$ & 0 & 0.44 & 1 & 0 & 0 & 40.67 & \\ \hline $y_2$ & 2 & 1 & 0 & 1 & 0 & 64 & \\ \hline $x_1$ & 1 & 0.56 & 0 & 0 & 0 & 3.33 & \\ \hline F & -30000 & -20000 & 0 & 0 & 0 & 0 & \\ \hline \end{tabular} [/mm]
Wir betrachten Zeile 2 und addieren zu ihr das folgende Vielfache von der Pivotzeile
[mm]- \frac{2}{1}=-2[/mm]
Das neue Tableau sieht so aus
[mm]\begin{tabular}{|c||c|c|c|c|c||c|c|} \hline &$x_1$&$x_2$&$y_1$&$y_2$&$x_1$&$b_i$ &$q_i$ \\ \hline $y_1$ & 0 & 0.44 & 1 & 0 & 0 & 40.67 & \\ \hline $y_2$ & 0 & -0.12 & 0 & 1 & 0 & 57.34 & \\ \hline $x_1$ & 1 & 0.56 & 0 & 0 & 0 & 3.33 & \\ \hline F & -30000 & -20000 & 0 & 0 & 0 & 0 & \\ \hline \end{tabular} [/mm]
Die Zeile 3 ist Privotzeile und bleibt unverändert, da sie schon normiert wurde.
Jetzt noch den gleichen Schritt auch mit der Zeile der F-Werte. Wir addieren zu dieser das folgende Vielfache der Pivotzeile
[mm]- \frac{-30000}{1}=30000[/mm]
Das neue Tableau sieht so aus
[mm]\begin{tabular}{|c||c|c|c|c|c||c|c|} \hline &$x_1$&$x_2$&$y_1$&$y_2$&$x_1$&$b_i$ &$q_i$ \\ \hline $y_1$ & 0 & 0.44 & 1 & 0 & 0 & 40.67 & \\ \hline $y_2$ & 0 & -0.12 & 0 & 1 & 0 & 57.34 & \\ \hline $x_1$ & 1 & 0.56 & 0 & 0 & 0 & 3.33 & \\ \hline F & 0 & -3200 & 0 & 0 & 0 & 99900 & \\ \hline \end{tabular} [/mm]
>
> Die Lösung wäre [mm]x_1[/mm] = 20 und [mm]x_2[/mm] = 24
Komm ich leider nicht drauf.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:43 Fr 17.02.2012 | | Autor: | Norman |
Oops da ist mir ein Fehler unterlaufen. Es soll natürlich 300.000 und nicht 30.00 sein. Damit kommt man dann wieder auf 2.
Die Ergebnisse müssten aber 100 pro korrekt sein, da sie kontrolliert wurde und das rauskam. Mit rumprobieren wäre man auch drauf gekommen.
Wie gesagt ich verwende das in der PDF angegebene Schmema. Das ist auch so ähnlich auf Wikipedia zu finden.
Mein Problem besteht halt im Aufbau der 2ten Tabelle. Ich möchte es halt nach dem angegeben Schema machen da ich finde das es mir auch deutlich schreib und gerade Zeit erspart und ich das auch so mal durch probieren soll.
Wenn du dir die PDF anschaust. Kannst du vielleicht durch einen Blick sehen ob das Verfahren dort falsch ist ?
Sorry nochmal für den falschen Zahlenwert.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:52 Fr 17.02.2012 | | Autor: | wieschoo |
Dann kann ich das unterschreiben ![[daumenhoch]](/images/smileys/daumenhoch.gif "[daumenhoch]")
Schau mal:
http://werkzeuge.wieschoo.com/simplex.php
mit Eingaben:
Zielfunktionsparameter:30000 20000
Matrix:
1 1 1 0 0 44
2 1 0 1 0 64
9000 5000 0 0 1 300000
|
|
|
|
