Aula 28

%%Aula 28/05/2015 - Matlab function [xb,z,y]= simplex_aula(A,b,c) %Implementação Simplex do tipo max c'x s.a. Ax <=b , x>=0
%Entrada: Matriz A e vetores b,c;
%Saídas: xb ( Solução Básica), z ( função objetivo) e y( variáveis duais) %% Verificar a corretude da entrada % Comparar as dimensoes de A , b e c
%% Algoritmo Simplex [m,n]=size(A); Aext=[A ,eye(m)];% matriz A de forma extendida para o problema na forma padrão cext=[c',zeros(1,m)]; % vetor c extendido : Adaptando para o problema na forma padrão %% Verificar se precisa da Fase 1 bmin = min(b);% encontra o menor valor do vetor b para verificar se é necessário ou não rodar a fase 1 if bmin<0 % Preciso rodar a Fase 1 !!! else % Não precisa Rodar a Fase 1 . As folgas são um SBV inicial . base = (n+1) : (n+m);%vetor com os índicas das colunas n+1 até n+ m nbase=1:n;%vetor com os índicas das colunas 1 até n end flag =0;% flag para mostrar se o algoritmo não convergiu while flag == 0 B = Aext(:,base);% B será a matriz associada aos índices da coluna da base N = Aext(:,nbase); cb = cext(:,base); cn = cext (:,nbase);

% !!!!!! Inversa da Matriz !!!!!!!!!!! Binv = inv(B); % inversa da B. y=cb*Binv; % variáveis duais cred=cn-y*N; % Custo reduzido. vec=cred > zeros(1,n); if(sum(vec)==0) % Condição de otimalidade % Estamos no ótimo !! % Retorna y ,cb ,z xb= Binv*b;% Vetor de variáveis Básicas % CUIDADO !! Não são as variáveis de decisão , necessariamente !! z= cb*xb; % função objetivo[ flag = 1; else % Há pelo menos um custo reduzido maior que zero % Troca de base. % !!!!!!!!!!!!! Escolha quem entra na Base !!!!!!!!!!!!!! [~,j] = max (cred); % Teste para ilimitado u= Binv*N(:,j)