MÉTHODE DU SIMPLEXE DUAL (REVISITÉE)

J.F. SCHEID

1. Introduction
La méthode du simplexe dual (C.E. Lemke 1954 [4], E.M.L. Beale 1954 [3]) consiste
à appliquer la méthode du simplexe au problème dual en travaillant avec des solutions
de base qui ne sont pas nécessairement positives (donc pas nécessairement réalisables).
On considère un problème d’optimisation linéaire (programme linéaire) écrit sous forme
standard (contraintes égalités) :
h i
max F (x) = c> x
x
(1) 
Ax = b
x≥0
Le problème dual de (1) s’écrit
h i
min G(y) = b> y
y
(2)  >
A y≥c
y de signes quelconques
ou bien encore sous forme standard
h i
min G(y, ξ) = b> y
(y,ξ)
 A> y − ξ = c

(3)
y de signes quelconques,
ξ≥0


A chaque itération de la méthode du simplexe dual, les variables primales entrante et

sortante de (1) sont déterminées en examinant le problème dual (2). Cette méthode
s’applique en ayant déjà déterminer une solution de base réalisable pour le problème dual.
C’est par exemple le cas si c ≤ 0 1 dans (2). La méthode du simplexe dual peut aussi être
utilisée en analyse de sensibilité lorsque qu’on a déjà obtenu une solution optimale. Si
on modifie le vecteur b la solution duale optimale précédente reste une solution de base
réalisable pour le dual. On peut alors appliquer le simplexe dual (avec le nouveau b) en
partant de cette solution de base duale réalisable.
Pour commencer, on supposera d’abord qu’on dispose d’une solution de base réalisable
pour le problème dual. On verra ensuite (cf. Section 5. Extension) qu’on peut relacher
cette hypothèse de départ et obtenir ainsi une méthode permettant de s’affranchir de la
Date: 24 octobre 2020.
1. Si c ≤ 0, on a alors une solution de base duale réalisable évidente en prenant comme variables de
bases duales les variables d’écart duales ξ = −c ≥ 0 et y = 0.
1
2 J.F. SCHEID

phase d’initialisation (Phase 1) quand celle-ci est nécessaire. L’algorithme du simplexe

dual est présenté ici avec la méthode des dictionnaires.

2. Simplexe et dualité
Commençons par appliquer la notion de dualité aux dictionnaires. La méthode du
simplexe avec dictionnaires appliquée à (1) conduit à chaque itération à un dictionnaire
primal qu’on peut écrire sous la forme
xB = b − AxH
(4)
F = F − L>
H xH

avec b = A−1 −1
B b, A = AB AH et LH représente les coûts réduits. On peut interpréter le
dictionnaire (4) comme provenant du PL primal suivant :
h i
>
max
  F (x) = F + LH xH
xB
x=
xH
(P L)    
xB
Id | A =b

xH
xB , xH ≥ 0


qui admet le problème dual suivant mis sous forme standard :

>
h i
min G(y, ξ) = F + b y
(y,ξ)
(P LD)  >
A y − ξ = LH
y, ξ ≥ 0
Le dictionnaire du simplexe associé à (P LD) s’écrit alors
>
ξ = −LH + A y
(5) >
G=F +b y
On pose yH = ξ et yB = y. Le dictionnaire (5) se réécrit
>
yH = −LH + A yB
(6) >
G = F + b yB

Définition 2.1.
i) On dira que (6) est le dictionnaire dual du dictionnaire
 primal (4).
xB
ii) Si LH ≤ 0, on dira que la solution de base x = associée à (4) est dual-
xH
réalisable.
Remarque. Si la solution de base duale (yH , yB ) du dictionnaire dual (6) est réalisable
i.e. si yH ≥ 0 alors la solution de base x est dual-réalisable.

Dans certaines situations, il peut être avantageux de résoudre le problème dual plutôt
que le problème primal. Par exemple, pour un PL sous forme canonique pure avec m
contraintes inégalités et n variables, si m est beaucoup plus grand que n on aura intérêt
 MÉTHODE DU SIMPLEXE DUAL (REVISITÉE) 3

à résoudre par simplexe le problème dual. Celui-ci comporte n contraintes (n << m)

