Optimisation Correction TD: Algorithme du simplexe

Objectifs et prérequis du TP sur l'algorithme du simplexe

Objectifs

Ce TP sur l'algorithme du simplexe a pour but d'apprendre à résoudre des problèmes d'optimisation linéaire. À l'issue de ce TP, vous serez capable de :

• Mettre un problème sous forme standard.
• Construire et manipuler le tableau du simplexe.
• Identifier les variables entrantes et sortantes.
• Déterminer la solution optimale d'un problème d'optimisation.

Prérequis

Pour réaliser ce TP, il est nécessaire d'avoir des connaissances de base en programmation linéaire et en mathématiques. Vous aurez besoin des éléments suivants :

• Un accès à un logiciel de calcul (comme Excel ou un langage de programmation).
• Une compréhension des concepts de base tels que les variables de décision, les contraintes et la fonction objectif.

Résoudre un problème d'optimisation pas à pas

Nous allons résoudre un problème d'optimisation linéaire en utilisant l'algorithme du simplexe. Prenons l'exemple suivant :

max z = 1000x1 + 1500x2
sous les contraintes :
8x1 + 4x2 ≤ 160
6x2 ≤ 120
x1 ≤ 34
x2 ≤ 14
x1, x2 ≥ 0

Nous commençons par mettre le problème sous forme standard en introduisant des variables d'écart :

max z = 1000x1 + 1500x2
sous les contraintes :
8x1 + 4x2 + x3 = 160
6x2 + x4 = 120
x1 + x5 = 34
x2 + x6 = 14
x3, x4, x5, x6 ≥ 0

Étape 1 : Construction du tableau initial

Le tableau du simplexe est construit avec les variables de base et hors base :

|  z  |  x1  |  x2  |  x3  |  x4  |  x5  |  x6  |  b  |
|-----|------|------|------|------|------|------|-----|
|  1  | -1000| -1500|  0   |  0   |  0   |  0   |  0  |
|  0  |  8   |  4   |  1   |  0   |  0   |  0   | 160 |
|  0  |  0   |  6   |  0   |  1   |  0   |  0   | 120 |
|  0  |  1   |  0   |  0   |  0   |  1   |  0   | 34  |
|  0  |  0   |  1   |  0   |  0   |  0   |  1   | 14  |

Étape 2 : Choix des variables entrantes et sortantes

En utilisant la règle de Dantzig, nous choisissons la variable entrante. Ici, la variable x2 est la plus prometteuse :

ck = maxj∈{1,2} cj, ici k = 2 avec ck = 1500.

Pour la variable sortante, nous calculons :

mini={3,...,6} bi/alk

Nous trouvons que x6 sort de la base. Nous effectuons le pivotage :

L0 devient L0 − ckbl/alk
Ll devient Ll/alk
Lj pour j ≠ l devient Lj − alj/alk

Étape 3 : Nouveau tableau du simplexe

Après le pivotage, le nouveau tableau est :

|  z  |  x1  |  x2  |  x3  |  x4  |  x5  |  x6  |  b  |
|-----|------|------|------|------|------|------|-----|
|  1  | -1000| 0    |  0   |  0   |  0   |  0   | 21000|
|  0  | 8    | 0    |  1   |  0   |  0   |  0   | 160 |
|  0  | 0    | 6    |  0   |  1   |  0   |  0   | 120 |
|  0  | 1    | 0    |  0   |  0   |  1   |  0   | 34  |
|  0  | 0    | 1    |  0   |  0   |  0   |  1   | 14  |

Résultats attendus

Après avoir suivi les étapes ci-dessus, vous devriez obtenir une solution de base admissible. Pour notre exemple, la solution optimale est :

x1 = 0, x2 = 12, z = 21000

Les valeurs de la fonction économique montrent que nous avons maximisé notre objectif sous les contraintes données.

Erreurs fréquentes avec l'algorithme du simplexe

Lors de l'utilisation de l'algorithme du simplexe, plusieurs erreurs peuvent survenir :

• Choix incorrect des variables : Ne pas choisir la bonne variable entrante ou sortante peut mener à des résultats erronés.
• Erreurs de calcul : Les erreurs arithmétiques lors du pivotage peuvent fausser les résultats.
• Non respect des contraintes : Oublier de vérifier que les solutions respectent toutes les contraintes peut annuler la validité de la solution.

Questions fréquentes

Qu'est-ce que l'algorithme du simplexe ?

L'algorithme du simplexe est une méthode d'optimisation utilisée pour résoudre des problèmes de programmation linéaire. Il permet de maximiser ou minimiser une fonction objective sous des contraintes linéaires.

Comment savoir si une solution est optimale ?

Une solution est considérée comme optimale lorsque tous les coefficients de la fonction objective dans le tableau du simplexe sont négatifs ou nuls. Cela signifie qu'aucune amélioration n'est possible.

Quelles sont les étapes de l'algorithme du simplexe ?

Les étapes incluent la mise en forme standard du problème, la construction du tableau initial, le choix des variables entrantes et sortantes, et le pivotage jusqu'à obtenir une solution optimale.

Quels outils utiliser pour appliquer l'algorithme du simplexe ?

Vous pouvez utiliser des logiciels comme Excel, MATLAB, ou des langages de programmation comme Python pour implémenter l'algorithme du simplexe.