Dualité forte en programmation linéaire : définition et exemples

La dualité forte est un résultat central de la programmation linéaire : elle relie un problème d’optimisation à un second problème, appelé dual. Lorsqu’ils admettent une solution optimale, leurs valeurs optimales coïncident. Cette propriété ne sert pas seulement à calculer une valeur : elle permet de certifier l’optimalité d’une solution, d’interpréter la valeur des ressources et de mieux comprendre les algorithmes de résolution.

Situer la dualité forte dans un problème de programmation linéaire

Problème primal, problème dual et correspondance entre contraintes et variables

Le problème formulé initialement est appelé problème primal. À chaque programme linéaire est associé un problème dual construit selon des règles précises : les contraintes du primal deviennent des variables du dual, tandis que les variables du primal deviennent des contraintes du dual. Pour un primal de maximisation avec contraintes de type « inférieur ou égal » et variables positives, le dual est habituellement un problème de minimisation. Les coefficients techniques sont transposés : si la matrice du primal est A, celle utilisée dans les contraintes duales est A transposée. Cette relation explique pourquoi le dual n’est pas un simple exercice de reformulation. Il représente souvent une autre lecture du même système : le primal cherche des quantités à produire ou à sélectionner ; le dual attribue une valeur aux ressources limitées. Les méthodes historiques de résolution, notamment celles issues de l’histoire de l’algorithme du simplexe, exploitent directement cette structure.

Rôle des problèmes de maximisation et de minimisation

Dans une interprétation économique, le primal maximise par exemple un bénéfice sous des contraintes de capacité. Le dual minimise le coût total de ressources valorisées, tout en imposant que chaque activité soit correctement couverte par cette valorisation.

Élément	Primal	Dual
Décision principale	Quantités d’activités	Valeurs attribuées aux ressources
Objectif courant	Maximiser un gain	Minimiser un coût ou une borne
Lecture pratique	Utiliser les ressources	Évaluer leur rareté

Primal et dual décrivent donc le même problème sous deux angles complémentaires, sans nécessairement avoir le même nombre de variables ou de contraintes.

Énoncer le théorème de dualité forte

Égalité des valeurs optimales du primal et du dual

Le théorème de dualité forte affirme que, pour une paire primal-dual de programmation linéaire, si une solution optimale finie existe, alors l’autre problème possède aussi une solution optimale et les deux fonctions objectif ont exactement la même valeur. Autrement dit, si le maximum du primal vaut 9, le minimum du dual vaut également 9. Les vecteurs de décision peuvent être différents et leurs dimensions aussi, mais la valeur optimale est identique. Cette égalité transforme une borne en certificat : une solution réalisable du primal et une solution réalisable du dual de même valeur sont toutes deux optimales.

Conditions d’existence d’une solution optimale et cas particuliers d’infaisabilité ou de non-bornitude

La dualité forte ne signifie pas que tout programme linéaire possède automatiquement une solution. Il faut distinguer plusieurs situations :

• si le primal est réalisable et admet un optimum fini, le dual admet aussi un optimum fini de même valeur ;
• si le primal est non borné vers l’amélioration, son dual est infaisable ;
• si le dual est non borné vers l’amélioration, son primal est infaisable ;
• les deux problèmes peuvent être infaisables, situation où aucune égalité de valeurs optimales ne peut être invoquée.

La prudence est essentielle : l’infaisabilité d’un problème ne permet pas, à elle seule, de conclure que l’autre est non borné. Il peut également être infaisable.

Distinguer dualité faible et dualité forte

L’inégalité fournie par la dualité faible

La dualité faible s’applique avant toute résolution complète. Pour un primal de maximisation et un dual de minimisation, toute solution réalisable du primal a une valeur inférieure ou égale à toute solution réalisable du dual. Le dual fournit donc une borne supérieure au maximum recherché. Cette propriété est plus générale dans son usage : elle reste valable pour chaque paire de solutions réalisables, même lorsqu’elles ne sont pas optimales. Elle sert notamment à détecter l’amélioration encore possible d’une solution candidate.

L’écart de dualité nul comme critère d’optimalité

