Trabalho 3

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

tabela_simplex.xlsx
Sheet1
		Instancia		Variaveis (n)		Restrições (m)		Função objetivo (z)		Número de iterações (cont)		Tempo de execução (Algoritmo) (t) [s]		Tempo de execução (LINPROG) (t2) [s]
		1		100		100		7,340909		16		0,015625		0,03125
		2		150		200		3,73025		36		0,140625		0,109375
		3		200		300		4,00101		23		0,28125		0,140625
		4		1000		350		5,539024		72		1,921875		1
		5		1500		400		3,539609		186		6,53125		3
		6		2000		600		3,6591		148		14,703125		4,953125
		7		2500		650		4,6102		209		27		8,296875
		8		3000		700		4,1014		188		29,375		9,859375
		9		3000		750		3,6611		241		46,03125		13,15625
		10		4000		800		3,8614		316		71,546875		21,34375
		m x n
		10000
		30000
		60000
		350000
		600000
		1200000
		1625000
		2100000
		2250000
		3200000
Sheet2
Sheet3
Tarefa_1_letra_a.m
% Esse é o problema da página 39 do livro texto (Chvátal), utilizado para exemplificar a necessidade da fase 1.
A = [2 -1 2 ; 2 -3 1 ; -1 1 -2];
b = [4 ; -5 ; -1];
c = [1 ; -1 ; 1];
t = cputime;
[z, x, s, y, estado, base, nbase, d, c_red, cont] = chicosimplexrev(A, b, c);
t = cputime - t;
 
space = ' ; ';
if (estado == 1)
 str_x = 'Vetor de variáveis de decisão originais: x = ['
 for l = 1:(size(x,1)-1)
 str_x = strcat(str_x,num2str(x(l)),space) 
 end
 str_x = strcat(str_x,num2str(x(size(x,1))),']')
 str_y = 'Vetor de variáveis duais: y = ['
 for l = 1:(size(y,1)-1)
 str_y = strcat(str_y,num2str(y(l)),space) 
 end
 str_y = strcat(str_y,num2str(y(size(y,1))),']')
 str_s = 'Vetor de folgas: s = ['
 for l = 1:(size(s,1)-1)
 str_s = strcat(str_s,num2str(s(l)),space) 
 end
 str_s = strcat(str_s,num2str(s(size(s,1))),']')
 str_c_red = 'Vetor de custos reduzidos: c_red = ['
 for l = 1:(size(c_red,1)-1)
 str_c_red = strcat(str_c_red,num2str(c_red(l)),space) 
 end
 str_c_red = strcat(str_c_red,num2str(c_red(size(c_red,1))),']')
 str_base = 'Vetor de indices relativos às variáveis básicas: base = ['
 for l = 1:(size(base,2)-1)
 str_base = strcat(str_base,num2str(base(l)),space) 
 end
 str_base = strcat(str_base,num2str(base(size(base,2))),']')
 str_nbase = 'Vetor de indices relativos às variáveis não básicas: nbase = ['
 for l = 1:(size(nbase,2)-1)
 str_nbase = strcat(str_nbase,num2str(nbase(l)),space) 
 end
 str_nbase = strcat(str_nbase,num2str(nbase(size(nbase,2))),']')
 str_ite = strcat('Número de iterações: ',num2str(cont)) 
 str_tempo = strcat('Tempo decorrido:',num2str(t), ' [s]')
 fid = fopen('C:\Temp\chico_tarefa_1_a.txt','w');
 %fid = fopen('C:\Temp\chico_tarefa_1_a.txt','w');
 fprintf(fid,'Solução ótima encontrada! \n \n Estado = %d \n \n Valor ótimo da função objetivo: z = %d \n %s \n %s \n %s \n %s \n %s \n %s \n \n %s \n %s', estado, z, str_x, str_y, str_s, str_c_red, str_base, str_nbase, str_ite, str_tempo);
 status = fclose(fid)
 
 winopen('C:\Temp\chico_tarefa_1_a.txt')
 %winopen('C:\Temp\chico_tarefa_1_a.txt')
 
elseif (estado == 0)
 str_x = 'Último vetor de variáveis de decisão originais encontrado: x = ['
 for l = 1:(size(x,1)-1)
 str_x = strcat(str_x,num2str(x(l)),space) 
 end
 str_x = strcat(str_x,num2str(x(size(x,1))),']')
 str_y = 'Último vetor de variáveis duais encontrado: y = ['
 for l = 1:(size(y,1)-1)
 str_y = strcat(str_y,num2str(y(l)),space) 
 end
 str_y = strcat(str_y,num2str(y(size(y,1))),']')
 str_s = 'Último vetor de folgas encontrado: s = ['
 for l = 1:(size(s,1)-1)
 str_s = strcat(str_s,num2str(s(l)),space) 
 end
 str_s = strcat(str_s,num2str(s(size(s,1))),']')
 str_c_red = 'Último vetor de custos reduzidos encontrado: c_red = ['
 for l = 1:(size(c_red,1)-1)
 str_c_red = strcat(str_c_red,num2str(c_red(l)),space) 
 end
 str_c_red = strcat(str_c_red,num2str(c_red(size(c_red,1))),']')
 str_base = 'Último vetor de indices relativos às variáveis básicas encontrado: base = ['
 for l = 1:(size(base,2)-1)
 str_base = strcat(str_base,num2str(base(l)),space) 
 end
 str_base = strcat(str_base,num2str(base(size(base,2))),']')
 str_nbase = 'Último vetor de indices relativos às variáveis não básicas encontrado: nbase = ['
 for l = 1:(size(nbase,2)-1)
 str_nbase = strcat(str_nbase,num2str(nbase(l)),space) 
 end
 str_nbase = strcat(str_nbase,num2str(nbase(size(nbase,2))),']')
 
 str_dire = 'Direção extrema: d = ['
 for l = 1:(size(d,1)-1)
 str_dire = strcat(str_dire,num2str(d(l)),space) 
 end
 str_dire = strcat(str_dire,num2str(d(size(d,1))),']')
 str_ite = strcat('Número de iterações: ',num2str(cont))
 str_tempo = strcat('Tempo decorrido:',num2str(t), ' [s]')
 fid = fopen('C:\Temp\chico_tarefa_1_a.txt','w');
 %fid = fopen('C:\Temp\chico_tarefa_1_a.txt','w');
 fprintf(fid,'O problema é ilimitado! \n \n Estado = %d \n \n Último valor da função objetivo encontrado: z = %d \n %s \n %s \n %s \n %s \n %s \n %s \n %s \n \n %s \n %s', estado, z, str_x, str_y, str_s, str_c_red, str_base, str_nbase, str_dire, str_mem, str_tempo);
 status = fclose(fid)
 
 winopen('C:\Temp\chico_tarefa_1_a.txt')
 %winopen('C:\Temp\chico_tarefa_1_a.txt')
