Examen Recherche Opérationnelle et CSP : IAR427 (IN4) 2024-2025

Classe : IN4  ·  Cours : IAR427 : Recherche opérationnelle et Problèmes de Satisfaction de Contraintes  ·  Durée : 3 h  ·  Année : 2024-2025  ·  Examinateur : Pr SOH Mathurin

Calculatrices, téléphones et documents de cours interdits.

• Notions :
• Problèmes NP-complets
• Heuristiques
• Métaheuristiques
• CSP booléen
• Programmation linéaire
• Simplexe
• Dualité
• Analyse de sensibilité
• Coût réduit
• Corrigé disponible

SUJET

Exercice 1 : Notions sur les problèmes NP-complets, les heuristiques et métaheuristiques (1+1+1+1) pts

1. Expliquez ce qu'est un problème NP-complet.
2. Donnez un exemple de problème NP-complet dans le domaine de la recherche opérationnelle et expliquez brièvement pourquoi il est NP-complet.
3. Définissez les termes suivants : Heuristique, Métaheuristique, Solution optimale et solution approximative.
4. Expliquez en quoi une métaheuristique diffère d'une heuristique classique et dans quel cas on utilise principalement les métaheuristiques.

Exercice 2 Bonus : Satisfaction des contraintes booléennes 3 points

Vous devez résoudre le problème suivant de satisfaction de contraintes booléennes (CSP). On vous donne les variables suivantes :

• X1, X2, X3, X4, où chaque Xi peut être soit 0, soit 1.

Les contraintes sont :

1. X1 ∧ X2 = 1 (X1 et X2 doivent être tous deux à 1)
2. X3 ∨ X4 = 1 (soit X3, soit X4 doit être égal à 1)
3. X1 → X3 (si X1 est vrai, alors X3 doit être vrai)

Résoudre ce problème en déterminant les valeurs possibles pour X1, X2, X3 et X4.

Problème 13 points (3+2+3+2+2+1)

Partie 1

Une entreprise veut déménager son matériel composé de 450 machines de trois types : M1, M2, M3. Elle décide de louer des camions. La société de location dispose de trois sortes de véhicules : V1, V2, V3 dont les tarifs sont respectivement de 500, 800 et 1200 Dirhams pour un voyage. Les camions V1 peuvent chacun transporter une machine M1, 4 machines M2 et 10 machines M3. Pour des raisons techniques la place d'une machine d'un type donné ne peut être utilisée pour une machine d'un autre type. Chaque camion V2 peut transporter 2 machines M1, 6 machines M2 et 20 machines M3. Alors que les véhicules V3 ont pour capacité maximum : 4 machines M1, 20 machines M2 et 24 machines M3. On veut transporter en un seul convoi 30 machines M1, 120 machines M2 et 300 machines M3. L'entreprise veut déterminer le nombre de véhicules à louer pour minimiser le coût total de transport. Donner le modèle linéaire de ce problème sans le résoudre.

Partie 2

La société JET produit deux types de peintures A et B, à partir de trois matières premières M1, M2 et M3. La peinture type A nécessite 10 kg de M1, 2 kg de M2 et 1 kg de M3 ; son prix de vente est 1200 F. La peinture type B nécessite 5 kg de M1 et 3 kg de M2 ; son prix de vente est 1000 F. La société dispose de 200 kg de M1, 60 kg de M2 et 34 kg de M3.

1. Écrire le programme linéaire qui permet de maximiser le bénéfice de la société.
2. Résoudre le problème par la méthode du simplexe, interpréter les résultats obtenus.
3. Écrire le programme dual et déduire sa solution.
4. Effectuer une analyse de sensibilité pour le prix de vente de la peinture type B.
5. Une entreprise concurrente demande à la société JET de lui vendre 50 % de la matière M1 (et ce, bien entendu, avant que la fabrication ne soit lancée). À quel prix minimum la société JET devra-t-elle vendre cette quantité ? Expliquer clairement votre raisonnement.
6. Supposons qu'un troisième type C est proposé par le département de production, qui nécessite 2 kg de M1 et 3 kg de M2, et dont le prix de vente est 650 F. Tenant compte de la valeur marginale de M1 et M2, est-ce que la société JET doit produire ce type ? Expliquer clairement votre raisonnement.

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 : Problèmes NP-complets, heuristiques et métaheuristiques

