Recherche opérationnelle

Mohamed Chahhou
PROGRAMMATION LINÉAIRE :
DUALITÉ
 Borne supérieur de la fonction
objectif: exemples
Soit le PL suivant dans sa forme canonique, sans résoudre max 6x1 + 5x2
le programme linéaire, trouver une borne supérieure de la S.C x 1 + x2 ≤ 5
fonction objectif. 3x1 + 2x2 ≤ 12
x1, x2 ≥ 0
a. Si aucune des contraintes n’existe, alors la borne
supérieure est ∞

b. Si on multiplie la deuxième contrainte par 3, on obtient :

9x1 + 6x2 ≤ 36
Or on sait que x1 ≥ 0, donc 9x1 ≥ 6x1
Et on sait que x2 ≥ 0, donc 6x2 ≥ 5x2
6x1 + 5x2 ≤ 9x1 + 6x2 ≤ 36
36 est donc une borne supérieure de la fonction objectif
 Borne supérieur de la fonction
objectif: exemples

c. Si on multiplie la première contrainte par 6, on obtient:

6x1 + 5x2 ≤ 6x1 + 6x2 ≤ 30
30 est la nouvelle borne supérieure de la fonction objectif max 6x1 + 5x2
S.C x 1 + x2 ≤ 5
d. 3x1 + 2x2 ≤ 12
1 * ( x1 + x2 ) ≤ 1 * 5 x1, x2 ≥ 0
+
2 * (3x1 + 2x2 ) ≤ 2 * 12
= 7x1 + 5x2 ≤ 29

6x1 + 5x2 ≤ 7x1 + 5x2 ≤ 29

29 est la nouvelle borne supérieure

Quelle est la plus petite borne supérieure de la fonction objectif ?

 Borne supérieur de la fonction
objectif: Généralisation
max 6x1 + 5x2
Pour généraliser cette approche, nous allons
S.C x 1 + x2 ≤ 5
multiplier les deux contraintes par des coefficients
3x1 + 2x2 ≤ 12
non négatifs y1 et y2 et calculer leur somme
x1, x2 ≥ 0

y1 x1 + y1 x2 ≤ 5y1
(y1 + 3y2)x1 + (y1 + 2y2)x2 ≤ 5y1 + 12y2
3y2 x1 + 2y2 x2 ≤ 12y2

Si (y1 + 3y2) ≥ 6 et (y1 + 2y2) ≥ 5 alors

5y1 + 12y2 est une borne supérieure

Puisqu’on souhaite trouver la plus petite borne supérieur, on doit donc trouver les
valeurs de y1 et y2 qui minimisent 5y1 + 12y2 avec les contraintes : (y1 + 3y2) ≥ 6 et
(y1 + 2y2) ≥ 5
 Programme linéaire dual
Nous avons obtenu un nouveau programme linéaire
Soit : appelé le DUAL du PL de départ (appelé PRIMAL)
min 5y1 + 12y2
S.C y1 + 3y2 ≥ 6
y1 + 2y2 ≥ 5 On sait que : 6x1 + 5x2 ≤ 5y1 + 12y2 (pour tout xi et yi)
y1, y2 ≥ 0 Toute valeur de la fonction objectif du dual est
supérieure ou égale à toute valeur de la fonction
objectif du primal

Puisque pour chaque contrainte du primal, on a associé un coefficient yi, le dual a donc
autant de variables de décision que de contraintes dans le primal

On remarque que la première contrainte du dual est créée à partir des coefficient de x1
dans le primal. De la même manière, on remarque aussi que la deuxième contrainte du
dual est issue des coefficients de x2 dans le primal.
Le dual a donc autant de contraintes que de variables de décision dans le primal
 Programme linéaire dual

PRIMAL (P) DUAL (D)

max 6x1 + 5x2 min 5y1 + 12y2
S.C x 1 + x2 ≤ 5 S.C y1 + 3y2 ≥ 6
3x1 + 2x2 ≤ 12 y1 + 2y2 ≥ 5
x1, x2 ≥ 0 y1, y2 ≥ 0

Le problème de maximisation est devenu un problème de minimisation

