Centre universitaire de Mila Année universitaire 2022/2023
Matière : Programmation linéaire 3° Année informatique
Série de TD N°2 (Initiation de l’algorithme du simplexe, la méthode des deux phases, la
méthode big-M)
Exercice 1. Résoudre avec l’algorithme du simplexe en deux phases le programme linéaire
(P).
{
Max( Z)=2 x 1+3 x 2+ x 3
x 1+ x 2+ x 3≤ 40
P≡ 2 x 1+ x 2−x 3 ≥10
−x 2+ x 3 ≥ 10
x1, x2, x3≥0
1) forme standard.
{
Max (Z)=2 x 1+3 x 2+ x 3
x 1+ x 2+ x 3+ x 4=40
P ≡ 2 x 1+ x 2−x 3 – x 5=10
−x 2+ x 3 – x 6=10
x1, x2,x 3, x4 ,x 5,x 6≥0
2) forme artificielle.
{
Max (Z)=2 x 1+3 x 2+ x 3
x 1+ x 2+ x 3+ x 4=40
P ≡ 2 x 1+ x 2−x 3 – x 5+ x 7=10
−x 2+ x 3 – x 6+ x 8=10
x1, x2,x 3, x4 ,x 5, x6≥0
2. Phase I :
2.1 La table initiale
x1↓ x2 x3 x4 x5 x6 x7 x8 bi
x4 1 1 1 1 0 0 0 0 40
←x7 2 1 -1 0 -1 0 1 0 10
x8 0 -1 1 0 0 -1 0 1 10
W 2 0 0 0 -1 -1 0 0 20
Z 2 3 1 0 0 0 0 0 0
1.2 Première itération
x1 x2 x3↓ x4 x5 x6 x7 x8 bi
x4 0 1/2 3/2 1 1/2 0 -1/2 0 35
x1 1 1/2 -1/2 0 -1/2 0 1/2 0 5
←x8 0 -1 1 0 0 -1 0 1 10
W 0 -1 1 0 0 -1 -1 0 10
Z 0 2 2 0 1 0 -1 0 -10
1.3 Deuxième itération
x1 x2 x3 x4 x5 x6 x7 x8 bi
x4 0 2 0 1 1/2 3/2 -1/2 -3/2 20
x1 1 0 0 0 -1/2 -1/2 1/2 1/2 10
x3 0 -1 1 0 0 -1 0 1 10
W 0 0 0 0 0 0 -1 -1 0
Z 0 4 0 0 1 2 -1 -2 -30
La fonction objective atteint la valeur nulle et toutes les variables artificielles sont exclues de
la base, donc on passe à la deuxième phase considérant la solution initiale retournée par la
première.
2
II. Phase II.
II.1 Table initiale
x1 x2↓ x3 x4 x5 x6 bi
←x4 0 2 0 1 1/2 3/2 20
x1 1 0 0 0 -1/2 -1/2 10
x3 0 -1 1 0 0 -1 10
Z 0 4 0 0 1 2 -30
II.2 Première itération
x1 x2 x3 x4 x5 x6 bi
x2 0 1 0 1/2 1/4 3/4 10
x1 1 0 0 0 -1/2 -1/2 10
x3 0 0 1 1/2 1/4 -1/4 20
Z 0 0 0 -2 0 -1 -70
Tous les coefficients dans la ligne de la fonction objective sont négatifs ou nuls donc la
solution est optimale avec :
x1*=10, x2*=10, x3*=20, x4*=x5*=x6*=0, Z*=-Z=70.
3
Exercice 2. Résoudre avec la méthode du simplexe en deux phases :
Maxz =x1-x2+x3
{
2 x 1−x 2−2 x 3 ≤ 4
2 x 1−3 x 2+ x 3 ≤−5
−x 1+ x 2−2 x 3 ≤−1
x1, x2, x3≥0
1) forme standard.
Maxz =x1-x2+x3
{
2 x 1−x 2−2 x 3+ x 4=4
−2 x 1+ 3 x 2−x 3−x 5=5
x 1−x 2+ 2 x 3−x 6=1
x1, x2,x 3, x4 ,x 5,x 6≥0
1.1 programme artificiel
Maxz =x1-x2+x3
Max w =-w1-w2
{
2 x 1− x 2−2 x 3+ x 4=4
−2 x 1+3 x 2−x 3−x 5+w 1=5
x 1−x 2+2 x 3−x 6+ w 2=1
x 1, x 2 , x 3 , x 4 , x 5 , x 6 ≥ 0
w 1 ≥0 , w 2≥ 0.
2. Phase I :
2.1 La table initiale
X1 X2 X3 X4 X5 X6 W1 W2 bi
X4 2 -1 -2 1 0 0 0 0 4
La ligne de
W est
W1 -2 3 -1 0 -1 0 1 0 5
W2 1 -1 2 0 0 -1 0 1 1
W -1 2 1 0 -1 -1 0 0 6
4
Z 1 -1 1 0 0 0 0 0 0
calculée en faisant la somme : LW=LW+Lw1+Lw2 afin d’exprimer W uniquement par les
variables de base.
2.2 Première itération :
X1 X2 X3 X4 X5 X6 W1 W2 bi
X4 4/3 0 -7/3 1 -1/3 0 1/3 0 17/3
X2 -2/3 1 -1/3 0 -1/3 0 1/3 0 5/3
W2 1/3 0 5/3 0 -1/3 -1 1/3 1 8/3
W 1/3 0 5/3 0 -1/3 -1 -2/3 0 8/3
Z 1/3 0 2/3 0 -1/3 0 1/3 0 5/3
2.3
Deuxième itération
X1 X2 X3 X4 X5 X6 W1 W2 bi
X4 9/5 0 0 1 -4/5 -7/5 4/5 7/5 47/5
X2 -3/5 1 0 0 -2/5 -1/5 2/5 1/5 11/5
X3 1/5 0 1 0 -1/5 -3/5 1/5 3/5 8/5
W 0 0 0 0 0 0 -1 -1 0
Z 1/5 0 0 0 -1/5 2/5 1/5 2/5 3/5
5
3. Phase II
3.1 Table initiale
X1 X2 X3 X4 X5 X6 bi
X4 9/5 0 0 1 -4/5 -7/5 47/5
X2 -3/5 1 0 0 -2/5 -1/5 11/5
X3 1/5 0 1 0 -1/5 -3/5 8/5
Z 1/5 0 0 0 -1/5 2/5 3/5
Tous les valeurs dans la colonne du pivot sont négatives ou nulles alors le problème admit une
solution non-bornée.
Exercice 3. Résoudre le programme linéaire par la méthode Big M.
Min z =3x1+4x2+5x3.
{
x 1+2 x 2+3 x 3 ≥ 5
2 x 1+2 x 2+ x 3 ≥ 6
¿ x 1 , x 2 , x 3≥ 0
Le M-problème
Max Z=-3x1-4x2-5x3-mw1-mw2
{
x 1+ 2 x 2+3 x 3−x 4 +w 1=5
2 x 1+ 2 x 2+ x 3−x 5+ w 2=6
¿ x 1 , x 2 , x 3 , x 4 , x 5 , w 1 , w 2≥ 0
1) Tableau initial
x1 x2 x3 x4 x5 w1 w2 bi
w1 1 2 3 -1 0 1 0 5
6
w2 2 2 1 0 -1 0 1 6
Z -3+3m -4+4m -5+4m -m -m 0 0 11m
1ière itération
x1 x2 x3 x4 x5 w2 bi
x1 1/2 1 3/2 -1/2 0 0 5/2
w2 1 0 -2 1 -1 1 1
Z m-1 0 1-2m m-2 -m 0 M+10
2ième itération
x1 x2 x3 x4 x5 bi
x2 0 1 5/2 -1 +1/2 2
x1 1 0 -2 1 -1 1
Z’ 0 0 -1 -1 -1 11
7
Tous les coefficients dans la ligne de la fonction objective sont négatifs ou nuls alors la
solution est optimale avec :
x2*=2, x1*=1, Z*=-Z=-11
Exercice 4.
Max Z=12 x 1+15 x 2+10 x 3
{
x 1 + x 2+2 x 3 ≥ 10
15 x 1 +6 x 2−5 x3 ≤ 30
x 1 +3 x2 +5 x 3 ≤ 18
x 1 , x 2 , x3 ≥ 0
La méthode big-M :
La M-forme :
Max Z=12 x 1+15 x 2+10 x 3-m x 7
{
x 1 + x 2+ 2 x 3−x 4 + x 7 =10
15 x 1 +6 x 2−5 x3 + x 5=30
x 1 +3 x2 +5 x 3+ x6 =18
x1 , x 2 , x 3 , x 4 , x5 , x 6 , x 7 ≥ 0
Table initiale
vb x1 x2 X3↓ x4 X5 X6 X7 b
X7 1 1 2 -1 0 0 1 10
X5 15 6 -5 0 1 0 0 30
<-X6 1 3 5 0 0 1 0 18
Z 12+m 15+m 10+2m -m 0 0 0 10m
8
Première itération
vb x1↓ x2 x3 x4 X5 X6 X7 b
X7 3/5 -1/5 0 -1 0 -2/5 1 14/5
<-X5 16 9 0 0 1 1 0 48
X3 1/5 3/5 1 0 0 1/5 0 18/5
Z 10+3m/ 9-m/5 0 -m 0 -2-2m/5 0 -
5 36+14m/5
Deuxième
itération
vb x1↓ x2 x3 x4 X5 X6 X7 b
X7 0 -19/15 0 -1 -3/80 -7/16 1 1
X1 1 9/16 0 0 1/16 1/16 0 3
X3 0 39/80 1 0 -1/80 3/16 0 3
Z 0 54/16-43m/80 0 -m -10/16- -21/8- 0 -
3m/80 7m/6 66+m
Tous les
coefficients dans la ligne de la fonction objective sont négatifs ou nuls alors qu’on n’arrive
pas à exclure la variable artificielle x7 de la base donc, le problème n’admet pas de solution
réalisable.
