Examen Recherche Opérationnelle et CSP : IAR421 (IN4) 2025-2026

Classe : IN4  ·  Cours : IAR421 : Recherche Opérationnelle et Problèmes de Satisfaction des Contraintes  ·  Durée : 3 h  ·  Année : 2025-2026  ·  Examinateur : Pr SOH Mathurin

Tous les exercices sont obligatoires. Calculatrices, téléphones et documents de cours interdits.

• Notions :
• Programmation linéaire
• Simplexe
• Variables d'écart
• CSP
• Générer et tester
• Retour arrière
• Forward checking
• Métaheuristiques
• Recherche tabou
• Voyageur de commerce
• Corrigé disponible

SUJET

Exercice 1 : Programmation Linéaire 7 points

Une entreprise de mécanique fabrique trois types de pièces : A, B, C dans trois ateliers : usinage, montage, finitions. Les données techniques et commerciales relatives à cette fabrication sont résumées dans le tableau suivant :

1. Écrire le programme de fabrication réalisable chaque mois permettant d'obtenir le bénéfice maximal sur la vente de toute cette fabrication.
2. Résoudre ce programme par l'algorithme du simplexe (méthode des tableaux).
3. Quel est le bénéfice mensuel maximal pouvant ainsi être réalisé ? Ce programme de fabrication utilise-t-il à plein les capacités de chaque atelier ?

Exercice 2 : Problèmes de Satisfaction des Contraintes 7,5 points

Partie A : Répondre uniquement à trois questions (3 pts)

1. Qu'est-ce qu'un problème de satisfaction de contraintes (CSP) ?
2. Quelle est la différence entre une contrainte en extension et une contrainte en intension ?
3. Quelle est la différence entre une affectation partielle et une affectation totale dans un CSP ?
4. Comment distingue-t-on un CSP sur-contraint d'un CSP sous-contraint ? Expliquez avec des exemples ou situations simples.

Partie B

Soit le CSP suivant : CSP = (X, D, C), tels que :

• X = {X1, X2, X3}
• D(X1) = D(X2) = D(X3) = {3, 6, 9}
• C = {C1, C2} avec C1 : X1 < X2 et C2 : X2 < X3

1. Ce CSP est-il consistant ? Justifier votre réponse.
2. On se donne l'ordre statique suivant d'instanciation de variables : (X1, X2, X3), ainsi que l'ordre statique suivant de choix des valeurs du domaine des variables : (3, 6, 9). Que représente cette information, quel est son type et son utilité ? Est-ce qu'elle est toujours fiable ?
3. En adoptant l'ordre de la question précédente d'instanciation de variables et de choix des valeurs, appliquer les algorithmes suivants sur ce CSP, en donnant l'arbre de recherche qui correspond à chacun d'eux :
   1. l'algorithme Générer et Tester ;
   2. l'algorithme Simple Retour Arrière ;
   3. l'algorithme d'anticipation.
4. D'après les résultats obtenus en 3, expliquer la différence entre ces algorithmes.

Exercice 3 : Résolution de Problèmes par des Heuristiques / Métaheuristiques 6 points

1. Définir Métaheuristique. (1 point)
2. Donner 4 métaheuristiques et donner leur principe de fonctionnement. (2 points)
3. Voici les données d'un problème de voyageur de commerce suivant : (3 points)

Appliquer la méta-heuristique dite Recherche avec tabous en utilisant (1-2-3-4-5-6-7-8-1) comme solution initiale.

CORRECTION

Tout ce qui suit est le corrigé détaillé de l'épreuve ci-dessus. Corrigé proposé par Yankam Ngueguim Joël Stéphane : Groupe Genius Répétition.

Exercice 1 : Programmation linéaire

1. Formulation du programme de fabrication

Variables de décision (on fabrique par lots de 10 pièces) :

• x₁ = nombre de lots de pièces A fabriqués par mois ;
• x₂ = nombre de lots de pièces B fabriqués par mois ;
• x₃ = nombre de lots de pièces C fabriqués par mois.

Fonction objectif (bénéfice mensuel à maximiser, en F) :

Max Z = 100 x₁ + 150 x₂ + 250 x₃

Contraintes (capacités horaires des trois ateliers) :

Contraintes de signe : x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0.

2. Résolution par l'algorithme du simplexe

Forme standard. On ajoute une variable d'écart par contrainte (x₄, x₅, x₆ = heures inutilisées dans chaque atelier) :

Max Z = 100 x1 + 150 x2 + 250 x3 + 0 x4 + 0 x5 + 0 x6

    x1 + 2   x2 + 4   x3 + x4           = 2000
1,5 x1 + 1,5 x2 + 4,5 x3      + x5      = 2400
1,5 x1 + 2,5 x2 + 1,5 x3           + x6 = 2400

