function [x,maxval]=simplex1(dict)
    % Apply simplex to a problem known to be feasible. 
    % dict: The starting dictionary.
    % x: optimal solution
    % maxval: optimal value
    [m,n]=size(dict); m = m-1; n=n-1;
    nvars = 1:n; bvars = (1:m) + n; % Indices to keep track of the variables
    numit = 100; 
    for N=1:numit
        inds = find(dict(1,2:end)>0); % Choice set for entering var.
        if isempty(inds)
            break;  % The dictionary is optimal
        end
        [t,k] = min(nvars(inds)); % Blands rule for choosing entering var.
        s = inds(k); % s is entering
        
        ratios = -dict(2:end,s+1)./dict(2:end,1);
        % Apply the covention 0/0=0. Matlab computes this to NaN otherwise
        inds = find((dict(2:end,s+1)==0) & (dict(2:end,1)==0));
        ratios(inds)=0;
        
        val= max(ratios);
        if val<=0
            disp('Problem is unbounded'); return;
        end
        
        inds = find(ratios==val); % Choice set for leaving var.
        [t,k] = min(bvars(inds)); % Blands rule for choosing leaving var.
        r = inds(k); % r is leaving
        s
        r
        % swap entering and leaving variable
        temp = bvars(r); bvars(r) =  nvars(s);nvars(s) = temp;
        dict = pivot(dict,s,r)
    end
    if N==numit % maximum number of iterations reached
        disp('Maximum number of iterations reached');
    end
    maxval = dict(1,1);
            
    % Define x
    x = zeros(n,1);
    inds = find(bvars <= n);
    x(bvars(inds)) = dict(inds+1,1); % Nonbasic variables set to right hand side
end