Fourier-Motzkin-Verfahren < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | sei Ax [mm] \le [/mm] b ein lineares Ungleichungssystem, wobei A [mm] \in \IR^{m x n}
[/mm]
Das lin. UGS soll über das FM-Verfahren gelöst werden.
Warum ist das FM-Verfahren nicht unbedingt effizient bzw. wieviel UG können nach den einzelnen Eliminationsschritten resultieren? |
Hallo zusammen,
ich bereite mich gerade auf meine Staatsexamensprüfung in OR vor und im Zusammenhang mit dem FM-Algorhythmus wird wohl ganz gern mal nach der Anzahl der resultierenden UG gefragt.
In meinen Skript steht ohne Erklärung, dass diese max. [mm] \bruch{m^{2}}{4} [/mm] beträgt und im einem Skript einer anderen Uni steht ebenfalls ohne Erklärung etwas von [mm] n^{2m}.
[/mm]
Ich selber habe lange rumgerätselt, bin aber leider weder auf den einen noch auf den anderen Wert gekommen.
Mir ist natürlich klar, dass die Antwort auf die Frage nach der Effizienz lauten wird, dass die Rechnung aufgrund der hohen Zahl an UG sehr aufwändig ausfallen kann. Doch ich würde gerne wissen, wieviel UG denn nun genau resultieren und warum.
Kann mir jemand weiterhelfen?
Grüße,
Patrick
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:20 Do 27.05.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
