Chapitre 7

Dualité en programmation linéaire

Introduction

Dans ce chapitre nous allons voir comment nous pouvons, à partir d'un programme linéaire
donné (qui sera appelé programme primal), construire un autre programme linéaire appelé
programme dual. Entre ces deux programmes il y a des liens très étroits : si un des deux a une
solution optimale l'autre en possède également une et les valeurs optimales des deux
programmes coïncident. Il arrive que la résolution du problème dual peut être plus simple que
celle du problème primal (par exemple on connaît une solution de base admissible pour le
dual et on peut démarrer directement le simplexe, tandis que pour le primal on est obligé
d'utiliser la méthode des deux phases).

En plus de l'intérêt mathématique ou numérique pour l'étude du problème dual, un aspect

autre très important est l'interprétation économique des variables duales. Ces variables
représentent des coûts marginaux et peuvent être considérées comme l'augmentation
maximale du revenu, par rapport à la solution optimale, qui résulterait de l'utilisation d'une
unité supplémentaire de l'un des biens.
Etant donné le PL suivant écrit sous forme canonique,

on peut considérer qu’il concerne une entreprise E1 fabricant n biens j, j {1, . . . , n} et

faisant intervenir m ressources i, i {1, . . . , m}. Le problème que peut se poser l’entreprise
est le suivant : Etant donnée la disponibilité bi pour chaque ressource i et le profit unitaire cj
pour chacun des biens j, quel doit être le niveau de production de chaque bien j pour que la
quantité de bien i consommée reste inférieure à la disponibilité bi et que le profit total soit
maximal?
Supposons qu’une autre entreprise E2, en rupture de stock, désire racheter les ressources de la
première, le problème qu’elle va se poser et le suivant : Etant donné un prix unitaire cj pour
chacun des n biens j et une disponibilité bi pour chacune des m ressources i, quel doit être le
prix unitaire minimum d’achat yi de chaque ressource i pour que la valeur totale des
ressources consommées par chaque bien j soit supérieure ou égale à cj (pour que cela rester
intéressant pour l’entreprise E1 et que le prix total d’achat des ressources disponible soit
minimum?

1
Ce deuxième problème constitue le problème dual du premier, il peut se mettre sous la forme :

On voit aisément que les contraintes, impliquent que le prix

d’achat des ressources par l’entreprise E2 reste supérieur au profit que peut en tirer
l’entreprise E1, c’est à dire,

ce qui est conforme aux lois de l’économie, on voit donc intuitivement que le minimum
atteint par le deuxième problème doit être égal au maximum du premier problème. La théorie
montre que c’est le cas quand le problème a des solutions.

La construction du programme dual

Considérons un programme linéaire sous la forme canonique appelée programme primal :

Primal

Le programme dual a m variables notées ¸y1,…., ym qui sont rangées sous la forme d'un
vecteur ligne . A noter la différence par rapport aux variables primales qui sont données sous
la forme d’un vecteur colonne . Alors le programme dual s’écrit sous la forme matricielle :

Ou encore,
Dual

2
Remarque : À toute variable d’écart primale (resp. duale) positive correspond une variable
structurelle duale (resp. primale) nulle. À toute variable structurelle primale (resp. duale)
positive correspond une variable d’écart duale (resp. primale) nulle. On note, xj (resp. yi) les
variables structurelles du primal (resp. dual) et ti (resp. uj) les variables d’écart du primal
(resp. dual). Le tableau suivant résume les correspondances entre les deux problèmes primal
et dual:

Problème primal Problème dual

Maximisation minimisation
Matrice des contraintes (m,n) transposée de la mat des contraintes (n,m)
n variables (vecteur colonne) n contraintes
m contraintes m variables (vecteur ligne)
variable nº j ≥ 0 contrainte nº j ≥
contrainte nº i ≤ variable nº i ≥ 0
contrainte nº i = variable nº i de signe qcq
variable nº j de signe qcq contrainte nº j =
(ligne de) coefficients fonction objectif second membre
second membre (colonne de) coefficients fonction objectif

Nous remarquons facilement que la matrice des contraintes du problème dual est la transposée
de celle du problème primal. Enfin, pouvons constater facilement que le dual du problème
dual c'est le problème primal.

Exemple
Primal Dual

Remarque : Le tableau précédent nous permet d’obtenir le dual d’un PL quelque soit sa
forme, néanmoins, il est préférable de mettre le PL primal sous forme canonique avant de
déterminer son dual. La forme canonique ici est un abus de langage puisque les ne sont pas
tous positifs. Il s’agit d’avoir en plus des contraintes de positivité (variables toutes positives),
toutes les contraintes sont de type pour un problème de minimisation et un
problème de maximisation.

Exemple : Soit le PL suivant

Nous l’écrivons d’abord sous cette forme pour obtenir son dual facilement.
3
 Primal Dual

Propriétés de la dualité

Théorème 1 : Soient x une solution admissible du primal et y une solution admissible du

dual. Alors on a . Autrement dit chaque valeur admissible du dual est
un majorant pour chaque valeur admissible du primal.

Démonstration. Soit une solution réalisable de P, alors on a et soit y

vérifiant : On a . □

Nous pouvons donc facilement déduire le résultat suivant

Théorème faible de la dualité : Soient et deux solutions amissibles respectivement du

primal et du dual. Si c = b, alors est une solution optimale de (P) et une solution
optimale de (D).

Démonstration. Soit une solution réalisable de P, alors on a d’après le théorème précédent

puisque est une solution réalisable de D. Donc est une solution
optimale de P. On montre de la même manière que st une solution optimale de D. □

A noter que la réciproque n'est pas aussi évidente à montrer, à savoir que si et sont
deux solutions optimales respectivement du primal et du dual, alors les valeurs optimales
coïncident. C'est l'objet du théorème suivant qui est un résultat central de la dualité en
programmation linéaire.

Théorème fort de la dualité: Si le problème primal (P) a une solution optimale , alors le
problème dual (D) a une solution optimale et les valeurs optimales coïncident, c = b.
Autrement dit z* = w*.

Démonstration :
Soient une solution optimale de P et B la base optimale correspondante.
Posons Rappelons que est le vecteur des multiplicateurs du simplexe
correspondant. On a les coûts réduits à l’optimum = et
pour Par suite . D’où est une solution réalisable du dual.
D’autre part on a , . D’après le théorème faible de la dualité, est une
solution optimale de D. □

4
Le théorème précédent donne le lien entre le primal (P) et le dual (D) dans le cas où P admet
une solution optimale finie. Cependant, il ne donne pas le résultat dans les autres cas. Le
théorème suivant englobe tous les cas possibles.

Théorème 2 : Soient P un problème linéaire primal et D son dual. Un seul cas parmi les trois
cas suivants est possible :
1. Les deux Problèmes P et D ont chacun une solution optimale finie et la valeur de
leur fonction objectif à l’optimum sont égales.
2. Si P est non borné, alors son dual D est contradictoire.
3. Si P n’a pas de solution, alors D est soit non borné ou contradictoire.
Démonstration :
1. Ceci est vrai d’après le théorème fort de la dualité.

2. Procédons par l’absurde. Supposons que P est non borné, alors il existe toujours une
solution telle que pour aussi grand que l’on veut. Supposons maintenant
que D est non contradictoire, alors il possède une solution réalisable y. D’après le
théorème 1 on a, . Ce qui est une contradiction.

3. Supposons que P n’a pas de solution, alors il n’a pas de solution optimale finie. Par
suite d’après le théorème fort de la dualité D ne possède pas de solution optimale finie.
Il est donc soit contradictoire ou non borné. □

Remarque: Nous pouvons montrer le point 2 du théorème précédent en utilisant les tableaux
du simplexe. En effet, si le primal que nous supposerons un problème de maximisation est
non borné, alors il existe une colonne dans le tableau du simplexe
correspondant à ce PL (à une itération donnée) dont tous les coefficients sont négatifs et
les coûts réduits correspondant sont positifs. Ceci correspond à une contrainte (ligne) du
dual dont tous les coefficients sont négatifs, avec un second membre positif. Ce qui est
contradictoire bien sur.

Théorème des écarts complémentaires :

Soient et deux solutions respectivement du primal et du dual. et sont optimales si et
seulement si

Démonstration :
Supposons que et sont deux solutions optimales de P et D respectivement.
Alors on a, , ou encore
Comme et la nullité du produit scalaire précédent implique
.
Inversement, si alors on et d’après le théorème faible de la
dualité, et sont deux solutions respectivement du primal et du dual. □

Exemple : Soient le PL (P) et son dual D suivant:

5
(P) (D)

Montrons que les solutions et sont deux solutions

optimales de P et D respectivement. Les deux problèmes sont d’abord sont mis sous leur
formes standard. Nous vérifions facilement que et sont deux solutions réalisables de P et
D respectivement.
D’autre part on a,

=[ ]

Par suite, d’après le théorème des écarts complémentaires, et

sont deux solutions optimales de P et D respectivement.

Passage du dernier tableau simplexe du primal au dernier tableau simplexe du dual :

Nous pouvons déduire le tableau optimal du simplexe du problème dual à partir de celui du
primal en utilisant les correspondances suivantes au signe près:

Variable de base xj (resp. [Link] tj) variable hors base uj (resp. de base yj)
ligne xj (resp. ti) en base colonne uj ([Link]) hors base.
colonne xj (resp. ti) hors base ligne uj ([Link]) en base.
ligne cj − zj (primal) colonne zi − bi.
Exemple

x1 x2 t1 t2 t3 B
1 0 3/5 -1/5 0 6
0 1 2/5 1/5 0 8
0 0 -4/5 3/5 1 8
Z 0 0 -9/5 -2/5 0 30

En utilisant les correspondances ci-dessus, nous déduisons que et sont les variables de
base et , sont les variables hors base pour le problème dual. On obtient donc le
dernier tableau du simplexe du problème dual suivant:

y1 y2 y3 u1 u2 B
1 0 4/5 -3/5 -2/5 9/5

0 1 -3/5 1/5 -1/5 2/5

Z 0 0 -8 -6 -8 30

6
Algorithme dual du simplexe

L’algorithme dual du simplexe consiste à appliquer l’algorithme primal du simplexe au

programme dual (le tableau dual est le transposé du tableau primal). Les opérations de
changement de base étant effectuées sur le tableau primal. Son principe est le suivant :
Soit B une base de (P) dual réalisable (ie : la solution de base correspondante u= cB du
dual vérifie u cH ) si B est également primal réalisable (ie xB = alors d’après
le théorème de la dualité u est la solution optimale du dual et x =[xB , xH] = [ est la
solution optimale du primal. Sinon le vecteur x n’est pas une solution du primal (ie xB =
0). La régle de changement de base de l’algorithme dual est donné par :

i. Si ≥0 terminé, la solution u= cB est la solution optimale du dual et

[ , ]= est la solution du primal.

ii. S’il existe r tel que r< 0 , deux cas peuvent se présenter :
1er cas :

S’il existe un coefficient (arj) < 0 dans la ligne r de (comme les variables sont non
contraintes en signe, le pivot appartient necessairement à l’une des n-m dernières contraintes
du tableau dual), alors on calcule :
=
Dans le tableau dual, la variable rentre en base, sort de la base. Dans le primal, la
variable rentre en base et sort de la base.

2ème cas :

Tous les coefficients de la ligne r de sont positifs (arj > 0 , alors le problème dual n’est
pas borné et par suite, le primal n’a pas de solution.

Remarques:

1) L’application de cet algorithme suppose que l’on connaisse une base duale réalisable de
départ ; C’est souvent le cas en particulier :

a/ Lorsqu’on a calculé une solution optimale du PL (P) pour un second membre donné
b et on cherche la nouvelle solution optimale pour des seconds membres peu
différents de b. Les mutiplicateurs du simplexe à l’optimum du premier problème (P)
constituent une solution de base duale réalisable pour le second problème.
b/ Lorsqu’une solution optimale de (P) a été déterminée, mais que l’on désire obtenir
la nouvelle solution optimale après avoir ajouté à (P) des contraintes supplémentaires.
C’est le cas par exemple dans la programmation linéaire en nombres entiers)
2) L’algorithme dual converge après un nombre fini d’itérations sous l’hypothèse de
dégénérescence (ie ) à chaque itération. En cas de
dégenérescence, la convergence en un nombre fini d’itérations peut encore être assurée
grace à l’emploie des mêmes méthodes que celles utilisées dans l’algorithme primal
(sélection du pivot).

Exemple

7
Considérons le PL (P) suivant dont le tableau optimal est donné ci-dessus:

Forme standard

1 0 1/4 1/4 15/4

0 1 -3/16 1/16 15/16
- 0 0 -5/16 -9/16 -135/16

La solution optimale est donnée par = avec =

Considérons maintenant le nouveau PL ( consititué par le problème initial auquel on a

ajouté une nouvelle contrainte « ». Quel est alors la solution optimale de (
On a 1=3 ou encore 1 1 .
En remplaçant par 1 dans la première équation du tableau précédent, on obtient :
1 ………(*)
Le premier tableau de ( est obtenu en remplacant la première ligne du tableau optimal de
(P) par l’équation précédente (*). On obtient le tableau suivant :

1
1 1 0 -1/4 -1/4 -3/4
0 1 -3/16 1/16 15/16
- 0 0 -5/16 -9/16 -135/16

D’après ce dernier tableau, on n’a pas une solution de départ primal réalisable. Cependant, on
a une solution dual réalisable On applique donc l’algorithme dual du
simplexe à ce nouveaux problème. Le choix de la variable qui entre et celle qui sort de la base
est donné par :
1 sort de la base puisque 1 et entre en base puisque
En appliquant une itération de l’algorithme Dual du Simplexe, on obtient le tableau optimal
suivant :

1
-4 0 1 1 3
-3/4 1 0 1/4 3/2
- -5//4 0 0 -1/4 -15/2

La solution optimale est donnée par = avec = .

NB : 1=0 alors = 1 = 3.

Exercices :

Exercice 1

8
Considérons le problème linéaire suivant :

Ecrire le problème dual et le résoudre graphiquement. En déduire la solution optimale du

problème primal.
Exercice 2

Considérons le problème linéaire suivant :

(p)

1/ Le PL précédent est il écrit sous forme canonique par rapport à une base réalisable ?
Justifier votre réponse. Sinon écrivez (P) sous forme canonique par rapport à une base
réalisable.
2/Formuler le problème dual D de P
3/La base optimale de (P) est et son inverse est
Calculer sans utiliser le simplexe la solution optimale de (P), celle de D ainsi que les valeurs
optimales des fonctions objectifs de P et D.

Exercice 2

Soit le problème linéaire P suivant :

(P)

1/ Donner le problème dual D du PL P

2/ Résoudre D avec la méthode du simplexe.
3/ Déduire le tableau optimal de P à partir du tableau optimal de D (expliquer les
correspondances)

Exercice 3

Soit le problème linéaire P suivant :

(P)

1/ Peut-on résoudre directement P avec la méthode du simplexe. Justifier votre réponse.

9
2/ Résoudre directementP avec une méthode appropriée. Justifier votre choix de la méthode.
3/ Donner le problème dual D du PL P, puis déduire une solution de base réalisable de D.
4/ Résoudre D avec la méthode du simplexe.
5/ Déduire le tableau optimal de P à partir du tableau optimal de D.

Exercice 4
Considérons le problème linéaire suivant :

(p)

1/ La solution définie par est elle une solution réalisable de (P) ? une
solution de base réalisable de (P) ? une solution optimale de (P) ? Justifier votre
réponse.
2/ Faire une résolution graphique de (P).
3/ Résoudre (P) avec une méthode appropriée.
4/ Formuler le problème duale D de P.
5/ Résoudre D avec la méthode du simplexe.
6/ Déduire le tableau optimale de P à partir de celui de D

Références Bibliographiques

[1] R. Diestel, Graph theory, Graduate Texts in Mathematics Series, vol. 173, Springer-
Verlag, New York 1997, 2000,
[2] F. Droesbeke, M. Hallin et C. Lefevre, Les graphes par l'exemple, ISBN 2-7298-8730-X,
Ellipses, 1987.
[3] N. Deo, Graph theory with applications to engineering and computer science, Prentice-
Hall, Englewood cli_s (N.J.),1975.
[4] Jean-Claude Moisdon, Michel Nakhla, Recherche opérationnelle, Méthodes d'optimisation
en gestion, Editeur(s) : Presses des Mines - Transvalor, 2010.
Collection : Economie et gestion
[5] M. Gondran et M. Minoux,Graphes et algorithmes, 2ème ed., Collection de la Direction
des Etudes et Recherches d'Electricit_e de France, Eyrolles 1985.
[6] M. Minoux et G. Bartnik, Graphes, algorithmes, logiciels, Dunod Informatique, ISBN 2-
04-016470-7, Bordas Paris, 1986.
[7] Roseaux, Exercices et problèmes résolus de recherche opérationnelle. Tome 1.
Graphes :leurs usages, leurs algorithmes, ISBN 2-10-003935-0, Dunod, Paris, 1998.
[8] Pierre Borne, Abdelkader El Kamel, Khaled Mellouli, Programmation linéaire et
applications, Eléments de cours et exercices résolus, Editeur(s) : Technip, 2004.
[9] Rémi Ruppli, Programmation linéaire, Idées et méthodes, Editeur(s) : Ellipses ; 2005

10
11