Recherche Opérationnelle – Optimisation Série 5

Exercice 1
On considère le problème (P) suivant :
Min(2 x1  3 x 2  x 3 )

 x1  x 2  x 3  10
( P)
2 x1  x 2  x 3  15
 x i  0 i  1,2,3

1/ donner toutes les bases de (P)
2/ Donner toutes les solutions admissibles de base de (P)

Exercice 2
Considérons le problème linéaire (P) suivant :

Max ( 5 x1  2 x 2 )

 3 x1  4 x 2  12

( P) 2 x1  x 2  14
 x x 4
 1 2
 x1  0 ; x 2  0

1/ Représenter graphiquement le domaine admissible du problème (P), donner l’ensemble des

solutions admissibles de bases et trouver la solution optimale.
2/ Retrouver ce résultat en utilisant la méthode du simplexe (méthode des tableaux)

Exercice 3
On considère le problème linéaire suivant :
max(5 x1  4 x 2  3x 3 )

2 x1  3x 2  x 3  5
(P) 4 x1  x 2  2 x 3  11
3 x  4 x  2 x  8
 1 2 3
 x i  0 i  1,2,3
1/ En prenant x1  1, x 2  1, x 3  0 a-t-on une solution
admissible de base ? Si la réponse est non,
expliquer pourquoi, si la réponse est oui donner la base correspondante.
2/ Résoudre (P) par la méthode du simplexe (méthode des tableaux).

Exercice 4
On considère un problème linéaire dans lequel on cherche à maximiser une foncion f(x). Soit
D le domaine admissible.
1/ Monter que si f(x1) > f(x2) alors pour tout x dans l’intervalle [x1,x2] on a f(x) > f(x2)
2 : Déduire que, pour un programme linéaire, un maximum local est maximum global.