et on sait que le côut de la méthode du simplexe dépend essentiellement du nombre de
contraintes et peu du nombre de variables. Si on résout le problème dual par la méthode
des dictionnaires et qu’on obtient une solution optimale duale alors le dictionnaire dual
final obtenu est de la forme (6) et on en déduit une solution optimale pour le problème
primal :
x∗B = b, x∗H = 0.
qui est associée au dictionnaire primal (4). Dans la méthode du simplexe dual, on applique
le simplexe sur le problème dual mais de façon implicite en continuant à travailler sur le
problème primal.

3. Méthode du simplexe dual

3.1. Principe de la méthode. On suppose qu’on dispose d’une solution de base initiale
duale-réalisable mais non nécessairement réalisable au sens où on n’a pas nécessairement
positivité des variables de base. Au cours des itérations de la méthode du simplexe dual,
les variables de base xB dans le dictionnaire primal (4) ne sont pas forcément toutes
positives. En revanche, les solutions de base seront toujours duale-réalisables. D’après le
dictionnaire primal (4), la solution de base est réalisable si et seulement si b ≥ 0 et on
rappelle qu’elle est duale-réalisable si LH ≤ 0.
On associe les variables de base primales xB aux variables duales yH (mêmes dimen-
sions) et les variables primales hors-base xH aux variables duales yB . A chaque itération
de la méthode du simplexe dual, on applique le simplexe sur le problème dual pour dé-
terminer les variables entrante et sortante dans le dictionnaire primal. Dans le
dictionnaire dual, on détermine la variable entrante yi (i ∈ H) et la variable sortante yj
(j ∈ B). Dans le dictionnaire primal, ces variables correspondent à la variable entrante
xj et à la variable sortante xi .
On note b = (bi )i∈B , A = (aij ) et LH = (Lk )k∈H .

— Variable duale entrante : yi avec i ∈ B tel que

(7) bi < 0


S’il existe plusieurs i ∈ B vérifiant (7), on choisit i ∈ B tel que bi = min bk < 0, k ∈ B
— Variable duale sortante : yj avec j ∈ H est déterminé en maintenant la positivité
des variables yH . On détermine l’indice j ∈ H tel que aij < 0 et

−Lk + aik yi ≥ 0, ∀k ∈ H
aik < 0

Lk
yi ≤ , ∀k ∈ H

c’est-à-dire a . Ainsi, on choisit j ∈ H tel que
 a < 0ik
ik

Lj Lk
(8) = min
aij k∈H aik
aik <0
4 J.F. SCHEID

Méthode du simplexe dual. Dans la méthode du simplexe dual, on ne travaille

pas explicitement avec le problème dual mais bien avec le problème primal. A chaque
itération, on détermine les indices i ∈ B vérifiant (7) et j ∈ H vérifiant (8). On choisit
alors xj comme variable primale entrante et xi comme variable primale sortante. La
valeur de la variable entrante est alors 2
bi
(9) xj = ≥0
aij
et xi = 0.

3.2. Arrêt du simplexe dual. Dans le simplexe dual, on parcourt les solutions de
base non nécessairement réalisables (au sens où on n’a pas nécessairement positivité). En
revanche, comme on maintient la positivité des variables de base duales, on aura toujours
LH ≤ 0. On distingue les différentes situations suivantes :
1. Il n’existe pas d’indice i ∈ B vérifiant (7).

Dans ce cas, on a bi ≥ 0, ∀i ∈ B i.e. b ≥ 0. La solution de base primale du

dictionnaire (4) est alors réalisable. Comme on a toujours LH ≤ 0, la solution de
base primale est optimale. Elle vaut

x∗B = b, x∗H = 0.

2. Il n’existe pas d’indice j ∈ H vérifiant (8).

Dans ce cas, on a aij ≥ 0, ∀j ∈ H où l’indice i ∈ B est tel que bi < 0. A partir de

la relation
X
xi = bi − aij xj ,
j∈H

on en déduit que xi < 0 quels que soient les xj ≥ 0. Par conséquent, le problème
primal n’a pas de solution réalisable.

Remarque. Le résultat de 2. peut aussi s’obtenir en raisonnant directement sur le dual.

En effet, pour tout j ∈ H, on a

yj = −Lj + aij yi

et on voit que yj ≥ 0 quel que soit yi ≥ 0 car aij ≥ 0 et Lj ≤ 0. Par conséquent on

