Chapitre 2

Méthode du Simplexe

La méthode du SIMPLEXE est l’outil principal qui permet la recherche de la solution

optimale d’un programme linéaire (PL) donné. C’est une procédure algébrique pour résoudre
des PL avec plus de deux variables.

Elle consiste à suivre un certain nombre d’étapes avant d’obtenir la solution d’un problème
donné. Il s’agit d’une méthode algébrique itérative qui permet de trouver la solution exacte
d’un problème de programmation linéaire en un nombre fini d’étapes

La méthode du simplexe a été inventée en 1947 par George B. Dantzig, mathématicien américain, est
considéré comme l’un des pères fondateurs de la programmation linéaire.

1
Position du problème général
Forme standard

Un problème de programmation linéaire (PL) se présente sous sa forme standard si toutes les
contraintes sont des équations. La fonction objectif doit également être maximisée.
Sous forme matricielle, la forme standard s’écrit :

De manière générale, considérons le problème suivant où x={x1, . . . , xn} T Rn

Variables d’écart

La méthode du simplexe exige que le programme linéaire soit sous une forme standard. Pour
cette raison, il faut transformer les inégalités rencontrées en égalités. Cette transformation se
fait simplement en introduisant des variables non-négatives (qui vérifient les contraintes de
non-négativité) appelées variables d’écart.
Si les contraintes sont du type :
pour i =1, …, m

Nous introduisons de nouvelles variables xn+i  0 appelée variables d’écart et écrivons

pour i =1, …, m
De même, nous pouvons être contraints de transformer les contraintes de la forme

en une égalité en soustrayant cette fois une variable d’écart xn+i  0. Nous écrivons alors

Remarque
Remarquons qu’avec l’introduction des variables d’écart, tout problème sous forme canonique
possède une forme standard équivalente.

Notons encore que la méthode du simplexe requiert des bi  0. Par conséquent, les contraintes
qui ont un bi négatif doivent être transformées en contraintes aux bi positifs. Cette
transformation se fait simplement en multipliant la contrainte par (-1).

Exemple Supposons que les contraintes d’un programme linéaire sont les suivantes

2
Pour les transformer en égalités, il faut introduire une variable d’écart dans la première et la
deuxième contrainte. La troisième est déjà sous forme d’égalité mais doit être multipliée par (-
1) pour avoir un bi positif. Ces trois contraintes peuvent donc être reformulées ainsi :

Généralement, considérons le problème suivant où x={x1, . . . , xn} T Rn

Le réel cj est souvent appelé le “prix” associé à la variable xj. En assignant un prix nul à chaque
variable d’écart, la transformation des contraintes en un système d’équations linéaires ne
change pas la fonction objectif qui est

où l’indice r indique le nombre de variables d’écart qu’il a fallu rajouter.

Introduction de variables d’écart, xn+1, . . . , xn+m, on obtient :

Caractérisation des solutions du problème

Considérons le problème de programmation linéaire se présentant sous forme standard

Le vecteur x contient toutes les variables, y compris les variables d’écart; il s’agit d’un vecteur
colonne d’ordre (n × 1). Le vecteur c est un vecteur ligne d’ordre (1×n).
Quant à la matrice A, d’ordre (m × n), il s’agit de la matrice des coefficients des contraintes
transformées. Enfin, le vecteur b d’ordre (m × 1) est le vecteur du second membre

Définition
On appelle solution d’un problème de programmation linéaire tout vecteur x qui satisfait les
contraintes A.x = b .
Une solution est appelée solution réalisable si elle vérifie les contraintes de non-négativité
Dans le cas contraire, on dit que la solution n’est pas réalisable.

3
Une solution réalisable est une solution optimale s’il n’existe pas d’autres solutions
réalisables qui fournissent une plus grande valeur de la fonction objectif.

Remarque
L’ensemble des contraintes s’écrit comme un système de m équations à n inconnues Ax = b.

Hypothèse de la méthode de Simplexe

Les hypothèses suivantes sont nécessaires pour développer la méthode du simplexe,
1. r(A) = r(A | b), c’est-à-dire que le système d’équations est compatible,
2. r(A) = m, où m est le nombre de contraintes.