xi >= 0  pour i = 1,...,6

Base de départ : (x₄, x₅, x₆) avec x₁ = x₂ = x₃ = 0, donc Z = 0.

Itération 1

Colonne pivot : x₃ (plus grand coefficient positif de la ligne Z : 250). Ligne pivot : x₄ (plus petit rapport : 500). Élément pivot : 4. x₃ entre en base, x₄ en sort.

Itération 2

Colonne pivot : x₁ (coefficient 75/2). Ligne pivot : x₅ (rapport 400). Pivot : 3/8. x₁ entre en base, x₅ en sort.

Itération 3

Colonne pivot : x₂ (coefficient 100). Ligne pivot : x₆ (rapport 300). Pivot : 4. x₂ entre en base, x₆ en sort.

Itération 4 : tableau final, optimalité

Tous les coefficients de la ligne Z sont ≤ 0 : la solution est optimale.

Remarque : dans la ligne Z, la colonne « Solution » contient −Z (convention du cours). Ici −Z = −170 000, donc Z = 170 000.

Lecture de la solution optimale : x₁ = 1000 ; x₂ = 300 ; x₃ = 100 ; x₄ = x₅ = x₆ = 0.

3. Bénéfice maximal et utilisation des capacités

Z* = 100×1000 + 150×300 + 250×100 = 100 000 + 45 000 + 25 000 = 170 000 F

Programme de fabrication optimal : 1000 lots de A (10 000 pièces A), 300 lots de B (3 000 pièces B) et 100 lots de C (1 000 pièces C) par mois.

Conclusion : les trois variables d'écart sont nulles et hors base à l'optimum. Oui, ce programme utilise à plein les capacités de chaque atelier : usinage, montage et finitions sont tous les trois saturés.

Exercice 2 : Problèmes de satisfaction de contraintes

Partie A : Questions de cours

1. Qu'est-ce qu'un CSP ?

Un CSP est un problème défini par un triplet (X, D, C) où :

• X = {X1, …, Xn} est un ensemble fini de variables ;
• D = {D(X1), …, D(Xn)} est l'ensemble des domaines, ensembles finis de valeurs possibles de chaque variable ;
• C = {C1, …, Cm} est un ensemble de contraintes, chacune portant sur un sous-ensemble de variables et limitant les combinaisons de valeurs autorisées.

Résoudre un CSP consiste à trouver une affectation de valeurs à toutes les variables, dans leurs domaines, qui satisfait toutes les contraintes (une solution), ou à prouver qu'il n'en existe pas. Exemples : coloriage de carte, emploi du temps, Sudoku, problème des N reines.

2. Contrainte en extension et contrainte en intension

• En extension : la contrainte est définie en énumérant explicitement la liste des tuples de valeurs autorisés (ou interdits). Exemple : C(X,Y) = {(1,2), (1,3), (2,3)}.
• En intension : la contrainte est définie par une expression, formule ou prédicat que les valeurs doivent vérifier. Exemple : X < Y, ou X + Y = 10.

Avec D(X) = D(Y) = {1,2,3}, la contrainte intensionnelle X < Y équivaut à la contrainte extensionnelle {(1,2), (1,3), (2,3)}. La forme intensionnelle est plus compacte ; la forme extensionnelle est plus générale mais volumineuse.

3. Affectation partielle et affectation totale

• Affectation partielle : seule une partie des variables a reçu une valeur. Elle est dite consistante si elle ne viole aucune contrainte dont toutes les variables sont déjà instanciées.
• Affectation totale : toutes les variables ont reçu une valeur.

Une solution est une affectation totale consistante. Exemple : pour X < Y < Z sur {1,2,3}, (X=1) est une affectation partielle, (X=1, Y=2, Z=3) est une affectation totale et c'est une solution.

4. CSP sur-contraint et CSP sous-contraint

• CSP sur-contraint : les contraintes sont trop nombreuses ou trop fortes, aucune solution n'existe. Exemple : X < Y et Y < X ; ou X ≠ Y, Y ≠ Z, X ≠ Z avec les domaines {1,2}.
• CSP sous-contraint : les contraintes sont peu restrictives, il existe beaucoup de solutions. Exemple : X ≠ Y avec D(X) = D(Y) = {1,2,3}, soit 6 solutions sur 9 affectations.

Entre les deux, un CSP est « bien contraint » lorsqu'il admet une solution unique, c'est le cas de la partie B. Pour un CSP sur-contraint, on cherche souvent à relâcher des contraintes (Max-CSP) ; pour un CSP sous-contraint, on peut chercher la meilleure solution selon un critère.

Partie B : Étude du CSP

