1 / 45

Chapitre 3: Méthode du simplexe

Hamed Sidi Nounou

Institut Universitaire Professionel, Licence LgTr

23 Avril 2020
 2 / 45
Programme linéaire sous forme standard

On considère le programme linéaire sous forme standard

suivant :
min c> x
s.c. Ax = b (1)
x ≥ 0.
où x ∈ Rn le vecteur des variables, c ∈ Rn , b ∈ Rm sont deux
vecteurs donnés, A est une matrice m × n donnée, m ≤ n, et
rg(A) = m.
On notera les colonnes de A par [A1 , A2 , · · · , An ], et on pose
l'ensemble convexe des solutions admissibles du programme
linéaire (1)
X := {x ∈ Rn | Ax = b, x ≥ 0}
 3 / 45
Méthode du simplexe

Dans les exemples qu'on a vu dans le deuxième chapitre, nous

avons pu résoudre les problèmes assez facilement car il n'y avait
que 2 variables, et donc une représentation graphique était
possible(méthode graphique). Mais la plupart des problèmes
réels le nombre de variables peuvent dépasser trois variables.
A la n des années 40, le mathématicien G. B. Dantzig
développa une méthode systématique de résolution de ces
programmes linéaires. Elle est connue sous le nom de méthode
du simplexe.
Principe de la méthode :
L'idée essentielle de cet algorithme consiste à trouver d'abord
une solution de base admissible, puis à calculer, à partir de
celle-ci, une autre solution, qui améliore la fonction
économique(objectif).
 4 / 45
Base et Solution de base réalisable

On introduit la notation suivante : pour une partie

B ⊆ {1, · · · , n} (l'ensemble d'indices des colonnes de A ) à m
éléments, on note AB la sous-matrice de A d'ordre m réduite
aux colonnes indicées par les éléments de B , et on note N le
complémentaire de B dans {1, · · · , n}.
N = {i ∈ {1, · · · , n} | i ∈
/ B}

L'ensemble des indices B est appelé base si la matrice AB est

inversible. Les variables d'indices de la base B sont notées par
xB ∈ Rm sont appelées variables en base et les autres
variables sont notées par xN ∈ Rn−m sont appelées variables
hors-base.
 5 / 45
Base et Solution de base réalisable

Exemple : Si la matrice A est donnée par :

 
1 2 2 1 3
A = 2 1 0 5 1 ,
2 0 1 4 3

et l'ensemble d'indices B est donné par B = {1, 3, 4} (les

colonnes 1,3,et 4 de A). Alors N = {2, 5}.
Dans ce cas m = 3, alors la matrice AB est donnée par :
 
1 2 1
AB = 2 0 5 et det(AB ) = 29 6= 0
2 1 4

Donc AB est inversible, ainsi B = {1, 3, 4} est une base, de plus

xB = {x1 , x3 , x4 } les variables de base, et xN = {x2 , x5 } les
variables hors-base.
 6 / 45
Base et Solution de base réalisable

On réécrit l'égalité Ax = b sous la forme

 
xB
(AB AN ) = AB xB + AN xN = b,
xN

où N est le complémentaire de B dans {1, · · · , n}.

Dans ce cas, on peut réécrire le système Ax = b dans la base B
en transformant l'écriture précédente en multipliant par A−1
B

xB + A−1 −1
B AN x N = AB b

La solution x du système Ax = b obtenue en posant

B b et xN := 0
xB := A−1

est appelée solution de base.

On dit que x est une solution de base réalisable si A−1
B b ≥ 0.
 7 / 45
Base et Solution de base réalisable

On suppose qu'on connaît au départ une base réalisable B .

L'algorithme du simplexe commence par réécrire le programme
(1) sous la forme équivalente
−1 > −1
min c> >
B AB b + (cN − cB AB AN )xN
s.c. xB + A−1 −1
B AN x N = AB b
x ≥ 0.

(cette équivalence est obtenue en remplaçant xB par son

expression xB = A−1 B b − AB AN xN ).
−1

On dénit c̄N := cN − cB A−1 B AN , le vecteur des coûts réduits.

> >

Il faut bien noter que ce programme et le programme (1) sont

complètement équivalents. L'avantage de cette forme, c'est
qu'on peut directement lire la valeur de la solution basique
réalisable associée à B : c'est le terme constant c>
B AB b de la
−1

fonction objectif. En eet, la solution basique réalisable associée

à B est xB = A−1 B b et xN = 0.
 8 / 45
Base et Solution de base réalisable

Théorème : Identication des sommets

