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

Français
4 pages
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

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

Sujets

Informations

Publié par
Nombre de lectures 412
Langue Français
Signaler un problème
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= 2x1+ 4x2+ 6x3 5x1+ 4x2+ 7x33 6x1+ 3x2+ 9x35 x10;x20;x30
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.
x1 4 3 8
x2 8 9 7
x3 1 0 0
x4 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