SEANCE 7

CHAPITRE 5 : LA THEORIE DE LA METHODE DU SIMPLEXE

Objectif de la séance : Comprendre la théorie de la méthode du simplexe

Contenu :
5.1 Fondements de la méthode du simplexe
5.2 La méthode du simplexe sous forme de matrice
5.3 Un aperçu fondamental
5.4 La méthode du simplexe révisée
5.5 Conclusions
Exercices d’application
Pour comprendre plus :
Plusieurs recherches documentaires peuvent se faire en ligne et à la bibliothèque (voir
bibliographie).

Le chapitre 4 avait présenté les mécanismes de base de la méthode du simplexe. Nous allons
maintenant approfondir un peu plus cet algorithme en examinant une partie de sa théorie sous-
jacente. La première section développe les propriétés géométriques et algébriques générales qui
forment le fondement de la méthode du simplexe. Nous décrivons ensuite la forme matricielle de
la méthode du simplexe, qui simplifie considérablement la procédure pour la mise en œuvre par
ordinateur. Nous utilisons ensuite cette forme matricielle pour présenter un aperçu fondamental
d'une propriété de la méthode du simplexe qui nous permet de déduire comment les modifications
apportées au modèle d'origine sont reportées dans le tableau du simplexe final. Cette idée fournira
la clé des sujets importants du Chap. 6 (théorie de la dualité).
5.1 Fondements de la méthode du simplexe
Le chapitre 4 a introduit les solutions possibles en coin et leur rôle clé dans la méthode du simplexe.
Ces concepts géométriques étaient liés à l'algèbre de la méthode du simplexe. Cependant, tout cela
a été fait dans le contexte d’un problème qui n'avait que deux variables de décision et a donc une
interprétation géométrique simple. Comment ces concepts se généralisent-ils à des dimensions
supérieures quand nous traitons de plus gros problèmes ? Nous abordons cette question dans cette
section. Nous commençons par introduire une terminologie de base pour tout problème de
programmation linéaire avec 𝑛 variables de décision. Ce faisant, vous trouverez peut-être utile de
vous reporter à la Fig. 5.1 (qui répète la Fig. 4.1) pour interpréter ces définitions en deux dimensions
(𝑛 = 2).
5.1.1. Terminologie
Il peut sembler intuitivement évident que les solutions optimales à tout problème de programmation
linéaire doivent se situer sur la bordure de la région réalisable et qu’il s’agit en fait d’une propriété
générale. Puisque la notion de bordure est un concept géométrique, nos définitions initiales
clarifient comment la bordure de la région réalisable est identifiée algébriquement.
L’équation limitant la bordure pour toute contraintes est obtenue en remplaçant les signes ≤, =
, 𝑜𝑢 ≥ par un signe d’égalité (=).

Figure 5.1 : Bordures des contraintes, équations qui délimitent les bordures et les points en coin

