Dualité en programmation linéaire

Pr S. HARROUDI

Ecole Nationale de Commerce et de Gestion de Casablanca

8 novembre 2023

Pr S. HARROUDI 8 novembre 2023 1 / 18

Dualité en programmation linéaire Relation primal/dual Relation primal/dual

Plan

1 Dualité en programmation linéaire

Pr S. HARROUDI 8 novembre 2023 2 / 18

Dualité en programmation linéaire Relation primal/dual Relation primal/dual

Plan

1 Dualité en programmation linéaire

2 Relation primal/dual : Théorèmes de la dualité faible et forte

Pr S. HARROUDI 8 novembre 2023 2 / 18

Dualité en programmation linéaire Relation primal/dual Relation primal/dual

Plan

1 Dualité en programmation linéaire

2 Relation primal/dual : Théorèmes de la dualité faible et forte

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

Pr S. HARROUDI 8 novembre 2023 2 / 18

Dualité en programmation linéaire Relation primal/dual Relation primal/dual

Utilité de la dualité en programmation linéaire

La dualité est une notion essentielle en programmation linéaire. A chaque

programme linéaire initial dit primal (P), on associe un autre programme
linéaire dit dual (D). La dualité présente un double intérêt :
D'une part, le programme dual à une interprétation économique
importante : il constitue une autre vision du programme initiale primal.
En particulier, la dualité permet de montrer qu'un problème
d'allocation optimale des ressources rares est aussi un problème de
tarication optimale de ces ressources.
Pour le mathématicien, les propriétés liant le programme primal et son
dual permettront de résoudre des problèmes de minimisation en termes
de maximisation, ce qui est souvant plus facile, et de développer des
alogorithmes de résolution rapides.
Les relations entre le primal et le dual se sont révélées extrêmement utiles
pour plusieurs applications particulièrement dans l'analyse de sensibilité.

Pr S. HARROUDI 8 novembre 2023 3 / 18

Dualité en programmation linéaire Relation primal/dual Relation primal/dual

Construction d'un modèle dual

Illustration de la notion
Une usine de fabrication de meubles produit deux types de bureaux M1 et M2 . La
fabrication de chaque type de produit nécessite l'intervention des ateliers menuiserie,
assemblage et vernissage. La disponibilité en heure de chaque ressource est donnée dans le
tableau suivant :
M1 M2 Temps libre
Menuiserie 1 2 20
Assemblage 2 1 22
Vernissage 1 1 12
Prot (DH) 300 200

On désire maximiser le revenu. On dénit :

x1 : Le nombre de bureaux de type M1 .
x2 : Le nombre de bureaux de type M2 .

Pr S. HARROUDI 8 novembre 2023 4 / 18

Dualité en programmation linéaire Relation primal/dual Relation primal/dual

Construction d'un modèle dual

Problème primal (P)

max z = 300x1 + 200x2


(ressources menuiserie)

x + 2x2 ≤ 20

 1



(P ) : 2x 1 + x 2 ≤ 22 (ressources assemblage)
≤ (ressources vernissage)

 x
 1

 + x 2 12

 x ≥ 0, x ≥ 0
1 2

Pr S. HARROUDI 8 novembre 2023 5 / 18

Dualité en programmation linéaire Relation primal/dual Relation primal/dual

Construction d'un modèle dual

Supposons qu'un client désire acheter la totalité des ressources disponibles. Il veut
certainement que le prix total de ces ressources soit minimal.
Le directeur de l'usine acceptera cette proposition si le prix oert par le client lui apporte
le même prot provonant de la vente des bureaux.
Pour cele, on associe un prix unitaire à chaque ressource : La disponibilité des ressources
y1 : Le prix d'une heure de menuiserie, 20 heures de menuiserie,
y2 : Le prix d'une heure d'assemblage, 22 heures d'assemblage,
y3 : Le prix d'une heure de vernissage. 12 heures de vernissage.
Le client cherche à minimiser les frais d'achat des ressources, c'est à dire :

min w = 20y1 + 22y2 + 12y3

Pr S. HARROUDI 8 novembre 2023 6 / 18

Dualité en programmation linéaire Relation primal/dual Relation primal/dual

Construction d'un modèle dual

M1 M2 Temps libre
Menuiserie 1 2 20
Assemblage 2 1 22
Vernissage 1 1 12
Prot (DH) 300 200

La production de chaque bureau M1 D'une manière similaire, la production de

