Amélioration de la rapidité des logiciels d'optimisation linéaire
Institution:
Paris 9Disciplines:
Directors:
Abstract EN:
Our study could be divied into two parts: the first one is for the purpose of improving the simplex method's rapidity and numerical stability; in the second one, we have made a number of improvments on karmarkar's algorithm. We have used a new method proposed by p. Tolla in order to improve the execution's rapidity of simplex method. The convergence of his method has been proved in our thesis. We have given three types of pivotage to improve the numerical stability of forrest and tomlin's method. As to karmarkar's algorithme, we have simplified his demonstration of convergence. A new method "slading function" which is polynomial has been proposed in our study. We have founded a new technic for conversion of solution and two heuristics in order to improve the stability of karmarkar's algorithm.
Abstract FR:
Notre étude peut être décomposée en deux parties: la première est consacrée à l'amélioration de la rapidité et de la stabilité numérique de la méthode du simplexe ; dans la deuxième partie, nous avons apporté quelques améliorations à l'algorithme de Karmarkar. Pour améliorer la rapidité d'exécution de l'algorithme du simplexe, nous avons utilisé une nouvelle méthode proposée par Pierre Tolla: nous en avons prouvé la convergence et la teste par une expérimentation numérique. Nous avons proposé trois types de stratégies de pivotage afin d'améliorer la stabilité numérique de la méthode de Forrest et Tomlin. En ce qui concerne l'algorithme de Karmarkar, nous avons simplifié sa démonstration de convergence et donne une estimation précise de la réduction de la fonction potentielle. Nous avons proposé une technique de fonction glissante qui a un caractère polynomial. Nous avons trouvé une méthode pour convertir la solution et deux heuristiques pour améliorer la stabilité numérique de l'algorithme de Karmarkar.