elseif (estado == -1)
 str_x = 'Último vetor de variáveis de decisão originais encontrado: x = ['
 for l = 1:(size(x,1)-1)
 str_x = strcat(str_x,num2str(x(l)),space) 
 end
 str_x = strcat(str_x,num2str(x(size(x,1))),']')
 str_y = 'Último vetor de variáveis duais encontrado: y = ['
 for l = 1:(size(y,1)-1)
 str_y = strcat(str_y,num2str(y(l)),space) 
 end
 str_y = strcat(str_y,num2str(y(size(y,1))),']')
 str_s = 'Último vetor de folgas encontrado: s = ['
 for l = 1:(size(s,1)-1)
 str_s = strcat(str_s,num2str(s(l)),space) 
 end
 str_s = strcat(str_s,num2str(s(size(s,1))),']')
 str_c_red = 'Último vetor de custos reduzidos encontrado: c_red = ['
 for l = 1:(size(c_red,1)-1)
 str_c_red = strcat(str_c_red,num2str(c_red(l)),space) 
 end
 str_c_red = strcat(str_c_red,num2str(c_red(size(c_red,1))),']')
 str_base = 'Último vetor de indices relativos às variáveis básicas encontrado: base = ['
 for l = 1:(size(base,2)-1)
 str_base = strcat(str_base,num2str(base(l)),space) 
 end
 str_base = strcat(str_base,num2str(base(size(base,2))),']')
 str_nbase = 'Último vetor de indices relativos às variáveis não básicas encontrado: nbase = ['
 for l = 1:(size(nbase,2)-1)
 str_nbase = strcat(str_nbase,num2str(nbase(l)),space) 
 end
 str_nbase = strcat(str_nbase,num2str(nbase(size(nbase,2))),']')
 
 
 str_ite = strcat('Número de iterações: ',num2str(cont))
 str_tempo = strcat('Tempo decorrido:',num2str(t), ' [s]')
 fid = fopen('C:\Temp\chico_tarefa_1_a.txt','w');
 %fid = fopen('C:\Temp\chico_tarefa_1_a.txt','w');
 fprintf(fid,'O problema é ilimitado! \n \n Estado = %d \n \n Último valor da função objetivo encontrado: z = %d \n %s \n %s \n %s \n %s \n %s \n %s \n \n %s \n %s', estado, z, str_x, str_y, str_s, str_c_red, str_base, str_nbase, str_mem, str_tempo);
 status = fclose(fid)
 
 winopen('C:\Temp\chico_tarefa_1_a.txt')
 %winopen('C:\Temp\chico_tarefa_1_a.txt')
 
elseif (estado == -2)
 str_x = 'Último vetor de variáveis de decisão originais encontrado: x = ['
 for l = 1:(size(x,1)-1)
 str_x = strcat(str_x,num2str(x(l)),space) 
 end
 str_x = strcat(str_x,num2str(x(size(x,1))),']')
 str_y = 'Último vetor de variáveis duais encontrado: y = ['
 for l = 1:(size(y,1)-1)
 str_y = strcat(str_y,num2str(y(l)),space) 
 end
 str_y = strcat(str_y,num2str(y(size(y,1))),']')
 str_s = 'Último vetor de folgas encontrado: s = ['
 for l = 1:(size(s,1)-1)
str_s = strcat(str_s,num2str(s(l)),space) 
 end
 str_s = strcat(str_s,num2str(s(size(s,1))),']')
 str_c_red = 'Último vetor de custos reduzidos encontrado: c_red = ['
 for l = 1:(size(c_red,1)-1)
 str_c_red = strcat(str_c_red,num2str(c_red(l)),space) 
 end
 str_c_red = strcat(str_c_red,num2str(c_red(size(c_red,1))),']')
 str_base = 'Último vetor de indices relativos às variáveis básicas encontrado: base = ['
 for l = 1:(size(base,2)-1)
 str_base = strcat(str_base,num2str(base(l)),space) 
 end
 str_base = strcat(str_base,num2str(base(size(base,2))),']')
 str_nbase = 'Último vetor de indices relativos às variáveis não básicas encontrado: nbase = ['
 for l = 1:(size(nbase,2)-1)
 str_nbase = strcat(str_nbase,num2str(nbase(l)),space) 
 end
 str_nbase = strcat(str_nbase,num2str(nbase(size(nbase,2))),']')
 
 
 str_ite = strcat('Número de iterações: ',num2str(cont))
 str_tempo = strcat('Tempo decorrido:',num2str(t), ' [s]')
 fid = fopen('C:\Temp\chico_tarefa_1_a.txt','w');
 %fid = fopen('C:\Temp\chico_tarefa_1_a.txt','w');
 fprintf(fid,'O número máximo de iterações foi atingido! \n \n Estado = %d \n \n Último valor da função objetivo encontrado: z = %d \n %s \n %s \n %s \n %s \n %s \n %s \n \n %s \n %s', estado, z, str_x, str_y, str_s, str_c_red, str_base, str_nbase, str_mem, str_tempo);
 status = fclose(fid)
 
 winopen('C:\Temp\chico_tarefa_1_a.txt')
 %winopen('C:\Temp\chico_tarefa_1_a.txt')