Le sens des inégalités a changé
Les membres droits des contraintes du primal sont devenu les coefficients de la
fonction objectif du dual
Les coefficients de la fonction objectif du primal sont devenu les membres droits des
contraintes du dual
Programme linéaire dual
Programme linéaire dual
Programme linéaire dual
Définition du dual dans le cas général
Comment obtenir le dual si le primal n’est pas dans la forme canonique, càd si le
primal possède :
- des contraintes ≥ ou = au lieu de ≤
- des variables négatives ou réelles ou de lieu de variables non négatives
Minimisation maximisation
Fonction objectif min Fonction objectif max
Second membre des contraintes Fonction objectif
A matrice des contraintes AT matrice des contraintes
Contrainte i de type ≥ Variable yi ≥ 0
Contrainte i de type ≤ Variable yi ≤ 0
Contrainte i de type = Variable yi sans restriction de signe
Variable xj ≥ 0 Contrainte j de type ≤
Variable xj ≤ 0 Contrainte j de type ≥
Variable xj sans restriction de signe Contrainte j de type =
On lit de gauche à droite quand le primal est en minimisation
On lit de droite à gauche quand le primal est en maximisation
 dual dans le cas général : exemple

Primal Dual

max 6x1 + x2 + 3x3 min 10y1 + 4y2 + 2y3

S.C 8x1 + x2 ≤ 10 S.C 8y1 + + 6y3 ≥ 6
x2 + x3 = 4 y1 + y2 - 2y3 = 1
6x1 – 2x2 + +4x3 ≥ 2 y2 + 4y3 ≤ 3
x1 ≥ 0, x3 ≤ 0, x2 réel y1 ≥ 0, y3 ≤ 0, y2 réel
 Théorèmes de la dualité

Considérons le problème P et son dual D

Si P et D ont des solutions réalisables X = Y, alors X est

une solution optimale pour P et Y est une solution
optimale pour D
 Théorèmes de la dualité

Considérons le problème P et son dual D

Si l’un des 2 problèmes a un optimum non fini (non

borné), alors l’autre problème n’a pas de solution
réalisable
Dualité forte : exemple
 Interprétation économique
Soit une entreprise agricole qui souhaite planter 3 variétés de fruits : A, B et C.
On souhaite déterminer les superficies xi (en hectare) des terres à planter pour avoir
un bénéfice maximal.

Par exemple, il faut 3 heures de travail par hectare pour planter le fruit B et 2 heures
de machinerie. 1 hectare de fruit B nous donne un profit de 1400.
La dimension totale du terrain est de 340 ha et on dispose de 2400 heures de travail
et de 560 heures en temps de machinerie.
Interprétation économique

max z = 1100xA + 1400xB + 1500xC

S.C xA + xB + xC ≤ 340 (dimension du terrain)
2xA + 3xB + xC ≤ 2400 (temps de travail)
xA + 2xB + 3xC ≤ 560 (temps machine)
xA , xB , xC ≥ 0
 Interprétation économique

Supposons qu’un acheteur souhaite acheter les activités de l’entreprise.

Posons :
y1 = prix à offrir à l’entreprise pour acheter un hectare de terrain
y2 = prix à offrir à l’entreprise pour acheter une heure de travail
y2 = prix à offrir à l’entreprise pour acheter une heure de machine

L’acheteur doit minimiser le total du prix à payer :

min w = 340y1 + 2400y2 + 560y3

L’entreprise a le choix entre vendre les ressources à l’acheteur ou bien de refuser l’offre
de l’acheteur si elle estime qu’il est plus profitable pour elle de planter elle-même les
fruits et de les revendre.

Afin que l’offre de l’acheteur soit accepté, il doit offrir au moins autant que le bénéfice
de chacune des activités
 Interprétation économique

Pour le fruit A : y1 + 2y2 + y3 ≥ 1100

On voit que l’acheteur propose un prix total au moins égal au bénéfice(1100) qu’aurait
fait l’entreprise si elle avait planter elle-même le fruit A

De la même manière, on obtient pour :

le fruit B : y1 + 3y2 + 2y3 ≥ 1400
le fruit C : y1 + y2 + 3y3 ≥ 1500
 Interprétation économique
Comparons les deux programmes linéaires :

max z = 1100xA + 1400xB + 1500xC On remarque que le problème de

S.C xA + xB + xC ≤ 340 l’acheteur est le dual de celui du vendeur.
2xA + 3xB + xC ≤ 2400 Le principe de la dualité peut s’énoncer
xA + 2xB + 3xC ≤ 560 de la manière suivante :
xA , xB , xC ≥ 0 le plus bas prix total à payer pour
l’acheteur doit être égal au bénéfice
maximal pour le producteur.
min w = 340y1 + 2400y2 + 560y3
S.C y1 + 2y2 + y3 ≥ 1100 L’accord de vente ne se fera que si les
y1 + 3y2 + 2y3 ≥ 1400 deux atteignent la valeur optimale de
y1 + y2 + 3y3 ≥ 1500 leur fonction objectif et on aura z* = w*
y1 , y2 , y3 ≥ 0

