Armand P., Hamma B. (1996). Interprétation géométrique d'une nouvelle règle de pivot en programmation linéaire : poster. In :
Moukeli P. (ed.). CARI'96 : actes du 3ème colloque africain sur la recherche en informatique = CARI'96 : proceedings of the 3rd African conference on research in computer science. Paris : ORSTOM, p. 366. (Colloques et Séminaires). CARI'96 : Colloque Africain sur la Recherche en Informatique = CARI'96 : African Conference on Research in Computer Science, 3., Libreville (GAB), 1996/10/09-16. ISBN 2-7099-1333-X. ISSN 0767-2896.
Titre du document
Interprétation géométrique d'une nouvelle règle de pivot en programmation linéaire : poster
Année de publication
1996
Type de document
Partie d'ouvrage
Auteurs
Armand P., Hamma B.
In
Moukeli P. (ed.), CARI'96 : actes du 3ème colloque africain sur la recherche en informatique = CARI'96 : proceedings of the 3rd African conference on research in computer science
Source
Paris : ORSTOM, 1996,
p. 366 (Colloques et Séminaires). ISBN 2-7099-1333-X ISSN 0767-2896
Colloque
CARI'96 : Colloque Africain sur la Recherche en Informatique = CARI'96 : African Conference on Research in Computer Science, 3., Libreville (GAB), 1996/10/09-16
En recherche opérationnelle, beaucoup de problèmes peuvent être résolus à l'aide de la programmation linéaire (PL). On peut définir la programmation linéaire comme un ensemble de méthodes pour trouver l'optimum d'une fonction-coût linéaire sur un ensemble de contraintes linéaires. Ces classes de méthodes rencontrent des difficultés de convergence numérique quand il y a dégénérescence en un sommet du polyèdre des contraintes (c'est-à-dire quand il y a au delà d'un certain nombre de contraintes saturées en ce sommet). Pour y remédier plusieurs techniques sont proposées. Dans cet article nous présentons une approche géométrique. Cette approche consiste à perturber le PL (programme linéaire) de telle sorte qu'un sommet dégénéré soit éclaté en des sommets (dits éclatés) contenus dans une même facette que le sommet original. Ainsi nous montrons que cette approche préserve l'incidence, c'est-à-dire que le graphe du polyèdre C(h) perturbé reste isomorphe au graphe du polyèdre original C. Ceci permet donc d'énumérer les sommets adjacents au sommet dégénéré (l'original). (Résumé d'auteur)
