Exercices programmation lineaire g1 gse g3 -Programmation li

Télécharger PDF

Exercices de Programmation Linéaire et Méthode du Simplexe

Cet article présente une série d'exercices, souvent rencontrés dans des cours d'optimisation à l'École Nationale des Sciences Appliquées de Fès, axés sur la programmation linéaire. Il couvre des aspects fondamentaux tels que la mise en forme standard, la représentation graphique des ensembles-solutions, ainsi que l'application des méthodes du simplexe et des deux phases pour résoudre divers problèmes d'optimisation.

Exercice 1 : Minimisation et Forme Standard d'un Problème Linéaire

Soit le problème de minimisation suivant :

Minimiser : x1 + 2x2 + x3
Sous contraintes :
- x1 + x2 - x3 ≥ 2
- x1 - x2 + x3 = 1
- x1 + x2 + x3 ≥ 2
Conditions sur les variables :
- x1, x2 ≥ 0
- x3 quelconque

Questions :

Donner la forme standard du problème.
Représenter graphiquement l'ensemble-solution.
Déterminer les coordonnées des points-sommets de l'ensemble solution.

La forme standard d'un problème de programmation linéaire est une représentation canonique où l'objectif est une minimisation ou une maximisation, toutes les contraintes sont des égalités (hors contraintes de non-négativité), et toutes les variables de décision sont non négatives. Les variables libres (quelconques) et les inégalités doivent être converties pour atteindre cette forme.

Exercice 2 : Résolution par la Méthode du Simplexe

Résoudre à l'aide de la méthode du simplexe le problème linéaire suivant :

Maximiser : 5x1 + 11x2
Sous contraintes :
- x1 + x2 ≤ 20
- 3x1 + 15x2 ≤ 225
- 5x1 + 10x2 ≤ 160
Conditions sur les variables :
- x1, x2 ≥ 0

La méthode du simplexe est un algorithme itératif largement utilisé pour résoudre des problèmes de programmation linéaire. Elle opère en passant d'un sommet à l'autre du polyèdre des solutions réalisables, en améliorant la valeur de la fonction objectif à chaque étape, jusqu'à l'atteinte d'une solution optimale.

Exercice 3 : Application de la Méthode des Deux Phases

Appliquer la méthode des deux phases du simplexe pour résoudre chacun des problèmes suivants :

Problème (P1)

Minimiser : 6x1 + 6x2 + 5x3
Sous contraintes :
- 2x1 + 3x2 + x3 ≥ 28
- x1 + x2 + 2x3 ≥ 14
- x1 + 4x2 + 2x3 ≥ 32
Conditions sur les variables :
- x1, x2, x3 ≥ 0

Problème (P2)

Maximiser : 6x1 + 3x2 + 4x4
Sous contraintes :
- x1 + x2 + x3 + x4 ≤ 30
- 3x1 + 6x2 + x3 - 2x4 ≤ 20
- x2 ≥ 4
Conditions sur les variables :
- x1, x2, x3, x4 ≥ 0

La méthode des deux phases est essentielle lorsque le problème de programmation linéaire ne possède pas de solution de base réalisable évidente pour initialiser la méthode du simplexe. La première phase consiste à résoudre un problème auxiliaire pour trouver une solution de base réalisable, tandis que la seconde phase optimise la fonction objectif originale en partant de cette solution.

Exercice 4 : Vérification d'Inexistence de Solution Réalisable

Appliquer la méthode des deux phases du simplexe pour vérifier que le problème (P) n'admet pas de solution réalisable :

Problème (P)

Minimiser : -5x1 - 4x2 - 7x3
Sous contraintes :
- 3x1 + 8x2 + 2x3 ≤ 40
- 9x1 + 5x2 + 7x3 ≤ 35
- 7x1 + 3x2 + 3x3 ≥ 51
Conditions sur les variables :
- x1, x2, x3 ≥ 0

L'absence de solution réalisable signifie qu'il est impossible de trouver un ensemble de valeurs pour les variables qui satisfasse simultanément toutes les contraintes du problème. La méthode des deux phases est particulièrement utile pour détecter ce scénario si la phase 1 ne peut atteindre une valeur nulle pour sa fonction objectif auxiliaire.

Foire Aux Questions (FAQ) sur la Programmation Linéaire

Qu'est-ce que la programmation linéaire ?: La programmation linéaire est une technique mathématique d'optimisation utilisée pour trouver la meilleure solution (maximisation ou minimisation) pour un problème où les fonctions objectif et les contraintes sont toutes linéaires. Elle est couramment appliquée dans des domaines comme la gestion de la production, la logistique et la finance.
Pourquoi doit-on convertir un problème en forme standard pour le simplexe ?: La conversion en forme standard est nécessaire car l'algorithme du simplexe est conçu pour fonctionner spécifiquement avec des contraintes d'égalité et des variables non négatives. Cela uniformise la structure des problèmes, facilitant l'application systématique de l'algorithme pour trouver la solution optimale.
Quelle est la différence entre la méthode du simplexe et la méthode des deux phases du simplexe ?: La méthode du simplexe est l'algorithme d'optimisation principal. La méthode des deux phases du simplexe est une extension utilisée lorsque le problème n'a pas de solution de base réalisable initiale évidente. La première phase crée et résout un problème auxiliaire pour trouver une solution de base réalisable, qui est ensuite utilisée comme point de départ pour la deuxième phase, où la méthode du simplexe classique est appliquée à la fonction objectif originale.