Dans le cadre du cours de recherche opérationnelle, nous avons exploré un

chapitre intitulé "PROGRAMMATION LINÉAIRE". Nous avons défini la

programmation linéaire comme la recherche de la solution la plus optimale à un
problème soumis à plusieurs conditions, appelées "contraintes". Pour mener à
bien cette recherche, nous avons identifié trois méthodes :
 La méthode graphique
 La méthode par dénombrement
 La méthode du simplexe
Les deux premières méthodes ont été étudiées en classe. Aujourd'hui, nous avons
le plaisir de vous présenter la troisième méthode, "LA MÉTHODE DU SIMPLEXE".
O. Introduction :
La méthode du simplexe est une technique d'optimisation utilisée pour résoudre
des problèmes de programmation linéaire, c'est-à-dire des problèmes où l'objectif
est de maximiser ou minimiser une fonction linéaire sous des contraintes
également linéaires, développée par George Dantzig dans les années 1940, est
largement utilisée en raison de son efficacité et de sa capacité à résoudre des
problèmes complexes.
1. Contexte et Objectif :
• Dans un environnement où les ressources sont limitées, il est essentiel pour les
entreprises de prendre des décisions éclairées sur l'allocation de ces ressources :
On cherche à optimiser (maximiser ou minimiser) une fonction objective Z = c₁x₁ +
c₂x₂ + ... + cₙxₙ sous des contraintes de la forme a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁ , où
xᵢ ≥ 0 . La méthode du simplexe permet d’aborder ces problèmes de manière
structurée.
• Exemple d'application : Allocation de ressources, planification de la
production, transport, etc.
2. Formulation du Problème :
• Variables Décisionnelles : x₁, x₂, ..., xₙ
• Fonction Objective : Maximiser ou minimiser Z
• Contraintes : Ensemble de contraintes linéaires
3. Étapes de la Méthode Simplexe :
1. Formulation Standard :
• Convertir toutes les inégalités en égalités en ajoutant des variables d'écart
(slack variables) pour les contraintes de type « ≤ ».
• S'assurer que toutes les variables sont non négatives.
2. Tableau Simplexe Initial :
• Construire un tableau simplexe qui résume les coefficients de la fonction
objective et des contraintes.
3. Sélection de la Variable Entrante :
• Identifier la variable avec le coefficient le plus élevé dans la ligne de la
fonction objective (pour maximiser) ; c'est la variable qui entrera dans la solution.
4. Sélection de la Variable Sortante :
• Déterminer quelle variable sortira en utilisant le critère du rapport minimum
(ratio test) pour conserver la non-négativité des variables.
5. Mise à Jour du Tableau :
• Effectuer des opérations sur les lignes du tableau pour mettre à jour les
valeurs des variables et recalculer les coefficients.
6. Itération :
• Répéter les étapes 3 à 5 jusqu'à ce qu'il n'y ait plus de coefficients positifs
dans la ligne de la fonction objective (solution optimale atteinte).
4. Interprétation des Résultats :
• Une fois que la solution optimale est atteinte, les valeurs des variables
décisionnelles peuvent être interprétées pour prendre des décisions basées sur le
modèle.
5. Limitations :
• La méthode simplexe ne fonctionne pas pour des problèmes non linéaires.
 • Elle peut rencontrer des problèmes de dégénérescence, conduisant à des
cycles infinis, bien que cela soit rare avec les techniques modernes.
Conclusion :
La méthode du simplexe est un outil puissant pour résoudre des problèmes
d'optimisation linéaire, largement utilisé dans divers domaines tels que
l'économie, l'ingénierie et la logistique. Sa capacité à gérer des problèmes
complexes avec plusieurs contraintes et variables en fait un choix privilégié pour
les analystes et les chercheurs.
Un Énoncé du Problème pour une bonne compréhension
Une entreprise fabrique deux produits, A et B. Chaque produit nécessite un
certain temps de travail sur deux machines, M1 et M2. Les données sont les
suivantes :
• Temps de production par unité : Produit A : 2 heures sur M1, 1 heure sur M2
Produit B : 1 heure sur M1, 2 heures sur M2
• Capacité disponible : Machine M1 : 8 heures par jour
Machine M2 : 6 heures par jour
• Profit par unité : Produit A : 3 €
Produit B : 4 €
Objectif : Maximiser le profit total.
Formulation du Problème
1. Variables Décisionnelles :
• x₁ = nombre d'unités produites de produit A
• x₂ = nombre d'unités produites de produit B
2. Fonction Objective : Z = 3x₁ + 4x₂ (à maximiser)
3. Contraintes :
• Pour la machine M1 : 2x₁ + x₂ ≤ 8
• Pour la machine M2 : x₁ + 2x₂ ≤ 6
• Non-négativité : x₁ ≥ 0, x₂ ≥ 0

Résolution par la Méthode du Simplexe

Étape 1 : Formulation Standard
Nous ajoutons des variables d'écart s₁ et s₂ pour convertir les inégalités en
égalités :
• Pour M1 : 2x₁ + x₂ + s₁ = 8
• Pour M2 : x₁ + 2x₂ + s₂ = 6
Étape 2 : Tableau Simplexe Initial
Base x₁ x₂ s₁ s₂ solution
s₁ 2 1 1 0 8
s₂ 1 2 0 1 6
Z -3 -4 0 0 0

Étape 3 : Sélection de la Variable Entrante

Le coefficient le plus négatif dans la ligne de la fonction objective est -4 (pour x₂ ).
Donc, x₂ entre dans la base.
Étape 4 : Sélection de la Variable Sortante
Calculons les ratios :
• Pour s₁ : 8/1 = 8
• Pour s₂ : 6/2 = 3
La variable sortante est donc s₂ .
Étape 5 : Mise à Jour du Tableau
Nous mettons à jour le tableau en utilisant la méthode du pivot :
Nouveau tableau :
Base x₁ x₂ s₁ s₂ Solution
s₁ 0 -1 1 -0 .5 4
x₂ 0 .5 1 0 0 .5 3
Z -3 0 0 2 12

Étape 6 : Répéter jusqu'à l'Optimalité

Nous répétons le processus : Sélectionnons la variable entrante (ici, x₁ ) et
déterminons la variable sortante (ici, s₁ ), puis mettons à jour le tableau.
Nouveau tableau :
Base x₁ x₂ s₁ s₂ Solution
x₁ 1 -2 2 -1 4
x₂ 0 1 -0 .5 0 .5 3
Z 0 0 -6 -3 24

Solution Finale
La solution optimale est atteinte lorsque tous les coefficients de la ligne Z sont
non négatifs. La solution optimale est :
• Produire 4 unités de produit A ( x₁ = 4 )
• Produire 3 unités de produit B ( x₂ = 3 )
Le profit maximal est donc : Z = 3(4) + 4(3) = 12 +12 = 24