Correction examen recherche operationnelle session principal
Télécharger PDFCorrection d'examen de Recherche Opérationnelle
Cette correction d'examen de Recherche Opérationnelle s'adresse aux étudiants de 3ème année EFB (Économie, Finance, Banque) de l'École Supérieure des Sciences Économiques et Commerciales de Tunis, session principale de Mai 2014. Elle couvre la modélisation en programmation linéaire et la résolution par la méthode du Simplexe.
Exercice 1 : Problème d'agriculture
Ce problème vise à maximiser le profit d'une exploitation agricole en allouant des surfaces pour différentes cultures.
1. Variables de décision
- x1 : la surface allouée à la culture des tomates (en unités de surface)
- x2 : la surface allouée à la culture des piments (en unités de surface)
2. Contraintes
Les contraintes représentent les limitations de ressources ou les exigences spécifiques :
- Contrainte de terrain : La surface totale cultivée ne doit pas dépasser 150 unités.
- Contrainte d'eau : La consommation totale d'eau pour les deux cultures ne doit pas dépasser 440 unités.
- Contrainte de main d’œuvre : Le besoin total en main d'œuvre ne doit pas dépasser 480 unités.
- Contrainte administrative (périmètre irrigué) : La surface allouée aux tomates ne doit pas dépasser 90 unités.
- Contraintes de non-négativité : Les surfaces cultivées ne peuvent pas être négatives.
3. Fonction objectif
Maximiser le profit généré par les cultures.
4. Programme linéaire modélisant le problème
Maximiser Z = 100x1 + 200x2
Sous contraintes :
- x1 + x2 ≤ 150
- 4x1 + 2x2 ≤ 440
- x1 + 4x2 ≤ 480
- x1 ≤ 90
- x1 ≥ 0, x2 ≥ 0
Exercice 2 : Problème médical
Ce problème vise à minimiser une certaine valeur (par exemple, un coût ou une quantité totale) liée à la prescription de pilules.
1. Variables de décision
- x1 : le nombre de pilules de petite taille à prescrire
- x2 : le nombre de pilules de grande taille à prescrire
2. Contraintes
Ces contraintes représentent des exigences minimales (par exemple, de dosage ou de nutriments).
- 2x1 + x2 ≥ 12
- 5x1 + 8x2 ≥ 74
- x1 + 6x2 ≥ 24
- Contraintes de non-négativité : Le nombre de pilules ne peut pas être négatif.
3. Fonction objectif
Minimiser Z = x1 + x2
4. Programme linéaire modélisant le problème
Minimiser Z = x1 + x2
Sous contraintes :
- 2x1 + x2 ≥ 12
- 5x1 + 8x2 ≥ 74
- x1 + 6x2 ≥ 24
- x1 ≥ 0, x2 ≥ 0
Exercice 3 : Problème de production
Ce problème concerne la fabrication de deux produits, P1 et P2, avec des ressources machines limitées, dans le but de maximiser le profit.
1. Variables de décision
- x1 : le nombre d’unités du produit P1 à fabriquer
- x2 : le nombre d’unités du produit P2 à fabriquer
2. Contraintes
Ces contraintes sont liées à la capacité des machines disponibles (M1, M2, M3).
- Machine M1 : 11x1 + 9x2 ≤ 9900
- Machine M2 : 7x1 + 12x2 ≤ 8400
- Machine M3 : 6x1 + 16x2 ≤ 9600
- Contraintes de non-négativité : Les quantités produites ne peuvent pas être négatives.
3. Fonction objectif
Maximiser Z = 900x1 + 1000x2
4. Programme linéaire résultant
Maximiser Z = 900x1 + 1000x2
Sous contraintes :
- 11x1 + 9x2 ≤ 9900
- 7x1 + 12x2 ≤ 8400
- 6x1 + 16x2 ≤ 9600
- x1 ≥ 0, x2 ≥ 0
Exercice 4 : Problème d'alimentation
Ce problème porte sur la minimisation du coût d'une alimentation pour des bestiaux, en utilisant deux types d'aliments (M et N) tout en respectant des exigences nutritionnelles minimales (composants A, B, C, D).
1. Variables de décision
- x1 : la quantité d’aliments M à utiliser
- x2 : la quantité d’aliments N à utiliser
2. Contraintes
Ces contraintes garantissent les quantités minimales requises pour chaque composant.
- Composant A : x1 ≥ 4
- Composant B : x2 ≥ 6
- Composant C : x1 + 2x2 ≥ 20
- Composant D : 2x1 + x2 ≥ 17
- Contraintes de non-négativité : Les quantités d'aliments ne peuvent pas être négatives.
3. Fonction objectif
Minimiser Z = 10x1 + 4x2
4. Programme linéaire
Minimiser Z = 10x1 + 4x2
Sous contraintes :
- x1 ≥ 4
- x2 ≥ 6
- x1 + 2x2 ≥ 20
- 2x1 + x2 ≥ 17
- x1 ≥ 0, x2 ≥ 0
Exercice 5 : Résolution par la méthode du Simplexe
Cet exercice détaille l'application de la méthode du Simplexe pour résoudre un programme linéaire de maximisation.
1. Forme standard du programme linéaire
Le programme linéaire est mis sous forme standard en introduisant des variables d'écart (x3, x4, x5) pour transformer les inégalités en égalités et pour assurer que toutes les variables sont non-négatives.
Maximiser Z = 3x1 + 2x2 + 0x3 + 0x4 + 0x5
Sous contraintes :
- -x1 + 2x2 + x3 = 4
- 3x1 + 2x2 + x4 = 4
- x1 - x2 + x5 = 3
- x1, x2, x3, x4, x5 ≥ 0
2. Solution initiale de base
La solution de base initiale est obtenue en fixant les variables de décision (x1, x2) à zéro, ce qui donne les valeurs pour les variables d'écart :
- x1 = 0
- x2 = 0
- x3 = 4
- x4 = 4
- x5 = 3
3. Tableau de simplexe initial (1ère itération)
Le tableau de simplexe organise les coefficients du programme linéaire et permet d'identifier la variable entrante (celle qui améliore le plus la fonction objectif) et la variable sortante (celle qui atteint sa limite en premier).
Les coûts marginaux (Cj) sont ceux de la fonction objectif.
Cj 3 2 0 0 0
| Cb | Base | x1 | x2 | x3 | x4 | x5 | b | Ratio (b/x1) |
|---|---|---|---|---|---|---|---|---|
| 0 | x3 | -1 | 2 | 1 | 0 | 0 | 4 | N/A (pivot négatif) |
| 0 | x4 | 3 | 2 | 0 | 1 | 0 | 14 | 14/3 |
| 0 | x5 | 1 | -1 | 0 | 0 | 1 | 3 | 3 |
| Cj-Zj | 3 | 2 | 0 | 0 | 0 | |||
La variable entrante est x1, car elle présente le plus grand effet net positif (Cj-Zj = 3). La variable sortante est x5, car elle correspond au plus petit quotient positif (Ratio = 3).
4. 2ème itération
Après le pivotage, un nouveau tableau est généré, reflétant l'échange des variables dans la base.
Cj 3 2 0 0 0
| Cb | Base | x1 | x2 | x3 | x4 | x5 | b | Ratio (b/x2) |
|---|---|---|---|---|---|---|---|---|
| 0 | x3 | 0 | 1 | 1 | 0 | 1 | 7 | 7 |
| 0 | x4 | 0 | 5 | 0 | 1 | -3 | 5 | 1 |
| 3 | x1 | 1 | 1 | 0 | 0 | 1 | 3 | 3 |
| Cj-Zj | 0 | 2 | 0 | 0 | -3 | |||
La variable entrante est x2 (Cj-Zj = 2). La variable sortante est x4 (plus petit ratio positif = 1).
5. 3ème itération et solution optimale
La méthode se poursuit jusqu'à ce que tous les gains marginaux (Cj-Zj) soient négatifs ou nuls, indiquant que la solution optimale a été atteinte pour un problème de maximisation.
Cj 3 2 0 0 0
| Cb | Base | x1 | x2 | x3 | x4 | x5 | b |
|---|---|---|---|---|---|---|---|
| 0 | x3 | 0 | 0 | 1 | -1/5 | 8/5 | 6 |
| 2 | x2 | 0 | 1 | 0 | 1/5 | -3/5 | 1 |
| 3 | x1 | 1 | 0 | 0 | 1/5 | 2/5 | 4 |
| Cj-Zj | 0 | 0 | 0 | -10 | 0 | ||
Tous les gains marginaux (Cj-Zj) sont négatifs ou nuls, ce qui indique que le tableau de simplexe est optimal.
La solution optimale du programme linéaire est :
- x1 = 4
- x2 = 1
- x3 = 6
- x4 = 0
- x5 = 0
La valeur de la fonction objectif Z est de 14.
6. Remarque sur les solutions optimales multiples
Lorsqu'un gain marginal (Cj-Zj) pour une variable hors base est nul, cela indique l'existence de solutions optimales multiples. L'introduction de cette variable dans la base ne modifiera pas la valeur de la fonction objectif.
Ici, l'effet net de l'augmentation d'une unité de la valeur de x5 (variable hors base) est nul.
Un autre tableau du simplexe, représentant une solution optimale alternative, est le suivant :
Cj 3 2 0 0 0
| Cb | Base | x1 | x2 | x3 | x4 | x5 | b |
|---|---|---|---|---|---|---|---|
| 0 | x5 | 0 | 0 | 5/8 | -1/8 | 1 | 15/4 |
| 2 | x2 | 0 | 1 | 3/8 | 1/8 | 0 | 13/4 |
| 3 | x1 | 1 | 0 | -1/4 | 1/4 | 0 | 5/2 |
| Cj-Zj | 0 | 0 | 0 | -1 | 0 | ||
Ce tableau est également optimal. La solution correspondante est :
- x1 = 5/2
- x2 = 13/4
- x3 = 0
- x4 = 0
- x5 = 15/4
La valeur de la fonction objectif Z est toujours 14.
Foire Aux Questions (FAQ)
Qu'est-ce que la Recherche Opérationnelle ?
La Recherche Opérationnelle (RO) est une discipline qui utilise des méthodes scientifiques et mathématiques pour prendre de meilleures décisions. Elle aide à résoudre des problèmes complexes d'optimisation, de planification ou d'allocation de ressources dans divers domaines comme la logistique, la production, la finance ou la santé.
Quand utilise-t-on la programmation linéaire ?
La programmation linéaire est utilisée lorsque le problème d'optimisation peut être modélisé avec une fonction objectif linéaire et un ensemble de contraintes linéaires. Elle est particulièrement efficace pour des problèmes de maximisation (profit, production) ou de minimisation (coût, temps) avec des ressources limitées ou des exigences à respecter.
Comment interpréter une solution optimale multiple en Simplexe ?
Une solution optimale multiple se produit lorsque la valeur Cj-Zj (gain marginal) pour au moins une variable hors base est égale à zéro dans le tableau simplexe final. Cela signifie qu'il existe d'autres combinaisons de variables qui conduisent à la même valeur optimale de la fonction objectif. L'entreprise ou l'organisation peut alors choisir la solution qui offre d'autres avantages non inclus dans le modèle linéaire, comme la flexibilité ou la facilité de mise en œuvre.