Modelagem e Analise de Decisão - Problemas de Fluxo em Rede

2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Modelagem e Análise de Decisão Edição revisada Cliff T Ragsdale Virginia Polytechnic Institute e State University Modelagem e Análise de Decisão Edição revisada Cliff T Ragsdale 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Introdução Nas empresas diversos problemas de decisão prática podem ser representados graficamente como problemas de fluxo de rede Este capítulo enfoca diversos desses problemas Problemas de transbordo Problemas com caminho mais curto Problemas de fluxo de rede Problemas com transporteescolha Problemas de fluxos máximos 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Características dos Problemas de Fluxo de Rede Problemas de fluxo de rede podem ser representados como um conjunto de nós conectados por arcos Existem três tipos de nós Oferta Demanda Transbordo Números positivos representam a demanda de um dado nó e números negativos representam a oferta disponível nesse nó 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados O Problema de Transbordo Bavarian Motor Company Newark 1 Boston 2 Columbus 3 Atlanta 5 Richmond 4 Jville 7 Mobile 6 30 40 50 35 40 30 35 25 50 45 50 200 300 80 100 60 170 70 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Definindo as Variáveis de Decisão Para cada arco em um modelo de fluxo de rede é preciso definir uma variável de decisão como Xij o número de itens enviados ou escoados do nó i para o nó j Por exemplo X12 o número de veículos enviados do nó 1 Newark para o nó 2 Boston X56 o número de veículos enviados do nó 5 Atlanta para o nó 6 Mobile Nota O número de arcos determina o número de variáveis 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Definindo a Função Objetivo Minimizando os custos totais de envio MIN 30X12 40X14 50X23 35X35 40X53 30X54 35X56 25X65 50X74 45X75 50X76 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Restrições para Problemas de Fluxo de Rede Para problemas de custo mínimo Aplique essa regra de equilíbrio de fluxo de rede em que de fluxo de rede em cada nó Oferta Total Demanda Total EntradaSaída Oferta ou Demanda Oferta Total Demanda Total EntradaSaída Oferta ou Demanda Oferta Total Demanda Total EntradaSaída Oferta ou Demanda 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Definindo as Restrições No problema da BMC Oferta Total 500 carros Demanda Total 480 carros Ou seja em cada nó criaremos uma restrição na forma Entrada Saída Oferta ou Demanda Restrição para o nó 1 X12 X14 200 Nota Não há entradas para o nó 1 Isso é equivalente a X12 X14 200 Oferta Demanda 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Defininindo as Restrições Restrições de fluxo X12 X14 200 nó 1 X12 X23 100 nó 2 X23 X53 X35 60 nó 3 X14 X54 X74 80 nó 4 X35 X65 X75 X53 X54 X56 170 nó 5 X56 X76 X65 70 nó 6 X74 X75 X76 300 nó 7 Condições de não negatividade Xij 0 para todos os i e j 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Implementando o Modelo Veja o arquivo Fig52xls 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Solução Ótima para o Problema de Transbordo da BMC Newark 1 Boston 2 Columbus 3 Atlanta 5 Richmond 4 Jville 7 Mobile 6 30 40 50 40 50 45 200 300 80 100 60 170 70 120 80 20 40 70 210 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados O Problema do Caminho Mais Curto Em muitos problemas de decisão precisamos determinar a rota ou o caminho mais curto ou menos custoso em uma rede do nó inicial até o nó final Ex Rotas de veículos de emergência Esse é um caso especial de problema de transbordo onde Existe um nó de oferta com a oferta de 1 Existe um nó de demanda com a demanda de 1 Todos os outros nós têm ofertademanda de 0 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados A American Car Association 0 Bham Atlanta Gville Va Bch Charl Lburg Kville Aville Gboro Raliegh Chatt 1 2 3 4 6 5 7 8 9 10 11 25 hrs 3 pts 30 hrs 4 pts 17 hrs 4 pts 25 hrs 3 pts 17 hrs 5 pts 28 hrs 7 pts 20 hrs 8 pts 15 hrs 2 pts 20 hrs 9 pts 50 hrs 9 pts 30 hrs 4 pts 47 hrs 9 pts 15 hrs 3 pts 23 hrs 3 pts 11 hrs 3 pts 20 hrs 4 pts 27 hrs 4 pts 33 hrs 5 pts 1 1 0 0 0 0 0 0 0 0 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Resolvendo o Problema Existem dois objetivos possíveis para esse problema Encontrar a rota mais rápida minimizando o tempo de viagem Encontrar a rota com maior qualidade de cenários maximizando a qualidade do cenário 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Resolvendo o Problema cont Fig 57 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados O Problema de Substituição de Equipamento O problema de substituição de equipamento é bastante comum Pode ser modelado como o problema do caminho mais curto 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados CompuTrain Company A CompuTrain fornece software educacional prático e treinamento para empresas Os computadores precisam ser substituídos pelo menos a cada dois anos Dois contratos de arrendamentos estão sendo considerados Cada um requer inicialmente 62000 Contrato 1 Preços aumentam 6 ao ano Crédito por troca de 60 para equipamentos com 1 ano de uso Crédito por troca de15 para equipamentos com 2 anos de uso Contrato 2 Preços aumentam 2 ao ano Crédito por troca de 30 para equipamentos com um ano de uso Crédito por troca de 10 para equipamentos com 2 anos de uso 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Fluxo de Rede para o Contrato 1 1 3 5 2 4 1 1 0 0 0 28520 60363 30231 63985 32045 67824 33968 Depois de 1 ano 10662000 0662000 28520 Depois de 2 anos 106262000 01562000 60363 Etc 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Resolvendo o Problema Fig 512 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Problemas de Transporte e Distribuição Algumas vezes problemas de transportedistribuição são mais raros ou não totalmente interconectados Mt Dora 1 Eustis 2 Clermont 3 Ocala 4 Orlando 5 Leesburg 6 Distância em milhas Capacidade Oferta 275000 400000 300000 225000 600000 200000 Pomares Instalações de Processamento 21 50 40 35 30 22 55 25 20 Esse problema é melhor implementado utilizando a técnica descrita no Capítulo 3 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Problemas Generalizados de Fluxo de Rede Há diversos exemplos de problemas de fluxo de rede em que ocorrem ganhos ou perdas em fluxos através de arcos Examplos Envio de petróleo ou gás através de uma tubulação com problemas de vazamento imperfeições de matériaprima em processos de produção Evaporação de líquidos perdas de alimentos e outros itens perecíveis Esses problemas exigem algumas modificações de modelagem 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Coal Bank Hollow Recycling 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Fluxo de Rede para o Problema de Reciclagem Jornal 1 Papéis Diversos 2 3 Papelão 4 Processo de Reciclagem 1 5 6 Polpa para Papel jornal 7 8 9 70 50 30 40 60 40 50 Papel Sulfite 13 12 11 13 9 10 14 13 90 80 95 75 85 85 90 85 5 6 8 6 7 8 95 90 90 90 95 95 0 0 Processo de Reciclagem 2 Polpa para Papel de Embalagem Papel de Qualidade para impressão 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Definindo a Função Objetivo Minimizando o custo total MIN 13X15 12X16 11X25 13X26 9X35 10X36 13X45 14X46 5X57 6X58 8X59 6X67 8X68 7X69 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Definindo as Restrições I Materiais X15 X16 70 nó 1 X25 X26 50 nó 2 X35 X36 30 nó 3 X45 X46 40 nó 4 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Processos de Reciclagem 09X1508X25095X35075X45 X57 X58X59 0 nó 5 085X16085X2609X36085X46X67X68X69 0 nó 6 Definindo as Restrições II 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Polpa de papel 095X57 090X67 60 nó 7 090X57 095X67 40 nó 8 090X57 095X67 50 nó 9 Definindo as Restrições III 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Implementando o Modelo Veja o arquivo Fig517xls 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Ponto Importante de Modelagem Para problemas generalizados de fluxo de rede os ganhos eou perdas associados a fluxos em cada arco aumentam eou reduzem de maneira efetiva a oferta disponível na rede Algumas vezes é difícil dizer antecipadamente se a oferta total é adequada para atender à demanda Em caso de dúvida é melhor assumir que a oferta total é capaz de satisfazer a demanda total e usar o Solver para comprovar ou refutar essa hipótese 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Problemas de Fluxos Máximos O problema de fluxo máximo é um tipo de problema de fluxo de rede em que a meta é determinar a quantidade máxima de fluxo que pode ocorrer na rede A quantidade de fluxo que pode ocorrer em cada arco é limitada por alguma restrição de capacidade Examplos Qual a quantidade de água capaz de escoar por uma rede de canos Quantos carros podem viajar por uma rede de ruas 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Northwest Petroleum Company Campo de Petróleo Estação de Bombeamento 3 Refinaria 1 2 3 4 5 6 6 4 3 6 4 5 2 2 Estação de Bombeamento 1 Estação de Bombeamento 2 Estação de Bombeamento 4 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Northwest Petroleum Company Campo de Petróleo Refinaria 1 2 3 4 5 6 6 4 3 6 4 5 2 2 Estação de Bombeamento 1 Estação de Bombeamento 3 Estação de Bombeamento 2 Estação de Bombeamento 4 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Formulação do Problema de Fluxo Máximo MAX X61 Sujeito a X61 X12 X13 0 X12 X24 X25 0 X13 X34 X35 0 X24 X34 X46 0 X25 X35 X56 0 X46 X56 X61 0 Com os seguintes limites nas variáveis de decisão 0 X12 6 0 X25 2 0 X46 6 0 X13 4 0 X34 2 0 X56 4 0 X24 3 0 X35 5 0 X61 inf 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Implementando o Modelo Veja o arquivo Fig524xls 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Solução Ótima Campo de Petróleo Refinaria 1 2 3 4 5 6 6 4 3 6 4 5 2 2 5 3 2 4 2 5 4 2 Estação de Bombeamento 1 Estação de Bombeamento 3 Estação de Bombeamento 2 Estação de Bombeamento 4 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Considerações Especiais Sobre Modelagem 1 2 3 4 5 6 100 100 75 50 0 0 3 4 4 5 5 5 3 6 Suponha que o fluxo total para o nó 3 deva ser de pelo menos 50 e o fluxo total para o nó 4 deva ser de pelo menos 60 Como ficaria esse modelo 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados 1 2 3 4 5 6 100 100 75 50 0 0 3 4 4 5 5 5 3 6 30 40 0 0 LB50 LB60 Problema revisado de fluxo de rede com limites inferiores para o fluxo total nos nós 3 e 4 Considerações Especiais Sobre Modelagem 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Considerações Especiais sobre Modelagem Dois Diferentes Tipos de Fluxo Entre Dois Nós 1 1 10 2 75 0 50 75 8 0 6 2 50 Dois ou mais arcos não podem dividir o mesmo nó inicial e final Ao invés disso tente 6 UB 35 8 UB 35 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Considerações Especiais sobre Modelagem Restrições de Capacidade na Oferta Total 1 100 2 100 3 75 4 80 5 UB40 3 UB35 6 UB35 4 UB30 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Considerações Especiais sobre Modelagem Restrições de Capacidade na Oferta Total 1 100 2 100 3 75 4 80 5 UB40 3 UB35 6 UB35 4 UB30 0 200 999 UB100 999 UB100 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Problemas de Árvore de Expansão Mínima Para uma rede com n nós uma árvore de expansão é um conjunto de n1 arcos que conectam todos os nós e não possuem laços Um problema de árvore de expansão mínima envolve a determinação do conjunto de arcos que conecta todos os nós em uma rede e minimiza o comprimento total ou custo dos arcos selecionados 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Exemplo de Árvore de Expansão Mínima Windstar Aerospace Company 2 3 1 4 5 6 150 100 40 85 65 50 90 80 75 85 Os nós representam computadores em uma rede local 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Um Algorítimo para o Problema de Árvore de Expansão Mínima 1 Selecione qualquer nó Chameo de sub rede atual 2 Inclua à subrede atual o arco mais econômico que conecte qualquer nó dentro da subrede atual para qualquer nó que ainda não esteja na subrede As ligações para o arco mais econômico podem ser interrompidas de maneira arbitrária Chameo de subrede atual 3 Se todos os nós estiverem na subrede você encontrou a solução ótima Caso contrário volte para a etapa 2 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Resolvendo o Problema Exemplo 1 2 3 1 4 5 6 100 85 90 80 85 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados 2 3 1 4 5 6 100 85 90 80 85 75 50 Resolvendo o Problema Exemplo 2 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Resolvendo o Problema Exemplo 3 2 3 1 4 5 6 100 85 80 85 75 50 65 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Resolvendo o Problema Exemplo 4 2 3 1 4 5 6 100 80 85 75 50 65 40 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Resolvendo o Problema Exemplo 5 2 3 1 4 5 6 80 85 75 50 65 40 150 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Resolvendo o Problema Exemplo 6 2 3 1 4 5 6 80 75 50 65 40 2007 SouthWestern College Publishing 2010 Cengage Learning Todos os direitos reservados Fim do Capítulo 5