a une solution de base duale réalisable et yi n’est pas borné, G n’est donc pas bornée
(min G = − inf). Le problème dual admettant un optimum infini, on en déduit que le
primal n’a pas de solution réalisable (cf. correspondance primal/dual).

2. Cela se déduit de la relation 0 = xi = bi − aij xj

 MÉTHODE DU SIMPLEXE DUAL (REVISITÉE) 5

4. Exemple : solution de base initiale duale-réalisable

On considère le programme linéaire
max [F (x1 , x2 , x3 ) = −x1 − 4x2 − 4x3 ] .
(x
1 ,x2 ,x3 )
(10)  x1 + 2x2 + 2x3 ≤ 11
x1 + 3x2 + 2x3 ≥ 15
x1 , x2 , x3 ≥ 0


qui admet la forme standard suivante :

max [F (x) = −x1 − 4x2 − 4x3 ] .
 5
x∈R
(11)  x1 + 2x2 + 2x3 + e1 = 11
x1 + 3x2 + 2x3 − e2 = 15
x1 , x2 , x3 , e1 , e2 ≥ 0


On remarquera que (11) n’admet pas de solution de base réalisable évidente (on ne peut
pas choisir e2 = −15). On initialise la méthode du simplexe dual avec la solution de base
non-réalisable :  
    x1
e 11
xB = 1 = , xH = x2  = 0
e2 −15
x3
mais puisque c = (−1, −4, −4)> ≤ 0, elle est duale-réalisable.
?Itération 1. Le dictionnaire initial s’écrit
e1 = 11 − x1 − 2x2 − 2x3
e2 = −15 + x1 + 3x2 + 2x3
F = −x1 − 4x2 − 4x3
Variable sortante xs = e2 car b2 = −15 < 0.
 calcule Lk /ask pour k ∈ H tel que ask < 0.
Variableentrante xe . On
−1 −4 −4 −1
min , , = et donc xe = x1 = 15.
ask <0 −1 −3 −2 −1
On obtient la nouvelle solution de base (toujours non-réalisable)
 
    e2
e1 −4
xB = = , xH = x2  = 0
x1 15
x3
?Itération 2. On effectue le pivotage des variables entrante/sortante pour obtenir le
nouveau dictionnaire.
x1 = 15 + e2 − 3x2 − 2x3
e1 = −4 − e2 + x2
F = −15 − e2 − x2 − 2x3
Variable sortante xs = e1 car b2 = −4 < 0.
 calcule Lk /ask pour k ∈ H tel que ask < 0.
Variableentrante xe . On
−1 −1 −2 −1
min , ,  =

et donc xe = x2 = 4.
ask <0 +1 −1 0 −1
6 J.F. SCHEID

On obtient la nouvelle solution de base (réalisable)

 
    e2
x2 4
(12) xB = = , xH =  e 1  = 0
x1 3
x3
On a obtenu une solution de base réalisable (positivité des variables de base). Comme
elle est aussi duale-réalisable, elle est donc optimale et max F = −19.

5. Extension
Dans la présentation faite de la méthode, on a supposé qu’on dispose initialement
d’une solution de base duale-réalisable (ce qui sous-entend que le problème dual est bien
réalisable). On peut étendre la méthode en partant d’une solution de base qui n’est pas
duale-réalisable.
Commençons par faire les remarques suivantes.
− Si cette solution de base est réalisable alors on peut appliquer le simplexe primal
(sans phase 1).
− Si elle n’est pas réalisable au sens où elle n’est pas positive mais vérifie quand même
les contraintes Ax = b, on va voir qu’on peut encore appliquer le simplexe dual.
On suppose donc à présent qu’on a une solution de base x qui n’est ni duale-réalisable,
ni réalisable mais vérifie Ax = b (x n’est donc pas positive). On suppose donc qu’on
dispose d’une solution de base x vérifiant (4) telle que
(H1) il existe i ∈ B tel que bi ≤ 0 (x non réalisable) ;
(H2) il existe j ∈ H tel que Lj > 0 (x non duale-réalisable) ;

En appliquant la méthode du simplexe dual en partant de cette solution de base initiale,