Par conséquent, la forme d'une équation de frontière de contrainte est 𝑎𝑖1 𝑥1 + 𝑎𝑖2𝑥2 + ⋯ +
𝑎𝑖𝑛 𝑥1𝑛 = 𝑏𝑖 pour les contraintes fonctionnelles et 𝑥𝑗 = 0 pour les contraintes de non-négativité.
Chacune de ces équations définit une forme géométrique « plate » (appelée hyperplan) dans un
espace à 𝑛 dimensions, analogue à la ligne dans un espace à deux dimensions et le plan dans un
espace à trois dimensions. Cet hyperplan constitue les limites de contrainte pour les contraintes
correspondantes. Lorsque la contrainte a un signe ≤ ou un signe ≥, cette limite de contrainte sépare
les points qui satisfont la contrainte (tous les points d’un côté jusqu’à la limite de contrainte incluse)
à partir des points qui violent la contrainte (tous ceux situés de l’autre côté de la limite de
contrainte). Lorsque la contrainte a un signe = , seuls les points de la limite de la contrainte satisfont
à la contrainte.
Dans notre problème utilisé comme exemple pédagogique (Fig. 5.1), nous avons au total 5
équations dont 3 qui sont fonctionnelles et 2 qui sont des contraintes de non-négativité. Puisque
nous sommes dans la dimension 𝑛 = 2 les bordures ou les limites des cinq contraintes sont cinq
lignes comme dans la figure 5.1. Géométriquement, tout point de la limite de la région réalisable
se trouve sur un ou plusieurs des hyperplans définis par les équations aux limites de contrainte
respectives. Ainsi, sur la Fig. 5.1, la limite est constituée des cinq segments de ligne les plus
sombres.
Une solution en coin est une solution réalisable qui n’est pas sur un segment qui connecte deux
autres solutions réalisables. On peut vérifier sur la figure 5.1 que tous les points en coin sont des
solutions de systèmes d’équations. On pourrait aussi remarquer que ce ne sont pas toutes les
solutions en coin qui sont réalisables.
Nous avons également du point de vue géométrique fait usage de la notion de solution adjacente
dans la résolution des problèmes par la méthode du simplexe. Alors que la notion est simple en
deux dimensions, elle peut devenir complexe lorsque la dimension devient supérieure à deux. Le
segment de ligne plus sombre de la figure 5.2 décrit le chemin de la méthode du simplexe sur une
itération typique. Le point (2, 4, 3) est la solution actuelle pour commencer l'itération, et le point
(4, 2, 4) sera la nouvelle solution à la fin de l'itération. Le point (2, 4, 3) se trouve à l'intersection
des limites de contrainte 𝑥2 = 4, 𝑥1 + 𝑥2 = 6, 𝑒𝑡 − 𝑥1 + 2𝑥3 = 4 de sorte que ces trois équations
sont les équations qui définissent cette solution en coin.

Figure 5.2 : Région réalisable dans un problème de programmation linéaire avec trois variables
5.1.2. Les propriétés des solutions en coin réalisables
Nous nous concentrons maintenant sur trois propriétés majeures des solutions en coin qui
s’appliquent à tout problème de programmation linéaire présentant des solutions réalisables et une
région réalisable délimitée (ou bornée).
Propriété 1 : a) S'il existe exactement une solution optimale, il doit s'agir d'une solution en coin
réalisable. (b) S'il existe plusieurs solutions optimales (et une région réalisable bornée), au moins
deux doivent être des solutions en coin adjacentes.
La preuve de la partie (a) de cette propriété peut être faite par contradiction.
Propriété 2 : il n'y a qu'un nombre fini de solutions en coin réalisable.
Propriété 3 : Si une solution réalisable en coin n'a pas de solution adjacente qui soit meilleure
(telle que mesurée par Z), il n'y a pas de meilleure solution nulle part. Par conséquent, une telle
solution est garantie comme étant une solution optimale (par la propriété 1), en supposant
seulement que le problème possède au moins une solution optimale (garantie si le problème
possède des solutions réalisables et une région réalisable bornée).
Ces trois propriétés sont aussi valables pour les problèmes qui sont augmentés des variables
artificielles.
5.2 La méthode du simplexe sous forme de matrice
La forme matricielle générale d’un problème de programmation linéaire est la suivante :
𝑀𝑎𝑥𝑖𝑚𝑖𝑠𝑒 𝑍 = 𝐶𝑋,
Sous contrainte de :
𝐴𝑋 ≤ 𝑏 𝑒𝑡 𝑋 ≥ 0,
Dans cette forme :
𝐶 = [𝑐1 , 𝑐2, … , 𝑐𝑛 ],
𝑋, 𝑏 𝑒𝑡 0 sont des vecteurs colonnes tels que :
𝑥1 𝑏1 0
𝑥2 𝑏2 0
. . .
𝑋= . , 𝑏= , 0= ,
. .
. . .
[𝑥𝑛 ] [𝑏𝑛 ] [0]

et A est la matrice des coefficients techniques,

