Adjacente Extremalpunkte < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Ich versuche gerade die adjacenten Extremalpunkte eines Extremalpunktes eines LPs zu berechnen. Die Methode des Simplex ist mir bekannt (das invertieren Basismatrix um die Richtungen zu bestimmen, usw.).
Da ich jedoch das ganze implementieren will, wollte ich fragen, ob jemand einen Weg kennt, ohne jedesmal die Matrix zu invertieren. Ziel ist es nicht, den Simplex zu implementieren, sondern lediglich möglichst schnell alle adjacenten Extremalpunkte eines Extremalpunktes in einem Polyeder zu berechnen.
Vielen Dank schon mal für Tipps.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:33 Do 09.08.2012 | | Autor: | Stoecki |
der simplex funktioniert ja so, dass jeweils immer ein basistausch stattfindet. angenommen du hast einen extremalpunkt (also eine ecke des polyeders gegeben, müsstest du das zugehörige tableau berechnen und alle möglichen benachbarten basen ausrechnen. also eine nichtbasisspalte zur basis hinzufügen und dafür eine basisspalte aus der basis entfernen. schau dir hierzu vielleicht mal folgenden ![[]](/images/popup.gif) Link an. Die Seiten 50 ff sollten dir denke ich helfen, wie man das implementieren könnte.
gruß bernhard
|
|
|
|
