Examen recherche operationnelle mai 2014 -Programmation lina
Télécharger PDFIntroduction à la Programmation Linéaire : Exercices Pratiques
La programmation linéaire est une technique mathématique utilisée pour optimiser une fonction objectif linéaire, sous réserve de contraintes linéaires d'inégalité ou d'égalité. Elle trouve des applications dans de nombreux domaines comme l'économie, la gestion de production, la logistique ou l'agriculture. Ces exercices illustrent diverses situations où la programmation linéaire permet de prendre des décisions optimales, qu'il s'agisse de maximiser un profit, de minimiser un coût ou de gérer des ressources.
Composantes Clés d'un Programme Linéaire
- Variables de décision : Les quantités inconnues que nous cherchons à déterminer (par exemple, le nombre d'hectares de cultures, le nombre de pilules, les quantités de produits).
- Fonction objectif : L'expression linéaire que nous voulons maximiser (profit, rendement) ou minimiser (coût, temps).
- Contraintes : Les inégalités ou égalités linéaires qui représentent les limitations des ressources disponibles (temps, matériaux, espace) ou les exigences minimales/maximales.
- Contraintes de non-négativité : Les variables de décision ne peuvent généralement pas prendre de valeurs négatives.
Exercice 1 : Optimisation de l'Allocation des Ressources Agricoles
Un agriculteur souhaite allouer 150 hectares de surface irrigable entre cultures de tomates et de piments. Il dispose de 480 heures de main-d'œuvre et de 440 m³ d'eau. Les besoins et bénéfices sont les suivants :
- Un hectare de tomates demande 1 heure de main-d'œuvre, 4 m³ d'eau et donne un bénéfice net de 100 dinars.
- Un hectare de piments demande 4 heures de main-d'œuvre, 2 m³ d'eau et donne un bénéfice net de 200 dinars.
Pour protéger le prix des tomates, l'agriculteur ne peut pas cultiver plus de 90 hectares de tomates. L'objectif est d'écrire le programme linéaire qui permet une meilleure allocation de ses ressources afin de maximiser le bénéfice total.
Formulation du Programme Linéaire
Variables de décision :
x1: Nombre d'hectares alloués aux tomates.x2: Nombre d'hectares alloués aux piments.
Fonction objectif (Maximiser le Bénéfice total) :
Maximiser Z = 100x1 + 200x2
Sous contraintes :
- Contrainte de surface :
x1 + x2 ≤ 150(hectares) - Contrainte de main-d'œuvre :
1x1 + 4x2 ≤ 480(heures) - Contrainte d'eau :
4x1 + 2x2 ≤ 440(m³) - Contrainte de protection des tomates :
x1 ≤ 90(hectares) - Contraintes de non-négativité :
x1 ≥ 0, x2 ≥ 0
Exercice 2 : Minimisation des Doses Médicamenteuses
Un spécialiste en médecine a formulé un médicament (des pilules) pour traiter le rhume, disponible en deux formats :
- Petite taille : contient 2 grains d'aspirine, 5 grains de bicarbonate et 1 grain de codéine.
- Grande taille : contient 1 grain d'aspirine, 8 grains de bicarbonate et 6 grains de codéine.
Pour guérir la maladie, le patient a besoin d'au moins 12 grains d'aspirine, 74 grains de bicarbonate et 24 grains de codéine. L'objectif est d'écrire le programme linéaire qui permet de déterminer le nombre minimal de pilules à prescrire au sujet pour qu'il soit guéri, tout en respectant les doses minimales de chaque ingrédient.
Formulation du Programme Linéaire
Variables de décision :
x1: Nombre de pilules de petite taille.x2: Nombre de pilules de grande taille.
Fonction objectif (Minimiser le nombre total de pilules) :
Minimiser Z = x1 + x2
Sous contraintes :
- Contrainte d'aspirine :
2x1 + 1x2 ≥ 12(grains) - Contrainte de bicarbonate :
5x1 + 8x2 ≥ 74(grains) - Contrainte de codéine :
1x1 + 6x2 ≥ 24(grains) - Contraintes de non-négativité :
x1 ≥ 0, x2 ≥ 0(etx1, x2doivent être des entiers, mais pour un PL on les considère réels initialement).
Exercice 3 : Maximisation du Profit en Production
Pour fabriquer deux produits P1 et P2, des opérations doivent être effectuées sur trois machines M1, M2 et M3. Les temps unitaires d'exécution sont :
- Pour le produit P1 : 11 minutes sur M1, 7 minutes sur M2, 6 minutes sur M3.
- Pour le produit P2 : 9 minutes sur M1, 12 minutes sur M2, 16 minutes sur M3.
Les machines sont disponibles pour les durées suivantes :
- Machine M1 : 165 heures (9900 minutes)
- Machine M2 : 140 heures (8400 minutes)
- Machine M3 : 160 heures (9600 minutes)
Le produit P1 génère un profit unitaire de 900 dinars et le produit P2 un profit unitaire de 1000 dinars. L'objectif est d'écrire le programme linéaire qui permet d'obtenir un profit total maximum, en supposant que les machines n'ont pas de temps d'inactivité au-delà de la production planifiée.
Formulation du Programme Linéaire
Variables de décision :
x1: Quantité de produit P1 à fabriquer.x2: Quantité de produit P2 à fabriquer.
Fonction objectif (Maximiser le Profit total) :
Maximiser Z = 900x1 + 1000x2
Sous contraintes :
- Contrainte de temps machine M1 :
11x1 + 9x2 ≤ 9900(minutes) - Contrainte de temps machine M2 :
7x1 + 12x2 ≤ 8400(minutes) - Contrainte de temps machine M3 :
6x1 + 16x2 ≤ 9600(minutes) - Contraintes de non-négativité :
x1 ≥ 0, x2 ≥ 0
Exercice 4 : Optimisation des Coûts d'Alimentation Animale
Une alimentation économique pour des bestiaux doit contenir au moins 4 sortes de composants nutritifs : A, B, C et D. Deux aliments commerciaux, M et N, sont disponibles :
- 1 Kg d'aliment M contient : 100 g (0,1 Kg) de A, 100 g (0,1 Kg) de C, 200 g (0,2 Kg) de D.
- 1 Kg d'aliment N contient : 100 g (0,1 Kg) de B, 200 g (0,2 Kg) de C, 100 g (0,1 Kg) de D.
Un animal doit consommer par jour au moins : 0,4 Kg de A, 0,6 Kg de B, 2 Kg de C, 1,7 Kg de D. L'aliment M coûte 10 DT/Kg et l'aliment N coûte 4 DT/Kg. L'objectif est d'écrire le programme linéaire qui permet de déterminer les quantités d'aliments M et N à utiliser par jour et par animal pour réaliser l'alimentation la moins coûteuse.
Formulation du Programme Linéaire
Variables de décision :
x1: Quantité (en Kg) d'aliment M à utiliser par jour.x2: Quantité (en Kg) d'aliment N à utiliser par jour.
Fonction objectif (Minimiser le Coût total) :
Minimiser Z = 10x1 + 4x2
Sous contraintes :
- Contrainte nutritive A :
0.1x1 ≥ 0.4(Kg) - Contrainte nutritive B :
0.1x2 ≥ 0.6(Kg) - Contrainte nutritive C :
0.1x1 + 0.2x2 ≥ 2(Kg) - Contrainte nutritive D :
0.2x1 + 0.1x2 ≥ 1.7(Kg) - Contraintes de non-négativité :
x1 ≥ 0, x2 ≥ 0
Exercice 5 : Résolution par la Méthode du Simplexe
Résoudre le programme linéaire suivant en utilisant la méthode du simplexe :
Maximiser Z = 3x1 + 2x2
Sous contraintes :
-x1 + 2x2 ≤ 43x1 + 2x2 ≤ 14x1 + x2 ≤ 3x1 ≥ 0, x2 ≥ 0
Description de la Méthode du Simplexe
La méthode du simplexe est un algorithme itératif pour résoudre les problèmes de programmation linéaire. Elle débute par une solution réalisable de base et l'améliore progressivement à chaque itération jusqu'à ce que la solution optimale soit trouvée.
Étapes clés :
- Forme standard : Convertir toutes les inégalités en égalités en introduisant des variables d'écart (slack variables) pour les contraintes de type "≤" ou des variables d'excédent (surplus variables) et artificielles pour les contraintes de type "≥" ou "=".
Pour notre problème, nous avons des contraintes de type "≤", donc nous allons introduire des variables d'écart. - Tableau initial du simplexe : Construire le tableau en plaçant les coefficients des variables de décision, des variables d'écart et de la fonction objectif.
- Choix de la variable entrante : Identifier la variable qui entrera dans la base (variable non-basique) en sélectionnant le coefficient le plus positif (pour la maximisation) dans la ligne de la fonction objectif (ligne Z).
- Choix de la variable sortante : Déterminer la variable qui quittera la base (variable basique) en effectuant le test du ratio minimum. Le ratio est calculé en divisant la colonne des termes constants par les coefficients positifs de la variable entrante dans chaque contrainte. La ligne avec le plus petit ratio positif indique la variable sortante.
- Opérations de pivotage : Effectuer des opérations sur les lignes pour transformer le tableau afin que le coefficient de la variable entrante dans sa ligne pivot devienne 1, et tous les autres coefficients dans la colonne de la variable entrante deviennent 0. Cela correspond à trouver une nouvelle solution de base réalisable.
- Répéter : Continuer les étapes 3 à 5 jusqu'à ce que tous les coefficients de la ligne de la fonction objectif soient négatifs ou nuls (pour la maximisation), indiquant que la solution optimale a été atteinte.
Préparation du problème pour le Simplexe :
Introduisons les variables d'écart s1, s2, s3 :
-x1 + 2x2 + s1 = 43x1 + 2x2 + s2 = 14x1 + x2 + s3 = 3
Et la fonction objectif : Z - 3x1 - 2x2 = 0
Avec x1, x2, s1, s2, s3 ≥ 0.
Le tableau initial du simplexe serait ensuite construit à partir de ces équations pour commencer les itérations.
Foire Aux Questions (FAQ)
Qu'est-ce que la programmation linéaire et pourquoi est-elle utile ?
La programmation linéaire est une méthode mathématique d'optimisation permettant de trouver la meilleure solution (maximisation de profit, minimisation de coût) pour un problème modélisé par des relations linéaires. Elle est utile dans la prise de décision en gestion, logistique, production, et bien d'autres domaines, lorsque les ressources sont limitées et que l'objectif est clair et quantifiable.
Quelles sont les conditions nécessaires pour appliquer la programmation linéaire ?
Pour appliquer la programmation linéaire, trois conditions principales doivent être remplies : la linéarité (les relations entre variables et la fonction objectif doivent être linéaires), la divisibilité (les variables de décision peuvent prendre des valeurs fractionnaires), et la certitude (tous les coefficients et constantes sont connus avec certitude).
Quels sont les avantages de la méthode du simplexe pour résoudre les problèmes de programmation linéaire ?
La méthode du simplexe est un algorithme robuste et systématique qui garantit de trouver une solution optimale (si elle existe) pour les problèmes de programmation linéaire. Elle est efficace pour les problèmes à plusieurs variables et contraintes, et sa nature itérative permet une compréhension claire du processus d'optimisation.