Probleme liniaire : dualite

Résolu
leen.net Messages postés 247 Statut Membre -  
KX Messages postés 19031 Statut Modérateur -
Bonjour,

quelqu'un pourrait m'expliquer le problème de dualité
merci

2 réponses

  1.
    KX Messages postés 19031 Statut Modérateur 3 020
     
    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.
    0
  2. leen.net Messages postés 247 Statut Membre 13
     
    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???
    0
    1. KX Messages postés 19031 Statut Modérateur 3 020
       
      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 : 

      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+.
      0
    2. KX Messages postés 19031 Statut Modérateur 3 020
       
      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 : 

      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 )
      0