Le simplexe pour les nuls

Pierre Fritsch

12 décembre 2005

1 Le problème
On considère le problème de programmation linéaire suivant :

max cT x|Ax ≤ b

où c est un vecteur de taille n, b un vecteur de taille m et A une matrice de dimension

2 Algorithme du simplexe
 Soit I un sous-ensemble de n éléments de {1, 2, . . . , m} et soit x solution de AI x = bI .
 Soit y tel que yi = (cA−1I )i pour i ∈ I et yj = 0 pour j ∈ / I.
 Si y ≥ 0 alors x est solution du système.
 Sinon soit i le plus petit indice tel que yh < 0 et soit Ui la colonne correspondante
de A−1
I ; déterminer pour chaque ligne Lj de la matrice A la valeur vj = −Lj Ui .
 Si ∀j , vj ≤ 0 alors cx est non borné pour Ax ≤ b.
b −L x
 Sinon soit j tel que j vj j soit minimum parmi les vj positifs. On pose alors I :=
I \ {i} ∪ {j} et on calcule x, intersection des hyperplans correspondants.

3 Un petit exemple
Prenons le cas de 2 variables x et y . On veut maximiser 4x + 5y tout en respectant les
contraintes 
 x+y ≤5
2x + y ≤ 8
x + 2y ≤ 8


Ce système se met sous la forme

1
 On a donc n = 2 et m = 3.

Première étape
 
1 1
 On choisit I = {1, 2} . Les lignes correspondantes de A sont AI = et celles
2 1
   
5 3
de b sont bI = . On calcule x = , solution de AI x = bI .
8 2
 
−1 −1 1
 AI = permet de calculer y = 6 −1 0 , tel que yi = cA−1
 

I =
2 −1 i
  
 −1 1
= 6 −1 i pour i ∈ I et yj = 0 pour j ∈ / I.
  
4 5
2 −1 i
 On n'a pas y ≥ 0.  
1
 On prend donc i = 2 le plus petit indice tel que yh < 0 et Ui = U2 = la
−1
colonne correspondante de A−1 I . On détermine pour chaque ligne Lj de la matrice
   
1 1   0
1
A la valeur vj = −Lj Ui − −Lj U2 : v = −A U2 =  2 1  =  −1 , i.e.
−1
1 2 1
v1 = 0 , v2 = −1 , v3 = 1 .
 On n'a pas ∀j , vj ≤ 0. J = {3} est l'ensemble des indices j pour lesquels vj est
strictement positif.
b −L x
 Pour chaque élément j de J , on calcule j vj j . Dans notre cas on se limite à j = 3
2 3
h i 3
8− 1 2 4 5
b3 −L3 x 2
pour lequel v3 = 1 = 1. Cette quantité est la plus petite des
bj −Lj x
vj calculés. On garde donc j = 3 .

Deuxième étape
 On remplace donc I par I \ {i} ∪ {j} = {1, 2} \ {2} ∪ {3}, soit I = {1, 3} . On a
     
1 1 5 2
donc AI = et bI = , qui donne x = , solution de AI x = bI .
1 2 8 3
   
2 −1 2 −1
 A−1 donne cA−1 = 3 1 et y = 3 0 1 .
     
I = I = 4 5
−1 1 −1 1
 
2
 On a y ≥ 0 donc x = est solution du système.
3