Chapitre 2 :

Résolution des programmes linéaires

La méthode du simplexe

La méthode du simplexe Présentation de la méthode

1. Présentation de la méthode du simplexe

Développée initialement par George Dantzig en 1947.

Outil principal de résolution des problèmes de programmation linéaire.

Il existe plusieurs formulations de cette méthode :

 méthode des tableaux,
 méthode algébrique (délicate dès que le nombre des variables et des
contraintes est important).
Méthode exacte itérative
et pour résoudre des problèmes linéaires de

grande taille :
 Elle consiste à suivre un certain nombre d'étapes (itérations) avant
d'obtenir la solution d'un problème donné,
 Elle permet de trouver la solution exacte en un nombre ni d'étapes.
Explore les sommets de la région admissible en améliorant à chaque

itération la valeur du critère.

Basée sur l'algèbre des matrices.

 La méthode du simplexe Notions générales

2. Notions générales
2.1 Rappels
Un programme linéaire s'écrit généralement sous la forme :
⎧
⎪ max (ou min) z = c1 x1 + c2 x2 + ... + cn xn
⎪
⎪
⎪
⎪ a11 x1 + a12 x2 + ... + a1n xn {≤, =, ≥} b1
⎪
⎪
⎨ a21 x1 + a22 x2 + ... + a2n xn {≤, =, ≥} b2
⎪ ... ⇐⇒
⎪
⎪
⎪
⎪
⎪
⎪ a x + am2 x2 + ... + amn xn {≤, =, ≥} bm
⎩ m1 1
x1 ≥ 0, . . . , xn ≥ 0
⎧ n
⎪
⎪
⎪
⎪ max / min z = cj xj
⎪
⎪
⎨ j=1
n
⎪
⎪
⎪ aij xj {≤, =, ≥} bi i = 1, m
⎪
⎪
⎪
⎩ j=1
xj ≥ 0 j = 1, n

La méthode du simplexe Notions générales

En utilisant la formulation matricielle :

⎧
⎨ max / min z = c T x
Ax {≤, =, ≥} b
⎩
x ≥0
c = (c1 , c2 , ..., cn ) ∈ Rn , b = (b1 , b2 , ..., bm ) ∈ Rm
⎛ ⎞
a11 a12 · · · a1n
⎜ a21 a22 · · · a2n ⎟
⎜ ⎟
A = ⎜ .. .. .. .. ⎟ matrice de type (m , n)
⎝ . . . . ⎠
am1 am2 · · · amn
n
et c T x = cj xj .
j=1

aij (i = 1, m ; j = 1, n) : coecients techniques ;

