//////////////////
//
// Algorithme du simplexe, TP3, L3 optimisation
//
///////////////////
m=2;
p=3;
G=zeros(m,p);
D=zeros(m,1);
C1=zeros(p,1);
////
//Exemple
//
G=[1,4,1;1,0,1];
D=[10;2];
C1=[1;2;1];
/////////////////////////////////////
//
// transformation en contrainte égalité (problème P)
//
/////////////////////////////////////
//
n=m+p;
A=[G,eye(m,m)];
B=D;
C=[C1;zeros(m,1)];
////
// recherche du premier sommet (sommet 1)
//
Jin=(p+1):n;
Jout=1:p;
X=zeros(n,1);
X(Jin)=inv(A(1:m,Jin))*B;
val=C'*X;
disp('premier sommet');disp(X)
disp('gain');disp(val)
/////////////////////////////
/////////////////////////////
/////////////////////////////
// 
//// calcul de H, Bprime, Cprime
//  
H=inv(A(1:m,Jin))*A(1:m,Jout);
Bprime=inv(A(1:m,Jin))*B;
Cprime=C(Jout)-H'*C(Jin);
valmax=max(Cprime);
/////////////////////////////
// calcul du sommet suivant
//
/////////////////////////////
// boucle simplexe
//////////////////////////////
while(valmax>0)
 //// qui entre dans la base?
//   
//
[a,b]=max(Cprime)
iin=Jout(b);
///////////////
//// qui sort de la base?
//
K=Bprime./H(:,iin);
ind=find(K>0);
[d,e]=min(K(ind));
iout=Jin(ind(e));
/////////////////////////////
//  nouveau sommet
//
Jin(ind(e))=iin;
Jout(b)=iout;
X=zeros(n,1);
X(Jin)=inv(A(1:m,Jin))*B;
val=C'*X;
//
//// actualisation de H, Bprime, Cprime
//
H=inv(A(1:m,Jin))*A(1:m,Jout);
Bprime=inv(A(1:m,Jin))*B;
Cprime=C(Jout)-H'*C(Jin)
valmax=max(Cprime);
disp('nouveau sommet');disp(X)
disp('gain');disp(val)
end
///////////////////////////






