Master 1 MIAGE Recherche Opérationnelle 1 TD6: le 9/11/2006

On considère le programme linéaire:

x_{1} >= 0
x_{2} >= 0
x_{3} >= 0
x_{4} >= 0
10x_{1} − 10x_{2} − 20x_{3} + 50x_{4} <= −100
−50x_{1} + 6x_{2} − 40x_{3} <= −50
30x_{1} + 5x_{2} + 40x_{3} + 5x_{4} <= 180
20x_{1} − 25x_{2} + 10x_{3} − 4x_{4} <= −300

fonction objective z = − 10x_{1} − 5x_{2} − 12x_{3} − 8x_{4} à maximiser.

1. Donner le dual du programme linéaire.

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

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

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

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.

6. En utilisant le même programme, résolvez le program initial.

(a) D’où vient la fonction objective du début de la première itération?

(b) D’où vient la fonction objective du début de la deuxième phase?