X = {X1, X2, X3} ; D(X1) = D(X2) = D(X3) = {3, 6, 9} ; C = {C1 : X1 < X2 ; C2 : X2 < X3}.

1) Ce CSP est-il consistant ?

Oui. Il admet au moins une solution : l'affectation (X1, X2, X3) = (3, 6, 9) vérifie C1 : 3 < 6 et C2 : 6 < 9. Comme il faut X1 < X2 < X3 avec seulement trois valeurs distinctes disponibles, c'est même la seule solution du CSP, qui est donc bien contraint.

2) Ordres statiques : signification, utilité, fiabilité

L'ordre statique d'instanciation des variables (X1, X2, X3) et l'ordre de choix des valeurs (3, 6, 9) sont deux heuristiques fixées avant la recherche et qui ne changent pas pendant son déroulement.

• Ce qu'elles représentent : l'ordre dans lequel l'algorithme choisit la prochaine variable à instancier (un niveau de l'arbre de recherche par variable) et l'ordre dans lequel il essaie les valeurs du domaine (l'ordre des branches d'un nœud). Elles définissent donc la forme de l'arbre de recherche parcouru.
• Utilité : elles influencent l'efficacité de la recherche. Un bon ordre, variables les plus contraintes d'abord, valeurs les plus prometteuses d'abord, permet de détecter tôt les échecs, de réduire les retours arrière et de trouver rapidement une solution. Ici, l'ordre croissant suit le sens des contraintes X1 < X2 < X3.
• Fiabilité : non, elles ne sont pas toujours fiables. Ce sont des heuristiques : elles n'affectent pas la correction (la complétude de l'algorithme reste garantie), mais n'apportent aucune garantie d'efficacité. Un mauvais ordre peut explorer inutilement une grande partie de l'arbre. Comme l'ordre est fixé à l'avance, il ne tient pas compte de l'évolution des domaines ; d'où l'intérêt des ordres dynamiques, par exemple MRV (variable de plus petit domaine).

3) Application des algorithmes

Ordre des variables : X1, X2, X3. Ordre des valeurs : 3, 6, 9.

a) Générer et Tester

Principe : on génère les affectations totales (27 au maximum) dans l'ordre lexicographique, puis on teste chacune sur l'ensemble des contraintes.

Bilan : 6 affectations totales générées et testées, 5 échecs, solution (3, 6, 9) trouvée au 6^e test.

b) Simple Retour Arrière (Backtracking)

Principe : on instancie les variables une à une ; dès qu'une contrainte est violée par l'affectation partielle, on revient en arrière et on essaie la valeur suivante.

X1 = 3  -> consistant (aucune contrainte entierement instanciee)
   X2 = 3  -> C1 : 3 < 3 faux   X   (retour arriere)
   X2 = 6  -> C1 : 3 < 6 vrai   OK
      X3 = 3  -> C2 : 6 < 3 faux   X
      X3 = 6  -> C2 : 6 < 6 faux   X
      X3 = 9  -> C2 : 6 < 9 vrai   OK  ->  SOLUTION (3, 6, 9)

Bilan : 6 affectations de valeur essayées, dont 3 échecs détectés dès l'affectation partielle. On n'a pas généré les combinaisons issues de X2 = 3, soit 3 affectations totales évitées.

c) Algorithme d'anticipation (Forward Checking)

Principe : après chaque affectation, on filtre les domaines des variables non encore instanciées en retirant les valeurs incompatibles avec la valeur choisie. Si un domaine devient vide, on revient en arrière immédiatement.

Bilan : 3 affectations seulement, aucun échec et aucun retour arrière : la valeur 3 de X2 et les valeurs 3 et 6 de X3 sont éliminées avant d'être essayées.

4) Comparaison des trois algorithmes

• Générer & Tester est le plus naïf : il ne profite pas des contraintes pour construire les affectations, teste chaque combinaison complète et ne détecte l'échec qu'à la fin (jusqu'à 3³ = 27 tests dans le pire cas). Il ne tire aucune leçon d'une erreur précoce : (3,3,3), (3,3,6) et (3,3,9) échouent tous pour la même raison, X1 < X2.
• Retour arrière simple teste les contraintes au fur et à mesure sur l'affectation partielle : une violation coupe tout le sous-arbre correspondant. Il détecte pourtant l'échec après avoir affecté la valeur.
• Anticipation (Forward Checking) va plus loin : après chaque affectation, elle propage la contrainte sur les domaines des variables futures et supprime les valeurs vouées à l'échec avant même de les essayer. C'est donc l'algorithme qui explore le moins de nœuds, ici 3, sans aucun échec, au prix d'un travail de filtrage supplémentaire à chaque nœud, largement compensé sur de grands problèmes.

Conclusion : Générer & Tester < Retour arrière < Anticipation en nombre de nœuds explorés, sachant que les trois algorithmes sont complets et trouvent la même solution (3, 6, 9).

Exercice 3 : Heuristiques et métaheuristiques

1) Définition d'une métaheuristique

