% LINEAR PROGRAMMING VIA THE SIMPLEX METHOD
clear all
A=[2,3,1,1,0,0;4,1,2,0,1,0;3,4,2,0,0,1];
b=[5,11,8];
c=[5,4,3,0,0,0];
m=3;
n=6;
x=[0,0,0,b(1),b(2),b(3)]
basis=[4,5,6]
phi=0
for iter=1:1000
%LARGEST C <=> VARIABLE INTO BASIS
cmax=0;
  for i=1:n
      if c(i)>cmax
          cmax=c(i);
          in=i;
      end
  end
  in
%STOP IF NO IMPROVEMENT IS POSSIBLE
       if cmax<=0; return; end     
 ymin=999999.;
%SMALLEST INCREMENT OF IN <=> IOUT
  for i=1:m
      if A(i,in) ~= 0
        y=b(i)/A(i,in);
        if y<ymin;
          ymin=y;
          iout=basis(i);
          isave=i;
        end  
      end
  end
  basis(isave)=in
  iout
%RESET BASIS
Asave=A(isave,in);
  for i=1:n      
      A(isave,i)=A(isave,i)/Asave;
  end
  b(isave)=b(isave)/Asave;
  for j=1:m
  Asave=A(j,isave);   
      if j ~= isave
        for i=1:n 
            A(j,i)=A(j,i)-A(isave,i)*Asave;
        end
        b(j)=b(j)-b(isave)*Asave;
      end
  end
  A
  b
%RESET ARRAY C
csave=c(in);
c(in)=0;
 for i=1:n
     if i ~= in
         c(i)=c(i)-csave*A(in,i);
     end
 end
 c
 phi=phi+csave*b(in)
 x=zeros(1,n);
 for i=1:m
     j=basis(i);
     x(j)=b(i);
 end
 x
 end
    
