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.

Interprétation du programme dual

dual4

Publicités