| Autor |
Beitrag |
    
richard
| | Veröffentlicht am Samstag, den 23. Dezember, 2000 - 21:38: | 
|
Hallo zusammen,
ich suche ein Buch, in dem das SIMPLEX-Verfahren nicht nur algorithmisch, sondern auch mathematisch begründet bzw. hergeleitet wird. Bisher fand ich nur wage Andeutungen oder reine "kochrezeptartigen" Texte, aber mich interessiert die Mathematik dahinter.
Wer kennt Bücher die in kleinen Schritten die reguläre Simplex-Theorie aufbauen?
Vielen Dank im Voraus
Richard |
Thomas Preu (Thomaspreu)
| | Veröffentlicht am Sonntag, den 24. Dezember, 2000 - 10:02: |
|
Hallo. Mich würde zunächst mal interesieren, was das SIMPLEX-Verfahren überhaupt ist(ich akzeptiere auch kochbuchartiges). SIMPLEX hört sich interesant an, aber ich habe keine Ahnung, was das ist. Ansonsten wünsche ich schöne Weihnachten. |
OliverKnieps (Oliverk)
| | Veröffentlicht am Sonntag, den 24. Dezember, 2000 - 21:54: |
|
Hallo Thomas,
das SIMPLEX-Verfahren gehört zum sehr interessanten Themengebiet der Linearen Algebra, respektive der sog. LINEAREN OPTIMIERUNG. Ein Simplex ist ein Körper in der n. Dimension mit n+1 Ecken, d.h. im R² ist es ein Dreieck, im R3 ist es die dreiseitige Pyramide usw! Ein Simplex ist immer ein einfacher Polyeder ("Vielfächner"), also alle Polyeder lassen sich aus Simplexen zusammensetzen.
Betreibt man duale lineare Optimierung, also mit nur zwei Variablen, reicht es aus die Lösung des Maximum / Minimumproblems (Beispiel: Gewinn soll maximal werden) auch auf zeichernischen Wege zu finden. Dazu verschiebt man die Zielgerade solange parallel, bis sie noch einen Punkt mit dem Planungsvieleck gemeinsam hat.
Genau da liegt schon das Problem: Im R² ist es ein ebenes Planungsvieleck, hat man es aber mit drei Variablen zu tun (Beispiel: Drei Produkte eines Unternehmens), so verlassen wir logischer weise die Ebene und bilden sog. HYPEREBENEN. Theoretisch lässt sich das Problem auf die n. Dimension ausweiten. Auf zeichnerischem Wege kommt man da aber nicht mehr weiter.
Hier greift das Simplexverfahren. Grundlegend will das Wort SIMPLEX suggerieren, das aus dem Planungsvieleck vom R² ein "Raumvieleck" wird. Es ist möglich, jemanden das Simplexverfahren ohne die hochgeradig komplexe Mathematik dahinter beizubringen, denn der Algorithmus als solches ist nicht schwer. Was die Frage von Richard betrifft, so muss ich zugeben, dass mir kein Buch bekannt ist, was das SIMPLEX-Verfahren mathematisch begründet, allenfalls "MEYERS ENZYKLOPÄDIE MATHEMATIK" befasst sich mit dem mathematisch Background, das aber sehr kompliziert. Ich werde diesbezüglich Nachforschungen anstellen.
Zur praktischen Anwendung bzw. zum ersten Kontakt mit dem von L.W. Kantorowicz (Nobelpreis für Wirtschaftswissenschaften) 1939 aufgestellten Problem für lineare Optimierung und von R. B. D. Nawamuthan 1956 entwickelten SIMPLEX-Verfahren empfehle ich z.B. ECKART/JEHLE/VOGEL: Analytische Geometrie B aus dem Bayerischen Schulbuchverlag (bsv) oder "Lineare Algebra Wirtschaft" aus dem Cornelsen Verlag.
Ich hoffe, einen kleinen Einstieg in diese komplexe Theorie geboten zu haben und wünschen allen hier
Frohe Weihnachten und ein gutes neues Jahr 2001!
(dir auch Thomas!)
Gruß
 Oliver |