1. Qu'est-ce qu'un problème NP-complet ?

Rappel des classes. P = problèmes de décision résolubles en temps polynomial par un algorithme déterministe. NP = problèmes de décision dont une solution proposée (un certificat) peut être vérifiée en temps polynomial.

Un problème de décision est NP-complet s'il vérifie deux conditions :

• il appartient à NP (on vérifie une solution en temps polynomial) ;
• il est NP-difficile : tout problème de NP se ramène à lui par une réduction polynomiale. En pratique, il suffit de montrer qu'un problème NP-complet connu (par exemple SAT) se réduit polynomialement à lui.

Conséquences. Les problèmes NP-complets sont les plus difficiles de NP. Aucun algorithme polynomial n'est connu pour eux : le temps de résolution exacte croît de façon exponentielle avec la taille des données. Si l'un d'eux était résolu en temps polynomial, tous le seraient et on aurait P = NP (question ouverte). On les traite donc en pratique par des méthodes approchées, heuristiques, métaheuristiques, dès que l'instance est grande.

2. Exemple en recherche opérationnelle : le voyageur de commerce (TSP)

Énoncé (version décision). Étant donné n villes, les distances entre elles et un entier k, existe-t-il une tournée passant exactement une fois par chaque ville et revenant au départ, de longueur ≤ k ?

Pourquoi est-il NP-complet ?

• TSP ∈ NP : étant donnée une tournée, on vérifie en O(n) qu'elle visite chaque ville une fois et on calcule sa longueur pour la comparer à k.
• TSP est NP-difficile : on réduit en temps polynomial le problème du cycle hamiltonien (NP-complet) au TSP. À partir d'un graphe G à n sommets, on crée n villes avec une distance 1 si l'arête existe dans G et 2 sinon, et on pose k = n. G possède un cycle hamiltonien si et seulement s'il existe une tournée de longueur ≤ n.
• Explosion combinatoire : il y a (n−1)!/2 tournées possibles, soit environ 6×10¹⁶ pour n = 20. L'énumération est impraticable.

Autres exemples : sac à dos, coloration de graphe, affectation de tâches avec contraintes, tournées de véhicules, ordonnancement.

3. Définitions

4. Métaheuristique et heuristique classique

Quand utilise-t-on principalement les métaheuristiques ? Pour les problèmes d'optimisation difficiles (NP-difficiles, combinatoires) de grande taille pour lesquels les méthodes exactes (simplexe, branch and bound, programmation dynamique) deviennent trop coûteuses en temps ou en mémoire ; lorsqu'une solution de bonne qualité en temps raisonnable suffit ; lorsque la fonction objectif est complexe (non linéaire, non dérivable, boîte noire) ; ou quand l'espace de recherche présente de nombreux optima locaux.

Exercice 2 Bonus : satisfaction de contraintes booléennes

Modélisation

• Variables : X = {X1, X2, X3, X4}.
• Domaines : D(Xi) = {0, 1} pour i = 1,…,4.
• Contraintes : C1 : X1 ∧ X2 = 1 ; C2 : X3 ∨ X4 = 1 ; C3 : X1 → X3 (équivalente à ¬X1 ∨ X3).

Résolution par propagation de contraintes

• C1 : X1 ∧ X2 = 1 n'est vrai que si X1 = 1 et X2 = 1. D'où X1 = 1 et X2 = 1.
• C3 : X1 → X3. Comme X1 = 1, l'implication n'est vraie que si X3 = 1 (si X3 = 0 on aurait 1 → 0 = faux). D'où X3 = 1.
• C2 : X3 ∨ X4 = 1. Comme X3 = 1, la contrainte est satisfaite quelle que soit la valeur de X4. X4 reste libre : X4 ∈ {0, 1}.

