Programmation linéaire : Optimisation d'une fonction linéaire sous contraintes linéaires.
- Identifier les variables de décision
- Formuler la fonction objectif
- Écrire les contraintes
- Tracer le domaine réalisable
- Évaluer la fonction objectif aux sommets
Soit x = nombre de meubles A produits
Soit y = nombre de meubles B produits
Maximiser : \(f(x,y) = 30x + 40y\) (profit total)
Contrainte de travail : \(2x + y \leq 40\)
Contrainte d'assemblage : \(x + 2y \leq 35\)
Contraintes de non-négativité : \(x \geq 0, y \geq 0\)
Intersection des contraintes : résoudre le système
\(2x + y = 40\) et \(x + 2y = 35\)
De la première : \(y = 40 - 2x\)
Dans la seconde : \(x + 2(40 - 2x) = 35\)
\(x + 80 - 4x = 35 \Rightarrow -3x = -45 \Rightarrow x = 15\)
\(y = 40 - 2(15) = 10\)
Sommets du domaine réalisable : (0,0), (20,0), (15,10), (0,17.5)
\(f(0,0) = 0\)
\(f(20,0) = 600\)
\(f(15,10) = 450 + 400 = 850\)
\(f(0,17.5) = 700\)
Le profit est maximisé en produisant 15 meubles A et 10 meubles B, avec un profit de 850€.
• Programmation linéaire : Solution optimale aux sommets du domaine réalisable
• Contraintes : Respecter toutes les limites imposées
• Validation : Vérifier que la solution est réalisable
La solution optimale se trouve toujours à un sommet du domaine réalisable
Les contraintes limitent les combinaisons possibles de production
Optimisation sous contrainte : Trouver le maximum d'une fonction avec une condition imposée.
Soit x la longueur et y la largeur du rectangle
Périmètre : \(2x + 2y = 20 \Rightarrow x + y = 10 \Rightarrow y = 10 - x\)
Aire : \(A = xy = x(10 - x) = 10x - x^2\)
\(A'(x) = 10 - 2x\)
\(A'(x) = 0 \Rightarrow 10 - 2x = 0 \Rightarrow x = 5\)
\(y = 10 - 5 = 5\)
\(A''(x) = -2 < 0\), donc \(x = 5\) est un maximum
Le rectangle d'aire maximale est un carré de 5cm × 5cm, avec une aire de 25cm².
• Substitution : Éliminer une variable avec la contrainte
• Optimisation : Maximum trouvé en annulant la dérivée
• Géométrie : Le carré maximise l'aire pour un périmètre fixe
Pour un périmètre fixe, le carré a la plus grande aire
La dérivée seconde négative confirme le maximum
Allocation optimale : Répartition d'un capital entre différents placements pour maximiser le rendement.
Soit x = montant investi dans l'action X
Soit y = montant investi dans l'action Y
Maximiser : \(R(x,y) = 0.05x + 0.08y\) (rendement total)
Budget total : \(x + y = 10000\)
Limite sur X : \(x \leq 6000\)
Non-négativité : \(x \geq 0, y \geq 0\)
De la contrainte budgétaire : \(y = 10000 - x\)
Donc : \(R(x) = 0.05x + 0.08(10000 - x) = 0.05x + 800 - 0.08x = 800 - 0.03x\)
\(R(x) = 800 - 0.03x\) est une fonction décroissante
Le maximum est atteint pour la plus petite valeur possible de x
Pour maximiser R, on doit minimiser x
Avec \(x \geq 0\) et \(x \leq 6000\), la valeur minimale est \(x = 0\)
Mais si \(x = 0\), alors \(y = 10000\)
On vérifie que \(x = 0 \leq 6000\) : OK
Testons \(x = 6000\) (limite supérieure) : \(y = 4000\)
\(R = 0.05(6000) + 0.08(4000) = 300 + 320 = 620\)
Testons \(x = 0\) : \(y = 10000\)
\(R = 0.05(0) + 0.08(10000) = 800\)
Pour maximiser le rendement, investir 0€ dans X et 10000€ dans Y, avec un rendement de 800€.
• Finance : Investir davantage dans l'actif qui rapporte le plus
• Optimisation : Analyser le comportement de la fonction
• Contraintes : Respecter les limites imposées
Lorsque la fonction est linéaire, l'optimum est atteint à un bord
Investir dans l'actif le plus rentable maximise le rendement
Optimisation volumique : Trouver les dimensions qui maximisent le volume d'un objet.
Feuille de dimensions 24cm × 16cm
On découpe des coins carrés de côté h et on replie pour former une boîte
Longueur : \(24 - 2h\)
Largeur : \(16 - 2h\)
Hauteur : \(h\)
\(V(h) = h(24 - 2h)(16 - 2h)\)
\(V(h) = h(384 - 48h - 32h + 4h^2) = h(384 - 80h + 4h^2)\)
\(V(h) = 384h - 80h^2 + 4h^3\)
\(h > 0\), \(24 - 2h > 0 \Rightarrow h < 12\), \(16 - 2h > 0 \Rightarrow h < 8\)
Donc \(0 < h < 8\)
\(V'(h) = 384 - 160h + 12h^2\)
\(12h^2 - 160h + 384 = 0\)
\(3h^2 - 40h + 96 = 0\)
\(\Delta = 1600 - 1152 = 448\)
\(h = \frac{40 \pm \sqrt{448}}{6} = \frac{40 \pm 21.17}{6}\)
\(h_1 \approx 3.14\), \(h_2 \approx 10.23\)
\(h_2 = 10.23 > 8\), donc non valide
\(h_1 = 3.14 < 8\), donc valide
\(V(3.14) = 3.14(24 - 6.28)(16 - 6.28) = 3.14 \times 17.72 \times 9.72 \approx 539.1\) cm³
La hauteur qui maximise le volume est d'environ 3.14cm, avec un volume de 539.1cm³.
• Géométrie : Calculer les dimensions de l'objet en fonction de la variable
• Optimisation : Annuler la dérivée pour trouver les extrema
• Validation : Vérifier que la solution est dans le domaine de validité
La hauteur optimale est inférieure à la moitié de la plus petite dimension
Les dimensions doivent rester positives pour que la boîte existe
Programmation linéaire : Optimisation d'une fonction linéaire sous contraintes linéaires.
Soit x = nombre d'unités de P1 produites
Soit y = nombre d'unités de P2 produites
Maximiser : \(f(x,y) = 10x + 15y\) (profit total)
Contrainte matière A : \(3x + y \leq 15\)
Contrainte matière B : \(2x + 4y \leq 20\)
Non-négativité : \(x \geq 0, y \geq 0\)
Intersection des contraintes : résoudre
\(3x + y = 15\) et \(2x + 4y = 20\)
De la première : \(y = 15 - 3x\)
Dans la seconde : \(2x + 4(15 - 3x) = 20\)
\(2x + 60 - 12x = 20 \Rightarrow -10x = -40 \Rightarrow x = 4\)
\(y = 15 - 3(4) = 3\)
Points d'intersection : (0,0), (5,0), (4,3), (0,5)
Vérification : (4,3) vérifie les contraintes
\(3(4) + 3 = 15 \leq 15\) ✓
\(2(4) + 4(3) = 20 \leq 20\) ✓
\(f(0,0) = 0\)
\(f(5,0) = 50\)
\(f(4,3) = 40 + 45 = 85\)
\(f(0,5) = 75\)
Le profit est maximisé en produisant 4 unités de P1 et 3 unités de P2, avec un profit de 85€.
• Programmation linéaire : Solution aux sommets du polygone de contraintes
• Contraintes : Respecter les disponibilités de matières premières
• Validation : Vérifier que la solution est réalisable
La solution optimale exploite pleinement les ressources limitantes
Les contraintes définissent les limites de production
- Identifier les variables : Déterminer les inconnues du problème
- Formuler l'objectif : Écrire la fonction à optimiser
- Établir les contraintes : Exprimer les limitations
- Résoudre mathématiquement : Utiliser les techniques appropriées
- Interpréter les résultats : Donner du sens à la solution
- La solution optimale se trouve toujours sur la frontière du domaine réalisable
- Les contraintes actives déterminent la solution optimale
- La programmation linéaire a des solutions aux sommets du polygone de contraintes
- La substitution permet de réduire le nombre de variables
- La dérivée nulle identifie les extrema locaux
