UNIVERSITE MOULOUD MAMMERI, TIZI-OUZOU.

FACULTE GENIE ELECTRIQUE

DEPARTEMENT INFORMATIQUE

IS 3
L
PL

u r
p o

Polycopié rédigé pour les L3 Iformatique par :

Mme Lynda GOUMEZIANE
[email protected]

écrit le : 2024
 TABLE DES MATIÈRES

3 Méthode primale de résolution d’un programme linéaire. 2

3.1 Position du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
3.1.1 Différentes formes de PL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
3.1.2 Transformation d’un PL à une forme standard . . . . . . . . . . . . . . . . . . . . . 4
3.2 Création d’une première solution de base : . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.2.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.2.2 Expression de la première solution de base : . . . . . . . . . . . . . . . . . . . . . . 7
3.3 Critère d’optimalité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.3.1 Critère d’optimatité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.4 Algorithme de simplexe | Méthode des tableaux . . . . . . . . . . . . . . . . . . . . . . . . 11
3.4.1 Tableau simplexe pour une forme canonique . . . . . . . . . . . . . . . . . . . . . . 11
3.4.2 Tableau simplexe pour une forme mixte | Méthode des pénalités . . . . . . . . . . . 12
3.4.3 Etape de la PL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.4.4 Conditions pour choisir une nouvelle variable de base (variable entrante) . . . . . . 13
3.4.5 Critère pour choisir l’équation recevant la nouvelle variable de base (variable sortante) 14
3.4.6 Construction de la nouvelle variable de base . . . . . . . . . . . . . . . . . . . . . . 14
3.4.7 Dégénérescence du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.4.8 Règle de Bland . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.5 Algorithme de simplexe | Méthode en deux phases . . . . . . . . . . . . . . . . . . . . . . . 15

1
 CHAPITRE 3
MÉTHODE PRIMALE DE RÉSOLUTION
D’UN PROGRAMME LINÉAIRE.

Dans ce chapitre, on va voir la méthode de simplexe qui résout un problème primal

d’un PL. La méthode a été développée par Dantzig en 1948 et reste toujours une référence
importante dans la classe des méthodes de résolution des problèmes linéaires.

Avant d’entamer le principe de la méthode de simplexe, on va citer quelques définitions

importantes pour ce chapitre :

3.1 Position du problème

3.1.1 Différentes formes de PL
Définition 3.1.1 Forme générale d’un PL

On appelle un problème d’optimisation linéaire sous forme générale, le système sui-

vant :  n
T
P


 max(min) f (x) = c ∗ x = cj xj
j=1
n

 s.c. x ∈ R
gi (x) ≤ 0 ∀i = 1, m


tel que :

f : Rn −→ R une fonction linéaire et g1 , ..., gm des applications affines.

Le même problème linéaire peut s’écrire sous diverse formes équivalentes les unes aux
autres. Parmi ces versions, nous distinguons : les formes canoniques mixtes, les formes
canoniques pures et les formes standards.

2
Définition 3.1.2 Forme canonique mixte
 Pn


 max(min) f (x) = c 1 ∗ x 1 + ... + c n ∗ x n = cj xj


 j=1


 s.c.

 Pn
∀i ∈ I1 , aij xj ≤ bi

 contraintes inégalités
j=1

 Pn


 ∀i ∈ I2 , aij xj = bi contraintes égalités
j=1



∀j ∈ J1 , xj ≥ 0 contraintes signes




∀j ∈ J2 ,

xj signes quelconques
Avec I = I1 ∪ I2 ensemble des indices des contraintes, tel que :
card(I) = m ⇒ m contraintes.
et J = J1 ∪ J2 ensemble des indices des variables, tel que :
card(J) = n ⇒ n variables.
Ce qui fait on aura :

– x = (x1 , ..., xn )T ∈ Rn inconnus

– c = (c1 , ..., cn )T ∈ Rn données
– b = (b1 , ..., bn )T ∈ Rn données  
a11 a12 ... a1n
– A est une matrice m × n : A =  ... ... ... 
am1 am2 ... amn
Définition 3.1.3 Forme canonique pure

Sous cette forme I2 = ∅ et J2 = ∅.

Par conséquent un PL est dit qu’il est sous forme canonique pure, s’il s’écrit comme
suit :
f (x) = cT ∗ x


 max(min)
s.c.


 A∗x≤b contrainte inégalité
x≥0 contrainte signe

Définition 3.1.4 Forme standard

Quand I1 = ∅ et J2 = ∅ la forme du programme linéaire est appelée forme standard.

f (x) = cT ∗ x


 max(min)
s.c.


 A∗x=b contrainte égalité
x≥0 contrainte signe


