function varargout = SimplexGUI(varargin)
% SIMPLEXGUI M-file for SimplexGUI.fig
%      SIMPLEXGUI, by itself, creates a new SIMPLEXGUI or raises the existing
%      singleton*.
%
%      H = SIMPLEXGUI returns the handle to a new SIMPLEXGUI or the handle to
%      the existing singleton*.
%
%      SIMPLEXGUI('CALLBACK',hObject,eventData,handles,...) calls the local
%      function named CALLBACK in SIMPLEXGUI.M with the given input arguments.
%
%      SIMPLEXGUI('Property','Value',...) creates a new SIMPLEXGUI or raises the
%      existing singleton*.  Starting from the left, property value pairs are
%      applied to the GUI before SimplexGUI_OpeningFcn gets called.  An
%      unrecognized property name or invalid value makes property application
%      stop.  All inputs are passed to SimplexGUI_OpeningFcn via varargin.
%
%      *See GUI Options on GUIDE's Tools menu.  Choose "GUI allows only one
%      instance to run (singleton)".
%
% See also: GUIDE, GUIDATA, GUIHANDLES

% Edit the above text to modify the response to help SimplexGUI

% Last Modified by GUIDE v2.5 20-Jul-2011 01:35:00

% Begin initialization code - DO NOT EDIT
gui_Singleton = 1;
gui_State = struct('gui_Name',       mfilename, ...
                   'gui_Singleton',  gui_Singleton, ...
                   'gui_OpeningFcn', @SimplexGUI_OpeningFcn, ...
                   'gui_OutputFcn',  @SimplexGUI_OutputFcn, ...
                   'gui_LayoutFcn',  [] , ...
                   'gui_Callback',   []);
if nargin && ischar(varargin{1})
    gui_State.gui_Callback = str2func(varargin{1});
end

if nargout
    [varargout{1:nargout}] = gui_mainfcn(gui_State, varargin{:});
else
    gui_mainfcn(gui_State, varargin{:});
end
% End initialization code - DO NOT EDIT


% --- Executes just before SimplexGUI is made visible.
function SimplexGUI_OpeningFcn(hObject, eventdata, handles, varargin)
% This function has no output args, see OutputFcn.
% hObject    handle to figure
% eventdata  reserved - to be defined in a future version of MATLAB
% handles    structure with handles and user data (see GUIDATA)
% varargin   command line arguments to SimplexGUI (see VARARGIN)

% Choose default command line output for SimplexGUI
handles.output = hObject;

% Update handles structure
guidata(hObject, handles);

% UIWAIT makes SimplexGUI wait for user response (see UIRESUME)
% uiwait(handles.figure1);


% --- Outputs from this function are returned to the command line.
function varargout = SimplexGUI_OutputFcn(hObject, eventdata, handles) 
% varargout  cell array for returning output args (see VARARGOUT);
% hObject    handle to figure
% eventdata  reserved - to be defined in a future version of MATLAB
% handles    structure with handles and user data (see GUIDATA)

% Get default command line output from handles structure
varargout{1} = handles.output;



function edit1_Callback(hObject, eventdata, handles)
% hObject    handle to edit1 (see GCBO)
% eventdata  reserved - to be defined in a future version of MATLAB
% handles    structure with handles and user data (see GUIDATA)

% Hints: get(hObject,'String') returns contents of edit1 as text
%        str2double(get(hObject,'String')) returns contents of edit1 as a double


% --- Executes during object creation, after setting all properties.
function edit1_CreateFcn(hObject, eventdata, handles)
% hObject    handle to edit1 (see GCBO)
% eventdata  reserved - to be defined in a future version of MATLAB
% handles    empty - handles not created until after all CreateFcns called

% Hint: edit controls usually have a white background on Windows.
%       See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor'))
    set(hObject,'BackgroundColor','white');
end



function edit2_Callback(hObject, eventdata, handles)
% hObject    handle to edit2 (see GCBO)
% eventdata  reserved - to be defined in a future version of MATLAB
% handles    structure with handles and user data (see GUIDATA)

