Réalisé par
:
EL BAHHAR KENZA
DRAB YOUSSEF
_GET 1_
Projet :
Algorithme du Simplexe
Qu’est-ce que l’algorithme du Simplexe ?
L'algorithme du simplexe est un algorithme de résolution des problèmes
d'optimisation linéaire. Il a été introduit par George Dantzig à partir de 1947.
C'est probablement le premier algorithme permettant de minimiser une
fonction sur un ensemble défini par des inégalités. De ce fait, il a beaucoup
contribué au démarrage de l'optimisation numérique. L'algorithme du simplexe
a longtemps été la méthode la plus utilisée pour résoudre les problèmes
d'optimisation linéaire.
Avant que l’algorithme du simplexe puisse être utilisé pour résoudre un programme linéaire,
ce programme linéaire doit être converti en un programme équivalent où toutes les
contraintes sont des équations et toutes les variables sont positives, utilisant cette
technique :
Forme d'inégalité Forme de la nouvelle variable
≥ - excès + artificielle
= + artificielle
≤ + écart
Si on considère un système d’équations à n variables et ݉ m équations où n≥m. Une solution
de base pour ce système est obtenue en considérant le sommet (0,0) comme solution de
base de départ et puis on définit les variables de base (V.B) et les variables hors base (V.H.B)
En ce qui suit, on cherche une solution de base meilleure, on pose tous les coefficients dans
un tableau de la manière suivante :
Exemple : Max Z= 4X1+ 3X2 sous les contraintes _qui sont écrits sous la forme
standard_ suivantes:
X1+ 3X2+ T1=40
2X1+ 5X2+ T2=90
X1 X2 T1 T2 R
T1 1 3 1 0 40
T2 2 5 0 1 90
Z 4 3 0 0 0
On fait le choix de la colonne pivot par le plus grand coefficient de la fonction économique
qui est égal à 4 dans cet exemple, et puis on cherche la ligne pivot on divisant chaque reste R
sur le coefficient équivalent de la colonne pivot, et puis la ligne pivot c’est celle qui a la plus
petite valeur positive qui détermine par la suite la variable entrante (qui correspond à la
colonne pivot) et la variable sortante (qui correspond à la ligne pivot)
Et puis on fait une actualisation du tableau. On divise la ligne pivot par le pivot et puis
chaque élément de la colonne pivot reçoit un 0 sauf le pivot et puis on calcule les autres
coefficients de la manière suivante :
aip j∗ai jp
a ij ← aij−
aip jp où ip est l’indice de la ligne pivot et jp est l’indice de la colonne pivot
Et puis, l’algorithme du Simplexe s’arrête si tous les coefficients des variables de la fonction
économique sont négatives ou nulles.
Programmation de l’algorithme du Simplexe par Matlab :
A=[2 1 1 0 0 26; 1 2 0 1 0 24; 1 1 0 0 1 14; 3 4 0 0 0 0 ];
n=2; //nombre des variables
m=3; // nombre des contraintes
OK=0; //la variable OK définit si la condition d’arrêt d’algorithme est vérifiée
while(OK==0)
//Step1: trouver la colonne pivot
max=A(m+1,1);
cp=1;
for j=2:n+m
if(A(m+1,j)>max)
max=A(m+1,j);
cp=j;
end
end
//Step2: trouver la ligne pivot
min=A(1,m+n+1)/A(1,cp);
lp=1;
for i=2:m
if(min>(A(i,m+n+1)/A(i,cp)))
lp=i;
min=A(i,m+n+1)/A(i,cp);
end
end
p=A(lp,cp);
//Step3: Actualiser la matrice par les nouveau coefficient sauf la ligne et la colonne pivot
for i=1:m+1
if(i~=lp)
for j=1:n+m+1
if(j~= cp)
max=A(i,cp)*A(lp,j);
A(i,j)=A(i,j)-A(i,cp)*A(lp,j)/p;
end
end
end
end
//Step4: diviser la ligne pivot par le pivot
for j=1:m+n+1
A(lp,j)=A(lp,j)/p;
End
//Step5: changer les éléments de la colonne pivot par des zéros sauf le pivot
for i=1:m+1
if(i~=lp)
A(i,cp)=0;
end
end
//Step6: test de la condition d’arrêt
max=A(m+1,1);
for j=2:m+n
if(A(m+1,j)>max)
max=A(m+1,j);
end
end
if(max<=0)
OK=1;
end
end
Optimisation du programme de l’algorithme du Simplexe
par Matlab :
Des fois, en utilisant la méthode de Simplexe, on se trouve dans des cas particuliers
comme si par exemple on a les coefficients de la fonction économique qui sont égaux. Le
choix de la colonne pivot ici n’aura pas d’effets sur le résultat final mais il se peut qu’on fasse
une ou des itérations de plus ce qui nous doit plus de temps.
Nous allons traiter ce cas, en essayant d’optimiser le premier programme écrit à choisir la
colonne pivot qui doit le moindre nombre d’itérations.
Exemple :
Max Z= 8X1+ 8X2 sous les contraintes _qui sont écrits sous la forme
standard_ suivantes :
3X1+ 4X2+ T1=360
5X1+ 2X2+ T2=320
2X1+ X2+ T3=130
X1 X2 T1 T2 T 3 R
T1 3 4 1 0 0 360
T2 5 2 0 1 0 320
T3 2 1 0 0 1 130
Z 8 8 0 0 0 0
Il existe une méthode pour choisir la colonne pivot qui doit moins d’itérations, moins de
temps, qui utilise les étapes suivantes :
Si on choisit la colonne pivot correspondante a X1 on aura le pivot égal à 5 car (320 /5
= 64 est le plus petit)
Et si on choisit le colonne pivot correspondante a X2 on aura le pivot égal à 4 car
(360/4 = 90 est le plus petit)
On compare entre les restes (64 et 90) et on prend la ligne pivot qui correspond au
plus grand des deux (c’est 90).
→Alors, la variable entrante c’est X2 et le pivot=4.
Programme optimisé de l’algorithme du Simplexe par
Matlab :
A=[3 4 1 0 0 360; 5 2 0 1 0 320; 2 1 0 0 1 130 ; 8 8 0 0 0 0 ];
n=2;
m=3;
OK=0; //pour la condition d’arrêt
//Seulement pour l’affichage des valeurs de X i
for i=1:n
B(i)=0;
end
while(OK==0)
//Step1: trouver une colonne pivot
max=A(m+1,1);
cp=1;
for j=2:n+m
if(A(m+1,j)>max)
max=A(m+1,j);
cp=j;
end
end
**********************************************************************************
//on vérifie s’il y a une redondance de la valeur du max, si oui, on enregistre son indice dans une
//matrice C et cpt est un compteur
C(1,1)=cp;
cpt=1;
for j=cp+1:m+n
if(max==A(m+1,j))
cpt=cpt+1;
C(cpt)=j;
end
end
//Si on a redondance on applique la méthode expliquée antérieurement pour le choix de la
colonne //pivot.On enregistre dans la matrice C=[ cp i lpi MaxDesRestesi]
if(cpt>1)
k=1;
for k=1:cpt
cp=C(k);
min=A(1,m+n+1)/A(1,cp);
lp=1;
for i=2:m
if(min>(A(i,m+n+1)/A(i,cp)))
lp=i;
min=A(i,m+n+1)/A(i,cp);
C(k,2)=lp;
C(k,3)=min;
end
end
end
max=C(1,3);
for k=2:cpt
if(max<C(k,3))
cp=C(k,1);
lp=C(k,2);
max=C(k,3);
end
end
//Si cpt reste =1
else
min=A(1,m+n+1)/A(1,cp);
lp=1;
for i=2:m
if(min>(A(i,m+n+1)/A(i,cp)))
lp=i;
min=A(i,m+n+1)/A(i,cp);
end
end
end
//Step2: actualisation de la matrice
p=A(lp,cp);
B(cp)=lp; //la matrice B pour l’affichage des X i
for i=1:m+1
if(i~=lp)
for j=1:n+m+1
if(j~= cp)
max=A(i,cp)*A(lp,j);
A(i,j)=A(i,j)-A(i,cp)*A(lp,j)/p;
end
end
end
end
//Step3: division de la ligne pivot dur le pivot
for j=1:m+n+1
A(lp,j)=A(lp,j)/p;
end
//Step3: changement des éléments de la colonne pivot par des zéros sauf le pivot
for i=1:m+1
if(i~=lp)
A(i,cp)=0;
end
end
//Step4: test de la condition d’arrêt
max=A(m+1,1);
for j=2:m+n
if(A(m+1,j)>max)
max=A(m+1,j);
end
end
if(max<=0)
OK=1;
end
end
//Affichage des Xi
for i=1:n
if(B(i)~=0)
fprintf("x%d= %f\n",i,A(B(i),m+n+1));
end
if(B(i)==0)
fprintf("x%d=0\n",i);
end
//Affichage de maxZ
z=- A(m+1,n+m+1));
fprintf("Z=%f\n",z);
end