La seconde hypothèse permet de former, à partir de A, une (m×m) sous matrice B non-
singulière.

Cette matrice B peut être formée par n’importe quel ensemble de m colonnes linéairement
indépendantes de A.

b). La matrice B est appelée matrice de base puisqu’elle est formée de m vecteurs linéairement
indépendants.

Notations

➢ On écrit A sous la forme A = [B, N] avec B de dimension (m×m) la matrice de base et N

de dimension (m×(n-m)) où N désigne les colonnes de A qui ne sont pas dans B

➢ On partitionne les vecteurs

➢ Le programme linéaire précédent peut donc être reformulé de la manière suivante

➢ Toute solution du problème vérifie A.x = b, c-à-d : [Link] + [Link] = b

➢ Les variables xB sont appelés variables de base et les variables xN les variables hors base.
➢ Le vecteur c peut lui aussi être partitionné de la même manière en c = (cB, cN).
➢ La solution de base associée à la base B est la solution particulière obtenue en posant
xN = 0.
➢ Le vecteur xB est alors déterminé de façon unique par la résolution du système de Cramer
[Link] = b , soit xB = B−1b
Exemple
Soit le problème de programmation linéaire suivant :

4
Ce problème peut se mettre sous forme standard en introduisant les variables d’écart x4 et x5 :

Sous forme matricielle, on obtient donc :

Formons à partir de A une matrice de base B

B est non-singulière (det(B )= 4  0). B= (b1, b2) avec

À cette matrice de base B correspond une solution de base donnée par xB = B-1b avec

Les autres variables étant nulles, x1 = x3 = x5 = 0.

Cette solution de base n’est pas réalisable pour la simple raison que xB1 = x2 = -5 viole la
contrainte de non-négativité. D’ou il faut changer de base B

Dans cet exemple, il est très facile de trouver une base qui fournisse une solution réalisable de

base. En effet, les colonnes a4 et a5 forment une base qui est l’identité

Pour cette base, la solution de base est le vecteur b puisque

La solution ainsi obtenue est une solution réalisable de base et z a pour valeur :
z = 0.16 + 0 . 20 = 0. ‘x1= 0 et x2 = 0.

Mais, cette solution n’est pas optimale. Il faut d’autres itération pour aboutir à une solution
réalisable et optimale.

Définitions
Tout vecteur xa satisfaisant les contraintes égalité est appelé vecteur admissible ou réalisable,
Un vecteur admissible qui maximise le critère est appelé vecteur admissible optimal.

5
L’ensemble Xad = {xa | A. xa = b, xa ≥ 0} est l’ensemble des solutions admissibles du
problème

Recherche d’une solution optimale

Proposition
Tout point extrême est une solution réalisable de base.

Principe de méthode de Simplexe

À la solution réalisable de base initiale correspond une valeur de la fonction objectif z.

Le but est d’améliorer la valeur de la fonction objectif en l’évaluant en un point extrême
adjacent.
Pour cela, étant donné une base B, on trouve un point extrême adjacent (nouvelle solution
réalisable de base) en échangeant l’une des colonnes de la base (bi) contre une colonne aj qui
n’est pas dans la base.
Cependant, en faisant cet échange, il faut s’assurer que la solution de base reste réalisable et
que la valeur de la fonction objectif augmente (ou du moins ne diminue pas)

Règle de changement de Base

Il y a deux règles à suivre pour cet échange.
➢ La première consiste à déterminer quelle colonne aj de A (à laquelle correspond une
variable xj) doit entrer dans la base pour améliorer la fonction objectif.
➢ La seconde consiste à sélectionner l’une des colonnes bi qui doit quitter la base de manière
à ce que la nouvelle solution de base reste réalisable.

Critères d’entrée et de sortie de la base

Pour développer ces deux critères, nous reformulons le programme linéaire sous la forme
suivante :

où J est l’ensemble des indices des variables hors base.

Notons que B est une base formée de m colonnes linéairement indépendantes. D’où, toute
colonne aj de la matrice A peut s’écrire comme une combinaison linéaire des colonnes de la
matrice B. On peut donc écrire :

