Numerische Stabilität der Simplex-Methode

12

Der Simplex-Algorithmus wird häufig entweder in der realen Arithmetik oder in der diskreten Welt mit genauen Berechnungen behandelt. Es scheint jedoch am häufigsten mit Gleitkomma-Arithmetik implementiert zu werden.

Dies führt zu der Frage, ob der Simplex-Algorithmus als numerischer Algorithmus anzusehen ist, insbesondere wie sich Rundungsfehler auf die Berechnung auswirken. Ich interessiere mich nicht für praktische Umsetzungen, sondern für theoretische Grundlagen.

Sind Ihnen Recherchen zu diesem Thema bekannt?

ds.algorithms reference-request optimization linear-programming na.numerical-analysis shuhalo
quelle
1
Wenn Sie an Implementierungen des Simplex-Algorithmus interessiert sind, empfehle ich Ihnen, die Frage in or-exchange.com
Snowie 22.01.13
@Snowie: Bei dieser Frage geht es weniger um die praktische Umsetzung als vielmehr um theoretische Aspekte. Es hat Arbeiten zu theoretischen Grundlagen der numerischen Analyse gegeben, und ich frage mich, ob dies die Theorie des Simplex-Algorithmus beeinflusst hat. Trotzdem danke für den Link noch.
Shuhalo
Ich habe die Frage bearbeitet, um mein Interesse zu verdeutlichen.
Shuhalo
3
Haben Sie sich eine geglättete Analyse angesehen ? Diese Arbeit befasst sich nicht nur mit der durchschnittlichen Falllaufzeit, sondern auch mit der durchschnittlichen Fallstabilität.
Peter Shor

Antworten:

3

Ja, es gibt Forschungen zu diesem Thema.

Die Simplex-Methode benimmt sich nicht immer gut , Wlodzimierz Ogryczak

retroLP, eine Implementierung der Standard-Simplex-Methode , Gavriel Yarmish und Richard Van Slyke

Eine numerisch stabile Form des Simplex-Algorithmus , Philip E. Gill und Walter Murray

Das könnte Sie auch interessieren überarbeitete Simplex-Methode . Diese Methode kann die Matrix-Sparsity ausnutzen. Es wird nicht die gesamte Matrix dargestellt. Diese These war für mich von großem Interesse: Ein Vergleich von Simplex-Methodenalgorithmen .

jnm2
quelle