Exercices programmation linéaire -Programmation linaire - Re
Télécharger PDFIntroduction à la Programmation Linéaire
La programmation linéaire est une technique mathématique d'optimisation utilisée pour maximiser ou minimiser une fonction objective linéaire, tout en respectant un ensemble de contraintes exprimées sous forme d'équations ou d'inéquations linéaires. Elle est largement appliquée en économie, en gestion de production et en logistique pour allouer les ressources de manière efficiente.
La Méthode du Simplexe : Résolution de Problèmes d'Optimisation
Exercice 1 : Application de l'Algorithme du Simplexe
Résoudre les programmes linéaires suivants en utilisant la méthode du simplexe :
Premier programme (Maximisation) :
Optimiser : Max (x1 + 2x2)
Sous les contraintes :
- x1 + 3x2 ≤ 21
- -x1 + 3x2 ≤ 18
- x1 - x2 ≤ 5
- x1, x2 ≥ 0
Deuxième programme (Minimisation) :
Optimiser : Min (x1 - 3x2)
Sous les contraintes :
- 3x1 - 2x2 ≤ 7
- -x1 + 4x2 ≤ 9
- -2x1 + 3x2 ≤ 6
- x1, x2 ≥ 0
Exercice 2 : Étude de Cas en Raffinerie de Pétrole
Une raffinerie traite deux types de pétrole brut pour produire de l'essence, du gasoil et du fuel. Les rendements sont les suivants :
- Brut 1 : Essence 25%, Gasoil 30%, Fuel 45%. Marge : 3 000 € par millier de m3.
- Brut 2 : Essence 35%, Gasoil 30%, Fuel 35%. Marge : 4 000 € par millier de m3.
Quotas de production maximum : 825 milliers de m3 d'essence, 750 de gasoil et 1065 de fuel. Calculez les quantités optimales de chaque brut à traiter pour maximiser le bénéfice total par la méthode du simplexe et proposez une interprétation graphique.
Exercice 3 : Recherche de Programme de Base Initial
Utilisez la méthode des valeurs ajoutées pour trouver un programme de base initial, puis résolvez par le simplexe les systèmes suivants :
Système A :
Max (x1 - x2 + x3) avec les égalités :
- -3x1 + 2x2 + x3 = 1
- x1 - x2 - x3 + x4 = 3
- x1 + 4x2 + 2x3 - 2x4 = 1
- x1, x2, x3, x4 ≥ 0
Exercice 4 : Optimisation du Profit et Mélanges
Une raffinerie produit deux essences (A et B) à partir de deux composants (P1 et P2). Les indices d'octane sont de 71 pour P1 (3900 barils dispo/jour) et 99 pour P2 (5000 barils dispo/jour). L'essence A doit avoir un indice ≥ 96 et l'essence B ≥ 85. Les prix de vente sont de 3,75 $ pour A et 2,75 $ pour B. Les excédents de P1 et P2 sont revendus respectivement à 1,25 $ et 2,25 $.
Déterminez la composition optimale pour maximiser le profit et précisez l'indice d'octane final des mélanges.
Exercice 5 : Gestion de la Production en Atelier
Une entreprise fabrique deux types de pièces (A et B) passant par trois ateliers (T, F, M). Les ressources en unités d'œuvre sont limitées (T: 200, F: 540, M: 480). Les marges par série de 100 pièces sont calculées après déduction des coûts variables de chaque atelier. Déterminez le plan de fabrication optimal pour maximiser la marge totale.
Exercice 6 : Lancement de Nouveaux Produits
Déterminez le plan de fabrication optimal pour deux modèles de moteurs (A et B) soumis à des contraintes de temps en emboutissage, soudure et peinture, tout en tenant compte de la saturation du marché pour le modèle A (1800 articles).
Exercice 7 : Minimisation des Redevances d'Extraction
Une société de carrières doit fournir des graviers de trois calibres différents. L'objectif est de minimiser le coût des redevances versées pour l'extraction dans deux carrières différentes, tout en satisfaisant la demande totale pour chaque calibre.
Analyse de la Dualité et Interprétation Économique
Exercice 8 : Prix Duaux et Facteurs de Production
Considérons une entreprise avec deux facteurs fixes : la main-d'œuvre et les équipements. Le programme vise à maximiser la marge sur coût variable.
1. Déterminez l'optimum graphiquement et calculez le vecteur des prix duaux π(I).
2. Analysez comment la marge optimale évolue en augmentant la capacité de l'un ou l'autre des facteurs.
3. Évaluez la rentabilité d'une extension simultanée des moyens de production en fonction du coût des facteurs.
Exercice 9 : Choix des Techniques de Production
Une entreprise peut fabriquer un bien via trois techniques différentes consommant des heures machine et de la main-d'œuvre. L'objectif est de maximiser la marge totale. Analysez si l'introduction d'une contrainte de demande minimale (10 unités) modifie la solution optimale trouvée par le simplexe.
Exercice 10 : Analyse de la Rentabilité par Division
Une société fabrique deux produits dans deux divisions (usinage et finition).
1. Calculez les marges sur coût variable unitaires.
2. Formulez le programme linéaire pour maximiser la marge totale sous contraintes d'heures-machine.
3. Déterminez les prix duaux pour chaque division et évaluez s'il est profitable d'augmenter les capacités de production en comparant ces prix duaux aux frais fixes engagés.
Foire Aux Questions (FAQ)
Qu'est-ce que la méthode du simplexe ?
La méthode du simplexe est un algorithme itératif permettant de résoudre des problèmes de programmation linéaire. Il consiste à se déplacer de sommet en sommet sur la frontière de la zone réalisable (un polyèdre) pour trouver celui qui maximise ou minimise la fonction objective.
À quoi servent les prix duaux en économie ?
Les prix duaux, aussi appelés "prix d'ombre", représentent la variation de la valeur de la fonction objective pour une augmentation unitaire d'une contrainte de ressource. Ils permettent de savoir combien l'entreprise serait prête à payer pour obtenir une unité supplémentaire d'une ressource rare.
Comment interpréter graphiquement un programme à deux variables ?
Pour deux variables (x1 et x2), les contraintes définissent une zone géométrique plane appelée domaine de faisabilité. La solution optimale se trouve généralement à l'un des sommets de ce domaine, là où la droite représentant la fonction objective atteint sa valeur maximale ou minimale tout en restant en contact avec la zone.