Outcome Range Problem in Interval Linear Programming: An Exact Approach

Die Intervallprogrammierung bietet ein mathematisches Modell für unsichere Optimierungsprobleme, bei dem die Eingabedaten unabhängig innerhalb der vorgegebenen unteren und oberen Grenzen gestört werden können. In diesem Aufsatz wird das kürzlich vorgeschlagene Problem des Ergebnisbereichs im Zusammenhang mit der linearen Intervallprogrammierung diskutiert. Die Motivation für das Ergebnisbereichsproblem besteht in der Beurteilung weiterer Auswirkungen und Folgen einer optimalen Entscheidungsfindung, modelliert im Programm durch eine zusätzliche lineare Ergebnisfunktion. Konkret besteht das Ziel darin, eine untere und eine obere Grenze für den Wert der vorgegebenen Ergebnisfunktion gegenüber der optimalen Lösungsmenge des Intervallprogramms zu berechnen. In diesem Aufsatz konzentrieren wir uns hauptsächlich auf Programme mit Intervallkoeffizienten in der objektiven Funktion und dem rechtsseitigen Vektor. Für diese spezielle Klasse von Intervallprogrammen entwerfen wir einen Algorithmus zur exakten Berechnung des Ergebnisbereichs, basierend auf komplementärer Nachlässigkeit und geführter Basisaufzählung. Schließlich führen wir eine Reihe von Rechenexperimenten durch, um die Leistung der vorgeschlagenen Methode zu bewerten.