Käpt`n Crunch
| | Veröffentlicht am Donnerstag, den 28. Dezember, 2000 - 22:20: |
|
Wow, das hat mich auch interessiert. Bisher konnte mir niemand was dazu sagen. Gut dass ich ohnehin die folgende Frage einstellen wollte, sonst hätte ich das obige nie gefunden.
Ich habe als Lösung für das folgende (aus Textaufgabe garantiert richtig aufgestellte) LGS:
a = 125/3, b = 40
aber ich bin mir mit diesen Lösungen nicht sicher. Könnte das jemand prüfen? Ich habe auch kein Programm mit dem ich die Lösungen selber prüfen kann, gibts so etwas? Winfunktion scheidet aus, das Modul darin arbeitet unzuverlässig und kann nur Standardfälle.
LGS:
Zielfunktion: 80a + 100b - 2000 = max
1) 6a+5b<=450
2) 3a+4b<=470
3) a>=20
4) a<=90
5) 2a<=130
6) b>=20
7) b<=40
Wobei ich meine, dass man 4) wegfallen lassen kann, da 5) eine niedrigere Restriktionssumme hat.
Wäre echt nett, wenn sich jemand die Arbeit machen könnte (bei mir waren`s 5 Tableaus, ging aber wegen der vielen Nullen recht flott) |
Thomas Preu (Thomaspreu)
| | Veröffentlicht am Freitag, den 29. Dezember, 2000 - 00:16: |
|
Zu den Simplizes steht in Spektrum der Wissenschaft in der Oktoberausgabe was drin. Hat aber mit dem was bis jetzt gesagt wurde nichts zu tun; Es geht um Spieltheorie: Zwei Spieler nehmen Teilmengen von einer vorgegebenen Menge der Mächtigkeit n nach bestimmten Regeln weg, bis nichts mehr übrig ist(an zulässigen Teilmengen); dabei kann dies durch ein n-Simplex dargestellt werden. Es gibt die noch unbewiesene Vermutung, dass es für dieses Spiel eine Gewinnstrategie gibt. |
Käpt`n Crunch
| | Veröffentlicht am Freitag, den 29. Dezember, 2000 - 02:02: |
|
Hallo, eine interessante Frage für alle, die sich gerne mal eine eigene Simplexaufgabe bauen würden.
Man kann doch aus dem Endtableau wieder auf das Starttableau kommen, wenn man über die bis zum Endtableau vorgekommenen Pivots zurückrechnet.
Kann man denn nicht ein beliebiges Endtableau zusammenstellen, aus dem man das zugehörige Starttableau berechnet? Dann hätte man selber eine Simplexaufgabe erstellt. Allerdings: zum Rückrechnen (wenn man den Weg bis zum Endtableau nicht kennt) scheinen etwas andere Regeln zum Bestimmen des Pivots zu gelten, die sich mir noch nicht erschlossen haben.
Das wäre doch mal sehr interessant! Wie kommen eigentlich die Lehrer immer auf ihre glatten Ergebnisse !!! |
Fern
| | Veröffentlicht am Freitag, den 29. Dezember, 2000 - 10:43: |
|
Hallo, Käpt'n Crunch,
Dein Ergebnis ist richtig!
Ich habe dazu mal eine grafische Lösung gezeichnet:
Die schwarzen Geraden stellen die Nebenbedingungen dar.
Das blaue Polygon beinhaltet die "feasible points".
Der Punkt M ist der gesuchte Punkt (125/3; 40) für den
die Zielfunktion den maximalen Wert (5333,33..) annimmt.
Die roten Linien stellen die Zielfunktion bei mit bestimmten konstanten Werten (Parametern) dar.
Wie man das Simplex-Verfahren zurückrechnet, habe ich mir auch noch nie überlegt. Um "runde" Ergebnisse zu erreichen, kann man aber auch an Hand einer Grafik, die entsprechenden Geraden manipulieren bis sie "runde" Schnittpunktkoordinaten aufweisen. Dies funktioniert allerdings nur bei Aufgaben mit zwei Variablen.
 |
Käpt`n Crunch
| | Veröffentlicht am Freitag, den 29. Dezember, 2000 - 12:32: |
|
Hallo Fern! Eine tolle Grafik! Mit welchem Programm hast Du die gemacht, bzw kennst Du ein Programm mit dem lineare Optimierungsaufgaben lösbar sind? Das wär was! |
Fern
| | Veröffentlicht am Freitag, den 29. Dezember, 2000 - 20:39: |
|
Hallo Käpt'n Crunch,
Die Grafik wurde mit Maple6 erstellt.
Dieses Programm kann auch Simplex Aufgaben lösen.
 |
|
