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

Description

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.

Sujets

• 2003

Informations

• Publié par: bankexam
• Publié le: 10 février 2007
• Nombre de lectures: 163
• Langue: Français

Extrait

UTBM-GI

M´edianAG41-Printemps2003 Dur´ee2heures-Documentsautorise´s

NomPre´nom:

AG41

Exercice 1 1.Donnerlacomplexite´d’unalgorithmedere´solutionpar´enum´erationduvoyageurdecommerce a`nvilles. Re´ponse: 2.Combienya-t-ildevariablesdebaseethorsbasepourunprogrammelin´eaire(PL)comportant ncrtnotnia’dseinf´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= 2x 1 + 4x 2 + 6x 3   5x 1 + 4x 2 + 7x 3 ≤3 6x 1 + 3x 2 + 9x 3 ≤5   x 1 ≥0;x 2 ≥0;x 3 ≥0

Exercice 2 : Tableau Simplexe

1.Effectueruneite´rationsurletableausimplexesuivantenutilisantles2crite`resdeDantzig pours´electionnerlesvariablesentranteetsortante.

x 1 x 2 x 3 x 4 -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= 2x 1 + 4x 2 + 6x 3   5x 1 + 4x 2 + 7x 3 ≥3 6x 1 + 3x 2 + 9x 3 ≥5   x 1 ≥0;x 2 ≥0;x 3 ≥0

AG41

2.Expliquerpourquoilasolutioninitialeduprimaln’estpasadmissible(apr`esintroductiondes variablesd’´ecart). R´eponse:

3.Sionchoisitdere´soudreleprimalparlam´ethodedugrandM,donnerl’expressiondela 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.Donnerl’arborescenceexplor´eeparl’algorithmedeLittlepourre´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´esentationgraphiqued’unechaˆıneam´eliorantedure´seaudetransportd´efini parlesarcs(arc/flux[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,lefluxcorrespon- dant. R´eponse:

3.Concluresurlavaleurdufluxmaximaldecer´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