end
return;
Tarefa_1_letra_b.m
% Esse é o problema ilimitado escolhido para letra (b) da tarefa 1:
% Esse problema foi retirado da internet.
% Site: http://www.dcc.fc.up.pt/~jpp/mad/teorica-03.pdf
%
% max 2x1 - x2
%
% s.a. x1 - x2 <= 1
% -2x1 - x2 <= -6
%
% x1,x2 >= 0
%
% Assim:
A = [ 1 -1 ; -2 -1 ];
b = [ 1 ; -6 ];
c = [ 2 ; -1 ];
t = cputime;
[z, x, s, y, estado, base, nbase, d, c_red, cont] = chicosimplexrev(A, b, c);
t = cputime - t;
space = ' ; ';
if (estado == 1)
 str_x = 'Vetor de variáveis de decisão originais: x = ['
 for l = 1:(size(x,1)-1)
 str_x = strcat(str_x,num2str(x(l)),space) 
 end
 str_x = strcat(str_x,num2str(x(size(x,1))),']')
 str_y = 'Vetor de variáveis duais: y = ['
 for l = 1:(size(y,1)-1)
 str_y = strcat(str_y,num2str(y(l)),space) 
 end
 str_y = strcat(str_y,num2str(y(size(y,1))),']')
 str_s = 'Vetor de folgas: s = ['
 for l = 1:(size(s,1)-1)
 str_s = strcat(str_s,num2str(s(l)),space) 
 end
 str_s = strcat(str_s,num2str(s(size(s,1))),']')
 str_c_red = 'Vetor de custos reduzidos: c_red = ['
 for l = 1:(size(c_red,1)-1)
 str_c_red = strcat(str_c_red,num2str(c_red(l)),space) 
 end
 str_c_red = strcat(str_c_red,num2str(c_red(size(c_red,1))),']')
 str_base = 'Vetor de indices relativos às variáveis básicas: base = ['
 for l = 1:(size(base,2)-1)
 str_base = strcat(str_base,num2str(base(l)),space) 
 end
 str_base = strcat(str_base,num2str(base(size(base,2))),']')
 str_nbase = 'Vetor de indices relativos às variáveis não básicas: nbase = ['
 for l = 1:(size(nbase,2)-1)
 str_nbase = strcat(str_nbase,num2str(nbase(l)),space) 
 end
 str_nbase = strcat(str_nbase,num2str(nbase(size(nbase,2))),']')
 str_ite = strcat('Número de iterações: ',num2str(cont))
 str_tempo = strcat('Tempo decorrido:',num2str(t), ' [s]')
 fid = fopen('C:\Temp\chico_tarefa_1_b.txt','w');
 %fid = fopen('C:\Temp\chico_tarefa_1_b.txt','w');
 fprintf(fid,'Solução ótima encontrada! \n \n Estado = %d \n \n Valor ótimo da função objetivo: z = %d \n %s \n %s \n %s \n %s \n %s \n %s \n \n %s \n %s', estado, z, str_x, str_y, str_s, str_c_red, str_base, str_nbase, str_ite, str_tempo);
 status = fclose(fid)
 
 winopen('C:\Temp\chico_tarefa_1_b.txt')
 %winopen('C:\Temp\chico_tarefa_1_b.txt')
 
elseif (estado == 0)
 str_x = 'Último vetor de variáveis de decisão originais encontrado: x = ['
 for l = 1:(size(x,1)-1)
 str_x = strcat(str_x,num2str(x(l)),space) 
 end
 str_x = strcat(str_x,num2str(x(size(x,1))),']')
 str_y = 'Último vetor de variáveis duais encontrado: y = ['
 for l = 1:(size(y,1)-1)
 str_y = strcat(str_y,num2str(y(l)),space) 
 end
 str_y = strcat(str_y,num2str(y(size(y,1))),']')
 str_s = 'Último vetor de folgas encontrado: s = ['
 for l = 1:(size(s,1)-1)
 str_s = strcat(str_s,num2str(s(l)),space) 
 end
 str_s = strcat(str_s,num2str(s(size(s,1))),']')
 str_c_red = 'Último vetor de custos reduzidos encontrado: c_red = ['
 for l = 1:(size(c_red,1)-1)
 str_c_red = strcat(str_c_red,num2str(c_red(l)),space) 
 end
 str_c_red = strcat(str_c_red,num2str(c_red(size(c_red,1))),']')
 str_base = 'Último vetor de indices relativos às variáveis básicas encontrado: base = ['
 for l = 1:(size(base,2)-1)
 str_base = strcat(str_base,num2str(base(l)),space) 
 end
 str_base = strcat(str_base,num2str(base(size(base,2))),']')
 str_nbase = 'Último vetor de indices relativos às variáveis não básicas encontrado: nbase = ['
 for l = 1:(size(nbase,2)-1)
 str_nbase = strcat(str_nbase,num2str(nbase(l)),space) 
 end
 str_nbase = strcat(str_nbase,num2str(nbase(size(nbase,2))),']')
 
 str_dire = 'Direção extrema: d = ['
 for l = 1:(size(d,1)-1)
 str_dire = strcat(str_dire,num2str(d(l)),space) 
 end
 str_dire = strcat(str_dire,num2str(d(size(d,1))),']')
 str_ite = strcat('Número de iterações: ',num2str(cont))
 str_tempo = strcat('Tempo decorrido:',num2str(t), ' [s]')
 fid = fopen('C:\Temp\chico_tarefa_1_b.txt','w');
 %fid = fopen('C:\Temp\chico_tarefa_1_b.txt','w');
 fprintf(fid,'O problema é ilimitado! \n \n Estado = %d \n \n Último valor da função objetivo encontrado: z = %d \n %s \n %s \n %s \n %s \n %s \n %s \n %s \n \n %s \n %s', estado, z, str_x, str_y, str_s, str_c_red, str_base, str_nbase, str_dire, str_ite, str_tempo);
 status = fclose(fid)
 
 winopen('C:\Temp\chico_tarefa_1_b.txt')
 %winopen('C:\Temp\chico_tarefa_1_b.txt')