bi (i = 1, m) : seconds membres des contraintes ;
cj (j = 1, n) : coecients de la fonction économique ;
xj (j = 1, n) : variables de décision (niveaux d'activité).

La méthode du simplexe Notions générales

2.2 Forme canonique d'un PL

maximisation de la fonction objectif

toutes les contraintes sont des inégalités du type ≤
toutes les variables sont positives
⎧ n
⎪
⎪
⎪
⎪ max z = cj xj
⎪
⎪
⎨ j=1
n
⎪
⎪ aij xj ≤ bi i = 1, m
⎪
⎪
⎪
⎪ j=1
⎩
xj ≥ 0 j = 1, n

Forme matricielle
⎧
⎨ max z = c T x
Ax ≤ b
⎩
x ≥0
 La méthode du simplexe Notions générales

Exemple :
⎧
⎪
⎪ max 6x1 + 7x2 + 8x3
⎪
⎪ x1 + 2x2 + x3 ≤ 100 ⎧
⎪
⎪
⎨ ⎨ max z = c T x
3x1 + 4x2 + 2x3 ≤ 120
(P1 ) ⇐⇒ Ax ≤ b
⎪ 2x1 + 6x2 + 4x3 ≤ 200 ⎩
⎪
⎪ x ≥0
⎪
⎪ x + x3 ≤ 150
⎪
⎩ 1
x1 , x2 , x3 ≥ 0
avec
⎛ ⎞ ⎛ ⎞
1 2 1 100 ⎛ ⎞ ⎛ ⎞
⎜ ⎟ ⎜ ⎟ 6 x1
A=⎜ ⎟ ; b=⎜ ⎟ ; c=⎝ ⎠ x = ⎝ x2 ⎠
3 4 2 120
⎝ 2 6 4 ⎠ ⎝ 200 ⎠ 7 ;

8 x3
1 0 1 150

A de type (4 , 3),
m=4 (contraintes) et n=3 (variables de décision).

La méthode du simplexe Notions générales

2.3 Forme standard d'un PL

maximisation de la fonction objectif

toutes les contraintes sont de type égalités (=)

toutes les variables sont positives
⎧ n
⎪
⎪
⎪
⎪ max z = cj xj
⎪
⎪
⎨ j=1
n
⎪
⎪ aij xj = bi i = 1, m
⎪
⎪
⎪
⎪ j=1
⎩
xj ≥ 0 j = 1, n

Forme matricielle
⎧
⎨ max z = c T x
Ax = b
⎩
x ≥0

La méthode du simplexe Notions générales

2.4 Passage entre les formes

1 min f ⇐⇒ max − f
Par exemple : minimiser x1 + 2x2 revient à maximiser −x1 − 2x2
car : f (x ∗ )
= min{ f (x) , x ∈ X } ⇐⇒ f (x ∗ )
≤ f (x) , ∀x ∈ X ⇐⇒
−f (x ∗ ) ≥ −f (x), ∀x ∈ X ⇐⇒ −f (x ∗ ) = max{ −f (x) , x ∈ X }
2 ax ≥ b ⇐⇒ −ax ≤ −b
ax ≤ b
3 ax = b ⇐⇒
ax ≥ b
ax + y = b
4 ax ≤ b ⇐⇒
y ≥0
y est dite variable d'écart
ax − y = b
5 ax ≥ b ⇐⇒
y ≥0
6 x ≤ 0 ⇐⇒ −x ≥ 0
x = x+ − x− x + = max(x , 0)
7 x quelconque ⇐⇒ avec
x+ ≥ 0 , x− ≥ 0 x − = max(−x , 0)
 La méthode du simplexe Notions générales

Propriété
Tout programme linéaire peut être mis sous la forme canonique et sous la
forme standard.
Remarques
1 Le passage entre la forme générale, la forme canonique et la forme
standard se fait moyennant les transformations ci-dessus.
2 La forme canonique est utilisée dans la résolution graphique.
Tandis que la forme standard permet une résolution matricielle et sera
utilisée pour la méthode de simplexe.
Notons aussi que la méthode du simplexe requiert des bi ≥ 0.

La méthode du simplexe Notions générales

Exemple :
⎧
⎪
⎪ min 5x1 − 3x2
⎪
⎨ x1 − x2 ≥ 2
⎪
Soit le problème : (P2 )
⎪
2x1 + 3x2 ≤ 4
⎪
⎪
⎪ −x1 + 6x2 = 10
⎩
x1 , x2 ≥ 0
En introduisant les variables d'écart x3 ≥ 0 et x4 ≥ 0 dans la première et la
deuxième contrainte, on met (P2 ) sous la forme équivalente :
⎧
⎪
⎪ max −5x1 + 3x2
⎪
⎨ x1 − x2 − x3 = 2
⎪

(P2 )
⎪
2x1 + 3x2 + x4 = 4
⎪
⎪
⎪ −x1 + 6x2 = 10
⎩
x1 , x2 , x3 , x4 ≥ 0

(P2 ) est la forme standard de (P2 ).

La méthode du simplexe Bases, variables de base et solution de base

3. Bases, variables de base et solution de base

Soit Ax = b un système d'équations linéaires avec :
A matrice de type (m , n), m ≤ n et rang (A) = m.
Le système est donc sous-déterminé c-à-d le nombre m d'équations est
inférieur au nombre n d'inconnues notées x1 , . . . , xn .
En plus, il existe au moins une sous-matrice de A notée B carrée inversible
de type (m , m) (d'ordre m).
Dénitions
On appelle base toute sous-matrice carrée B inversible de type
(m , m) extraite de A.
Les variables associées aux colonnes de B sont dites variables de base,
les autres variables hors base.
Par extension, on appellera également base la liste ordonnée des
variables de base ou de leurs indices (notée B).
 La méthode du simplexe Bases, variables de base et solution de base

Exemple :
Soit le système linéaire :

x2 + 2x3 + 2x4 = 1
x1 + x2 + 2x3 + 3x4 = 1
Ce système peut s'écrire Ax =⎛b ⎞
, avec :

  x1  
⎜ x2 ⎟
A=
0 1 2 2
⎜
x =⎝ ⎟ et b =
1

x3 ⎠
,
1 1 2 3 1

x4
A est de type ( 2 , 4) (2 équations et 4 variables).
 
1 2
La sous-matrice B= est inversible et rang (A) = 2.
1 3

Ainsi B est une base.

Les variables de base associés à B sont x2 et x4 .

Les variables hors base associés à B sont x1 et x3 .

La méthode du simplexe Bases, variables de base et solution de base

Remarques
Une base est inversible et donc les variables de base correspondent à

des colonnes linéairement indépendantes de la matrice A.

Par conséquent, on peut avoir plusieurs bases dans une matrice A.
En eet, on peut le remarquer dans l'exemple précédent :
 
0 1
est aussi une base et correspond alors aux variables de base
1 1
x1 et x2 .
 
1 2
n'est pas une base (car non inversible).
1 2

Avec les conditions précédentes, le système Ax = b admet une

innité de solutions.

La méthode du simplexe Bases, variables de base et solution de base

Le système de l'exemple précédent :

x2 + 2x3 + 2x4 = 1
x1 + x2 + 2x3 + 3x4 = 1
admet une innité de solutions.
⎛⎞
  x1  
⎜ x2 ⎟
A=
0 1 2 2
x =⎝ ⎜ ⎟ et b =
1

x3 ⎠
On a : ,
1 1 2 3 1

x4
   
1 2 − 1 3 −2
B= est une base et B =
1 3 −1 1
Ax = b ⇐⇒ B −1 A x = B −1 b
    
3 −2 0 1 2 2 −2 1 2 0
B −1 A = =
−1 1 1 1 2 3 1 0 0 1
   
3 −2 1
B −1 b = =
−1 1 0
 La méthode du simplexe Bases, variables de base et solution de base

Donc le système est équivalent à :

⎛ ⎞
  x1  
−2 1 2 0 ⎜ ⎟
⎜ x2 ⎟ = 1 −2x1 + x2 + 2x3 = 1
⇐⇒
1 0 0 1 ⎝ x3 ⎠ 0 x1 + x4 = 0
x4
x2 = 1 + 2x1 − 2x3
⇐⇒
x4 = −x1
Le système précédent est équivalent au système de départ Ax = b mais
exprimé dans la base B
En xant des valeurs arbitraires pour x1 et x3 , on obtient les solutions
correspondantes pour x2 et x4 .
En particulier, pour x1 = 0 et x3 = 0, on obtient la solution x2 = 1 et
x4 = 0.
On dit alors que cette solution est la solution de base associée à la base B .

La méthode du simplexe Bases, variables de base et solution de base

Généralisation :
Soit Ax = b un système d'équations linéaires tel que A matrice de type
(m , n), m ≤ n et rang (A) = m. Soit B une base de A.
Après permutation des colonnes de A de manière à ce que celles de B
soient en premier, on obtient :
 
 
A=
P
B N et x=
P xB
xN
où
N est la sous-matrice de A correspondant aux variables hors base,
xB vecteur de Rm formé par les variables de base,
xN vecteur de Rn−m formé par les variables hors base.
et on a :
Ax = b ⇐⇒ BxB + NxN = b ⇐⇒ xB = B −1 b − B −1 NxN
Pour déterminer toutes les solutions du système, on choisit donc
arbitrairement les valeurs de xN (paramètres) et on calcule les valeurs
correspondantes de xB .
La méthode du simplexe Bases, variables de base et solution de base

Dénitions
On appelle solution de base (associée à la base B ), la solution
particulière obtenue en prenant xN = 0.
xB est déterminée de façon unique par :

BxB = b ⇐⇒ xB = B −1 b

Une solution de base est dite réalisable si xB ≥ 0 (toutes les variables

de base sont positives), autrement dit : B −1 b ≥ 0.
Remarque :
Dans le cas d'un programme linéaire sous forme standard avec les
contraintes Ax = b , x ≥ 0, une solution de base réalisable correspond
géométriquement à un sommet du polyèdre des contraintes.
En particulier, une solution optimale correspond à une solution de base
réalisable qui maximise la fonction objectif.
 Programmes linéaires et modélisation Exemples de programmes linéaires

Exemple 1 :
Une entreprise de fabrication de châssis envisage la production de deux
nouveaux modèles au moyen des capacités résiduelles de ses trois ateliers.
Il s'agit respectivement d'un châssis en aluminium et d'un châssis en bois.
Le premier produit nécessite le passage dans le premier atelier pour
fabriquer le cadre en aluminium et dans le troisième atelier où le verre est
monté sur le châssis. Tandis que le second produit nécessite le passage
dans le deuxième atelier pour fabriquer le cadre en bois et dans le troisième
atelier où le verre est monté sur le châssis.

Programmes linéaires et modélisation Exemples de programmes linéaires

Les marges unitaires, les temps de fabrication de chacun des produits dans
chacun des ateliers ainsi que les capacités hebdomadaires résiduelles de ces
ateliers sont donnés au tableau suivant :
Produit 1 Produit 2 Capacité
(châssis aluminium) (châssis bois) disponible
(heures/produit) (heures/produit) (heures/semaine)
Atelier 1 1 0 4
Atelier 2 0 2 12
Atelier 3 3 2 18
Marge 3 UM 5 UM
La question qui se pose est la suivante : combien faut-il produire de châssis
de chaque type par semaine pour maximiser le prot net ?

Programmes linéaires et modélisation Exemples de programmes linéaires

1. Identication des variables de décision

La première étape consiste à choisir les variables du problème.
Les quantités que le modèle doit déterminer sont les productions de châssis
par semaine. Posons donc :
x1 : nombre de châssis du produit 1 (châssis en aluminium)
x2 : nombre de châssis du produit 2 (châssis en bois).

2. Expression de l'objectif
La deuxième étape consiste à formuler l'objectif.
L'entreprise désire maximiser son prot net. La marge étant de 3 pour le
premier type de châssis et de 5 pour le second, l'objectif (ou fonction
économique) s'exprime comme suit :

max z = 3x1 + 5x2

 Programmes linéaires et modélisation Exemples de programmes linéaires
3. Expression des contraintes
La 3ème étape est la formulation des contraintes du problème.
Le temps pour assembler 1 châssis de type 1 dans l'atelier 1 est de 1 heure
où il reste 4 heures disponibles. D'où la contrainte de capacité de l'atelier1 :
x1 ≤ 4
De même, pour les contraintes de capacités des deux autres ateliers :
2x2 ≤ 12 et 3x1 + 2x2 ≤ 18
D'autre part, les quantités produites ne peuvent être négatives.
Mathématiquement : x1 ≥ 0, x2 ≥ 0
Finalement, le problème peut être formulé en programme linéaire :
⎧
⎪
⎪ max z = 3x1 + 5x2
⎪
⎪
⎨ x1 ≤ 4
(P1 ) 2x2 ≤ 12
⎪
⎪
⎪
⎪ 3x1 + 2x2 ≤ 18
⎩ x ≥0; x ≥0
1 2
 La méthode du simplexe Méthode du simplexe en tableaux

4. Méthode du simplexe en tableaux

4.1 Exemple :

Considérons le problème déjà étudié (Exemple précedent).

Rappelons le programme linéaire qui modélise ce problème :
⎧
⎪
⎪ max z = 3x1 + 5x2
⎪
⎪
⎨ x1 ≤ 4
(P) 2x2 ≤ 12
⎪
⎪
⎪
⎪ 3x1 + 2x2 ≤ 18
⎩ x ≥ 0 ;x ≥ 0
1 2
où

x1 est le nombre de chassis du produit 1 (chassis en aluminium),

x2 est le nombre de chassis du produit 2 (chassis en bois).

La méthode du simplexe Méthode du simplexe en tableaux

La forme standard du programme linéaire (P) s'écrit :

⎧
⎪
⎪ max z = 3x1 + 5x2 + 0e1 + 0e2 + 0e3
⎪
⎪
⎨ x1 + e1 + 0e2 + 0e3 = 4
(PS) 2x2 + 0e1 + e2 + 0e3 = 12
⎪
⎪
⎪ 3x + 2x2 + 0e1 + 0e2 + e3 = 18
⎪
⎩ 1
x1 ≥ 0 ; x2 ≥ 0 ; e1 ≥ 0 ; e2 ≥ 0 ; e3 ≥ 0
où ei est la variable d'écart associée à la ième contrainte.

Le système linéaire des contraintes associé à (PS) peut s'écrire :

Ãx̃ = b̃
x̃ ≥ 0
⎛ ⎞
⎛ ⎞ x1 ⎛ ⎞
⎜ x2 ⎟
1 0 1 0 0
⎜ ⎟ 4

à = ⎝ 0 2 0 1 0 ⎠ ; x̃ = ⎜ ⎟
⎜ e1 ⎟ ; b̃ =
⎝ 12 ⎠
3 2 0 0 1 ⎝ e2 ⎠ 18

e3
z = c̃ T x̃ = 3x1 + 5x2 + 0e1 + 0e2 + 0e3 avec c̃ = (x1 , x2 , 0 , 0 , 0)T

La méthode du simplexe Méthode du simplexe en tableaux

Choix de la solution de base réalisable initiale :

⎛ ⎞
1 0 0

Une base initiale est donnée par la matrice : I =⎝ 0 1 0 ⎠

0 0 1

Elle correspond aux variables de base e1 , e2 , e3

et variables hors base x1 , x2 .
La solution de base réalisable initiale est :

(x1 , x2 , e1 , e2 , e3 ) = (0 , 0 , 4 , 12 , 18)
Cela signie qu'au départ on a :

x1 = 0 ; x2 = 0 ; e1 = 4 ; e2 = 12 ; e3 = 18
Autrement dit : on ne produit rien au départ

et z = 3x1 + 5x2 + 0e1 + 0e2 + 0e3 = 0.

 La méthode du simplexe Méthode du simplexe en tableaux

Tableau initial :

Le premier tableau du simplexe (tableau initial) s'écrit :

Base x1 x2 e1 e2 e3 s.m

e1 1 0 1 0 0 4

e2 0 2 0 1 0 12

e3 3 2 0 0 1 18

z 3 5 0 0 0 0

Variables de base : e1 , e2 , e3 Variables hors base : x1 , x2

Solution de base : (x1 , x2 , e1 , e2 , e3 ) = (0 , 0 , 4 , 12 , 18)

La dernière ligne donne les valeurs marginales (ou taux de substitution )

des variables hors base. Elle correspond à la valeur de −z donc la marge

bénéciaire initiale z = 0.
La solution n'est pas optimale. On recherche donc une solution de base

meilleure : d'où une autre itération.

La méthode du simplexe Méthode du simplexe en tableaux

Itération du simplexe :

On augmente la fonction objectif en faisant entrer une variable dans la base

prenant la place d'une variable qui va sortir de la base.

Choix de la variable entrante dans la base :

Une augmentation de 1 unité de x1 ferait croître la fonction objectif de 3

Une augmentation de 1 unité de x2 ferait croître la fonction objectif de 5.

On a intérêt à augmenter la valeur de la fonction objectif le plus

rapidement possible donc à augmenter la variable ayant le plus grand

coecient strictement positif (cas de maximisation) de la dernière ligne :

x2 variable entrante dans la base.

Règle générale pour la variable entrante dans la base :

On sélectionne la variable hors base ayant le plus grand coecient

strictement positif dans la dernière ligne ( x2 dans notre cas).

La méthode du simplexe Méthode du simplexe en tableaux

Choix de la variable sortante de la base :

La question qui se pose est : jusqu'à quelle limite doit-on augmenter x2 ?
Une première idée est de pousser x2 le plus loin possible tant que les

variables de base restent positives.

Supposons qu'on augmente x2 en maintenant x1 hors base ( x1 = 0), alors :

⎧
⎪ e1 = 4 ⎧
⎪
⎨ ⎨ e2 = 12 − 2x2 ≥ 0
2x2 + e2 = 12
⇐⇒ e3 = 18 − 2x2 ≥ 0
⎪ 2x + e3 = 18 ⎩
⎪
⎩ 2 x2 ≥ 0
x2 ≥ 0 ; e1 ≥ 0 ; e2 ≥ 0 ; e3 ≥ 0
⎧
⎨ x2 ≤ 12/2 = 6
⇐⇒ x2 ≤ 18/2 = 9 =⇒ 0 ≤ x2 ≤ min{12/2 , / } = 12/2 = 6
18 2
⎩
x2 ≥ 0
Ainsi, la valeur limite que x2 peut prendre est x2 = 6. La deuxième

contrainte sera alors saturée ( e2 = 0) : e2 variable sortante de la base.

 La méthode du simplexe Méthode du simplexe en tableaux

Règle générale pour la variable sortante de la base :

On eectue le rapport des seconds membres des contraintes aux
coecients strictement positifs correspondants à la variable entrante, puis
on sélectionne la variable de la base ayant le plus petit rapport positif dans
la colonne R (e2 dans notre cas).
Tableau 1
Base x1 x↓2 e1 e2 e3 s.m R
e1 1 0 1 0 0 4 4/0 = ∞
← e2 0 2 0 1 0 12 12/2 = 6
e3 3 2 0 0 1 18 18/2 = 9
z 3 5 0 0 0 0

x2 variable entrante dans la base.

e2 variable sortante de la base.
Le coecient à l'intersection de la colonne de la variable entrante et la
ligne de la variable sortante s'appelle pivot (2 dans notre cas).

La méthode du simplexe Méthode du simplexe en tableaux

Pour obtenir le tableau 2, on eectue des pivotages.

Règles de calcul :
Les coecients de la ligne du pivot sont divisés par le pivot.
Les coecients de la colonne du pivot (sauf le pivot) sont nuls.
Les autres coecients sont obtenus par la règle :
Cpivot
Nv = Av − ( × Lpivot)
Pivot
Nv : nouvelle valeur
Av : ancienne valeur
Cpivot : colonne du pivot
Lpivot : Ligne du pivot

La méthode du simplexe Méthode du simplexe en tableaux

Tableau 1
↓
Base x1 x2 e1 e2 e3 s.m R
e1 1 0 1 0 0 4 4/0 = ∞
← e2 0 2 0 1 0 12 12/2 = 6
e3 3 2 0 0 1 18 18/2 = 9
z 3 5 0 0 0 0

Tableau 2
↓
Base x1 x2 e1 e2 e3 s.m R
e1 1 0 1 0 0 4 4
x2 0 1 0 1/2 0 6 ∞
← e3 3 0 0 −1 1 6 2
z 3 0 0 −5/2 0 −30

Variable entrante dans la base : x1 Variable sortante de la base : e3

Pivot : 3
 La méthode du simplexe Méthode du simplexe en tableaux

Tableau 2
Base
↓
x1 x2 e1 e2 e3 s.m R
e1 1 0 1 0 0 4 4
x2 0 1 0 1/2 0 6 ∞
← e3 3 0 0 −1 1 6 2
z 3 0 0 −5/2 0 −30

Tableau 3
Base x1 x2 e1 e2 e3 s.m
e1 0 0 1 1/3 −1/3 2
x2 0 1 0 1/2 0 6
x1 1 0 0 −1/3 1/3 2
z 0 0 0 −3/2 −1 −36

La méthode du simplexe Méthode du simplexe en tableaux

Tous les coecients de la dernière ligne (coecients de la fonction

objectif) sont négatifs ou nuls : on ne peut plus augmenter la fonction
objectif. Le tableau 3 est optimal et l'algorithme du simplexe s'arrête.
On a donc : x1∗ = 2 ; x2∗ = 6 et zmax = 36.
Interprétation économique :
L'entreprise doit produire 2 châssis de type 1 (en aluminium) et 6 châssis
de type 2 (en bois) pour réaliser un prot maximal de 36 UM.
A l'optimum les variables de base sont x1∗ = 2 ; x2∗ = 6 et e1∗ = 2 et les
variables hors base sont e2∗ = e3∗ = 0 .
La première contrainte n'est pas saturée : il reste une capacité disponible
dans l'atelier 1 (sous-emploi) égale à 2 heures par semaine.
La deuxième et la troisième contrainte sont saturées : il ne reste plus de
capacité disponible dans les ateliers 2 et 3 (plein emploi). En eet :
4 − x1∗ = 4 − 2 = 2
12 − 2x2∗ = 12 − 2 × 6 = 0
18 − (3x1∗ + 2x2∗ ) = 18 − (3 × 2 + 2 × 6) = 0.
La méthode du simplexe Cas général

4.2 Cas général :

Considérons un programme linéaire sous forme standard :
⎧
⎨ max z = c T x
(PS) Ax = b
⎩
x ≥0

où est une A matrice de type (m , n), m ≤ n et rang (A) = m.

Supposons connue une base B telle que la solution de base associée est
réalisable.
Notons :
B = {i1 , . . . , im } : l'ensemble des indices correspondants aux colonnes de B
(et donc aux variables de base),
N = {j1 , ..., jn−m } = {1, ..., n} \ B : l'ensemble des indices hors base,
N : la sous-matrice de A correspondant aux colonnes des indices hors base,
xB : le vecteur de Rm formé par les variables de base (xi , i ∈ B ),
xN : le vecteur de Rn−m formé par les variables hors base (xi , i ∈ N ).
 La méthode du simplexe Cas général

Rappelons que la solution de base associée à B est réalisable si :

xB = B −1 b ≥ 0.
En eectuant un partitionnement suivant les indices de B et ceux de N , on
peut écrire :
 
 xB 
Ax = b ⇐⇒ B N =b
xN
⇐⇒ B xB + N xN = b
⇐⇒ xB + B −1 N xN = B −1 b
⇐⇒ xB = B −1 b − B −1 N xN

La fonction objectif peut s'écrire :

z = cT x = ci xi + ci xi = cB xB + cN xN
i∈B i ∈N

avec cB = (ci1 , ..., cim ) et cN = (cj1 , ..., cjn−m )

La méthode du simplexe Cas général

Donc le PL est équivalent à la forme réduite associée à la base B :

⎧
⎨ max z = cB xB + cN xN
(PR) x + B −1 N xN = B −1 b
⎩ B
xB ≥ 0 , xN ≥ 0

On peut maintenant formuler le problème en réécrivant les contraintes et

l'objectif en fonction des variables hors base :
xB + B −1 N xN = B −1 b ⇐⇒ xB = B −1 b − B −1 N xN =⇒
z = cB xB + cN xN
= cB (B −1 b − B −1 N xN ) + cN xN
= (cN − cB B −1 N)xN + cB B −1 b
z = dN xN + z̄ ⇐⇒ dN xN = z − z̄

avec dN = cN − cB B −1 N ; z̄ = cB B −1 b
les composantes de dN s'appellent coûts réduits des variables hors base.
Ils interviennent de façon déterminante dans la méthode du simplexe.
La méthode du simplexe Cas général

Ainsi, le problème consiste à maximiser z sachant :

xB + B −1 N xN = B −1 b
dN xN = z − z̄

et xB ≥ 0 , xN ≥ 0.
La solution de base est donnée par : xN = 0 ; xB = b̄ = B −1 b.
Cette solution de base est réalisable signie que b̄ = B −1 b ≥ 0.
La valeur de la fonction objectif z associée à cette solution est z̄ .
Finalement, le tableau du simplexe associé à la base B est (à une
permutation de colonnes près) de la forme :
Base xB xN s.m
xB Im B 1N
− b̄ = B −1 b
−z 0 dN −z̄

dN = cN − cB B −1 N ; z̄ = cB B −1 b
 La méthode du simplexe Cas général

Par exemple, le tableau 2 du paragraphe 4.1 donne :

↓
Base x1 x2 e1 e2 e3 s.m
e1 1 0 1 0 0 4
x2 0 1 0 1/2 0 6
← e3 3 0 0 −1 1 6
z 3 0 0 −5/2 0 −30

Base xB xN s.m
xB Im B −1 N b̄ = B −1 b
z 0 dN z̄

xB = (e1 , x2 , e3 ): variables de base,

xN = (x1 , e2 ) : variables hors base,
dN = (3 , −5/2) ; b̄ = (4 , 6 , 6),
Solution de base : (x1 , x2 , e1 , e2 , e3 ) = (0 , 6 , 4 , 0 , 6),
Fonction objectif : z̄ = 30.
La méthode du simplexe Cas général

Remarques :
La forme tableau présente l'avantage de préserver la structure du
programme linéaire. En plus, elle met en évidence les opérations
matricielles (résolution des systèmes linéaires par exemple) mis en
÷uvre durant la résolution.
Les variables de base se distinguent par le fait qu'elles forment une
matrice identité dans le système des contraintes et n'interviennent pas
dans la fonction objectif. les variables hors base sont les variables
restantes et leur coecients dans la fonction objectif sont représentés
par les coûts réduits (vecteur dN ).
Rappelons que, une fois le choix du pivot établi, le passage d'un
tableau simplexe au tableau suivant s'eectue manuellement en
utilisant les règles de calculs :
 Les coecients de la ligne du pivot sont divisés par le pivot.
 Les coecients de la colonne du pivot (sauf le pivot) sont nuls.
 Les autres coecients sont obtenus par la règle du rectangle.

La méthode du simplexe Cas général

Dénition
1 Une solution de base xB associée à la base B est dite non dégénérée
si :
xB = B −1 b > 0
c-à-d le second membre du système réduit b̄ > 0
autrement dit, si toutes les variables de base sont strictement positives.
Dans le cas contraire, on dit que la solution de base est dégénérée.
2 Un programme linéaire est non dégénéré si toute solution de base
réalisable est non dégénérée.

Théorème (Critère d'optimalité)

Si
dN = cN − cB B −1 N ≤ 0

alors la solution de base réalisable xN = 0 ; xB = b̄ = B −1 b est optimale.

 La méthode du simplexe Cas général

Preuve du Théorème :

Soit x = (x1 , ..., xn ) une solution de base réalisable quelconque et soit

x∗ = (x1∗ , ..., xn∗ ) la solution de base associée à B .

Comme xN ≥ 0 (car x réalisable) et dN ≤ 0 (par hypothèse) on a :

dN xN = di xi ≤ 0
i ∈N

D'où :

z(x1 , ..., xn ) = dN xN + z̄ ≤ z̄ = z(x1∗ , ..., xn∗ ).

Étapes du simplexe (cas général) :

Si le critère d'optimalité ( dN ≤ 0) n'est pas vérié on va procéder soit à

une itération, soit on va découvrir que max z = +∞.

Supposons alors qu'il existe au moins une composante dj de dN telle que

dj > 0, j ∈ N .

La méthode du simplexe Cas général

Choix de la variable entrante :

Considérons l'indice j ∈N tel que

dj = max{dk ; k ∈ N }

et la colonne d'indice j de la matrice ĀN = B −1 N = (ākj , (1 ≤ k ≤ m).

On a les possibilités suivantes :

1 ākj ≤ 0, ∀ k = 1, ..., m
(Tous les termes de la colonne j de la variable entrante sont ≤ 0).
Dans ce cas l'ensemble réalisable est non borné et max z = +∞
2 Il existe k ∈ {1, ..., m} tel que ākj > 0
Dans ce cas on va procéder à une itération et

xj est la variable entrante dans la base.

La méthode du simplexe Cas général

Choix de la variable sortante :

On va supposer maintenant que le programme linéaire est non dégénéré.

Soit p l'indice vériant :

b̄p b̄p
= min{ ; āpj > 0}
āpj āpj

(On fait le rapport des coecients du s.m du tableau simplexe avec les

coecients de la colonne j de la variable entrante et on choisit le plus petit)

Dans ce cas, xp est la variable sortante de la base.

Théorème (Convergence de l'algorithme du simplexe)

Supposons que le programme linéaire est non dégénéré et qu'il admette au

moins une solution optimale (avec zmax ni). Alors après un nombre ni

d'itérations, l'algorithme du simplexe va trouver une solution de base

optimale.
 La méthode du simplexe Problèmes particuliers

4.3 Problèmes particuliers :

Dans le paragraphe précédent, nous avons fait les deux hypothèses

suivantes :

1 La connaissance d'une solution de base réalisable initiale.

2 Le programme linéaire est non dégénéré.

En général, ces hypothèses ne sont pas toujours vériées.

Détermination d'une base réalisable initiale :

Pour déterminer une base initiale réalisable, considérons tout d'abord le cas

où le PL est donné sous la forme canonique :

⎧
⎪
⎪ max z = c1 x1 + c2 x2 + ... + cn xn
⎪
⎪
⎪
⎪ a11 x1 + a12 x2 + ... + a1n xn ≤ b1
⎪
⎨ a21 x1 + a22 x2 + ... + a2n xn ≤ b2
(PC ) .
⎪
⎪ .
⎪
⎪
.
⎪
⎪ a x + am2 x2 + ... + amn xn ≤ bm
⎪
⎩ m1 1
x1 ≥ 0, . . . , xn ≥ 0

La méthode du simplexe Problèmes particuliers

En introduisant des variables d'écart (e1 , ..., em ) , nous obtenons le PL sous

forme standard :
⎧
⎪
⎪ max z = c1 x1 + c2 x2 + ... + cn xn + 0e1 + ... + 0en
⎪
⎪
⎪
⎪ a11 x1 + a12 x2 + ... + a1n xn + e1 = b1
⎪
⎨ a21 x1 + a22 x2 + ... + a2n xn + e2 = b2
(PS) .
⎪
⎪ .
⎪
⎪
.
⎪
⎪ a x + am2 x2 + ... + amn xn + em = bm
⎪
⎩ m1 1
x1 ≥ 0, . . . , xn ≥ 0, e1 ≥ 0, . . . , em ≥ 0
En posant
 
à = A Im ; x̃ = (x1 , ..., xn , e1 , ..., em )T ; c̃ = (c1 , ..., cn , 0, ..., 0)T
où Im est la matrice identité d'ordre m.
(PS) s'écrit alors sous la forme matricielle :
⎧
⎨ max z̃ = c̃ T x̃
Ãx̃ = b
⎩
x̃ ≥ 0

La méthode du simplexe Problèmes particuliers

Comme Im est inversible on a une solution de base initiale :

B = Im ; N = A ; xB = B −1 b = b ; xN = x = 0
Si b≥0 alors cette solution est en plus réalisable.

Le problème se pose dans le cas contraire c-à-d celui où il existe au moins

un indice j tel que bj < 0.

Dans ce cas, xB = b, xN = x = 0 est une solution de base mais non

réalisable et il faut procéder à une première étape qui consiste à déterminer

une solution de base réalisable de départ : c'est la phase I de la méthode

du simplexe.

Problème de dégénérescence :

Dans le cas où le PL est dégénéré, on peut avoir :

b̄p b̄p
= min{ ; āpj > 0} = 0
āpj āpj
Alors la fonction objectif z ne varie pas après le changement de base et par

conséquent on peut rencontrer les situations suivantes :

 La méthode du simplexe Problèmes particuliers

Lors de la détermination de la variable entrante, nous sommes en

présence d'au moins deux variables hors base ayant le même et le plus
élevé coecient strictement positif dans la dernière ligne.
Lors de la détermination de la variable sortante, nous sommes en
présence d'au moins deux variables de base ayant le même et le plus
petit rapport positif dans la dernière colonne.
il est possible, après un certain nombre d'itérations, de retrouver le
tableau de départ (problème de cyclage).

:
Lorsque plusieurs variables sont susceptibles d'entrer ou de sortir de la
base, on choisit toujours la variable xr ayant le plus petit indice r .

La méthode du simplexe Problèmes particuliers

Exemples :
T1
Base x1 x2 x3 x4 x5 x6 s.m R
x5 4 7 0 0 1 4 4 4/7
x4 2 8 0 1 0 3 0 0
x3 -2 9 1 0 0 2 0 0
z -5 2 0 0 0 5 -3
Variables candidates à enter dans la base : x2
Variables candidates à sortir de la base : x4 et x3 . On choisit donc x3 .
T2
↓
Base x1 x2 x3 e1 e2 e3 s.m R
← e1 1 2 5 1 0 0 4 2
e2 3 4 3 0 1 0 8 2
e3 2 4 1 0 0 1 12 3
z 2 3 1 0 0 1 0

La méthode du simplexe Problèmes particuliers

T3
↓
Base x1 x2 x3 e1 e2 e3 s.m
e1 1 2 5 1 0 0 3
e2 3 1 3 0 1 0 10
e3 2 8 1 0 0 1 8
z 3 3 2 0 0 0 0

T4
↓
Base x1 x2 e1 e2 s.m
e1 0 -2 1 -1 20
x1 1 0 0 2,5 3
z 0 16 0 -3 -32

Tous les coecients de la colonne de la variable entrante x2 sont négatifs

ou nuls : zmax = +∞
 La méthode du simplexe Problèmes particuliers

Un autre cas particulier : innité de solutions optimales

Si à la n des itérations, une variable est hors base avec un coecient nul
dans la dernière ligne du tableau optimal, alors on a une arête (face,...)
optimale. Les autres sommets optimaux peuvent être obtenus en faisant
rentrer cette variable dans la base. Considérons, par exemple, le tableau
optimal suivant :
Base x1 x2 e1 e2 s.m
x1 1 0 1 1 3
x2 0 1 -1 -2 2
z 0 0 -1 0 -8
On fait entrer e2 dans la base et x1 sera alors la variable sortante. Ainsi, on
obtient une autre solution optimale :
Base x1 x2 e1 e2 s.m
e2 1 0 1 1 3
x2 2 1 1 0 8
z 0 0 1 0 -8

La méthode du simplexe Simplexe avec minimisation

4.4 Simplexe avec minimisation de l'objectif :

Dans le cas de minimisation de l'objectif, les itérations et l'optimalité de la
méthode du simplexe sont déterminés par les critères suivants :
Critère de la variable entrante : On choisit la variable hors base
ayant le coût réduit le plus négatif.
Critère de la variable sortante : le même que dans le cas de
maximisation, puisque ce critère est lié à la réalisabilité des variables.
Critère d'optimalité : L'algorithme du simplexe s'arrête quand tous
les coûts réduits des variables hors base (coecients de la dernière
ligne du tableau simplexe) sont tous positifs ou nuls.
Les critères précédents découlent de la propriété suivante :
minimiser z = c1 x1 + ... + cn xn revient à maximiser −z .

La méthode du simplexe Simplexe avec minimisation

Exemple :
Soit le problème : ⎧
⎪
⎪ min −x1 − 2x2
⎪
⎪
⎨ −3x1 + 2x2 ≤ 2
(PM) −x1 + 2x2 ≤ 4
⎪
⎪
⎪
⎪ x + x2 ≤ 5
⎩ 1
x1 , x2 ≥ 0
En rajoutant les variables d'écart on obtient la forme standard :
⎧
⎪
⎪ min −x1 − 2x2
⎪
⎪
⎨ −3x1 + 2x2 + e1 = 2
(PMS) −x1 + 2x2 + e2 = 4
⎪
⎪
⎪
⎪ x + x2 + e3 = 5
⎩ 1
x1 , x2 , e1 , e2 , e3 ≥ 0
On remarque que tous les termes du second membre (2, 4 et 5) sont
positifs. Dans notre cas, l'obtention d'une solution de base réalisable
initiale est triviale. Elle correspond aux variables de base e1 , e2 , e3 et
variables hors base x1 , x2 .
La sol tion de base réalisable initiale est
 La méthode du simplexe Simplexe avec minimisation

Les contraintes de (PMS) peuvent être représentées par le système :

Ãx̃ = b̃
x̃ ≥ 0
⎛ ⎞
⎛ ⎞ x1 ⎛ ⎞
−3 2 1 0 0 ⎜ x2 ⎟ 2
⎜ ⎟
à = ⎝ −1 2 0 1 0 ⎠ ; x̃ = ⎜
⎜ e1 ⎟ ; b̃ = b = ⎝ 4 ⎠
⎟
1 1 0 0 1 ⎝ e2 ⎠ 5
e3
z = c̃ T x̃ = −x1 − 2x2 + 0e1 + 0e2 + 0e3 avec c̃ = (x1 , x2 , 0 , 0 , 0)T
⎛ ⎞
1 0 0
Une base initiale est donnée par la matrice identité : I = ⎝ 0 1 0 ⎠
0 0 1
La solution de base réalisable initiale est :
(x1 , x2 , e1 , e2 , e3 ) = (0 , 0 , 2 , 4 , 5)

La méthode du simplexe Simplexe avec minimisation

Tableau 1
Base x1
↓
x2 e1 e2 e3 s.m R
← e1 -3 2 1 0 0 2 1
e2 -1 2 0 1 0 4 2
e3 1 1 0 0 1 5 5
z -1 -2 0 0 0 0
x2 variable entrante dans la base.
e1 variable sortante de la base.
Tableau 2
Base
↓
x1 x2 e1 e2 e3 s.m R
x2 -3/2 1 1/2 0 0 1 −2/3
← e2 2 0 -1 1 0 2 1
e3 5/2 0 -1/2 0 1 4 8/5
z -4 0 1 0 0 2

La méthode du simplexe Simplexe avec minimisation

Tableau 3
Base x1 x2
↓
e1 e2 e3 s.m R
x2 0 1 -1/4 3/4 0 5/2 10
x1 1 0 -1/2 1/2 0 1 -2
← e3 0 0 3/4 -5/4 1 3/2 2
z 0 0 -1 2 0 6

Tableau 4
Base x1 x2 e1 e2 e3 s.m
x2 0 1 0 1/3 1/3 3
x1 1 0 0 -1/3 2/3 2
e1 0 0 1 -5/3 4/3 2
z 0 0 0 1/3 4/3 8
Tous les coecients de la dernière ligne sont positifs ou nuls : le tableau 4
est optimal et x∗1 = 2 ; x∗2 = 3 ; e∗1 = 2 ; e∗2 = e∗3 = 0 ; z∗ = −8
 La méthode du simplexe Initialisation de la méthode du simplexe

5. Initialisation de la méthode du simplexe

Jusqu'ici nous avons vu comment trouver une solution de base réalisable
initiale lorsque le programme linéaire de départ est sous forme canonique :
⎧
⎨ max z = c T x
Ax ≤ b
⎩
x ≥0

alors en ajoutant une variable d'écart ei à chaque contrainte pour la

transformer en une égalité, la matrice à qui
 correspond
 à l'ensemble des
contraintes Ãx = b prend la forme : Ã = A Im
avec x̃ = (x1 , ..., xn , e1 , ..., em )T et Im est la matrice identité d'ordre m.
Le passage en forme standard permet d'avoir une base initiale
B0 = {ei , i = 1...m} facilement.
Si le second membre est positif alors cette base est réalisable et correspond
à l'origine : xN = (x1 , ..., xn ) = 0 et xB = (e1 , ..., em ).

La méthode du simplexe Initialisation de la méthode du simplexe

Mais dans le cas général on peut avoir les situations suivantes :

L'une des m contraintes possède un second membre bi négatif, alors il
y a violation de la contrainte de positivité pour la variable d'écart
concernée (ei = bi < 0).
Le problème contient déjà des contraintes d'égalité alors ces dernières
n'ont pas besoin de l'adjonction de variables d'écart et il n'existe pas
de sous-matrice identité dans la matrice Ã.
Il est alors nécessaire de mettre en place une procédure pour obtenir une
matrice identité comme matrice de base initiale et qui correspond à une
solution de base initiale réalisable. En général, une telle procédure est basée
sur l'adjonction de variables articielles.

La méthode du simplexe Initialisation de la méthode du simplexe

Méthode du grand M :
Considérons le PL suivant :
⎧
⎪
⎪ max z = x1 + x2
⎨
2x1 + x2 ≥ 4
(P1 )
⎪
⎪ x + 2x2 = 6
⎩ 1
x1 , x2 ≥ 0

On remarque que les termes du second membre sont tous positifs, mais la
1ère contrainte est de type ≥ et la 2ème contrainte est de type =
On rajoute une variable d'écart e1 à la 1ère contrainte (pour avoir l'égalité).
On rajoute en plus deux variables articielles a1 et a2 aux 2 contraintes.
En plus, on transforme la fonction objectif en pondérant les variables
articielles avec un coecient −M où M est un nombre supposé positif et
assez grand.
 La méthode du simplexe Initialisation de la méthode du simplexe

On obtient alors le PL :
⎧
⎪
⎪ max z = x1 + x2 −Ma1 − Ma2
⎨
2x1 + x2 − e1 + a1 = 4
⎪ x1 + 2x2 + a2 = 6
⎪
⎩
x1 , x2 , e1 , a1 , a2 ≥ 0

qui est sous forme standard.

On remarque que les contraintes du dernier problème peuvent s'écrire :
Ãx̃ = b̃
x̃ ≥ 0
⎛ ⎞
x1
  ⎜ ⎟  
à =
2 1 −1 1 0 ⎜
; x̃ = ⎜
x2 ⎟
⎟ ; b̃ = b = 4
1 2 0 0 1 ⎜
⎝
e1
a1
⎟
⎠ 6
a2

La méthode du simplexe Initialisation de la méthode du simplexe

La solution de base initiale est donnée par :

Variables de base : a1 = 4 ; a2 = 6
Variables hors base : x1 = x2 = e1 = 0
Pour établir le premier tableau du simplexe, il faut maintenant exprimer les
variables de base en fonction des variables hors base.
2x1 + x2 − e1 + a1 = 4 ⇒ a1 = 4 − 2x1 − x2 + e1
x1 + 2x2 + a2 = 6 a2 = 6 − x1 − 2x2

La fonction objectif devient alors :

z = x1 + x2 −Ma1 − Ma2
= x1 + x2 − M(4 − 2x1 − x2 + e1 ) − M(6 − x1 − 2x2 )
z = (3M + 1)x1 + (3M + 1)x2 − Me1 − 10M

Notons aussi que : si x1 = x2 = e1 = 0 alors z = z̄ = −10M .

La méthode du simplexe Initialisation de la méthode du simplexe

Nous pouvons maintenant démarrer le simplexe avec le tableau suivant :

Tableau 1
Base ↓
x1 x2 e1 a1 a2s.m R
← a1 2 1 -1 1 0 4 2
a2 1 2 0 0 1 6 6
−z 3M+1 3M+1 -M 0 0 10 M
x1et x2 candidates à entrer dans la base. En appliquant la règle de Bland,
x1entrante. a1 sort de la base.
Tableau 2
Base x1 ↓
x2 e1 a1 a2 s.m R
x1 1 1/2 -1/2 1/2 0 2 4
← a2 0 3/2 1/2 -1/2 1 4 8/3
−z 0 (3M+1)/2 (M+1)/2 -(3M+1)/2 0 -2 + 4M
 La méthode du simplexe Initialisation de la méthode du simplexe

Tableau 3
Base x1 x2
↓
e1 a1 a2 s.m R
x1 1 0 -2/3 2/3 -1/3 2/3 -1
← x2 0 1 1/3 -1/3 2/3 8/3 8
−z 0 0 1/3 -M-1/3 -M-1/3 -10/3

Tableau 4
Base x1 x2 e1 a1 a2 s.m
x1 1 2 0 0 1 6
e1 0 3 1 -1 2 8
−z 0 -1 0 -M -M-1 -6

Le tableau 4 est optimal et x1∗ = 6 ; x2∗ = 0 ; e1∗ = 8 ; zmax = 6.

On remarque que chaque variable articielle (a1 et a2 ) a été mise hors base
de telle sorte que leurs valeurs sont nulles dans le tableau optimal.

La méthode du simplexe Initialisation de la méthode du simplexe

En général, la méthode du grand M ( big M ,méthode M) consiste à :

Introduire des variables articielles ai , (i = 1, ..., p) dans les
contraintes qui posent un problème pour la réalisabilité de la base
initiale.
m
Remplacer la fonction objectif par z = max c T x − M ai
i =1
où M est une constante positive assez grande.
En pratique, on n'est pas obligé de donner une valeur à M.
Chaque fois que M est comparé à un nombre, il sera toujours
considéré comme plus grand.
Si la méthode du simplexe se termine avec une solution (x ∗ , a∗ ) telle
que a∗ = (a1∗ , ..., ap∗ ) = 0, alors x ∗ est une solution optimale du
problème de départ.
Si la méthode du simplexe se termine avec une solution (x ∗ , a∗ ) telle
que a∗ = 0 (c-à-d qu'au moins une variable articielle est encore dans
la base dans le tableau optimal), alors le problème est non réalisable.

La méthode du simplexe Initialisation de la méthode du simplexe

Chapitre 3 :
Résolution des programmes linéaires
La dualité
 Dualité Exemple introductif

1. Exemple introductif
Une entreprise E1 fabrique les produits P1 et P2. Elle utilise les matières
premières M1, M2 et M3, à raison de :
2 tonnes de M1, 1 tonne de M2 et 3 tonnes de M3
par unité produite de P1,
1 tonne de M1, 3 tonnes de M2 et 4 tonnes de M3
par unité produite de P2.
Elle dispose de :
50 tonnes de M1, 25 tonnes de M2 et 60 tonnes de M3.
Le bénéce net est de 5000 UM par unité de P1 et de 2000 UM par unité
de P2.
Le problème que se pose l'entreprise est le suivant :
Quelle quantité de chacun des deux produits P1 et P2 l'entreprise doit-elle
fabriquer pour que le bénéce soit maximal ?

Dualité Exemple introductif

Produit P1 Produit P2 Disponibilité

Quantité de m.p M1 (tonnes) 2 1 50
Quantité de m.p M2 (tonnes) 1 3 25
Quantité de m.p M3 (tonnes) 3 4 60
Prix unitaire (UM) 5000 2000
Le problème de l'entreprise E1 se modélise par le programme linéaire :
⎧
⎪
⎪ max z = 5000x1 + 2000x2
⎪
⎪
⎪
⎨ 2x1 + x2 ≤ 50
⎪ Quantité de m.p M1
(P) x1 + 3x2 ≤ 25 Quantité de m.p M2
⎪
⎪ 3x1 + 4x2 ≤ 60
⎪
⎪ Quantité de m.p M3
⎪
⎪
⎩
x1 ≥ 0 ; x2 ≥ 0

x1 : quantité de produits P1 fabriqués

x2 : quantité de produits P2 fabriqués

Dualité Exemple introductif

Supposons qu'une autre entreprise E2, en rupture de stock, désire racheter
les matières premières (M1, M2 et M3) de l'entreprise E1. Le problème
qu'elle va se poser et le suivant :
Quel doit être le prix unitaire minimum d'achat y1 , y2 et y3 de chaque
matière première, pour que :
la valeur totale des m.p consommées par chaque produit P1 et P2 soit
supérieure ou égale à leurs prix unitaires respectifs, c1 = 5000 UM et
c2 = 2000 UM (pour que cela reste intéressant pour l'entreprise E1),
le prix total d'achat des matières premières disponibles soit minimum ?
Ce deuxième problème peut se mettre sous la forme :
⎧
⎪
⎪ min w = 50y1 + 25y2 + 60y3
⎪
⎨
(D)
2y1 + y2 + 3y3 ≥ 5000 contrainte produit P1
⎪
⎪ y1 + 3y2 + 4y3 ≥ 2000 contrainte produit P2
⎪
⎩
y1 ; y2 ; y3 ≥ 0
yi : prix unitaire d'achat de la m.p Mi (i = 1, 2, 3)
 Dualité Exemple introductif

Le problème (D) est appelé problème dual de (P).

Le problème (P) est appelé problème primal.
Remarque
Comparons les deux problèmes, primal (P) et dual (D) :
⎧
⎪
⎪ max z = 5000x1 + 2000x2
⎪
⎪
⎪
⎨ 2x1 + x2 ≤ 50
(P) x1 + 3x2 ≤ 25
⎪
⎪
⎪
⎪ 3x1 + 4x2 ≤ 60
⎪
⎩
x1 , x2 ≥0
⎧
⎪
⎪ min w = 50y1 + 25y2 + 60y3
⎪
⎨
2y1 + y2 + 3y3 ≥ 5000
(D)
⎪
⎪ y1 + 3y2 + 4y3 ≥ 2000
⎪
⎩
y1 , y2 , y3 ≥0

Dualité Exemple introductif

Les coecients de la fonction objectif w de (D) correspondent aux
coecients du second membre de (P).
De même, Les coecients de la fonction objectif z de (P) correspondent
aux coecients du second membre de (D).
Si nous désignons par :
A, b et c respectivement la matrice des contraintes, le second membre et le
vecteur des coûts du problème (P),
A , b  et c  respectivement la matrice des contraintes, le second membre et
le vecteur des coûts du problème (D),
alors on a :
⎛ ⎞ ⎛ ⎞
2 1 50  
5000
A = ⎝ 1 3 ⎠ ; b = ⎝ 25 ⎠ ; c =
2000
3 4 60
⎛ ⎞
    50
2 1 3 5000
A = = AT ; b  = = c ; c  = ⎝ 25 ⎠ = b
1 3 4 2000
60

Dualité Exemple introductif

Le problème primal (P) et son dual (D) sont liés par les relations suivantes :

Le problème (P) contient 2 variables (x1 et x2 ) et 3 contraintes.

Le problème (D) contient 3 variables (y1 , y2 et y3 ) et 2 contraintes.
On en conclut que le nombre de variables de (P) est égal au nombre
de contraintes de (D) et réciproquement, le nombre de variables de
(D) est égal au nombre de contraintes de (P).
On peut vérier facilement que le dual de (D) est le problème (P).
Le problème (P) est un problème de maximisation. Tandis que (D) est
un problème de minimisation.
Le minimum wmin atteint par le problème (D) est égal au maximum
zmax du problème (P).
Cela signie dans notre cas que le prix d'achat minimal des matières
premières par l'entreprise E2 est égal au prot maximal que peut en
tirer l'entreprise E1 en vendant ces matières premières.
 Dualité Formulation générale du problème dual

2. Formulation générale du problème dual

Formulation algébrique :
Soit un programme linéaire sous forme canonique :
⎧
⎪
⎪ max z = c1 x1 + c2 x2 + ... + cn xn
⎪
⎪
⎪
⎪ a11 x1 + a12 x2 + ... + a1n xn ≤ b1
⎪
⎪
⎪
⎨ a x + a x + ... + a x ≤ b
21 1 22 2 2n n 2
(P)
.
⎪ .
⎪
⎪
⎪ .
⎪
⎪
⎪
⎪ a x + am2 x2 + ... + amn xn ≤ bm
⎪
⎩ m1 1
x1 ≥ 0, . . . , xn ≥ 0

n variables x1 , x2 ,..., xn et m contraintes.

Coecients du second membre : b1 , b2 ,..., bm .
Coecients (coûts) de la fonction objectif : c1 , c2 ,..., cn
Matrice des contraintes A de type (m, n) (m lignes et n colonnes).

Dualité Formulation générale du problème dual

Le problème dual de (P) est déni par :

⎧
⎪
⎪ min w = b1 y1 + b2 y2 + ... + bm ym
⎪
⎪
⎪
⎪ a11 y1 + a21 y2 + ... + am1 ym ≥ c1
⎪
⎪
⎪
⎨ a y + a y + ... + a y ≥ c
12 1 22 2 m2 m 2
(D)
.
⎪ .
⎪
⎪
⎪ .
⎪
⎪
⎪
⎪ a y + am2 y2 + ... + amn ym ≥ cn
⎪
⎩ 1n 1
y1 ≥ 0, . . . , ym ≥ 0

m variables y1 , y2 ,..., ym et n contraintes.

Coecients du second membre : c1 , c2 ,..., cn .
Coecients (coûts) de la fonction objectif : b1 , b2 ,..., bm
Matrice des contraintes : A = AT de type (n, m) (n lignes et m colonnes).

Dualité Formulation générale du problème dual

Formulation matricielle :
⎧ ⎧
⎨ max z = c T x ⎨ min w = bT y
(P) Ax ≤ b (D) AT y ≥ c
⎩ ⎩
x ≥0 y ≥0
Exemples :
⎧
⎪
⎪ max z = x1 + 3x2
⎪
⎪
⎪
⎨ x1 + x2 ≤ 14
(P1 ) −2x1 + 3x2 ≤ 12
⎪
⎪
⎪
⎪ 2x1 − x2 ≤ 12
⎪
⎩
x1 , x2 ≥0
⎧
⎪
⎪ min w = 14y1 + 12y2 + 12y3
⎪
⎨
y1 − 2y2 + 2y3 ≥ 1
(D1 )
⎪
⎪ y1 + 3y2 − y3 ≥ 3
⎪
⎩
y1 , y2 , y3 ≥0
 Dualité Formulation générale du problème dual
⎧ ⎧
⎪
⎪ min z = −2x1 + 9x2 ⎪
⎪ min z = −2x1 + 9x2
⎪
⎪ ⎪
⎪
⎪
⎨ 3x1 + x2 ≥ 10 ⎪
⎨ 3x1 + x2 ≥ 10
(P2 ) 4x1 − 3x2 ≤ 8 ⇐⇒ −4x1 + 3x2 ≥ −8
⎪
⎪ ⎪
⎪
⎪
⎪ x1 − x2 ≤ 6 ⎪
⎪ −x1 + x2 ≥ −6
⎪
⎩ ⎪
⎩
x1 , x2 ≥0 x1 , x2 ≥0
Le dual de (P2 ) est :
⎧
⎪
⎪ max w = 10y1 − 8y2 − 6y3
⎨
3y1 − 4y2 − y3 ≤ −2
(D2 )
⎪
⎪ y + 3y2 + y3 ≤ 9
⎩ 1
y1 , y2 , y3 ≥0
Question : Dual de (D2) ?
⎧
⎪
⎪ min z = −2u1 + 9u2
⎪
⎪
⎨ 3 u1 + u2 ≥ 10
(D̄2 ) −4u1 + 3u2 ≥ −8 Le dual du dual de (P2 ) = (P2 ).
⎪
⎪
⎪
⎪ −u1 + u2 ≥ −6
⎩
u1 , u2 ≥0

Dualité Correspondances entre le primal et le dual

3. Correspondances entre le primal et le dual

Problème Primal Problème Dual

maximisation minimisation
second membre des contraintes coecient de la fonction objectif
coecient de la fonction objectif second membre des contraintes
m contraintes m variables de décision
n variables de décision n contraintes
i ème contrainte de type ≤ i ème variable ≥ 0
j ème variable ≥ 0 j ème contrainte de type ≥

Dualité Théorème de dualité

4. Théorème de dualité
Avec les notations du paragraphe 2, on a les résultats suivants :
Théorème 1 (Dualité forte)
Le problème primal (P) admet une solution optimale x ∗ si et seulement si le
problème dual (D) admet une solution optimale y ∗ , et dans ce cas, on a :
c T x ∗ = b T y ∗ autrement dit z ∗ = w ∗ .

Théorème 2 (conditions de complémentarité)

Soient x une solution réalisable du problème primal (P) et y une solution
réalisable du problème dual (D). Alors x et y sont optimales ssi :
 n 
yi bi − aij xj = 0, i = 1, ..., m (1)
j=1
 m 
yi aij − cj xj = 0, j = 1, ..., n (2)
i=1
 Dualité Théorème de dualité

Par exemple :
⎧
⎪
⎪ max z = 5000x1 + 2000x2 ⎧
⎪
⎪
⎪ ⎪
⎪ min w = 50y1 + 25y2 + 60y3
⎪
⎨ 2x1 + x2 ≤ 50 ⎪
⎨
2y1 + y2 + 3y3 ≥ 5000
(P) x1 + 3x2 ≤ 25 (D)
⎪
⎪ ⎪
⎪ y1 + 3y2 + 4y3 ≥ 2000
⎪
⎪
⎪ 3x1 + 4x2 ≤ 60 ⎪
⎩
⎪
⎩ x ≥0; x ≥0 y1 , y2 , y3 ≥ 0
1 2

Si x = (x1 , x2 ) réalisable pour P et y = (y1 , y2 , y3 ) réalisable pour D ,

alors x et y solutions optimales ssi :
y1 (50 − 2x1 − x2 ) = 0 ; y2 (25 − x1 − 3x2 ) = 0 ; y3 (60 − 3x1 − 4x2 ) = 0
(2y1 + y2 + 3y3 − 5000) x1 = 0 ; (y1 + 3y2 + 4y3 − 2000) x2 = 0

Dualité Théorème de dualité

Une interprétation économique du théorème 1 a été donnée dans le
paragraphe 2 sur l'exemple introductif.
Les problèmes primal et dual peuvent s'écrire :
⎧ n ⎧
⎪ m
⎪
⎪ ⎪
⎪
⎪
⎪ max z = cj xj ⎪
⎪ min w = bi yi
⎪
⎪ ⎪
⎪
⎨ j=1 ⎨ i=1
n m
(P) (D)
⎪
⎪ aij xj ≤ bi (i = 1, ..., m) ⎪
⎪ aij yi ≥ cj (j = 1, n)
⎪
⎪ ⎪
⎪
⎪
⎪ j= 1 ⎪
⎪ i=1
⎪
⎩ x ≥ 0 (j = 1, ..., n) ⎩
j yi ≥ 0 (i = 1, m)
Soient x ∗ une solution optimale de (P) et y ∗ une solution optimale de (D).
D'après le théorème 2, on a :
 n 
yi∗ bi − aij xj∗ = 0, i = 1, ..., m (3)
j=1
 m 
yi∗ aij − cj xj∗ = 0, j = 1, ..., n (4)
i =1

Dualité Théorème de dualité

Conséquences :
Si la i ème contrainte du problème primal (P) est non saturée alors
n
bi − aij xj∗ = 0
j=1

et la relation (3) entraîne que yi∗ = 0.

Si la j ème contrainte du problème dual (D) est non saturée alors
m
yi∗ aij − cj = 0
i=1

et la relation (4) entraîne que xj∗ = 0.

Si yi∗ > 0 alors (3) ⇒ la i ème contrainte de (P) est saturée.
Si xj∗ > 0 alors (4) ⇒ la j ème contrainte de (D) est saturée.
 Dualité Interprétation économique des variables duales

5. Interprétation économique des variables duales

Considérons le problème de production suivant :
Une entreprise fabrique 2 produits P1 et P2. Soient x1 et x2 leurs quantités
respectives.
Leurs marges respectives sont de 4 UM et 3 UM.
Pour produire une unité du produit P1 on utilise 2 unités de matière
première et 5 heures de travail, tandis que pour une unité de P2 on a
besoin de 1 unité de matière première et de 6 heures de travail.
Le stock est de 3 unités et le nombre d'heures de travail par jour est de 11h.
Ce problème peut être modéliser par le programme linéaire suivant :
⎧
⎪
⎪ max z = 4x1 + 3x2
⎪
⎨
(P)
2x1 + x2 ≤ 3 Quantité de m.p
⎪
⎪
⎪
5x1 + 6x2 ≤ 11 Nombre d'heures de travail/jour
⎩
x1 ≥ 0 ; x2 ≥ 0

Dualité Interprétation économique des variables duales

Le chef d'entreprise voudrait savoir ce que lui rapporterait le fait que son
atelier soit ouvert une heure de plus par jour. Autrement dit, il voudrait
connaître l'augmentation de sa marge bénéciaire si le deuxième coecient
du second membre passait de 11 à 12. On obtient alors un deuxième P.L :
⎧
⎪
⎪ max z = 4x1 + 3x2
⎪
⎨
(P  )
2x1 + x2 ≤ 3 (Quantité de m.p)
⎪
⎪
⎪
5 x1 + 6 x2 ≤ 12 (Nombre d'heures de travail/jour)
⎩
x1 ≥ 0 ; x2 ≥ 0

La solution optimale de (P) est : A = (1, 1) et zmax = 7 UM.

La solution optimale de (P  ) est : A = (6/7, 9/7) et zmax
 = 51/7 UM.
L'augmentation de l'objectif est de : Δz = 51/7 − 7 = 2/7.

Dualité Interprétation économique des variables duales

D'autre part, le dual de (P) s'écrit :

⎧
⎪
⎪ min w = 3y1 + 11y2
⎪
⎨
(D)
2y1 + 5y2 ≥ 4
⎪
⎪ y1 + 6y2 ≥ 3
⎪
⎩
y1 ≥ 0 ; y2 ≥ 0

Le problème dual (D) a pour solution optimale : (y1∗ , y2∗ ) = (9/7, 2/7).
Donc y2∗ représente l'augmentation de l'objectif si on augmente le nombre
d'heures de travail/jour de 1 unité. Si on avait augmenté la capacité de
stockage d'une unité (c-à-d de 3 à 4) sans augmenter le nombre d'heures,
on aurait pu constater une augmentation de l'objectif égale à 9/7.
En général on a le résultat suivant :
Si on augmente la i ème composante du second membre du problème
primal (bi ) d'une unité, alors la fonction objectif augmentera d'une
quantité égale à la i ème variable duale optimale (yi∗ ).
 Dualité Interprétation économique des variables duales

Remarques
Les valeurs des variables duales yi sont appelées coûts marginaux ou
valeurs marginales.
Si une contrainte d'indice i est non saturée, alors les relations de
complémentarité entraînent que yi∗ = 0, c-à-d le coût marginal
d'indice i est nul. Donc on n'a pas intérêt à augmenter la capacité si
on n'a pas utilisé toutes les ressources.
Si le coût marginal d'indice i est non nul c-à-d yi∗ = 0, alors la
contrainte d'indice i est saturée ; cela signie que toutes les ressources
ont été utilisées, donc une augmentation de la capacité permettra
d'augmenter le bénéce.

Passage du tableau optimal primal au tableau optimal dual et vice versa

Primal Dual

La valeur optimale de la fonction objectif z = La valeur optimale de la fonction objectif w

Colonne s.m des variables de base associées
Coûts marginaux des variables hors base Signe opposé
(Valeurs optimales des variables de base associées)
Colonne second membre Signe opposé Coûts marginaux
La variable d’écart tj hors base (tj = 0)
La variable de décision xj en base (xj > 0)
(Contrainte d’indice j saturée)
La variable d’écart tj en base (tj > 0)
La variable de décision xj hors base (xj = 0)
(Contrainte d’indice j non saturée)
La variable d’écart ei en base (ei > 0)
La variable de décision yi hors base (yi = 0)
(Contrainte d’indice i non saturée)
La variable d’écart ei hors base (ei = 0)
La variable de décision yi en base (yi > 0)
(Contrainte d’indice i saturée)
Ligne xj en base Signe opposé Colonne tj hors base

Ligne ei en base Signe opposé Colonne yi hors base

Colonne xj hors base Signe opposé Ligne tj en base

Colonne ei hors base Signe opposé Ligne yi en base

Dualité Exercice d'application

Exercice d'application :
Une entreprise fabrique les produits P1 et P2. Elle utilise les matières

premières M1, M2 et M3. Les quantités (en tonnes) de chaque matière

première par unité de produit fabriqué, les capacités disponibles (tonnes)

ainsi que les marges unitaires sont rapportées dans le tableau ci-dessous :

Produit P1 Produit P2 Disponibilité

Quantité de m.p M1 1 3 96

Quantité de m.p M2 1 1 40

Quantité de m.p M3 7 4 238

Prix unitaire (UM) 15 25

1 Formuler un P.L (P) aidant l'entreprise à maximiser son chire

d'aaires et résoudre (P) par l'algorithme du simplexe.

2 Donner le P.L dual (D) et ses valeurs optimales ( y1∗ , y2∗ , y3∗ , w ∗ ).
3 Si la fabrique pouvait augmenter la quantité de matière première M1

ou M2, dans laquelle serait-il conseillé d'investir en premier ?

4 Établir le tableau optimal dual.

 Dualité Exercice d'application

Exercice d'application - corrigé :

1)
Variables de décision :
x1 : quantité de produits P1 fabriqués

x2 : quantité de produits P2 fabriqués

Programme linéaire :
⎧
⎪
⎪ max z = 15x1 + 25x2
⎪
⎪
⎪
⎪
⎨ x1 + 3x2 ≤ 96 Contrainte quantité de m.p M1

(P) x1 + x2 ≤ 40 Contrainte quantité de m.p M2

⎪
⎪
⎪ 7x1 + 4x2 ≤ 238
⎪
⎪
Contrainte quantité de m.p M3
⎪
⎩
x1 ≥ 0 ; x2 ≥ 0

Dualité Exercice d'application

Forme standard du problème primal :
⎧
⎪
⎪ max z = 15x1 + 25x2
⎪
⎪
⎨ x1 + 3x2 + e1 = 96
(P.S) x1 + x2 + e2 = 40
⎪
⎪
⎪ 7x + 4x2 + e3 = 238
⎪
⎩ 1
x1 , x2 , x3 , e1 , e2 , e3 ≥ 0

Tableau 1
↓
Base x1 x2 e1 e2 e3 s.m R

← e1 1 3 1 0 0 96 / = 32
96 3

e2 1 1 0 1 0 40 / = 40
40 1

e3 7 4 0 0 1 238 238/4 = 59, 5

−z 15 25 0 0 0 0

Variable entrante : x2 .
Variable sortante : e1 .
Pivot : 3

Dualité Exercice d'application

Tableau 2
↓
Base x1 x2 e1 e2 e3 s.m R

x2 /
1 3 1 / 1 3 0 0 32 96

← e2 2/3 0 −1/3 1 0 8 12

e3 /
17 3 0 −4/3 0 1 110 238 4/ = 19, 4
−z 20/3 0 −25/3 0 0 -800

Variable entrante : x1 ; Variable sortante : e2 ; Pivot : /

2 3

Tableau 3
Base x1 x2 e1 e2 e3 s.m

x2 0 1 /
1 2 −1/2 0 28

x1 1 0 −1/2 3/2 0 12

e3 0 0 3/2 −17/2 1 42

−z 0 0 −5 −10 0 −880
Le tableau 3 est optimal car tous les coecients de la dernière ligne −z
sont négatifs ou nuls.
 Dualité Exercice d'application

x1∗ = 12 ; x2∗ = 28 ; e1∗ = e2∗ = 0 ; e3∗ = 42 ; z ∗ = 880.

L'entreprise doit fabriquer 12 produits P1 et 28 produits P2 pour réaliser un
prot maximal de 880 UM.

2) ⎧
⎪
⎪ min w = 96y1 + 40y2 + 238y3
⎪
⎨
y1 + y2 + 7y3 ≥ 15 contrainte produit P1
(D)
⎪
⎪ 3 y1 + y2 + 4y3 ≥ 25 contrainte produit P2
⎪
⎩
y1 ; y2 ; y3 ≥ 0
yi : prix unitaire d'achat de la m.p Mi (i = 1, 2, 3)
D'après la ligne −z du tableau 3, les coûts marginaux de e1 , e2 et e3 sont
respectivement : −5, −10 et 0. Donc
y1∗ = 5 ; y2∗ = 10 ; y3∗ = 0 et w ∗ = z ∗ = 880
(Voir passage du tableau optimal primal au tableau optimal dual).

Dualité Exercice d'application

3)
On a y1∗ = 5 et y2∗ = 10, donc une augmentation de la quantité de la m.p
M1 (resp. M2 ) d'une tonne va entraîner une amélioration du chire
d'aaires de 5 UM (resp. 10 UM). Ainsi l'entreprise a intérêt à investir
dans la quantité de la m.p M2 en premier.

Dualité Exercice d'application

4) Il faut appliquer les règles de passage du tableau optimal primal au