6
Variables zj
Définissons une nouvelle variable zj par

En utilisant ces notations, les contraintes s’écrivent alors :

et la fonction objectif se réécrit par :

D’ou on obtient :

Remarque
Lorsqu’on obtient une solution réalisable de base, les valeurs des variables xj sont nulles pour
tout indice j  J. Dans ce cas, la valeur de la fonction objectif est z = cBB-1b.
Encore une fois, le but est d’améliorer au maximum cette valeur de z.

Dans l’équation précédente de z, les variables xj sont non-négatives et la sommation est

précédée du signe négatif. C’est donc la variable xj , au plus petit (zj - cj) < 0, qui améliorera
le plus la valeur de la fonction objectif.
Le critère d’entrée dans la base est donc le suivant.

• Critère d’entrée dans la base

Le vecteur ak qui doit entrer dans la base correspond à la variable hors base xk pour laquelle
(zj - cj) a la plus petite valeur négative :

Il reste encore à déterminer quel vecteur de base doit quitter la base. On a :

7
Toutes les variables hors base sont nulles sauf xk qui devient une variable de base.

Notons xk est une nouvelle variable de base, elle sera notée 𝑥̂𝑘 .
Ainsi la nouvelle solution de base, notée 𝑥̂𝐵 s’écrit :

La ième composante de cette solution de base est :

Pour que cette solution de base soit réalisable, il faut que les variables de base soient non-
négatives,

Pour les variables qui ont yik positif, il faut que

Cette inégalité devant être valable pour tout i tel que yik > 0, 𝑥̂𝑘 doit être égale au plus petit
rapport xBi/yik.
Supposons que ce plus petit rapport soit associé à la rème variable de base xBr. On pose alors :

Cela permet de sortir xBr de la base.

Critère de sortie de la base

Soit le vecteur ak qui doit entrer dans la base. Le vecteur br associé à la variable xBr qui doit
sortir de la base est celui qui satisfait :

Étapes de la méthode du simplexe

Étape 1 Rechercher la solution optimale à partir d’une solution réalisable de base :

xB = B-1b.
Étape 2 Examiner les (zj - cj) pour toutes les colonnes aj qui ne sont pas dans la base.
Si tous les (zj - cj)  0, passer à l’étape 6, sinon passer à l’étape 3.
Étape 3 S’il existe un (zj - cj) négatif pour lequel il n’y a pas d’éléments positifs dans yj, arrêter
la recherche puisque la solution optimale est infinie.
Sinon, choisir le vecteur (et donc la variable) associée à la valeur la plus négative des (zj - cj)
pour entrer dans la base :

Étape 4 Déterminer le vecteur (et donc la variable) qui sort de la base à l’aide du critère :

􀀖
8
Étape 5 Établir la nouvelle base, calculer la nouvelle solution réalisable de base et la nouvelle
valeur de la fonction objectif.
Retourner à l’étape 2.
Étape 6 La solution réalisable de base courante est la solution optimale.

La solution optimale n’est pas unique s’il existe un (zj - cj) nul pour un vecteur aj qui ne se
trouve pas dans la base.

Exemple
Considérons le programme linéaire suivant à résoudre par la méthode du simplexe

En introduisant les variables d’écart x3 et x4 dans les contraintes, le problème s’écrit sous forme
standard suivante :

Notations matricielles

Les colonnes a3 et a4 de la matrice A forment une matrice identité. On peut donc les prendre

comme base :
À cette base, correspond la solution réalisable de base

Le vecteur CB est donné par cB =(0 , 0)

Les variables hors base x1 et x2 sont nulles. La valeur de la fonction objectif vaut alors :

Jusque-là, les colonnes a3 et a4 sont dans la base. Mais la fonction cout z n est optimale. Doc il
faut changer la base

Pour savoir quelle colonne doit entrer dans la base (a1 ou a2), il faut calculer (zj - cj) pour les
variables hors base :