𝑎11 𝑎12 … 𝑎1𝑛
𝑎21 𝑎22 … 𝑎
𝐴 = [ … … … … … … … … … . .2𝑛
. . ].
𝑎𝑚1 𝑎𝑚2 … 𝑎𝑚𝑛
Pour obtenir la forme augmentée du problème nous allons introduire la colonne des variables
artificielles,
𝑥𝑛+1
𝑥𝑛+2
.
𝑋𝑠 = . ,
.
[𝑥𝑛+𝑚]
Si bien que les contraintes deviennent
𝑋 𝑋
[A, I] [ ] = 𝑏 𝑒𝑡 [ ] ≥ 0 ,
𝑋𝑠 𝑋𝑠
Dans cette forme 𝐼 est une matrice identité de dimension 𝑚 × 𝑚 et le vecteur nul est de
dimension 𝑛 + 𝑚.
5.2.1. Résolution pour la solution basique réalisable
Rappelons que l’approche générale de la méthode du simplexe consiste à obtenir une séquence de
solutions d’amélioration jusqu’à ce qu’une solution optimale soit atteinte. Une des caractéristiques
fondamentales de la forme matricielle de la méthode du simplexe concerne la manière dont elle
résout chaque nouvelle solution après avoir identifié ses variables de base et non basiques. Étant
donné ces variables, la solution de base résultante est la solution des 𝑚 équations.
𝑋
[A, I] [ ] = 𝑏,
𝑋𝑠
𝑋
avec les 𝑛 variables non basiques des 𝑛 + 𝑚 éléments de [ ] initialiser a zéro. L'élimination de
𝑋𝑠
ces 𝑛 variables en les égalant à zéro laisse un ensemble de 𝑚 équations à 𝑚 inconnues (les variables
de base). Cet ensemble d'équations peut être noté par,
𝐵𝑋𝐵 = 𝑏,
Avec le vecteur de variables basique
𝑥𝐵1
𝑥𝐵2
. 𝑋
𝑋𝐵 = . , obtenu par élimination des variables non basiques de [ ].De même la matrice
𝑋𝑠
.
[𝑥𝐵𝑚 ]
basique
𝐵11 𝐵12 … 𝐵1𝑚
𝐵 𝐵
𝐵 = [ …21… … …22 … 𝐵 ], est obtenue en éliminant les colonnes qui correspondent aux
… … … … … …2𝑚..
𝐵𝑚1 𝐵𝑚2 … 𝐵𝑚𝑛
coefficients des variables non-basiques de la matrice [A, I]. La méthode du simplexe est construite
de manière à rendre la matrice 𝐵 non singulière et que son inverse 𝐵 −1 existe. Ainsi, pour résoudre
l’équation 𝐵𝑋𝐵 = 𝑏, il va falloir prémultiplier les deux parties de l’équation par 𝐵 −1.
𝐵 −1𝐵𝑋𝐵 = 𝐵 −1𝑏, pour avoir 𝑋𝐵 = 𝐵 −1𝑏.

i nous notons 𝑐𝐵 comme étant les coefficients de la fonction objectif correspondant aux éléments
de 𝑋𝐵 alors, la valeur de la fonction objectif pour cette solution basique est :
𝑍 = 𝑐𝐵 𝑋𝐵 = 𝑐𝐵 𝐵 −1𝑏. 𝑍 = 𝑐𝐵 𝐵 −1𝑏
Exemple : Pour illustration, nous allons considérer, notre problème pédagogique avec deux
variables qui a été résolu par la méthode du simplexe dans la Table 4.8. Pour ce problème

En référant à la Table 4.8, nous voyons que les solutions obtenues par la méthode du simplexe sont
les suivantes :
Itération 0

Itération 1

Et donc,
Itération 2

5.2.2. La forme matricielle des équations dans la résolution tabulaire

Le dernier préalable avant de résumer la forme matricielle de la méthode du simplexe consiste à
montrer la forme matricielle de l’ensemble des équations figurant dans le tableau du simplexe pour
toute itération de la méthode du simplexe d'origine. Pour l’ensemble des équations d’origine, la
forme matricielle est la suivante :