nécessite 1h de menuiserie, 2h d'assemblage chaque bureau M2 nécessite 2h de
et 1h de vernissage. Donc le revenu menuiserie, 1h d'assemblage et 1h de
engendré par la vente de ces ressources est vernissage. Alors le revenu engendré par la
y1 + 2y2 + y3 et on sait que le prot vente de ces ressources est 2y1 + y2 + y3 et
engendré par la production et la vente d'un on sait que le prot engendré par la
bureau M1 est 300dh, càd, le client doit production et la vente d'un bureau M2 est
payer susamment pour convaincre le 200dh.
directeur de l'usine de vendre ses ressources. D'où la contrainte imposée par le primal sur
D'où la contrainte imposée par le primal sur le dual est dénie par : 2y1 + y2 + y3 ≥ 200.
le dual est dénie par : y1 + 2y2 + y3 ≥ 300.

Pr S. HARROUDI 8 novembre 2023 7 / 18

Dualité en programmation linéaire Relation primal/dual Relation primal/dual

Construction d'un modèle dual

PL primal (P) PL dual (D)

max z = 300x1 + 200x2 min w = 20y1 + 22y2 + 12y3
s.c s.c
x1 + 2x2 ≤ 20



 2x1 + x2 ≤ 22

 
y1 + 2y2 + y3 ≥ 300
(P ) :


x1 + x2 ≤ 12



 (D) : 2y1 + y2 + y3 ≥ 200
 x ≥ 0, x ≥ 0
 
1 2  y1 ≥ 0, y2 ≥ 0, y3 ≥ 0


(yi désigne la valeur (prix) d'une unité de

la ressource i).

Pr S. HARROUDI 8 novembre 2023 8 / 18

Dualité en programmation linéaire Relation primal/dual Relation primal/dual

Dualité : Caractéristiques

La dualité se caractérise par les règles suivantes :

Le sens de l'optimisation est inversé. La maximisation (resp.
minimisation) dans le primal devient une minimisation (resp.
maximisation) dans le dual.
Les coecients de la fonction économique du primal deviennent les
seconds membres des contraintes dans le dual ; les seconds membres des
contraintes primales deviennent les coecients de la fonction
économique du dual.
Les signes dans les inégalités des contraintes ou dans la contrainte de
positivité des variables de décision suivent des règles précises de
transformations.

Théorème
Le problème dual du problème dual est le problème primal.

Pr S. HARROUDI 8 novembre 2023 9 / 18

Dualité en programmation linéaire Relation primal/dual Relation primal/dual

Règle de construction

Règle de construction
Maximisation Minimisation
Nombre de contraintes ⇐⇒ Nombre de variables
Nombre de variables ⇐⇒ Nombre de contraintes
Type de contraintes Type de variables principales
= ⇐⇒ quelconque
≤ ⇐⇒ ≥0
≥ ⇐⇒ ≤0
Type de variables de décision Type de contraintes
quelconque ⇐⇒ =
≥0 ⇐⇒ ≥
≤0 ⇐⇒ ≤

Pr S. HARROUDI 8 novembre 2023 10 / 18

Dualité en programmation linéaire Relation primal/dual Relation primal/dual

Règle de construction

Exemples :

Primal



 max z = x1 + 3x2

 x1 + x2 ≤ 14



(P1 ) : −2x1 + 3x2 ≤ 7
2x1 − x2 ≤ 5





 x ≥ 0, x ≥ 0

1 2



 min z = 60x1 + 90x2

 20x1 + 5x2 ≥ 25



(P2 ) : 30x1 + 20x2 ≥ 60
5x1 + 10x2 ≥ 15



PrS. HARROUDI 8 novembre 2023 11 / 18


Dualité en programmation linéaire Relation primal/dual Relation primal/dual

Règle de construction

Exemples :

Primal Dual

 

 max z = x1 + 3x2 
 min w = 14y1 + 7y2 + 5y3
 
 x1 + x2 ≤ 14

  y1 − 2y2 + 2y3 ≥ 1

(D1 ) :

(P1 ) : −2x1 + 3x2 ≤ 7 


y1 + 3y2 − y3 ≥ 3
2x1 − x2 ≤ 5

  y1 ≥ 0, y2 ≥ 0, y3 ≥ 0




 x ≥ 0, x ≥ 0

1 2


 max w = 25y1 + 60y2 + 15y3


min z = 60x1 + 90x2  20y1 + 30y2 + 5y3 ≤ 60

(D2 ) :


5y1 + 20y2 + 10y3 ≤ 90

 20x1 + 5x2 ≥ 25

 
 

(P2 ) : 30x1 + 20x2 ≥ 60  y1 ≥ 0, y2 ≥ 0, y3 ≥ 0


5x1 + 10x2 ≥ 15



