Theorie der Entartungsgraphen

Viele betriebswirtschaftliche Problemstellungen lassen sich als mathematische Optimierungsprobleme mit linearen Nebenbedingungen formulieren. Zur Bestimmung einer optimalen Lösung werden in der Regel auf dem Simplexverfahren basierende Verfahren eingesetzt. Wenn die Lösungsmenge entartete Ecken enthält, treten bei der Anwendung solcher Verfahren häufig verschiedene Effizienz- und Konvergenzprobleme auf. Ursache der zahlreichen mit Entartung verbundenen Probleme ist die Tatsache, dass zu einer entarteten Ecke eine Vielzahl von Basen gehört. Diese Arbeit knüpft an die Theorie der Entartungsgraphen an, die es ermöglicht, die Entartungsprobleme aus einer einheitlichen Sicht zu studieren und zu lösen. Der Autor stellt die Verbindungen und Zusammenhänge zwischen der Theorie der Entartungsgraphen und der Theorie der orientierten Matroiden dar. Die eineindeutige Zuordnung zwischen den positiven Entartungsgraphen und den orientierten Vektorenmatroiden wird erwiesen. Es wird eine kombinatorische Formel für die Bestimmung der Anzahl der positiven (bzw. negativen) Kanten eines Entartungsgraphen hergeleitet. Die Eigenschaften der sogenannten innenisolierten Knoten werden analysiert und auch geometrisch interpretiert. Die Benutzung solcher Knoten hat eine praktische Bedeutung bei der Suche nach neuen Anticycling- Strategien oder Lösungen des Nachbarschaftsproblems. Basierend auf den Resultaten der Untersuchung der innenisolierten Knoten wird ein Algorithmus zur Bestimmung aller Nachbarn einer entarteten Ecke vorgestellt. Der Algorithmus ist auf der künstlichen Vorstellung eines „Makro“-Übergangsgraphen aufgeb. Ein solcher Graph ist einem Übergangsgraphen ähnlich, aber die Gruppen solcher Knoten, die in dem Übergangsgraph „jeder mit jedem“ verbunden sind und sich also nach dem obigen Ansatz durch andere Knotenmengen ersetzen lassen, werden praktisch als ein „Makro“-Knoten betrachtet.