Cet ensemble d’équations est également présenté dans le premier tableau du simplexe de la Table
5.8. Les opérations algébriques effectuées par la méthode du simplexe (multiplier une équation par
une constante et ajouter un multiple d’une équation à une autre) sont exprimées sous forme de
matrice en prémultipliant les deux équations originales par la matrice appropriée. Cette matrice
aurait les mêmes éléments que la matrice identité, sauf que chaque multiple pour une opération
algébrique irait à l’endroit nécessaire pour que la multiplication matricielle effectue cette opération.
Même après une série d’opérations algébriques sur plusieurs itérations, nous pouvons encore
déduire ce que cette matrice doit être (symboliquement) pour toute la série en utilisant ce que nous
savons déjà sur les membres de droite du nouvel ensemble d’équations. En particulier, après toute
itération, 𝑋𝐵 = 𝐵 −1𝑏 et 𝑍 = 𝑐𝐵 𝐵 −1𝑏, de sorte que les membres de droite du nouvel ensemble
d’équations sont devenus

Comme nous effectuons la même série d'opérations algébriques des deux côtés de l'ensemble
d'équations d'origine, nous utilisons cette même matrice qui prémultiplie le côté droit d'origine pour
prémultiplier le côté gauche d'origine. Par conséquent,

Table 5.8 : Tableau initial et suivant du simplexe sous forme matricielle

La forme matricielle désirée de la série d’équation après toute itération est :

Exemple : Pour illustrer cette forme matricielle de la série d’équations actuelles, nous montrerons
comment elle produit la série finale d’équations résultant de l’itération 2 pour notre problème
pédagogique. En utilisant les valeurs 𝐵 −1et 𝑐𝐵 donnés pour l'itération 2 à la fin de la sous-section
précédente, on a :
De plus, en utilisant les valeurs de 𝑋𝐵 = 𝐵 −1𝑏 et 𝑍 = 𝑐𝐵 𝐵 −1𝑏 calculées à la fin de la sous-section
précédente, ces résultats donnent l’ensemble des équations suivantes :

Ce qui est la même chose comme dans la Table 4.8.

