Td1 optimisation programmation lineaire et optimisation -Pro
Télécharger PDFExercices Corrigés d'Optimisation et Programmation Linéaire
Cette série d'exercices porte sur l'étude des systèmes d'inéquations et la résolution de problèmes d'optimisation par la méthode graphique. La programmation linéaire est un outil mathématique essentiel pour la prise de décision, permettant de maximiser un profit ou de minimiser un coût sous certaines contraintes.
Exercice 1 : Introduction aux inéquations à deux inconnues
On donne les quatre points E, A, B, C caractérisés par leurs coordonnées : E(20 ; 10), A(20 ; 50), B(40 ; 30) et C(50 ; 10).
1°) Placer ces points dans un repère puis tracer le polygone EABC.
2°) Écrire les équations de droites (EA), (EC), (AB), (BC).
3°) Écrire le système de quatre inéquations permettant de caractériser un point intérieur au polygone EABC.
Note explicative : Pour déterminer l'équation d'une droite passant par deux points, on utilise la formule de la pente m = (yB - yA) / (xB - xA), puis on résout pour l'ordonnée à l'origine.
Exercice 2 : Représentation graphique de systèmes
Représentez graphiquement l'ensemble des points M de coordonnées (x ; y) vérifiant les systèmes suivants :
Système a :
2x + 4y ≤ 10
3x - 4y ≥ 2
x + y ≥ 0
Corrigé : On représente graphiquement les trois droites frontières D1 : 2x + 4y = 10, D2 : 3x - 4y = 2 et D3 : x + y = 0. La zone solution est l'intersection des demi-plans définis par les inéquations.
Système b :
2x + 3y ≤ 12
3x + y ≤ 9
x + y ≥ 2
x ≥ 0, y ≥ 0
Corrigé : Le système conduit à tracer cinq droites. Les deux dernières (x=0 et y=0) correspondent aux axes des coordonnées. On obtient un polygone de solutions en hachurant les zones non valides.
Système c (Valeurs absolues) :
|x + 2y| ≤ 6
|x - 2y| ≥ 2
Corrigé : Par définition des valeurs absolues :
-6 ≤ x + 2y ≤ 6
x - 2y ≥ 2 ou x - 2y ≤ -2
Le domaine de solution est la réunion de deux régions S1 et S2 délimitées par les droites D1 : x+2y=6, D2 : x+2y=-6, D3 : x-2y=-2 et D4 : x-2y=2.
Exercice 3 : Maximisation d'une fonction objectif
Déterminer le maximum de la fonction f(x, y) = x + 3y sous les contraintes suivantes :
2x + 5y ≤ 10
3x + 4y ≤ 12
x > 0, y > 0
Corrigé : On trace les droites frontières et on identifie le polygone des contraintes. On trace ensuite des droites de niveau Δ(a) d'équation x + 3y = a. En augmentant la valeur de "a", la droite se déplace. Le point extrême touchant encore le domaine est le point A(0 ; 2). Le maximum est donc atteint pour x = 0 et y = 2, soit f(0, 2) = 0 + 3(2) = 6.
Exercice 4 : Recherche de minimum et de maximum
Déterminer le minimum et le maximum de (2x + 3y) sous les contraintes :
2x + y ≥ 0
x - y ≤ 3
x - y ≥ -5
Corrigé :
1. Le minimum est atteint au point d'intersection des droites 2x + y = 0 et x - y = 3, soit le point A(1 ; -2). Min = 2(1) + 3(-2) = -4.
2. Le maximum n'est pas défini car le domaine des solutions est ouvert (non borné) dans la direction de croissance de la fonction objectif.
Exercice 5 : Optimisation de variables x1 et x2
Déterminer le maximum de (10x1 + 30x2) sous les contraintes :
x1 + 3x2 ≤ 18
x1 + x2 ≤ 8
2x1 + x2 ≤ 14
x1 ≥ 0, x2 ≥ 0
Corrigé : L'ensemble des solutions est défini par un polygone. Le maximum se situe sur la portion de la droite d'équation x1 + 3x2 = 18 incluse dans le domaine admissible.
Exercice 6 : Optimisation de la production en usine
Une usine fabrique deux produits. Chaque produit passe par trois ateliers (A, B, C) avec les consommations horaires suivantes :
Produit 1 : Atelier A (2h), Atelier B (1h), Atelier C (1h).
Produit 2 : Atelier A (1h), Atelier B (1h), Atelier C (0h).
Bénéfices : Produit 1 (2€), Produit 2 (1€).
Limitations d'énergie : Atelier A ≤ 6, Atelier B ≤ 4, Atelier C ≤ 3.
Corrigé :
Fonction à maximiser : Z = 2X1 + X2
Contraintes :
X1 + 2X2 ≤ 6 (Atelier A)
X1 + X2 ≤ 4 (Atelier B)
X1 ≤ 3 (Atelier C)
X1, X2 ≥ 0
Exercice 7 : Gestion des stocks hôteliers
Un gérant d'hôtel a besoin de 90 draps, 240 serviettes et 240 gants. Deux lots sont proposés :
Lot A (200F) : 2 draps, 4 serviettes, 8 gants.
Lot B (400F) : 3 draps, 12 serviettes, 6 gants.
Corrigé :
1. Système d'inéquations :
2x + 3y ≥ 90 (Draps)
4x + 12y ≥ 240 (Serviettes)
8x + 6y ≥ 240 (Gants)
x ≥ 0, y ≥ 0
2. Fonction objectif (à minimiser) : 200x + 400y.
Exercice 8 : Recette maximale d'un fleuriste
Un fleuriste dispose de 50 lys, 80 roses et 80 jonquilles. Il propose deux types de bouquets :
Bouquet 1 (40€) : 10 lys, 10 roses, 20 jonquilles.
Bouquet 2 (50€) : 10 lys, 20 roses, 10 jonquilles.
Corrigé :
Soit x le nombre de bouquets 1 et y le nombre de bouquets 2.
Contraintes simplifiées :
x + y ≤ 5 (Lys)
2x + y ≤ 8 (Roses)
x + 2y ≤ 8 (Jonquilles)
Objectif : Maximiser 4x + 5y.
Conclusion
La méthode graphique est simple et efficace pour résoudre des problèmes à deux variables. Cependant, pour des problèmes impliquant trois variables ou plus, elle devient impraticable. Dans ces cas, on utilise la méthode du Simplexe, développée par George Dantzig, qui permet de résoudre des systèmes complexes de programmation linéaire de manière algorithmique.
FAQ - Programmation Linéaire
Qu'est-ce qu'une fonction objectif ?
C'est une expression mathématique (souvent linéaire) que l'on cherche à maximiser (pour un profit, un rendement) ou à minimiser (pour un coût, une perte) dans un problème d'optimisation.
Quand le maximum d'un problème linéaire n'est-il pas défini ?
Le maximum n'est pas défini lorsque le domaine des solutions (l'ensemble des contraintes) est ouvert ou non borné dans la direction où la fonction objectif croît indéfiniment.
Quelle est la différence entre une contrainte et une solution admissible ?
Une contrainte est une limitation (souvent une inéquation) imposée par les ressources. Une solution admissible est n'importe quel point (x, y) qui respecte simultanément toutes les contraintes du système.