Définition 3.1.5 Forme simpliciale

Un PL sous forme standard est simpliciale si A ( la matrice des contraintes) de taille
m × n avec m ≤ n se décompose en :

A = (H|Im )

avec :
– Im matrice identité de taille m
– H matrice de taille (n − m)

Lemme 3.1.6
min Z = − max(−Z)
Cette formule réduit les procédures itératives dans l’algorithme qui sera éléboré pour
résoudre le P LS . (La compléxité de l’algorithme sera réduite)
Comme sur MatLab, la méthode de simplexe, qui a pour instruction linprog est dévelopée
que pour un problème de maximisation.

3.1.2 Transformation d’un PL à une forme standard

Pour comprendre le déroulement de l’algorithme du simplexe, considérons le problème
mixte à deux variables (n=2) et trois contraintes (m=3) :


 max Z = c1 ∗ x1 + c2 ∗ x2
 s.c. a11 ∗ x1 + a12 ∗ x2 ≤ b1 − − − − − − − (1)


(P LM ) a21 ∗ x1 + a22 ∗ x2 = b2 − − − − − − − (2)
a31 ∗ x1 + a32 ∗ x2 ≥ b3 − − − − − − − (3)




x1 , x2 ≥ 0


La forme standard du problème P LM est déterminée selon les variations des contraintes,
mais le principe est le même, il faut transformer l’inéquation en équation.

Voyons comment transformer les deux inéquations (1) et (3) en équations.

Variable d’écart :

Prenant l’inéquation (1) :

a11 ∗ x1 + a12 ∗ x2 ≤ b1

En ajoutant au premier membre de cette inéquation une variable positive ou nulle e1 ,

appelée variable d’écart, on aura la transformation souhaitée :

a11 ∗ x1 + a12 ∗ x2 + e1 = b1

Si, à l’optimum, la variable d’écart :

e1 = 0 ⇒ a11 ∗ x1 + a12 ∗ x2 = b1
e1 > 0 ⇒ a11 ∗ x1 + a12 ∗ x2 < b1
Dans ce dernier cas on trouvera :

e1 = b1 − (a11 ∗ x1 + a12 ∗ x2 )

Connaitre les valeurs des variables d’écart est utile lors de l’interprétation à donner
après voir déterminer la solution optimale.

Variable d’excédent :

Prenons maintenant l’inéquation (3) :

a31 ∗ x1 + a32 ∗ x2 ≥ b3

En retranchant au premier membre de cette inéquation une variable positive ou nulle

e2 , appelée variable d’excédent, on aura la transformation souhaitée :

a31 ∗ x1 + a32 ∗ x2 − e2 = b3

Si, à l’optimum, la variable d’excédent :

e2 = 0 ⇒ a31 ∗ x1 + a32 ∗ x2 = b3
e2 > 0 ⇒ a31 ∗ x1 + a32 ∗ x2 > b3
Dans ce dernier cas, on aura :

e2 = b3 − (a31 ∗ x1 + a32 ∗ x2 )

Résumé :

L’utilisation des variables d’écart et d’excèdent permet de transformer des inéquations

en équations, de plus la solution optimale du programme transformé est équivalente à
celle du programme original.
 Donc pour trouver la solution du (P LM ), il suffit de trouver la solution du (P LS )
transformé :


 max Z = c1 ∗ x1 + c2 ∗ x2
 s.c. a11 ∗ x1 + a12 ∗ x2 + e1 = b1


(P LS ) a21 ∗ x1 + a22 ∗ x2 = b2
a31 ∗ x1 + a32 ∗ x2 − e2 = b3




x1 , x2 , e1 , e2 ≥ 0


où e1 est une variable d’écart et e2 est une variable d’excédent.

Le but est de structurer une méthode générale pour résoudre un PL.

Comme les valeurs des bi peuvent être quelconques, nous choisirons la
convention suivante :

Remarque 3.1.7 CONVENTION :

Dans la méthode de résolution d’un (P LM ), il faut s’assurer que les constantes bi , ∀i ∈

I sont toujours positive.

Exemple 3.1.8 

 9 ∗ x1 − 5 ∗ x2 ≤ −12
−5 ∗ x1 + 2 ∗ x2 = −4


 −3 ∗ x1 − 11 ∗ x2 ≥ −2
x1 , x2 ≥ 0


Le système équivalent doit satisfaire la convention :



 −9 ∗ x1 + 5 ∗ x2 ≥ 12
+5 ∗ x1 − 2 ∗ x2 = +4


 +3 ∗ x1 + 11 ∗ x2 ≤ 2
x1 , x2 ≥ 0


3.2 Création d’une première solution de base :

3.2.1 Définitions
Définition 3.2.1 Variables principales et non principales :