A un programme d’allocation optimal des ressources (primal) correspond un

programme de tarification optimal de ces ressources (dual)
 Théorème des écarts complémentaires

Soit X = [x1, x2,…, xn] une solution réalisable du primal et notons si les variables d’écart du
primal
Soit Y = [y1, y2,…, ym] une solution réalisable du dual et notons ei les variables d’écart du
dual
Alors X est une solution optimale du primal et Y est une solution optimale du dual si et
seulement si :

si yi = 0 (i=1,2, …m) et
ej xj = 0 (j=1,2, … n)
 Théorème des écarts complémentaires
:exemple
Primal Solution optimale du primal
Max z = 60x1 + 30x2 + 20x3 x1 = 2, x2 = 0, x3 = 8
SC 8x1 + 6x2 + x3 ≤ 48 s1 = 24, s2 = 0, s3 = 0
4x1 + 2x2 + 1.5x3 ≤ 20 z* = 280
2x1 + 1.5x2 + 0.5 x3 ≤ 48
xi ≥ 0

Dual Solution optimale du dual

Min w = 48y1 + 20y2 + 8y3 y1 = 0, y2 = 10, y3 = 10
SC 8y1 + 4y2 + 2y3 ≥ 60 e1 = 0, e2 = 5, e3 = 0
6y1 + 2y2 + 1.5y3 ≥ 30 w* = 280
y1 + 1.5y2 + 0.5y3 ≥ 20
yi ≥ 0 On peut vérifier que :
si yi = 0 (i=1,2, …m) et
ej xj = 0 (j=1,2, … n)
 Théorème des écarts
complémentaires: application
En utilisant le théorème des écarts complémentaires, on peut trouver la solution du primal
si on connait la solution de son dual
Primal
Max z = 60x1 + 30x2 + 20x3
SC 8x1 + 6x2 + x3 + s1 = 48 si yi = 0 => s1 ≥ 0, s2 = 0, s3 = 0
4x1 + 2x2 + 1.5x3 + s2 = 20 ej xj = 0 => x1 ≥ 0, x2 =0, x3 ≥ 0
2x1 + 1.5x2 + 0.5 x3+ s3 = 48
xi ≥ 0
En remplaçant dans le problème primal, on
obtient le système d’équations à 3 inconnues :
Solution optimale du dual 8x1 + x3 + s1 = 48
y1 = 0, y2 = 10, y3 = 10 4x1 + 1.5x3 = 20
e1 = 0, e2 = 5, e3 = 0 2x1 + 0.5 x3 = 48
w* = 280
En résolvant ce système d’équations, on obtient la
solution optimale du primal:
s1 = 24, x1 = 2, x3 = 24 et z*=280
 Exercice

Résoudre le PL suivant:

Min z = 2x1 + 3x2

SC 5x1 + 10x2 ≥ 90
4x1 + 3x2 ≥ 48
x1 ≥3
xi ≥ 0
 Exercice : solution
Dual Solution optimale du dual:
max w= 90y1 + 48y2 + 3y3 y1 = 6/25
SC 5y1 + 4y2 + y3 ≤ 2 y2 = 1/5
10y1 + 3y2 ≤3 y3 = 0
yi ≥ 0 w* = 31.2

Dernier tableau du simplexe

y1 y2 y3 e1 e2 C
y2 0 1 2/5 2/5 -1/5 1/5
y1 1 0 -3/25 -3/25 1/25 6/25
-w 0 0 -27/5 -42/5 -24/5 -31.2
 Exercice : solution

En appliquant le théorème des écarts complémentaires, on obtient :

si yi = 0 => s1 = 0, s2 = 0, s3 ≥ 0
ej xj = 0 => x1 ≥ 0, x2 ≥ 0

En remplaçant dans : On obtient: Solution du primal

5x1 + 10x2 - s1 = 90 5x1 + 10x2 = 90 x1 = 42/5

4x1 + 3x2 - s2 = 48 4x1 + 3x2 = 48 x2 = 24/5
x1 - s3 = 3 x1 - s3 = 3 s3 = 27/5
Z* = 31.2