3eme annee finance recherche operationnelle serie 3 -Program
Télécharger PDFExercice n°1 : Résolution par l'algorithme du Simplex
Résoudre chacun des deux programmes linéaires suivants par l'algorithme du simplex :
Programme Linéaire 1
Maximiser Z = 4x₁ + 2x₂
Sous les contraintes :
- 3x₁ + 6x₂ ≤ 5
- 3x₁ + x₂ ≤ 15
- x₁ ≥ 0, x₂ ≥ 0
Programme Linéaire 2
Maximiser Z = x₁ + 9x₂ + 3x₃
Sous les contraintes :
- x₁ + 2x₂ + 3x₃ ≤ 9
- 3x₁ + 2x₂ + 2x₃ ≤ 15
- x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0
L'algorithme du simplex est une méthode itérative utilisée pour trouver la solution optimale des problèmes de programmation linéaire. Il navigue d'un sommet à l'autre de la région des solutions réalisables, en améliorant la valeur de la fonction objectif à chaque étape, jusqu'à atteindre l'optimum.
Exercice n°2 : Test d'optimalité de bases
Soit le programme linéaire suivant :
Maximiser Z = 3x₁ + 2x₂ + x₃
Sous les contraintes :
- x₁ + 2x₂ + 3x₃ ≤ 9
- x₁ + 2x₂ + 2x₃ ≤ 6
- x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0
Tester l'optimalité de chacune des trois bases suivantes : B₁ = {x₄, x₅, x₆}, B₂ = {x₃, x₅, x₆}, B₃ = {x₂, x₃, x₄}.
Que peut-on conclure pour chacune d'elles ?
Pour tester l'optimalité d'une base en programmation linéaire, on examine les coûts réduits (coefficients de la fonction objectif dans le dictionnaire du simplex) des variables hors base. Si tous ces coûts réduits sont négatifs ou nuls (pour un problème de maximisation), la base est optimale. Les variables x₄, x₅, x₆ sont généralement des variables d'écart introduites pour convertir les inégalités en égalités.
Exercice n°3 : Dictionnaire du Simplex Optimal
Soit le programme linéaire suivant :
Maximiser Z = 4x₁ + 9x₂ + 5x₃
Sous les contraintes :
- x₁ + 2x₂ + 2x₃ ≤ 150
- x₁ + x₂ + 3x₃ ≤ 100
- x₁ + 2x₂ + x₃ ≤ 160
- x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0
Sachant qu'à l'optimalité, on a obtenu :
Écrire le dictionnaire du simplex optimal du programme linéaire.
Retrouver le même dictionnaire en utilisant l'algorithme du simplex.
Un dictionnaire du simplex est une représentation algébrique des équations d'un problème de programmation linéaire, où les variables de base sont exprimées en fonction des variables hors base. Le dictionnaire optimal est celui où la fonction objectif ne peut plus être améliorée et où toutes les variables de base sont non négatives.
Note : Les informations spécifiques (les valeurs obtenues à l'optimalité) nécessaires pour écrire le dictionnaire ne sont pas fournies dans l'énoncé original. Pour cette raison, seule une explication conceptuelle est donnée.
Exercice n°4 : Programme Linéaire non Réalisable
Utiliser l'algorithme du simplex pour montrer que le programme linéaire suivant est non réalisable :
Minimiser Z = 2x₁ + 3x₂
Sous les contraintes :
- 2x₁ + 2x₂ ≥ 2
- x₁ + 2x₂ ≥ 4
- x₁ ≥ 0, x₂ ≥ 0
Un programme linéaire est dit non réalisable si aucun point ne satisfait simultanément toutes les contraintes. L'algorithme du simplex, souvent via la méthode en deux phases ou la méthode du Grand M, permet de détecter cette condition lorsqu'il est impossible de trouver une solution de base réalisable pour le problème modifié (avec variables artificielles).
Exercice n°5 : Programme Linéaire non Borné
Montrer que le programme linéaire suivant est non borné :
Maximiser Z = x₁ + 2x₂
Sous les contraintes :
- 5x₁ + 4x₂ ≤ 10
- x₁ - x₂ ≤ 5
- x₁ ≥ 0, x₂ ≥ 0
Un programme linéaire est non borné lorsque la valeur de la fonction objectif peut être augmentée (pour une maximisation) ou diminuée (pour une minimisation) indéfiniment sans violer aucune des contraintes. Dans l'algorithme du simplex, cela se manifeste par la détection d'une direction d'amélioration infinie, c'est-à-dire une colonne du tableau simplex dont tous les éléments sont négatifs ou nuls, alors que le coût réduit correspondant est positif.
Exercice n°6 : Solutions de Base, Dualité et Résolution
Soit le programme linéaire suivant :
Minimiser W = 8x₁ + 8x₂ + 5x₃
Sous les contraintes :
- 2x₁ + x₂ + 3x₃ ≥ ? (contrainte incomplète)
- x₁ + 2x₂ + 2x₃ ≥ ? (contrainte incomplète)
- x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0
Note : Les contraintes sont incomplètes car le membre de droite est manquant dans l'énoncé original. Pour résoudre cet exercice, ces valeurs seraient nécessaires.
Trouver toutes les solutions de base dont la variable x₁ est en base. Parmi ces solutions de base, quelles sont celles qui sont réalisables ?
Donner le programme dual.
Résoudre le programme dual.
Une solution de base est obtenue en fixant un certain nombre de variables à zéro (variables hors base) et en résolvant le système d'équations résultant pour les variables restantes (variables de base). Une solution de base réalisable est une solution de base où toutes les variables (de base et hors base) respectent les contraintes de non-négativité.
Le programme dual est une formulation alternative d'un problème de programmation linéaire. Il existe une relation forte entre le primal (le problème original) et son dual, notamment en termes de solutions optimales (théorèmes de dualité). Résoudre le dual peut parfois être plus simple que de résoudre le primal, et sa solution fournit des informations précieuses sur le problème original (par exemple, les prix duaux).
Foire Aux Questions (FAQ)
Qu'est-ce que l'algorithme du Simplex ?
L'algorithme du Simplex est une méthode mathématique itérative utilisée pour résoudre des problèmes de programmation linéaire. Il permet de trouver la meilleure solution (optimale) pour maximiser ou minimiser une fonction linéaire, sous un ensemble de contraintes linéaires. Il fonctionne en se déplaçant d'un point "coin" à l'autre de la région des solutions réalisables jusqu'à ce qu'il ne puisse plus améliorer la valeur de la fonction objectif.
Que signifie qu'un programme linéaire est "non réalisable" ?
Un programme linéaire est considéré comme "non réalisable" lorsqu'il n'existe aucune combinaison de valeurs pour les variables qui satisfasse simultanément toutes les contraintes données. En d'autres termes, la région des solutions réalisables est vide. L'algorithme du Simplex permet de détecter cette situation, généralement lors de l'application de la méthode en deux phases, si la phase 1 ne parvient pas à trouver une solution réalisable.
Dans quel cas un programme linéaire est-il "non borné" ?
Un programme linéaire est "non borné" si la valeur de la fonction objectif peut être augmentée (pour une maximisation) ou diminuée (pour une minimisation) à l'infini, sans jamais violer les contraintes. Cela signifie qu'il n'y a pas de limite supérieure (ou inférieure) à la fonction objectif dans la région des solutions réalisables. Le Simplex détecte un cas non borné lorsqu'il trouve une variable entrante dont la colonne dans le tableau du simplex ne contient aucune valeur positive, indiquant une direction d'amélioration infinie.