Examen recherche operationnelle juin 2010 -Programmation lin
Télécharger PDFIntroduction à la Recherche Opérationnelle
La recherche opérationnelle est une discipline qui utilise des méthodes scientifiques pour la prise de décision. Elle implique la modélisation de problèmes complexes, souvent sous forme de programmes linéaires, pour trouver des solutions optimales. Cet article explore des concepts fondamentaux à travers des exercices pratiques.
Exercice n° 1 : Programme Linéaire Non Réalisable
Utiliser l'algorithme du simplexe pour montrer que le programme linéaire suivant est non réalisable :
Min Z = -2x₁ + 3x₂
Sous les contraintes suivantes :
- -x₁ + 2x₂ ≤ 2
- 2x₁ - x₂ ≤ 3
- x₂ ≥ 4
- x₁ ≥ 0, x₂ ≥ 0
Explication : Un programme linéaire est qualifié de non réalisable si l'ensemble de ses contraintes est contradictoire, rendant impossible l'existence d'une solution qui satisfasse toutes les conditions simultanément. Cela signifie que la région réalisable, c'est-à-dire l'ensemble de toutes les solutions possibles, est vide.
Exercice n° 2 : Programme Linéaire Non Borné
Montrer que le programme linéaire suivant est non borné :
Max Z = x₁ + x₂
Sous les contraintes suivantes :
- -5x₁ + 4x₂ < 10
- x₂ ≤ 5
- x₁ ≥ 0, x₂ ≥ 0
Explication : Un programme linéaire est considéré comme non borné lorsque la valeur de sa fonction objectif peut être augmentée (pour une maximisation) ou diminuée (pour une minimisation) indéfiniment, sans jamais violer aucune des contraintes. Cela se produit lorsque la région réalisable s'étend à l'infini dans la direction d'amélioration de la fonction objectif.
Exercice n° 3 : Solutions de Base et Dualité
Soit le programme linéaire suivant :
Min W = 8x₁ + 8x₂ + 5x₃
Sous les contraintes suivantes :
- 2x₁ + x₂ + x₃ ≥ 3
- x₁ + 2x₂ + x₃ ≥ 2
- x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0
Questions :
- Trouver toutes les solutions de base dont la variable x₁ est en base. Parmi les solutions de base trouvées, quelles sont celles qui sont réalisables ?
- Donner le programme dual.
- Résoudre le programme dual.
Explication : Une solution de base est un point d'intersection de certaines contraintes du programme linéaire. Parmi ces solutions, celles qui respectent toutes les contraintes sont dites réalisables. Le programme dual est une formulation alternative du problème original (primal), essentielle pour l'analyse de sensibilité et offrant parfois une méthode de résolution plus simple ou des informations économiques sur les ressources.
Foire Aux Questions (FAQ)
Qu'est-ce qu'une solution de base en programmation linéaire ?
En programmation linéaire, une solution de base est un point obtenu en fixant certaines variables à zéro (variables hors base) et en résolvant le système d'équations pour les variables restantes (variables en base). Ces solutions correspondent aux sommets de la région réalisable si elles respectent toutes les contraintes.
Comment un programme linéaire peut-il être non réalisable ?
Un programme linéaire est non réalisable lorsque les contraintes imposées sont mutuellement exclusives. Par exemple, si l'on a simultanément les contraintes "x < 5" et "x > 10", il n'existe aucune valeur de x qui puisse satisfaire les deux. Cela mène à une région réalisable vide.
Pourquoi étudier le programme dual d'un problème ?
L'étude du programme dual est cruciale en recherche opérationnelle pour plusieurs raisons : elle fournit une borne inférieure (pour un problème de maximisation) ou supérieure (pour un problème de minimisation) à la valeur optimale du primal, offre des informations précieuses sur les prix marginaux des ressources (prix duaux), et peut parfois être plus facile à résoudre que le primal, surtout lorsque le primal a de nombreuses contraintes.