Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Wow! Simplex Algorithmus
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> Wow! Simplex Algorithmus
 
Autor Nachricht
faculty
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 10.06.2005
Beiträge: 363
Wohnort: Ingolstadt

BeitragVerfasst am: 30 Nov 2008 - 16:20:32    Titel: Wow! Simplex Algorithmus

Hallo Community!

Ich weiss nicht, inwiefern das folgende Problem für euch nun trivial ist oder nicht. Ich bin am verzweifeln...

Der folgende Link ist das PDF-Dokument für meine 6. Vorlesung (am Montag) zur Mathematik für Wirtschaftswissenschaftler.

Es geht um den Simplex-Algorithmus. Es werden 2 Beispiele abgehandelt.

Das erste Bsp. ist auf den ersten 11 Seiten. Mich interessiert das zweite Beispiel ab Seite 12!

http://www.ifam.uni-hannover.de/~leydecke/Lehre/WiWi/ws0809/WiWi_V6.pdf

Ich rechne seit heute morgen daran rum und es will einfach nicht in meinen Kopf reingehen WARUM (also durch welche Rechenschritte) sich jeweils die Zeile der ZIELFUNKTION (2. Zeile) (also die nach der Kopfzeile der Variablen) verändert?!

Ich weiss, dass ich jeweils Pivotschritte ausführen muss, um in den jeweiligen Spalten Einheitsvektoren zu erzeugen bzw. die jeweilige Variable zur Basisvariablen zu machen.

Aber es geht einfach nicht in meinen Kopf was die zweite Zeile beeinflusst. Warum und durch was verändert sich die Zielfunktionszeile von Schritt zu Schritt?
faculty
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 10.06.2005
Beiträge: 363
Wohnort: Ingolstadt

BeitragVerfasst am: 30 Nov 2008 - 16:39:57    Titel:

vllt. sollte ich noch anmerken, dass das Stoff des 1. Semesters ist Smile
faculty
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 10.06.2005
Beiträge: 363
Wohnort: Ingolstadt

BeitragVerfasst am: 30 Nov 2008 - 17:34:03    Titel:

Darf ich das so interpretieren, dass das selbst für euch zu schwer ist?

Oder ist es zu einfach?

Oder zu aufwendig, dass anzugucken?

Sagt mir, was ich noch für Infos liefern soll Smile

Ich verzweifle an dem Mist!
cyrix42
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 14.08.2006
Beiträge: 24256

BeitragVerfasst am: 30 Nov 2008 - 17:37:55    Titel:

Ich habe lineare Optimierung nie leiden können... Wink

Die entsprechende Schei-Klausur hab ich mit 3,7 bestanden. *g* (Mehr Bock als mich am Abend vorher darauf vorzubereiten hatte ich nicht. Das Prinzip ist mir aber schon klar: Laufe von einer Ecke des Polyeders zur nächstbesseren, bis es keine bessere Ecke mehr gibt.)


Cyrix
BarneyG.
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 16.11.2008
Beiträge: 668

BeitragVerfasst am: 30 Nov 2008 - 18:16:20    Titel:

Zitat:
Ich habe lineare Optimierung nie leiden können...


Na sowas! Und dabei ist doch die lineare Optimierung wenigstens ein Teilgebiet der BWL wo mal zur Abwechslung die Mathematik einigermassen stringent eingesetzt wird. Ansonsten neigen die Wirtschaftler dazu z.B. Funktionen einfach zu differenzieren, ohne sich auch nur einen Deut um die Differenzierbarkeit, geschweige den Stetigkeit zu kümmern ... Very Happy

Also: das Ganze ist im Skript doch recht gut beschrieben.

Zunächst mal suchst du in der ersten Zeile den kleinsten Wert:

−2 −1 0 0 0

Das ist die -2, also ist die Spalte j0 = 1

Dann schaust du nach dem kleinsten Quotienten gebildet aus den Elementen der Spalte j0 und der Ergebnisspalte (ganz rechts).

1/5 -1/0 6/21

Die Division durch 0 ist zwar verboten, aber das wird in der BWL nicht ganz so genau genommen. Da kommt halt "unendlich" heraus. Der kleinste Quotient findet sich also in der 3. Zeile, d.h. i0 = 3.

Dann wird diese Zeile durch den Wert 6 dividiert (Wert von Spalte j0, Zeile i0).

Danach werden die übrigen Werte der Spalte j0 durch Subtraktion von entsprechenden Vielfachen der Zeile i0 auf Null gebracht.