Vérification

Solutions : (X1, X2, X3, X4) = (1, 1, 1, 0) et (1, 1, 1, 1). Le problème est consistant avec 2 solutions ; X1 = X2 = X3 = 1 est imposé, seule la valeur de X4 est libre.

Problème

Partie 1 : modèle linéaire de location de camions

Variables de décision (nombres entiers de camions loués) : x1 = nombre de camions V1 ; x2 = nombre de camions V2 ; x3 = nombre de camions V3.

Fonction objectif (minimiser le coût total de transport, en Dirhams) :

Min Z = 500 x₁ + 800 x₂ + 1200 x₃

Contraintes. Le convoi doit contenir toutes les machines ; la place d'un type de machine n'étant pas utilisable pour un autre type, on écrit une contrainte par type :

M1 :   1 x1 +  2 x2 +  4 x3  >=   30
M2 :   4 x1 +  6 x2 + 20 x3  >=  120
M3 :  10 x1 + 20 x2 + 24 x3  >=  300

x1, x2, x3 >= 0  et entiers

Les variables sont entières : on ne loue pas une fraction de camion.

Remarque de cohérence : 30 + 120 + 300 = 450, ce qui correspond bien aux 450 machines de l'énoncé.

Partie 2.1 : programme linéaire de la société JET

x_A = quantité de peinture A produite ; x_B = quantité de peinture B produite.

Max Z = 1200 x_A + 1000 x_B

Avec x_A ≥ 0 et x_B ≥ 0. La peinture B ne consomme pas de M3 : la troisième contrainte ne porte que sur A.

Partie 2.2 : résolution par le simplexe

Forme standard. On ajoute une variable d'écart par contrainte (s1, s2, s3 = kilos inutilisés de M1, M2, M3) :

10 xA + 5 xB + s1        = 200
 2 xA + 3 xB      + s2   =  60
   xA                + s3 =  34

Itération 1

Colonne pivot : x_A (plus grand coefficient de la ligne Z : 1200). Ligne pivot : s1 (plus petit rapport : 20). Pivot : 10. x_A entre en base, s1 sort.

Itération 2

Colonne pivot : x_B (coefficient 400). Ligne pivot : s2 (rapport 10). Pivot : 2. x_B entre en base, s2 sort.

Itération 3 : tableau final, optimalité

Tous les coefficients de la ligne Z sont ≤ 0 : la solution est optimale. La colonne « Solution » de la ligne Z contient −Z, d'où Z = 28 000.

Solution optimale : x_A = 15 ; x_B = 10 ; s1 = 0 ; s2 = 0 ; s3 = 19. Bénéfice maximal Z* = 1200×15 + 1000×10 = 28 000 F.

Interprétation.

• La société doit produire 15 unités de A et 10 unités de B, pour un bénéfice de 28 000 F.
• M1 et M2 sont saturées (s1 = s2 = 0) : 10×15 + 5×10 = 200 kg de M1 et 2×15 + 3×10 = 60 kg de M2. Ce sont les ressources rares, les goulots d'étranglement.
• M3 n'est pas saturée : 15 kg utilisés sur 34, il reste 19 kg (s3 = 19). M3 a donc une valeur marginale nulle.

Partie 2.3 : programme dual et sa solution

À chaque contrainte du primal correspond une variable duale : y1 (M1), y2 (M2), y3 (M3), qui sont les valeurs marginales ou prix d'ombre des matières premières.

Min W = 200 y1 + 60 y2 + 34 y3

s.c.   10 y1 + 2 y2 + y3  >=  1200     (peinture A)
        5 y1 + 3 y2       >=  1000     (peinture B)

y1, y2, y3 >= 0

