On considère le problème (P) écrit sous forme standard :Définition 3.1. Le problème dual (D) du problème (P) s’écrit :
Le problème (P) s’appelle le problème primal ; w est la fonction duale et les yi les variables duales.Remarques.
On établit facilement que le problème dual de (D) est (P).
On verra dans le chapitre 6, consacré à la relaxation lagrangienne, une géné ralisation de la définition de la dualité.
De la définition du problème dual, on déduit la proposition suivante :Proposition 3.2. Soient une solution réalisable du problème primal et une solution réalisable du problème dual. On a :
De plus, si les deux quantités ci-dessus sont égales, alors constituent une solution optimale du problème primal et une solution optimale du problème dual.Preuve. Les solutions étant réalisables respectivement pour le problème primal et le problème dual, on a :
En particulier, ceci montre que les problèmes primal et dual sont bornés : des solutions optimales existent. Si l’inégalité précédente est une égalité, toute solution réalisable de (P) donne à z une valeur majorée par : est solution optimale de (P). On montre de même que, toujours en cas d’égalité, est solution optimale de (D).Application.
La considération du problème dual nous permet de vérifier que nous avons bien obtenu, par l’algorithme du simplexe, une solution optimale pour un problème donné. Nous allons l’expliquer sur le problème traité dans la partie 1.2, page 16. Le problème (P) est …