Toute solution de base x telle que xB := A−1
B b et xN := 0 est un
sommet du polytope X .

Démonstration.

Par l'absurde. On suppose que le point x n'est pas un sommet de X.

x peut alors s'écrire x = λy + (1 − λ)z avec 0 < λ < 1, y et z ∈ X,
y 6= x , z 6= x.
En décomposant suivant les composantes
  B et N :
xB = λyB + (1 − λ)zB y ∈ X ⇒ yN ≥ 0
avec
xN = λyN + (1 − λ)zN z ∈ X ⇒ zN ≥ 0
Or xN = 0 = λyN + (1 − λ)zN et 0 < λ < 1 ⇒ yN = 0 et zN = 0. A

partir de y, z ∈ X on a

AB yB + AN yN = b ⇒ yB = A−1
 
B b ⇒ yB = xB
AB zB + AN zN = b ⇒ zB = A−1B b zB = xB
On obtient y = z = x en contradiction avec l'hypothèse que x n'est

pas un sommet de X .
 9 / 45
Base et Solution de base réalisable
Pourquoi la méthode du simplexe ?

Nous savons que la solution optimale du problème

d'optimisation linéaire (1) se trouve en un sommet de l'ensemble
convexe des solutions admissibles X (un théorème du chapitre
2). De plus, selon le théorème précédent, les sommets sont
étroitement reliés aux solutions de base admissibles c-à-d une
solution de base x∗ correspond à un sommet de X .
Par conséquent, il sut de calculer tous les sommets de X pour
trouver la solution optimale. Mais le nombre de sommets est de
l'ordre m!(n−m)!
n!
ce qui est beaucoup trop pour des n et m
relativement grands. C'est pour cette raison la méthode du
simplexe est venue pour éviter de calculer tous les sommets. A
partir d'un sommet donné, la méthode calculera une suite de
sommets adjacents l'un par rapport au précédent et qui
améliore la fonction-objectif. Autrement dit, on se déplace
d'une solution de base admissible à une autre solution de base
admissible(Les solutions non admissibles ne sont pas examinées).
 10 / 45
Conditions d'optimalité

Théorème
Soit B une base réalisable. Si c̄N ≥ 0, alors B est optimale.

Démonstration.
Soit x ∈ X . Donc Ax = b et x ≥ 0. En écrivant Ax = AB xB + AN xN , on
obtient xB = A−1
B b − AB AN xN . On a
−1

z(x) = cTB xB + c>

N xN

= c> −1 > −1 >

B AB b − cB AB AN xN + cN xN

= c> −1 > > −1

B AB b + (cN − cB AB AN )xN

= c> −1
B AB b + c̄N xN

Puisque x ∈ X alors 0. Et puisque c̄N ≥ 0, alors z(x) ≥ c>

 xN≥ −1 B AB b.
−1

xB AB b
Soit x∗ = = la solution associée à la base B . Alors
0Rn−m 0Rn−m

z(x∗ ) = cTB xB + c> > −1

N xN = cB AB b ≤ z(x) ∀x ∈ X

et x∗ est solution de base optimale.

 11 / 45
Conditions d'optimalité

Corollaire
Soit B0 une base réalisable et x0 la solution de base
correspondante. S'il existe un indice j tel que c̄j < 0, alors
1 soit l'optimum de z c'est −∞,
2 soit il existe une autre base B1 et une autre solution de
base x1 tel que z(x1 ) < z(x0 ) (x1 est meilleure que x0 ).
Démonstration.
A−1
 
Soit x0 = B0 b la solution de base associée à B0 et j tel que c̄j < 0. Soit
0Rn−m
 
xB 0
x=
x N0
, avec xN0 = θej et θ > 0, (ej nul sauf la composante j égale 1 ) . On a
Ax = b ⇒ xB0 = A−1B0 b − AB0 AN0 xN0 = AB0 b − θAB0 AN0 ej .
−1 −1 −1

>
z(x) = cT
B0 xB0 + cN0 xN0
−1 −1
= c> > >
B0 AB0 b − cB0 AB0 AN0 xN0 + cN0 xN0
−1 −1
= c> > >
B0 AB0 b + (cN0 − cB0 AB0 AN0 )xN0
−1
= c> 0
B0 AB b + θc̄N0 ej = z(x ) + θc̄j
 12 / 45
Conditions d'optimalité

Deux cas se présentent :

1 toutes les composantes de A−1 B0 AN0 ej = AB0 aj sont négatives ou nulles.
−1

Alors xB0 ≥ 0 pour tout θ ≥ 0. Puisque z(x) = z(x0 ) + θc̄j alors le

