FSJES Ain sebaa S6 - Gestion - Recherche Opérationnelle 2017/2018

Série de TD 2 - Méthode du simplexe

Exercice 1
Pour chacun des programmes linéaires suivants :
 Donner la forme standard en utilisant les variables d'écart suggérées.
 Dresser le tableau initial de la méthode simplexe.
 Déterminer le premier pivot.
max Z = 22x1 + 32x2 + 25x3 max Z = 346x1 + 210x2 + 158x3 min Z = −3x1 + 10x2 + 8x3
(e1 ) 3x1 + 4x2 ≤ 18 (e1 ) 25x1 + 42x2 + 28x3 ≤ 210 (e1 ) 5x1 + 12x2 + 6x3 ≤ 20
(e2 ) 5x1 + 2x2 + 1x3 ≤ 27 (e2 ) 36x1 − 26x2 + 54x3 ≤ 390 (e2 ) 2x1 + 2x2 + 2x3 ≥ 3
(e3 ) 2x1 + 6x2 − 3x3 ≤ 15 (e3 ) 42x1 + 34x2 − 61x3 ≤ 345 (e3 ) x1 + 4x2 + 5x3 ≤ 19
(e4 ) 4x1 − 1x2 + 5x3 ≤ 12 (e4 ) 65x1 − 64x2 + 86x3 ≤ 541 (e4 ) 3x2 + 4x3 ≤ 15
x1 , x2 , x3 ≥ 0 x1 , x2 , x3 ≥ 0 x1 , x2 , x3 ≥ 0

Exercice 2
Compléter la 1ère colonne (Base) et discuter la nature des tableaux suivants en justiant
(réalisable, optimal, non borné, dégénéré, non réalisable, innité de solutions optimales) :
T1
Base x1 x2 x3 x4 x5 s.m
0 -1 0 1 -1/4 3
0 0 1 0 1 4
1 -1/3 0 0 4 0
−z 0 3/4 0 0 -3/4 -9
T2
Base x1 x2 x3 x4 x5 s.m
1 0 1 0 0 4
0 1 0 1/2 0 6
3 0 0 −1 1 8
−z -3 0 0 −5/2 0 −30

T3
Base x1 x x x s.m
0 1 1 1 9
2 3 4

1 -3 -1 0 5
−z 0 0 -1 0 -7
T4
Base x1 x2 e1 e2 e3 s.m
0 0 1 1/3 −1/3 2
0 1 0 1/2 0 -7
1 0 0 −1/3 1/3 2
−z 0 0 0 −3/2 −1 −36

Département de Statistiques et Mathématiques Appliquées à l'Économie et à la Gestion (SMAEG) 1

FSJES Ain sebaa S6 - Gestion - Recherche Opérationnelle 2017/2018
Exercice 3
On donne le premier et le dernier tableau d'un programme linéaire. On demande de préciser le
programme de maximisation que les deux tableaux sont censés résoudre, et sa solution optimale.
Tableau initial :
a b c d e f g
5 3 9 1 0 0 0 12,4
6 4 7 0 1 0 0 14,5
2 9 8 0 0 1 0 9,5
3 12 4 0 0 0 1 13,6
3 4 2 0 0 0 0 0
Tableau nal :
a b c d e f g
0 0 157/46 1 -39/46 1/23 0 239/460
1 0 31/46 0 9/46 -2/23 0 925/460
0 1 17/23 0 -1/23 3/23 0 140/230
0 0 -317/23 0 -3/46 -30/23 1 121/460
0 0 -137/46 0 -19/46 -6/23 0 -3895/460
Exercice 4
Résoudre

à l'aide de la méthode du simplexe

les programmes linéaires suivants

:

 max z = 500x1 + 300x2 
 max z = 4x1 + 5x2 
 max z = 3x1 + 3x2 + 4x3
 20x1 + 10x2 ≤ 2000  1 + x2 ≤ 8
2x  x1 + x2 + 2x3 ≤ 4

 
 

(P1 ) 10x1 + 45x2 ≤ 5400 (P2 ) x1 + 2x2 ≤ 7 (P3 ) 2x1 + 3x3 ≤ 5
40x1 + 30x2 ≤ 4800 x2 ≤ 3 2x1 + x2 + 3x3 ≤ 7

 
 


 
 

x1 , x2 ≥ 0 x1 , x2 ≥ 0 x1 , x2 , x3 ≥ 0
  

 

 max z = x1 + 3x2 
 min z = −x1 − 2x2
 x1 + x2 ≤ 14  −3x1 + 2x2 ≤ 2

 

(P4 ) −2x1 + 3x2 ≤ 12 (P5 ) −x1 + 2x2 ≤ 4
2x − x2 ≤ 12 x1 + x2 ≤ 5
 
 1

 

 
x1 , x2 ≥ 0 x1 , x2 ≥ 0


Exercice 5
On considère les deux

programmes linéaires : 

 max z = 2x1 + x2 
 max z = 3x1 + 2x2
2x1 + x2 ≤ 8 3x1 + 4x2 ≤ 6
 
(P1 ) (P2 )

 x1 + x2 ≥ 5 
 2x1 − 3x2 = 12
x1 , x2 ≥ 0 x1 , x2 ≥ 0
 

1. En appliquant la méthode du grand M, résoudre (P ) et (P ). 1 2

2. En déduire que (P ) admet une innité de solutions optimales et que (P ) est non réali-
sable.
1 2

Département de Statistiques et Mathématiques Appliquées à l'Économie et à la Gestion (SMAEG) 2