on rencontrera une des 3 situations d’arrêt suivantes (qui sont une généralisation des
conditions d’arrêt de la section 3.2) :
Cas d’arrêt du simplexe dual.
(1) Il n’existe pas d’indice i ∈ B vérifiant (7).
Dans ce cas, on a bi ≥ 0, ∀i ∈ B i.e. b ≥ 0. La solution de base primale du
dictionnaire (4) est alors réalisable. On distingue 2 cas :
(a) Si LH ≤ 0 alors la solution de base primale est optimale (c’est la condi-
tion d’optimalité). Elle vaut
x∗B = b, x∗H = 0.
(b) S’il existe j ∈ H tel que Lj > 0, alors yj < 0 et comme b ≥ 0 on ne peut plus
diminuer G. Le problème dual n’a pas de solution réalisable. Donc dans ce
cas, le problème primal admet un optimum infini (cf. correspondance
primal/dual).
 MÉTHODE DU SIMPLEXE DUAL (REVISITÉE) 7

(2) Il n’existe pas d’indice j ∈ H vérifiant (8).

Dans ce cas, on a aij ≥ 0, ∀j ∈ H où l’indice i ∈ B est tel que bi < 0. A partir
de la relation X
xi = bi − aij xj ,
j∈H
on en déduit que xi < 0 quels que soient les xj ≥ 0. Par conséquent, le problème
primal n’a pas de solution réalisable.

Remarque. Le résultat de (2) peut s’obtenir en raisonnant directement sur le dual. En

effet, à partir de la relation
yj = −Lj + aij yi ,
pour tout j ∈ H, on distingue 2 cas.
i) Si aij > 0, ∀j ∈ H alors on aura yj ≥ 0 pour yi > 0 suffisamment grand et ceci quel
que soit le signe de Lj . Par conséquent on a une solution de base duale réalisable
et yi n’est pas borné, G n’est donc pas bornée et le problème dual admet donc
un optimum infini (min G = − inf).
ii) S’il existe j ∈ H tel que aij = 0, alors on distingue 2 cas :
— Si Lj ≤ 0 alors yj ≥ 0 quelque soit la valeur de yi . Donc G n’est donc pas
bornée, le problème dual admet un optimum infini.
— Si Lj > 0 alors yj < 0 quelque soit la valeur de yi . Donc le problème dual
n’a pas de solution réalisable.
On a montré que dans le cas 2., le problème dual admet soit un optimum infini, soit
n’a pas de solution réalisable. On en déduit (cf. correspondance primal/dual) que dans
ce cas, le primal n’a pas de solution réalisable.

5.1. Simplexe dual : s’affranchir de la phase 1. On suppose qu’on dispose d’une

solution de base initiale qui n’est pas nécessairement réalisable, ni duale-réalisable. On
peut toujours utiliser une méthode de simplexe primal ou dual directement, sans avoir
recours à une phase d’initialisation avec variables artificielles (phase 1). En fonction de
l’état de la solution de base initiale, on a le schéma de procédure suivant.

solution de base initiale réalisable non réalisable

duale-réalisable solution optimale simplexe dual (a)
non duale-réalisable simplexe primal simplexe dual (b)

Table 1. Procédure primal/dual en fonction de l’état de la solution de

base initiale

La situation (a) correspond à la méthode duale présentée à la Section 3 quand la

solution de base initiale est duale-réalisable (mais non-réalisable). Dans la situation (b),
les hypothèses (H1) et (H2) sont satisfaites.
8 J.F. SCHEID

Enfin, on remarquera qu’avec un PL sous forme standard

h i
max F (x) = c> x
x

Ax ≤ b
x≥0
on peut choisir comme solution de base initiale xB = e = b et xH = 0 où e sont les
variables d’écart et ceci quels que soient les signes des composantes de b. Le schéma
primal/dual ci-dessus s’applique alors avec cette solution de base initiale. Cette solution
de base initiale est réalisable si et seulement si b ≥ 0, elle est duale-réalisable si et
seulement si c ≤ 0.

6. Exemples
On considère plusieurs exemples correspondants à la situation (b) de la Table 1, c’est-
à-dire avec une solution de base initiale ni réalisable ni duale-réalisable. On donne 3
exemples pour chacune des situations d’arrêt établies précédemment.

6.1. Solution réalisable optimale. On considère le programme linéaire

