function [x,basis] = simplex(A,b,c,basis,pricing)
% Das Programm simplex_opt loest lineare Optimierungsprobleme der Art:
% min c'*x
% s.t. A*x = b, x >= 0
% (d.h.  es wurden bereits Slackvariablen eingefuehrt)
%
% INPUT:
% ------
% A,b,c     - Eingabedaten des linearen Programms (Matrix A, Vektoren b, c)
% basis     - zulässige Startbasis (Eingabe als Zeilenvektor)
% pricing   - 0 für Negativste reduzierte Kosten, 1 für Regel von Bland
%
% OUTPUT:
% -------
% x         - Optimalloesung
% basis     - Basis der Optimalloesung bzw. [] bei unbeschraenkt
%

    % Initialisierung
    n = size(A,2); % Anzahl der Spalten von A
    B = basis;
    N = 1:n;  
    N(B) = []; % Erzeuge Nichtbasis - 1:n ohne die Elemente der Basis

    % Berechne das aktuelle x aus der Basis
          x = zeros(n,1);
          x(B) =    %%%% ergaenze

        while true    % Simplexiteration, Abbruch durch Herausspringen 

            % Ausgabe von Basis, x und Zielfunktionswert
            B
            x
            ZFW = c'*x

            % BTRAN
            % Berechne y        
            y =      %%%% ergaenze

            % PRICE
            % Bestimme die reduzierten Kosten z_N
            z_N =           %%%% ergaenze

            % Bestimme, ob es negative reduzierte Kosten gibt:
            % wenn nein, optimal
            if all(z_N >= 0)
                % Optimalloesung gefunden
                basis = B;
                x = x;
                return   
            end

            if pricing == 0
                % negativste reduzierte Kosten
                [z_N_i_dach, i_dach] = min(z_N);       
                i_dach = N(i_dach);  % bestimme Index in A, bisher Index in N
            else
                % Regel von Bland - waehle immer negative reduzierte Kosten mit kleinstem Index 
                ind = find( z_N < 0 );  % Indizes zu neg. red. Kosten
                ind = N(ind);           % bestimme Index in A, bisher Index in N
                i_dach = min(ind);
            end 

            % FTRAN
            % Berechne w_quer
            w_quer =     %%%% ergaenze

            % Ratio Test
            if  %%%% ergaenze
                    disp('Lineares Programm ist ... ');  %%%% ergaenze
                basis = [];
                x = [];
                return
            end
            ind = find(w_quer > 0);
            ratio = x(B(ind))./w_quer(ind);
            xi = min(ratio);

            j_dach = find(ratio == xi);
            j_dach = ind(j_dach);
            [j_dach_min k] = min(B(j_dach));
            j_dach = j_dach(k);
 
            % Update
            x(B) =    %%%% ergaenze
            x(i_dach) =   %%%% ergaenze

            % Basiswechsel
            B(j_dach) =   %%%% ergaenze
            N = 1:n;
            N(B) = [];
        end
end