MIAGE M1 Recherche Opérationnelle 1 TD8: le 14/11/2007

On considère le programme linéaire:

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

fonction objective z = − 10x_{1} − 5x_{2} − 2x_{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, résolvez le programme dual par l’algorithme du simplexe.

6. Comment est-ce que les tableaux finals donnent aussi la solution du programme primal?

Envoyer à robson@labri.fr un mail avec TD8 dans le titre et avec vos réponses aux questions 2 et 6.