max [F (x1 , x2 , x3 ) = 3x1 + 4x2 + x3 ] .
(x
1 ,x2 ,x3 )
(13)  x1 + 2x2 + 2x3 ≤ 8
x1 + 2x2 + 3x3 ≥ 9
x1 , x2 , x3 ≥ 0


qui admet la forme standard suivante :

max [F (x) = 3x1 + 4x2 + x3 ] .
x∈R5

(14)  x1 + 2x2 + 2x3 + e1 = 8
x1 + 2x2 + 3x3 − e2 = 9
x1 , x2 , x3 , e1 , e2 ≥ 0


On remarquera que (14) n’admet pas de solution de base réalisable évidente (on ne peut
pas choisir e2 = −9). On initialise la méthode du simplexe dual avec la solution de base
non-réalisable :  
    x1
e1 8
xB = = , xH = x 2  = 0

e2 −9
x3
Cette solution de base n’est pas non plus duale-réalisable car c = (3, 4, 1)> > 0. On est
donc bien dans le cadre des hypothèses (H1) et (H2).
?Itération 1. Le dictionnaire initial s’écrit
e1 = 8 − x1 − 2x2 − 2x3
e2 = −9 + x1 + 2x2 + 3x3
F = 3x1 + 4x2 + x3
Variable sortante xs = e2 car b2 = −9 < 0.
Variable entrante xe . On calcule Lk /ask pour k ∈ H tel que ask < 0.
 MÉTHODE DU SIMPLEXE DUAL (REVISITÉE) 9
 
3 4 1
min , , = −3 et donc xe = x1 = 9.
ask <0 −1 −2 −3
On obtient la nouvelle solution de base (toujours non-réalisable)
 
    e2
e1 −1
xB = = , xH = x2  = 0
x1 9
x3
?Itération 2. On effectue le pivotage des variables entrante/sortante pour obtenir le
nouveau dictionnaire.
x1 = 9 + e2 − 2x2 − 3x3
e1 = −1 − e2 + x3
F = 27 + 3e2 − 2x2 − 8x3
Variable sortante xs = e1 car b2 = −1 < 0.
 calcule Lk /ask pour k ∈ H tel que ask < 0.
Variableentrante xe . On
3 −2 −8 −8
min , ,
= = 8 et donc xe = x3 = 1.
ask <0 +1 0 −1 −1
On obtient la nouvelle solution de base (réalisable)
 
    e2
x3 1
(15) xB = = , xH =  x 2  = 0
x1 6
e1
?Itération 3. On obtient le dictionnaire.
x3 = 1 + e 2 + e 1
x1 = 6 − 2e2 − 2x2 − 3e1
F = 19 − 5e2 − 2x2 − 8e1
Tous les coûts réduits sont négatifs (LH ≤ 0) et la solution de base (15) est réalisable
(b ≥ 0). Elle est donc optimale (cas (1a) des situations d’arrêt du simplexe dual).

6.2. Optimum inifini. On considère le programme linéaire

max [F (x1 , x2 ) = x1 + 3x2 ] .
(x
1 ,x2 )
x + x2 ≥ 3
 1

(16)

x1 − 2x2 ≥ 5
 −2x1 + x2 ≤ 5

x1 , x2 ≥ 0


qui admet la forme standard suivante :

max [F (x) = x1 + 3x2 ] .
x∈R5

x + x2 − e1 = 3
 1

(17)

x1 − 2x2 − e2 = 5

 −2x 1 + x2 + e 3 = 5
x1 , x2 , e1 , e2 , e3 ≥ 0

10 J.F. SCHEID

On initialise la méthode du simplexe dual avec la solution de base non-réalisable :

   
e1 −3  
x1
xB = e2 = −5 , xH =
    =0
x2
e3 5
Cette solution de base n’est pas non plus duale-réalisable car c = (1, 3)> > 0. On est
donc bien dans le cadre des hypothèses (H1) et (H2).
?Itération 1. Le dictionnaire initial s’écrit
e1 = −3 + x1 + x2
e2 = −5 + x1 − 2x2
e3 = 5 + 2x1 − x2
F = x1 + 3x2
Variable sortante xs = e2 car b2 = −5 = min(−3, −5) < 0.
xe . On calcule Lk /ask pour k ∈ H tel que ask < 0.
Variableentrante 
1 3 1
min ,  = et donc xe = x1 = 5.
ask <0 −1  +2 −1
On obtient la nouvelle solution de base (réalisable)
   