% Hints: get(hObject,'String') returns contents of edit2 as text
%        str2double(get(hObject,'String')) returns contents of edit2 as a double


% --- Executes during object creation, after setting all properties.
function edit2_CreateFcn(hObject, eventdata, handles)
% hObject    handle to edit2 (see GCBO)
% eventdata  reserved - to be defined in a future version of MATLAB
% handles    empty - handles not created until after all CreateFcns called

% Hint: edit controls usually have a white background on Windows.
%       See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor'))
    set(hObject,'BackgroundColor','white');
end


% --- Executes on selection change in listbox1.
function listbox1_Callback(hObject, eventdata, handles)
% hObject    handle to listbox1 (see GCBO)
% eventdata  reserved - to be defined in a future version of MATLAB
% handles    structure with handles and user data (see GUIDATA)

% Hints: contents = cellstr(get(hObject,'String')) returns listbox1 contents as cell array
%        contents{get(hObject,'Value')} returns selected item from listbox1


% --- Executes during object creation, after setting all properties.
function listbox1_CreateFcn(hObject, eventdata, handles)
% hObject    handle to listbox1 (see GCBO)
% eventdata  reserved - to be defined in a future version of MATLAB
% handles    empty - handles not created until after all CreateFcns called

% Hint: listbox controls usually have a white background on Windows.
%       See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor'))
    set(hObject,'BackgroundColor','white');
end

%================================================
%         Bearbeiten-Schaltfläche
%================================================
% --- Executes on button press in pushbutton1.
function pushbutton1_Callback(hObject, eventdata, handles)
% hObject    handle to pushbutton1 (see GCBO)
% eventdata  reserved - to be defined in a future version of MATLAB
% handles    structure with handles and user data (see GUIDATA)
position = get(handles.listbox1,'value');
string = get(handles.listbox1,'String');
str = string;
[n m] = size(string)
if n>0
if n == 1
    def = {'',string};
else
    def = {'',string(position,:)};
end
answer = inputdlg({'Neue Ungleichung:','Bisherige Ungleichung:'},'',1,def);
if isempty(answer)

else
    if n == 1
        string = answer{1};
    else
        temp = answer{1}
        if isequal(temp,'')
           string(position,:)=' ';
        else
            [valid c] = is_valid(temp,0);
            if valid == 1
               string(position,:)= ' ';
               string(position,1:length(temp))=temp;
            end
        end
    end
end
set(handles.listbox1,'String',string);
end


%================================================
%         OK-Schaltfläche
%================================================
% --- Executes on button press in pushbutton2.
function pushbutton2_Callback(hObject, eventdata, handles)
% hObject    handle to pushbutton2 (see GCBO)
% eventdata  reserved - to be defined in a future version of MATLAB
% handles    structure with handles and user data (see GUIDATA)
str='';
str = get(handles.edit1,'String');
[valid c]= is_valid(str,1);
max = get(handles.radiobutton2,'value');
A=[];

if max ~=0
   c= -1*c ;
