Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Simplex
Hi,
ich habe ein paar Fragen zum Simplex-Algorithmus und hoffe, jemand kann die mir beantworten.
- Wie bestimme ich die anfängliche Basis? Kann ich die beliebig wählen und nur prüfen, dass meine Bedingung erfüllt ist? Müssen in der Basis B gleich viele Elemente sein wie in N?
- PRICING: Wie bestimme ich, welche Variable in die Basis eintritt?
- UPDATE: Ich berechne:
x_B = x_B - y*w
x_j = y y soll in diesen beiden Berechnungen gamma sein
B_i = j
Ist das richtig? Ich habe mir das aus den Übungslösungen zusammengereimt, bin aber nicht sicher, ob das stimmt.
MfG
Vielleicht kann dir ja jemand im Mathe 3 Subforum helfen 
Oh gott, ja, das hab ich auch gerade gemerkt… Tut mir leid… Das erklärt auch warum meine Suche keine Ergebnisse hervorgebracht hat.
1 „Gefällt mir“
zu 1. Basis kann nur geraten werden und dann überprüft werden
zu 2. im Schritt vorher hast du den Vektor z berechnet. suche dir aus z einen eintrag aus der < 0. die stelle an der der eintrag steht ist die spalte, die aus N ausgewählt wird. also wenn z (1,-1) ist wählt man die 2. spalte aus N aus
zu 3. ersten beiden punkte sind okay was der dritte sein soll verstehe ich grad nicht 
Die gewählten Basisvektoren müssen linear unabhängig sein. Du kannst zwar raten, aber nachdem du zur Bestimmung der ersten Basislösung (x_B = (A_B)^-1 * b) gleich die Matrix mit den Basisvektoren A_B invertieren musst, empfiehlt sich (besonders wenn man in der Klausur nur einen Schritt des Algorithmus ausführen soll) eine leicht invertierbare Matrix zu wählen.
Beim Einfügen der Schlupfvariablen entsteht im hinteren Teil der Matrix A, die ja alle Nebenbedingungen enthält, ja eine Einheitsmatrix. Die hinteren Spalten werden wahrscheinlich nicht direkt zur optimalen Lösung führen, lassen sich aber im ersten Schritt schnell invertieren.
Genau. In den Übungsaufgaben bin ich immer ganz gut damit gefahren, die Spalte mit dem kleinsten Wert zu nehmen.
Sieht richtig aus.
Im Forum der Mathe C3-Gruppe auf StudOn hat Herr Schewe die Overhead-Folie mit dem Algorithmus hochgeladen.
Servus, hätte auch mal ne Frage.
Wie sieht das aus wenn ein Startpunkt vorgegeben ist? Das versteh ich noch nicht so ganz. Wie berechnet man da die Basislösung? Das kam bspw. in der H20 dran. Da wird in der Lösung gesagt jeah jetzt haben wir x = (120; 20; 0; 50; 0; 20) dank unsrem Startpunkt und B = (1; 2 ;4 ;5). Dann ist unser Xb = (120, 20, 50, 20). Wieso wird hier nichts mit A^-1*b berechnet? Stehe etwas auf dem Schlauch.
Greetz.
Ich fang mal da an, wo das LP schon in Standardform gebracht wurde.
Also Startpunkt ist (120, 20) = (x_1, x_2). Du willst aber alle 6 x_i berechnen und die bekommst du, über die Bedingungen, z.B. x_1 + x_3 = 120 → x_3 = 0, darum ist an der 2. Stelle von x = (120; 20; 0; 50; 0; 20) auch eine 0. Das machst du mit allen anderen und bekommst somit das x
B heißt nicht umsonst BASIS, d.h. ein lin. unabhängiges Erzeugendensystem. Deine Matrix A besteht aus 6 Vektoren, da du 4 lin. unab. Vektoren brauchst, wurde hier B = (1; 2 ;4 ;5) gewählt, möglich wäre auch B=(3,4,5,6) und für die restlichen Schritte: Ich hab mal auf H20 aufgebaut nochmal Simplex zusammengefasst, schau mal, obs dir hilft:
ist weiter unten.
und wieso nichts mit a^{-1}b berechnet wird: FAULHEIT 
Warum 4, bzw. woher weiss ich das?
1 „Gefällt mir“
Weil das b 4 Dimensionen hat (und das kommt von den 4 Gleichungen als Nebenbedingung)
2 „Gefällt mir“
Mhmm mhmmm…
hfftl wirds iwie ne 4.0 morgen
Auf Mathe3 konnte man sich wenigstens noch vorbereiten. Bei Mathe4 war das sinnlos. :nuts:
Anyway, gl allen.