UTBM 2003 ag41 optimisation et recherche operationnelle genie informatique semestre 2 partiel

Publié par

UTBM-GI AG41M´edian AG41 - Printemps 2003Dur´ee 2 heures - Documents autoris´esNom Pr´enom :Exercice 11. Donnerlacomplexit´ed’unalgorithmeder´esolutionpar´enum´erationduvoyageurdecommercea`n villes.R´eponse :2. Combienya-t-ildevariablesdebaseethorsbasepourunprogrammelin´eaire(PL)comportantn contraintes d’inf´eriorit´e etm ...
Publié le : jeudi 21 juillet 2011
Lecture(s) : 410
Nombre de pages : 4
Voir plus Voir moins
UTBM-GI
M´edianAG41-Printemps2003 Dur´ee2heures-Documentsautorise´s
NomPre´nom:
AG41
Exercice 1 1.Donnerlacomplexite´dunalgorithmedere´solutionpar´enum´erationduvoyageurdecommerce a`nvilles. Re´ponse: 2.Combienya-t-ildevariablesdebaseethorsbasepourunprogrammelin´eaire(PL)comportant ncrtnotniadseinf´eriorit´eetmavirbaelisinitlata´e?Desr.leil Re´ponse: 3.Combienya-t-ildevariablesdebaseethorsbasepourunprogrammelin´eairecomportantn contraintesd´egalit´eetmvariables initiales (m > nerllaietD´)?. Re´ponse: 4. Donnerle tableau simplexe correspondant au PL suivant : R´eponse: maxz= 2x1+ 4x2+ 6x3 5x1+ 4x2+ 7x33 6x1+ 3x2+ 9x35 x10;x20;x30
Exercice 2 : Tableau Simplexe
1.Eectueruneite´rationsurletableausimplexesuivantenutilisantles2crite`resdeDantzig pours´electionnerlesvariablesentranteetsortante.
x1x2x3x4-z 4 8 1 02 3 9 0 16 8 7 0 00
2. Indiquerles variables entrante et sortante. R´eponse: 3. Indiquerla nouvelle base. R´eponse: 4. Indiquerla matrice de base. Re´ponse:
5.DonnerlestroncaturesdeGomoryrelativesa`cettebase. Re´ponse:
1
UTBM-GI
Exercice 3 : Dual
1. Donnerle dual du PL primal suivant : PL primale:nspo´eR minz= 2x1+ 4x2+ 6x3 5x1+ 4x2+ 7x33 6x1+ 3x2+ 9x35 x10;x20;x30
AG41
2.Expliquerpourquoilasolutioninitialeduprimalnestpasadmissible(apr`esintroductiondes variablesd´ecart). R´eponse:
3.Sionchoisitdere´soudreleprimalparlam´ethodedugrandM,donnerlexpressiondela fonction objectifzen fonction des variables hors base avant d’appliquer le simplexe. R´eponse:
4. Donnerle tableau simplexe donnant la solution optimale du dual. R´eponse:
5. Utiliserles relations d’exclusion pour trouver l’optimal du primal. R´eponse:
2
UTBM-GI
AG41
Exercice 4 : Voyageur de commerce et Little 1. Indiquersi la matrice suivante est une matrice de distance. R´eponse: A B C D A 02 4 8 B 4 0 8 2 C 2 8 04 D 84 2 0 2.Donnerlarborescenceexplor´eeparlalgorithmedeLittlepourre´soudrelevoyageurdecom-mercea`4villessuivant,enpr´ecisantpourchaquesommetson´evaluationetpourchaquearc, le choix correspondant. R´eponse: A B C D A 01 2 2 B 2 0 1 2 C 4 2 01 D 84 2 0
3. Donnerla solution optimale de ce voyageur de commerce et sa longueur. R´eponse:
Exercice5:R´eseaudetransport
1.Donnerlarepr´esentationgraphiquedunechaˆıneam´eliorantedure´seaudetransportd´eni parlesarcs(arc/ux[capacite´]):OA/12[12];OB/10[15];OC/15[15];AD/7[10];AF/5[5]; BE/8[10] ;BF/2[2] ;CE/4[5] ;CF/6[10] ;CD/5[5] ;EP/12[12] ;FP/13[15] ;DP/12[15]. R´eponse:
2.Am´elioreraumieuxcettechaıˆne.Donnerpourchaquearcdecettechaıˆne,leuxcorrespon-dant. R´eponse:
3.Concluresurlavaleurduuxmaximaldecer´eseaudetransport. R´eponse:
3
UTBM-GI
AG41
Exercice6:Proble`medetransport 1.Soitunprobl`emedetransportcomportant3fournisseursdontlesdisponibilite´ssont30,20et 25 ;et 4 clients dont les demandes sont 15, 27, 21 et 12. Donner la solution du coin nord-ouest deceproble`me. Re´ponse:
2.Ondonnelamatricedescouˆtsunitairesded´eplacements(a`gauche)etunesolutionmeilleure quecelleducoinnord-ouest.Appliquerlam´ethodedustepping-stonepourdonnerlasolution optimale. 1 23 41 2 3 4 A 8 106 5A 1515 B 46 20 8B 20 C 27 1310 C7 612 Re´ponse:
4
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.