9
Les deux valeurs étant négatives, le critère d’entrée nous indique que la variable à entrer dans
la base (et donc la colonne correspondante) est x1 puisque min(-4, -3) = -4. Par conséquent, la
colonne a1 doit entrer dans la base.
Il reste à savoir le vecteur qui va sortir de la base. Pour cela, on applique le critère de sortie
pour savoir quelle colonne doit sortir de la base :

C’est donc xB1 = x3 qui sort de la base.

En définitive, la colonne a1 remplace la colonne a3 pour former une nouvelle base.

Calculons la nouvelle valeur de la variable x1 qui entre dans la base :

Les nouvelles valeurs des variables de base d’origine se calculent par :

La nouvelle valeur de la fonction cout z est :

Remarquons que la valeur de la fonction objectif s’est améliorée en passant de 0 à 20.

À ce stade, nous disposons de la solution réalisable de base suivante :
x1 = 5, x2 = 0, x3 = 0 et x4 = 3
La matrice de base B est formée par les colonnes a1 et a4 :

Calculant à nouveau (zj - cj) pour les variables hors base pour voir si la valeur de la fonction objectif
peut être encore améliorée. Pour cela calculons

10
D’ou

On voit alors qu’il n’existe qu’une valeur de (zj - cj) négative.

En appliquant le critère d’entrée c’est donc la colonne a2 correspondant à la variable x2 qui entre dans
la base.
On doit alors appliquer le critère de sortie. Pour cela faisons les calculs suivants ;

C’est donc la colonne a4 associée à la variable x4 qui sort de la base.

La nouvelle valeur de la variable x2 qui entre dans la base est

Les nouvelles valeurs des variables xB1 = x1 et xB2 = x4 sont :

La nouvelle valeur de la fonction objectif est :

Avec cette nouvelle solution réalisable de base x1 = 2, x2 = 6, x3 = 0 et x4 = 0,

La valeur de la fonction objectif s’est encore améliorée ! On se demande si cette valeur peut encore
être améliorée.
Pour le savoir, calculons (zj -cj) pour les variables hors base, c’est-à-dire x3 et x4 ; la matrice de base B
est formée des colonnes a1 et a2

Finalement, tous les (zj -cj) sont non-négatifs et du cout on ne peut plus appliquer le critère d’entrée.
Dans ce cas, la valeur de z ne peut plus être améliorée ; la solution réalisable de base correspondant à
cette situation est alors la solution optimale.

11
Tableaux du simplexe et procédure de calcul

Lorsque l’on calcule la méthode du simplexe à la main, il est préférable de travailler avec un tableau qui
contient toutes les données nécessaires. À chaque itération correspond un nouveau tableau prenant la
forme suivante : Tableau du simplexe

La première colonne indique les prix cB correspondant aux vecteurs de base.

La deuxième colonne indique quels vecteurs se trouvent dans la base.
Les vecteurs bi, i = 1, . . ., m représentent les m colonnes de la matrice de base B.
Si la matrice de base est formée des colonnes a1, a3 et a4 par exemple, on écrira a1 à la place de
b1, a3 à la place de b2 et a4 à la place de b3.
La troisième colonne du tableau fournit la solution réalisable de base xB sauf à la dernière ligne
où l’on trouve la valeur de z pour la solution réalisable de base.
Les colonnes suivantes indiquent les valeurs des yj pour tous les vecteurs de A.
La première ligne donne les prix associés aux variables et la dernière ligne donne les (zj - cj).

Utilisation du tableau du simplexe

Les informations données par le tableau peuvent être utiliser pour effectuer les différentes
étapes de la méthode du simplexe.
En premier lieu, examinons les éléments de la dernière ligne (zj - cj) correspondant aux vecteurs
hors base aj. Si tous les (zj -cj)  0, la solution est optimale.
S’il existe un (zj -cj) < 0 pour lequel il n’existe pas d’éléments positifs dans yj (la colonne au-
dessus de (zj - cj)), la solution est infinie.
Si tel n’est pas le cas, nous choisissons le plus petit (zj - cj).
Appelons la colonne correspondante k. Ainsi ak entre dans la base. Le vecteur qui doit sortir de
la base est choisi par le critère :

