Universit Sidi Mohammed Ben Abdallah
Facult des sciences et techniques FES
Mini-Projet
ALGORITHME DE SIMPLEXE
Prpar par :
Alae Ennasyry
Programmation Mathmatique
Anne universitaire :
2012-2013
Licence
Calcul Scientifique et Applications
Algorithme de Simplexe
Le Simplexe est un des algorithmes fondamentaux pour la rsolution des
programmes linaires, dont notamment les problmes conomiques.
Lalgorithme permet de maximiser ou minimiser une relation conomique
dite fonction objective de plusieurs variables sous certaines contraintes.
Lobjectif du Projet est de mettre en pratique cette mthode en utilisant le
logiciel MATLAB pour rsoudre un problme de minimisation.
lalgorithme du simplexe :
1) convertir le problme sa forme standard (ie on doit ajouter une
matrice I canonique
avec : I (m, m) o m est le nombre de contraintes
2) (a) Si Ci0 i=1,..,n ; stop loptimum est atteint,
(b) Sinon ; choisir une colonne s qui va entre en base (on
prend le cout le plus ngatif).
3) choix de la ligne qui va quitter la base :
(a) si Si ais0 i=1,..,m ; stop la solution est non borne
(b) sinon, choisir la ligne r en utilisant la rgle de plus petit
rapport:
=min{
/ > 0 }
4) Passage au tableau suivant :
transformation de la ligne r (dite ligne pivot).
transformation de la colonne s par la colonne er de la base
canonique.
Transformation des autres cases en appliquant la rgle
suivante :
ai,j=ai,j-
* ar,j bi=bi-
* br
5) revenir ltape 2)
function z=simplexe(A,C,b)
[n m]=size(A);
%1ere tape :
T=[A eye(n) b';C];
x=zeros(m,1);
%2eme tape (la recherch de s) :
min=0;
s=0;
for i=1:m+n
if(T(n+1,i)<min)
min=T(n+1,i);
s=i;
end
end
k=0;
%3eme tape (la recherch de r )
while(s~=0)
min=10000;
r=0;
for i=1:n
if(T(i,s)>0)
if(T(i,n+m+1)/T(i,s)<min)
min=T(i,n+m+1)/T(i,s);
r=i;
end
end
end
% 4eme tape :
if(r==0)
disp('la solution est non bornee')
break; %pour sortir de la boucle
else % le changement des lment du tableau sauf la ligne pivot
for i=1:n+1
if(i~=r)
T(i,:)=T(i,:)-T(i,s)*T(r,:)/T(r,s);
end
end
end
% le changement de la ligne pivot
T(r,:)=T(r,:)/T(r,s);
% il ne faut pas oublier que le x (vecteur solution) change aussi aprs chaque itration
for i=1:n
if x(i)>0
x(i)=x(i)-T(i,s)*T(r,s)/T(r,s);
end
end
if(s>0)
x(s)=T(r,n+m+1);
end
% et enfin on cherche le s une deuxime fois pour vrifier le test darrt
min=0;
s=-1;
for i=1:m+n
if(T(n+1,i)<min)
min=T(n+1,i);
s=i;
end
end
end
if(s==-1)
disp('la solution est :')
x
end
disp('valeur optimale est :)
Remarques :
T est le tableau du simplexe
X est un vecteur qui reprsente la solution du
problme
s est lindice de la colonne pivot
r est lindice de la ligne pivot
(s et r sont initialiss par zros )
Implmentation de lalgorithme sur MATLAB :
