Examen recherche operationnelle session juin 2011 -Programma
Télécharger PDFExercice I
Trois produits sont fabriqués en passant par trois opérations différentes. Chaque opération nécessite un certain temps (en minutes) par unité de produit. Pour chaque opération, la capacité en temps par jour est limitée. D'autre part, on réalise un profit par unité de chaque produit, sachant que toute la production est vendue. Les données du problème sont résumées dans le tableau suivant :
| Temps par unité (minutes) | Capacité (minutes/jour) | |||
|---|---|---|---|---|
| Opération | Produit 1 | Produit 2 | Produit 3 | |
| 1 | 1 | 2 | 1 | 430 |
| 2 | 3 | 0 | 2 | 460 |
| 3 | 1 | 4 | 0 | 420 |
| Profit par unité | 3 | 2 | 5 | |
1) Citer trois exemples d'application de la recherche opérationnelle.
2) Définir la programmation linéaire.
3) Formuler le programme linéaire correspondant au tableau ci-dessus.
Exercice II
Soit le programme linéaire suivant :
Maximiser Z = x1 + 7x2 + 8x3
Sous contraintes :
- x1 + 2x2 + x3 ≤ 4
- 2x1 + 5x2 + x3 ≤ 8
- x1 + x2 + x3 ≤ 4
- x1, x2, x3 ≥ 0
1) Résoudre graphiquement ce programme linéaire. Expliquer.
2) Écrire ce programme linéaire sous la forme standard.
3) Trouver une solution réalisable de base initiale et déterminer les variables de base et les variables hors base.
4) Quelle est la règle de choix de la variable entrante ?
5) Résoudre ce programme linéaire en utilisant la méthode du dictionnaire du simplexe. Quelle est la solution optimale ? Expliquer.
6) Résoudre ce programme linéaire en utilisant la méthode du tableau du simplexe.
Correction Exercice I
1) Exemples d'application de la recherche opérationnelle :
- Production : Problèmes de choix des combinaisons de production, gestion des stocks, planification des capacités.
- Distribution : Localisation géographique optimale d'usines et d'entrepôts en tenant compte des sources d'approvisionnement et des points de vente, optimisation des tournées de livraison.
- Gestion financière : Planification des investissements, choix des crédits et des emprunts, optimisation de la composition d'un portefeuille.
2) Définition de la programmation linéaire :
La programmation linéaire est une technique d'optimisation mathématique utilisée pour déterminer la meilleure allocation de ressources limitées. Elle a pour objet la maximisation ou la minimisation d'une fonction linéaire, appelée fonction objectif, sous un ensemble de contraintes représentées par des inégalités ou des égalités linéaires. Les variables de décision doivent être non-négatives.
3) Formulation du programme linéaire :
Soient x1, x2, x3 les quantités produites des produits 1, 2 et 3 respectivement.
Fonction objectif (Maximisation du profit) :
Maximiser Z = 3x1 + 2x2 + 5x3
Sous contraintes (capacités des opérations) :
- Opération 1 : x1 + 2x2 + x3 ≤ 430
- Opération 2 : 3x1 + 2x3 ≤ 460
- Opération 3 : x1 + 4x2 ≤ 420
Contraintes de non-négativité :
- x1, x2, x3 ≥ 0
Correction Exercice II
1) Résolution graphique du programme linéaire :
Le programme linéaire contient trois variables de décision (x1, x2, x3). Une résolution graphique n'est pas possible ou du moins pas pratique, car elle nécessiterait une représentation dans un espace à trois dimensions, ce qui est difficile à visualiser et à analyser manuellement. La méthode graphique est généralement applicable pour des problèmes avec seulement deux variables de décision.
2) Écriture sous forme standard :
Pour écrire le programme linéaire sous forme standard, nous introduisons des variables d'écart (slack variables) s1, s2, s3 pour convertir les inégalités en égalités. Ces variables représentent la ressource non utilisée pour chaque contrainte.
Fonction objectif :
Maximiser Z = x1 + 7x2 + 8x3 + 0s1 + 0s2 + 0s3
Sous contraintes :
- x1 + 2x2 + x3 + s1 = 4
- 2x1 + 5x2 + x3 + s2 = 8
- x1 + x2 + x3 + s3 = 4
Contraintes de non-négativité :
- x1, x2, x3, s1, s2, s3 ≥ 0
3) Solution réalisable de base initiale :
La solution réalisable de base initiale est obtenue en posant les variables de décision (originales) à zéro. Les variables d'écart deviennent alors les variables de base.
- Variables hors base (VHB) : x1 = 0, x2 = 0, x3 = 0
- Variables de base (VB) :
- s1 = 4 (car x1 + 2x2 + x3 + s1 = 4 devient 0 + 0 + 0 + s1 = 4)
- s2 = 8 (car 2x1 + 5x2 + x3 + s2 = 8 devient 0 + 0 + 0 + s2 = 8)
- s3 = 4 (car x1 + x2 + x3 + s3 = 4 devient 0 + 0 + 0 + s3 = 4)
La valeur de la fonction objectif Z pour cette solution initiale est Z = 0 + 7(0) + 8(0) = 0.
4) Règle de choix de la variable entrante :
Dans la méthode du simplexe pour la maximisation, la variable entrante est celle qui correspond au coefficient le plus positif dans la fonction objectif (ou le coefficient le plus négatif dans la ligne Z si la fonction objectif est réécrite comme Z - CTx = 0). Ce choix vise à augmenter la valeur de la fonction objectif le plus rapidement possible par unité de cette variable.
5) Résolution par la méthode du dictionnaire du simplexe :
La méthode du dictionnaire du simplexe consiste à exprimer les variables de base en fonction des variables hors base. L'objectif est d'itérer en choisissant une variable entrante et une variable sortante jusqu'à ce que tous les coefficients de la fonction objectif soient négatifs ou nuls pour un problème de maximisation.
Dictionnaire initial :
- s1 = 4 - x1 - 2x2 - x3
- s2 = 8 - 2x1 - 5x2 - x3
- s3 = 4 - x1 - x2 - x3
- Z = x1 + 7x2 + 8x3
Choix de la variable entrante : x3 (car son coefficient est le plus élevé dans Z : 8).
Choix de la variable sortante (règle du ratio minimum) :
- Pour s1 : 4/1 = 4
- Pour s2 : 8/1 = 8
- Pour s3 : 4/1 = 4
Il y a une égalité entre s1 et s3. On peut choisir arbitrairement s3 comme variable sortante.
Pivoting : Exprimer x3 en fonction de s3 et des autres variables à partir de la ligne de s3, puis substituer dans les autres équations et la fonction objectif.
- De s3 = 4 - x1 - x2 - x3, on tire x3 = 4 - x1 - x2 - s3.
Dictionnaire après le premier pivot (x3 entre, s3 sort) :
- s1 = 4 - x1 - 2x2 - (4 - x1 - x2 - s3) = -x2 + s3
- s2 = 8 - 2x1 - 5x2 - (4 - x1 - x2 - s3) = 4 - x1 - 4x2 + s3
- x3 = 4 - x1 - x2 - s3
- Z = x1 + 7x2 + 8(4 - x1 - x2 - s3) = 32 - 7x1 - x2 - 8s3
Vérification de l'optimalité : Tous les coefficients des variables hors base (x1, x2, s3) dans l'expression de Z sont négatifs (-7, -1, -8). Cela signifie que la solution actuelle est optimale.
Solution optimale :
- x1 = 0
- x2 = 0
- x3 = 4 (valeur trouvée dans le dictionnaire pour x3 lorsque les VHB sont à zéro)
- s1 = 0 (valeur trouvée dans le dictionnaire pour s1 lorsque les VHB sont à zéro)
- s2 = 4 (valeur trouvée dans le dictionnaire pour s2 lorsque les VHB sont à zéro)
- s3 = 0 (variable hors base)
La valeur maximale de la fonction objectif est Z = 32.
6) Résolution par la méthode du tableau du simplexe :
La méthode du tableau du simplexe est une approche tabulaire et systématique pour appliquer les mêmes principes que la méthode du dictionnaire. On représente les coefficients des variables, les côtés droits des contraintes et les coefficients de la fonction objectif dans un tableau.
Tableau initial (avec variables d'écart s1, s2, s3) :
| Base | x1 | x2 | x3 | s1 | s2 | s3 | RHS (b) |
|---|---|---|---|---|---|---|---|
| s1 | 1 | 2 | 1 | 1 | 0 | 0 | 4 |
| s2 | 2 | 5 | 1 | 0 | 1 | 0 | 8 |
| s3 | 1 | 1 | 1 | 0 | 0 | 1 | 4 |
| Z | -1 | -7 | -8 | 0 | 0 | 0 | 0 |
(Note: La ligne Z est exprimée comme Z - (x1 + 7x2 + 8x3) = 0 pour le tableau, donc les coefficients des variables de décision sont négatifs pour un problème de maximisation.)
Choix de la variable entrante : x3 (coefficient le plus négatif dans la ligne Z : -8).
Choix de la variable sortante (ratio minimum) :
- s1 : 4/1 = 4
- s2 : 8/1 = 8
- s3 : 4/1 = 4
Pivot arbitraire sur s3 (nous choisissons s3 pour être cohérent avec l'exemple du dictionnaire). L'élément pivot est 1 (intersection de la ligne s3 et de la colonne x3).
Tableau après pivot (x3 entre, s3 sort) :
| Base | x1 | x2 | x3 | s1 | s2 | s3 | RHS (b) |
|---|---|---|---|---|---|---|---|
| s1 | 0 | 1 | 0 | 1 | 0 | -1 | 0 |
| s2 | 1 | 4 | 0 | 0 | 1 | -1 | 4 |
| x3 | 1 | 1 | 1 | 0 | 0 | 1 | 4 |
| Z | 7 | 1 | 0 | 0 | 0 | 8 | 32 |
Vérification de l'optimalité : Tous les coefficients de la ligne Z sont positifs ou nuls. La solution est optimale.
Solution optimale :
- x1 = 0 (variable hors base)
- x2 = 0 (variable hors base)
- x3 = 4 (valeur de RHS pour la ligne x3)
- s1 = 0 (valeur de RHS pour la ligne s1)
- s2 = 4 (valeur de RHS pour la ligne s2)
- s3 = 0 (variable hors base)
La valeur maximale de la fonction objectif est Z = 32.
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, notamment des modèles mathématiques, pour aider à la prise de décision et à l'optimisation des systèmes complexes. Elle vise à trouver la meilleure solution possible pour des problèmes de gestion et d'allocation de ressources limitées.
Quand utilise-t-on la méthode graphique pour résoudre un programme linéaire ?
La méthode graphique est principalement utilisée pour résoudre des programmes linéaires comportant seulement deux variables de décision. Elle permet de visualiser l'espace des solutions possibles (région admissible) et d'identifier graphiquement le point optimal qui maximise ou minimise la fonction objectif. Pour trois variables ou plus, elle devient impraticable.
Quel est le principe de base de la méthode du simplexe ?
Le principe de base de la méthode du simplexe est de partir d'une solution réalisable de base initiale (généralement le point d'origine, si possible) et d'améliorer itérativement cette solution en se déplaçant d'un sommet à l'autre de la région admissible. À chaque étape (pivot), une variable non-basique entre dans la base et une variable basique en sort, jusqu'à ce qu'une solution optimale soit trouvée, où aucune amélioration supplémentaire de la fonction objectif n'est possible.