minimum de z c'est −∞.
2 une composante de A−1 B0 aj > 0. Soient xB0 les composantes de xB0 , b̄i les
i

composantes de AB0 b et āij les composantes de A−1

−1
B0 aj , pour i = 1, · · · , m.
Alors pour tout i = 1, · · · , m

b̄i
xiB0 ≥ 0 ⇐⇒ b̄i − θāij ≥ 0 ⇐⇒ θ ≤ .
āij
 
b̄i
Donc il faut donc que θ ≤ min | āij > 0 . Pour ces valeurs de θ > 0,
i∈B0 āij
le point x déni
 précédemment  est meilleur pour z . Le meilleur point étant
b̄i b̄i
pour θ = min | āij > 0 . Si θ = ā 0 alors la composante i0 de x est
i∈B0 āij i0 j

nulle puisque que xi = b̄i0 − θāi0 j = 0 alors que xj = θ > 0. Le point x1 = x

est alors une solution de base réalisable associée à la base B1 obtenue en
remplaçant dans la base B0 la colonne ai0 par la colonne aj . Et d'après ce
qui précède,
z(x1 ) = z(x0 ) + θc̄j < z(x0 ). (x1 est meilleure que x0 ).
 13 / 45
Conditions d'optimalité

La variable xj de la démonstration précédente est appelée

variable entrante (elle entre en base suivante B1 ), et la
variable xi0 est appelée variable sortante (elle sort de base
suivante B1 ).
Pour passer de la base B à une base adjacente B 0 meilleure, on
choisit une variable hors-base xj (j ∈/ B ) qui va entrer dans la
nouvelle base B 0 , cette variable appelée variable entrante, et
on détermine une variable de base xi (i ∈ B ) qui va quitter la
base appelée variable sortante.
 14 / 45
Conditions d'optimalité

Remarque
Si deux indices vérient θ = āii0j = āii1j , alors la base B1 va
b̄ b̄
1
0 1
être dégénérée ( xB1 comporte des composantes nulles)
puisque xi1 = 0, avec i1 un indice de base, et donc A−1 B1 b a
au moins une composante nulle.
2 Si B0 était dégénérée, alors on aura θ = 0 et le changement
de base de B0 à B1 ne fait pas varier z ; z(x0 ) = z(x1 ).
3 Le corollaire précédent montre que si inf z(x) > −∞, alors
x∈X
en partant d'une base B0 réalisable et de la solution de base
correspondante, on peut construire, en l'absence de
dégénérescence, une suite de bases réalisables dont les
solutions de bases correspondantes font diminuer z
strictement. Après un nombre ni d'étapes on trouvera
l'optimum.
 15 / 45
Conditions d'optimalité

Algorithm 1 Simplexe
1. Choisir une base réalisable B0 et poser k = 0.
2. Al'étape
 k on a une base B et la solution de base correspondante
A−1
B b . On calcule b̄ = A−1 b
x= B et c̄N = c> > −1
N − cB AB AN .
0
3. Si c̄N ≥ 0, STOP, le minimum est atteint. Sinon il existe un indice e
tel que c̄e < 0. Soit ae la colonne de A d'indice e. Calculer āe := A−1
B ae .

Si āe ≤ 0, STOP ; le minimum égal à −∞.

Sinon, calculer
 
b̄s b̄i
x̂e = := min | āie > 0
āse i∈B āie

4. La variable xe prend la valeur x̂e et rentre en base, et la variable xs

sort de la base. On construit ensuite la nouvelle base réalisable en faisant
le pivotage.
5. Faire k ←− k + 1 et retourner à 2.

(on va voir cette technique du pivotage dans la suite du document !)

 16 / 45
Méthode des tableaux : Algorithme du simplexe

Le programme (1) est équivalent au programme suivant

min z
s.c. Ax = b
( en posant z = c> x)
c> x − z = 0
x ≥ 0.
On peut représenter la dernière forme par le tableau suivant
0 b1
.. ..
A . .
0 bm
c̄> −1 0
On écrit le problème sous forme canonique dans la base B
−1

min z = z̄ + c̄>
N xN
 b̄ = AB b
xN ≥0 avec z̄ = c> b̄ (2)
s.c. xB = b̄ − A−1 ≥0  > B>
B AN xN
−1
c̄N = cN − c>
B AB AN
 17 / 45
Méthode des tableaux : Algorithme du simplexe


 xB = b̄
La solution de base associée à B est : xN = 0
z = z̄

