Notas de Aula - Métodos Quantitativos - Problemas de Localização de Facilidades e Algoritmos de Transporte

Notas de Aula da Disciplina de Métodos Quantitativos para Tomada de Decisão Prof Edgard Pedroso Arquivo de aulas n o 9 PLF nº e locais definidos algoritmo de transporte e heurística de Gillett Johnson Problemas de Localização de Instalações de Facilidades PLF Exemplos de Aplicação Localizações de Postos de saúde Creches Escolas Locais de Provas para o Vestibular Agências 24 horas Farmácias outros Observação Podemos aplicar os métodos do PLF pontos para centros de distribuições para formar primeiramente os clusters e em seguida dentro de cada cluster usar os métodos de roteamento Problemas de Localização de Facilidades PLF 1ª versão Se o número e a localização das instalações já estiverem definidos A Algoritmo de Transportes já bem conhecido fornece solução exata B Algoritmo de Gillett Johnson Modificado fornece solução heurística aproximada 1ª versão Se o nº e a localização das instalações já estiverem definidos Algoritmo de Transportes Solução Exata Exemplo Seja um problema c 8 ptos de demanda bairros das casas dos alunos e 3 instalações Escolas Ptos de Instalações e Demandas Demandas Capacidades de oferta E1 3 E2 5 E3 5 A1 2 A2 2 A3 2 A4 1 A5 2 A6 1 A7 1 A8 2 A2 E1 A1 A3 A4 E2 A5 A6 A7 A8 E3 2 1 2 1 2 1 2 2 5 5 3 Qual deverá ser a designação dos pontos de demanda alunos às instalações escolas Aplique o algoritmo de transporte Origens escolas Destinos bairros das casas dos alunos Capaci dades A1 A2 A3 A4 A5 A6 A7 A8 E1 5 2 5 9 11 16 13 10 3 E2 9 6 4 4 4 8 8 9 5 E3 9 7 9 11 12 14 7 3 5 Demandas 2 2 2 1 2 1 1 2 13 A solução inicial do Algoritmo de Transporte pode ser determinada por 1 Regra do Canto Noroeste 2 Método do Custo Mínimo 3 Método de Voguel Problema balanceado 1 Comece pela célula superior da esquerda 2 Ponha nessa célula a maior quantidade permitida pela oferta e demanda 3 Atualize os valores da oferta e da demanda que foram modificados pelo 2º passo 4 Siga para a célula da direita se houver alguma oferta restante e volte ao 2º passo Caso contrário siga para a célula inferior e volte para o 2º passo Origens escolas Destinos bairros das casas dos alunos Capaci dades A1 A2 A3 A4 A5 A6 A7 A8 E1 5 2 5 9 11 16 13 10 3 E2 9 6 4 4 4 8 8 9 5 E3 9 7 9 11 12 14 7 3 5 Demandas 2 2 2 1 2 1 1 2 13 Solução inicial do Algoritmo de Transporte determinada pela Regra do Canto Noroeste 2 1 1 2 0 0 4 0 0 1 1 2 1 0 1 1 1 0 1 0 4 1 0 3 1 0 2 2 0 0 Origens escolas Destinos bairros das casas dos alunos Capaci dades A1 A2 A3 A4 A5 A6 A7 A8 E1 5 2 5 9 11 16 13 10 3 E2 9 6 4 4 4 8 8 9 5 E3 9 7 9 11 12 14 7 3 5 Demandas 2 2 2 1 2 1 1 2 13 Solução inicial do Algoritmo de Transporte determinada pela Regra do Canto Noroeste 2 1 2 1 1 1 1 1 1 2 Custo2x51x21x62x41x41x41x121x141x72x373 Origens escolas Destinos bairros das casas dos alunos Capaci dades A1 A2 A3 A4 A5 A6 A7 A8 E1 5 2 5 9 11 16 13 10 3 E2 9 6 4 4 4 8 8 9 5 E3 9 7 9 11 12 14 7 3 5 Demandas 2 2 2 1 2 1 1 2 13 Solução inicial do Algoritmo de Transporte determinada pela Método do Custo Mínimo 2 0 1 2 1 Localize no quadro a célula que contém o menor custo que não tenha oferta ou demanda nula 2 Coloque nessa célula a maior quantidade permitida pela oferta e demanda correspondentes 3 Atualize os valores da oferta e da demanda que foram modificados pelo 2º passo e volte ao 1º passo 0 3 2 0 3 1 0 2 2 0 0 1 1 1 1 2 0 1 0 0 0 0 1 Origens escolas Destinos bairros das casas dos alunos Capaci dades A1 A2 A3 A4 A5 A6 A7 A8 E1 5 2 5 9 11 16 13 10 3 E2 9 6 4 4 4 8 8 9 5 E3 9 7 9 11 12 14 7 3 5 Demandas 2 2 2 1 2 1 1 2 13 Solução inicial do Algoritmo de Transporte determinada pela Método do Custo Mínimo 2 2 2 1 2 1 1 1 1 Custo 1x52x22x41x42x41x91x141x72x3 65 Solução inicial do Algoritmo de Transporte determinada pelo Método de Voguel Atenção Implementado modificado para decidir sobre os desempates entre penalidades iguais Origens escolas Destinos bairros das casas dos alunos Capaci dades Penali dades A1 A2 A3 A4 A5 A6 A7 A8 E1 5 2 5 9 11 16 13 10 3 E2 9 6 4 4 4 8 8 9 5 E3 9 7 9 11 12 14 7 3 5 Demandas 2 2 2 1 2 1 1 2 13 Penali dades 3 1 0 2 0 0 0 Em cada linha verifique a diferença de custo entre o menor valor e o segundo menor Em cada coluna verifique a diferença de custo entre o menor valor e o segundo menor Na linha ou coluna correspondente à maior de todas as variações selecione a célula de menor custo e coloque aí a maior quantidade permitida pela oferta e demanda correspondentes Atualize as ofertas e demandas Se na linha a oferta é zerada cancele a linha e volte para 2º passo Se na coluna a demanda é zerada cancele a coluna e volte para 1º passo e em seguida ao 3º passo 0 4 4 4 1 5 7 6 1 6 2 3 0 1 2 3 1 2 1 2 1 1 1 6 0 1 0 2 0 2 0 4 0 1 1 0 0 4 0 0 1 1 0 0 Regra implementada Sempre que houver empate nas penalidades entre linhas eou colunas será dada prioridade de designação à linha ou coluna que tiver o menor custo Origens escolas Destinos bairros das casas dos alunos Capaci dades A1 A2 A3 A4 A5 A6 A7 A8 E1 5 2 5 9 11 16 13 10 3 E2 9 6 4 4 4 8 8 9 5 E3 9 7 9 11 12 14 7 3 5 Demandas 2 2 2 1 2 1 1 2 13 Solução inicial do Algoritmo de Transporte determinada pelo Método de Voguel modificado 1 2 2 1 2 1 1 1 1 1 Custo1x52x21x41x42x41x81x91x91x72x364 Origens escolas Destinos bairros das casas dos alunos Capaci dades A1 A2 A3 A4 A5 A6 A7 A8 E1 5 2 5 9 11 16 13 10 3 E2 9 6 4 4 4 8 8 9 5 E3 9 7 9 11 12 14 7 3 5 Demandas 2 2 2 1 2 1 1 2 13 1 2 2 1 2 1 1 1 1 1 Solução Algoritmo de Transporte pelo Método Dual UV a partir da solução inicial dada pelo método de Voguel Modificado Não Básicas Var 0 Básicas Var j i ij j i ij v u c v u c Entra na base a variável de maior custo relativo Positivo pmin V B x11 x12 X23 x24 x25 x26 x31 x33 x37 x38 Coeficiente c11u1v10 c12u1v20 c23u2v30 c24u2v40 c25u2v50 c26u2v60 c31u3v10 c33u3v30 c37u3v70 c38u3v80 Substituindo Cij 5u1v10 2u1v20 4u2v30 4u2v40 4u2v50 8u2v60 9u3v10 9u3v30 7u3v70 3u3v80 Arbitrando u10 v1 5 v2 2 u2 1 v4 5 v5 5 v6 9 u3 4 v3 5 v7 3 v8 1 V NB x13 x14 x15 x16 x17 x18 x21 x22 x27 x28 x32 x34 x35 x36 Coeficiente c13u1v3 c14u1v4 c15u1v5 c16u1v6 c17u1v7 c18u1v8 c21u2v1 c22u2v2 c27u2v7 c28u2v8 c32u3v2 c34u3v4 c35u3v5 c36u3v6 Valor 505 0 905 4 1105 6 1609 7 1303 10 1001 11 915 5 612 5 813 6 911 11 742 1 1145 2 1245 3 1449 1 Regra de Parada Todos custos relativos das variáveis não básicas são negativos ou zeros pmin OBS Coincidente mente a regra de parada ocorreu já ao final da primeira iteração Solução do Problema de Localização de Facilidades PLF Aplicando o Algoritmo de Transporte E1 A1 A2 E2A3A4A5A6 E3A1A3A7A8 Custo 64 1 1 1 2 2 1 1 1 Origens escolas Destinos bairros das casas dos alunos Capaci dades A1 A2 A3 A4 A5 A6 A7 A8 E1 5 2 5 9 11 16 13 10 3 E2 9 6 4 4 4 8 8 9 5 E3 9 7 9 11 12 14 7 3 5 Demandas 2 2 2 1 2 1 1 2 13 1 2 2 1 2 1 1 1 1 1 Custo1x52x21x41x42x41x81x91x91x72x3 64 Solução do Problema de Localização de Facilidades PLF Aplicando o Algoritmo de Transporte E1 A1 A2 E2A3A4A5A6 E3A1A3A7A8 Custo 64 1 1 1 2 2 1 1 1 Origens escolas Destinos bairros das casas dos alunos Capaci dades A1 A2 A3 A4 A5 A6 A7 A8 E1 5 2 5 9 11 16 13 10 3 E2 9 6 4 4 4 8 8 9 5 E3 9 7 9 11 12 14 7 3 5 Demandas 2 2 2 1 2 1 1 2 13 1 2 2 1 2 1 1 1 1 1 Custo1x52x21x41x42x41x81x91x91x72x3 64 A2 E1 A1 A3 A4 E2 A5 A6 A7 A8 E3 2 1 2 1 2 1 2 2 5 5 3 GRUPOS CLUSTERS E1 A1 A2 E2A3A4A5A6 E3A1A3A7A8 Custo 64 Software LINDO LP OPTIMUM FOUND AT STEP 12 OBJECTIVE FUNCTION VALUE 1 6400000 VARIABLE VALUE REDUCED COST X11 1000000 0000000 X12 2000000 0000000 X13 0000000 0000000 X14 0000000 4000000 X15 0000000 6000000 X16 0000000 7000000 X17 0000000 10000000 X18 0000000 11000000 X21 0000000 5000000 X22 0000000 5000000 X23 1000000 0000000 X24 1000000 0000000 X25 2000000 0000000 X26 1000000 0000000 X27 0000000 6000000 X28 0000000 11000000 X31 1000000 0000000 X32 0000000 1000000 X33 1000000 0000000 X34 0000000 2000000 X35 0000000 3000000 X36 0000000 1000000 X37 1000000 0000000 X38 2000000 0000000 B Se o nº e a localização das instalações já estiverem definidos Algoritmo de Gillett Johnson Modificado Solução Heurística Origens escolas t i Destinos i bairros Capacidades A1 A2 A3 A4 A5 A6 A7 A8 E1 5 2 5 9 11 16 13 10 3 E2 9 6 4 4 4 8 8 9 5 E3 9 7 9 11 12 14 7 3 5 Demandas 2 2 2 1 2 1 1 2 13 Diferenças 4 4 1 5 7 6 1 6 1 Inicialmente todos os nós de demanda encontramse sem designação 2 Para cada nó i seja ti a instalação mais próxima a i e ti a segunda instalação mais próxima a i 3 Para cada nó i a diferença difi citi citi é calculada e a ordem decrescente dos valores das difi determinam a ordem na qual os nós serão designados a uma instalação ou seja os nós com maior difi são designados antes dos de menor difi Maior diferença significa maior urgência nas designações Solução Aproximada 3 A designação dos nós às instalações é feita obedecendose a capacidade das instalações 4 Quando algum nó for designado para uma instalação e sua demanda total ou parte dela esgota a capacidade da instalação recalculase a diferença difi para todos os nós ainda não designados ou já designados mas com a demanda parcialmente atendida desconsiderandose as instalações com capacidades já esgotadas e recomeçase o processo até que todos os nós sejam designados e suas demandas totalmente atendidas Origens escolas Destinos bairros Capacidades A1 A2 A3 A4 A5 A6 A7 A8 E1 5 2 5 9 11 16 13 10 3 E2 9 6 4 4 4 8 8 9 5 E3 9 7 9 11 12 14 7 3 5 Demandas 2 2 2 1 2 1 1 2 13 Diferenças 4 4 1 5 7 6 1 6 Ordem Urgência 1 Ordem Urgência 2 Ordem Urgência 3 2 3 2 0 2 3 0 0 0 2 1 1 1 1 5 1 0 0 1 2 0 0 0 1 0 1 1ª 1 3ª 1 2ª 0 1 0 1 0 0 1 Atenção Sempre que houver empate entre as diferenças será dada prioridade de designação à diferença relativa a coluna que tiver o menor custo 1º 2º 3º 4º 5º 6º Origens escolas Destinos bairros Capacidades A1 A2 A3 A4 A5 A6 A7 A8 E1 5 2 5 9 11 16 13 10 3 E2 9 6 4 4 4 8 8 9 5 E3 9 7 9 11 12 14 7 3 5 Demandas 2 2 2 1 2 1 1 2 13 2 2 1 1 1 1 2 1 1 1 Custo 1x52x21x41x42x41x81x91x91x72x3 64 E1 A1 A2 E2A3A4A5A6 E3A1A3A7A8 Custo 64 Valor ótimo por coincidência pois é uma heurística e então não há a certeza da obtenção da solução ótima A2 E1 A1 A3 A4 E2 A5 A6 A7 A8 E3 2 1 2 1 2 1 2 2 5 5 3 GRUPOS CLUSTERS E1 A1 A2 E2A3A4A5A6 E3A1A3A7A8 Custo 64 Notas de Aula Prof Edgard 1 Arenales M Armentano V Morabito R E Yanasse H Pesquisa Operacional para cursos de Engenharia Editora Campus Rio de Janeiro 2007 2 Bodin L Golden B Assad A and Ball M Routing and Scheduling of veicles and crews Special edition of Computer and Operations Research col 10 n2 1983 3 Bronson R Pesquisa Operacional São Paulo Schaum McGrawHill do Brasil Ltda 1985 4 Goldbarg M C e Luna H P Otimização Combinatória e Programação Linear Modelos e Algoritmos Editora Campus Rio de Janeiro 2000 5 Hillier F S e Lieberman G J Introdução à Pesquisa Operacional traduzido McGrawHill São Paulo 2006 6 Murty K Linear and Combinatorial Programming Robert E Krieger Publishing Company Malabar Florida 1985 7 Puccini A de L e Pizzolato N D Programação Linear Livros Técnicos e Científicos Ed Ltda Rio de Janeiro 1990 Importante Este material tem finalidade única e exclusivamente didática e serve apenas como notas de apoio às aulas da disciplina de Métodos Quantitativos para Tomada de Decisão do curso de Graduação de Engenharia de Produção Este material não pode ser utilizado como referência bibliográfica e muito menos comercialmente Recomendase consultar as seguintes obras