L'algorithme simplex est souvent traité soit dans l'arithmétique réelle, soit dans le monde discret avec des calculs exacts. Cependant, il semble être implémenté le plus souvent avec une arithmétique à virgule flottante.
Cela conduit à se demander si l'algorithme simplex doit être considéré comme un algorithme numérique, en particulier comment les erreurs d'arrondi affectent le calcul. Je ne m'intéresse pas aux implémentations pratiques, mais plutôt aux fondements théoriques.
Connaissez-vous des recherches sur cette question?
ds.algorithms
reference-request
optimization
linear-programming
na.numerical-analysis
shuhalo
la source
la source
Réponses:
Oui, il y a des recherches sur cette question.
La méthode Simplex n'est pas toujours bien conduite , Wlodzimierz Ogryczak
retroLP, An Implementation of the Standard Simplex Method , Gavriel Yarmish et Richard Van Slyke
Une forme numériquement stable de l'algorithme Simplex , Philip E. Gill et Walter Murray
Vous pourriez également être intéressé par la méthode simplex révisée . Cette méthode peut tirer parti de la rareté de la matrice; il ne garde pas une représentation de la matrice entière. Cette thèse m'a beaucoup intéressé: une comparaison des algorithmes de la méthode simplex .
la source