Programmation linéaire

Chapitre 6 : Théorie de la dualité

Ilyas Himmich
i.himmich@insea.ac.ma

13 janvier 2022
Motivation

Définition de la dualité

Interprétation économique de la dualité

Dualité forte et faible

Complémentarité

2
Motivation
Étant donnée un programme linéaire sous la forme vectorielle :
max z = ct x
Ax ≤ b (1)
x≥0

Questions
Est ce qu’on peut maximiser jusqu’à l’infini ?
Peut-on trouver une borne supérieur sur x ?

Exemple

max z = x1 + x2
4x1 + 5x2 ≤ 20
2x1 + x2 ≤ 6 (2)
x2 ≤ 2
x1 , x2 ≥ 0
3
Motivation

La région admissible (domaine réalisable) est bornée. La solution optimale est alors
finie.
Soit x = (x1 , x2 ) une solution réalisable quelconque. On a :

z = x1 + x2 ≤ 4x1 + 5x2 ≤ 20 (3)

On peut faire mieux :

z = x1 + x2 ≤ 2x1 + x2 ≤ 6 (4)
Cette borne peut être améliorée davantage :

z = x1 + x2 = 12 (2x1 + 2x2 )
= 12 (2x1 + x2 ) + 21 x2
(5)
≤ 12 6 + 12 2
≤4

4
Motivation
On peut alors borner z supérieurement avec une combinaison linéaire des termes de
gauche des contraintes comme suit :

z = x1 + x2 ≤ y1 (4x1 + 5x2 ) + y2 (2x1 + x2 ) + y3 (x2 )

= (4y1 + 2y2 )x1 + (5y1 + y2 + y3 )x2 (6)
≤ y1 (20) + y2 (6) + y3 (2)
Et ce, à condition que :

4y1 + 2y2 ≥ 1
5y1 + y2 + y3 ≥ 1 (7)
y1 , y2 , y3 ≥ 0
La meilleure borne supérieure est la solution du système :

min 20 y1 + 6 y2 + 2 y3
s.c. 4y1 + 2y2 ≥ 1
(8)
5y1 + y2 + y3 ≥ 1
y1 , y2 , y3 ≥ 0

5
Motivation
Résumé
Trouver une combinaison valide des contraintes permettant de borner terme à
terme la fonction objectif :
max z = x1 + x2
4x1 + 5x2 ≤ 20 ×y1
2x1 + x2 ≤ 6 ×y2
x2 ≤ 2 ×y3
(4y1 + 2y2 ) x1 + (5y1 + y2 + y3 ) x2 ≤ 20y1 + 6y2 + 2y3

min 20 y1 + 6 y2 + 2 y3 (borne sup minimale)

s.c.
4 y1 + 2 y2 ≥ 1
5 y1 + y2 + y3 ≥ 1 (9)
yi ≥ 0, i = 1, 2, 3

6
Définition

Problème primal Problème dual

 
 max zP = cT x  min zD = yT b
(P) Ax ≤ b (D) yT A ≥ cT
 
x ∈ Rn+ y ∈ Rm+

Écriture équivalente du dual

 
 min zD = yT b  min zD = bT y
yT A ≥ cT ≡ AT y ≥ c
 
y ∈ Rm+ y ∈ Rm+

7
Dé nition de la dualité

Remarques

• m = nombre de contraintes de (P) = nombre de variables de (D),

• n = nombre de variables de (P) = nombre de contraintes de (D).
• La matrice des contraintes du dual est la transposée de la matrice des contraintes
du primal.
• Le vecteur de la fonction objectif du dual est le vecteur des membres de droite du
primal et vice-versa.
• Si (P) contient deux contraintes, (D) contient deux variables et peut être résolu
graphiquement quelque soit le nombre de variables de (P).

8
Dé nition de la dualité

Exercice 1
Montrer que le dual du dual est le primal.

Exercice 2
Donner le dual du problème primal suivant :