Cela signifie que le vecteur de la rème ligne dans la colonne “vecteurs de base” est remplacé par
ak.
12
Pivot
Il faut à présent tracer un nouveau tableau. À l’intersection de la colonne ak qui entre dans la
base et du vecteur br qui en sort, se trouve le terme yrk qui est appelé le pivot de la
transformation.
La colonne ak est appelée colonne-pivot et le vecteur br ligne-pivot. I
l est utile d’encercler dans le tableau le pivot ainsi que la colonne-pivot et la ligne-pivot.
Établissons les formules de transformation en ajoutant le symbole “ˆ” au-dessus des nouvelles
valeurs afin de les distinguer des anciennes. Les nouvelles valeurs des variables de base se calculent
facilement à partir des anciennes.

Exemple
Résoudre par la méthode du Simplexe le problème de programmation linéaire suivant

Posons ce programme linéaire sous forme standard.

On Applique les différentes étapes de la méthode du simplexe.

Étape 1
La base B est formée par les vecteurs a3 et a4 et correspond à la matrice identité.

La solution réalisable de base correspondante est donnée par

. Les termes (zj -cj) correspondant aux vecteurs de base sont nuls et ceux correspondant aux vecteurs
hors base s’obtiennent en calculant :

La fonction objectif a pour valeur :

Ces résultats sont mis sur le tableau initial du simplexe suivant :

13
Étape 2 Dans ce tableau, nous voyons qu’il reste des (zj - cj) négatifs.
Étape 3 Les vecteurs yj situés au-dessus des (zj -cj) négatifs n’ont que des éléments positifs. Une
amélioration de la fonction objectif est donc possible et nous cherchons le vecteur qui doit entrer dans
la base.
La plus petite valeur négative des (zj -cj) est -4 obtenue pour (z2 - c2). Donc, k = 2 et le vecteur a2 entre
dans la base.
La colonne correspondante est la colonne-pivot qui a été encadrée dans le tableau. Pour connaître le
vecteur qui sort de la base, nous passons à l’étape 4.
Étape 4 Examinons les rapports xBi/yi2 avec yi2 > 0 :

Le plus petit rapport est 6 et correspond à xB2/y22. Ainsi, r = 2 et le vecteur a4 (correspondant à la variable
xB2 = x4) sort de la base. La ligne correspondante est la ligne-pivot qui a été encadrée dans le tableau. Il
reste à établir le nouveau tableau à l’étape 5.
Étape 5 Puisque a2 remplace a4 dans la base, on remplace cB2 = c4 = 0 par c2 = 4 dans la colonne cB. Tous
les autres éléments du nouveau tableau se calculent à partir des formules précédentes.

14
Polytopes Convexes
Ensemble convexe et polytope
Définition
Un sous-ensemble S de Rn est dit convexe ssi : ∀x ∈ S, y ∈ S,  ∈ [0, 1] ⇒ x + (1 − )y ∈
S
Le demi-espace fermé des (x1, x2, . . . , xn) vérifiant : 1x1 + 2x2 + . . . + nxn ≤ 
C’est un ensemble convexe.
L’intersection d’un nombre fini de sous-ensembles convexes de Rn est un ensemble convexe.
Un polytope convexe de Rn est l’intersection d’un nombre fini de demi-espaces fermés.
Un polyèdre convexe de Rn est un polytope borné.
Combinaison linéaire convexe
Etant donnés k points x1, x2, . . . , xk de Rn, on appelle combinaison linéaire convexe de ces k points,
un point x tel que:

Propriété
L’ensemble S des solutions admissibles d’un problème de programmation linéaire est :
➢ Soit un polytope convexe (cas des domaines non bornés),
➢ Soit un polyèdre convexe (cas des domaines bornés),

Point extrême
On appelle points extrêmes d’un polytope ou d’un polyèdre convexe S, un point x ∈ S qui ne peut pas
être exprimé comme combinaison linéaire convexe d’autres points y ∈ S (y  x).
Ces points correspondent aux sommets du polytope.
Tout point x d’un polyèdre convexe S ⊂ Rn est combinaison linéaire convexe de points extrêmes de S.

15