e1 2  
e2
xB = x 1 = 5 , xH =
    =0
x2
e3 15
?Itération 2. Après pivotage des variables entrante/sortante on obtient le dictionnaire
e1 = 5 + e2 + 2x2
e2 = 2 + e2 + 3x2
e3 = 15 + 2e2 + 3x2
F = 5 + e2 + 5x2
On a b = (5, 2, 15)> ≥ 0 et LH = (1, 5)> donc LH n’est pas négatif et on est dans le cas
(1b) des situations d’arrêt du simplexe dual. Par conséquent, le problème primal admet
un optimum infini.
6.3. Pas de solution de base réalisable. On considère le programme linéaire
max [F (x1 , x2 ) = x1 − x2 ] .
(x
1 ,x2 )
x + 2x2 ≤ 5
 1

(18)

2x1 + x2 ≤ 6

 x 1 + x2 ≥ 4
x1 , x2 ≥ 0


qui admet la forme standard suivante :

max [F (x) = x1 − x2 ] .
 5
x∈R
x + 2x2 + e1 = 5
 1

(19)

2x1 + x2 + e2 = 6

 x1 + x2 − e3 = 4
x1 , x2 , e1 , e2 , e3 ≥ 0

 MÉTHODE DU SIMPLEXE DUAL (REVISITÉE) 11

On initialise la méthode du simplexe dual avec la solution de base non-réalisable :

   
e1 5  
x1
xB = e2  =  6  , xH = =0
x2
e3 −4
Cette solution de base n’est pas non plus duale-réalisable car c = (1, −1)> n’est pas
négatif. On est donc bien dans le cadre des hypothèses (H1) et (H2).
?Itération 1. Le dictionnaire initial s’écrit
e1 = 5 − x1 − 2x2
e2 = 6 − 2x1 − x2
e3 = −4 + x1 + x2
F = x1 − x2
Variable sortante xs = e3 car b3 = −4 < 0.
xe . On calcule Lk /ask pour k ∈ H tel que ask < 0.
Variableentrante 
1 −1 1
min , = et donc xe = x1 = 4.
ask <0 −1 −1 −1
On obtient la nouvelle solution de base (toujours non-réalisable)
   
e1 1  
e3
xB = e2 = −2 , xH =
    =0
x2
x1 4
?Itération 2. Après pivotage des variables entrante/sortante on obtient le dictionnaire
x1 = 4 + e 3 − x2
e1 = 1 − e3 − x2
e2 = −2 − 2e3 + x2
F = 4 + e3 − 2x2
Variable sortante xs = e2 car b3 = −2 < 0.
 xe . On calcule Lk /ask pour k ∈ H tel que ask < 0.
Variableentrante
1 −2 −2
min  , = = 2 et donc xe = x2 = 2.
ask <0 2 −1 −1
On obtient la nouvelle solution de base (toujours non-réalisable)
   
e1 −1  
e
xB = x 2 =
   2 , xH = 3 = 0

e2
x1 2
?Itération 3. Après pivotage des variables entrante/sortante on obtient le dictionnaire
x2 = 2 + e2 + e3
x1 = 2 − e2 − e3
e1 = −1 − e2 − 3e3
F = −2e2 − 3e3
Variable sortante xs = e1 car b3 = −1 < 0.
12 J.F. SCHEID

Variable entrante xe . On a (ask )k = (1, 1)> ≥ 0 donc il n’existe pas de coefficient ask < 0.
On est dans le cas (2) des situations d’arrêt. Le problème primal n’admet donc pas de
solution de base réalisable.

Références
[1] Bazaraa M. S., Jarvis J. J., Sherali H. D., Linear Programming and Network Flows, 4th Edition,
Wiley, 2010.
[2] Banciu M., Dual simplex. Wiley Encyclopedia of Operations Research and Management Science
(2010).
[3] Beale E. M. L. An alternative method for linear programming. Mathematical Proceedings of the
Cambridge Philosophical Society, 50(4), 513-523. (1954)
[4] Lemke C.E., The dual method of solving the linear programming problem, Naval Research Logistics
Quarterly, John Wiley & Sons, vol. 1(1), pages 36-47. (1954).