Sur Limplantation Des Methodes De Points Interieurs Pour La Programmation Lineaire

Author : HERVE.. LETERRIER
Publisher :
ISBN 13 :
Total Pages : 399 pages
Book Rating : 4.:/5 (49 download)

DOWNLOAD NOW!

Download or read book METHODES INTERIEURES EN PROGRAMMATION LINEAIRE written by HERVE.. LETERRIER and published by . This book was released on 1997 with total page 399 pages. Available in PDF, EPUB and Kindle. Book excerpt: L'OBJET DE CETTE THESE CONSISTE EN LA COMPARAISON ET L'AMELIORATION DES ALGORITHMES DE RESOLUTION DE PROGRAMMES LINEAIRES FONDES SUR LE PRINCIPE DE CHEMINEMENT A L'INTERIEUR STRICT DU POLYTOPE DES POINTS REALISABLES. CECI NOUS CONDUIT TOUT D'ABORD A FAIRE UN ETAT DE L'ART DES METHODES INTERIEURES EN PROGRAMMATION LINEAIRE PROPOSEES DEPUIS 1947, ET A EN EXTRAIRE CELLES QUI SEMBLENT AVOIR, SELON LA LITTERATURE, LES MEILLEURES PERFORMANCES OU SUSCEPTIBLES D'ETRE SENSIBLEMENT AMELIOREES : C'EST A DIRE, LES METHODES DUALES PUREMENT AFFINES, LES METHODES AFFINES UTILISANT UNE FONCTION POTENTIELLE, ET LES METHODES PRIMALES-DUALES DE PATH-FOLLOWING, SIMPLE ET PREDICTIVE-CORRECTIVE DE TYPE S.MEHROTRA, QUI EST ACTUELLEMENT L'UNE DES PLUS RAPIDES. PLUS PRECISEMENT, EN NOUS BASANT SUR LES TRAVAUX D'ADLER ET AL., L'ALGORITHME DUAL AFFINE DE I.I.DIKIN AINSI QUE L'ALGORITHME POLYNOMIAL AFFINE DE C.C.GONZAGA ONT ETE IMPLEMENTES AVEC LA BIBLIOTHEQUE FORTRAN IPMLO. POUR LES METHODES DE PATH-FOLLOWING, NOUS AVONS UTILISE LE CODE PDLBM DE LA METHODE PRIMALE-DUALE AVEC FONCTION BARRIERE LOGARITHMIQUE DE MCSHANE ET AL., AINSI QUE 2 CODES DE LA METHODE PRIMALE-DUALE PREDICTIVE-CORRECTIVE : L'EXCELLENT CODE UNIVERSITAIRE HOPDM 2.13 DE J.GONDZIO ET LE CODE PROFESSIONNEL CPLEX 3.0 QUI SONT PARMI LES PLUS RAPIDES ET LES PLUS PRECIS EXISTANTS. POUR EFFECTUER DES COMPARAISONS PLUS PERTINENTES DES ALGORITHMES EXPERIMENTES, NOUS NOUS PLACONS DANS UN CONTEXTE UNIQUE DE PROGRAMMATION ADAPTE AUX BESOINS ACTUELS DE LA RECHERCHE : NOTAMMENT, D'UNE PART, NOUS RAFFINONS LES CRITERES DE PERFORMANCES EXISTANTS, EN PROPOSONS DE NOUVEAUX ET COMPARONS LES PERFORMANCES DES CODES POUR L'OBTENTION DE SOLUTIONS APPROCHEES. POUR EPROUVER PLUS SEVEREMENT LES ALGORITHMES, NOUS SIMULONS DES CONDITIONS EXPERIMENTALES PARTICULIEREMENT DEFAVORABLES ET DIFFICILES POUR UNE APPROCHE INTERIEURE. D'AUTRE PART, LA RAPIDITE DE CONVERGENCE DES METHODES INTERIEURES ETANT TOUJOURS ET PARTICULIEREMENT SENSIBLE AU CHOIX DES INITIA LISATIONS -CELLES CI N'ETANT PAS DETERMINEES D'UNE MANIERE PARFAITE- IL NOUS A AUSSI PARU IMPORTANT DE TESTER LA ROBUSTESSE DES PERFORMANCES ET DE NOS COMPARAISONS NUMERIQUES DES CODES, EN FAISANT VARIER LA POSITION DU POINT DE DEPART DANS LE POLYEDRE. A NOTRE CONNAISSANCE, DE TELS TESTS DE ROBUSTESSE N'AVAIENT PAS ETE ENCORE ENTREPRIS. PAR AILLEURS, LORS D'UNE 1#E#R#E SERIE D'EXPERIMENTATIONS, NOUS METTONS EN EVIDENCE LES POINTS FAIBLES DES METHODES DUALES AFFINES ET DES METHODES PRIMALES-DUALES DEJA EXISTANTES : LE PROBLEME DE CONVERGENCE TROP LENTE OU DE CONVERGENCE NON POLYNOMIALE DE LA METHODE DUALE AFFINE, ET LE MANQUE DE ROBUSTESSE DE LA METHODE PRIMALE-DUALE. POUR Y REMEDIER, NOUS PROPOSONS ET METTONS EN OEUVRE 4 AMELIORATIONS IMPORTANTES DE LA METHODE DUALE ; NOTAMMENT, UNE METHODE DE RECENTRAGE DU PREMIER POINT REALISABLE SOUS UNE CONTRAINTE PLANCHER, AINSI QU'UNE ADAPTATION DE LA METHODE POLYNOMIALE DE GONZAGA, QUI VONT CONSTITUER DEUX CODES PARTICULIEREMENT EFFICACES : REO2. ET GONZ. L'UNE DE CES DEUX METHODES POURRA AMELIORER LA ROBUSTESSE DES METHODES PRIMALES-DUALES. AVEC NOTRE NOUVEAU PROTOCOLE EXPERIMENTAL ET GRACE A NOS AMELIORATIONS DE LA METHODE DUALE, NOUS METTONS EN EVIDENCE DES PHENOMENES NUMERIQUES TOUT A FAIT INTERESSANTS, INCONNUS JUSQU'ALORS, QUI VONT REMETTRE EN QUESTION LES CONCLUSIONS ETABLIES PAR LA COMMUNAUTE SCIENTIFIQUE. LORS DE TESTS NUMERIQUES TRES POUSSES, NOUS CONFIRMONS QUE LES MEILLEURES METHODES PRIMALES-DUALES SONT INCONTESTABLEMENT PLUS RAPIDES QUE LES MEILLEURES METHODES DUALES, MAIS DANS DES PROPORTIONS BIEN MOINDRES QU'IL N'Y PARAISSAIT. DE PLUS, LES CODES DUAUX SE SONT AVERES NETTEMENT PLUS ROBUSTES QUE LES CODES PRIMAUX-DUAUX. EN CONCLUSION, NOUS NOUS DEMANDONS ALORS LEGITIMEMENT, LORSQUE L'ON CONCOIT UN LOGICIEL - QUE L'ON VEUT EFFICACE - DE PROGRAMMATION MATHEMATIQUE, S'IL N'EST PAS PREFERABLE DE LUI DONNER A LA FOIS DES QUALITES DE RAPIDITE ET DE ROBUSTESSE PLUTOT QUE SEULEMENT LA PREMIERE DE CELLES-CI.