Gibt es nun in der ersten Zeile noch negative Werte, wird das ganze fortgesetzt. Ansonsten hat man das Optimum gefunden.
faculty
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 10.06.2005
Beiträge: 363
Wohnort: Ingolstadt

BeitragVerfasst am: 30 Nov 2008 - 18:42:18    Titel:

hi erstmal vielen dank für die antwort,

deine beschriebenen schritte kann ich alle nachvollziehen und ehrlich gesagt waren die mir auch bekannt. Aber die gesamte Pivotisierung, d.h. die Schritte die man in der eigentlichen Koeffizientenmatrix anwendet, sind doch alle nicht auf die Zeile mir der Zielfunktion bezogen, ODER????

Ich weiss einfach nicht, WANN und WARUM bzw. WODURCH sich die Werte der Zielfunktionszeile ändern.

danke
BarneyG.
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 16.11.2008
Beiträge: 668

BeitragVerfasst am: 30 Nov 2008 - 20:32:10    Titel:

Dann ist dein Problem also nicht der Algorithmus selbst, sondern die Interpretation des Algorithmus.

Im ersten Tableau siehst du doch die Zielfunktion und die Restriktionen. Koeffizienten in der ersten Zeile mit dem Wert 0 tragen nichts zum Wert der Zielfunktion bei. Das sind die Schlupfvariablen x3, x4 und x5. Diese Variablen dienen nur dazu, die Restriktionen einzuhalten.

Allein die Variablen x1 und x2 sind relevant für den Wert der Zielfunktion.

Man beginnt mit einer Lösung (0, 0, 5, 0, 21) also einem Vektor, der nur Schlupfvariablen gesetzt hat. Der Wert der Zielfunktion ist demgemäß 0. Und dieser Wert steht in der rechten oberen Ecke.

Nun wollen wir diesen Vektor abändern, d.h. eine der Variablen x1 oder x2 gegen eine der Schlupfvariablen austauschen. Wir wollen natürlich die Variable wählen, die den größten Beitrag zur Zielfunktion liefert. Das ist die Variable mit dem kleinsten Wert in Zeile 1. In unserem Fall also die Variable x1 (entspricht dem Wert -2).

Wenn wir den Wert für x1 von 0 auf einen positiven Wert erhöhen, müssen wir natürlich gleichzeitig die Werte der Schlupfvariablen x3, x4 und x5 verringern, damit die Restriktionen erhalten bleiben. Das geht so lange gut, bis eine dieser Variablen 0 wird! Denn negativ werden dürfen diese Variablen nicht. Welche der Variablen wird nun zuerst 0? Das erkennen wir an den Quotienten. In der dritten Zeile wird die Schlupfvariable x5 als erste 0. Und zwar dann, wenn die Variable x1 den Wert 7/2 angenommen hat. (Denn 6 * 7/2 = 21).

Wir haben also die Variablen x1 = 0 und x5 = 21 ausgetauscht gegen x1 = 7/2 und x5 = 0. Die Zielfunktion wächst dabei auf den Wert 2 * 7/2 + 0 * 1 = 7 an.

Dies verbirgt sich hinter der Umformung des Tableaus im ersten Schritt. In der rechten oberen Ecke siehst du insbesondere den neuen Wert der Zielfunktion.

Danach suchen wir nach der nächsten Variablen, die unsere Zielfunktion noch erhöhen kann. Das ist die Variable x2. Wenn diese Variable erhöht wird, dann suchen wir wieder die erste Schlupfvariable, die Null wird, (das ist x3) und tauschen diese gegen x1 aus. usw. usw.

Wenn keine Variable mehr einen Beitrag zur Erhöhung der Zielfunktion liefern kann, dann ist das Verfahren beendet.

Vielleicht schaust du dir das Verfahren in diesem Licht noch einmal schrittweise an und versuchst zu verstehen, wie der Algorithmus funktioniert.
faculty
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 10.06.2005
Beiträge: 363
Wohnort: Ingolstadt

BeitragVerfasst am: 01 Dez 2008 - 06:35:15    Titel:

hi barney

nochmal vielen dank für deine Hilfe ... ich habe mir deinen Kommentar gerade mal ausgedruckt und werde heute versuchen, dass noch mal 100%ig nachzuvollziehen!

wenn's nicht klappt meld ich mich wieder Wink
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> Wow! Simplex Algorithmus
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum