30 CHAPITRE 3.

MÉTHODE DU SIMPLEXE
rendons la colonne associé a e1 unitaire
Variables de base x1 x2 e 1 e 2 e3 −z b R
1 1
L1 ← L1 + 4 L3 x2 0 1 0 3 0 0 3
1
L2 ← L2 + 2 L3 x1 1 0 0 − 31 2
3 0 2
e1 0 0 1 − 35 4
3 0 2
1 4
L4 ← L4 + L3 −z 0 0 0 3 3 1 8

La nouvelle solution de base est

( x1 , x2 , e 1 , e 2 , e 3 ) t = (2, 3, 2, 0, 0) t ,

qui correspond à un coût minimum de z = −8, comme les coût réduit de toutes les variables sont
positifs ou nuls, cette solution est optimale et l'algorithme du simplexe s'arrête.

2.4 Conclusion
L'algorithme du simplexe consiste à se déplacer d'un point extrême du polytope K = { x : Ax =
b, x ≥ 0} à un autre point extrême adjacent jusqu'à ce qu'on se rende compte que la solution
réalisable actuelle est optimale ou que le problème n'est pas réalisable ou que le problème n'est pas
borné supérieurement (ou inférieurement dans le cas de minimisation).

3 Méthodes des deux phases

Nous avons vu comment trouver une base de depart lorsque les contraintes du problème sont
toutes de type ≤ : les variables d'écart constituent alors une base de depart naturelle, leurs
colonnes formant a une permutation pres une matrice identité.
En pratique il est frequent que le PL comporte également des contraintes de type ≥ ou de type
=. Dans ce cas, nous n'avons plus de base de depart évidente, il faut en chercher une. Ce sera la
premiere phase de la méthode du simplexe.
La méthode du simplexe consiste donc en deux phases :
Phase I : recherche d'une base de depart par la resolution par l'algorithme du simplexe du pro-
gramme auxiliaire (dénit plus loin) ou mise en evidence que le problème de depart n'admet
aucune solution admissible.
Phase II : application de l'algorithme du simplexe au problème de depart cette fois, en partant de
la base mise en evidence a la n de la phase I
Exemple 3.1 Comment, par exemple trouver une solution de base réalisable initiale au problème
suivant

 max 2 x1 + 3 x2
x



s.t. x1 + x2 ≤ 10,

(P ) :


 5 x1 + 4 x2 ≥ 20


x1 , x2 ≥ 0.
3. MÉTHODES DES DEUX PHASES 31

On transforme ce problème sous la forme canonique Ax ≤ b et ensuite on ajoute les variables

d'écart.


 max 2 x1 + 3 x2
x



s.t. x1 + x2 + e 1 = 10,
(3.3)



 −5 x1 − 4 x2 + e 2 = −20


x1 , x2 , e 1 , e 2 ≥ 0.

Clairement le point (0, 0, 10, −20), n'est pas admissible.

3.1 Recherche d'une base de départ : Phase I

L'objectif est de trouver une solution de base admissible qui servira de point de départ pour
l'algorithme du simplexe. L'idée est de résoudre un problème intermédiaire de minimisation dont la
solution fournira le point de départ de la méthode du simplexe. Ce problème intermédiaire porte le
nom de Phase I du simplexe.

Démarche à suivre :
On commence par écrire le programme auxiliaire (PA) associé au problème de départ (P) :
1. On s'assure que les membres de droite b i sont tous positifs ou nuls, quitte à multiplier la
contrainte correspondante par -1 si son membre de droite est négatif (sinon on aboutirait à
des solutions de base non réalisables),
2. On introduit une variable d'écart e i pour chaque contrainte i de type ≤, aectée d'un signe
+ dans la contrainte ré-écrite, comme on le faisait jusqu'à présent,
3. On introduit aussi une variable d'écart e i pour chaque contrainte i de type ≥, mais aectée
d'un signe - dans la contrainte ré-écrite : l'écart qu'elle mesure est en eet négatif ou nul,
mais la variable d'écart doit rester positive ou nulle,
4. Le problème ne comporte plus que des contraintes d'égalité, mais seules les variables d'écart
associées aux contraintes initiales de type ≤ forment des colonnes de la matrice identité.
Pour chacune des autres contraintes (c'est-à-dire les contraintes initiales ≥ ré-écrites avec une
variable d'écart aectée d'un signe -, et les contraintes initiales =), on introduit une variable
articielle t i positive ou nulle de la même façon qu'on introduisait les variables d'écart.
5. La fonction objectif de (PA) est alors la somme des variables articielles. On cherche à la
minimiser (en fait à l'annuler).
32 CHAPITRE 3. MÉTHODE DU SIMPLEXE
3.2 Illustration de la méthode sur un exemple
Dans l'exemple ci-dessus, il s'agit d'introduire deux variables d'écart e1 et e2 et une variable
articielle t1 et de considérer le problème de minimisation associé
 
 max 2 x1 + 3 x2  max 2 x1 + 3 x2
x x
 
Var. d'écart

 

s.t. x1 + x2 ≤ 10, s.t. x1 + x2 + e 1 = 10,
 
(P ) : =⇒


 5 x1 + 4 x2 ≥ 20 

 5 x1 + 4 x2 − e 2 = 20
 

x1 , x2 ≥ 0. 
x , x , e , e ≥ 0.
 1 2 1 2
 min z t = t 1 (20 − 5 x1 − 4 x2 + e 2 )
Var. articiel


 s.t. x1 + x2 + e 1 = 10,
=⇒ (P A )
+ new obj 

 5 x1 + 4 x2 − e 2 + t 1 = 20
x1 , x2 , e 1 , e 2 , t 1 ≥ 0.


I Phase I
Le problème (PA) admet toujours une solution admissible, il sut de prendre le point ( x1 , x2 , e 1 , e 2 , t1 ) =
(0, 0, 10, 0, 20).

On forme le tableau initial du simplexe pour ce problème.

Variables de base x1 x2 e 1 e 2 t 1 − z t b R
e1 1 1 1 0 0 0 10
t1 5 4 0 −1 1 0 20
−zt 0 0 0 0 1 1 0

Pour que t1 joue le rôle d'une variable de base, il faut faire apparaître un 0 sur la dernière ligne de
la colonne de t1 , pas suite, on transforme le tableau en soustrayant la deuxième ligne de la dernière.
Nous obtenons le tableau suivant :
Variables de base x1 x2 e 1 e 2 t1 − z t b R
10
e1 1 1 1 0 0 0 10 1
t1 5 4 0 −1 1 0 20 20
5 =4 ←
−zt −5 −4 0 1 0 1 −20
↑

Cette solution de base n'étant pas optimale, on poursuit avec la méthode standard du simplexe.
Dans notre cas, on choisit la variable entrante x1 et la variable sortante t1 , on obtient le tableau
suivant
Variables de base x1 x2 e 1 e 2 t1 − z t b R
1 1
e1 0 5 1 5 − 15 0 6
4
x1 1 5 0 − 51 1
5 0 4
−zt 0 0 0 0 1 1 0
On ne peut améliorer ce résultat car la fonction objective z = t 1 = 0.

Nous avons obtenu la solution optimale de la Phase I (4, 0, 6, 0, 0) avec la base { e 1 , x1 }. De plus,
la variable t1 = 0 devient inutile car hors-base. Ainsi, on peut enlever la colonne correspondante à
t1 .

Donc (4, 0, 6, 0, 0) constitue une solution de base initiale du problème (P), ce qui va nous per-
mettre de construire le tableau du simplexe de (P) pour démarrer la phase II.
3. MÉTHODES DES DEUX PHASES 33

I Phase II
Après avoir terminer la phase I avec une solution optimale de valeur optimale nulle et où les
variables articielles sont toutes des variables hors base. Pour commencer la première itération de la
phase II, il faudra remplacer les coecients de la fonction objectif z t par ceux de la fonction objectif
original z, puis recalculer les coûts relatifs.
Variables de base x1 x2 e 1 e 2 z b R
e1 0 15 1 1
5 0 6
x1 1 45 0 − 51 0 4
z 2 3 0 0 −1 0

x1 étant une variable de base nous devons remplacer 2 par 0 dans la dernière ligne du tableau par
l'opération suivante L 3 ← L 3 − 2L 2
Variables de base x1 x2 e1 e2 z b R
1 1
e1 0 5 1 5 0 6 6 × 5 = 30
4
x1 1 5 0 − 15 0 4 4 × 45 = 5 ←
7
z 0 5 0 − 25 −1 −8
↑

La variable x2 entre dans la base et la variable x1 sort de la base.

Variables de base x1 x2 e 1 e 2 z b R
e1 0 15 1 1
5 0 6 6 × 5 = 30
5
x1 4 1 0 − 15 0 4 4 × 45 = 5 ←
z 0 75 0 2
5 −1 −8

On poursuit avec la méthode standard du simplexe

Variables de base x1 x2 e 1 e 2 z b R
e1 − 14 0 1 1
4 0 5 5 × 4 = 20 ←
5
x2 4 1 0 − 14 0 5
z − 75 0 0 3
4 −1 −15
↑

La variable e2 entre dans la base et la variable e1 sort de la base.

Variables de base x1 x2 e 1 e 2 z b R
e2 −1 0 4 1 0 20
x2 1 1 1 0 0 10
z −1 0 −3 0 −1 −30

L'algorithme se termine à cette étape. La solution optimale est (0, 10, 0, 20) avec z = 30. Ceci est
bien conforme au graphique ci-dessous.

3.3 La méthode de "The big M "

L'idée ici est de remplacer le programme (P) par un autre qui a la même solution. Pratiquement
il s'agit de faire deux choses :
34 CHAPITRE 3. MÉTHODE DU SIMPLEXE

Fig. 3.1  Le graphe associé à l'exemple 3.3

• créer la base articiellement en ajoutant les colonnes manquantes de la matrice identité, cela
revient à introduire des variables supplémentaires, appelées "variables articielles",
• modier la fonction objective de sorte que les variables articielles quittent la base au fur et
à mesure des itérations.
Pour le méthode du grand M on pénalise les variables articielles dans la fonction objective avec un
coecient négatif très grand noté − M pour un problème de maximisation ( + M pour un problème
de minimisation). Ainsi, la maximisation de la fonction objective passe nécessairement par forcer les
variables articielles à quitter la base. Si à l'optimum, certaines variables articielles sont dans la
base, avec une valeur non nulle, alors le programme n'à pas de solution réalisable.
Pour l'exemple donné plus haut, le programme associé, noté M, est le suivant.


 max z = 2 x1 + 3 x2 − Mt 1

 s.t. x1 + x2 + e 1 = 10,
(P A )


 5 x1 + 4 x2 − e 2 + t 1 = 20
x1 , x2 , e 1 , e 2 , t 1 ≥ 0.


Le tableau initial du simplexe est :

Variables de base x1 x2 e 1 e 2 t1 z b R
e1 1 1 1 0 0 0 10
t1 5 4 0 −1 1 0 20
z 2 3 0 0 − M −1 0

Pour que t1 joue le rôle d'une variable de base, il faut faire apparaître un 0 sur la dernière ligne de
la colonne de t1 , pas suite, on transforme le tableau en soustrayant M fois la deuxième ligne de la
dernière. Nous obtenons le tableau suivant :
Variables de base x1 x2 e 1 e 2 t1 z b R
10
e1 1 1 1 0 0 0 10 1
t1 5 4 0 −1 1 0 20 20
5 =4 ←
z 2 + 5M 3 + 4M 0 −M 0 −1 20 M
↑

La variable articiel t1 est toujours dans la base, nous devons eectuer une autre itération
Variables de base x1 x2 e 1 e 2 t1 z b R
1 1
e1 0 5 1 5 − 15 0 6
4
x1 1 5 0 − 51 1
5 0 4
7 2
z 0 5 0 5 −2 − 5 M −1 −8
4. PROBLÈMES IRRÉGULIERS 35

la variable articiel t1 est hors base avec un fort coecient négatif et ne peut plus entrer dans la
base. La phase I s'achève en éliminant la colonne de la variable t1 du tableau. Nous retrouvons ainsi
le tableau suivant avec lequel on va démarrer la phase II du simplexe comme on l'a déjà fait dans la
section précédente.

Remarque 3.3 • Il se peut que la phase I se termine avec une solution de base optimale
comportant une ou plusieurs variables articielles.
• Si l'une de ces variables articielles de base prend une valeur négative, alors le problème
initial est non réalisable.
• Si toutes les variables articielles de base ont une valeur nulle, il faut les sortir de la base
pour trouver le tableau initial du simplexe pour le problème (P). Pour cela, on doit remplacer
chacune de ces variables articielles par l'une des variables hors base, qui ne doit pas être
une variable articielle. Puisque la variable de sortie a une valeur nulle, alors la nouvelle
variable de base aura aussi une valeur nulle.

4 Problèmes irréguliers
4.1 Cas de solution non bornée
Graphiquement, ce problème est caractérisé par le fait qu'on peut déplacer la droite de la fonction
objectif indéniment de manière à accroître la valeur, en gardant toujours une intersection non vide
avec l'ensemble des solutions réalisables.
Avec la méthode de simplexe, on reconnaît ce problème lorsque la variable entrante n'admet
aucune limite sur sa valeur d'entrée, c'est à dire que tous les ratios abiij sont négatifs ou nuls.
On considère le problème suivant :

 min z
min −2 x1 − 3 x2 + x3


 
− x1 − x2 − x3 + e 1 = 3

 

 − x1 − x2 − x3 ≤ 3 rajout des variables d'écart

 

 
 x1 − x2 + x3 + e 2 = 4
x1 − x2 + x3 ≤ 4 =⇒
  − x1 + x2 + 2 x3 + e 3 = 1
− x 1 + x2 + 2 x3 ≤ 1

 

− 2 x1 − 3 x2 + x3 − z = 0

 

 
 x1 , x2 , x3 ≥ 0 

x1 , x2 , x3 , e 1 , e 2 , e 3 ≥ 0


Le tableau initial s'écrit

Variables de base x1 x2 x3 e 1 e 2 e 3 − z b R
e1 −1 −1 −1 1 0 0 0 3
e2 1 −1 1 0 1 0 0 4
e3 −1 1 2 0 0 1 0 1 ←
−z −2 −3 1 0 0 3 1 0
↑

Variable sortante : e3.

Variable entrante : x2 .
36 CHAPITRE 3. MÉTHODE DU SIMPLEXE
On pivote autour de de la troisième ligne et on trouve le tableau suivant
Variables de base x1 x2 x3 e 1 e 2 e 3 − z b R
e1 −2 0 1 1 0 0 0 4
e2 0 0 3 0 1 0 0 5
e3 −1 1 2 0 0 1 0 1
−z −5 0 7 0 0 0 1 3
↑

La variable entrante est x1 . Toutefois, le critère du quotient ne s'applique plus car toutes les entrées
(lignes 1 à 3) de la colonne 1 sont négatives ou nulles.

Remarque 3.4 Selon cet exemple, on peut conclure que s'il n'est pas possible de calculer la ligne
de pivot pour un choix de colonne de pivot j, le problème n'admet pas de solution optimale car il
sera toujours non borné.

4.2 Les problèmes impossibles

Graphiquement, on a caractérisé ces problèmes par un ensemble de solutions réalisables vide. Avec
la méthode de simplexe, on reconnaît que le problème est impossible si une ou plusieurs variables
articielles sont présentes dans la base dans le tableau de simplexe optimal, ce qui signie que la
solution donnée par ce tableau n'est pas réellement réalisable.
Vérions à l'aide de la méthode de simplexe, que le problème suivant est réellement impossible :


 max 4 x1 + 3 x2

 x1 + x2 ≤ 2


 3 x1 + x2 ≥ 10
x1 , x2 ≥ 0


En introduisant les variables d'écarts et les variables articielles le programme s'écrit :



 max 4 x1 + 3 x2 − Mt

 x1 + x2 + e 1 = 2


 3 x1 + x2 − e 2 + t = 10
x1 , x2 , e 1 , e 2 , t ≥ 0


La résolution par le simplexe donne les tableaux suivant

Variables de base x1 x2 e 1 e 2 t1 z b R
e1 1 1 1 0 0 0 2
t1 3 1 0 −1 1 0 10
z 4 3 0 0 − M −1 0

Ainsi,
Variables de base x1 x2 e 1 e 2 t1 z b R
e1 1 1 1 0 0 0 2
t1 3 1 0 −1 1 0 10
z 4 + 3M 3 + M 0 − M 0 −1 10 M
4. PROBLÈMES IRRÉGULIERS 37

D'où,
Variables de base x1 x2 e1 e2 t1 z b R
x1 1 1 1 0 0 0 2
t1 0 −2 −3 −1 1 0 10
z 0 −1 − 2 M −4 − 3 M 0 − M −1 4 M − 8
Le tableau de simplexe ci-dessus est optimal avec une variable articielle dans la base.

4.3 Les problèmes à solutions multiples

Nous avons vu dans l'algorithme du simplexe que lorsque les coûts marginaux de toutes les
variables hors base sont ≤ 0, alors la solution actuelle est optimale. Mais s'ils sont tous non nuls
(< 0), alors la solution optimale est unique. Si par contre, l'un de ces coûts des variables hors base
est nul, alors on peut avoir deux ou plusieurs solutions de base optimales. Pour illustrer, reprenons
l'exercice de la section résolution graphique qui admet une innité de solutions optimales.




min −50 x1 − 30 x2
s.t 10 x1 + 6 x2 ≤ 45




4 x1 + 6 x2 ≤ 36

2 x1 + 6 x2 ≤ 27





 x ≥ 0

Variables de base x1 x2 e 1 e 2 e 3 − z b R
e1 10 6 1 0 0 0 45
e2 4 6 0 1 0 0 36
e3 2 6 0 0 1 0 27
−z −50 −30 0 0 0 1 0
La variable x1 entre dans la base pour remplacer la variable e1

Variables de base x1 x2 e1 e2 e3 −z b R
3 1 9
x1 1 5 10 0 0 0 2
18
e2 0 5 − 52 1 0 0 18
24
e3 0 5 − 51 0 1 0 18
−z 0 0 5 0 0 1 225

Nous obtenons une solution de base optimale dont les variables de base sont x1 , e 2 et e 3 . Mais
le coût marginal de la variable hors base x2 est nul. Faisons entrer cette variable dans la base et
appliquons la règle du plus petit rapport pour choisir la variable de sortie qui est dans ce cas e 3 .
Nous obtenons le tableau suivant
Variables de base x1 x2 e 1 e2 e3 −z b R
1
x1 1 0 8 0 − 81 0 9
4
e2 0 0 − 14 1 − 34 0 9
2
1 5 15
x2 0 1 − 24 0 24 0 4
−z 0 0 5 0 0 1 225

Nous obtenons donc une autre solution de base optimale dont les variables de base sont x1 , e 2 et
x2 .
38 CHAPITRE 3. MÉTHODE DU SIMPLEXE
4.4 Les problèmes à solution dégénérée
En appliquons la règle du plus petit rapport pour désigner la variable de sortie, il est possible
que le plus petit rapport soit atteint pour deux contraintes. En eectuant le changement de base,
nous obtenons alors une solution de base avec l'une des composante nulle. Nous disons qu'on a
une dégénérescence. Ceci peut entraîner des dicultés d'execution et d'ecacité de l'algorithme du
simplexe. En eet, nous pouvons faire plusieurs changement de base sans améliorer la valeur de la
fonction objectif. Nous pouvons même retrouver une base déjà rencontrer à une itération précédente.
On dit alors qu'on a un phénomène de cyclage. An d'illustrer ce type de dégénérescence. considérons
l'exemple suivant : 

 min −4 x1 − 3 x3

 s.t x1 − x2 ≤ 2



2 x1 + x3 ≤ 4

x1 + x2 + x3 ≤ 3





 x1 , x2 , x3 ≥ 0
Introduisons les variables d'écart et écrivons le premier tableau du simplexe :
Variables de base x1 x2 x3 e 1 e 2 e 3 − z b R
e1 1 −1 0 1 0 0 0 2
e2 2 0 1 0 1 0 0 4
e3 1 1 1 0 0 1 0 3
−z −4 0 −3 0 0 0 1 0

La variable x1 entre dans la base, mais en appliquons la règle du plus petit rapport, nous constatons
que le minimum des rapports est atteint pour les deux premières contraintes, alors que seulement une
des deux doit quitter la base. Choisissons arbitrairement e 1 comme variable sortante. nous obtenons
alors le tableau suivant :
Variables de base x1 x2 x3 e 1 e 2 e 3 − z b R
x1 1 −1 0 1 0 0 0 2
e2 0 2 1 −2 1 0 0 0
e3 0 2 1 −1 0 1 0 1
−z 0 −4 −3 4 0 0 1 8

cette solution de base n'est pas optimale puisque les coûts marginaux des variables hors base ne
sont pas tous positifs. Cette solution de base est dite dégénérée puisque l'une des variables de base
est nulle ( e 2 = 0). La variable x2 entre dans la base. En appliquons la règle du plus petit rapport,
nous constatons que la variable e 2 quitte la base et nous obtenons le tableau suivant
Variables de base x1 x2 x3 e 1 e 2 e 3 − z b R
1 1
x1 1 0 2 0 2 0 0 2
1 1
x2 0 1 2 −1 2 0 0 0
e3 0 0 0 1 −1 1 0 1
−z 0 0 −1 0 2 0 1 8

Nous constatons que la nouvelle solution de base est non optimale et qu'elle est aussi dégénérée
( x2 = 0). CE changement de base n'a pas modié la valeur de la fonction objectif ( z = −4). A
l'itération suivante de l'algorithme du simplexe, cette variable x2 quitte la base et sera remplacée
4. PROBLÈMES IRRÉGULIERS 39

par la variable x3
Variables de base x1 x2 x3 e 1 e 2 e 3 − z b R
x1 1 −1 0 1 0 0 0 2
x3 0 2 1 −2 1 0 0 0
e3 0 0 0 1 −1 1 0 1
−z 0 2 0 −2 3 0 1 8

Encore une fois, ce changement de base n'a pas modié la valeur de la fonction objectif. En plus la
nouvelle solution de base est aussi non optimale. Nous pouvons donc se poser la question de savoir
si nous allons continuer ainsi sans pouvoir trouver la solution de base optimale. Heureusement ce
phénomène de dégénérescence s'arrête à l'itération suivante
Variables de base x1 x2 x3 e 1 e 2 e 3 − z b R
x1 1 −1 0 0 1 −1 0 1
x3 0 2 1 0 −1 2 0 2
e1 0 0 0 1 −1 1 0 1
−z 0 2 0 0 1 2 1 10

Remarque 3.5 Dans le cas où on a plusieurs variables candidates d'entrer en base et plusieurs
variables candidates de sortir de la base, la règle du plus petit indice, découverte par R. Bland,
peut nous éviter le cyclage inni. Cette règle consiste à choisir systématiquement, comme variable
entrante, parmi les multiples candidats, la variable x qui correspond au plus petit indice e et
comme variable sortante, la variable x qui correspond au plus petit indice s.
e
s
 [ Quatrième Chapitre \
Dualité

1 Motivation et dénitions
Revenons encore une fois au problème de production de l'introduction.

P1 P2 disponibilité
équipement 3 9 81
main d'oeuvre 4 5 55
matière première 2 1 20
bénéce 6 4

Supposons à présent qu'un acheteur se présente pour acheter toutes les ressources b i , 1 ≤ i ≤ m,
de l'entreprise. Il propose à l'entreprise un prix unitaire yi , 1 ≤ i ≤ m, pour chacune des ressources.
L'entreprise acceptera de lui vendre toutes ses ressources uniquement si elle obtient pour chaque
produit P j un prix de vente au moins égal au prot c j qu'elle ferait en vendant ses produits. On
doit donc avoir
3 y1 + 4 y2 + 2 y3 ≥ c 1 = 6
9 y1 + 5 y2 + 1 y3 ≥ c 2 = 4
y1 , y2 , y3 ≥ 0
De son côté, l'acheteur cherche à minimiser le prix total d'achat. On se demande alors quels sont
les prix unitaires yi , 1 ≥ i ≥ m, que l'acheteur doit proposer à l'entreprise en question pour qu'elle
accepte de vendre toutes ses ressources ? Le problème peut donc s'écrire

 min g( y) = 81 y1 + 55 y2 + 20 y3


 y
s.t 3 y1 + 4 y2 + 2 y3 ≥ c 1 = 6 (4.1)



 9 y1 + 5 y2 + 1 y3 ≥ c 2 = 4

y1 , y2 , y3 ≥ 0


Dénition 4.1 Au programme linéaire primal


 maxn

 f ( x) = c t x
x∈R
(PL) : s.t Ax ≤ b


 x≥0

on associe le programme linéaire dual


 min g( y) = b t y
 y∈Rm

(PLD ) : s.t At y ≥ c


y≥0


40
1. MOTIVATION ET DÉFINITIONS 41

Exemple 4.1 Illustration graphique du problème primal et dual :

On considère le problème suivant :

 min f ( x) = − x1 − x2
x∈R2



s.t − x1 − 3 x2 ≤ −3



 −2 x1 − x2 ≤ −2

x1 , x2 ≥ 0


qui admet la solution x ∗

= ( x1 , x2 ) =
¡3 4
5, 5
¢
et f (x ) = − . Le problème dual s'écrit sous la forme :
∗ 7
5


 max g( y) = −3 y1 − 2 y2
2
 y∈R



s.t − y1 − 2 y2 ≥ −1



 −3 y1 − y2 ≥ −1
y1 , y2 ≥ 0


qui admet la solution y ∗

= ( y1 , y2 ) =
¡1 2
5, 5
¢
et g( y ) = − . Dans cet exemple, on observe que la
∗ 7
5

valeur minimale du primal est égale à la valeur maximale du dual.

42 CHAPITRE 4. DUALITÉ
1.1 Comparaison primal/dual
Primal Dual
max( f ) min( g)
coecient c de f second membre c
second membre b coecient b de g
m contraintes inégalités ( ≤) m contraintes de positivité
n contraintes de positivité n contraintes inégalités ( ≥)

Si le problème primal est sous forme standard avec les contraintes à Ax != bà alors !on passe à
A b
la forme canonique pure en écrivant les contraintes Ax = b ⇐⇒ ≤ . De façon
−A −b
générale, on a la dénition suivante lorsque le problème primal est sous forme canonique mixte :
Primal Dual
t
maxn f ( x) = c x min g( y) = b t y
x∈R y∈Rm
n
X
∀i ∈ I1, ai j x j ≤ bi ∀ i ∈ I 1 , yi ≥ 0
j =1
n
de signe quelconque
X
∀i ∈ I2, ai j x j = bi ∀ i ∈ I 2 , yi
j =1
m
X
∀ j ∈ J1 , x j ≥ 0 ∀ j ∈ J1 , a i j yi ≥ c j
i =1
m
de signe quelconque
X
∀ j ∈ J2 , x j ∀ j ∈ J2 , a i j yi = c j
i =1

2 Propriétés - Théorèmes de dualité

Proposition 4.1 Le dual du dual est le primal.

Démonstration A partir de la dénition du dual d'un PL sous forme canonique pure :

− g( y) = (− b) t y

g( y) = b t y

 min  maxm
 y∈Rm
 
 y∈R
s.t At y ≥ c ⇐⇒ s.t − A t y ≤ −c

 

y≥0 y≥0
 

Si on prend le dual du dual, on a donc

 

 minn (− c) t x 
 maxn ct x
 x∈R  x∈R

 s.t (− A t ) t x ≥ (− b) ⇐⇒
 s.t Ax ≤ b
 
 x≥0  x≥0

et on reconnaît le problème primal du départ.

On s'intéresse à présent au lien entre les solutions de programmes linéaires en dualité.
2. PROPRIÉTÉS - THÉORÈMES DE DUALITÉ 43

Théorème 4.1 (Théorème faible de dualité)

Soit x une solution réalisable d'un (PL) sous forme canonique mixte et y une solution réalisable
du problème dual (PLD). Alors :
1. f (x) ≤ g( y).
2. Si f (x) = g( y) alors x et y sont des solutions optimales de (PL) et (PLD) respectivement.
Démonstration Dans le cas où (PL) est sous forme canonique pure :
1. On a d'une part Ax ≤ b, x ≥ 0 et d'autre part A y ≥ c, y ≥ 0. Par conséquent,
t

t t t
Ax ≤ y b = g( y) car y ≥ 0.
f ( x) = c x ≤ ( A y) x = y |{z} t t

≤b

2. Soient x et y des solutions réalisables de (PL) et (PLD) respectivement telles que f (x ) =

∗ ∗ ∗

g( y ). D'après 1., pour toute solution réalisable x de (PL), on a f ( x) ≤ g( y ) = f ( x ) donc x

∗ ∗ ∗ ∗

est une solution réalisable optimale. Idem pour y . ∗

Théorème 4.2 (Théorème fort de dualité)

Si le problème primal (PL) admet une solution réalisable optimale x alors le problème dual (PLD)
∗

admet lui aussi une solution réalisable optimale y et on a ∗

f ( x∗ ) = g( y∗ ).

Démonstration On suppose que (PL) est sous forme standard. Si (PL) admet une solution réali-
sable optimale, alors il admet une solution de base réalisable optimale. On note B la base optimale ∗

et on désigne par x la solution de base réalisable optimale : x = A b. On choisit alors

∗ ∗ −1
B∗
1 t
y∗ = ( A −
B∗ ) c B .
∗

Montrons que y est une solution réalisable optimale pour le dual (PLD). On a
∗

t ∗ t −1 t
AH ∗y = AH ∗ ( A B∗ ) c B∗

1 t
= ( A−
B∗ A H ) c B
∗ ∗

= c H∗ − L H∗
Or, à l'optimum tous les coûts réduits sont négatifs ou nuls ( L ≤0 ) donc A t
y∗ ≥ c H∗ . Par
dénition, on a A y = c et donc on obtient
H∗ H∗
t ∗
B∗ B∗

A t y∗ ≥ c
est de signe quelconque.
y∗
Par conséquent, y est une solution réalisable du dual (PLD). On remarquera que le problème primal
∗

(PL) étant mis sous forme standard, il n'y a pas de contrainte de positivité sur les variables y du
dual. Par ailleurs
f ( x∗ ) = c t x∗ = c B
t −1
∗ A B∗ b

1 t t
= (( A − ∗ ) c B∗ ) b
| B {z }
y∗
= g( y∗ )
44 CHAPITRE 4. DUALITÉ
et donc par le Théorème faible de dualité, y est optimale pour (PLD).
∗

On a vu qu'il y avait 3 cas possibles (et seulement 3) pour le problème primal (PL) :
1. il existe (au moins) une solution optimale.
2. l'ensemble DR des solutions réalisables n'est pas borné et l'optimum est inni.
3. pas de solution réalisable ( DR = ;)
Les mêmes situations se retrouvent pour le problème dual. Plus précisément, le lien entre les
deux problèmes en dualité est donné par le résultat suivant.

Théorème 4.3
Étant donnés un problème primal (PL) et son dual (PLD), une et une seule des trois situations
suivantes peut se produire.
a) les deux problèmes possèdent chacun des solutions optimales (à l'optimum, les coûts sont
égaux).
b) un des problèmes possède une solution réalisable avec un optimum inni, l'autre n'a pas de
solution.
c) aucun des deux problèmes ne possède de solution réalisable.

Il y a donc 3 situations (au lieu de 9) qui peuvent se résumer dans le tableau suivant :

3 Conditions d'optimalité primal-dual (COPD)

On s'intéresse au cas (a) où les problèmes primal et dual possèdent chacun des solutions optimales
(optimum ni). On peut alors calculer l'une à partir de l'autre.

Théorème 4.4
Soient x et y des solutions réalisables respectivement du problème primal (PL) et du problème
dual (PLD). Alors x et y sont des solutions réalisables optimales si et seulement si les conditions
d'optimalité primal-dual (COPD) suivantes sont vériées :
 Si une contrainte est satisfaite en tant qu'inégalité stricte dans (PL) (resp. dans (PLD))
alors la variable correspondante de (PLD) (resp. de (PL)) est nulle.
 Si la valeur d'une variable dans (PL) ou (PLD) est strictement positive alors la contrainte
correspondante de l'autre programme est une égalité.
3. CONDITIONS D'OPTIMALITÉ PRIMAL-DUAL (COPD) 45

Supposons que le problème primal s'écrive sous forme canonique mixte. Alors x et y sont op-
timales respectivement pour le problème primal et le problème dual si et seulement si on a les
COPD :  n
a i j x j = b i ou yi = 0
X
∀ i ∈ I ,

1



j =1
m
ou x j = 0
 X
 ∀ j ∈ J1 , a i j yi = c j


i =1

Démonstration (Démonstration de la condition nécessaire du Théorème 3.)

Supposons pour simplier que le problème primal (PL) soit mis sous forme canonique pure. Soient x
et y des solutions réalisables optimales de (PL) et (PLD) respectivement. On a donc Ax ≤ b, x ≥ 0
et A y ≥ c, y ≥ 0. En introduisant les variables d'écart e et ² respectivement pour (PL) et (PLD),
t

on a
et
t
Ax + e = b A y−² = c
x, e ≥ 0 x, ² ≥ 0
Dans ces conditions,
f ( x) = c t x = ( A t y − ²) t x = y t Ax − ² t x
g( y) = b t y = ( Ax + e) t y = ( Ax) t y + e t y = y t Ax + e t y.

Or d'après le Théorème de la dualité forte, f (x) = g( y) donc on obtient

² t x + e t y = 0. (4.2)
Puisque x ≥ 0 et y ≥ 0, on a nécessairement
(
² i x i = 0, ∀ i
e j y j = 0, ∀ j

ce qui donne les COPD (encore appelées "relations d'exclusion") :

(
Si ² 6= 0 alors x = 0 , ( Si e 6= 0 alors y = 0
Si x 6= 0 alors ² = 0 Si y 6= 0 alors e = 0
i i j j
i i j j

La réciproque (condition susante) se démontre à partir du Théorème faible de dualité.

3.1 Utilisation pratique des COPD
La dualité et les COPD permettent souvent de vérier si une solution réalisable d'un (PL) est
optimale ou non, à partir de la connaissance d'une solution optimale du problème dual. Lorsque (PL)
et (PLD) ont des solutions réalisables optimales x∗ et y∗ respectivement, on a :
n
a i j x∗j < b i =⇒ yi∗ = 0
X
j =1
m
a i j yi∗ > c j =⇒ x∗j = 0
X
i =1

et n
a i j x∗j = b i
X
yi∗ > 0 =⇒
j =1
m
a i j yi∗ = c j
X
x∗j > 0 =⇒
i =1
46 CHAPITRE 4. DUALITÉ
Exemple 4.2 Le problème dual du problème de production s'écrit

 min g( y) = 81 y1 + 55 y2 + 20 y3


 y
s.t 3 y1 + 4 y2 + 2 y3 ≥ c 1 = 6 (4.3)



 9 y1 + 5 y2 + 1 y3 ≥ c 2 = 4

y1 , y2 , y3 ≥ 0


Le problème primal (PL) admet la solution optimale :

27 COPD
e∗1 = >0 =⇒ y1∗ = 0
2
15 COPD
x1∗ = >0 =⇒ 3 y1∗ + 4 y2∗ + 2 y3∗ = 6 (²∗1 = 0)
2
COPD
x2∗ = 5 > 0 =⇒ 9 y1∗ + 5 y2∗ + y3∗ = 4 (²∗2 = 0)
e∗2 = e∗3 = 0

En résolvant le système pour y , on obtient la solution optimale du problème dual :

∗

1 7
y1∗ = 0, y2∗ = , y3∗ = .
3 3

3.2 Calcul de la solution du problème dual à partir du tableau du

simplexe du problème primal
Dans cette section, nous allons voir comment nous pouvons calculer la solution du problème dual
à l'aide du tableau nal du simplexe appliqué au problème primal.
On considère le problème de production


 max [ f ( x1 , x2 ) = 6 x1 + 4 x2 ]


 (x1 ,x2 )
s.t. 3 x1 + 9 x2 ≤ 81



 4 x1 + 5 x2 ≤ 55




 2 x1 + x2 ≤ 20

 x1 , x2 ≥ 0

le tableau nal du simplexe est :

Variables de base x1 x2 e 1 e 2 e3 z b R
e1 0 0 1 − 15 6
7
2 0 27
2
1
x2 0 1 0 3 − 32 0 5
x1 1 0 0 − 16 5
6 0 15
2
z 0 0 0 − 13 − 37 −1 −65

La solution optimale est donc

¶t
15 27
µ
t
( x1 , x2 , e 1 , e 2 , e 3 ) = , 5, , 0, 0 ,
2 2

qui correspond à un bénéce maximum de z = 65.

3. CONDITIONS D'OPTIMALITÉ PRIMAL-DUAL (COPD) 47

Calculons la solution du problème dual. Le dual s'écrit


 min g( y) = 81 y1 + 55 y2 + 20 y3


 y
s.t 3 y1 + 4 y2 + 2 y3 ≥ 6 (4.4)



 9 y1 + 5 y2 + 1 y3 ≥ 4

y1 , y2 , y3 ≥ 0


On applique la méthode du simplexe au problème dual, après la Phase I et la Phase II on obtient

le tableau est

Variables de base y1 y2 y3 ²1 ²2 −z b R
y3 − 27 0 1 − 56 2
3 0 7
3
5 1
y2 2 1 0 6 − 13 0 1
3
27
−z 2 0 0 152 5 1 −65

La solution optimale est ¶t

1 7
µ
t
( y1 , y2 , y3 , ²1 , ²2 ) = 0, , , 0, 0 ,
3 3

On observe que la solution y se trouve à la dernière ligne du tableau nal du simplexe du problème
primal. En eet, les coecients c i de la dernière ligne du tableau correspondent à
(
y j = − c n+ j , j = 1, ..., m
² i = − c i , i = 1, .., n

en applique sur le tableau primal et on obtient

1 7
c 3 = y1 = 0; c 4 = y2 = ; c 5 = y3 = ; c 1 = ²1 = 0; c 2 = ²2 = 0.
3 3

En parfaite dualité, on a les mêmes relations par rapport au tableau du problème dual. On obtient
que les coecients ci de la dernière du tableau du dual correspondent à
(
x i = c m+ i , i = 1, ..., n
e j = c j , j = 1, .., m

en applique sur le tableau dual et on obtient

15 27
c 4 = x1 = ; c 5 = x2 = 5; c 1 = e 1 = ; c 2 = e 2 = 0; c 3 = e 3 = 0.
2 2