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

Description

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 ...

Informations

• Publié par: shura
• Nombre de lectures: 412
• Langue: Français

Extrait

UTBMGI

Médian AG41  Printemps 2003

Nom Prénom :

Exercice 1

Durée 2 heures  Documents autorisés

AG41

1. Donner la complexité d’un algorithme de résolution par énumération du voyageur de commerc anlliv.se è Réponse : 2. Combien y atil de variables de base et hors base pour un programme linéaire (PL) comportant ncontraintes d’infériorité etm? Détailler.variables initiales Réponse : 3. Combien y atil de variables de base et hors base pour un programme linéaire comportantn contraintes d’égalité etmvariables initiales (m > nDétailler.) ? Réponse : 4. Donner le tableau simplexe correspondant au PL suivant : Réponse :  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. Effectuer une itération sur le tableau simplexe suivant en utilisant les 2 critères de Dantzig pour sélectionner les variables entrante et sortante.

x 1 4 3 8

x 2 8 9 7

x 3 1 0 0

x 4 0 1 0

z 2 6 0

2. Indiquer les variables entrante et sortante. Réponse : 3. Indiquer la nouvelle base. Réponse : 4. Indiquer la matrice de base. Réponse :

5. Donner les troncatures de Gomory relatives à cette base. Réponse :

1