function out=m164hw3(A,b,c,x)
%Assuming that A has full row rank, b>=0 and x is a nondegenerate basic 
%feasible solution performs one step of the simplex method to minimize z=c.x, 
%i.e. outputs a new basic feasible solution.  Follows general formulas
%found in on page 98 in the book

xsize=size(x);
bsize=size(b);
basicvariables = find(x~=0);
nonbasicvariables = find(x==0);

B=A(:,basicvariables); % calculates B and N
N=A(:,nonbasicvariables);
cB=c(basicvariables);
cN=c(nonbasicvariables);

bhat=B^-1*b;
cNhat=cN-cB*B^-1*N; %z = cB*B^-1*b + cNhat*xN
if cNhat>=0
    out=x;
    msgbox('x is already optimal')
else
    [cNhatmin,newbasicvariable]=min(cNhat);
    enteringvariable=nonbasicvariables(newbasicvariable); %entering variable
    
    ratios=bhat./(B^-1*A(:,enteringvariable)); 
    for i=1:bsize %set negative to infinity so they won't be part of the min
        if ratios(i)<0
            ratios(i)=Inf;
        end
    end
    [maxsteplength,newnonbasicvariable]=min(ratios); %ratio test
    %exitingvariable=basicvariables(newnonbasicvariable); %exiting variable

    if maxsteplength==Inf
        out=-Inf;
        msgbox('unbounded problem no finite solution') %all the ratios were negative
    else
        basicvariables(newnonbasicvariable)=enteringvariable;%find new basic and nonbasic variables
        %nonbasicvariables(newbasicvariable)=exitingvariable; 
        
        Bnew=A(:,basicvariables); %our new B
        xB=Bnew^-1*b;
        
        out=zeros(xsize); %create new basic feasible solution
        out(basicvariables)=xB;
    end
end