elseif (estado == -1)
 str_x = 'Último vetor de variáveis de decisão originais encontrado: x = ['
 for l = 1:(size(x,1)-1)
 str_x = strcat(str_x,num2str(x(l)),space) 
 end
 str_x = strcat(str_x,num2str(x(size(x,1))),']')
 str_y = 'Último vetor de variáveis duais encontrado: y = ['
 for l = 1:(size(y,1)-1)
 str_y = strcat(str_y,num2str(y(l)),space) 
 end
 str_y = strcat(str_y,num2str(y(size(y,1))),']')
 str_s = 'Último vetor de folgas encontrado: s = ['
 for l = 1:(size(s,1)-1)
 str_s = strcat(str_s,num2str(s(l)),space) 
 end
 str_s = strcat(str_s,num2str(s(size(s,1))),']')
 str_c_red = 'Último vetor de custos reduzidos encontrado: c_red = ['
 for l = 1:(size(c_red,1)-1)
 str_c_red = strcat(str_c_red,num2str(c_red(l)),space) 
 end
 str_c_red = strcat(str_c_red,num2str(c_red(size(c_red,1))),']')
 str_base = 'Último vetor de indices relativos às variáveis básicas encontrado: base = ['
 for l = 1:(size(base,2)-1)
 str_base = strcat(str_base,num2str(base(l)),space) 
 end
 str_base = strcat(str_base,num2str(base(size(base,2))),']')
 str_nbase = 'Último vetor de indices relativos às variáveis não básicas encontrado: nbase = ['
 for l = 1:(size(nbase,2)-1)
 str_nbase = strcat(str_nbase,num2str(nbase(l)),space) 
 end
 str_nbase = strcat(str_nbase,num2str(nbase(size(nbase,2))),']')
 
 
 str_ite = strcat('Número de iterações: ',num2str(cont))
 str_tempo = strcat('Tempo decorrido:',num2str(t), ' [s]')
 fid = fopen('C:\Temp\chico_tarefa_1_b.txt','w');
 %fid = fopen('C:\Temp\chico_tarefa_1_b.txt','w');
 fprintf(fid,'O problema é ilimitado! \n \n Estado = %d \n
\n Último valor da função objetivo encontrado: z = %d \n %s \n %s \n %s \n %s \n %s \n %s \n \n %s \n %s', estado, z, str_x, str_y, str_s, str_c_red, str_base, str_nbase, str_ite, str_tempo);
 status = fclose(fid)
 
 winopen('C:\Temp\chico_tarefa_1_b.txt')
 %winopen('C:\Temp\chico_tarefa_1_b.txt')
 
elseif (estado == -2)
 str_x = 'Último vetor de variáveis de decisão originais encontrado: x = ['
 for l = 1:(size(x,1)-1)
 str_x = strcat(str_x,num2str(x(l)),space) 
 end
 str_x = strcat(str_x,num2str(x(size(x,1))),']')
 str_y = 'Último vetor de variáveis duais encontrado: y = ['
 for l = 1:(size(y,1)-1)
 str_y = strcat(str_y,num2str(y(l)),space) 
 end
 str_y = strcat(str_y,num2str(y(size(y,1))),']')
 str_s = 'Último vetor de folgas encontrado: s = ['
 for l = 1:(size(s,1)-1)
 str_s = strcat(str_s,num2str(s(l)),space) 
 end
 str_s = strcat(str_s,num2str(s(size(s,1))),']')
 str_c_red = 'Último vetor de custos reduzidos encontrado: c_red = ['
 for l = 1:(size(c_red,1)-1)
 str_c_red = strcat(str_c_red,num2str(c_red(l)),space) 
 end
 str_c_red = strcat(str_c_red,num2str(c_red(size(c_red,1))),']')
 str_base = 'Último vetor de indices relativos às variáveis básicas encontrado: base = ['
 for l = 1:(size(base,2)-1)
 str_base = strcat(str_base,num2str(base(l)),space) 
 end
 str_base = strcat(str_base,num2str(base(size(base,2))),']')
 str_nbase = 'Último vetor de indices relativos às variáveis não básicas encontrado: nbase = ['
 for l = 1:(size(nbase,2)-1)
 str_nbase = strcat(str_nbase,num2str(nbase(l)),space) 
 end
 str_nbase = strcat(str_nbase,num2str(nbase(size(nbase,2))),']')
 
 
 str_ite = strcat('Número de iterações: ',num2str(cont))
 str_tempo = strcat('Tempo decorrido:',num2str(t), ' [s]')
 fid = fopen('C:\Temp\chico_tarefa_1_b.txt','w');
 %fid = fopen('C:\Temp\chico_tarefa_1_b.txt','w');
 fprintf(fid,'O número máximo de iterações foi atingido! \n \n Estado = %d \n \n Último valor da função objetivo encontrado: z = %d \n %s \n %s \n %s \n %s \n %s \n %s \n \n %s \n %s', estado, z, str_x, str_y, str_s, str_c_red, str_base, str_nbase, str_ite, str_tempo);
 status = fclose(fid)
 
 winopen('C:\Temp\chico_tarefa_1_b.txt')
 %winopen('C:\Temp\chico_tarefa_1_b.txt')
end
return;
Tarefa_2.m
% Para tarefa 2, alteramos os valores de 'n' e 'm'.
m = 750 % Número de restrições
n = 3000 % Número de variáveis de decisão originais
A = unidrnd(100,[m,n]);
b = unidrnd(100,[m,1]);
c = unidrnd(100,[n,1]);
% Calcula o tempo de execução do algoritmo:
t = cputime;
[z, x, s, y, estado, base, nbase, d, c_red, cont] = chicosimplexrev(A, b, c);
t = cputime - t;
fprintf('Tempo de execução: %f \n', t);
LB = zeros(n,1); % Declara: x >= 0
% Calcula o tempo de execução do linprog:
t2 = cputime;
[x_lp , fval, exitflag, output, lambda] = linprog(-c,A,b,[],[],LB,[],[],optimset('LargeScale','off','simplex','on'));
t2 = cputime - t2;
fprintf('Tempo de execução do linprog: %f. \n', t2);
Apresentacao_simplexrev.pptx
Trabalho de Programação Linear
Implementação do 
Método Simplex Revisado
1
Índice
	Introdução......................................................3
	Simplex Revisado: Passo a passo................4	
	Tarefa I (a): primeira instância de teste.........7
	Tarefa II (b): segunda instância de teste......17
	Tarefa 2.........................................................22
	Conclusão.....................................................28
2
3
Introdução
Esta apresentação tem como objetivo apresentar o Método Simplex Revisado, de forma resumida, e algumas de suas aplicações utilizando a ferramenta MATLAB.
4
Simplex Revisado: Passo a passo
 Verifica-se se existe elemento negativo no vetor “b”.
 Caso exista, executamos a Fase 1, caso contrário executamos direto a Fase 2.
 Na Fase 1 criamos os vetores “base” e “nbase” com os índices das variáveis básicas e não básicas, respectivamente, das colunas da matriz A na forma padrão (também criada na Fase 1). Inicialmente, a base é composta pelas colunas das folgas.
 Criamos as matrizes B e N com as colunas determinadas pelos vetores “base” e “nbase”, respectivamente.
 Criamos a matriz A_aux2 concatenando o matriz A na forma padrão com a coluna de coeficientes (-1) da variável auxiliar “w”.
 Criamos o vetor de custos do problema auxiliar, sendo os custos das variáveis originais e folgas = 0 e o custo de “w” igual a -1. Assim também criamos os vetores de custos das variáveis básicas, “cb”, e não básicas, “cn” utilizando os vetores “base” e “nbase”.
5
 Criamos o vetor “xb” de variáveis básicas inicial, que é o próprio vetor “b”.
 Criamos uma matriz A_fase2 concatenando a matriz A original com a coluna de coeficientes (-1) de “w”.
 Com todas as informações anteriores, construímos o dicionário inicial inviável do problema auxiliar.
 Efetuamos, então, a primeira troca de base, entrando a variável auxiliar e saindo a variável mais inviável (mais negativa) da base. Assim, temos um dicionário viável para trabalhar e, portanto, executamos a Fase 2.
 Na Fase 2, recebemos, da Fase 1, a matriz “A_aux2” (com folgas e -1), vetor “b”, vetor c_aux1 (custos do problema auxiliar), dimensões da matriz “A_fase2” (concatenação da A com -1), vetor “xb” e novos vetores “base” e “nbase” (depois da primeira troca de base). Caso contrário, essas informações vem do arquivo geral do simplex revisado com “base” e “nbase” sendo as folgas e variáveis de decisão do problema na forma canônica.
 Criamos as matrizes “B” e “N” e vetores “cb” e “cn” com os vetores “base” e “nbase”.
 Criamos o vetor de custos reduzidos: c_red = (cn’ – y’*N)’
6
 Escolhemos a variável que entra na base pelo critério do primeiro custo reduzido não negativo.
 Escolhemos a variável que sai da base pelo teste da razão, em que sai a variável com a menor razão, ou seja, que limita mais o crescimento da variável entrante. Assim, efetuamos a troca de base.
 Efetuamos essas operações até chegarmos a um desses pontos a seguir:
 O vetor de custos reduzidos é totalmente negativo: ÓTIMO ENCONTRADO.
 O vetor “d” (d = B-1*a) de direção extrema é totalmente negativo: PROBLEMA ILIMITADO
 Vindo da Fase 1, “w” está na base ao encontrar o ótimo: PROBLEMA ORIGINAL INVIÁVEL
 O algoritmo chegou ao máximo de iterações permitidas: BREAK
Instância I de teste.
Problema da página 39 do livro texto (Chvátal).
Utilizando a Fase 1. 
7
Segue o problema (forma canônica):
	maximizar	x1 – x2 + x3
	sujeito a:
			2x1 – x2 + 2x3	≤ 4
			2x1 – 3x2 + x3	≤ -5
			 -x1 + x2 – 2x3	≤ -1 
			x1, x2, x3 ≥ 0
8
Forma padrão (com folgas):
	maximizar	x1 – x2 + x3 + 0s1 + 0s2 + 0s3
	sujeito a:
			2x1 – x2 + 2x3 + s1 = 4
			2x1 – 3x2 + x3 + s2 = -5
			 -x1 + x2 – 2x3 + s3 = -1 
			x1, x2, x3, s1, s2, s3 ≥ 0
9
9
10
Inicialmente, verificamos se existe algum elemento negativo no vetor “b”.
Nesse problema: b = [ 4 -5 -1 ]T
Isso cria origem inviável para começar nosso algoritmo:
s1 = 4 – 2x1 + x2 – 2x3
s2 = -5 – 2x1 + 3x2 – x3
s3 = -1 + x1 – x2 + 2x3
---------------------------------
z = x1 – x2 + x3
Isso faz com que não fique claro que o problema tem qualquer solução viável e até mesmo um dicionário inicial viável.
11
Para resolver esse problema, entramos na Fase 1 e criamos um problema auxiliar.
	maximizar	- w
	sujeito a:
			2x1 – x2 + 2x3 – w	≤ 4
			2x1 – 3x2 + x3 – w	≤ -5
			 -x1 + x2 – 2x3 – w	≤ -1 
			x1, x2, x3, w ≥ 0
Incluindo a variável auxiliar “w”, aumentamos a região de viabilidade do problema, podendo assim incluir a origem.
12
Passando para forma padrão:
	maximizar	- w
	sujeito a:
			2x1 – x2 + 2x3 + s1 – w = 4
			2x1 – 3x2 + x3 + s2 – w = -5
			 -x1 + x2 – 2x3 + s3 – w = -1 
			x1, x2, x3, s1, s2, s3, w ≥ 0
13
Assim, temos o primeiro dicionário inviável do problema auxiliar.
s1 = 4 – 2x1 + x2 – 2x3 + w
s2 = -5 – 2x1 + 3x2 – x3 + w
s3 = -1 + x1 – x2 + 2x3 + w
--------------------------------------
z = - w
Verificamos, então, qual variável sai da base para a entrada de “w”, sendo a com valor mais inviável (mais negativo). Nesse caso, sai a variável “s2” (-5).
14
Depois da troca entre “s2” e “w”, temos um dicionário viável do problema auxiliar.
s1 = 9 – 2x2 – x3 + s2
w = 5 + 2x1 – 3x2 + x3 + s2
s3 = 4 + 3x1 – 4x2 + 3x3 + s2
--------------------------------------
z = -5 – 2x1 + 3x2 – x3 – s2
Assim, podemos agora executar a Fase 2 para resolver o problema auxiliar. 
15
Uma vez executada a Fase 2, temos 2 casos:
“w” está fora da base e tem valor = 0.
“w” está na base e tem valor ~= 0.
No caso 1, criamos um dicionário ótimo para o problema original, então podemos executar novamente a Fase 2 com o novo dicionário e prosseguir para solucionar problema original.
No caso 2, efetuamos uma troca forçada para tirar a variável auxiliar da base e executamos novamente a Fase 2. Ao final da Fase 2, evidenciamos que o problema original é “inviável”.
16
Resultados
Instância II de teste.
Problema retirado da internet.
http://www.dcc.fc.up.pt/~jpp/mad/teorica-03.pdf
Exemplo escolhido de problema ILIMITADO. 
17
18
Segue o problema (forma canônica):
	maximizar	2x1 - x2
	sujeito a:
			 x1 – x2 	≤ 1
			-2x1 – x2	≤ -6
			x1, x2 ≥ 0
A = [ 1 -1 ; -2 -1 ]
b = [ 1 ; -6 ]
c = [ 2 ; -1 ]
19
Forma padrão (com folgas):
	maximizar	2x1 – x2 + 0s1 + 0s2 
	sujeito a:
			 x1 – x2 + s1	 ≤ 1
		 -2x1 – x2 + s2 ≤ -6
			x1, x2, s1, s2≥ 0
20
Z = 2x1 – x2
 x1 – x2 = 1
 -2x1 – x2 = -6
Gráfico
21
Resultados
22
Tarefa 2
Maximizando o Lucro da
Venda de Vinhos
23
Contexto:
A famosa empresa francesa “Meilleur Vin” quer maximizar seu lucro com a venda de seus vinhos caríssimos, decidindo quanto deve produzir de cada tipo de vinho. Contudo, a mesma tem algumas restrições de fornecimento de tipos de uvas diferentes por dia e quantidade nescessária de cada tipo de uva para produzir cada tipo de vinho.
Fazemos então as seguintes atribuições:
xi = quantidade produzida do vinho i [unidades]
bj = fornecimento máximo da uva j por dia [toneladas/unidade de vinho]
ci = lucro de venda do vinho i [10^3 EUR]
aij = quantidade nescessaria de cada uva j para produzir 1 unidade do vinho i 
i = [1,n]
j = [1,m]
24
Formulação matemática:
Maximizar	c1x1 + c2x2 + ... + cnxn
Sujeito a:	a11x1 + a12x2 + ... + a1nxn	≤ b1
		a21x1 + a22x2 + ... + a2nxn 	≤ b2
		...		 …
		am1x1 + am2x2 + ... + amnxn 	≤ bm
	
		x1, x2, ..., xn ≥ 0
25
instância
variáveis(n)
Restrições (m)
Função objetivo (z)
Número de iterações (cont)
Tempo de execução (Algoritmo) (t) [s]
Tempo de execução (LINPROG) (t2) [s]
1
100
100
7.340909
16
0.015625
0.03125
2
150
200
3.73025
36
0.140625
0.109375
3
200
300
4.00101
23
0.28125
0.140625
4
1000
350
5.539024
72
1.921875
1
5
1500
400
3.539609
186
6.53125
3
6
2000
600
3.6591
148
14.703125
4.953125
7
2500
650
4.6102
209
27
8.296875
8
3000
700
4.1014
188
29.375
9.859375
9
3000
750
3.6611
241
46.03125
13.15625
10
4000
800
3.8614
316
71.546875
21.34375
Ao gerar, aleatoriamente, vetores de lucros para a venda de cada tipo de vinho, fornecimento diário de cada tipo de uva, e quantidade nescessária de cada tipo de uva para produzir cada tipo de vinho, obtemos a tabela abaixo:
26
27
28
Conclusão
Com relação ao tempo de execução do algoritmo criado comparado ao tempo da função LINPROG, pode-se concluir que para números pequenos de variáveis e restrições, ambos tem aproximadamente o mesmo tempo de execução. Contudo, a partir de 1000 variáveis e 350 restrições, observamos que o algoritmo aumenta acentuadamente seu tempo de execução, enquanto a função LINPROG aumenta mais sutilmente.
De forma geral, ao aumentarmos o tamanho das instâncias, aumenta também o número de iterações. Porem, e possível observar que ainda existe oscilações ao longo do aumento do tamanho das instâncias. Isso ocorre devido ao número de iterações depender do resultado da aleatoriedade da criação dos vetores para a determinada instância, além das capacidades físicas da máquina em que foi testado o algoritmo/LINPROG.
Fase1.m
function [z, estado, d, x, s, y, c_red, base, nbase, cont, xb] = chicofase1(A, b, c, m, n)
% Fase 1 do simplex revisado.
% Condições iniciais:
cont = 0;										% Condicão inicial do contador de interações.
m = m;
n = n;
% Início da fase 1 do simplex revisado:
base = [n+1:n+m];								% Cria o conjunto de indices das variaveis básicas.
nbase = [1:n,n+m+1]; % Cria o conjunto de indices das variaveis não básicas.
A_aux1 = [A, eye(m)]; % Cria a matriz A_aux1 concatenando a matriz A com a Identidade.
A_aux2 = [A_aux1, -1*ones(m,1)]; % Cria a matriz A_aux2 icluindo os coeficientes da variave de operação 'w'.
B = A_aux2(:, base); % Cria a matriz B de coeficientes das variáveis básicas.
N = A_aux2(:, nbase); 			% Cria a matriz N de coeficientes das variáveis não básicas.
c_aux1 = vertcat(zeros(n+m,1), -1); % Cria o vetor de custos 'c_aux1' referente a função objetivo da fase 1.
cn = c_aux1(nbase, :); % Cria o vetor de custos das variáveis não básicas do problema da fase1.
cb = c_aux1(base, :);
xb = b; % Cria o vetor de variáveis básicas.
A_fase2 = [A,-1*ones(m,1)];						% Cria a matriz que é dado de entrada para fase 2 do simplex revisado.
[l,k] = size(A_fase2);							% Atribui as dimensões da matriz 'A_fase2' às variaveis 'l' e 'k'.
a = N(:,n+1);									% Cria o vetor 'a' de coeficientes da variável operacinal 'w'.
[t,i] = min(xb); % Escolhe a variável que sai da base. 
d = B\a; % Cria o vetor de direção extrema.	
xb = xb - (-t)*d;								% Calcula o novo vetor de variáveis básicas.
xb(i) = -t;										% Atualiza o vetor de variáveis básicas.
aux = base(i);									% Armazena o valor do indice i na variável 'aux'.
base(i) = nbase(n+1);							% Coloca a variável que entra na base.
nbase(n+1) = aux;								% Retira a variável que sai da base.
cont = cont + 1; % Contabiliza a interação inicial da fase 1.
% Depois de criar o dicionário viável incial do problema auxiliar, executa a fase 2 do simplex revisado:
[z, estado, d, xx, x, s, y, c_red, base, nbase, cont2] = chicofase2(A_aux2, b, c_aux1, l, k, xb, base, nbase, cont);
cont = cont2;									% Atualiza contagem de iterações.
% Verifica se a variável auxiliar terminou na base:
if ( sum(base == n+m+1) == 1 )
 B = A_aux2(:,base); 
 N = A_aux2(:,nbase); 
 cb = c_aux1(base,:); 
 cn = c_aux1(nbase,:); 
 d = [];
 y = B'\cb;
 c_red = (cn' - (y')*N)'; 
 [cr_min,j] = min(c_red);
 [w_xb,i] = find(base == n+m+1); 
 % Retira a variável auxiliar da base;
 
 aux = base(i);
