MIAGE M1 Recherche Opérationnelle 1 TD8: le 5/11/2008

On considère le programme linéaire:

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
x_{1} ≥ 0
x_{2} ≥ 0
x_{3} ≥ 0
x_{4} ≥ 0

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?

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

4. Effectuer le changement de variable qui met ce programme auxiliaire dans la forme où (0, 0, 0 ⋯, 0) est une solution réalisable. Résolvez ce nouveau programme en utilisant Interactif ; quelle est la solution du programme de base trouvée?

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 une solution optimale du programme primal?

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