Dual programme linéaire

[invitec3b608ea]

Bonjour à tous,

Ma question est toute bête... nous sommes d'accord qu'en programmation linéaire, un programme linéaire et son dual ont la même valeur de fonction objectif (pour peu que celle-ci existe et soit finie).

Or le programme suivant :

minimiser x1-2x2

sous les contraintes

x1-x2>=-3
-2x1>=-2
x2>=2

a pour valeur de fonction optimale -3, tandis que son dual :

maximiser -3y1-2y2+2y3

sous les contraintes

y1-2y2<= 1
-y1+y3 <=-2

a pour valeur de fonction optimale -7.

Est-ce que je me trompe de dual ?! J'ai pourtant vérifié et re-revérifié, quelque chose m'échappe ou une bête erreur dans le passage au dual a été commise...

Si quelqu'un voyait l'astuce, ça m'aiderait beaucoup.

Merci à vous !
-----

[invitec3b608ea]

Je précise que je n’ai pas du tout l’habitude de travailler avec ces programmes linéaires… donc je peux faire une erreur n’importe où (mais a priori, je ne la vois pas du tout cette erreur…). Donc la formule générique de passage au dual :

min {cX|AX>=b,X>=0} -> max{Yb|YA<=c,Y>=0}

On voit donc que :

max{Yb|YA<=c,Y>=0}=min{-Yb|-YA>=-c,Y>=0}

a pour dual :

max{-cX|-AX<=-b,X>=0} = min{cX|AX>=b,X>=0} c’est-à-dire le primal.

Et donc, le dual du dual c’est le primal…

Parfois il faut réadapter la formule, ici (problème message n°1) ce n’est pas le cas. Et donc, un résultat assez évident :

Comme c>=YA (dual), on a cX>=YAX>=Yb

donc la fonction économique du primal est plus grande que celle du dual. Par suite, je donne l’intuition avec les mains parce que je n’ai pas la preuve formelle à disposition dans l’immédiat : comme le dual du dual c’est le primal, on a aussi Yb>=cX (pour peu que les valeurs soit finies et existent) et donc les fonctions économiques sont de valeurs égales pour ces deux programmes.

Bon, avec le programme linéaire fourni lors du message 1, je ne vérifie pas cette égalité entre les fonctions à max/minimiser. Pourtant, et j’ai (re-re-re)vérifié quelques fois déjà… je ne crois ni me tromper de dual, ni me tromper dans la résolution des programmes (faits à la main +sieurs fois - simplex + dual simplex - + vérification avec un solver).

Et c’est là que je ne parviens pas à imaginer une indication sur l’erreur commise quelque part …


PS : désolé pour l'absence de LaTeX, autrefois il y avait ici des balises que je ne trouve plus...

[invitec3b608ea]

le résultat de -3 était obtenu pour une maximisation du primal ....... j'ai maximisé au lieu de minimiser à 3 reprises (!) et je l'ai encodé dans le solver avec une maximisation. J'étais épuisé et énervé et suis resté des heures à faire la même erreur. Désolé.