Centre universitaire de Mila Année universitaire 2023/2024
Matière : Programmation linéaire 3° Année informatique
Série de TD N°2 (Algorithme du simplexe)
Exercice 2
1) Résolution graphique
Les points extrêmes sont :O(0,0) )=> Zo=0; A(6, 0)=> ZA=6 α ; C(0,2) )=> Zc=2 ;
D(2,2) )=> Zd=2 α+2 ; …(2pts)
a) α <0, la solution optimale est Z*= Zc=2, x1*=0, x2*=2….(0.5)
b) α =0, solution multiple Z*= Zc= Zd=2….(0.5)
c) 0<α<1/2, la solution optimale est Z*= Zd=2 α+2 , x1*=2, x2*=2….(0.5)
d) α =1/2, solution multiple Z*= Za= Zd=3 ….(0.5)
e) α> 1/2, solution optimale Z*= Za= 6 α ….(0.5).
La résolution du P (-1,0 ) par la méthode du simplexe
La forme standard
Max Z(-1)=- x 1+ x 2
{
x1 +2 x 2+ x 3=6
x2 + x 4 =2
x1 , x 2 , x 3 , x 4 ≥ 0
vb x1 x2↓ x3 x4 b
X3 1 2 1 0 6
<-X4 0 1 0 1 2
Z 1 1 0 0 0
vb x1 x2↓ x3 x4 b
X3 1 2 1 -2 2
<-X2 0 1 0 1 2
Z -1 0 0 -1 -2
Z*=2, x3*2, x2*=2, x1*=x4*=0
Exercice 3
1) Le programme linéaire qui maximise la fonction Z est le suivant:
Max Z=x1-x2+x3
{
x 1+ x 2+ x 3 ≤ 8
x 2≤ 1
¿ x1,x 2,x 3≥0
1.1- La résolution du problème à l’aide de la méthode du simplexe :
a) la forme standard :
Max Z=x1-x2+x3
{
x 1+ x 2+ x 3+ x 4=8
x 2+ x 5=1
¿ x 1 , x 2 , x 3 , x 4 , x 5 ≥0
b) La table initiale
V.B x1 ↓ x2 x3 x4 x5 bi
←x 1 1 1 1 0 8
4
x5 0 1 0 0 1 1
Z 1 -1 1 0 0 0
b) Première itération
V.B x1 x2 x3 x4 x5 bi
x1 1 1 1 1 0 8
x5 0 1 0 0 1 1
Z 0 -2 0 -1 0 -8
Tous les coefficients dans la ligne de la fonction objective sont négatifs ou nuls alors la fonction Z est
maximale avec :
X1*=8, X2*=X3*=X4*=0, X5*=1 avec Z*=8.
2) Le programme linéaire qui minimise la fonction Z est le suivant:
Min Z=x1-x2+x3
2
{
x 1+ x 2+ x 3 ≤ 8
x 2≤ 1
¿ x1,x 2,x 3≥0
2.1 La résolution du problème à l’aide de la méthode du simplexe :
a) la forme standard :
Max W=Min -Z =-x1+x2-x3
{
x 1+ x 2+ x 3+ x 4=8
x 2+ x 5=1
¿ x 1 , x 2 , x 3 , x 4 , x 5 ≥0
b) La table initiale
V.B x1 x2 ↓ x3 x4 x5 bi
x4 1 1 1 1 0 8
←x 0 1 0 0 1 1
5
W -1 1 -1 0 0 0
b) Première itération
V.B x1 x2 x3 x4 x5 bi
x4 1 0 1 1 -1 7
X2 0 1 0 0 1 1
W -1 0 -1 0 -1 -1
Tous les coefficients dans la ligne de la fonction objective sont négatifs ou nuls alors la fonction W est
maximale avec :
X2*=1, X4*=7, X1*=X3*=X5*=0, avec MAXW=1⟹Min Z=1
Exercice 4
Max Z=4x1+12x2+3x3
{
x 1 ≤ 1000
x 2 ≤ 500
x 3 ≤ 1500
3 x 1+6 x 2+2 x 3 ≤ 1500
x1, x2, x3≥0
Forme standard
Max Z=4x1+12x2+3x3
3
{
x 1+ x 4=1000
x 2+ x 5=500
x 3+ x 6=1500
3 x 1+6 x 2+2 x 3+ x 7=1500
x 1 , x 2, x 3 ≥ 0
x4 ,x 5, x6≥0
Table initiale
v.b x1 x2 x3 x4 x5 x6 x7 bi
x4 1 0 0 1 0 0 0 1000
←x5 0 1 0 0 1 0 0 500
x6 0 0 1 0 0 1 0 1500
X7 3 6 2 0 0 0 1 6750
Z 4 3 12 0 0 0 0 0
1ere itération
v.b x1 ↓ x2 x3 x4 x5 x6 x7 bi
←x4 1 0 0 1 0 0 0 1000
x5 0 1 0 0 1 0 0 500
x6 0 0 1 0 0 1 0 1500
X7 3 0 2 0 -6 0 1 6750
Z 4 0 3 0 -12 0 0 -6000
2eme itération
v.b x1 x2 x3↓ x4 x5 x6 x7 bi
x1 1 0 0 1 0 0 0 1000
4
x2 0 1 0 0 1 0 0 500
x6 0 0 1 0 0 1 0 1500
←x7 0 0 2 -3 -6 0 1 750
Z 4 0 3 0 -12 0 0 -10000
3eme itération
v.b x1 x2 x3 x4 ↓ x5 x6 x7 bi
X1 1 0 0 1 0 0 0 1000
x2 0 1 0 0 1 0 0 500
←x6 0 0 0 3/2 3 1 -1/2 1500
x3 0 0 1 -3/2 -3 0 1/2 375
Z 0 0 0 1/2 -3 0 -3/2 -11125
4eme itération
v.b x1 x2 x3 x4 x5 x6 x7 bi
x1 1 0 0 0 -2 -2/3 -1/3 250
x2 0 1 0 0 1 0 0 500
x4 0 0 0 1 2 2/3 -1/3 750
x3 0 0 1 0 0 1 0 1500
Z 0 0 0 0 -4 -1/3 -4/3 -11500
5
Tous les coefficients dans la ligne de la fonction objective sont négatifs ou nuls alors, la
solution est optimale avec :
x1*=250, x2*=500, x3*=1500, x4*=750, x5*=x6*=x7*=0, Z*=-Z=11500.
Exercice 5 Résoudre avec la méthode du simplexe :
Max Z= 3x1+2x2+4x3
{
x 1+ x 2+2 x 3 ≤ 4
2 x 1+ 3 x 3 ≤5
2 x 1+ x 2+3 x 3 ≤ 7
x∧1 , x 2 , x 3 ≥ 0
1- La forme standard du PL :
Max Z= 3x1+2x2+4x3
{
x 1+ x 2+2 x 3+ x 3=4
2 x 1+3 x 3+ x 5=5
2 x 1+ x 2+3 x 3+ x 6=7
x∧1 , x 2 , x 3 , x 4 , x 5 , x 6 ≥ 0
2- Table initiale
v.b bi x1 x2 x3↓ x4 x5 x6
x4 4 1 1 2 1 0 0
←x5 5 2 0 3 0 1 0
x6 7 2 1 3 0 0 1
Z 0 3 2 4 0 0 0
3- Première itération
6
v.b bi x1 x2↓ x3 x4 x5 x6
←x4 2/3 -1/3 1 0 1 -2/3 0
x3 5/3 2/3 0 1 0 1/3 0
x6 2 0 1 0 0 -1 1
Z -20/3 1/3 2 0 0 -4/3 0
4- Deuxième itération
v.b bi x1↓ x2 x3 x4 x5 x6
x2 2/3 -1/3 1 0 1 -2/3 0
←x3 5/3 2/3 0 1 0 1/3 0
x6 4/3 1/3 0 0 -1 -1/3 1
Z -8 1 0 0 -2 0 0
5- Troisième itération
v.b bi x1 x2 x3 x4 x5 x6
x2 3/2 0 1 1/2 1 -1/2 0
x1 5/2 1 0 3/2 0 1/2 0
x6 1/2 0 0 -1/2 -1 -1/2 1
Z -21/2 0 0 -3/2 -2 -1/2 0
On constate que tous les coefficients dans la ligne de la fonction objective sont négatifs ou
nuls alors, la solution est optimale avec :
7
x1*=x1=5/2, x2*=x2=3/2, x6*=x6=3/2, x3*=x4*=x5*=0.
Z*=-Z=21/2.
Exercice 6.
Max z =-5x1+5x2+13x3
{
−x 1+ x 2+3 x 3 ≤ 20
12 x 1+ 4 x 2+10 x 3 ≤ 90
x 1 , x 2, x 3 ≥ 0
Max z =-5x1+x2+13x3
{
−x 1+ x 2+3 x 3+ x 4=20
12 x 1+ 4 x 2+10 x 3+ x 5=90
x1, x2, x3, x 4, x5≥0
1) Tableau initial :
v.b x1 x2 x3↓ x4 x5 Bi
←x4 -1 1 3 1 0 20
x5 12 4 10 0 1 90
Z -5 5 13 0 0 0
2) Première itération
v.b x1 X2↓ x3 x4 x5 Bi
←x3 -1/3 1/3 1 1/3 0 20/3
x5 46/3 2/3 0 -10/3 1 70/3
Z -2/3 2/3 0 -13/3 0 -260/3
2) Deuxième itération
8
v.b x1 x2 x3↓ x4 x5 Bi
x3 -1 1 3 1 0 20
x5 16 0 -2 -4 1 10
Z 0 0 -2 -5 0 -100
Tous les coefficients dans la ligne de la fonction objective sont négatifs ou nuls alors, la
solution est optimale avec :
x2*=x2=20, x5*=x5=10, x1*=x3*=x4*=0.
Z*=-Z=100
2- La nouvelle base en changeant le second membre de la contrainte n 1 :
B= ( xx 25) , A =( 14 01)
B AB-1= (−41 01)
( xx 25)=(−41 01) (3090)= (−30
30
) x5<0 Solution non admissible.
2.1 La solution du problème par l algorithme du simplexe.
. 1) Tableau initial :
v.b x1 x2 x3↓ x4 x5 Bi
x4 -1 1 3 1 0 30
←x5 12 4 10 0 1 90
Z -5 5 13 0 0 0
2) Première itération
v.b x1 X2↓ x3 x4 x5 Bi
x4 -4,6 -0,2 0 1 -0,3 3
x3 1,2 0,4 1 0 0,1 9
9
Z -20,6 -0.2 0 0 -1.3 -117
Tous les coefficients dans la ligne de la fonction objective sont négatifs ou nuls alors, la
solution est optimale avec :
x3*=x3=9, x4*=x4=3, x1*=x2*=x5*=0.
Z*=-Z=117.
L intervalle de validité de la base B= ( xx 25) :
(−41 01) (90b )=(−4 b+b 90)≥ ( 00) => b∈[0 , 22.5].
10