3eme annee finance recherche operationnelle juin 2012 -Progr
Télécharger PDFUniversité de Tunis, École Supérieure des Sciences Économiques et Commerciales de Tunis
3ème Année Finance
Année Universitaire 2011/2012
Recherche Opérationnelle — Juin 2012 (session principale)
Exercice 1
Montrer que le programme linéaire suivant est non borné :
Maximiser Z = x1 + x2
Sous les contraintes :
- -5x1 + 4x2 ≤ 10
- x2 ≤ 5
- x1, x2 ≥ 0 (contraintes implicites pour un programme linéaire standard)
Exercice 2
Soit le programme linéaire suivant :
Maximiser Z = x1 + 9x2 + x3
Sous les contraintes :
- x1 + 2x2 + 3x3 ≤ 9
- 3x1 + 2x2 + 2x3 ≤ 15
- x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
- Résoudre ce programme linéaire par la méthode du dictionnaire du simplexe.
- Retrouver le même résultat en utilisant l'algorithme du simplexe.
Exercice 3
Soit le programme linéaire suivant :
Maximiser Z = 3x1 + x2 + 2x3
Sous les contraintes :
- x1 - x2 + x3 ≤ 3
- 3x1 + 2x2 + x3 ≤ 9
- 2x1 + x2 + 2x3 ≤ 6
- x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
Tester l'optimalité de chacune des trois bases suivantes :
- B1 = {4, 5, 6}
- B2 = {3, 5, 6}
- B3 = {2, 3, 4}
Que peut-on conclure pour chacune d'elles ?
Exercice 4
Soit le programme linéaire suivant :
Maximiser Z = 4x1 + 9x2 + 5x3
Sous les contraintes :
- x1 + 2x2 + 2x3 ≤ 150
- x1 + x2 + 2x3 ≥ 100
- x1 + 2x2 + x3 ≤ 160
- x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
Résoudre ce programme linéaire en utilisant l'algorithme du simplexe.
Correction de l'Examen de Recherche Opérationnelle - Session Principale 2012
Correction Exercice 1
L'ensemble des solutions réalisables est infini de points, ce qui implique que le Programme Linéaire (PL) est non borné.
Correction Exercice 2
Pour résoudre ce programme linéaire par la méthode du simplexe (dictionnaire ou algorithme), nous ajoutons des variables d'écart (slack variables) pour transformer les inégalités en égalités.
Programme après ajout des variables d'écart :
Maximiser Z = x1 + 9x2 + x3 + 0x4 + 0x5
Sous les contraintes :
- x1 + 2x2 + 3x3 + x4 = 9
- 3x1 + 2x2 + 2x3 + x5 = 15
- x1, x2, x3, x4, x5 ≥ 0
Solution initiale de base :
x1 = 0, x2 = 0, x3 = 0
x4 = 9, x5 = 15
Z = 0
Les étapes de l'algorithme du simplexe impliquent le choix de la variable entrante (celle avec le coefficient le plus positif dans la fonction objectif) et de la variable sortante (déterminée par le ratio minimal).
Après plusieurs itérations, la solution optimale est atteinte.
Solution optimale trouvée :
x1 = 0, x2 = 4.5, x3 = 0
La valeur optimale de Z est : Z = 1(0) + 9(4.5) + 1(0) = 40.5 (ou 81/2).
Correction Exercice 3
Nous testons l'optimalité de chaque base en vérifiant la faisabilité et l'optimalité (coefficients des variables hors base dans la ligne Z).
Base B1 = {4, 5, 6}
Vérification des contraintes :
Z = 12 + 5 + 12 = 29 (Cette somme semble représenter une combinaison des coefficients ou valeurs, mais n'est pas directement la valeur de Z du programme initial).
4 - 5 + 6 ≤ 3 (Non vérifié)
Conclusion : La base B1 n'est pas réalisable.
Base B2 = {3, 5, 6}
Vérification des contraintes :
Z = 3 + 5 + 12 = 26 (Même remarque que pour B1)
3 - 5 + 6 ≤ 3 (Non vérifié)
Conclusion : La base B2 n'est pas réalisable.
Base B3 = {2, 3, 4}
Vérification des contraintes :
Z = 6 + 3 + 8 = 17 (Même remarque que pour B1)
2 - 3 + 4 ≤ 3 (Vérifié)
6 + 6 + 4 ≤ 9 (Non vérifié)
Conclusion : La base B3 n'est pas réalisable.
En résumé, aucune des bases proposées n'est réalisable ou optimale pour le programme linéaire donné.
Correction Exercice 4
Pour résoudre ce programme linéaire, nous utilisons l'algorithme du simplexe avec la méthode du Grand M (M-méthode) en raison de la contrainte de type "supérieur ou égal à" (x1 + x2 + 2x3 ≥ 100), qui nécessite l'introduction d'une variable artificielle.
Programme après ajout des variables d'écart (x4, x6), de surplus (x5) et artificielle (a1) :
Maximiser Z = 4x1 + 9x2 + 5x3 + 0x4 + 0x5 + 0x6 - Ma1
Sous les contraintes :
- x1 + 2x2 + 2x3 + x4 = 150
- x1 + x2 + 2x3 - x5 + a1 = 100
- x1 + 2x2 + x3 + x6 = 160
- x1, x2, x3, x4, x5, x6, a1 ≥ 0
Après application de l'algorithme du simplexe sur plusieurs tableaux, les itérations mènent à la solution optimale.
Solution optimale trouvée :
x1 = 50, x2 = 50, x3 = 0
La valeur optimale de Z est : Z = 4(50) + 9(50) + 5(0) = 200 + 450 = 650.
Questions Fréquentes (FAQ)
Qu'est-ce qu'un programme linéaire non borné ?
Un programme linéaire est dit non borné si la fonction objectif peut prendre une valeur arbitrairement grande (pour une maximisation) ou arbitrairement petite (pour une minimisation), tout en respectant les contraintes du problème. Cela se produit lorsque la région des solutions réalisables est ouverte dans la direction d'amélioration de la fonction objectif.
Quand utilise-t-on la méthode du Grand M dans l'algorithme du simplexe ?
La méthode du Grand M est utilisée lorsque le programme linéaire contient des contraintes de type "supérieur ou égal à" (≥) ou des contraintes d'égalité. Ces types de contraintes ne permettent pas d'identifier directement une solution de base réalisable initiale, nécessitant l'introduction de variables artificielles. Le "Grand M" est une pénalité très élevée ajoutée à la fonction objectif pour forcer ces variables artificielles à être nulles dans la solution optimale.
Quelle est l'importance de vérifier la faisabilité et l'optimalité des bases en programmation linéaire ?
La vérification de la faisabilité assure que la solution proposée respecte toutes les contraintes du problème (contraintes structurelles et de non-négativité). L'optimalité, quant à elle, garantit que la solution est la meilleure possible pour la fonction objectif donnée (maximisation ou minimisation). Un programme linéaire doit être à la fois réalisable et optimal pour être une solution valide et la meilleure.