%0 Book Section
%9 OS CH : Chapitres d'ouvrages scientifiques
%A Armand, P.
%A Hamma, B.
%T Interprétation géométrique d'une nouvelle règle de pivot en programmation linéaire : poster
%B 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
%C Paris
%D 1996
%E Moukeli, P.
%L fdi:010008746
%G FRE
%I ORSTOM
%@ 2-7099-1333-X
%K PROGRAMMATION ; MODELE MATHEMATIQUE ; INTERPRETATION ; RESOLUTION
%P 366
%U https://www.documentation.ird.fr/hor/fdi:010008746
%> https://horizon.documentation.ird.fr/exl-doc/pleins_textes/pleins_textes_6/colloques2/010008746.pdf
%W Horizon (IRD)
%X 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)
%S Colloques et Séminaires
%B CARI'96 : Colloque Africain sur la Recherche en Informatique = CARI'96 : African Conference on Research in Computer Science
%8 1996/10/09-16
%$ 020MATH01