On peut représenter le programme précédent (3) par le tableau
suivant appelé tableau du simplexe :
x SB x1 ··· xj ··· xn SB
xB A−1
B A b̄ = xB A−1
B A1 ··· A−1
B Aj ··· A−1
B An b̄
-1 c̄> −z̄ -1 c̄1 ··· c̄j ··· c̄n −z̄

où Aj es la j ème colonne de A, c̄> est le vecteur des coûts

N − cB AB AN , et −z̄ est l'opposé du
réduits c̄B = 0 et c̄N = c> > −1

coût.
Explication du contenu de tableau : on met dans la 1ère colonne du tableau les variables
de base xB , dans la dernière case on écrit −1 c-à-d lorsque on arrive à la solution optimale on
prend l'opposé de la valeur situe dans la dernière case de tableau à droite. On met dans la
2ème colonne toutes les variables x = (x1 , · · · , xn ), puis A−1
B
A, après c̄> . Dans la dernière

colonne on met la solution de base (SB) b̄, et −z̄ est l'opposé la valeur de la solution de base.
 18 / 45
Méthode des tableaux : Algorithme du simplexe

Remarques
Tout coecient négatif de c̄> N peut faire oce de variable
entrante. D'après une règle de Dantzig on choisit la
variable hors-base de coût réduit le plus négatif (plus forte
descente).
Soit āj la colonne de A−1 B AN correspondant à la variable
entrante. On regarde les coecients strictement positifs de
āj et parmi ceux-là, on choisit la variable sortante xi telle
que āb̄iji soit le plus petit possible.
 19 / 45
Méthode des tableaux : Algorithme du simplexe