Une métaheuristique (du grec méta : au-delà, à un plus haut niveau ; heuriskein : trouver) est un algorithme d'optimisation générique visant à résoudre des problèmes d'optimisation difficiles, souvent combinatoires, NP-difficiles, pour lesquels on ne connaît pas de méthode classique efficace. Elle fournit une solution de bonne qualité en temps raisonnable, sans garantie d'optimalité, en combinant exploration (diversification) et exploitation (intensification) de l'espace de recherche. Elle est indépendante du problème traité, souvent fondée sur un échantillonnage probabiliste et inspirée de systèmes naturels (physique, biologie, comportement social).

2) Quatre métaheuristiques et leur principe

Autres possibles : essaims particulaires (PSO), descente de gradient, estimation de distributions.

3) Voyageur de commerce : recherche avec tabous

Données

Villes 1 à 8. Les « – » du tableau indiquent l'absence de liaison directe : le coût est pris égal à ∞ et la tournée correspondante est interdite. Matrice symétrique complète des distances :

Paramètres de la recherche

• Solution initiale : s₀ = (1-2-3-4-5-6-7-8-1).
• Voisinage : échange de deux villes dans la tournée (la ville 1, point de départ, reste fixe), soit C(7,2) = 21 voisins par itération.
• Liste tabou : les 3 dernières paires de villes échangées. Un mouvement tabou n'est accepté que si le voisin est meilleur que la meilleure solution connue (critère d'aspiration).
• Choix : à chaque itération, le meilleur voisin autorisé, même s'il est pire que la solution courante. Arrêt : 6 itérations.

Évaluation de la solution initiale

f(s₀) = 14 + 13 + 11 + 11 + 15 + 9 + 13 + 17 = 103

La tournée est réalisable : toutes les liaisons existent. Meilleure solution courante : s* = s₀, f* = 103.

Déroulement des itérations

Itération 1 : courante : 1-2-3-4-5-6-7-8-1, coût 103. Liste tabou : ∅

Mouvement choisi : échange (2, 3). Nouvelle solution 1-3-2-4-5-6-7-8-1, coût 107. Les 6 meilleurs voisins sur 21 sont affichés ; les autres ont un coût supérieur ou sont infaisables.

Itération 2 : courante : 1-3-2-4-5-6-7-8-1, coût 107. Liste tabou : {(2,3)}

Mouvement choisi : échange (4, 5). Nouvelle solution 1-3-2-5-4-6-7-8-1, coût 108.

Itération 3 : courante : 1-3-2-5-4-6-7-8-1, coût 108. Liste tabou : {(2,3), (4,5)}

Mouvement choisi : échange (4, 6). Nouvelle solution 1-3-2-5-6-4-7-8-1, coût 111.

Itération 4 : courante : 1-3-2-5-6-4-7-8-1, coût 111. Liste tabou : {(2,3), (4,5), (4,6)}

Mouvement choisi : échange (3, 8). Nouvelle solution 1-8-2-5-6-4-7-3-1, coût 115.

Itération 5 : courante : 1-8-2-5-6-4-7-3-1, coût 115. Liste tabou : {(4,5), (4,6), (3,8)}

Mouvement choisi : échange (2, 7). Nouvelle solution 1-8-7-5-6-4-2-3-1, coût 115.

Itération 6 : courante : 1-8-7-5-6-4-2-3-1, coût 115. Liste tabou : {(4,6), (3,8), (2,7)}

Mouvement choisi : échange (5, 6). Nouvelle solution 1-8-7-6-5-4-2-3-1, coût 107.

Récapitulatif

Résultat : après 6 itérations, la meilleure tournée rencontrée reste 1-2-3-4-5-6-7-8-1 de coût 103, c'est-à-dire la solution initiale. On remarque que la recherche tabou accepte des solutions de coût plus élevé (107, 108, 111, 115) pour sortir du voisinage de la solution initiale et éviter de cycler, grâce à la liste tabou.

Remarque. En poursuivant la même recherche avec une liste tabou de taille 3, l'algorithme atteint le coût 98 à la 13^e itération, avec la tournée 1-8-3-7-6-5-4-2-1 (identique à 1-2-4-5-6-7-3-8-1 parcourue en sens inverse). Une énumération complète des tournées confirme que 98 est l'optimum global : 14 + 14 + 11 + 15 + 9 + 9 + 9 + 17 = 98. C'est l'illustration du caractère approché des métaheuristiques : en 6 itérations, l'algorithme n'a pas encore atteint l'optimum, mais il ne s'est pas non plus enfermé dans le premier optimum local.