Estabilidad numérica del método Simplex

12

El algoritmo simplex a menudo se trata dentro de la aritmética real o en el mundo discreto con cálculos exactos. Sin embargo, parece implementarse con mayor frecuencia con aritmética de punto flotante.

Esto lleva a la pregunta de si el algoritmo simplex debe considerarse como un algoritmo numérico, en particular cómo los errores de redondeo afectan el cálculo. No estoy interesado en implementaciones prácticas, sino más bien en fundamentos teóricos.

¿Conoces alguna investigación sobre este tema?

shuhalo
fuente
1
Si está interesado en implementaciones del algoritmo simplex, le sugiero que haga la pregunta en or-exchange.com
Snowie
@Snowie: Esta pregunta no trata tanto de la implementación práctica como de los aspectos teóricos. Se ha trabajado en fundamentos teóricos del análisis numérico, y me pregunto si ha afectado la teoría del algoritmo simplex. De todos modos, gracias por el enlace todavía.
shuhalo
He editado la pregunta para aclarar mi interés.
shuhalo
3
¿Has mirado el análisis suavizado ? Este trabajo no solo aborda el tiempo de ejecución promedio del caso, sino también la estabilidad promedio del caso.
Peter Shor el

Respuestas:

3

Sí, hay investigaciones sobre este tema.

El método Simplex no siempre se comporta bien , Wlodzimierz Ogryczak

retroLP, una implementación del método estándar simplex , Gavriel Yarmish y Richard Van Slyke

Una forma numéricamente estable del algoritmo simplex , Philip E. Gill y Walter Murray

También puede interesarle el método simplex revisado . Este método puede aprovechar la dispersión de la matriz; no mantiene una representación de toda la matriz. Esta tesis fue de gran interés para mí: una comparación de algoritmos de método simplex .

jnm2
fuente