Examen recherche opérationnelle sujet 01

Examen corrige recherche opérationnelle

Exercice 1: Evaluation des Connaissances générales (5 points)

1. Expliciter la différence entre un problème d'optimisation (programmation linéaire) et un problème de satisfaction des contraintes

2. Une entreprise fabrique des armoires et des tables; Une armoire nécessite 1h de travail et 9 m2 de bois; Une table nécessite 1h de travail et 5m2 de bois; On dispose de 6h de travail et de 45 m2 de bois Chaque armoire génère un profit de 80 00FCFA, et chaque table 5000FCFA.

a)Formuler comme un problème de programmation linéaire en nombre entiers

b) Le résoudre par la méthode de simplexe.

3.La méthode de recuit simulé utilise la loi de probabilité de Poisson pour poursuivre la recherche de solution même lorsqu’un optimum local est rencontré

Exercice 2 :  Metaheuristique et exemple (5points)

1. Définir metaheuristique.
2. Citer deux propriétés communes à toutes les métaheuristiques vues au cours.
3. Quel est l'avantage d'une métaheuristique à population par rapport à celle à solution unique?
4. Quel est l'inconvénient d'une métaheuristique à population par rapport à celle à solution unique?
5. Citer une métaheuristique constructive et une métaheuristique transformative vues au cours.

Exercice 3 : Problème de satisfaction de contraintes (CPS) (5 points)

Il s'agit de colorier les 14 régions de la carte ci-dessous, de sorte que deux régions ayant une frontière en commun soient coloriées avec des couleurs différentes. On dispose pour cela des 4 couleurs suivantes : bleu, rouge, jaune et vert.

Modélisez ce problème sous la forme d'un problème de satisfaction de contraintes.

Exercice 4 (Formalisation de problème) (5 points)

Quatre jeunes juges tout juste sortis de l’école nationale de la magistrature se retrouvent à l’occasion d’une rencontre amicale et échangent leurs points de vue sur leur première année d’expérience. Ils étaient tous quatre de très bons étudiants et occupaient les 4 premières places dans le classement de sortie de l’école, ce qui leur a plus ou moins permis de choisir le lieu de leur première affectation. On sait qu’au moment de leur candidature, ils étaient tous âgés de 27 à 29 ans et que deux d’entre eux avaient 28 ans. On sait également que : (a) André à 29 ans. (b) Lucie était moins bien classée que le candidat affecté à Paris. (c) Les deux premiers ont choisi une affectation dans des villes au sud de la France (Lyon ou Marseille). (d) Les deux ayant 28ans se suivaient dans le classement final. (e) Didier, qui a 28 ans était moins bien classé que celui qui est allé à Lyon. (f) Ce n’est pas Claire qui est allée à Lyon. (g) Le plus jeune candidat était classé au moins 2 rangs derrière Claire et s’est retrouvé affecté à Lille.

1. Formaliser l’énoncé précédent sous forme d’un problème de satisfaction de contraintes. Bien préciser le sens de vos variables et comment vous modélisez les différentes parties de l’énoncé. Vous ferez attention à ne pas utiliser de contraintes disjonctives.
2. Dessinez le graphe de contraintes de ce problème.
3. Ce CSP est-il cohérent par Sommet ? cohérent par arc ? Justifiez votre réponse
4. Trouver une solution pour ce problème. Vous pouvez procéder comme vous le souhaitez... mais expliquez et détaillez votre manière d’obtenir cette solution.