imported>Aka: /* Quellen */ typografische Anführungszeichen, ISBN-Format, Leerzeichen in Überschrift

2022-08-08T15:39:15Z

Quellen: typografische Anführungszeichen, ISBN-Format, Leerzeichen in Überschrift

Neue Seite

Die '''Netzwerk-Simplexmethode''' ist in der [[Optimierung (Mathematik)|Optimierung]] ein Verfahren zur Lösung von Min-cost-flow-Problemen durch Nutzung von Methoden des [[Simplex-Verfahren]]s. Prinzipiell könnte man dieses Problem als allgemeines [[Lineare Optimierung|lineares Optimierungsproblem]] formulieren und mit dem generischen Simplex-Verfahren lösen. Bei dieser speziellen Art von Netzwerkflussproblemen lässt sich aber jede [[Basis (Vektorraum)|Basis]] im Simplex-Verfahren als [[Baum (Graphentheorie)|Baum]] in einem Graphen interpretieren. Der Übergang von einer Basis zur nächsten entspricht dem Übergang von einem Baum zu einem anderen. Dadurch lässt sich das Lösungsverfahren deutlich beschleunigen, indem man die Simplex-Schritte durch solche kombinatorischen Operationen ersetzt. Ausgehend von einem zulässigen Baumvektor, kann man sich mit Hilfe des zugehörigen Dualproblems in jedem Iterationsschritt verbessern, bis man den optimalen Baumvektor erhält.

== Quellen ==
* Hamacher, Klamroth: „Lineare und Netzwerk Optimierung - Linear and Network Optimization. Ein bilinguales Lehrbuch - A bilingual textbook“, ISBN 3-528-03155-7
* Krumke, Noltemeier: „Graphentheoretische Konzepte und Algorithmen“, ISBN 3-519-00526-3

[[Kategorie:Optimierungsalgorithmus]]

Netzwerk-Simplexmethode - Versionsgeschichte

imported>Aka: /* Quellen */ typografische Anführungszeichen, ISBN-Format, Leerzeichen in Überschrift