Programmation linéaire et optimisation exercices corrigés -P
Télécharger PDFTD 2 : Programmation linéaire et optimisation par la méthode du Simplexe
Exercice 1 : Optimisation linéaire par la Méthode du Simplexe
Énoncé du problème
On considère la région R dans un plan définie par les inégalités suivantes :
- 2x + y ≤ 30
- x + 4y ≤ 64
- 5x + 6y ≤ 110
- x ≥ 0 et y ≥ 0
L'objectif est de trouver le maximum de la fonction objectif z = f(x, y) = 10x + 20y sur la région R.
Solution par la méthode du Simplexe
Pour résoudre ce problème de programmation linéaire, nous utilisons la méthode du simplexe. Le premier pas est de construire le tableau initial du simplexe, en introduisant les variables d'écart (s1, s2, s3) pour convertir les inégalités en égalités. Ces variables représentent les quantités non utilisées des ressources. Les variables de base initiales sont s1, s2, s3.
Le tableau initial est le suivant :
Variables de base | x | y | s1 | s2 | s3 | bi | bi/ai
-----------------------------------------------------------
s1 | 2 | 1 | 1 | 0 | 0 | 30 | 30/1 = 30
s2 | 1 | 4 | 0 | 1 | 0 | 64 | 64/4 = 16
s3 | 5 | 6 | 0 | 0 | 1 | 110 | 110/6 ≈ 18.33
Z | -10 | -20 | 0 | 0 | 0 | 0 |
Première itération : Choix du pivot et transformation du tableau
Pour la maximisation, la variable entrante est celle qui a le coefficient le plus négatif dans la ligne Z. Ici, c'est -20, correspondant à la variable y. Pour déterminer la variable sortante, nous calculons les ratios bi/ai pour les coefficients positifs de la colonne y. Le plus petit ratio positif est 16 (64/4), qui correspond à la ligne de s2. Le pivot est donc la valeur 4 (intersection de la colonne y et de la ligne s2).
Après les opérations de ligne (division de la ligne du pivot par le pivot et annulation des autres coefficients de la colonne du pivot), le tableau devient :
Variables de base | x | y | s1 | s2 | s3 | bi | bi/ai
-----------------------------------------------------------
s1 | 7/4 | 0 | 1 | -1/4 | 0 | 14 | 14/(7/4) = 8
y | 1/4 | 1 | 0 | 1/4 | 0 | 16 | 16/(1/4) = 64
s3 | 7/2 | 0 | 0 | -3/2 | 1 | 14 | 14/(7/2) = 4
Z | -5 | 0 | 0 | 5 | 0 | 320 |
Le nouveau point solution faisable est {x, y} = {0, 16}, avec une valeur de fonction objectif z = 320. La méthode du simplexe s'est déplacée du point d'origine {0, 0} le long de l'arête x=0 vers ce nouveau point.
Deuxième itération : Nouveau pivot et approche de l'optimum
La variable la plus négative dans la ligne de la fonction objectif est -5, correspondant à la variable x (variable entrante). Pour déterminer la variable sortante, nous calculons les ratios bi/ai pour les coefficients positifs de la colonne x. Les ratios sont : 14/(7/4) = 8, 16/(1/4) = 64, 14/(7/2) = 4. Le plus petit ratio positif est 4, correspondant à la ligne de s3. Le pivot est donc 7/2 (intersection de la colonne x et de la ligne s3).
Après les opérations de ligne, le tableau devient :
Variables de base | x | y | s1 | s2 | s3 | bi
-----------------------------------------------------------
s1 | 0 | 0 | 1 | 1/2 | -1/2 | 7
y | 0 | 1 | 0 | 3/7 | -1/14 | 15
x | 1 | 0 | 0 | -3/7 | 2/7 | 4
Z | 0 | 0 | 0 | 20/7 | 10/7 | 340
Solution optimale
Puisqu'il n'y a plus de coefficients négatifs dans la ligne de la fonction objectif (Z), la solution optimale est atteinte.
D'après le tableau final :
- La variable x est basique, et sa valeur est l'élément bi correspondant à sa ligne : x = 4.
- La variable y est basique, et sa valeur est l'élément bi correspondant à sa ligne : y = 15.
- La variable s1 est basique, sa valeur est s1 = 7.
- Les variables s2 et s3 sont non-basiques, donc s2 = 0 et s3 = 0.
Le point solution optimale est {x, y} = {4, 15}. La méthode du simplexe s'est déplacée de la solution précédente {0, 16} vers ce nouveau point le long de l'arête x + 4y = 64.
La valeur maximale de la fonction objectif Z est lue dans la dernière ligne et la colonne bi : Z = 340.
L'évolution de la fonction objectif au fil des itérations est la suivante :
- Au point d'origine {0, 0}, Z = 10(0) + 20(0) = 0
- Après la première itération {0, 16}, Z = 10(0) + 20(16) = 320
- Après la deuxième itération {4, 15}, Z = 10(4) + 20(15) = 40 + 300 = 340
Exercice 2 : Résolution d'un problème de PL standard
Énoncé du problème
Résoudre par la méthode du simplexe le problème de programmation linéaire (PL) standard suivant :
Maximiser la fonction objectif Z = x1 + 2x2 – x3
Soumise aux contraintes suivantes :
- 2x1 + x2 + x3 ≤ 14
- 4x1 + 2x2 + 3x3 ≤ 28
- 2x1 + 5x2 + 5x3 ≤ 30
- x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
Note
Cet exercice nécessite l'application des mêmes principes de la méthode du simplexe que l'Exercice 1 pour trouver la solution optimale, en introduisant des variables d'écart pour transformer les inégalités en égalités.
Exercice 3 : Optimisation d'investissement
Un investisseur doit choisir parmi deux types d'actifs : Ilog et BNP Paribas. L'action Ilog a une espérance de gain de 80 € et l'action BNP Paribas de 60 € (valeur ajustée pour être cohérente avec la fonction objectif). L'investisseur ne peut acheter au total que 100 actions et compte dépenser au plus 800 €. L'action Ilog coûte 5 € et l'action BNP Paribas 10 €. L'achat des actions se fait via une banque qui touche une commission de 2 € par action Ilog et 1 € par action BNP Paribas. L'investisseur ne veut pas dépasser 150 € de commissions. Combien d'actions de chaque type l'investisseur doit acheter pour maximiser ses revenus futurs ?
1. Définition des variables de décision
Les variables de décision sont les quantités sur lesquelles l'investisseur doit prendre des décisions. Ici, il s'agit du nombre d'actions de chaque type à acheter :
- x1 : Nombre d'actions Ilog à acheter.
- x2 : Nombre d'actions BNP Paribas à acheter.
2. Formulation de la fonction objectif
La fonction objectif représente le revenu total que l'investisseur souhaite maximiser. Basée sur l'espérance de gain par action :
Maximiser Z = 80x1 + 60x2.
3. Définition des contraintes
Les contraintes sont les limitations et conditions que les décisions doivent respecter :
- Contrainte sur le nombre total d'actions : L'investisseur ne peut acheter au total que 100 actions.
x1 + x2 ≤ 100 - Contrainte sur les commissions bancaires : La commission totale ne doit pas dépasser 150 €.
2x1 + x2 ≤ 150 - Contrainte budgétaire : Le coût total d'achat des actions ne doit pas dépasser 800 €.
5x1 + 10x2 ≤ 800 - Contraintes de non-négativité : Le nombre d'actions ne peut pas être négatif.
x1 ≥ 0 et x2 ≥ 0
4. Forme générale du Problème de Programmation Linéaire (PL)
Le problème peut être formulé comme suit :
Maximiser Z = 80x1 + 60x2
Sujet à :
- x1 + x2 ≤ 100
- 2x1 + x2 ≤ 150
- 5x1 + 10x2 ≤ 800
- x1 ≥ 0, x2 ≥ 0
5. Résolution graphique
Bien que la solution graphique ne soit pas détaillée ici, cette méthode consiste à tracer les droites correspondant aux contraintes, à identifier la région des solutions admissibles (le polygone de faisabilité), puis à trouver le point optimal en déplaçant la ligne de niveau de la fonction objectif jusqu'à son point le plus éloigné dans la direction d'amélioration.
6. Résolution par la méthode du Simplexe (méthode du tableau)
Pour résoudre le problème par la méthode du simplexe, nous transformons les inégalités en égalités en introduisant des variables d'écart (x3, x4, x5) :
Maximiser Z = 80x1 + 60x2 + 0x3 + 0x4 + 0x5
Sujet à :
- x1 + x2 + x3 = 100
- 2x1 + x2 + x4 = 150
- 5x1 + 10x2 + x5 = 800
- x1, x2, x3, x4, x5 ≥ 0
La résolution itérative de la méthode du simplexe, en déterminant successivement les variables entrantes et sortantes, conduit à la solution optimale. Le processus s'arrête lorsque tous les coefficients de la ligne de la fonction objectif sont non-négatifs.
D'après le résultat fourni, la solution optimale est :
- x1 = 50 (50 actions Ilog)
- x2 = 50 (50 actions BNP Paribas)
- Le revenu maximal (Z) est de 7000 €.
7. Formulation du simplexe sous forme matricielle
La forme matricielle est une représentation compacte du problème de programmation linéaire en forme standard.
Les composants sont :
- Vecteur des coefficients de la fonction objectif : c = [80, 60, 0, 0, 0]
- Vecteur des variables : x = [x1, x2, x3, x4, x5]T
- Matrice des coefficients des contraintes (A) :
1 1 1 0 0 2 1 0 1 0 5 10 0 0 1
- Vecteur des seconds membres des contraintes (b) : b = [100, 150, 800]T
Le problème de PL sous forme standard s'écrit alors :
Maximiser Z = c * x
Sujet à : A * x = b
x ≥ 0
8. Résolution par outils logiciels
Pour des problèmes de programmation linéaire plus complexes ou pour vérifier les calculs manuels, il est courant d'utiliser des logiciels spécialisés en optimisation ou des solveurs intégrés dans des tableurs. Ces outils permettent de trouver rapidement la solution optimale en appliquant les algorithmes du simplexe ou d'autres méthodes d'optimisation.
Foire Aux Questions (FAQ) sur la Programmation Linéaire et le Simplexe
Qu'est-ce que la méthode du simplexe ?
La méthode du simplexe est un algorithme itératif développé par George Dantzig pour résoudre les problèmes d'optimisation linéaire. Elle fonctionne en se déplaçant d'un sommet à l'autre d'un polygone de faisabilité (défini par les contraintes), améliorant la valeur de la fonction objectif à chaque étape, jusqu'à atteindre une solution optimale.
Pourquoi utilise-t-on des variables d'écart dans la méthode du simplexe ?
Les variables d'écart sont introduites pour convertir les contraintes d'inégalité (≤ ou ≥) en égalités. Elles représentent la "marge" ou l'excédent de ressource non utilisée. Cette transformation est essentielle pour former le tableau initial du simplexe, qui doit travailler avec un système d'équations linéaires.
Comment identifier la solution optimale dans un tableau du simplexe ?
Pour un problème de maximisation, la solution optimale est atteinte lorsque tous les coefficients de la ligne de la fonction objectif (ligne Z) sont non-négatifs. À ce stade, les valeurs des variables de décision basiques et la valeur maximale de la fonction objectif peuvent être lues directement dans la colonne des seconds membres (bi).