L’écart de dualité est la différence entre la valeur duale et la valeur primale pour deux solutions réalisables. En programmation linéaire, un écart nul certifie l’optimalité des deux solutions. La dualité forte garantit qu’un tel écart nul est atteignable lorsque les conditions d’existence sont réunies. Dans des cadres plus larges, cette égalité demande des hypothèses supplémentaires. Les liens avec l’optimisation convexe en apprentissage automatique sont importants : en optimisation non linéaire, la dualité peut présenter un écart strictement positif.

Vérifier l’optimalité avec les conditions de complémentarité

Contraintes saturées et variables duales strictement positives

Les conditions de complémentarité précisent quelles contraintes et variables peuvent être actives simultanément. Pour chaque contrainte primale de type inférieur ou égal, le produit entre son écart de capacité et la variable duale associée doit être nul à l’optimum. Ainsi, si une variable duale est strictement positive, la contrainte primale correspondante est nécessairement saturée. À l’inverse, une ressource non entièrement utilisée possède un prix d’ombre nul. Ce mécanisme donne une interprétation opérationnelle aux multiplicateurs du dual.

Variables primales positives et contraintes duales à l’égalité

Réciproquement, si une variable primale est strictement positive, sa contrainte duale associée doit être satisfaite à l’égalité. Une activité réellement retenue dans la solution apporte donc exactement autant qu’elle coûte selon la valorisation duale. Ces conditions sont une manière efficace de contrôler une solution proposée. Elles prolongent les principes présentés dans les conditions de Karush-Kuhn-Tucker, dont elles constituent le cas linéaire particulièrement clair.

Illustrer la dualité forte sur un exemple chiffré simple

Formulation du problème primal et construction de son dual

Considérons le primal suivant : maximiser 3x + 2y, sous les contraintes x + y inférieur ou égal à 4, 2x + y inférieur ou égal à 5, avec x et y positifs ou nuls. Son dual consiste à minimiser 4u + 5v, sous les contraintes u + 2v supérieur ou égal à 3 et u + v supérieur ou égal à 2, avec u et v positifs ou nuls. Les variables u et v correspondent respectivement aux deux contraintes de ressources du primal.

Comparaison des solutions et interprétation économique des prix d’ombre

La solution primale x = 1 et y = 3 satisfait les deux contraintes à l’égalité et donne une valeur de 9. Côté dual, u = 1 et v = 1 est réalisable : les deux contraintes duales sont aussi à l’égalité, et l’objectif vaut 4 + 5 = 9. La dualité faible interdit au primal de dépasser toute valeur duale réalisable. Comme les deux valeurs sont égales, les deux solutions sont optimales. Ici, une unité supplémentaire de chaque ressource aurait, localement, une valeur marginale de 1 selon le dual, sous réserve que la base optimale reste pertinente.

Utiliser la dualité forte sans commettre les erreurs courantes

Respecter les conventions de signe et les formes canoniques

La construction du dual dépend du sens de l’objectif, du sens des contraintes et du signe des variables. Une variable primale libre correspond à une contrainte duale d’égalité ; une contrainte primale d’égalité engendre une variable duale libre. Appliquer mécaniquement les règles du cas standard à un modèle mixte conduit fréquemment à un dual incorrect.

Ne pas confondre valeur optimale, solution optimale et faisabilité

L’égalité des objectifs ne signifie pas que les solutions primale et duale sont identiques. Elle ne dispense pas non plus de vérifier la faisabilité des deux côtés. Enfin, la dualité forte n’est pas la même chose que la relaxation d’un modèle : cette dernière peut fournir des bornes, comme l’explique la relaxation lagrangienne en optimisation, sans garantir automatiquement un écart nul.

La dualité forte comme preuve d’optimalité

La dualité forte établit un lien décisif entre deux formulations d’un même programme linéaire : lorsque les conditions appropriées sont réunies, primal et dual atteignent la même valeur optimale. Cette égalité donne bien plus qu’un résultat numérique : elle fournit une preuve d’optimalité et éclaire la valeur des ressources à travers les variables duales. La dualité faible, l’écart nul et les conditions de complémentarité forment un ensemble cohérent pour contrôler une solution. En pratique, il faut d’abord vérifier la faisabilité, respecter les règles de construction du dual, puis comparer les objectifs. Une solution primale et une solution duale réalisables ayant une valeur identique constituent un certificat d’optimalité fiable.