La forme matricielle de l'ensemble des équations après chaque itération (comme indiqué dans
l'encadré juste avant l'exemple ci-dessus) fournit la clé pour l'exécution de la forme matricielle de
la méthode du simplexe. Les expressions matricielles figurant dans ces équations (ou dans la partie
inférieure du tableau 5.8) permettent de calculer directement tous les nombres qui figureraient dans
l’ensemble d’équations actuel (pour la forme algébrique de la méthode du simplexe) ou dans le
tableau du simplexe actuel (pour la forme tabulaire de la méthode du simplexe). Les trois formes
de la méthode du simplexe prennent exactement les mêmes décisions (entrée d'une variable de
base, sortie d'une variable de base, etc.), étape par étape et itération après itération. La seule
différence entre ces formes réside dans les méthodes utilisées pour calculer les nombres nécessaires
à la prise de décision. Comme résumé ci-dessous, la forme matricielle offre un moyen pratique et
compact de calculer ces nombres sans entraîner une série de systèmes d'équations ou une série de
tableaux du simplexe.
5.2.3. Résumé de la forme matricielle du simplexe
1. Initialisation : Introduisez les variables artificielles, etc., pour obtenir les variables de base
initiales, comme décrit au Chap. 4. Cela donne les valeurs initiales, 𝑋𝐵 et 𝑐𝐵 , 𝐵, 𝐵 −1 (où 𝐵 = 𝐼 =
𝐵 −1 selon notre hypothèse actuelle selon laquelle le problème à résoudre correspond à notre forme
standard). Ensuite aller au test d'optimalité.
2. Itération :
Étape 1. Déterminez la variable de base entrante : reportez-vous aux coefficients des
variables non basiques dans Eq. (0) obtenus lors de l'application précédente du test
d'optimalité ci-dessous. Ensuite (comme décrit dans la section 4.4), sélectionnez la variable
avec le coefficient négatif ayant la plus grande valeur absolue comme variable de base
entrante.
Étape 2. Déterminez la variable de basique sortante : Utilisez les expressions de matrice,
𝐵 −1𝐴 (pour les coefficients des variables d'origine) et 𝐵 −1 (pour les coefficients des
variables artificielles), pour calculer les coefficients de la variable de base entrante dans
toutes les équations sauf Eq. (0). Utilisez également le calcul précédent de 𝑋𝐵 = 𝐵 −1𝑏 (voir
l’étape 3) pour identifier le côté droit de ces équations. Ensuite (comme décrit dans la
section 4.4), utilisez le test du ratio minimum pour sélectionner la variable de base sortante.
Étape 3. Déterminez la nouvelle solution : mettez à jour la matrice de base 𝐵 en remplaçant
la colonne de la variable de base sortante par la colonne correspondante dans [A, I] pour la
variable de base entrante. Effectuez également les remplacements correspondants dans 𝑋𝐵 et
𝑐𝐵 . Puis dérivez 𝐵 −1 (comme illustré à l’Annexe 4) et définissez 𝑋𝐵 = 𝐵 −1𝑏.
1. Test d’optimalité : Utilisez les expressions de la matrice, 𝑐𝐵 𝐵 −1𝐴 − 𝑐 (pour les coefficients des
variables originales) et 𝑐𝐵 𝐵 −1 (pour les coefficients des variables artificielles), pour calculer
les coefficients des variables non basiques dans l’équation (0). La solution actuelle est optimale
si et seulement si tous ces coefficients sont non négatifs. Si c'est optimal, arrêtez. Sinon, passez
à une itération pour obtenir la solution suivante.
Exemple : A partir de l’exercice pédagogique nous allons suivre toutes les étapes dans la résolution
matricielle comme suit :
Pour rappel, nous avons

Initialisation (itération 0)
Comme montré précédemment, les variables de basique dans cette initialisation sont les variables
artificielles.

Le test d’optimalité
Les coefficients des variables non basiques (𝑥1 𝑒𝑡 𝑥2) dans la fonction objectif sont :
Ces coefficients négatifs indiquent que la solution initiale en coin n’est pas réalisable.
Initialisation 1
Puisque -5 est supérieur en valeur absolue à -3, la variable de base entrante est 𝑥2. Les coefficients
de 𝑥2 dans chaque équation sauf Eq. (0) sont :
1 0
𝐵 −1𝐴 = [0 2]
3 2
En divisant les éléments de droite des équations par les coefficients de 𝑥2 (le vecteur de la deuxième
colonne) et en appliquant le test du ratio minimum, on trouve que la variable sortante de la base est
𝑥4. Ainsi, nous aurons

Le test d’optimalité
Les variables non basiques sont 𝑥1 et 𝑥4, 𝑒𝑡 leurs coefficients dans l′equation 0 sont:
Pour 𝑥1 ,

Pour 𝑥4 ,

Comme le coefficient de 𝑥1 est négatif nous ne sommes pas encore à l’optimum. Nous devons
aller à l’itération suivante. Puisque la variable 𝑥1 est la seule variable non basique ayant un
coefficient négatif, elle devient la variable entrante. Nous avons donc,
En appliquant le test du ratio minimum on retrouve que la variable 𝑥5 est la variable sortante de
la base. Nous avons donc,

Test d’optimalité
Les deux variables non basiques actuelles sont 𝑥4 𝑒𝑡 𝑥5. En utilisant le calcul usuel on trouve
leurs coefficients dans la fonction objectif sont tous positifs et sont égaux a 3/2 et 1
respectivement. Nous sommes donc à l’optimum et la solution optimale est (𝑥1 = 2, 𝑥2 = 6, 𝑥3 =
2, 𝑥4 = 0, 𝑥5 = 0, ).
Conclusion
Bien que la méthode du simplexe soit une procédure algébrique, elle repose sur des concepts
géométriques assez simples. Ces concepts permettent d’utiliser l’algorithme pour n’examiner
qu’un nombre relativement petit de solutions réalisables avant d’atteindre et d’identifier une
solution optimale. Les opérations matricielles constituent un moyen plus rapide de combiner et
d’exécuter des opérations algébriques élémentaires ou des opérations de lignes. Par conséquent,
la forme matricielle du simplexe fournit un moyen efficace d'adapter la méthode du simplexe
pour la mise en œuvre par ordinateur.