Theorie der Entartungsgraphen

Más información sobre el libro

Viele betriebswirtschaftliche Problemstellungen lassen sich als mathematische Optimierungsprobleme mit linearen Nebenbedingungen formulieren. Zur Bestimmung optimaler Lösungen werden häufig auf dem Simplexverfahren basierende Verfahren eingesetzt. Bei entarteten Ecken treten jedoch Effizienz- und Konvergenzprobleme auf, da zu einer entarteten Ecke viele Basen gehören. Diese Arbeit untersucht die Theorie der Entartungsgraphen, die es ermöglicht, die Probleme aus einer einheitlichen Perspektive zu betrachten und zu lösen. Der Autor zeigt die Verbindungen zwischen der Theorie der Entartungsgraphen und der Theorie der orientierten Matroiden auf und beweist die eindeutige Zuordnung zwischen positiven Entartungsgraphen und orientierten Vektorenmatroiden. Eine kombinatorische Formel zur Bestimmung der Anzahl positiver und negativer Kanten eines Entartungsgraphen wird abgeleitet. Die Eigenschaften innenisolierter Knoten werden analysiert und geometrisch interpretiert, was praktische Bedeutung bei der Suche nach neuen Anticycling-Strategien oder Lösungen des Nachbarschaftsproblems hat. Auf Basis der Ergebnisse wird ein Algorithmus zur Bestimmung aller Nachbarn einer entarteten Ecke vorgestellt. Dieser Algorithmus basiert auf der Vorstellung eines „Makro“-Übergangsgraphen, in dem Gruppen von Knoten, die eng verbunden sind, als „Makro“-Knoten betrachtet werden.