Solution lue dans le tableau final (ligne Z, sous les variables d'écart, en valeur absolue) : y1 = 80, y2 = 200, y3 = 0.

Vérification par les écarts complémentaires. x_A > 0 et x_B > 0, donc les deux contraintes duales sont saturées. Comme s3 > 0, on a y3 = 0, d'où le système 10y1 + 2y2 = 1200 et 5y1 + 3y2 = 1000, qui donne y1 = 80 et y2 = 200. On vérifie : 10×80 + 2×200 = 1200 ✓ et 5×80 + 3×200 = 1000 ✓.

Solution duale : y1 = 80 F/kg, y2 = 200 F/kg, y3 = 0. W* = 200×80 + 60×200 + 34×0 = 16 000 + 12 000 = 28 000 F = Z* : le théorème de la dualité forte est vérifié.

Partie 2.4 : analyse de sensibilité sur le prix de vente de B

Soit c_B le prix de vente de B, c_A = 1200 restant fixé. La base optimale (x_A, x_B, s3) reste optimale tant que les coefficients de la ligne Z des variables hors base (s1, s2) restent ≤ 0. À partir du tableau final :

• Pour s1 : 180 − c_B/10 ≥ 0  ⇔  c_B ≤ 1800.
• Pour s2 : c_B/2 − 300 ≥ 0  ⇔  c_B ≥ 600.

600 ≤ c_B ≤ 1800 F. Tant que le prix de vente de B reste dans cet intervalle, le programme optimal (15 A et 10 B) ne change pas ; seul le bénéfice varie, selon Z = 18 000 + 10 c_B. Le prix actuel de 1000 F est bien dans l'intervalle, avec une marge de −400 F et +800 F.

Hors de l'intervalle : si c_B < 600, la société ne produit plus que A (x_A = 20, x_B = 0) ; si c_B > 1800, elle produit uniquement B (x_A = 0, x_B = 20).

Partie 2.5 : vente de 50 % de la matière M1

50 % de M1 représente 100 kg. Il resterait donc 100 kg de M1 pour JET.

Raisonnement. La valeur marginale d'un kilo de M1 est y1 = 80 F : chaque kilo de M1 vendu fait varier le bénéfice de 80 F, tant que la base optimale reste valide. L'intervalle de validité du second membre b1 de M1 se trouve en résolvant 10x_A + 5x_B = b1 et 2x_A + 3x_B = 60, ce qui donne x_A = (3b1 − 300)/20 ≥ 0 et x_B = (600 − 2b1)/20 ≥ 0, soit 100 ≤ b1 ≤ 300. Avec b1 = 100 on est exactement à la limite de l'intervalle : la valeur marginale de 80 F/kg reste valable.

Si JET vend ces 100 kg, la production devient x_A = 0, x_B = 20 et le bénéfice tombe à 1000 × 20 = 20 000 F, soit une perte de 28 000 − 20 000 = 8 000 F, c'est-à-dire exactement 100 kg × 80 F/kg.

Prix minimum de cession : 80 F par kilo, soit 8 000 F pour les 100 kg. En dessous, JET perd de l'argent ; à ce prix elle est indifférente ; au-delà elle gagne.

Partie 2.6 : faut-il produire la peinture C ?

C nécessite 2 kg de M1 et 3 kg de M2, et se vend 650 F. On compare son prix de vente au coût d'opportunité des ressources qu'elle consomme, évalué aux valeurs marginales y1 = 80 et y2 = 200 :

Coût d'opportunité de C = 2 × 80 + 3 × 200 = 160 + 600 = 760 F

Coût réduit de C = 650 − 760 = −110 F < 0

Produire une unité de C ferait donc perdre 110 F par rapport au programme actuel. Autrement dit, la contrainte duale 2y1 + 3y2 ≥ 650 est déjà satisfaite (760 ≥ 650) : le plan optimal n'est pas améliorable par C.

Conclusion : non, la société JET ne doit pas produire le type C. Son prix de vente (650 F) est inférieur à la valeur des ressources rares qu'il consomme (760 F). Il deviendrait rentable si son prix dépassait 760 F. En ajoutant C au modèle, le programme optimal reste bien 15 A, 10 B, 0 C avec Z = 28 000 F.