Optimisation et recherche opérationnelle 2003 Génie Informatique Université de Technologie de Belfort Montbéliard

Publié par

Examen du Supérieur Université de Technologie de Belfort Montbéliard. Sujet de Optimisation et recherche opérationnelle 2003. Retrouvez le corrigé Optimisation et recherche opérationnelle 2003 sur Bankexam.fr.
Publié le : samedi 10 février 2007
Lecture(s) : 242
Tags :
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.