max z = aT x + bT y
AT x ≤ c
BT y ≤ d (10)
T
c y=e
y≥0

9
Dé nition de la dualité

Exercice 3
Donner le dual du problème primal suivant :

max z = c x
 ( ) ( )
{  A b
Ax = b x≤
(P) ⇔ −A −b
x ≥ 0 
x≥0

10
Remarque
On peut construire le dual en utilisant la définition de la dualité après passage à la
forme canonique. Néanmoins, on peut le faire directement en se basant sur ls règles
suivantes.

Théorème
Les liens entre le programme primal et son dual sont les suivants :
Primal Dual
maximisation minimisation
coefficient de z second membre des contraintes
second membre
 des contraintes coefficient
 de w
 =  sans contrainte de signe
contrainte ≤ variable ≥0
 
 ≥ ≤0

 sans contrainte de signe  =
variable ≥0 contrainte ≥
 
≤0 ≤

11
Interprétation économique de la dualité

Problème de l’agriculteur
L’agriculteur cherche à maximiser le profit sous contraintes de ressources
disponibles.
Le problème primal (P) est :

Max zP = 1000 x1 + 2000 x2

s.c x1 + x2 ≤ 150
4x1 + 2x2 ≤ 440
x1 + 4 x2 ≤ 480
x1 ≤ 90
x1 ≥ 0 et x2 ≥ 0

12
Interprétation économique de la dualité

Scénario
Supposons qu’un client (grossiste) voudrait acheter la totalité de nos ressources
disponibles. Notre agriculteur acceptera certainement cette proposition si le prix
offert par ce client lui procure au moins le même profit.

Le problème du client consiste à minimiser les frais d’achat des ressources : c’est à
dire 150y1 + 440y2 + 480y3 + 90y4 sous la contrainte que les prix satisfont notre
agriculteur. Il devrait donc proposer des prix à chacune de ces ressources.
• y1 représente le prix d’un hectare de terrain.
• y2 le prix d’un m3 d’eau.
• y3 le prix d’une heure de main d’oeuvre.
• y4 le prix de la permission de la culture d’un hectare de tomates.

13
Interprétation économique de la dualité

Contraintes imposées par l’agriculteur

Pour notre agriculteur :
- 1 hectare de terrain, 4m3 d’eau, 1 heure de travail et une permission pour 1 hectare
est équivalent à un revenu de 1000 dhs.
- 1 hectare de terrain, 2m3 d’eau et 4 heures de travail lui engendrent un revenu de
2000 dhs.
Par conséquent, l’agriculteur n’est prêt à vendre ses ressources que si
y1 + 4y2 + y3 + y4 lui rapporte un revenu supérieur ou égale à 1000 DH et que si
y1 + 2y2 + 4y3 lui rapporte un revenu supérieur ou égal à 2000 DH.

14
Interprétation économique de la dualité

Problème du client
Le client cherche alors à minimiser les coûts d’achat des ressources sous contraintes
de profits imposés par le client.
Ainsi le problème du client est (D) :

Min zD = 150 y1 + 440 y2 + 480 y3 + 90 y4

s.c y1 + 4 y2 + y3 + y4 ≥ 1000
y1 + 2 y2 + 4 y3 ≥ 2000
y1 , y2 , y3 et y4 ≥ 0

15
Interprétation économique de la dualité

16
Dualité forte et faible

Notation

(P) zP = max cT x avec x ∈ X = {x ∈ Rn /A x ≤ b , x ≥ 0}

x

(D) zD = min yT b avec x ∈ Y = {b ∈ Rm /yT A ≤ cT , y ≥ 0}

y

Théorème de dualité faible

Pour tout x ∈ X et y ∈ Y, on a :

cT x ≤ yT b

17
Dualité forte et faible

Corrolaire 1
• Si (P) est réalisable non borné (zP = +∞), alors (D) est non réalisable (Y = ∅).
• Si (D) est réalisable non borné (zD = −∞), alors (P) est non réalisable (X = ∅).

Corrolaire 2
S’il existe x∗ ∈ X et y∗ ∈ Y, tels que : cT x∗ = y∗ T b, alors :
• x∗ est optimale pour (P).
• y∗ est optimale pour (D).

18
Dualité forte et faible

Corrolaire 1
• Si (P) est réalisable non borné (zP = +∞), alors (D) est non réalisable (Y = ∅).
• Si (D) est réalisable non borné (zD = −∞), alors (P) est non réalisable (X = ∅).

Théorème de dualité forte

• Si (P) et (D) possèdent des solutions réalisables, alors ils ont tous les deux des
solutions optimales finies et dans ce cas : zP = zD .

19
Dualité forte et faible

Rappelons les trois cas qui peuvent se produire pour un programme linéaire (PL) :
• RB : il existe une ou plusieurs solutions optimales finies.
• RNB : la solution optimale est infinie (z = +∞).
• NR : le PL ne possède pas de solutions réalisables.

Théorème
Seuls les trois cas suivants peuvent se produire :
A : (P) et (D) possèdent des solutions optimales finie et zP = zD
B : (P) ou (D) possède une solution réalisable, mais pas les deux.
C : (P) et (D) ne sont pas réalisables.

20
Dualité forte et faible

(D)
RB RNB NR
RB A × ×
(P) RNB × × B
NR × B C

Théorème
Seuls les trois cas suivants peuvent se produire :
A : (P) et (D) possèdent des solutions optimales finie et zP = zD
B : (P) ou (D) possède une solution réalisable, mais pas les deux.
C : (P) et (D) ne sont pas réalisables.

21
Dualité forte et faible

Exercice
Analyser l’ensemble des solutions du problème :

(P) zP = max cT x
x
Ax = 0
c≥0

22
Complémentarité

Notation
(P) zP = maxx cT x avec x ∈ X = {x ∈ Rn /A x ≤ b , x ≥ 0}
(D) zD = miny yT b avec x ∈ Y = {b ∈ Rm /yT A ≤ cT , y ≥ 0}

Théorème des écarts supplémentaires

Soient x∗ ∈ X et y∗ ∈ Y.
x∗ et y∗ sont primal-dual optimales si et seulement si :

[y∗ T A − cT ] x∗ = 0 = y∗ T [A x∗ − b]

Définition
• [A x∗ − b] : Écart primal.
• [y∗ T A − cT ] : Écart dual.

23
Complémentarité

Autre façon d’écrire le théorème des écarts supplémentaires

• Pour chaque j ∈ {1, 2, ..., n} : x∗j = 0 ou (y∗ T A)j = cj

• Pour chaque i ∈ {1, 2, ..., m} : y∗i = 0 ou (A x∗ )i = bi

Remarque
Pour vérifier si x∗ est une solution optimale de (P), il suffit de vérifier l’existence d’une
solution y∗ ∈ Rm telle que :
• y∗i = 0 lorsque (A x∗ )i < bi
T
• (y∗ A)j = cj lorsque x∗j > 0.
Puis on vérifie si y∗ est dual réalisable.

24
Complémentarité

Exercice
Est ce que la solution y = (0, 43 , 32 , 53 , 0)T est optimale pour le problème primal suivant ?

Max zP = 7 y1 + 6 y2 + 5 y3 − 2 y4 + 3 y5

s.c : y1 + 3 y2 + 5 y3 − 2 y4 + 2 y5 ≤ 4
4 y1 + 2 y2 − 2 y3 + y4 + y5 ≤ 3
2 y1 + 4 y2 + 4 y3 − 2 y4 + 5 y5 ≤ 5
3 y1 + y2 + 2 y3 − y4 − 2 y5 ≤ 1
y1 , y2 , y3 , y4 et y5 ≥ 0

25