Exercice
Soit le programme linéaire suivant :
min −10x1 − 12x2 − 12x3
s.c. x1 + 2x2 + 2x3 ≤ 20
2x1 + x2 + 2x3 ≤ 20
2x1 + 2x2 + x3 ≤ 20
x1 , x2 , x3 ≥ 0.
( simplexe a besoin toujours d'écrire le PL sous forme standard)

On l'écrit sous forme standard en introduisant les variables

d'écart x4 , x5 , x6 ≥ 0.
min −10x1 − 12x2 − 12x3
s.c. x1 + 2x2 + 2x3 + x4 = 20
2x1 + x2 + 2x3 + x5 = 20
2x1 + 2x2 + x3 + x6 = 20
x1 , x2 , x3 , x4 , x5 , x6 ≥ 0.
 20 / 45
Méthode des tableaux : Algorithme du simplexe

On considère B = {4, 5, 6}, la sous-matrice de A d'ordre 3

réduite aux colonnes 4, 5, et 6 (les indices de B ) est
 
1 0 0
I3 = 0 1 0
0 0 1

c'est une matrice identité d'ordre 3, ainsi elle est inversible,

donc B est une base. Les variables de base sont x4 , x5 et x6 , et
les variables hors-base sont x1 , x2 et x3 . Puisque
 
20
−1
I3 b = b = 20 ≥ 0

20

Donc B est une base réalisable. Alors on va commencer à

tracer le premier tableau de simplexe.
 21 / 45
Méthode des tableaux : Algorithme du simplexe

1er tableau de simplexe :

xB \x x1 x2 x3 x4 x5 x6 SB Base initiale
x4 1 2 2 1 0 0 20 admissible
x5 2 1 2 0 1 0 20 xB = (x4 , x5 , x6 )
x6 2 2 1 0 0 1 20 = (20, 20, 20)
-1 −10 −12 −12 0 0 0 0

On a c̄> N = −10, −12, −12 . La solution de base n'est pas

optimale : il y a des coûts réduits négatifs ( directions de

descente). On va choisir −12 le plus négatif (règle de Dantzig mais on
peut choisir −10 et on va arriver à la même solution optimale vers la n).
La variable x2 (ou x3 ) va entrer en base. On choisit d'entrer par
exemple la variable x2 (on hachure la colonne de x ) 2

xB \x x1 x2 x3 x4 x5 x6 SB
x4 1 2 2 1 0 0 20
x5 2 1 2 0 1 0 20
x6 2 2 1 0 0 1 20
-1 −10 −12 −12 0 0 0 0
 22 / 45
Méthode des tableaux : Algorithme du simplexe

On cherche la variable qui va sortir de base :

x4 : b̄4
ā42
= 20
2
= 10
x5 : b̄5
ā52
= 20
1
= 20
x6 : b̄6
ā62
= 20
2
= 10
On choisit la variable qui correspond au plus petit quotient,
dans ce cas on peut sortir x4 ou x6 . x4 par exemple
xB \x x1 x2 x3 x4 x5 x6 SB
x4 1 2 2 1 0 0 20
x5 2 1 2 0 1 0 20
x6 2 2 1 0 0 1 20
-1 −10 −12 −12 0 0 0 0

L'intersection de la colonne de variable qui entre en base x2 et

la ligne de variable qui sort de base x4 est appelé le pivot
ā42 = 2 (élément en jaune).
 23 / 45
Méthode des tableaux : Algorithme du simplexe
Pivotage

Pour remplir le 2ème tableau du simplexe on suit les étapes de

pivotage suivantes :
Dans la 1ère colonne on remplace x4 par x2 (et on garde x5
et x6 ).
On divise la ligne de pivot par le pivot.
On met des zéros au-dessus et au-dessous de pivot.
Si la ligne de pivot rencontre une colonne en un 0, alors la
colonne est inchangée.
Si une ligne rencontre la colonne de pivot en un 0, alors la
ligne est inchangée.
xB \x x1 x2 x3 x4 x5 x6 SB
1 1
x2 2
1 1 2
0 0 10
x5 . 0 . . . . .
x6 . 0 . . . . .
-1 . 0 . . . . .
 24 / 45
Méthode des tableaux : Algorithme du simplexe
Pivotage

Pour continuer le remplissage de 2ème tableau, o fait l'opération

de pivotage suivante :
pour calculer l'élément d'une case, on se déplace suivant la ligne
de l'élément jusqu'à ce qu'on touche la colonne de pivot
(élément de la colonne de pivot), et se déplace suivant la colonne
de l'élément concerné jusqu'à ce qu'on touche la ligne de pivot
(élément de la ligne de pivot). La valeur de l'élément concerné
dans le nouveau tableau est :
(élément de la colonne de pivot) × (élément de la ligne de pivot)
élément concerné−
pivot
 25 / 45
Méthode des tableaux : Algorithme du simplexe
Pivotage

si i = s
( āsj
ā0ij = āse
āij −
āie āsj
āse si i 6= s

si i = s
(
b̄s
b̄0i = āse
b̄i − āie b̄s
āse si i 6= s

āsj c̄e
c̄0j = c̄j −
āse
 26 / 45
Méthode des tableaux : Algorithme du simplexe
Pivotage

En appliquant la même opération pour les autres éléments, on

obtient le 2ème tableau de simplexe suivant :

xB \x x1 x2 x3 x4 x5 x6 SB
1 1
x2 2
1 1 2
0 0 10
3
x5 2
0 1 −1 1 0 10
x6 1 0 −1 −1 0 1 0
-1 −4 0 0 6 0 0 120

On a c̄>
N = −4, 0, 6 . La solution de base n'est pas optimale : il

y a un élément des coûts réduits négatif (−4). La variable x1 va

entrer en base.
 27 / 45
Méthode des tableaux : Algorithme du simplexe

On suit les mêmes étapes précédentes pour choisir la variable

qui va sortir de base.
xB \x x1 x2 x3 x4 x5 x6 SB b̄2
= 10
1 1 ā21 1 = 20
x2 2
1 1 2
0 0 10 2
x5 3
2
0 1 −1 1 0 10 b̄5
ā51
= 10
3 = 3
20
La
x6 1 0 −1 −1 0 1 0 b̄6 0
2

-1 −4 0 0 6 0 0 120 ā61
= 1
=0
variable x6 sort de base.

D'après les opérations de pivotage on obtient le 3ème tableau du

simplexe :
xB \x x1 x2 x3 x4 x5 x6 SB b̄2 10 20
3 −1 ā23
= 3 = 3
x2 0 1 2
1 0 2
10 2
5 1
x5 0 0 2 2
1 − 32 10 b̄5
ā51
= 10
5 = 20
5
x1 1 0 −1 −1 0 1 0 2

-1 0 0 −4 2 0 4 120
x3 entre en base et x5 sort de base.
 28 / 45
Méthode des tableaux : Algorithme du simplexe

4ème tableau du simplexe :

xB \x x1 x2 x3 x4 x5 x6 SB
−13 −3 2
x2 0 1 0 2 5 5
4
2 −3
x3 0 0 1 5 5 5
4
2 2
x1 1 0 0 4 5 5
4
-1 0 0 0 22 8
5
8
5
136

On a On a c̄> N = 22, 5 , 5 ≥ 0 alors la solution est optimale :

8 8

x∗ = (4, 4, 4, 0, 0, 0)> et z ∗ = −136.

La
 solution
  de  notre problème de départ est :
x1 4
x2  = 4 et sa valeur minimale égale à −136.
x3 4
 29 / 45
Méthode des deux phases

On considère le programme linéaire sous forme standard

suivant :
min c> x
s.c. Ax = b (3)
x ≥ 0.
où x ∈ Rn le vecteur des variables, c ∈ Rn , b ∈ Rm sont deux
vecteurs donnés, A est une matrice m × n donnée, m ≤ n.

Pour résoudre ce problème en utilisant la méthode du simplexe

nécessite une base initiale admissible (B0 ) mais cette solution
de base admissible de départ :
n'est pas toujours connue a priori.
ou certains problèmes n'admettent pas de solution
admissible, donc il est impossible de trouver une base de
départ.
 30 / 45
Technique pour trouver une solution réalisable : Via un problème auxilliaire
Cas où le Pl est sous forme canoniqe

Cas particulier : si le programme linéaire est sous forme

canonique
min c> x
s.c. Ax ≤ b
x ≥ 0.
où x ∈ Rn le vecteur des variables, c ∈ Rn , b ∈ Rm sont deux
vecteurs donnés, A est une matrice m × n donnée.

Si b ≥ 0, alors l'ajout des variables d'écart e fait apparaître une

sous-matrice identité dont les colonnes forment une base
réalisable naturelle de départ. En eet,
min c> x
s.c. Ax + e = b
x, e ≥ 0.
 31 / 45
Technique pour trouver une solution réalisable : Via un problème auxilliaire

 

x
Ax + e = b ⇔ A I =b
e
 
x
les variables sont ∈ Rn+m , x = (x1 , · · · , xn ) et
e
e = (xn+1 , · · · , xn+m ).
Alors on peut considérer B = {n + 1, · · · , n + m} (les indices des
variables d'écart ), et la matrice associée à cette base est AB = Im ,
ainsi que AB est inversible (l'identité I est inversible ) A−1
B = Im = Im .
−1

De plus AB b = Im × b = b ≥ 0 (car b ≥ 0), donc B est une base

−1

réalisable, et la solution de base réalisable est

 
∗ 0Rn
x =
b

A ce niveau on peut démarrer l'algorithme de simplexe. (tracer le

premier tableau)
 32 / 45
Technique pour trouver une solution réalisable : Via un problème auxilliaire

Si ce n'est pas le cas (le problème n'est pas sous forme canonique ou b  0 ), par
exemple le problème est dénie comme (3), dans ce cas on va
passer par une phase préliminaire (phase I) pour construire une
base initiale. Pour ce faire, on considère un problème auxiliaire
min 0> x + e> y
s.c. Ax + y = b (P La )
x, y ≥ 0.

où e> = (1, · · · , 1) vecteur unitaire de Rm ;

m
X
>
e y = y1 + · · · + ym = yi
i=1

x les n variables du problème initial (3), et y les m variables

auxiliaires appelées variables articielles (une variable par
contrainte).
 33 / 45
Technique pour trouver une solution réalisable : Via un problème auxilliaire

Théorème
le système (3) a une solution réalisable x0 si et seulement si le
point (x0 , 0) est solution optimale du programme (P La ) et son
coût optimal est nul ( = 0).

Démonstration.
Soit x0 une solution de (3). Alors le point (x0 , 0) avec y = 0
vérie Ax + y = b, de plus, c'est une solution optimale du
problème (P La ) car la fonction objective e> y = e> 0 = 0 ≥ 0.
Vice-versa, si le point (x0 , 0) est solution optimale du problème
(P La ), il vérie Ax0 + 0 = b donc Ax0 = b, ainsi x0 est une
solution réalisable de (3).
 34 / 45
Technique pour trouver une solution réalisable : Via un problème auxilliaire

Remarques :
On peut supposer b ≥ 0(au besoin en multipliant les
contraintes égalité par −1).
Après la résolution de (P La ) les variables y sont nulles à
l'optimum. Elles sont :
soit hors base ( B est réalisable pour (3))

soit en base (solution dégénérée)

Pour obtenir une base admissible du problème (3) qui ne

contienne que des variables x, il faut échanger les variables
y en base par des pivotages avec des variables x. Soit ās
une colonne de Ā hors-base et ār une une colonne de AB
associée à une variable articielle.
Pour pouvoir remplacer la colonne ār par la colonne ās tout
en gardant AB réalisable, il faut et il sut que ārs 6= 0.
 35 / 45
Technique pour trouver une solution réalisable : Via un problème auxilliaire

Après l'échange entre les colonnes articielles et non articielles

(quand ceci est possible), on aura deux cas :

La dernière base ne contient aucune variable articielle.

Elle est donc réalisable pour (3).

La dernière base contient encore des variables articielles.

Dans ce cas le rang de A est strictement inférieur à m
(présence des contraintes redondantes).
 36 / 45
Technique pour trouver une solution réalisable : Via un problème auxilliaire

Exemple
On considère le programme linéaire suivant :
min x1 + x2 + x3
s.c. x1 + 2x2 + 3x3 = 3
−x1 + 2x2 + 6x3 = 2
4x2 + 9x3 = 5
3x3 + x4 = 1
x1 , x2 , x3 , x4 ≥ 0.
On introduit les variables articielles y1 , y2 , y3 et y4 positives, on obtient le
problème auxiliaire
min y1 + y2 + y3 + y4
s.c. x1 + 2x2 + 3x3 + y1 = 3
−x1 + 2x2 + 6x3 + y2 = 2
4x2 + 9x3 + y3 = 5
3x3 + x4 + y4 = 1
x1 , x2 , x3 , x4 , y1 , y2 , y3 , y4 ≥ 0.
 37 / 45
Technique pour trouver une solution réalisable : Via un problème auxilliaire

Le tableau initial du simplexe pour le problème auxiliaire (P La )

B \ x, y x1 x2 x3 x4 y1 y2 y3 y4 SB
y1 1 2 3 0 1 0 0 0 3
y2 −1 2 6 0 0 1 0 0 2
y3 0 4 9 0 0 0 1 0 5
y4 0 0 3 1 0 0 0 1 1
−1 0 −8 −21 −1 0 0 0 0 −11

y \ x, y x1 x2 x3 x4 y1 y2 y3 y4 SB
3
y1 1 2 3 0 1 0 0 0 3 3
=1
2
y2 −1 2 6 0 0 1 0 0 2 6
= 13
5
y3 0 4 9 0 0 0 1 0 5 9
= 0.55
1
y4 0 0 3 1 0 0 0 1 1 3
= 0.33
−1 0 −8 −21 −1 0 0 0 0 −11

Solution de base non optimale : coûts réduits négatifs

c̄N = (0, −8, −21, −1) (= directions de descente)
Variable entrante : x3
Variable sortante : y4
 38 / 45
Technique pour trouver une solution réalisable : Via un problème auxilliaire

Le 2ème tableau de (P La )
B \ x, y x1 x2 x3 x4 y1 y2 y3 y4 SB
y1 1 2 0 −1 1 0 0 −1 2
y2 −1 2 0 −2 0 1 0 −2 0
y3 0 4 0 −3 0 0 1 −3 2
1 1 1
x3 0 0 1 3
0 0 0 3 3
−1 0 −8 0 6 0 0 0 7 −4

B \ x, y x1 x2 x3 x4 y1 y2 y3 y4 SB
2
y1 1 2 0 −1 1 0 0 −1 2 2
=1
0
y2 −1 2 0 −2 0 1 0 −2 0 2
=0
2
y3 0 4 0 −3 0 0 1 −3 2 4
= 0.5
1 1 1
x3 0 0 1 3
0 0 0 3 3
−1 0 −8 0 6 0 0 0 7 −4
 39 / 45
Technique pour trouver une solution réalisable : Via un problème auxilliaire

Le 3ème tableau de (P La )
B \ x, y x1 x2 x3 x4 y1 y2 y3 y4 SB
y1 2 0 0 1 1 −1 0 1 2
−1 1
x2 2
1 0 −1 0 2
0 −1 0
y3 2 0 0 1 0 −2 1 1 2
1 1 1
x3 0 0 1 3
0 0 0 3 3
−1 −4 0 0 −2 0 4 0 −1 −4

B \ x, y x1 x2 x3 x4 y1 y2 y3 y4 SB
2
y1 2 0 0 1 1 −1 0 1 2 1
=2
−1 1
x2 2
1 0 −1 0 2
0 −1 0
2
y3 2 0 0 1 0 −2 1 1 2 1
=2
1 1 1 1/3
x3 0 0 1 3
0 0 0 3 3 1/3
=1
−1 −4 0 0 −2 0 4 0 −1 −4
 40 / 45
Technique pour trouver une solution réalisable : Via un problème auxilliaire

Le 4ème tableau de (P La )
B \ x, y x1 x2 x3 x4 x1 y2 y3 y4 SB
1 1 −1 1
x1 1 0 0 2 2 2
0 2
1
−3 1 1 −3 1
x2 0 1 0 4 4 4
0 4 2
y3 0 0 0 0 −1 −1 1 0 0
1 1 1
x4 0 0 1 3
0 0 0 3 3
−1 0 0 0 0 2 2 0 1 0

Echange des variables auxiliaires y en base avec des variables x.

Tous les pivots sont nuls sur la ligne 3
La contrainte 3 est redondante (= somme des 2 premières
contraintes)
La matrice A n'est pas de rang plein
La procédure permet d'identier les contraintes
redondantes.
Suppression de la contrainte 3
Suppression de la variable auxiliaire y3
 41 / 45
Technique pour trouver une solution réalisable : Via un problème auxilliaire

On supprime la troisième contrainte (contrainte 3) et la variable

articielle y3 .
B \ x, y x1 x2 x3 x4 y1 y2 y3 y4 SB
1 1 −1 1
x1 1 0 0 2 2 2
0 2
1
−3 1 1 −3 1
x2 0 1 0 4 4 4
0 4 2
y3 0 0 0 0 −1 −1 1 0 0
1 1 1
x3 0 0 1 3
0 0 0 3 3
−1 0 0 0 0 2 2 0 1 0

On obtient le tableau solution du problème auxiliaire suivant

B \ x, y x1 x2 x3 x4 y1 y2 y4 SB
1 1 −1 1
x1 1 0 0 2 2 2 2
1
−3 1 1 −3 1
x2 0 1 0 4 4 4 4 2
1 1 1
x3 0 0 1 3
0 0 3 3
−1 0 0 0 0 2 2 1 0

Le coût est nul, donc (x1 , x2 , x3 , x4 ) = (1, 1/2, 1/3, 0) est un

point admissible du problème initial.
 42 / 45
Technique pour trouver une solution réalisable : Via un problème auxilliaire

On supprime les colonnes correspondent aux variables

articielles y , on obtient une base initiale B = {1, 2, 3} de (3) :
xB \ x x1 x2 x3 x4 SB
1
x1 1 0 0 2
1
−3 1
x2 0 1 0 4 2
1 1
x3 0 0 1 3 3
−1 0 0 0 . .
On calcule les coûts réduits et le coût dans la base B :
c̄N = c> > −1
N − cB AB AN et −z = −c> B AB b.
−1
 1 
2
= 0 − 1 1 1 .  −3



c̄N 4

1
3
1 3 1 1
=0−( − + )=−
2 4 3 12
 
1
11
−z = − 1 1 1 .  12  = −


1 6
3
 43 / 45
Technique pour trouver une solution réalisable : Via un problème auxilliaire

Le 1er tableau du simplexe du problème initial

xB \ x x1 x2 x3 x4 SB
1
x1 1 0 0 2 1
−3 1
x2 0 1 0 4 2
1 1
x3 0 0 1 3 3
−1
−1 0 0 0 12 − 11
6

La base n'est pas optimale : on détermine la variable entrante et

sortante.
xB \ x x1 x2 x3 x4 SB
1
x1 1 0 0 1
1 1/2 =2
2
−3 1
x2 0 1 0 4 2
1 1 1/3
x3 0 0 1 3 3 1/3 =1
−1
−1 0 0 0 12 − 11
6
 44 / 45
Technique pour trouver une solution réalisable : Via un problème auxilliaire

Le 2ème tableau du simplexe

xB \ x x1 x2 x3 x4 SB

x1 1 0 . 0 .
x2 0 1 . 0 .
x4 0 0 3 1 1
−1 0 0 . 0 .

xB \ x x1 x2 x3 x4 SB
−3 1
x1 1 0 2 0 2
9 5
x2 0 1 4 0 4
x4 0 0 3 1 1
1
−1 0 0 4 0 − 74

La base est optimale : la solution optimale du problème de

départ est x∗ = (1/2, 5/4, 0, 1) et sa valeur minimale est z = 47 .
 45 / 45
Méthode des deux phases

Prétraitement
Mettre le problème sous forme standard
Prémultiplier les contraintes (2nd membre positif)
Phase 1 : Problème auxiliaire
Introduire une variable auxiliaire y par contrainte
Construire le tableau initial du problème auxiliaire
Résoudre le problème auxiliaire
Faire sortir les variables auxiliaires y de la base
Supprimer les contraintes redondantes (pivots tous nuls sur
une ligne)
Supprimer les colonnes correspondant aux variables
auxiliaires y (base ne contenant que des variables x)
Phase 2 : Problème initial
Calculer la dernière ligne du tableau (coûts réduits, coût)
Résoudre le problème initial