Simplex / Pivot / LP |
| 19.01.2007, 21:56 | Kmatze | Auf diesen Beitrag antworten » | ||||||
| Simplex / Pivot / LP Ich beschäftige mich momentan mit dem Simplex-Algorithmus Angenommen ich habe folgendes Problem MAX 2 x_1 + 5x_2 s.t. x_1 + x_2 >= 50 x_1 - x_2 >= 50 x_1 + x_2 >= -50 x_1 - x_2 >= -50 Dann formen wir die erst in ein Standardformat um MAX 2x_1 + 5x_2 s.t. x_3 = x_1 + x_2 - 50 x_4 = x_1 - x_2 - 50 x_5 = x_1 + x_2 + 50 x_6 = x_1 - x_2 + 50 Dann suchen wir das PIVOTelement. Hierbei suchen wir zuerst den größten Positiven Koeffizienten in der Zielfunktion, und wählen dies Spalte aus: hier: x2 Dann berechnen wir, inwieweit wir x_3, x_4 x_5 x_6 Maximal erhöhen dürfen. Von diesen Werten suchen wir dann das Minimum heraus. Aber wie geht dieser Zwischenschritt? D.h. Um wieviel darf ich x_i Maximal erhöhen? Ich habe in dem fiktiven LP Problem 4 Gleicungen aufgestellt, welches die 4 verschiedenen Möglichkeiten abdeckt: x_1 -> 50 x_2 -> ??? x_3 -> unendlich x_4 -> 50 Bei 3 der 4 Möglichkeiten habe ich so eine Ahnung, ob das tatsächlich Richtig ist weiß ich allerdings nicht genau! Und bei x_2 weiß ich gar nichts. Vielen Dank Matze |
||||||||
| 19.01.2007, 22:56 | Abakus | Auf diesen Beitrag antworten » | ||||||
| RE: Simplex / Pivot / LP Willkommen im Forum, Kmatze 
Du siehst hier eigentlich bereits, dass die 3-te und 4-te Restriktion ersatzlos gestrichen werden können (wenn alle Variablen positiv sein sollen, wovon ich hier zusätzlich ausgehe). Ferner kannst du beliebig groß machen, d.h. die Lösungsmenge wird unbeschränkt sein.
OK, hier gibt es auch andere Regeln und Formate. Bei einem Maximierungsproblem hast du standardmäßig eher "<="-Restriktionen.
Hier wirkt sich das Problem mit der Unbeschränktheit aus. Du kannst beliebig erhöhen. Grüße Abakus 
|
||||||||
| 19.01.2007, 23:25 | Kmatze | Auf diesen Beitrag antworten » | ||||||
Hallo, dass ich bei MAX eher <= habe ist klar, aber wenn ich das sowieso in eine Standardformat umwandle, ist das gleichgültig!! Weil einfach alles mit *(-1) multipliziert würde.... Und dass das Modell keinen Sinn macht ist mir auch klar. Deshalb hatte ich ja fiktiv geschrieben. Mein Problem ist einfach, dass ich dann zwar 4 Restriktionen habe, aber nicht bestimmen kann, wie sich die Variablen x3,x4,x5,x6 ändern dürfen, dass trotzdem x1 und xi (also x3 oder x4 oder x5 oder x6) in der Basis sind Danke Matze |
||||||||
| 20.01.2007, 01:11 | Abakus | Auf diesen Beitrag antworten » | ||||||
Das kommt drauf an, welche Bedingungen dieses Standardformat enthält.
Ja, es ist möglich, dass das Verfahren hier stoppt, weil kein Pivot zulässig auswählbar ist. Das liegt dann an dem Problem. Du willst x_2 ja austauschen, also betrachte zB . Diese Bedingung geht aber für größer werdende x_2 nicht kaputt, sondern x_3 wird mit x_2 immer größer. Grüße Abakus
|
||||||||
| 20.01.2007, 19:08 | Kmatze | Auf diesen Beitrag antworten » | ||||||
genau das ist eben falsch. x2 geht nur bis 50 Das ist ja mein Problem |
||||||||
| 21.01.2007, 00:47 | Abakus | Auf diesen Beitrag antworten » | ||||||
Gesucht ist ja ein max. x_2, so dass x_3 positiv bleibt. Was möchtest du denn gerne haben oder erreichen ? Die Aufgabe hat eben keine endliche Lösung und das Simplex-Verfahren ist daher nicht durchführbar bzw. steckt an einer Zulässigkeitsbedingung bei der Pivotwahl fest. Grüße Abakus
|
||||||||
| Anzeige | ||||||||
|
|
||||||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
