Slide - Programação Inteira - 2024-1

PROBLEMA DE COBERTURA Características: As variáveis de decisão são binárias. Os coeficientes do lado esquerdo das restrições são 0 (zero) ou 1. O lado direito das restrições é do tipo >= 1. A função objetivo é do tipo: min c1x1 + ... + cnxn. EXEMPLO 1. 1-O departamento de segurança do campus de uma universidade pretende instalar guaritas de segurança nas 11 ruas do campus, conforme o diagrama a seguir, onde Tj (j=1,...,8) representa uma possível localização de guarita. Minimizar o número de guaritas instaladas, tendo como exigência a existência de no mínimo uma guarita atendendo cada uma das 11 ruas. PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) PROBLEMA DA COBERTURA EXEMPLO 1. PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) PROBLEMA DA COBERTURA SOLUÇÃO EXEMPLO 1. PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) PROBLEMA DA COBERTURA SOLUÇÃO EXEMPLO 1. PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) PROBLEMA DA COBERTURA SOLUÇÃO EXEMPLO 1. Número mínimo de guaritas PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) PROBLEMA DA COBERTURA EXEMPLO 2. A CEARS – Cia de Estoques Agrícolas do Estado do Rio Grande do Sul está avaliando uma série de localidades no estado do Rio Grande do Sul para construir 3 novos armazéns agrícolas. A CEARS está interessada em encontrar as 3 localidades para construir seus armazéns de modo que o custo total de construção e logístico seja mínimo. A tabela a seguir mostra dados relativos aos armazéns e clientes. PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) PROBLEMA DA COBERTURA EXEMPLO 2 Custo logístico por tonelada entre armazém e destino Opção de localização do armazém Custo de construção ($ milhões) Capacidade (kton) Uruguaia na Pelotas Caxias Do Sul Passo Fundo Porto Alegre Alegrete 7 600 2,10 6,30 7,80 6,30 7,50 Caçapava 5 750 5,70 2,70 4,50 4,50 3,78 Tupanciretá 9 350 5,40 5,58 4,38 2,88 4,80 Vacaria 6 450 10,20 6,54 1,14 2,40 3,00 Santa Rosa 4 400 5,58 7,86 6,00 3,48 6,84 Demanda anual (milhares de Tonelada) 150 450 300 250 500 PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) PROBLEMA DA COBERTURA SOLUÇÃO EXEMPLO 2. Modelo: F.O. : Min C = 7000x1 + 5000x2 + 9000x3 + 6000x4 + 4000x5 + 2,1y11 + 6,3y12 + 7,8y13 + 6,3y14 + 7,5y15 + … + 6,84y55 s.a. y11 + y12 + y13 + y14 + y15 <= 600000x1 (Capacidade do armazém 1) y21 + y22 + y23 + y24 + y25 <= 750000x2 (Capacidade do armazém 2) y31 + y32 + y33 + y34 + y35 <= 350000x3 (Capacidade do armazém 3) y41 + y42 + y43 + y44 + y45 <= 450000x4 (Capacidade do armazém 4) y51 + y52 + y53 + y54 + y55 <= 400000x5 (Capacidade do armazém 5) y11 + y21 + y31 + y41 + y51 = 150000 (Demanda destino 1) y12 + y22 + y32 + y42 + y52 = 450000 (Demanda destino 2) y13 + y23 + y33 + y43 + y53 = 300000 (Demanda destino 3) y14 + y24 + y34 + y44 + y54 = 250000 (Demanda destino 4) y15 + y25 + y35 + y45 + y55 = 500000 (Demanda destino 5) x1 + x2 + x3 +x4 +x5 = 3. xj {0,1}, j=1,...,5 ∈ yij >= 0, i=1,...,5 PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) PROBLEMA DA COBERTURA SOLUÇÃO EXEMPLO 2. Modelo. Restrições: PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) PROBLEMA DA COBERTURA. SOLUÇÃO DO EXEMPLO 2. PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) PROBLEMA DA COBERTURA SOLUÇÃO EXEMPLO 2 PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) PROBLEMA DA COBERTURA P-MEDIANAS Método usado no problema da Localização de Facilidades ou Cobertura, que a partir de locais candidatos determina qual instalação atenderá qual ponto de demanda. MODELO: Exemplo 3: Para o conjunto de 8 pontos a seguir, deseja-se resolver o problema de Localização de Facilidades onde procura-se determinar duas localizações (p-medias) para melhor atender os clientes. Use p-medianas para resolver o problema. PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) PROBLEMA DA COBERTURA P-MEDIANAS SOLUÇÃO PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) PROBLEMA DA COBERTURA P-MEDIANAS SOLUÇÃO EXEMPLO 3: MATRIZ DISTÂNCIAS PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) PROBLEMA DA COBERTURA P-MEDIANAS SOLUÇÃO EXEMPLO 3: MODELO: PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) PROBLEMA DA COBERTURA P-MEDIANAS SOLUÇÃO EXEMPLO 3: EXCEL: PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) PROBLEMA DA COBERTURA P-MEDIANAS SOLUÇÃO EXEMPLO 3: EXCEL: São 64 (8 lin e 8 col) restrições do tipo Xij <= Yj e estas serão escritas diretamente no Solver do Excel PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) PROBLEMA DA COBERTURA P-MEDIANAS SOLUÇÃO EXEMPLO 3: EXCEL: No preenchimento das restrições em “Parâmetros do Solver”, a linha azul representa 8 restrições do tipo Xi1 <= Y1. De forma semelhante escreve-se outras 7 para Y2, Y3,...,Y8. O resultado obtido (figura abaixo) mostra que os pontos 4 e 5 serão as p-medianas, sendo que: (a) p-mediana 4 atende 4, 1, 2 e 7; (b) p- mediana 5 atende 5, 3, 6 e 8 PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) Suponha que barras de 10m de comprimento devam ser cortadas para atender pedidos de barras de 3m e 4m. Como cortar as barras de 10m a fim de minimizar as perdas e atender a demanda? Exemplos de padrões de corte possíveis: 1) 3m + 3m + 3m = 9m  perda = 1m : X1; a1=(3,0) (3 barras de 3m) 2) 4m + 4m = 8m  perda = 2m : X2; a2=(0,2) (2 barras de 4m) 3) 3m + 3m + 4m = 10 m  perda = 0 : X3; a3=(2,1) (2 b de 3m e 1 b de 4m) PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) Certa empresa trabalha com a produção de etiquetas autocolantes. O papel usado para sua confecção encontra-se em bobinas de mesmo comprimento. A largura das bobinas é de 50 cm. As encomendas para a próxima semana impõem a necessidade de se cortarem bobinas em tiras de: 32 bobinas de 15 cm de largura; 17 bobinas de 17,5 cm de largura e 21 bobinas de 20 cm de largura. É política da empresa manter em estoque o excedente ao pedido em quantidade máxima de 10 bobinas cortadas de acordo com a encomenda. Pede-se o esquema de corte de perda total mínima. EXEMPLO 3. PROBLEMA DE CORTE UNIDIMENSIONAL TAMANHOS – TIPO (i) PADRÕES DE CORTE (j) 1 2 3 4 5 6 15 cm 3 2 2 1 0 0 17,5 cm 0 1 0 2 1 0 20 cm 0 0 1 0 1 2 PERDA(cm) 5 2,5 0 0 12,5 10 xj = número de bobinas cortadas no padrão j, com j=1,...,6 aj = (a1j a2j a3j): vetor para o padrão de corte j, onde a1j = número de bobinas do tipo 1 (15 cm) no padrão j a2j = número de bobinas do tipo 2 (17,5 cm) no padrão j a3j = número de bobinas do tipo 3 (20 cm) no padrão j PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) SOLUÇÃO EXEMPLO 3. PROBLEMA DE CORTE UNIDIMENSIONAL PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) SOLUÇÃO EXEMPLO 3. PROBLEMA DE CORTE UNIDIMENSIONAL Min =5*x1+2.5*x2+12.5*x5+10*x6; SOLUÇÃO ÓTIMA: 3*x1+2*x2+2*x3+x4>=32; x1=x2=x5=0; x3=16; x4=9; x6=3 e 3*x1+2*x2+2*x3+x4<=42; PERDA= 30. x2+2*x4+x5>=17; PARA ESTOQUE: 9 BOBINAS DE x2+2*x4+x5<=27; 15 cm, 1 BOBINA DE 17,5 cm E x3+x5+2*x6>=21; 1 BOBINA DE 20 cm. x3+x5+2*x6<=31; X1,x2,x3,x4,x5,x6>=0 e inteiras; RESTRIÇÕES: PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) EXEMPLO 4. PROBLEMA DE CORTE UNIDIMENSIONAL Considere o problema onde temos barras de 9 m de comprimento e que devem ser convenientemente cortadas para obtermos barras menores, nos seguintes tamanhos: 50 barras de 2 m. 30 barras de 3 m. 40 barras de 4 m. Resolver o problema minimizando as sobras. TAMANHOS – TIPO (i) PADRÕES DE CORTE (j) 1 2 3 4 5 6 7 2 m 4 3 2 1 0 1 0 3 m 0 1 0 2 3 1 0 4 m 0 0 1 0 0 1 2 PERDA(m) 1 0 1 1 0 0 1 PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) SOLUÇÃO DO EXEMPLO 4. PROBLEMA DE CORTE UNIDIMENSIONAL PESQUISA OPERACIONAL II . PROF.: LEVI LOPES TEIXEIRA PROGRAMAÇÃO INTEIRA (PI) SOLUÇÃO DO EXEMPLO 4. PROBLEMA DE CORTE UNIDIMENSIONAL Min perdas = x1 +x3 + x4+x7 Solução Ótima: s.a. x2=30; x5=10; x6=50; perdas=0. Embora 4x1+3x2+2x3+x4+x6 >=50 as perdas=0, serão armazenadas 90 peças x2+2x4+3x5+x6>=30 de 2m, 80 peças de 3m e 10 peças de 4m. x3+x6+2*x7>=40; xj>=0 e int. Trocando o sinal “>=“ por “=“, obtém-se a seguinte solução ótima: x2=10; x6=20; x7=10; perdas=10. Neste caso as quantidades das peças de 2m, 3m e 4m não excedem as demandas, não sendo necessário o armazenamento. Porém, há uma perda de 10m.