Dualité faible Ecarts complémentaires
Sujet 5: Dualité — faible et forte
MHT 423 :
Modèles et méthodes d’optimisation
Andrew J. Miller
Dernière mise à jour: March 24, 2010
Dualité faible Ecarts complémentaires
Dans ce sujet...
1 Dualité faible
2 Dualité forte : Ecarts complémentaires
Théorème des écarts complémentaires
L’utilisation du théorème dans la méthode du simplexe
Dualité faible Ecarts complémentaires
1 Dualité faible
2 Dualité forte : Ecarts complémentaires
Théorème des écarts complémentaires
L’utilisation du théorème dans la méthode du simplexe
Dualité faible Ecarts complémentaires
Rappel : un exemple
max 1.9x1 + 2.6x2
s.à. 2x1 + x2 ≤ 4000
x1 + 2x2 ≤ 5000
x1 , x2 ≥ 0
La solution optimale est (1000, 2000).
Une solution réalisable pour le dual est y = (0, 1.9) ... mais cela
n’est pas optimale.
Une solution optimale pour le dual est y = (0.4, 1.1). Cette
solution a la même valeur objective que la solution optimale
primale.
Dualité faible Ecarts complémentaires
Definition
Théorème
Soit x̄ une solution réalisable d’un programme linéaire de
maximisation, et ȳ une solution réalisable de son dual.
Alors c T x̄ ≤ b T ȳ est toujours vrai.
Preuve :
Alors, n’importe quelle solution
réalisable pour le problème primal définit
une borne sur la valeur la fonction
c T x̄ ≤ (AT ȳ )T x̄ objective duale, et vice versa.
= (ȳ T A)x̄
= ȳ T (Ax̄) A noter : c T x̄ ≤ b T ȳ est toujours
≤ ȳ T b vrai si les solutions x̄ et ȳ sont
optimales.
≤ b T ȳ .
Dualité faible Ecarts complémentaires
Une conséquence : problèmes non-bornés et irréalisables
Si le primal est non-borné, alors le dual est irréalisable.
Exemple :
max x1 + x2
s.à x1 − 2x2 ≤ 1
x1 , x2 ≥ 0
Dualité faible Ecarts complémentaires
Une conséquence : problèmes non-bornés et irréalisables
Evidemment, on peut aussi dire le suivant : Si le dual est
non-borné, alors le primal est irréalisable.
Exemple :
max x1 + x2
s.à −x1 ≤ −2
−x2 ≤ −1
x1 + 2x2 ≤ 3
x1 , x2 ≥ 0
Dualité faible Ecarts complémentaires
Une autre conséquence : problèmes réalisables
Si tous les deux problèmes ont une solution réalisable, alors chaque
problème a (au moins) une solution optimale.
Pourquoi?
Dualité faible Ecarts complémentaires
Une autre possibilité
Il est possible que tous les deux problèmes (primal et dual) soient
irréalisables.
Exemple :
max x1 + x2
s.à x1 − 2x2 ≤ 1
x1 ≤ −1
x1 , x2 ≥ 0
Dualité faible Ecarts complémentaires
Les quatre possibilités pour un pair primal-dual
1 Le primal a une solution optimale est le dual a aussi une
solution optimale.
2 Le primal est non-borné est le dual est irréalisable.
3 Le dual est irréalisable est le primal est non-borné.
4 Tous les deux problèmes sont irréalisables.
Dans le cas 1, une solution optimale primale aura la même valeur
objective qu’une solution optimale duale.
Pour prouver qu’il existe seulement ces quatre possibilités, ainsi
que la déclaration précédente concernante le premier cas est vraie,
il faut considérer la dualité forte et le théorème des écarts
complémentaires.
Dualité faible Ecarts complémentaires
1 Dualité faible
2 Dualité forte : Ecarts complémentaires
Théorème des écarts complémentaires
L’utilisation du théorème dans la méthode du simplexe
Dualité faible Ecarts complémentaires
Théorème des écarts complémentaires
Théorème
Soit x̄ une solution réalisable pour le problème primal. La solution
x̄ est optimale si et seulement si il existe une solution réalisable ȳ
pour le problème dual telle que
(bi − nj=1 aij x̄j )ȳi = 0, i = 1, ..., m
P
(cj − m
P
i=1 aij ȳi )x̄j = 0, j = 1, ..., n
Dualité faible Ecarts complémentaires
Corollaire
C’est évident que si une telle solution duale ȳ existe, ȳ est
forcément une solution optimale.
Corollaire
Soit x̄ une solution optimale pour le problème primal, et ȳ une
solution optimale pour le problème dual. Alors
(bi − nj=1 aij x̄j )ȳi = 0, i = 1, ..., m
P
(cj − m
P
i=1 aij ȳi )x̄j = 0, j = 1, ..., n
Dualité faible Ecarts complémentaires
Corollaire : dualité forte
En considérant la preuve de la dualité faible, on voit l’inégalité
c T x̄ ≤ (AT ȳ )T x̄ =⇒ (c − AT ȳ )T x̄ ≤ 0.
Mais si x̄ et ȳ sont optimales, la théorème des écarts
complémentaires nous dit qu’il faut que
(c − AT ȳ )T x̄ = 0 =⇒ c T x̄ = (AT ȳ )T x̄
Alors, on a montré le suivant.
Corollaire : dualité forte
Soit x̄ une solution optimale pour le problème primal, et ȳ une
solution optimale pour le problème dual. Alors c T x = b T y .
Dualité faible Ecarts complémentaires
Corollaire : les quatre possibilités...
Corollaire
Etant donné un programme linéaire primal et son dual, une des quatre
déclarations suivantes et vraie pour ce pair de problèmes :
1 Le primal a une solution optimale est le dual a aussi une solution
optimale.
2 Le primal est non-borné est le dual est irréalisable.
3 Le dual est irréalisable est le primal est non-borné.
4 Tous les deux problèmes sont irréalisables.
Dualité faible Ecarts complémentaires
Conséquences
La dualité forte
Critères d’optimalité
Dualité faible Ecarts complémentaires
1 Dualité faible
2 Dualité forte : Ecarts complémentaires
Théorème des écarts complémentaires
L’utilisation du théorème dans la méthode du simplexe
Dualité faible Ecarts complémentaires
Exemples
Si on considère un point extrème qui n’est pas pas optimale, on
peut définir une solution duale qui vérifient les conditions d’écarts
complémentaires.
Mais cette solution ne sera pas réalisable pour le problème dual.
Par contre, pour une solution optimale, la solution duale ainsi
générée sera réalisable et optimale.
Dualité faible Ecarts complémentaires
Exemple 1 : Monet dans deux dimensions
Solution optimale: (1000, 2000)
Solution non-optimale: (0, 2500)
Dualité faible Ecarts complémentaires
Exemple 2 : Diététique
Solution optimale:
2 49 2 5
(6 , 9 , 6 , 5 )
3 99 3 99
Solution non-optimale:
39 6
(10, 9 , 0, 6 )
99 99
Dualité faible Ecarts complémentaires
A souvenir
Théorem D’écarts Complémentaires
A quoi sert le problème dual :
Son importance pour définir les critères d’optimalité ; cette
importance dépend sur le Théorem D’écarts Complémentaires
son utilisation dans l’algorithme de simplexe
