Probleme liniaire : dualite
Résolu
leen.net
Messages postés
212
Date d'inscription
Statut
Membre
Dernière intervention
-
KX Messages postés 16761 Date d'inscription Statut Modérateur Dernière intervention -
KX Messages postés 16761 Date d'inscription Statut Modérateur Dernière intervention -
Bonjour,
quelqu'un pourrait m'expliquer le problème de dualité
merci
quelqu'un pourrait m'expliquer le problème de dualité
merci
2 réponses
Un exemple simple : tu veux imprimer des affiches sur du papier.
Problème primal : maximiser le nombre d'affiches imprimées.
Problème dual : minimiser la quantité de papier utilisée pour imprimer.
Remarque : je ne garantis pas que l'exemple soit formellement correct, mais si tu comprends le principe c'est le but. Tu pourras trouver plus rigoureux sur Wikipédia.
Problème primal : maximiser le nombre d'affiches imprimées.
Problème dual : minimiser la quantité de papier utilisée pour imprimer.
Remarque : je ne garantis pas que l'exemple soit formellement correct, mais si tu comprends le principe c'est le but. Tu pourras trouver plus rigoureux sur Wikipédia.
par exemple, j'ai cet exemple:
min z= 3x1 - 3x2 +x3 - 6x4
sujet de: x1+ x2 + x3+ x4=1
x1- 3x2 + 2x4 >=5
x1, x4 appartient a R
x2, x3 >=0
dual:
max z =y1 +y2
sujet de: y1+y2 =3
y1 - 3y2 <= -3
y1 <=1
y1 +2y2 = -6
y1 appartient a R
y2>=0
je n'ai pas compris comment la transformation s'est faite???
min z= 3x1 - 3x2 +x3 - 6x4
sujet de: x1+ x2 + x3+ x4=1
x1- 3x2 + 2x4 >=5
x1, x4 appartient a R
x2, x3 >=0
dual:
max z =y1 +y2
sujet de: y1+y2 =3
y1 - 3y2 <= -3
y1 <=1
y1 +2y2 = -6
y1 appartient a R
y2>=0
je n'ai pas compris comment la transformation s'est faite???
Je ne suis pas tout à fait d'accord avec tes symboles =, normalement on travaille avec la forme canonique, de sorte que l'on ait toujours <= pour les maximisations, et >= pour les minimisations, il ne doit pas y avoir de signes = qui sont ambiguës. De plus tous les x devraient êtres positifs, et les y réels.
En ce qui concerne les valeurs il faut lire les lignes en colonnes, et les colonnes en lignes :
Remarque : en général on parle plutôt de primal pour le programme à maximiser, et de dual pour le programme à minimiser. Toi tu as l'inverse, peut-être qu'il faudrait alors mettre xi sur R, et yj sur R+.
En ce qui concerne les valeurs il faut lire les lignes en colonnes, et les colonnes en lignes :
Primal x1+x2+x3+x4 >= 1 +1 +1 +1 +1 >= +1 x1-3x2+2x4 >= 5 +1 -3 +0 +2 >= +5 min z=3x1-3x2+x3-6x4 +3 -3 +1 -6 = z x1,x2,x3,x4 sur R+ Dual +1 +1 <= +3 y1+y2 <= 3 +1 -3 <= -3 y1-3y2 <= -3 +1 +0 <= +1 y1 <= 1 +1 +2 <= -6 y1+2y2 <= -6 +1 +5 = z max z = y1+5y2 y1,y2 sur R
Remarque : en général on parle plutôt de primal pour le programme à maximiser, et de dual pour le programme à minimiser. Toi tu as l'inverse, peut-être qu'il faudrait alors mettre xi sur R, et yj sur R+.
Remarque : concernant les signes des x et des y, et sur les opérateurs = sur lesquels j'avais de gros doutes, j'ai vérifié et en fait c'est bon ;-)
La variable yj du dual est réelle si et seulement si on a un signe = sur la contrainte j du primal.
De même on a un signe = sur la contrainte i du dual si et seulement si la variable xi du primal est réelle.
Du coup on a bien comme tu le mettait :
La variable yj du dual est réelle si et seulement si on a un signe = sur la contrainte j du primal.
De même on a un signe = sur la contrainte i du dual si et seulement si la variable xi du primal est réelle.
Du coup on a bien comme tu le mettait :
Primal x1 + x2 + x3 + x4 = 1 (y1 sur R ) x1 - 3x2 + 2x4 >= 5 (y2 sur R+) Dual y1 + y2 = 3 (x1 sur R ) y1 - 3y2 <= -3 (x2 sur R+) y1 <= 1 (x3 sur R+) y1 + 2y2 = -6 (x4 sur R )