ÉCOLE NATIONALE SUPÉRIEURE POLYTECHNIQUE
Master 2 — Programmation Linéaire et Non Linéaire
Devoir à la Maison — Corrigé Complet
PARTIE I — QUESTIONS THÉORIQUES
Question 1 — Définition de la Recherche Opérationnelle
La Recherche Opérationnelle (RO) est une discipline scientifique qui applique des méthodes analytiques
avancées pour aider à prendre de meilleures décisions. Elle consiste à modéliser des problèmes
complexes de gestion et d'organisation à l'aide de formulations mathématiques (fonctions objectif,
contraintes), puis à résoudre ces modèles par des algorithmes afin d'identifier la solution optimale parmi
un ensemble de solutions réalisables. Elle regroupe notamment : la programmation linéaire, la
programmation en nombres entiers, la théorie des graphes, les files d'attente, et la simulation.
Question 2 — Importance dans le domaine de l'ingénierie / management
La Recherche Opérationnelle est essentielle dans de nombreux domaines d'ingénierie et de gestion. Elle
permet notamment :
Domaine Application
Gestion de production Optimisation des plans de fabrication (ex. : quantités produites, mix-produit)
Logistique & transport Minimisation des coûts d'acheminement, tournées de véhicules
Finance Optimisation de portefeuilles d'investissements
Énergie Planification de la production électrique, répartition de charges
Télécommunications Routage optimal des flux de données
Santé Affectation des ressources médicales, planification des soins
PARTIE II — EXERCICE 1 : Problème de Maximisation
Formulation du problème
Maximiser :
Z = 4x1 + 6x2 + 3x3
Sous les contraintes :
x1 + 6x2 + 2x3 ≤ 24 (C1)
x1 + 3x2 − 2x3 ≤ 9 (C2)
x1, x2, x3 ≥ 0
Mise en forme standard (ajout des variables d'écart)
On introduit les variables d'écart e1 ≥ 0 et e2 ≥ 0 pour transformer les inégalités en égalités :
x1 + 6x2 + 2x3 + e1 = 24
x1 + 3x2 − 2x3 + e2 = 9
Z − 4x1 − 6x2 − 3x3 = 0
Solution de base initiale : e1 = 24, e2 = 9, x1 = x2 = x3 = 0 → Z = 0
Tableau Simplexe — Itération 0 (Initial)
La variable entrante est x2 (coefficient le plus négatif dans la ligne Z : −6).
Ratios : C1 → 24/6 = 4 ; C2 → 9/3 = 3. Variable sortante : e2 (ratio minimal = 3). Élément pivot : 3 (ligne C2,
colonne x2).
Base x1 x2 x3 e1 e2 bi Ratio
e1 1 6 2 1 0 24 24/6 = 4
e2 1 3* -2 0 1 9 9/3 = 3 ← min
Z -4 -6 -3 0 0 0 —
* Élément pivot (surligné en orange)
Opérations de pivotage — Itération 1
Nouvelle ligne pivot (R2) : diviser par 3
R2' = R2 / 3 → [1/3, 1, -2/3, 0, 1/3, 3]
Élimination :
R1' = R1 − 6×R2' → [1-2, 0, 2+4, 1, -2, 24-18] = [-1, 0, 6, 1, -2, 6]
Rz' = Rz + 6×R2' → [-4+2, 0, -3-4, 0, 2, 0+18] = [-2, 0, -7, 0, 2, 18]
Tableau Simplexe — Itération 1
Variable entrante : x3 (coeff. le plus négatif dans Z : −7). Ratios : e1 → 6/6 = 1 ; x2 → ratio négatif, ignoré. Variable
sortante : e1. Élément pivot : 6.
Base x1 x2 x3 e1 e2 bi Ratio
e1 -1 0 6* 1 -2 6 6/6 = 1 ← min
x2 1/3 1 -2/3 0 1/3 3 négatif, ignoré
Z -2 0 -7 0 2 18 —
Opérations de pivotage — Itération 2
Nouvelle ligne pivot (R1) : diviser par 6
R1'' = R1'/6 → [-1/6, 0, 1, 1/6, -1/3, 1]
Élimination :
R2'' = R2' + (2/3)×R1'' → [1/3-1/9, 1, 0, 1/9, 1/3-2/9, 3+2/3]
= [2/9, 1, 0, 1/9, 1/9, 11/3]
Rz'' = Rz' + 7×R1'' → [-2-7/6, 0, 0, 7/6, 2-7/3, 18+7]
= [-19/6, 0, 0, 7/6, -1/3, 25]
Tableau Simplexe — Itération 2
Variable entrante : x1 (seul coeff. négatif dans Z : −19/6). Ratios : x3 → 1/(-1/6) < 0, ignoré ; x2 → (11/3)/(2/9) =
33/2 = 16.5. Variable sortante : x2. Élément pivot : 2/9.
Base x1 x2 x3 e1 e2 bi Ratio
x3 -1/6 0 1 1/6 -1/3 1 négatif, ignoré
x2 2/9* 1 0 1/9 1/9 11/3 16.5 ← min
Z -19/6 0 0 7/6 -1/3 25 —
Opérations de pivotage — Itération 3
Nouvelle ligne pivot (R2) : multiplier par 9/2
R2''' = R2''×(9/2) → [1, 9/2, 0, 1/2, 1/2, 33/2]
Élimination :
R1''' = R1'' + (1/6)×R2''' → [0, 3/4, 1, 1/4, -1/4, 1+11/4] = [0, 3/4, 1,
1/4, -1/4, 15/4]
Rz''' = Rz'' + (19/6)×R2''' → [0, 19×(9/2)/6, 0, 7/6+19/12, -1/3+19/12,
25+19×33/12]
Rz''' = [0, 57/4, 0, 25/12, 5/4, 25+209/4] = [0, 57/4, 0, 25/12, 5/4,
309/4]
Tableau Simplexe — Itération 3 (Optimal)
Tous les coefficients de la ligne Z sont ≥ 0 → Solution optimale atteinte !
Base x1 x2 x3 e1 e2 bi
x3 0 3/4 1 1/4 -1/4 15/4
x1 1 9/2 0 1/2 1/2 33/2
Z 0 57/4 0 25/12 5/4 309/4
✔ Solution Optimale — Exercice 1
Variable Valeur Calcul
x1 33/2 = 16.5 Lue dans le tableau final
x2 0 Hors base
x3 15/4 = 3.75 Lue dans le tableau final
Z* 309/4 = 77.25 Valeur optimale de la fonction objectif
Vérification : Z = 4(33/2) + 6(0) + 3(15/4) = 66 + 0 + 45/4 = 66 + 11.25 = 77.25 ✓
PARTIE III — EXERCICE 2 : Société VTT-ÉVASION
Données du problème
ASPIN (x) ISERAN (y) TOURMALET (z)
Temps de montage (h) 1 1.5 3
Coût des pièces (€) 80 90 120
Marge unitaire (€) 32 45 72
Question 1 — Programme initial : 6 ASPIN, 12 ISERAN, 12 TOURMALET
Calculs pour le programme initial (x=6, y=12, z=12) :
Indicateur Formule Calcul Résultat
Temps total de montage 1×x + 1.5×y + 3×z 1×6 + 1.5×12 + 3×12 6 + 18 + 36 = <b>60 h</b>
Coût total des pièces 80×x + 90×y + 120×z 80×6 + 90×12 + 120×12
480+1080+1440 = <b>3 000 €</b>
Marge totale 32×x + 45×y + 72×z 32×6 + 45×12 + 72×12
192+540+864 = <b>1 596 €</b>
Question 2a — Forme standard du problème d'optimisation
L'entreprise souhaite maximiser la marge sans dépasser le temps de montage ni le coût des pièces du
programme initial, avec une production totale maximale de 35 VTT/jour.
On note : x = nb ASPIN, y = nb ISERAN, z = nb TOURMALET fabriqués par jour.
Les variables d'écart e1, e2, e3 sont associées respectivement à :
• e1 : contrainte sur la production totale (≤ 35)
• e2 : contrainte sur le temps de montage (≤ 60 h)
• e3 : contrainte sur le coût des pièces (≤ 3 000 €)
Fonction objectif :
Max Z = 32x + 45y + 72z
Contraintes (forme standard avec variables d'écart) :
x + y + z + e1 = 35 (production totale)
x + 1.5y + 3z + e2 = 60 (temps de montage)
80x + 90y + 120z + e3 = 3000 (coût des pièces)
x, y, z, e1, e2, e3 ≥ 0
Solution de base initiale (variables de base : e1=35, e2=60, e3=3000) → Z = 0
Question 2b — Résolution par la méthode du Simplexe
Ligne Z (à maximiser) : Z − 32x − 45y − 72z = 0. La variable entrante est z (coefficient le plus négatif :
−72).
Tableau Simplexe — Itération 0 (Initial)
Ratios : e1→35/1=35 ; e2→60/3=20 ; e3→3000/120=25. Variable sortante : e2 (ratio minimal = 20). Pivot : 3.
Base x y z e1 e2 e3 bi Ratio
e1 1 1 1 1 0 0 35 35/1 = 35
e2 1 1.5 3* 0 1 0 60 60/3 = 20 ← min
e3 80 90 120 0 0 1 3000 3000/120 = 25
Z -32 -45 -72 0 0 0 0 —
Opérations — Itération 1
R2' = R2/3 → [1/3, 1/2, 1, 0, 1/3, 0, 20]
R1' = R1 − 1×R2' → [2/3, 1/2, 0, 1, -1/3, 0, 15]
R3' = R3 − 120×R2' → [40, 30, 0, 0, -40, 1, 600]
Rz' = Rz + 72×R2' → [-8, -9, 0, 0, 24, 0, 1440]
Tableau Simplexe — Itération 1
Variable entrante : y (coefficient le plus négatif : −9). Ratios : e1→15/(1/2)=30 ; z→20/(1/2)=40 ; e3→600/30=20.
Variable sortante : e3 (ratio min = 20). Pivot : 30.
Base x y z e1 e2 e3 bi Ratio
e1 2/3 1/2 0 1 -1/3 0 15 15/(1/2)=30
z 1/3 1/2 1 0 1/3 0 20 20/(1/2)=40
e3 40 30* 0 0 -40 1 600 600/30=20 ← min
Z -8 -9 0 0 24 0 1440 —
Opérations — Itération 2
R3'' = R3'/30 → [4/3, 1, 0, 0, -4/3, 1/30, 20]
R1'' = R1' − (1/2)×R3'' → [2/3-2/3, 0, 0, 1, -1/3+2/3, -1/60, 15-10] = [0,
0, 0, 1, 1/3, -1/60, 5]
R2'' = R2' − (1/2)×R3'' → [1/3-2/3, 0, 1, 0, 1/3+2/3, -1/60, 20-10] =
[-1/3, 0, 1, 0, 1, -1/60, 10]
Rz'' = Rz' + 9×R3'' → [-8+12, 0, 0, 0, 24-12, 9/30, 1440+180] = [4, 0, 0,
0, 12, 3/10, 1620]
Tableau Simplexe — Itération 2 (Optimal)
Tous les coefficients de la ligne Z sont ≥ 0 → Solution optimale atteinte !
Base x y z e1 e2 e3 bi
e1 0 0 0 1 1/3 -1/60 5
z -1/3 0 1 0 1 -1/60 10
y 4/3 1 0 0 -4/3 1/30 20
Z 4 0 0 0 12 3/10 1620
✔ Solution Optimale — Exercice 2
Variable Valeur Interprétation
x (ASPIN) 0 Ne pas produire d'ASPIN
y (ISERAN) 20 unités Produire 20 ISERAN par jour
z (TOURMALET) 10 unités Produire 10 TOURMALET par jour
Production totale 30 VTT/jour 30 ≤ 35 → contrainte respectée
Temps de montage 1.5×20+3×10 = 60 h Contrainte saturée (e2=0)
Coût des pièces 90×20+120×10=3000 € Contrainte saturée (e3=0)
Z* (Marge max.) 1 620 €/jour Gain vs prog. initial : +24 €/jour
Vérification : Z* = 32(0) + 45(20) + 72(10) = 0 + 900 + 720 = 1 620 € ✓ (Programme initial : 1 596 € → amélioration
de +24 €/jour)
Corrigé réalisé par méthode du Simplexe — Master 2 ENSP — Programmation Linéaire et Non Linéaire — 2025/2026