IUP MIAGE
IUP3 Recherche Opérationnelle 1
Corrigé de TD6: le 20/10/2004

On considère le programme linéaire:


x1
> =
0
x2
> =
0
x3
> =
0
x4
> =
0
10x1-10x2 -20x3+50x4
< =
-100
-50x1+6x2 -40x3
< =
-50
30x1+5x2 +40x3+5x4
< =
180
20x1-25x2+10x3-4x4
< =
-300

fonction objective z = -10x1-5x2-12x3-8x4 à maximiser.

  1. Donner le dual du programme linéaire.


    y1
    > =
    0
    y2
    > =
    0
    y3
    > =
    0
    y4
    > =
    0
    10y1-50y2 +30y3+20y4
    > =
    -10
    -10y1+6y2 +5y3-25y4
    > =
    -5
    -20y1-40y2 +40y3+10y4
    > =
    -12
    50y1+5y3-4y4
    > =
    -8

    fonction objective z = -100y1-50y2+180y3-300y4 à minimiser.

    ou


    y1
    > =
    0
    y2
    > =
    0
    y3
    > =
    0
    y4
    > =
    0
    -10y1+50y2 -30y3-20y4
    < =
    10
    10y1-6y2 -5y3+25y4
    < =
    5
    20y1+40y2 -40y3-10y4
    < =
    12
    -50y1-5y3+4y4
    < =
    8

    fonction objective z = 100y1+50y2-180y3+300y4 à maximiser.

  2. Quelle est une solution réalisable de base de ce programme dual qui est très facile à trouver (et quelle est sa base)?

    y1=y2=y3=y4=0 (base les variables d'écart y5, y6, y7, y8)

  3. Donner le programme linéaire auxiliaire qui sert à trouver une solution de base réalisable du programme initial.


    x1
    > =
    0
    x2
    > =
    0
    x3
    > =
    0
    x4
    > =
    0
    x5
    > =
    0
    10x1-10x2 -20x3+50x4 -x5
    < =
    -100
    -50x1+6x2 -40x3 -x5
    < =
    -50
    30x1+5x2 +40x3+5x4
    < =
    180
    20x1-25x2+10x3-4x4-x5
    < =
    -300

    fonction objective z = -x5 à maximiser.

  4. Quelle est une solution réalisable de base de ce programme auxiliaire qui est très facile à trouver (et quelle est sa base)? x1=x2=x3=x4=0,x5=300 (base x5 et les trois variables d'écart non-nulles x6, x7, x8; [noter que la dernière variable d'écart x9 est nulle.])

    Remarque La solution de ce programme auxiliaire est:

    base finale: 1 2 3 6 
    solution
    variable 1=0.987097
    variable 2=13.612903
    variable 3=2.058065
    variable 4=0.000000
    variable 5=0.000000
    pour un resultat de 0.000000

    Donc, on a trouvé une solution réalisable du programme initial (0.987097,13.612903,2.058065,0.000000) et cette solution est de base en tant que la solution des équations
    x4
    =
    0
    -50x1+6x2 -40x3
    =
    -50
    30x1+5x2 +40x3+5x4
    =
    180
    20x1-25x2+10x3-4x4
    =
    -300
    (les équations correspondant aux variables hors base de la solution trouvée, à savoir x4 et les variables d'écart des 3 dernières contraintes (x7, x8, x9); on jette le x5 qui n'avait rien à voir avec le programme de départ.)
  5. En utilisant le programme Interactif.exe, résolvez le programme dual par l'algorithme du simplexe et remarquez comment cet algorithme donne aussi la solution du programme initial.

    Le résultat final donné par le programme est:

      -0.044     1.000    -0.752     0.000     0.022     0.017     0.000     0.000     0.309
    0.389 0.000 -0.380 1.000 0.005 0.044 0.000 0.000 0.274
    25.663 0.000 -13.716 0.000 -0.831 -0.265 1.000 0.000 2.353
    -51.557 0.000 -3.477 0.000 -0.021 -0.176 0.000 1.000 6.902
    -14.601 0.000 -28.230 0.000 -2.699 -14.159 0.000 0.000
    Base est: 2 4 7 8

    base finale: 2 4 7 8
    solution
    variable 1=0.000000
    variable 2=0.309735
    variable 3=0.000000
    variable 4=0.274336
    pour un resultat de 97.787611


    et les quatre dernier éléments de la ligne ``coefficients de la fonction objective'' (ceux correspondant aux variables d'écart de ce programme dual) sont les valeurs d'une solution optimale du programme initial (multipliées par -1).



File translated from TEX by TTH, version 3.05.
On 8 Dec 2004, 15:17.