base(i) = nbase(j);
 nbase(j) = aux;
 cont = cont +1;
end
nbase(nbase == m+n+1) = []; % Eliminando a variável operacional;
% Verifica se o problema é inviável:
if (z ~= 0)
 estado = -1;
 xx = zeros(n+m,1);
 xx = [x;s];
 xb = xx(base);
end
% Retorna:
 xx = zeros(n+m,1);
 xx = [x;s];
 xb = xx(base);
return;
Fase2.m
function [z, estado, d, xx, x, s, y, c_red, base, nbase, cont2] = chicofase2(A_aux, b, c_aux, m, n, xb, base, nbase, cont2)
% Fase 2 do simplex revisado para solucionar um problema de PL, com dicionário inicial viável, do tipo: 
% z = max ( c'x | Ax <= b ; x >= 0 )	
stop = false; % Condição inicial da variável 'stop', que indica se o algoritmo deve ser interrompido.
while ( stop == false ) 
	otimo = true; % Condição incial da variável 'otimo'. 
 
 % Incialmente dimensionamos e determinamos os conjuntos, matrizes e vetores: B, N, cb, cn	
	
 B = A_aux(:, base); % Cria matriz 'B' com as colunas "base" da matriz A_aux.
 N = A_aux(:, nbase); % Cria matriz 'N' com as colunas "nbase" da matriz A_aux.
 cb = c_aux(base, :); % Posicoes "base" do vetor c_aux fazem o vetor cb de custos das variaveis basicas.
 cn = c_aux(nbase, :); % Posicoes "nbase" do vetor c_aux fazem o vetor cn de custos das variaveis nao basicas.
	d = []; % Cria vetor 'd' vazio.
	
	% Agora calculamos os vetores de variaveis duais e de custos reduzidos: y e c_red
	
	y = B'\cb; % Calcula o vetor 'y' transposto de variaveis duais.
	c_red = (cn'-(y)'*N)'; % Calcula o vetor 'c_red' de custos reduzidos.
	
 % Então, verificamos se o ótimo foi encontrado:
 
 j = min(find(c_red > 0)); % Aloca em 'j' o indice do primeiro custo não negativo do vetor 'c_red' (Método Lexicográfico).
 cr_max = max(c_red); % Aloca o maior custo do vetor 'c_red'.
	a = N(:, j); % Cria o vetor 'a' de coeficientes da variável entrante, sendo a coluna j da matriz N.
 
	if ( cr_max > 0 ) % Teste do otimo. Verifica se o vetor 'c_red' tem pelo menos um termo positivo.
		otimo = false; 
	
	end
	
	if ( otimo == true ) % Se encontrar o ótimo:
 
 stop = true; % Interrompe o algoritmo.
 estado = 1; % Estado = 1 (existe um ótimo).
 
 end
	
	% Início das iterações: 
	
	if ( (stop == false) & (cont2 < 10000) )
 d = B\a; % Cálculo do vetor 'd'.
 
 if ( max(d) <= 0 ) % Testa para saber se 'd' é totalmente negativo.
 
 stop = true; % Se for verdade, interrompe o algoritmo.
 estado = 0; % Estado = 0 (o problema é ilimitado).
 d = d(1:n,:); % Vetor de direção extrema.
 break;
 end 
 
		% Verifica que variável sai da base:
 
 r = xb./d; % Teste da razão.
 r(r<0) = NaN; % Descarta qualquer valor negativo do vetor 'r'.
 [t,i] = min(r); % Aloca valor minimo de 'r' na variavel 't' e seu indice na variavel 'i'.
 % Atualiza a base:
 
 aux = base(i); % Aloca indice 'i' da base na variavel auxiliar "aux".
 base(i) = nbase(j); % Troca indice 'i' da base pelo indice 'j' de fora da base.
 nbase(j) = aux; % Troca indice 'j' de fora da base pelo indice 'i' da base alocado em "aux".
 % Atualiza o vetor de custos das variáveis básicas:
 
 aux2 = cb(i); % Aloca custo da varivavel que sai da base de 'cb' na variavel auxiliar "aux2".
 cb(i) = cn(j); % Troca o custo da variavel que sai da base de 'cb' pelo custo da variavel que entra na base de 'cn'.
 cn(j) = aux2; % Troca o custo da variavel que entra na base de 'cn' pelo custo da variavel que sai da base de 'cb'.
 % Atualiza o vetor de variáveis básicas:
 
 xb = xb - t*d; % Atualiza xb, zerando a variavel que sai da base em xb de indice 'i'.
 xb(i) = t; % Troca as variaveis em xb, substituindo o valor da variavel que sai (zero) 
 % pelo da variavel que entra (t).
 cont2 = cont2 + 1; % Contagem de iterações.
 
 end
 % Verifica se o algoritmo alcançou o número máximo de iterações:
 
 if ( (stop == false) & (cont2 >= 10000) )
 
 stop = true; 
 estado = -2;
 d = d(1:n,:);
 break;
 
 end
 
end
cont = cont2; % Atualização do contador.
xx = zeros(n+m,1);
xx(base) = xb; % Cria vetor 'xx' com as variáveis básicas e não básicas.
% Retorno da função;
y = B'\cb; % Retorna o vetor de variáveis duais.
z = y'*b % Retorna o valor ótimo da função objetivo.
estado; % Retorna o estado do problema.
xx; % Retorna o vetor de variáveis básicas e não básicas.
x = xx(1:n); % Retorna o ponto ótimo x*.
s = xx((n+1):(n+m),1); % Retorna o vetor das folgas.
d = B\a; 								
d = -d; % Retorna o vetor de direção extrema.
c_red; % Retorna o vetor de custo reduzido.
base; % Retorna o vetor de índices relativos às variáveis básicas.
nbase; % Retorna o vetor de índices relativos às variáveis não básicas.
cont2; % Retorna o número de iterações.
return;
Simplexrev.m
function [z, x, s, y, estado, base, nbase, d, c_red, cont] = chicosimplexrev(A, b, c)
% Essa função resolve um problema de PL da seguinte forma:
% z = max (c'x | Ax <= b, x >= 0) 
% Verificações iniciais:
[m n] = size(A); % Dimensiona a matriz A.
% Confere as dimensões dos vetores 'b' e 'c':
if ( sum(size(c)) ~= (n+1) )
 fprintf('Existe um erro na dimensão do vetor c! \n');
 return;
end
if ( sum(size(b)) ~= (m+1) )
 fprintf('Existe um erro na dimensão do vetor b! \n');
 return;
end
% Início do simplex revisado:
if ( min(b) < 0 ) % Verifica se deve executar a fase 1.
 
 % Executa a fase 1:
 
 [z, estado, d, x, s, y, c_red, base, nbase, cont, xb] = chicofase1(A, b, c, m, n);
 
 % Verifica se o problema é inviável:
 
 if (estado == -1)
 fprintf('O problema é inviável! \n');
 fprintf('O estado do problema é: %d \n',estado);
 fprintf('A ultima solução foi: \n');
 x
 fprintf('O valor de w é igual a %d \n', -z);
 return;
 end; 
 A_aux1 = [A, eye(m)];
% Cria a matriz A_aux1 concatenando a matriz A com a Identidade (com folgas).
 c_aux1 = vertcat(c, zeros(m,1)); % Cria o vetor de custos 'c_aux1' referente a função objetivo do problema auxiliar.
 % Então, executa-se a fase 2 do simplex revisado:
 
 [z, estado, d, xx, x, s, y, c_red, base, nbase, cont2] = chicofase2(A_aux1, b, c_aux1, m, n, xb, base, nbase, cont);
 
 cont = cont2; % Atualiza o contador.
 
else
 % Caso não seja nescessária a fase, executa-se direto a fase 2.
 % Atribuições iniciais:
 cont = 0; % Condição inicial do contador de iterações.
 
 base = [n+1:n+m];								% Cria conjunto de indices das variaveis básicas.
 nbase = [1:n];									% Cria conjunto de indices das variaveis não básicas.
 A_aux = [A, eye(m)];							% Cria a matriz 'A_aux' concatenando a matriz A com a Identidade (com folgas).
 c_aux = vertcat(c, zeros(m,1));					% Cria o vetor de 'c_aux' concatenando o vetor 'c' com m zeros.
 B = A_aux(:, base); 						% Cria a matriz B de coeficientes das variáveis básicas.
 N = A_aux(:, nbase); 							% Cria a matriz N de coeficientes das variáveis não básicas.
 xb = B\b; 										% xb = (B^-1)*b ; Calcula o vetor xb de variaveis basicas.
 xn = zeros(n,1); 								% xn = 0 ; Cria o vetor xn de variaveis não básicas iguais a 0.
 % Executa a fase 2 do simplex revisado:
 
 [z, estado, d, xx, x, s, y, c_red, base, nbase, cont2] = chicofase2(A_aux, b, c_aux, m, n, xb, base, nbase, cont);
 cont = cont2; % Atualiza o contador de iterações.
end
% Imprime os resultados nas páginas:
if (estado == 1)
 
 fprintf('Existe ponto ótimo! \n');
 fprintf('O valor ótimo da função objetivo: z = %f. \n', z);
 fprintf('O estado do problema é: %d. \n', estado);
 fprintf('O ponto ótimo: \n');
 x
 fprintf('Vetor de folgas das restrições: \n');
 s
 fprintf('Vetor de variáveis duais associadas às restrições: \n');
 y
 fprintf('Vetor de custos reduzidos é: \n');
 c_red
 fprintf('Vetor de índices relativos às variáveis básicas: \n');
 base
 fprintf('Vetor de índices relativos às variáveis não básicas: \n');
 nbase
 fprintf('Número de iterações: %d \n', cont);
 
elseif (estado == 0)
 fprintf('O problema é ilimitado! \n');
 fprintf('O estado do problema é: %d \n', estado);
 fprintf('Último valor da função objetivo encontrado: %d \n', z);
 fprintf('O vetor de direção extrema é: \n');
 d = d(1:n,:)
 
elseif (estado == -2)
 fprintf('O numero maximo de iterações foi atingido! \n');
 fprintf('O algoritmo foi interrompido! \n');
end