tableau optimal dual.
La dernière ligne du tableau 3 donne :
w ∗ = 880 ; y1∗ = 5 ; y2∗ = 10 ; y3∗ = 0 ; t1∗ = 0 ; t2∗ = 0
(t1 et t2 sont les variables d'écart associées au problème dual) ;
Le s.m du tableau optimal dual est donné par la dernière ligne du tableau
optimal primal avec un signe opposé.
De même, la dernière ligne du tableau optimal dual est déduite du s.m du
tableau optimal primal avec un signe opposé.
On peut faire les correspondances suivantes :
x ←→ t
i i y ←→ e
i i

Si une variable est dans la base son correspondant est hors base :
e1 et e2 sont hors base dans le primal donc leurs correspondants y1 et y2
sont dans la base pour le dual.
 Dualité Exercice d'application
case (variable1, variable2) = - (case correspondant1, correspondant 2).
Exemples :
case (y1 ,y3 ) = - case (e1 ,e3 )= -3/2 case (y1 ,t1 ) = - case (e1 ,x1 ) = 1/2

Tableau optimal primal

Base x1 x2 e1 e2 e3 s.m
x2 0 1 1/2 −1/2 0 28
x1 1 0 −1/2 3/2 0 12
e3 0 0 3/2 −17/2 1 42
−z 0 0 −5 −10 0 −880

Tableau optimal dual

Base y1 y2 y3 t1 t2 s.m
y1 1 0 -3/2 1/2 -1/2 5
y2 0 1 17/2 -3/2 1/2 10
−w 0 0 -42 -12 -28 -880