ECOLE NATIONALE                                                                                                            2005-2006

DES SCIENCES DE                                                                                                                I.I. 3

L'INFORMATIQUE

 

Optimisation Combinatoire

Examen

          

Documents autorisés                                                                                 05 Décembre 2005

Enseignante : M. MAGHREBI                                                                      Durée : 2 heures

                                                                                                                   Nombre de pages : 2

 

Exercice 1  

1. Donner la définition d’un Problème d'optimisation combinatoire.

2. Donner la classification de ces problèmes.

3. Donner un algorithme exact pour résoudre ces problèmes. Quelles sont ses avantages et ses inconvénients.

4. Appliquer l'algorithme de séparation et évaluation (seulement les quartes premières itérations) pour le problème du voyageur de commerce symétrique suivant:

+oc  15  17  16   11

15  +oo  6    10   9

17   6  +00  12 +00

16  10  12  +oo  13

11  9  +oo   13  +00

 

Quelle est la limite de cette méthode?

5. Quelle est la définition d'une heuristique, et quelle est la performance d'une heuristique?

6. Quelle est la définition d'une méta-heuristique? Donner des exemples.

7. Donner les différents paramètres qu'on doit spécifier pour l'algorithme du recuit simulé. Donner deux types de voisinages pour le problème du voyageur de commerce (donner un exemple pour un problème de taille 6) .

8. Quels sont les problèmes étudiés dans l'article [1]? Donner leur complexité.

 Donner un exemple, de taille 3, pour choques problèmes.

9. Quelles sont les différentes méthodes pour résoudre chacun de ces problèmes?

   Quelle est la méthode appliquée dans l'article 111?

10. Donner les différents paramètres d'un algorithme Tabou.

11. Donner un exemple de l'influence de la liste Tabou.

12. Méthode Tabou pour le cas du Flow Shop

(a) Donner l'ensemble des solutions.

(b) Donner le voisinage proposé par les auteurs de l'article [1].

(c) Représenter un exemple par un graphe (Topologie: solution, son coût et liens). Faite tourner l'algorithme sur l'exemple.

(d)  Quels sont les paramètres proposés par les auteurs de l'article 1.1]? Existe-t-il des méthodes théoriques pour donner ces paramètres? Quelle est la méthode utilisée par les auteurs de l'article [1] pour spécifier ces paramètres?

(e)  Quel est l'avantage de la mèthode SPIRIT?

13. Méthode Tabou pour le cas du Job Shop

(a) Donner l'ensemble des solutions.

(b) Donner le voisinage proposé par les auteurs de l'article 11].

(c) Représenter un exemple par un graphe (Topologie: solution, son coût et liens). Faite tourner l'algorithme sur l'exemple.

(d) Quels sont les paramètres proposés dans ce cas par les auteurs? Quelle est la mèthode utilisée pour spécifier ces paramètres?

(e) Quel est l'avantage de la mèthode Tabou.

References

[1] Alain Hertz et Marino Widmer, La méthode TABOU appliquée aux

problèmes d'ordonnancement. APII. Volume 29, pages 353-378,

1995.