Devoir à la maison
corrigé
Méthode simplexe
Exercice 1
A) Résoudre avec la méthode du simplexe primal le problème suivant :
Max
z
2
cs
..
x
1
x
1
2
x
2
x
2
3
x
x
3
3
6
2
x
x
1
x
1
2
xxx
,
1
2
x
,
3
24
x
3
0
9
(
P
1
)
Réponse :
#1
e1
e2
e3
z
x1
-1
1
1
-2
x2
2
1
-1
-1
x3
1
0
1
-3
e1
1
0
0
0
e2
0
1
0
0
e3
0
0
1
0
x3 entre et e1 sort Li*=L1← L1 / 1. Ensuite,
L2← L2 - 0 × L1, L3← L3 - 1 × L1, Lz← Lz + 3 × L1
#2
x3
e2
e3
z
x1
-1
1
2
-5
x2
2
1
-3
5
x3
1
0
0
0
e1
1
0
-1
3
e2
0
1
0
0
e3
0
0
1
0
x1 entre et e3 sort Li*=L3← L3 / 2. Ensuite,
L1← L1 + 1 × L3, L2← L2 - 1 × L3, Lz← Lz + 5 × L1
b
6
24
9
0
b
6
24
3
18
6
-
9
L1
L2
L3
Lz
-
24
3/2
#3
x3
e2
x1
z
x1
0
0
1
0
x2
1/2
5/2
-3/2
-5/2
x3
1
0
0
0
e1
1/2
1/2
- 1/2
1/2
e2
0
1
0
0
e3
½
- ½
½
5/2
b
15/2
45/2
3/2
51/2
15
9
-
x2 entre et e2 sort Li*=L2← L2 × 2/5. Ensuite,
L1← L1 – 1/2 × L2, L3← L3 + 3/2 × L2, Lz← Lz + 5/2 × L2
#4
x3
x2
x1
z
x1
0
0
1
0
x2
0
1
0
0
x3
1
0
0
0
e1
2/5
1/5
- 1/5
1
e2
- 1/5
2/5
3/5
1
e3
3/5
- 1/5
1/5
2
b
3
9
15
48
Solution de Base Réalisable (SBR) optimale (ligne z 0)
x
B
x
x
3
2
x
1
3
9
15
,
x
L
e
1
e
e
3
2
0
0
0
et
*
z
48
Remarque 1 : les commentaires entre les tableaux sont facultatifs si l’étudiant peut
garantir un calcul sans fautes. Dans le cas contraire, un minimum de commentaires
permet de montrer une bonne compréhension de la méthode.
Remarque 2 : l’étudiant peut vérifier l’exactitude de son calcul en recalculant z* en
revenant à son expression :
339
2
(ok)
48
15
3
2
x
x
z
*
*
x
1
*
2
*
3
B) Résoudre avec les méthodes du simplexe en deux phases et du simplexe dual le
problème suivant :
Max
z
2
cs
..
x
3
x
Publicité
x
1
2
x
2
x
1
x
2
x
3
2
(2
10
x
1
4
x
3
)2
3
4
x
1
x
1
2
xxx
,
1
2
x
,
3
4
2
x
3
0
(
P
2
)
Méthode 1 :
Simplexe dual
x1
-1
1
1
-2
-
x2
2
0
-1
1
-
e2
#1
0
e1
1
e2
0
e3
0
z
-
Lz/Li*
e2 sort et x3 entre Li*=L2← L2 / -4. Ensuite,
L1← L1 - 2 × L2, L1← L1 - 2 × L2, Lz← Lz + L2
x3
2
-4
2
-1
1/4
e1
1
0
0
0
-
b
10
-2
4
0
e3
0
0
1
0
-
L1
L2
L3
Lz
#2
e1
x3
e3
z
x1
- 1/2
- 1/4
3/2
-9/4
x2
2
0
-1
1
x3
0
1
0
0
e1
1
0
0
0
e2
1/2
- 1/4
1/2
- 1/4
e3
0
0
1
0
b
9
1/2
3
1/2
-
-
2
Vecteur b positif On revient au simplexe primal
x1 entre et e3 sort Li*=L3← L3 × 2/3. Ensuite,
L1← L1 +1/2 × L3, L2← L2 + 1/4 × L3, Lz← Lz + 9/4 × L3
#3
e1
x3
x1
z
x2
x1
0 5/3
0
- 1/6
- 2/3
1
0
- 1/2
e2
2/3
- 1/6
1/3
1/2
x2 entre et e1 sort Li*=L1← L1 × 3/5. Ensuite,
L2← L2 +1/6 × L1, L3← L3 + 2/3 × L1, Lz← Lz + 1/2 × L1
e1
1
0
0
0
x3
0
1
0
0
e3
1/3
1/6
2/3
3/2
#4
x2
x3
x1
z
x1
0
0
1
0
x2
1
0
0
0
x3
0
1
0
0
e1
3/5
1/10
2/5
2/7
e2
2/5
-1/10
3/5
2/3
e3
1/5
1/5
4/5
8/5
Méthode 2 :
phase 1
x1
-1
-1
1
0
1
#1
e1
a1
e3
z'
z'
Méthode du simplexe en 2 phases
x2
2
0
-1
0
0
x3
2
4
2
0
-4
e1
1
0
0
0
0
e2
0
-1
0
0
1
e3
0
0
1
0
0
b
10
1
2
5
b
6
2
6
8
a1
0
1
0
1
0
6
-
-
5
0,5
2
b
10
2
4
0
-2
Rq (correction du tableau): la ligne z’ a été recalculée selon la formule
Lz’← Lz’ - L2 (qui est une transformation linéaire sans aucun impact dur la
définition du problème) pour que la variable de base a1 admette une colonne
valide (un seul « 1 » et des « 0 » partout). L’ancienne ligne z’ peut être
barrée.
x3 entre et a1 sort Li*=L2← L2 /4. Ensuite,
L1← L1 -2 × L2, L3← L3 -2 × L2, Lz’← Lz’ +4 × L2 (calcul de z’
facultatif si aucune variables artificielles dans la base: des 0 partout)
#2
e1
x3
e3
z'
x1
- 1/2
- 1/4
3/2
0
x2
2
0
-1
0
x3
0
1
0
0
e1
1
0
0
0
e2
1/2
- 1/4
1/2
0
e3
0
0
1
0
a1
-
-
-
-
b
9
1/2
3
0
-
-
2
phase 2
#3
e1
x3
Publicité
e3
z
z
x1
- 1/2
- 1/4
3/2
-2
-9/4
x2
2
0
-1
1
1
x3
0
1
0
-1
0
e1
1
0
0
0
0
e2
1/2
- 1/4
1/2
0
- 1/4
e3
0
0
1
0
0
b
9
1/2
3
0
1/2
-
-
2
Rq (correction du tableau): la ligne z a été recalculée selon la formule Lz←
Lz’ + L2 pour que la variable de base x3 admette une colonne valide.
L’ancienne ligne z peut être barrée.
x1 entre et e3 sort Li*=L3← L3 × 2/3. Ensuite,
L1← L1 +1/2 × L3, L2← L2 +1/4 × L3, Lz’← Lz’ +9/4 × L3
#4
e1
x3
x1
z
x1
0
0
1
0
x2
5/3
- 1/6
- 2/3
- 1/2
e2
2/3
- 1/6
1/3
1/2
x2 entre et e1 sort Li*=L1← L1 × 3/5. Ensuite,
L2← L2 +1/6 × L1, L3← L3 +2/3 × L1, Lz’← Lz’ +1/2 × L1
x3
0
1
0
0
e1
1
0
0
0
e3
1/3
1/6
2/3
3/2
b
10
1
2
5
6
-
-
#5
x2
x3
x1
z
x1
0
0
1
0
x2
1
0
0
0
x3
0
1
0
0
e1
3/5
1/10
2/5
2/7
e2
2/5
-1/10
3/5
2/3
e3
1/5
1/5
4/5
8/5
b
6
2
6
8
SBR optimale (ligne z 0)
e
1
e
e
3
2
0
0
0
et
*
z
8
x
B
x
x
2
3
x
1
2
6
6
,
x
L
Exercice 2
Résoudre avec la méthode du simplexe en deux phases le problème suivant :
x
1
2
x
2
x
2
3
x
x
3
3
6
Max
z
2
cs
..
x
1
x
3
3
x
x
1
2
xxx
,
1
2
,
3
12
2
x
3
0
(
P
1
)
6
3
6
Réponse (les tableaux):
phase 1
b
6
3
12
0
-3
3
3
3
3
0
9
18
e1
a1
e3
z'
z'
e1
x3
e3
z'
phase 2
e1
x3
e3
z
z
e2
x3
e3
z
e2
x3
x1
z
x2
x3
x1
z
x1
-1
0
1
0
0
x1
-1
0
1
0
x1
-1
0
1
-2
-2
x1
-1
-1
3
-5
x2
2
0
-1
0
0
x2
2
0
-1
0
x2
2
0
-1
-1
-1
x2
2
2
-5
5
x3
1
1
Publicité
2
0
-1
x3
0
1
0
0
x3
0
1
0
-3
0
x3
0
1
0
0
e1
1
0
0
0
0
e1
1
0
0
0
e1
1
0
0
0
0
e1
1
1
-2
3
e2
0
-1
0
0
1
e2
1
-1
2
0
e2
1
-1
2
0
-3
e2
1
0
0
0
e3
0
0
1
0
0
e3
0
0
1
0
e3
0
0
1
0
0
e3
0
0
1
0
a1
0
1
0
1
0
b
3
3
6
0
b
3
3
6
0
9
b
3
6
0
18
x1
0
0
1
0
x2
1/3
1/3
-5/3
-10/3
x3
0
1
0
0
e1
1/3
1/3
- 2/3
- 1/3
e2
1
0
0
0
e3
1/3
1/3
1/3
5/3
x1
0
0
1
0
x2
1
0
0
0
x3
0
1
0
0
e1
1
0
1
3
e2
3
-1
5
10
e3
1
0
2
5
b
3
6
0
18
b
9
3
15
48
Exercice 3
Résoudre le problème suivant :
(
P
)
z
3
x
1
2
x
2
4
x
3
Max
..
cs
x
1
x
2
1
x
1
2
x
2
x
2
3
x
2
3
x
2
xxx
2
1
,
,
3
4
3
7
x
3
7
0
Réponse :
#1
e1
e2
e3
z
x1
1
2
2
-3
x2
1
3
1
-2
x3 entre et e1 sort Li*=L1← L1 /2. Ensuite,
L2← L2 -0 × L1, L3← L3 -3 × L1, Lz← Lz +4 × L1
x3
2
0
3
-4
e2
0
1
0
0
e1
1
0
0
0
e3
0
0
1
0
2
b
4
7
7 7/3
0
#2
x3
e2
e3
z
x1
1/2
2
1/2
-1
x2
1/2
3
- 1/2
0
x3
1
0
0
0
e1
½
0
-3/2
2
E2
0
1
0
0
e3
0
0
1
0
x1 entre et e3 sort Li*=L3← L3 ×2. Ensuite,
L1← L1 -1/2 × L3, L2← L2 -2 × L3, Lz← Lz + L3
4
b
2
7 7/2
1
8
2
#3
x3
e2
x1
z
x1
0
0
1
0
x2
1
5
-1
-1
x2 entre et e2 sort Li*=L2← L2 /5. Ensuite,
L1← L1 -1× L2 L3← L3 –(-1) × L2, Lz← Lz + L2
e1
2
6
-3
-1
E2
0
1
0
0
x3
1
0
0
Publicité
0
e3
-1
-4
2
2
b
1
3
2
10
1
3/5
#4
x3
x2
x1
z
e1
4/5
6/5
-9/5
1/5
SBR optimale (ligne z positive ou nulle)
x3
1
0
0
0
x1
0
0
1
0
x2
0
1
0
0
e2
- 1/5
1/5
1/5
1/5
e3
- 1/5
- 4/5
6/5
6/5
b
2/5
3/5
13/5
63/5
x
B
x
x
3
2
x
1
2
5
3
5
13
5
,
x
L
e
1
e
e
2
3
0
0
0
et
*
z
53
6,10
5
Exercice 4
Résoudre le problème suivant :
(
P
)
Max
..
cs
x
1
x
1
z
2
x
1
x
2
3
x
3
x
3
6
x
1
2
x
x
2
2
24
x
2
x
12
3
2
xxx
,
2
1
,
0
3
Réponse (tableaux) :
6
-
6
24
0
18
9
x1
-1
1
1
-2
x1
-1
1
3
-5
x2
2
1
-1
-1
x2
2
1
-5
5
x3
1
0
2
-3
x3
1
0
0
0
e1
1
0
0
0
e1
1
0
-2
3
e2
0
1
0
0
e2
0
1
0
0
e3
0
0
1
0
e3
0
0
1
0
x2
x1
0
1/3
0 8/3
1
-5/3
0 -10/3
x1
0
0
1
0
x2
0
1
0
0
x3
1
0
0
0
x3
1
0
0
0
e1
1/3
2/3
- 2/3
- 1/3
e1
1/4
1/4
- 1/4
1/2
e3
e2
1/3
0
- 1/3
1
0
1/3
0 5/3
e2
- 1/8
3/8
5/8
5/4
e3
3/8
- 1/8
1/8
5/4
b
6
24
12
0
b
6
24
0
18
b
6
24
0
18
b
3
9
15
48
e1
e2
e3
z
x3
e2
e3
z
x3
e2
x1
z
x3
x2
x1
z