SHARE
TWEET

Algoritmo Simplex

a guest Mar 28th, 2019 83 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Universidade Federal do Rio Grande do Norte
  2. // Centro de Tecnologia
  3. // Programa de Pós-graduação em Engenharia Elétrica
  4. // Aluno: Evandson Claude Seabra Dantas
  5. // Matrícula: 20191003111
  6.  
  7. // Apaga as variáveis do Scilab e limpa a tela
  8. clear; clc; funcprot(0);
  9.  
  10. // Tipo de problema
  11. // 1 = Maximização
  12. // 0 = Minimização
  13. tipo = 1;
  14.  
  15. // Função objetivo
  16. // z = x1 x2 x3 ...
  17. z = [2 1];
  18.  
  19. // Restrições
  20. xij = [1 0;
  21.        0 1;
  22.        1 3];
  23.        
  24. // Sinal das desilgualdades
  25. // -1 representa <=
  26. // 0 representa =
  27. // +1 representa >=
  28. s = [ -1;
  29.       -1;
  30.       +1];
  31.  
  32. // Sinal das desilgualdades
  33. b = [+3;
  34.      +4;
  35.      +13];
  36.  
  37.      
  38. // ==================================================================
  39. // A PARTIR DAQUI NÃO PRECISA ALTERAR MAIS NADA
  40. // ==================================================================
  41. // ALGORITMO SIMPLEX (SEMPRE MAXIMIZAR)
  42. // s_objetivo (caracter) : Letra correspondente a função objetivo
  43. // s_M = Matriz expandida do Simplex
  44. // s_imprime = 1 -> Imprime o passo-a-passo
  45. // s_imprime = 0 -> Imprime apenas o resultado final
  46. // H -> Matriz resolvida
  47. // Bases -> Variáveis básicas encontradas
  48. function [H, bases] = simplex(s_objetivo, s_M, bases, s_imprime)
  49.     m = size(s_M, 1) - 1; // Exclui a linha da função objetivo
  50.     n = size(s_M, 2) - 2; // Exclui a coluna z e a coluna b.
  51.     p_col = -1;
  52.     passo = 0;
  53.     while(p_col<0)
  54.        
  55.         // Política gulosa (maior peso na função objetivo)
  56.         [p_col, col] = min(s_M(1,2:n+1));
  57.        
  58.         // Vetor de divisão
  59.         vdiv = s_M(2:m+1,col+1);
  60.        
  61.         // Troca os zeros por NaN (Not a Number)
  62.         vdiv(vdiv==0) = %nan;
  63.        
  64.         // Calcula os fatores limitantes
  65.         q = s_M(2:m+1,n+2)./vdiv;
  66.        
  67.         // Copia os fatores limitantes
  68.         qnn = q;
  69.        
  70.         // Troca os NaN por Inf
  71.         qnn(isnan(qnn)) = %inf;
  72.  
  73.         // Substitui fatores limitantes negativos por valores infinitos positivos
  74.         qnn(q<0) = %inf;
  75.         // Procura pelo menor valor de q
  76.        
  77.         [q_min, lin] = min(qnn);
  78.         // Corrige a linha em função da primeira linha (função objetivo)
  79.        
  80.         // Separa o elemento pivo
  81.         pivo = s_M(lin+1,col+1);
  82.    
  83.         // Imprime a matriz M
  84.        // ===========================================
  85.        if (s_imprime > 0)
  86.             passo = passo + 1;
  87.             mprintf('\n\n Passo %d:\n ',passo);
  88.             for v = 1:(33+n*10), mprintf('-');end;
  89.             mprintf('\n | Fator Limitante | Base | %c |',s_objetivo);
  90.             for v = 1:n, mprintf('   x%d   |',v);end;    
  91.             mprintf('   b    |\n |                 |      |');
  92.             for v = 1:(7+n*10), mprintf('-');end;
  93.             mprintf('\n |                 |      | 1 |');
  94.             for v = 1:(n+1), mprintf(' %6.2f |',s_M(1,1+v));end;  
  95.             mprintf('\n ');
  96.             for v = 1:(33+n*10), mprintf('-');end;
  97.             mprintf('\n ');
  98.             // ===========================================
  99.             for v = 1:length(q)
  100.                 if(isnan(q(v))) then
  101.                   mprintf('|        Infinito |  x%d  | 0 |',bases(v));
  102.                 else
  103.                   mprintf('| %15.2f |  x%d  | 0 |',q(v),bases(v));  
  104.                 end
  105.               for k = 1:(n+1)
  106.                 mprintf(' %6.2f |',s_M(1+v,1+k));
  107.               end
  108.               mprintf(' \n ');
  109.             end
  110.             for v = 1:(33+n*10), mprintf('-');end;
  111.             mprintf('\n');    
  112.             // ===========================================
  113.             mprintf(' Coluna Pivotal: %d\n',col);
  114.             mprintf(' Linha Pivotal: %d\n',lin);
  115.             mprintf(' Pivô: %.2f\n\n',pivo);
  116.             mprintf(' Operações:\n');
  117.         end
  118.        
  119.         if (isinf(q_min)) then
  120.             disp(' Não há convergência para estes parâmetros! ');
  121.             abort;
  122.         end
  123.        
  124.         // Lista as linhas a serem atualizadas
  125.         atualizar = 1:m+1;   // Para todas as linhas
  126.         atualizar(lin+1) = []; // Excerto a linha pivotal
  127.  
  128.         // Para cada linha da tabela...
  129.         for i = atualizar
  130.            // Calcula o escalar
  131.            alpha = s_M(i,col+1)./pivo;
  132.            s_M(i,:) = s_M(i,:) - alpha*s_M(lin+1,:);
  133.            if (s_imprime > 0)
  134.             mprintf(' L%d = L%d - %.2f*L%d\n',i-1,i-1,alpha,lin);
  135.            end
  136.         end
  137.  
  138.         // Atualiza a linha pivotal por ultimo
  139.         s_M(lin+1,:) = s_M(lin+1,:)./pivo;
  140.         if (s_imprime > 0)
  141.             mprintf(' L%d = %.2f*L%d\n\n\n ',lin,1/pivo,lin);
  142.         end
  143.         // Troca as bases
  144.         bases(lin) = col;
  145.        
  146.     end
  147.     // Copia a matriz resolvida
  148.     H = s_M;
  149. endfunction
  150.  
  151. // Verifica se existem erros de digitação
  152. if (2*size(xij,1)~=length(s)+length(b)) then
  153.     error('O número de linhas, sinais e desigualdades não coincidem');
  154. end
  155.  
  156. // ==================================================================
  157. // Imprime o sistema de equações
  158. mprintf('Função Objetivo: \n ');
  159. if (tipo>0) then
  160.     mprintf('Maximizar ');
  161. else
  162.     mprintf('Minimizar ');    
  163. end
  164. mprintf(' z = ');
  165. for i = 1:length(z)
  166.     if(z(i)~=0) then
  167.       mprintf(' + (%.2f)x%d',z(i),i);
  168.     end    
  169. end
  170. mprintf('\n\n');
  171. for lin = 1:size(xij,1)
  172.     for col = 1:size(xij,2)
  173.         if(xij(lin,col)~=0) then
  174.             mprintf(' + (%.2f)x%d',xij(lin,col),col);
  175.         end
  176.     end
  177.     if (s(lin)<0) then
  178.         mprintf(' ≤ ');
  179.     elseif (s(lin)>0) then
  180.         mprintf(' ≥ ');
  181.     else
  182.         mprintf(' = ');
  183.     end
  184.      mprintf('%.2f\n',b(lin));
  185. end
  186.  
  187. // Fim da impressão do sistema de equações
  188. // ==================================================================
  189.  
  190. // Tira qualquer negatividade do segundo membro da equação
  191. for lin = 1:length(s)
  192.     if (b(lin) < 0) then
  193.        b(lin) = -b(lin);
  194.        s(lin) = -s(lin); // troca o sinal da desigualdade
  195.        xij(lin,:) = -xij(lin,:);
  196.     end
  197. end
  198.  
  199. // Copia a matriz
  200. M = xij;
  201.  
  202. // Trata as restrições de sinais (expandindo a matriz)
  203. // Armazena as posições das variáveis básicas
  204. bases = [];
  205. // Armazena as posições das variáveis artificiais
  206. v_artificiais = [];
  207. for i = 1:length(s)
  208.     if (s(i) < 0) then
  209.         // Adiciona uma variável de folga
  210.         M(i,size(M,2)+1) = 1;
  211.         // Adiciona a posição da base
  212.         bases = [bases size(M,2)];
  213.     elseif (s(i) == 0)
  214.         // Adiciona uma variável artificial
  215.         M(i,size(M,2)+1) = 1;
  216.         // Salva a posição da variável artificial
  217.         v_artificiais = [v_artificiais size(M,2)];
  218.         // Adiciona a posição da base
  219.         bases = [bases size(M,2)];
  220.     elseif (s(i) > 0)
  221.         // Adiciona uma variável de folta e uma artificial
  222.         M(i,size(M,2)+[1 2]) = [-1 1];
  223.         // Salva a posição da variável artificial
  224.         v_artificiais = [v_artificiais size(M,2)];
  225.         // Adiciona a posição da base
  226.         bases = [bases size(M,2)];
  227.     end
  228. end
  229.  
  230. // Obtém m e n
  231. m = size(M, 1);
  232. n = size(M, 2);
  233.  
  234. // Completa a função objetivo com zeros (variáveis básicas)
  235. z = [z zeros(1,n-length(z))];
  236.  
  237. // Após adicionar as variáveis de folga e artificiais a super matriz
  238. // Adiciona-se a igualdade
  239. M = [M b];
  240. // Adiciona a coluna referente ao eixo Z
  241. M = [zeros(m,1) M];
  242. // Adiciona a linha referente ao eixo Z trantado o tipo (maximizar ou minimizar)
  243. M = [1 ((-1)^(tipo>0)).*z 0;M];
  244.  
  245. // Relatório Inicial
  246. mprintf(' =======================\n');
  247. mprintf('  Sistema de Equações\n');
  248. mprintf(' =======================\n');
  249. for v = 1:(m+1)
  250.     mprintf(' (%2.f)z',M(v,1));
  251.     for k = 2:(n+1)
  252.         mprintf(' + (%2.f)x%d',M(v,k),k-1);
  253.     end
  254.     mprintf(' = (%2.f)\n',M(v,n+2));
  255. end
  256. mprintf('\n ');
  257.  
  258. // Verifica se vai logo para o Simplex ou tem variáveis auxiliares
  259. // para resolver antes
  260. if (v_artificiais~=[]) then
  261.     disp('Método da Duas Etapas primeiro!');
  262.     disp('Objetivo: Zerar as variáveis artificiais');
  263.     disp('Objetivo: Minimizar w: ');
  264.    
  265.     // Cria a nova função objetivo
  266.     w = zeros(1,n);
  267.     w(v_artificiais) = 1;
  268.    
  269.    // Imprime a nova função objetivo
  270.     mprintf(' w = ');
  271.     for i = 1:length(w)
  272.         if(w(i)~=0) then
  273.           mprintf(' + (%.2f)x%d',w(i),i);
  274.         end    
  275.     end
  276.     mprintf('\n ');
  277.    
  278.     // Copia a mega-matriz
  279.     M2 = M;
  280.    
  281.     // Substitui a função objetivo original pela nova função objetivo
  282.     M2(1,:) = [1 w 0];
  283.    
  284.     // Em função da variável não básica
  285.     M2(1,:) = M2(1,:) - M2(m+1,:);
  286.    
  287.     // Roda o SIMPLEX para minimizar w
  288.     [M2, bases] = simplex('w', M2, bases, 1);
  289.  
  290.     // Substitui a função objetivo pela original
  291.     M2(1,:) = M(1,:);
  292.  
  293.     // Exclui as colunas pivotais
  294.     M2(:,v_artificiais+1) = [];
  295.  
  296.     // Atualiza a super matriz original (sem as variáveis artificiais)
  297.     M = M2;
  298.  
  299.     // Atualiza n (removendo as variáveis artificiais)
  300.     n = size(M, 2) - 2;
  301.  
  302. end
  303. disp(' ');
  304. disp('Simplex!');
  305. disp('===================================================');
  306. [M, bases] = simplex('z',M, bases, 1);
  307. disp('===================================================');
  308. disp('Resultados ótimos encontrados: ');
  309.  
  310. // Imprime a melhor solução
  311. // Verifica se existem múltiplas soluções
  312.  if (tipo>0) then
  313.      mprintf('\n\tMax z = %.2f\n\n',M(1,n+2));
  314.  else
  315.      mprintf('\n\tMin z = %.2f\n\n',M(1,n+2));
  316.  end
  317.  mprintf(' Com variáveis básicas: \n');
  318.  for i = 1:length(bases)
  319.      mprintf('\tx%d = %.2f\n',bases(i),M(i+1,n+2));
  320.  end
  321.  
  322. // Procura pelas variáveis NÃO-BÁSICAS
  323. nao_bases = 1:n;
  324. // Devido a um bug do Scilab temos que usar bases' se não a variável
  325. // bases muda o seu valor.
  326. nao_bases(bases') = [];
  327. if sum(M(1,1+nao_bases)==0) then
  328.     disp('Opa! Existem outras soluções para este problema.');
  329.     disp('-------------------------------');
  330.     var_nao_bases_nulas = nao_bases(M(1,1+nao_bases)==0);
  331.     for outra_base = var_nao_bases_nulas
  332.         // Subtrai a linha 0 pela linha que contém maior elemento na coluna da variável não-basica
  333.         [p_linha, linha] = max(M(2:m+1,outra_base));
  334.         // Trocando a Linha X pela Coluna Y
  335.         mprintf(' Coluna Pivotal: %d\n ',outra_base);
  336.         mprintf('Linha Pivotal: %d\n ',linha);
  337.         mprintf('Pivô: %d\n ',M(1+linha,1+outra_base));
  338.         mprintf('Nova solução: ');
  339.         atualizar = 1:m+1;   // Para todas as linhas
  340.         atualizar(linha+1) = []; // Excerto a linha pivotal
  341.         for i = atualizar
  342.            // Calcula o escalar
  343.            alpha = M(i,outra_base+1)./M(1+linha,1+outra_base);
  344.            M(i,:) = M(i,:) - alpha*M(linha+1,:);
  345.         end
  346.         // atualiza a linha pivotal
  347.         M(linha+1,:) = M(linha+1,:)./M(1+linha,1+outra_base);
  348.         // Atualiza as bases
  349.         bases(linha) = outra_base;
  350.        
  351.         if (tipo>0) then
  352.          mprintf('\n\tMax z = %.2f\n\n',M(1,n+2));
  353.          else
  354.              mprintf('\n\tMin z = %.2f\n\n',M(1,n+2));
  355.          end
  356.          mprintf(' Com variáveis básicas: \n');
  357.          for i = 1:length(bases)
  358.              mprintf('\tx%d = %.2f\n',bases(i),M(i+1,n+2));
  359.          end
  360.     end
  361.    
  362. end
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top