Programme dual

Bien que le programme primal offre une solution par la méthode du simplexe, nous n’avons que la garantie de ne pas pouvoir améliorer la solution. Afin de prouver qu’il s’agit d’une solution optimale, nous devons aussi résoudre son programme dual. Ce programme dual, en plus de garantir ou non l’optimalité, permettra aussi d’analyser la sensibilité des variables au changement.

Construction du programme dual

Le programme dual est une symétrie du programme primal :

Il y a une contrainte pour chaque variable du programme primal; et une variable duale pour chaque contrainte du programme primal; les coefficients de la fonction objectif primale sont des éléments b du dual et réciproquement.
Il est à noter que le dual du dual est le primal.

primdual

dual

Dualité faible : pour toute solution du dual et pour toute solution du primal, la valeur objectif du dual z=cx* est supérieur ou égal à celui du primal w=by*.

dual2

Dualité forte : si le primal a une solution optimale x* alors le dual a une solution optimale y* et la valeur objectif du primal est égal à celle du dual.

Puisque le dual du dual est le primal, le primal a une solution optimale si et seulement si le dual a une solution optimale.

Il existe une relation dans les solutions du primal et du dual :

  • si un problème a des solutions réalisables et un domaine borné pour la fonction objectif, alors il en est de même pour son dual.
  • si un problème a des solutions réalisables et un domaine non borné pour la fonction objectif, alors son dual n’a pas de solution réalisable.
  • si un problème n’a pas de solutions réalisables, le dual a soit un domaine non borné pour la fonction objectif, soit n’a pas de solutions réalisables.

Écarts complémentaires

Version I. Soient x* et y* les solutions du primal et du dual. Ces deux solutions sont optimales si et seulement si :

  • pour tout j de 1 à n
    • soit la contrainte j du dual est saturée
    • soit x*j=0
    • ou les deux
  • pour tout i de 1 à m
    • soit la contrainte i du primal est saturée
    • soit y*i=0
    • ou les deux

dual3

Version II. Une solution x du primal est optimale si et seulement si il existe un vecteur y* tel que :

  • y* est admissible
  • si xj>0 alors la j-ème contrainte du dual est saturée
  • si la i-ème contrainte du primal n’est pas saturée alors y*i=0

Il est ainsi possible de construire une solution d’un programme à partir de l’autre, et ainsi prouver la dualité forte pour l’optimalité de la solution.

economic-interpretation-of-duality-shadow-price-and-the-complementary-slackness-property-19-638

Interprétation du programme dual

dual4

Publicités