www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Englisch
  Status Grammatik
  Status Lektüre
  Status Korrekturlesen
  Status Übersetzung
  Status Sonstiges (Englisch)

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Uni-Sonstiges" - Simplex Algorithmus
Simplex Algorithmus < Sonstiges < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Sonstiges"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Simplex Algorithmus: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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 ([]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]
        
Bezug
Simplex Algorithmus: Antwort
Status: (Antwort) fertig Status 
Datum: 15:16 Fr 17.02.2012
Autor: wieschoo


> 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.

Bezug
                
Bezug
Simplex Algorithmus: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.  

Bezug
                        
Bezug
Simplex Algorithmus: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 15:52 Fr 17.02.2012
Autor: wieschoo

Dann kann ich das unterschreiben [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


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Sonstiges"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.englischraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]