PrS. HARROUDI 8 novembre 2023 11 / 18


Dualité en programmation linéaire Relation primal/dual Relation primal/dual

Théorèmes de la dualité faible et forte

Théorème : Dualité faible

Considérons la paire primale-duale :

Primal Dual
max cT x min bT y
s.c. A x = b s.c. AT y ≥ c
x≥0
Si x est une solution admissible du primal et y une solution admissible
du dual, alors
z = c T x ≤ w = bT y

Interprétation de la dualité faible :

z ≤ w : prot ≤ valeur des ressources.

Pr S. HARROUDI 8 novembre 2023 12 / 18

Dualité en programmation linéaire Relation primal/dual Relation primal/dual

Théorèmes de la dualité faible et forte

Théorème : Dualité forte

Considérons la paire primale-duale :

Primal Dual
max cT x min bT y
s.c. A x = b s.c. AT y ≥ c
x≥0
Si le primal et le dual admettent tous les deux une solution admissible, ils ont tous
les deux une solution optimale nie et la même valeur objectif optimale z = w.
Si le primal (dual) est non borné, le dual (primal) n'admet pas de solution admissible.
Interprétation de la dualité forte :
Le prot maximal est atteint si les ressources ont été exploitées complétement, i.e. jusqu'à
épuisement de leur valeur, z = w.

Pr S. HARROUDI 8 novembre 2023 13 / 18

Dualité en programmation linéaire Relation primal/dual Relation primal/dual

Théorèmes des écarts complémentaires

Le programme primal et dual étant liés, il est possible de déduire une solution
du programme réciproque à l'aide des écarts complémantaires.
Problématique : Comment trouver une solution d'un problème à partir de
la solution de l'autre ?
Théorème des écarts complémentaires
Notons x∗ la solution optimale du primal et y ∗ la solution du dual.
Si x∗ > 0, alors la j-ième contrainte du dual est saturée.
Si la j-ième contrainte du dual n'est pas saturée, alors x∗ = 0.
Si y ∗ > 0, alors la i-ième contrainte du primal est saturée.
Si la i-ième contrainte du primal n'est pas saturée, alors y ∗ = 0.

Pr S. HARROUDI 8 novembre 2023 14 / 18

Dualité en programmation linéaire Relation primal/dual Relation primal/dual

Théorèmes des écarts complémentaires

Exemple
Soit le problème primal suivant :


 max z = 15x1 + 25x2

 x1 + 3x2 ≤ 96



(P ) : x1 + x2 ≤ 40
1 + 4x2 ≤ 238



 7x

 x ≥ 0, x ≥ 0

1 2

La solution du primal est : x1 = 12; x2 = 28

Son dual est : 

 min w = 96y1 + 40y2 + 238y3

 y1 + y2 + 7y3 ≥ 15

(D) :

 3y1 + y2 + 4y3 ≥ 25

 y1 ≥ 0, y2 ≥ 0, y3 ≥ 0


Pr S. HARROUDI 8 novembre 2023 15 / 18

Dualité en programmation linéaire Relation primal/dual Relation primal/dual

Théorèmes des écarts complémentaires

Exemple
La dernière contrainte du primal n'est pas saturée, donc la variable du dual
associée est nulle : y3 = 0.
On obtient alors le système suivant :
y1 + y2 = 15
3y1 + y2 = 25
d'où : y1 = 5, y2 = 10, y3 = 0.

Pr S. HARROUDI 8 novembre 2023 16 / 18

Dualité en programmation linéaire Relation primal/dual Relation primal/dual

Théorémes des écarts complémentaires

Exercice :
Soit le PL primal suivant :


 min z = 2x1 + 5x2 + 3x3

x 1 ≥ 10





 x2 ≥

15
(P ) :

 x1 + 2x2 + x3 ≥ 60

 2x1 + x2 + 2x3 ≥ 95




 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0


1 Donner (D) le dual du programme (P).

2 Résoudre (D) par la méthode du simplexe.
3 Déduire la solution optimale du programme primal (P).

Pr S. HARROUDI 8 novembre 2023 17 / 18

Dualité en programmation linéaire Relation primal/dual Relation primal/dual

Théorèmes des écarts complémentaires

Exercice :
Le PL dual (D) est :


 max w = 10y1 + 15y2 + 60y3 + 95y4

 y1 + y3 + 2y4 ≤ 2



(D) : y2 + 2y3 + y4 ≤ 5
y3 + 2y4 ≤ 3





 y ≥ 0, y ≥ 0, y ≥ 0, y ≥ 0

1 2 3 4

Pr S. HARROUDI 8 novembre 2023 18 / 18