Dans un système d’équations linéaires, si des variables sont explicitement exprimées

en fonction d’autres, les premières sont principales (VP) et les autres sont non principales
(VNP).
Dans un modèle de PL, les VP et les VNP peuvent prendre que des valeurs positives ou
nulles.
Définition 3.2.2 Variables de base :

Une VB est une VP positive ou nulle.

Si une VB est une VP, la réciproque n’est pas nécessairement vraie.

Définition 3.2.3 Variables hors base :

Une VHB est une VNP nulle.

Définition 3.2.4 Solution de base :

Soit un PL à 0 n0 variables et 0 m0 contraintes sous forme d’équations. Toute solution à

ce système de contraintes, composée de m VB positives et (n-m) VHB est dite solution
de base

Définition 3.2.5 Solution de base dégénérée :

Une solution de base est dite dégénérée si son nombre de variables positives est
inférieur au nombre de contraintes, ou explicitement, si au moins une VB est nulle.

Exemple 3.2.6

Soit le système : 
x1 − x2 + x3 = 1
x1 + x2 + x3 = 1
La solution :
1 1
x1 = (V B), x2 = 0 (V HB), x3 = (V B)
2 2
est solution de base, tandis que la solution :

x1 = 1 (V B), x2 = 0 (V B), x3 = 0 (V HB)

est une solution dégénérée.

3.2.2 Expression de la première solution de base :

Théorème 3.2.7 ”Une solution de base est un point extrême du domaine des
solutions réalisables”.
Aussi, ”un point extrême du domaine des solutions réalisables est une solu-
tion de base”
(Pour la preuve voir Linear Programming de G. Hadley 1962.)
 Avec ce théorème de la solution de base, on peut définir l’idée globale de la méthode
de simplexe :

Le simplexe est un algorithme itérative, il démarre par un point initial, qui sera dans ce
cas de figure, la première solution de base réalisable, qui n’est qu’un des points extrêmes
de la région des solutions réalisables. A partir de cette première solution réalisable, l’al-
gorithme va passer vers une autre solution réalisable (point extrême adjacent au premier
point de départ) en s’assurant chaque fois qu’un tel passage nous permet d’accroı̂tre la
fonction économique (max) ou la décroı̂tre (min).

Donc pour trouver cette première solution de base, il faut trouver les variables de base
qui seront différentes des variables principales, dans notre cas on aura m = 3 variables
de bases (selon le nombre de contraintes) et n = 2 variables hors base (selon le nombre
des variables de décision).

Prenant le système des contraintes du programme standard (P LS ).



 a11 ∗ x1 + a12 ∗ x2 + e1 = b1
a21 ∗ x1 + a22 ∗ x2 = b2

a ∗ x1 + a32 ∗ x2 − e2 = b3
 31


x1 , x2 e1 , e2 ≥ 0
m


 e1 = b1 − a11 ∗ x1 − a12 ∗ x2
0 = b2 − a21 ∗ x1 − a22 ∗ x2


 −e2 = b3 − a31 ∗ x1 − a32 ∗ x2
x1 , x 2 e1 , e2 ≥ 0


Si on prend (x1 , x2 ) = (0, 0), on aura :



 e1 = b1
0 = b2


 −e2 = b3
x1 , x 2 e1 , e2 ≥ 0


On remarque que la 2eme contrainte n’a pas de variable de base la représentant ce qui
contredit le nombre de variables de base qu’il faut pour avoir une solution de base ad-
missible, et la 3eme contrainte contredit la convention imposée sur bi qui doit être positif
∀i = 1, 2.

Pour résoudre ce problème de la variable négative et ajuster le nombre de variables de

