Mathematisches Glossar

Fluss - Menge von Pfaden von einem gemeinsamen Startknoten (Quelle) zu einem gemeinsamen Zielknoten (Senke). Jeder Pfad hat einen nichtnegativen Wert. Die Summe dieser Werte ist der Wert des Flusses.
» ist verwandt mit: Pfad

Heuristik - Optimierungstechnik, bei der auf irgend eine beliebige Weise irgend eine Lösung eines Optimierungsproblems bestimmt wird.

Kombinatorische Optimierung - Disziplin der mathematischen Optimierung, bei der die beste aus einer endlichen, aber möglicherweise sehr grossen Zahl von Lösungen gesucht wird.
» enthält bzw. ist weiter als: Lineare Programmierung

Lagrange Pricing - Technik zur Lösung von sehr großen Mehrgüterflussproblemen, bei der auf einen Teilgraphen gerechnet wird. Fehlende Bögen werden durch die Lösung einer gewissen Lagrange Relaxierung des gesamten Problems bestimmt und nur bei Bedarf miteinbezogen.
» ist Bestandteil von: Lagrange Relaxierung

Lagrange Relaxierung -
» hat als Bestandteil: Lagrange Pricing

Lineare Programmierung - Optimierungstechnik mit Hilfe von linearen Gleichungen und Ungleichungen.
» ist enthalten in bzw. ist feiner als: Kombinatorische Optimierung; ist Methode zur Lösung von: Zuordnungsproblem

LP - Standardabkürzung für Lineare Programmierung

Mehrgüterflussproblem - Kombinatorisches Optimierungsproblem, bei dem mehrere Flüsse gleichzeitig durch eine gegebene, mit Kapazitätsbeschränkungen auf den Kanten versehene Graphen so kostengünstig wie möglich geroutet werden.
» wird beschrieben durch: Optimalitätbeweis

Minimalkostenflussproblem - Kombinatorisches Optimierungsproblem, bei dem ein Fluss mit minimalen Kantenkosten zwischen einer gegebenen Quelle und Senke gesucht ist. Auf den Kanten sind Kapazitätsbedingungen für die Menge der möglichen Pfade, die eine Kante benutzen können, vorgegeben.

Optimalitätbeweis - Technik der kombinatorischen Optimierung, bei der man versucht, für ein Minimierungsproblem eine Lösung und eine untere Schranke mit gleichem Wert zu bestimmen (analog für Maximierungsprobleme).
» macht Aussagen über: Mehrgüterflussproblem

Pfad -
» ist verwandt mit: Fluss

Relaxierung - Technik der mathematischen Optimierung, bei der die Lösungsmenge eines Problems künstlich vergrößert wird. Das relaxierte Problem ist typischerweise einfacher zu lösen als das Original.

Untere Schranke - Aussage, dass der Wert eines Minimierungsproblems nicht unterhalb eines gewissen Wertes liegen kann.

Zuordnungsproblem - Kombinatorisches Optimierungsproblem, bei dem einer Menge von Aufgaben eine Menge von Ressourcen mit minimalen Gesamtkosten. zugewiesen wird. Jeder Aufgabe wird dabei genau eine Ressource zugewiesen und umgekehrt.
» hat als Lösungsmethode: Lineare Programmierung