end
B=[];
if valid == 1
    string = get(handles.listbox1,'string');
    [n m] = size(string);
    if n >= 1
       for i=1:n
           if ~(isequal(regexprep(string(i,:),'\s',''),''))
              [valid x] = is_valid(string(i,:),0); 
              A=[A;x'];
              [j k]=size(B);
              B=[B;x(1),x(2),zeros(1,k-length(x)),x(3)];
              [j k]=size(B);
              [u v]=size(A);
              B=[B(:,1:k-1),zeros(j,1),B(:,k)];
              B(j,k)=1;
           end
       end
       [u v]=size(A);
       [j k]=size(B);
       A=[A;zeros(1,v)];
       A(u+1,1:3)=c';
       B=[B;zeros(1,k)];
       B(j+1,1:3)=c';
       [j k]=size(B);
       [bv basismatrix]=validbase(B(1:j-1,1:k-1),B(1:j-1,k));
       PS = get(handles.checkbox1,'value');
       if PS == 1
           C=[B(:,1:k-1),-eye(j),B(:,k)];
           [o p]=size(C);
           for i=1:j-1
              if B(i,k) >= 0
                 C=[C(:,1:k-1+i-1),C(:,k-1+i+1:p)];
                 p=p-1;
              end
           end
           C=[C(:,1:p-2),C(:,p)];
           p=p-1;
           bv=zeros(1,p-1);
           Ik=[];
           for i=1:o-1
                t=find(C(i,1:p-1) ~=0,1,'last');
                bv(t)=C(i,t)*A(i,v);
                Ik=[Ik,t];
           end
           [bv,y,cx,Ik,k,info] =  simplex (C(1:o-1,1:p-1),C(1:o-1,p)',C(o,1:p-1)',bv',Ik');
           bv=bv';
       end
       o = length(bv);
       Ik=[];
           for i=1:o
                if bv(i) ~= 0
                   Ik=[Ik,i] ;
                end
           end
           [j k]=size(B);
        [x,y,cx,Ik,k,info] =  simplex (B(1:j-1,1:k-1),B(1:j-1,k)',B(j,1:k-1)',bv',Ik');
    end
[u v] = size(A);
figure();
bild(A(1:u-1,1:v-1),A(:,v),basismatrix(:,1:2)',x)
msgbox(strcat('Die Loesung des Linearen Problems ist: ', ' x_1=',num2str(x(1)),' und x_2=',num2str(x(2)), '. Die Zielfunktion hat den Wert: ',num2str(A(u,1)*x(1)+A(u,2)*x(2))));
end

%================================================
%         Neue Ungleichung-Schaltfläche
%================================================
% --- Executes on button press in pushbutton4.
function pushbutton4_Callback(hObject, eventdata, handles)
% hObject    handle to pushbutton4 (see GCBO)
% eventdata  reserved - to be defined in a future version of MATLAB
% handles    structure with handles and user data (see GUIDATA)
str = get(handles.edit2,'String');
string = get(handles.listbox1,'string');
if is_valid(str,0) == 1
    values = strvcat(string,str);
else
    str='';
    values = strvcat(string,str);
end
set(handles.listbox1,'String',values);
set(handles.edit2,'String','');

%================================================
%         Abbrechen-Schaltfläche
%================================================
% --- Executes on button press in pushbutton5.
function pushbutton5_Callback(hObject, eventdata, handles)
% hObject    handle to pushbutton5 (see GCBO)
% eventdata  reserved - to be defined in a future version of MATLAB
% handles    structure with handles and user data (see GUIDATA)
close(SimplexGUI);

function [valid c] = is_valid(ungleichung, ist_zielfunktion)
if isempty(ungleichung)
    valid=0;
    c=zeros(3,1);
    msgbox('Bitte geben Sie die Zielfunktion und mindestens eine Ungleichung ein.')
   return
end
ungleichung = strrep(ungleichung,' ','');
valid = 1;
c=zeros(3,1);
kleiner=-1;
minus=zeros(3,1);
if (ist_zielfunktion == 1)
    M = regexpi(ungleichung,'-(([0-9]*\.?[0-9]*)|([1-9]+/[1-9]+))?x_1(\+|\-)(([0-9]*\.?[0-9]*)|([1-9]+/[1-9]+))?x_2','match');
    [n m] = size(M);
    if n >0 && m>0 && (strcmp(M(1),ungleichung))
        minus(1) =1;
        ungleichung = ungleichung(2:length(ungleichung));
    end
    M = regexpi(ungleichung,'(([0-9]*\.?[0-9]*)|([1-9]+/[1-9]+))?x_1-(([0-9]*\.?[0-9]*)|([1-9]+/[1-9]+))?x_2','match');
    [n m] = size(M);
    if n >0 && m>0 && (strcmp(M(1),ungleichung))
        minus(2) =1;
    end
   M = regexpi(ungleichung,'(([0-9]*\.?[0-9]*)|([1-9]+/[1-9]+))?x_1(\+|\-)(([0-9]*\.?[0-9]*)|([1-9]+/[1-9]+))?x_2','match');
   [n m] = size(M);
   if n >0 && m>0 && (strcmp(M(1),ungleichung))
      valid = 1;
      str=cellstr(ungleichung);
   else
      valid = 0;
      msgbox('Leider besitzt die Zielfunktion nicht das korrekte Format. Bitte geben Sie die Zielfunktion in der Form "3x_1+4x_2" ein.');
   end
else
    if strfind(ungleichung,'x_1')
        
    else
        M = regexpi(ungleichung,'-(([0-9]*\.?[0-9]*)|([1-9]+/[1-9]+))?x_2','match');
        [n m] = size(M);
        if  n >0 && m>0
            minus(1) =1;
        end
        if minus(1) == 1
            ungleichung = strcat('0x_1',ungleichung);
        else
            ungleichung = strcat('0x_1+',ungleichung);
        end
        
    end

    if strfind(ungleichung,'<=')
        str=regexp(ungleichung,'<=','split');
        kleiner=1;
    elseif strfind(ungleichung,'>=')
        str=regexp(ungleichung,'>=','split');
        kleiner=0;
    elseif strfind(ungleichung,'==')
        str=regexp(ungleichung,'==','split');
        valid = 0;
        msgbox('Leider besitzt die Ungleichung nicht das korrekte Format. Bitte geben Sie eine Ungleichung in der Form "3x_1+4x_2<=5" oder "3x_1+4x_2>=5" ein.');
    else
        valid = 0;
        msgbox('Leider besitzt die Ungleichung nicht das korrekte Format. Bitte geben Sie eine Ungleichung in der Form "3x_1+4x_2<=5" oder "3x_1+4x_2>=5" ein.');
    end
    if valid == 1
        if strfind(str{1},'x_2')

        else
            str{1} = strcat(str{1},'+0x_2');
        end
        M = regexpi(str{1},'-(([0-9]*\.?[0-9]*)|([1-9]+/[1-9]+))?x_1(\+|\-)(([0-9]*\.?[0-9]*)|([1-9]+/[1-9]+))?x_2','match');
        [n m] = size(M);
        if  n >0 && m>0 && (strcmp(M(1),str{1}))
            minus(1) =1;
            str{1} = str{1}(2:length(str{1}));
        end
        M = regexpi(str{1},'(([0-9]*\.?[0-9]*)|([1-9]+/[1-9]+))?x_1-(([0-9]*\.?[0-9]*)|([1-9]+/[1-9]+))?x_2','match');
        [n m] = size(M);
        if n >0 && m>0 && (strcmp(M(1),str{1}))
            minus(2) =1;
        end
        if valid ==1
           M = regexpi(str{1},'(([0-9]*\.?[0-9]*)|([1-9]+/[1-9]+))?x_1(\+|\-)(([0-9]*\.?[0-9]*)|([1-9]+/[1-9]+))?x_2','match');
           [n m] = size(M);
           if n >0 && m>0 && (strcmp(M(1),str{1}))
              valid = 1;
           else
              valid = 0;
              msgbox('Leider besitzt die Ungleichung nicht das korrekte Format. Bitte geben Sie eine Ungleichung in der Form "3x_1+4x_2<=5" oder "3x_1+4x_2>=5" ein.');
           end
        end    
    end
end


if valid == 1
    if strfind(str{1},'x_1')
        temp = regexp(str{1},'x_1','split');
        if isequal(temp{1},'')~=1
            if kleiner==0
                c(1)=-str2num(temp{1});
            else
                c(1)=str2num(temp{1});
            end
        else
            if kleiner==0
                c(1)=-1;
            else
                c(1)=1;
            end
        end
    end
    if strfind(str{1},'x_2')
        temp = regexp(str{1},'x_2','split');
        temp = regexp(temp{1},'[\+\-]','split');
        if isequal(temp{2},'')~=1
            if kleiner==0
                c(2)=-str2num(temp{2});
            else
                c(2)=str2num(temp{2});
            end
        else
            if kleiner==0
                c(2)=-1;
            else
                c(2)=1;
            end
        end
    end
    if kleiner==0
        c(3)=-str2num(str{2});
    elseif kleiner ~=-1
        c(3)=str2num(str{2});
    end
    if minus(1) == 1
        c(1) = -1* c(1);
    end
    if minus(2) == 1
        c(2) = -1* c(2);
    end
    if minus(3)==1
        c(3) = -1* c(3);
    end
end

function [bv basismatrix] = validbase(A,b)


%Input: Matrix mit Schlupfvariablen z, ohne Schlupfvariablen y
%Output: 
% ein zulï¿½ssiger Basisvektor, falls der Algorithmus anwendbar ist
% ein Nullvektor sonst

B = A;
v = size(A);
zeilen = v(1); %Zeilen von A
spalten = v(2); %Spalten von A
bv = zeros(1,spalten); %Initialisierung von bv
basis = zeros(1,spalten); %Basisvektor
C = zeros(zeilen,zeilen); %Teilmatrizen von A
x = zeros(zeilen,1);
kwerte = zeros(1,zeilen);
n = 0; % Hilfsvariable
basismatrix = zeros(1,spalten); %Matrix, die zulï¿½ssige Basisvektoren als Zeilenvektoren enthï¿½lt
bm = 1; %Hilfsvariable


for i = 1:spalten
    for j = i+1:spalten
        B = A; %je zwei Spalten von A null setzen
        B(:,i) = zeros(zeilen,1);
        B(:,j) = zeros(zeilen,1);
        s = 1;
        for k = 1:spalten
            if B(:,k) == zeros(zeilen,1)
            else
                C(:,s) = B(:,k); %Teilmatrizen bilden (Nullspalten entfernen)
                kwerte(s) = k; %Bestimmung der Stellen, an der die Zahlenwerte im Basisvektor auftauchen
                s = s + 1;
            end
        end
        if  rank(C) == zeilen %bei invertierbaren Matrizen
            x = inv(C)*b; %LGS lï¿½sen
        else %Verhindert, dass Nullzeilen in bsismatrix auftauchen
            n = n + 1;
        end
        for l=1:length(kwerte)
            if kwerte(l)>0
                basis(kwerte(l)) = x(l); %Basiswerte in basisvektor eintragen
            end
        end
        for m=1:length(basis) %Kriterium fï¿½r Ausschluss von unzulï¿½ssigen Basisvektoren
            if basis(m) < 0
                n = n + 1;
            end
        end
        if n > 0 %kein zulï¿½ssiger Basisvektor
        else
            basismatrix(bm,:) = basis; %Eintragen der zulï¿½ssigen Basisvektoren in eine Matrix
            bm = bm + 1; %Kriterium fï¿½r Anwendbarkeit des Simplex-Algorithmus
        end
        n = 0; %Neuinitialisierung wichtiger Variablen
        x = zeros(zeilen,1);
        kwerte = zeros(1,zeilen);
        basis = zeros(1,spalten);
    end
end
if bm >= 2
    bv = basismatrix(1,:);
end

function []=bild(A,b,B,opt)
%ich nehme an, dass A die ursprüngliche Matrix mit den ungleichungen, b die
%rechte seite der ungleichungen ist und gehe vorerst von x1 und x2 aus, x3 
%kann nachgearbeitet werden. B wird die Matrix mit den Basisvektoren sein.
%Die zu optimierende gleichung ist außen vor
%opt seien die korrdinaten für die optimallösung (nur x1 und x2)
[n,m]=size(A);
if m~=2
    error('ich brauch nur x1 und x2')
end
B=sortieren(B);
%range1 ist ein vektor, der die größten x1 und x2 koordinaten der
%Basisvektoren ausliest. damit will ich eien sinnvolle "plotrange"
%bestimmen. range ist das mas von range1 mal 1.3, also das maximum mit um
%30% vergrößert. damit sollten die verhältnisse passen
range1=[max(B(1,:)),max(B(2,:))];
range=max(range1)*1.3;
k=1;

% ich bastel matritzen X und Y, hinterher nehme ich je eine zeile und
% plotte sie. der zeichen2 vektor is quasi der gleiche wie zeichen nur ohne
% werte, wo die beiden A-werte null sind
for j=1:n
    if A(j,1)~=0 && A(j,2)~=0 % einfacher fall, alles ungleich null
        X(k,:)=0:0.01:range;
        lang=size(X(k,:),2);
        Y(k,:)=(A(j,1).*X(k,:) -ones(1,lang).*b(j))./(-A(j,2));
        k=k+1;
        
    elseif A(j,1)==0 && A(j,2)~=0 % kein x1, d.h. parallele zur x1-achse
        X(k,:)=0:0.01:range;
        Y(k,:)=b(j)/A(j,2);
        k=k+1;
        
    elseif A(j,1)~=0 && A(j,2)==0 % kein x2, d.h. parallele zur x2-achse
        Y(k,:)=0:0.01:range;
        X(k,:)=b(j)/A(j,1); % extra vertauscht
        k=k+1;
        
    else
    end
end

[np, mp]=size(X);
%if mp~=range*100
%    error('hier ist was schiefgelaufen')
%end
hold on
for j=1:np
    plot(X(j,:),Y(j,:))
end

B=[B,B(:,1)]; % fügt ersten basisvektor noch mal an matrix an, brauchbar für den area befehl
a=area(B(1,:),B(2,:)); %nimmt alle basisvektoren und füllt die fläche dazwischen
set(a,'FaceColor','y')

plot(opt(1),opt(2),'ro','MarkerSize',3,'Linewidth',3) % plottet den otpimalen punkt als roten dicken punkt
text(opt(1),opt(2),'  Optimale Kombination') % beschriftet den punkt

xlabel('x_1') %beschriftungen und so
ylabel('x_2')
title('Polyeder und Optimale Kombination von x_1 und x_2')
axis([0 range 0 range])

function gerade(P1, P2, L)
% zeichnet Gerade in der Ebene
% P1 & P2 sind Vektoren mit den x,y-Koordinaten
% L ist der Geradenparameter 0, 1, 0.1 zeichnet die
% Strecke P1P2

l = (L(1):L(3):L(2));
x = P1(1) + l*(P2(1) - P1(1));
y = P1(2) + l*(P2(2) - P1(2));

plot(x,y);
% Aufruf: gerade([x1, y1], [x2, y2], [lmin, lmax, dl])

function [x,y,cx,Ik,k,info] = simplex(A,b,c,x,Ik)

%
%   simplex.m (Simplex method for linear programs)
%   ========= ====================================
%
%   This subroutine contains a simple implementation of the simplex
%   method for the solution of linear programs given in the standard form
%
%      min c'x    subject to    Ax=b, x>=0.                     
%
%   The implementation assumes that the program can be started at a feasible 
%   basic vector. Furthermore, the current implementation has the following 
%   disadvantages:
%    -> The full rank of A is not checked
%    -> No strategy for a possible cycling is included
%    -> The linear systems with the basis matrix B are solved
%       in a straightforward way.
%
%   Meaning of the input parameters:
%
%   A, b, c:  Data of the linear program
%   x, Ik:    initial basic feasible solution with corresponding index set Ik
%
%   Meaning of the output parameters:
%
%   x:    last basic feasible solution found by the algorithm
%   y:    last iterate for the dual problem
%   cx:   objective function value at current iteration
%   Ik:   index set corresponding to last basic feasible solution x
%   k:    number of iterations until termination
%   info: Output parameter providing the following information:
%     info=0: program still running or (at k=kmax) maximum iteration reached
%     info=1: indicates that the solution of the linear program was found
%     info=2: indicates that the linear program is unbounded from below
%
%   copyright: Christian Kanzow
%              Institute of Mathematics
%              University of Wuerzburg
%              Am Hubland
%              97074 Wuerzburg
%              GERMANY
%
%              e-mail: kanzow@mathematik.uni-wuerzburg.de
%
%   written on:        March 9, 2003
%   last modification: October 23, 2007
%

[m,n]=size(A);              % dimension of problem
eps=1e-8;                   % small number, viewed as zero
kmax=1000;                  % maximum number of iterations allowed
info=0;                     % initialization of output parameter info

%   Initializations:

Jk=1:n; Jk(Ik)=[];          % index set of nonbasic variables
B=A(:,Ik);                  % basis matrix
N=A(:,Jk);                  % nonbasis matrix
cx=c'*x;                    % optimal function value at starting point
k=0;                        % iteration counter

%   Iteration:
   
while (k<kmax) & (info==0) 

   y=B'\c(Ik);              % step (S.1)
   u=c(Jk)-N'*y;            % step (S.2)
   [umin,indexr]=min(u);    % step (S.3)
   if umin>-eps             
      info=1;
      return
   end
   rk=Jk(indexr);           % step (S.4); this is not Bland's rule
   d=B\A(:,rk);             % step (S.5)
   [dmax,indexs]=max(d);    % step (S.6)
   if dmax<eps           
      info=2;
      return
   end
   sk=Ik(indexs);           % step (S.7); this is not Bland's rule
   t=x(sk)/d(indexs);       % compute stepsize t
   for i=1:m
      if d(i)>0
         if x(Ik(i))/d(i)<t
            t=x(Ik(i))/d(i);
            sk=Ik(i);
            indexs=i;
         end
      end
   end

   xnew=zeros(n,1);         % compute new iterate
   for i=1:m
      if Ik(i)~=sk
         xnew(Ik(i))=x(Ik(i))-t*d(i);
      end
   end
   xnew(rk)=t;
   x=xnew;
   cx=c'*x;                 % current objective function value

   Ik(indexs)=rk;           % update index set of basic variables
   Jk(indexr)=sk;           % update index set of nonbasic variables
   B=A(:,Ik);               % new basis matrix
   N=A(:,Jk);               % new nonbasis matrix
   k=k+1;                   % update iteration counter

end

return

% --- Executes on button press in checkbox1.
function checkbox1_Callback(hObject, eventdata, handles)
% hObject    handle to checkbox1 (see GCBO)
% eventdata  reserved - to be defined in a future version of MATLAB
% handles    structure with handles and user data (see GUIDATA)

function [B]=sortieren(A)

[~,index]=sort(A,2);    % a ist "sortierte matrix" hier aber nutzlos
                        % b enthält die ursprünglichen indizes
Bi=A(:,index(1,:));     % Bi ist die Matrix, deren einträge nach x-werten sortiert sind

n=size(A,2);

if Bi(1,1)==Bi(1,2)     % Falls zwei gleiche x-werte auftreten nehmen wir den kleineren als erstes
    mini=min(Bi(2,1),Bi(2,2));
    maxi=max(Bi(2,1),Bi(2,2));
    Bi(2,1)=mini;
    Bi(2,2)=maxi;
end
if Bi(1,n)==Bi(1,n-1)   % Gleiches gilt für y-werte
    mini=min(Bi(2,n),Bi(2,n-1));
    maxi=max(Bi(2,n),Bi(2,n-1));
    Bi(2,n)=maxi;
    Bi(2,n-1)=mini;
end

z=Bi(1,n)-Bi(1,1);      % wir definieren eine gerade g, hier das handwerkszeug
a=Bi(:,1);
b=Bi(:,n);

g=@(t) a+(1-t).*(a-b);  % die gerade soll verwendet werden um zu unterscheiden
                        % welche punkte der opere oder untere teil des
                        % polyeders sind
Bo=[0;0];               % einführen der vorläufigen matrizen Bo für B_oben
Bu=[0;0];               % bzw B_unten
for k=2:n-1
    t=(Bi(1,k)-Bi(1,1))/z;
    if Bi(2,k)>g(t)
        Bo=[Bo,Bi(:,k)];
    else
        Bu=[Bu,Bi(:,k)];
    end
end

[~,index]=sort(Bo,2);   % Sortieren Bo und Bu wie schon A  
Boo=Bo(:,index(1,:));
Boo=Boo(:,2:end);       % entferne unnötige nullen

[~,index]=sort(Bu,2);    
Buu=Bu(:,index(1,:));
Buu=Buu(:,2:end);
                        % und setzen alles zusammen
B=[Bi(:,1),Buu,Bi(:,n),fliplr(Boo)];