bases au nombre de contraintes, on va introduire d’autres variables qui n’auront aucune
interprétation économique. Elles interviennent juste pour utiliser la méthode de simplexe
et à avoir une première solution de base comme l’origine (une solution de base initiale
par défaut, sinon on peut commencer par d’autres solutions de base admissible si elles
vérifient les contraintes du (P LM ). Ces variables sont appelées : variables artificielles.
Donc les variables artificielles seront ajoutées dans les contraintes qui ont des variables
d’excédents et celles qui ont une égalité dans le P LM .

Ainsi le système de contraintes de P LM sera transformé en un système d’équation

linéaire suivant : 

 a11 ∗ x1 + a12 ∗ x2 + e1 = b1
a21 ∗ x1 + a22 ∗ x2 + t1 = b2

a ∗ x1 + a32 ∗ x2 − e2 + t2 = b3
 31


x1 , x 2 , e 1 , e 2 , t 1 , t 2 ≥ 0
A partir de ce système on peut fournir immédiatement une première solution de base :
0
Solbase =(x1 ,x2 ,e1 ,e2 ,t1 ,t2 )=(0,0, b1 , 0, b2 , b3 )

Exemple 3.2.8 Considérons le système de contraintes quelconque suivant :


 x1 + x2 + x3 = 1
(S) : 2 ∗ x1 + 3 ∗ x2 = 1
x1 , x2 , x3 ≥ 0


1. Trouvons toutes les solutions de base initiale de ce système ?

La première observation c’est qu’on a 3 variables et 2 contraintes, ce qui veut dire
qu’il y a deux VB et une VHB, donc on peut distinguer trois solutions de base
initiale : 
 x1 = 0 ;
– Si x1 est une VHB, alors : x2 = 31 ; ⇒(x1 , x2 , x3 ) = (0, 31 , 23 )
x = 23 .

 3
 x1 = 21 ;
– Si x2 est une VHB, alors : x2 = 0 ; ⇒(x1 , x2 , x3 ) = ( 21 , 0, 12 )
x3 = 12 .


 x1 = 2 ;
– Si x3 est une VHB, alors : x2 = -1 ; ⇒(x1 , x2 , x3 ) = (2, −1, 0)
x3 = 0.


2. On remarque que (x1 , x2 , x3 ) = (2, −1, 0) n’est pas une solution réalisable x2 ≤ 0
ce qui fait les deux points extrêmes de la région définie par le système S sont ( 21 , 0, 12 )
et (0, 31 , 23 )
3. Si on a la fonction objectif à minimiser Z = −3 ∗ x1 − 2 ∗ x2 − x3 sur la région (S),
le min est atteint au point x∗ = ( 21 , 0, 12 ) avec Z ∗ = Z(x∗ ) = −2
Remarque 3.2.9 Puisque les P LM et le P LSM sont équivalents, donc quand on trouvera
l’optimum, les variables artificielles doivent être nulles, sinon les contraintes originales
ne seraient pas respectées.
Par exemple, si la solution optimale est telle que t1 ≥ 0, ceci implique que la deuxième
contrainte de P LM est :
a21 ∗ x1 + a22 ∗ x2 ≤ b2
qui est une contradiction avec :
a21 ∗ x1 + a22 ∗ x2 = b2
Afin de remedier à ce problème, on va introduire dans la fonction objectif pour chaque
variable artificielle ajoutée le coefficien −M pour un problème à maximum, +M pour un
problème à minimum où M est une valeur très grande telle que l’infini !

Cette méthode est appelée la mèthode des pénalités, ou la méthode du

grand M (Big-M method) une des variantes de la méthode de simplexe.

Les pénalités ont pour objet de provoquer l’élimination des variables artificielles au fil
des itérations. Normalement, à l’optimum (s’il existe) les variables artificielles sont hors
base. Si celles-ci sont à l’optimum dans la base, avec une valeur non nulle, le programme
n’a pas de solution.

Conclusion 1 Maintenant on peut déduire la forme standard avec la méthode des pénalités :
1. d’un problème mixte de maximisation comme suit :


 max Z = c1 ∗ x1 + c2 ∗ x2 − M ∗ t1 − M ∗ t2
 s.c. a11 ∗ x1 + a12 ∗ x2 + e1 = b1


(P LSM ) a21 ∗ x1 + a22 ∗ x2 + t1 = b2
a31 ∗ x1 + a32 ∗ x2 − e2 + t2 = b3




x1 , x2 , e1 , e2 , t1 , t2 ≥ 0


2. ou d’un problème mixte de minimisation comme suit :



 min Z = c1 ∗ x1 + c2 ∗ x2 + M ∗ t1 + M ∗ t2
 s.c.

 a11 ∗ x1 + a12 ∗ x2 + e1 = b1
(P LSM ) a21 ∗ x1 + a22 ∗ x2 + t1 = b2
a31 ∗ x1 + a32 ∗ x2 − e2 + t2 = b3




x1 , x2 , e1 , e2 , t1 , t2 ≥ 0


3.3 Critère d’optimalité

La fonction objectif Z change de coèficient à chaque étape. En substituant à chaque
itération les variables non principale au problème mixte dans la fonction objectif, on aura
la relation suivante à l’étape (k) :
n
(k)
X
Z = z0 − c(k) ∗ xj
j=1

3.3.1 Critère d’optimatité

Lorsque on maximise (minimise) une fonction objectif, la solution op-
timale est obtenue lorsque tous les coeficients c(k) des variables hors base
sont négatif (positif )

c(k) est l’effet sur Z de l’accroissemnt unitaire donné à la variable hors base x(k) et
e(k)

3.4 Algorithme de simplexe | Méthode des tableaux

3.4.1 Tableau simplexe pour une forme canonique
Soit le problème canonique dans R2 avec m = 3 contraintes :


 max(min) Z = c1 ∗ x1 + c2 ∗ x2
 s.c. a11 ∗ x1 + a12 ∗ x2 ≤ b1


(P LC ) a21 ∗ x1 + a22 ∗ x2 ≤ b2
a31 ∗ x1 + a32 ∗ x2 ≤ b3




x1 , x 2 ≥ 0


Le programme standard équivalent est :



 max(min) Z = c1 ∗ x1 + c2 ∗ x2



 s.c. a11 ∗ x1 + a12 ∗ x2 + e1 = b1
a21 ∗ x1 + a22 ∗ x2 + e2 = b2

(P LSC )

 a31 ∗ x1 + a32 ∗ x2 + e3 = b3
x1 , x2 ≥ 0




e1 , e 2 , e 3 ≥ 0


Afin d’éviter de résoudre le P LS par la méthode matricielle, on va l’exprimer sous

forme d’un tableau :

Base x1 x2 e1 e2 e3 bi
e1 a11 a12 1 0 0 b1
e2 a21 a22 0 1 0 b2
e3 a31 a32 0 0 1 b3
ci c1 c2 0 0 0 z0
Ce premier tableau est appelé le tableau initial de la méthode de simplexe (k=0) avec la
solution de base initiale réalisable :

0
Solbase =(x1 ,x2 ,e1 ,e2 ,e3 )=(0,0, b1 , b2 , b3 )
et
z0 = 0

3.4.2 Tableau simplexe pour une forme mixte | Méthode des pénalités
Soit le problème mixte dans R2 avec m = 3 contraintes :


 max (min) Z = c1 ∗ x1 + c2 ∗ x2
 s.c.

 a11 ∗ x1 + a12 ∗ x2 ≤ b1
(P LM ) a21 ∗ x1 + a22 ∗ x2 = b2
a31 ∗ x1 + a32 ∗ x2 ≥ b3




x1 , x2 ≥ 0


On a trouvé que sa forme standard est :



 max (min) Z = c1 ∗ x1 + c2 ∗ x2 − (+)M ∗ t1 − (+)M ∗ t2
 s.c.

 a11 ∗ x1 + a12 ∗ x2 + e1 = b1
(P LSM ) a21 ∗ x1 + a22 ∗ x2 + t1 = b2
a31 ∗ x1 + a32 ∗ x2 − e2 + t2 = b3




x1 , x2 , e1 , e2 , t1 , t2 ≥ 0


Comme les variables artificielles n’ont aucune signification économique, la fonction

objectif ne doit pas dépendre de t1 et t2 , ce qui nous conduit à remplacer les équations
des t1 et t2 émanantes des contraintes dans l’équation de la fonction objectif, c-à-.d :


 t1 = −a21 ∗ x1 − a22 ∗ x2 + b2
+ t2 = −a31 ∗ x1 − a32 ∗ x2 + e2 + b3


 − − − − −− −− − − − − − − − − − − − − − − − − − − − − −
t1 + t2 = −(a21 + a31 ) ∗ x1 − (a22 + a32 ) ∗ x2 + e2 + b2 + b3


On remplace dans la formule de la fonction objectif de la formule standard primaire

P LSM :
max (min) Z = [c1 + (-)(a21 + a31 ) ∗ M ] ∗ x1 + [c2 + (-)(a22 + a32 ) ∗ M ] ∗ x2
−(+)M ∗ e2 − (+)M ∗ (b2 + b3 )
Le programme standard équivalent est :


 max (min) Z = [c1 + (-)(a21 + a31 ) ∗ M ] ∗ x1 + [c2 + (-)(a22 + a32 ) ∗ M ] ∗ x2



 −(+)M ∗ e2 − (+)M ∗ (b2 + b3 )
s.c. a11 ∗ x1 + a12 ∗ x2 + e1 = b1
0

(P LSM )

 a21 ∗ x1 + a22 ∗ x2 + t1 = b2
a31 ∗ x1 + a32 ∗ x2 − e2 + t2 = b3




x1 , x2 , e1 , e2 , t1 , t2 ≥ 0


Maintenant on peut écrire le tableau initial du programme standard d’un problème

mixte P LM

Base x1 x2 e1 e2 t1 t2 bi
e1 a11 a12 1 0 0 0 b1
t1 a21 a22 0 0 1 0 b2
t2 a31 a32 0 -1 0 1 b3
ci [c1 + (-)(a21 + a31 ) ∗ M ] [c2 + (-)(a22 + a32 ) ∗ M ] 0 -(+)M 0 0 +(-)M ∗ (b2 + b3 )
avec la solution de base initiale réalisable :

0
Solbase =(x1 ,x2 ,e1 ,e2 ,t1 ,t2 ) =(0,0, b1 , 0, b2 , b3 )

3.4.3 Etape de la PL
1. Ecrire le modèle (Modélisation).
2. Transformation du système de contraintes en un système d’équation.
3. Création d’une première solution de base.
4. Début de la procédure itérative
5. Calculer les coèfficients c(k)
6. Critère d’optimalité
7. Si oui arrêter, afficher solution
8. Sinon calcul itérative et aller à l’étape 6

3.4.4 Conditions pour choisir une nouvelle variable de base (variable en-
trante)
ck sont les coefficients qui expriment la modification globale apportée à la fonction
objectif (accroissement ou décroissement) unitaire donner à la valeur hors base xj .
Si le PL est une maximisation donc le choix de la nouvelle variable de base est celle dont
son coefficient c( k) est le plus grand positif, sinon si c’est un PL de minimisation elle sera
choisie quand son coefficient c(k) est le plus petit négatif.

Ce qui fait d’après le critère d’optimalité on peut déduire le test d’arrêt de l’algo-
rithme :

– c(k) ≤ 0 pour un problème de maximisation.

– c(k) ≥ 0 pour un problème de minimisation.
Revenons à notre tableau initial :

1. le choix de la variable entrante entraine le choix de la colonne de pivot, c.-à-d., on

choisit l’indice j tel que :

– cj = max {ci , ci ≥ 0} ←− maximisation.

i=1,...,5
– cj = min {ci , ci ≤ 0} ←− minimisation.
i=1,...,5
2. si aucun choix n’est possible,dans les deux cas, alors la solution optimale est atteinte
et l’algorithme s’arrête.

3.4.5 Critère pour choisir l’équation recevant la nouvelle variable de base

(variable sortante)
La variable de base doit vérifier les contraintes, c’est à dire, elle va être une variable
d’une solution de base réalisable, donc le choix de la variable sortante revient à choisir
la ligne du pivot. Pour cela, on choisit l’indice i en utilisant le critère du quotient :
bi bk
= min{ |akj > 0, k = 1, 3}
aij akj
où j est la colonne de pivot de la variable entrante.

3.4.6 Construction de la nouvelle variable de base

On applique la procédure d’élimination de Gauss-Jordan autour du pivot situé à
l’intersection de la ligne i et de la colonne j. En premier, on divise la ligne i par le pivot
pour le mettre égal à 1 (normalisation du pivot. Ensuite avec cette nouvelle ligne on
réduit les éléments de la colonne du pivot à 0 sauf le pivot.
Les opérations sont les suivantes :
Li
→ Li
aij
Lk − (aij )Li → Lk , k = 1, 4
——————————————————-
3.4.7 Dégénérescence du simplexe
Une solution de base réalisable est dite dégénérée si au moins une des variables de
base est nulle.

Si au cours de l’exécution de l’algorithme du simplexe, aucune base rencontrée n’est

pas dégénérée, alors l’algorithme se termine en un nombre fini d’itérations.

Par contre si l’algorithme recontre une base dégénérée dans une itération donnée, alors
on peut rencontrer un éventuel cyclage de l’algorithme, c.-à-d. on retrouve une base déjà
rencontrée (repasser par un sommet déjà calculer ne vérifiant pas le critère d’arrêt) et
on itère indéfiniment.

Pour traiter les cas de dégénérescence, on peut appliquer la règle de Bland (1977)
qui assure l’arrêt de l’algorithme en un nombre fini d’itérations. Aussi quand plusieurs
variables sont susceptibles d’entrer à ou de sortir de la base, on choisit toujours celle qui
a l’indice le plus petit.

3.4.8 Règle de Bland

– s’il y a deux ou plusieurs variables qui peuvent entrer en base, alors on choisit celle
qui a le plus petit indice ;
– s’il y a deux ou plusieurs variables qui peuvent sortir de la base, alors on choisit
celle qui a le plus petit indice ;

3.5 Algorithme de simplexe | Méthode en deux phases

Comme son nom l’indique, la méthode en deux phases consiste à segmenter l’algo-
rithme du simplexe en deux étapes.
Revenons au problème standard d’un PL mixte :


 max Z = c1 ∗ x1 + c2 ∗ x2
 s.c.

 a11 ∗ x1 + a12 ∗ x2 + e1 = b1
(P LSM ) a21 ∗ x1 + a22 ∗ x2 + t1 = b2
a31 ∗ x1 + a32 ∗ x2 − e2 + t2 = b3




x1 , x2 , e1 , e2 , t1 , t2 ≥ 0


La première étape, dite Phase I(PI) : consiste a minimisé un PL intermédiaire dont

sa fonction objectif est la somme des variables artificielles qui apparaissent après la
standardisation du problème mixte sous les mêmes contraintes du P LSM , c.à.d, :



 min Ze = t1 + t2
 s.c.

 a11 ∗ x1 + a12 ∗ x2 + e1 = b1
(P L)
f a21 ∗ x1 + a22 ∗ x2 + t1 = b2 − − − − − 1




 a31 ∗ x1 + a32 ∗ x2 − e2 + t2 = b3 − − − − − 2
 x1 , x 2 , e 1 , e 2 , t 1 , t 2 ≥ 0

Comme les variables artificielles n’ont aucun sens économique, le (PfL) sera équivalent
à :



 min Ze = −(a21 + a31 ) ∗ x1 − (a22 + a32 ) ∗ x2 + e2 + b2 + b3 ⇐= 1 et 2
 s.c. a11 ∗ x1 + a12 ∗ x2 + e1 = b1


(PfL) a21 ∗ x1 + a22 ∗ x2 + t1 = b2
a31 ∗ x1 + a32 ∗ x2 − e2 + t2 = b3




x1 , x2 , e1 , e2 , t1 , t2 ≥ 0



La résolution du (PfL) suit les mêmes règles de l’algorithme de simplexe.

Après que le critère d’optimalité est atteint, plusieurs cas peuvent se présenter :
– Cas 1 : Si min Ze > 0 alors le domaine réalisable du problème primal est vide (et
on dit que le problème primal n’est pas réalisable)
– Cas 2 : Si min Ze = 0 avec acune variable artifficielle dans la base, alors le problème
intermédiare fournit une solution de base réalisable initiale pour le problème primal
standard P LSM
Si la PI se termine par le 2éme cas, alors on passe à la PII.
La Phase II(PII) débute avec le dernier tableau (dernière solution) de la PI en rem-
plaçant la dernière ligne du tableau de simplexe par la fonction objectif économique (tout
en substituant par les relations des variables de décision trouvées dans le dernier tableau
de la phase I) du problème primal ; l’algorithme se poursuit selon les critères usuels de
la méthode du simplexe.
Exemple 3.5.1 Exemple d’application :
Soit le modèle de programmation linéaire suivant :


 max Z = x1 + 2 ∗ x2 − − − − − 1



 s.c. x1 + x2 + e1 = 5 − − − − − 2
(P LSM ) x1 + 2 ∗ x2 − e2 + t1 = 2 − − − − − 3
x1 − e3 + t2 = 1 − − − − − 4





x1 , x2 , e1 , e2 , e3 , t1 , t2 ≥ 0


Où : x1 , x2 sont des variables de décision,

e1 est une variable d’écart,
e2 , e3 sont des variables d’excédent,
et t1 , t2 sont des variables d’artificielles.
- Phase I :
La fonction objectif à minimiser en cette phase est la somme des variables artificielles,
qui est :
0
min Z = t1 + t2
sous les mêmes contraintes.
Comme les variables artificielles n’ont aucun sens économique, on peut les remplacer par
leurs formules autant que VP :



 t1 = −x1 − 2 ∗ x2 + e2 + 2 ⇐= 2
+ t2 = −x1 + e3 + 1 ⇐= 3


 − − − − −− −− − − − − − − − − − − − − − − − − − − − − −
t1 + t2 = −2 ∗ x1 − 2 ∗ x2 + e2 + e3 + 3


Le problème intermédiare de la PI devient :




 min Ze = −2 ∗ x1 − 2 ∗ x2 + e2 + e3 + 3
s.c. x1 + x2 + e1 = 5



(P LSM )
f x 1 + 2 ∗ x 2 − e 2 + t1 = 2
x1 − e3 + t2 = 1




x1 , x2 , e1 , e2 , e3 , t1 , t2 ≥ 0



1- Tableau initial de la Phase I : k=0

bi
Base x1 x2 e1 e2 e3 t1 t2 bi CP
e1 1 1 1 0 0 0 0 5 5 e(0)
L 1
(0)
t1 1 2 0 -1 0 1 0 2 2 L2
e
t2 1 0 0 0 -1 0 1 1 1 e(0)
L 3
(0)
−Ze -2 -2 0 1 1 0 0 -3  L4
e
 
V.Bnew ←− x1 −→ j = 1(règle de Bland) (0)
ce qui fait le pivot est p(0) = a31 = 1
V.H.Bnew ←− t2 −→ i = 3
2- Itération k=1 :

bi
Base x1 x2 e1 e2 e3 t1 t2 bi CP
e1 0 1 1 0 1 0 -1 4 5 e(1)
L =Le(0) − a(0) L e(1)
1 1 11 3
t1 0 2 0 -1 1 1 1 1 1/2 e(1)
L =Le(0) − a(0) L e(1)
2 2 21 3
(1) e(0) /a(0)
x1 1 0 0 0 -1 0 1 1  L3
e =L 3 31
−Ze 0 -2 0 1 -1 0 2 -1  e(1)
L e (0)
= L4 − a41 L
(0) e (1)
4 3

V.Bnew ←− x2 −→ j = 2 (1)
ce qui fait le pivot est p(1) = a22 = 2
V.H.Bnew ←− t1 −→ i = 2
3- Itération k=2 :

Base x1 x2 e1 e2 e3 t1 t2 bi
e1 0 0 1 1/2 1/2 -1/2 -1/2 7/2 e(2)
L =Le(1) − a(1) L e(2)
1 1 12 2
(2) e(1) /a(1)
x2 0 1 0 -1/2 1/2 1/2 -1/2 1/2 L2
e =L 2 22
x1 1 0 0 0 -1 0 1 1 e(2)
L e (1)
= L3 − a32 L
(1) e (2)
3 2
(2) (1) (1) e (2)
−Ze 0 0 0 0 0 1 1 0 L4
e = L4 − a42 L2
e

On remarque min Ze = 0 et le critère d’optimalité est atteint, alors la PI est terminée

et le P LM S admet une solution de base initiale réalisable. x(0) = (x1 , x2 , e1 , e2 , e3 ) =
(1, 1/2, 7/2, 0, 0)

Pour démarrer la PII il faut optimiser cette fois ci la fonction objectif du modèle
original et éliminer du dernier tableau de la PI les deux colonnes associées aux
variables artificielles t1 et t2
4- Tableau initial de la phase II Itération k=3 : La ligne −Z des valeurs margi-
nales du premier tableau de la pahse II est bien sûr modifiée puisqu’on n’a plus la
même fonction économique.

Base x1 x2 e1 e2 e3 bi
e1 0 0 1 1/2 1/2 7/2 L1
x2 0 1 0 -1/2 1/2 1/2 L2
x1 1 0 0 0 -1 1 L3
−Zprimal 1 2 0 0 0 0 L4
−Z 0 0 0 1 0 -2 L5 = L4 − (L3 + 2L2 ) (∗)
 Pour trouver ces valeurs, On peut procéder de deux manières :
1. Indirectement, il suffit d’écrire le système des contraintes du dernier tableau de
la PI et remplacer dans la fonction objectif du problème primal, c-à-d. :

– 2ème ligne du tableau : e1 + 12 ∗ e2 + 21 ∗ e3 = 72 —– 5

– 3ème ligne du tableau : x2 − 12 ∗ e2 + 21 ∗ e3 = 12 —– 6
– 4ème ligne du tableau : x1 − e3 = 1 —– 7
– La fonction objectif de notre problème est : Z = x1 + 2 ∗ x2 —– 8
en remplaçant : 5 , 6 et 7 dans 8 , pour trouver la fonction objectif à cette
itéartion, on aura :
Z = e2 + 2
Ce qui fait le coéfficient de e2 est égale à 1 et Z (3) = −(−2)
2. Directement, en ajoutant une ligne avant la ligne de la fonction objectif pour
mettre les coéfficients de Zprimal du P LSM , après sommer cette ligne avec les
lignes qui forme cette fonction objectif (voir ∗)
Ce qui fait le tableau de l’itération k=3 de PII, est :

bi
Base x1 x2 e1 e2e3 bi CP
(3)
e1 0 0 1 1/2
1/2 7/2 7 L1
(3)
x2 0 1 0 -1/2
1/2 1/2  L2
(3)
x1 1 0 0 0 -1 1  L3
(3)
−Z 0 0 0 1 0 -2  L4

V.Bnew ←− e2 −→ j = 4 (3)
ce qui fait le pivot est p(3) = a14 = 1/2
V.H.Bnew ←− e1 −→ i = 1
5- Itération k=4 :
Base x1 x2 e1 e2 e3 bi
(4) (3) (3)
e2 0 0 2 1 1 7 L1 = L1 /a14
(4) (3) (3) (4)
x2 0 1 1 0 1 4 L2 = L2 − a24 L1
(4) (3) (3) (4)
x1 1 0 0 0 -1 1 L3 = L3 − a34 L1
(4) (3) (3) (4)
−Z 0 0 -2 0 -1 -9 L4 = L4 − a44 L1
On remarque que le critère d’optimalité est satsfait, par conséquence la solution de
base obtenue de la phase II est la solution optimale du programme linéaire original.

x∗ = (1, 4)
et
Z∗ = 9