Pesquisa Operacional II UFRA - Plano de Ensino e Introducao a Programacao em Redes

Universidade Federal Rural da Amazônia UFRA Curso de Bacharelado em Engenharia de Produção Campus de Parauapebas Pesquisa Operacional II Semestre 20241 7º Período CH Semanal 4 horas CH Total 68 horas Professor Me Fabrício Menezes Mares Plano de Ensino Curso de Bacharelado em Engenharia de Produção Campus de Parauapebas PLANO GRAFO PROBLEMA MODELO ATIVIDADE ELEMENTOS LEMBRA BIBLIOGRAF Curso de Bacharelado em Engenharia de Produção Campus de Parauapebas Características para se identificar um problema de Estrutura de grafo ou rede que consiste em diversos nós em que cada nó deve estar conectado a um ou mais arcos Programação em Redes Dentre os principais problemas de programação em redes têmse Problema clássico de transporte Problema de transbordo Problema de designação de tarefas Problema do caminho mais curto Problema do fluxo máximo Problema da árvore geradora mínima entre outros Introdução à Programação em Redes PLANO GRAFO PROBLEMA MODELO ATIVIDADE ELEMENTOS LEMBRA BIBLIOGRAF Curso de Bacharelado em Engenharia de Produção Campus de Parauapebas é definido a partir de um conjunto de nós ou vértices e um conjunto de arcos ou arestas interconectando esses nós Um grafo Grafo Arcos fazem conexões entre pares de nós podendo representar caminhos rotas fios cabos canais entre outros Nós podem representar facilidades como fábricas centros de distribuição terminais ou portos marítimos estações de trabalho ou interseções Terminologia de Grafos e Redes A notação de um grafo é G N A em que N é um conjunto de nós e A é um conjunto de arcos A Figura mostra um exemplo de grafo com cinco nós e oito arcos PLANO GRAFO PROBLEMA MODELO ATIVIDADE ELEMENTOS LEMBRA BIBLIOGRAF Curso de Bacharelado em Engenharia de Produção Campus de Parauapebas Observe o que cada elemento representa uma variável numérica Representação Arcos fazem conexões entre os nós estão associados a uma variável numérica chamada fluxo que representa uma característica mensurável dessa ligação como distância entre os nós custo de transporte tempo despendido dimensão do fio quantidade de peças transportadas entre outras Nós podem estar associados a uma variável numérica chamada capacidade podendo representar a capacidade de carga e descarga suprimentos demanda entre outras Obs Um grafo cujos arcos eou nós estão associados à variável numérica fluxo eou capacidade é chamado de rede Terminologia de Grafos e Redes PLANO GRAFO PROBLEMA MODELO ATIVIDADE ELEMENTOS LEMBRA BIBLIOGRAF Curso de Bacharelado em Engenharia de Produção Campus de Parauapebas A Figura mostra um exemplo de redes Fonte Belfiore e Favero 2013 Os nós representam as cidades Os fluxos arcos representam as distâncias km entre elas Terminologia de Grafos e Redes Obs daqui em diante utilizaremos apenas a notação rede PLANO GRAFO PROBLEMA MODELO ATIVIDADE ELEMENTOS LEMBRA BIBLIOGRAF Curso de Bacharelado em Engenharia de Produção Campus de Parauapebas Tipologias dos nós Representam entidades que produzem ou distribuem determinado produto nós de oferta ou fontes Representam entidades que consumem o produto nós de demanda são os pontos intermediários entre os nós de oferta e demanda e representam os pontos de passagem desses produtos nós de transbordo PLANO GRAFO PROBLEMA MODELO ATIVIDADE ELEMENTOS LEMBRA BIBLIOGRAF Tipologias de arcos Curso de Bacharelado em Engenharia de Produção Campus de Parauapebas Os arcos podem ter uma seta indicando a direção do arco Quando o fluxo entre os respectivos nós ocorre em uma única direção indicada por uma seta arco direcionado Quando o fluxo ocorre em ambas as direções Quando há uma única conexão entre nós porém sem a seta indicando a direção do arco presumese que é não direcionado arco não direcionado PLANO GRAFO PROBLEMA MODELO ATIVIDADE ELEMENTOS LEMBRA BIBLIOGRAF Curso de Bacharelado em Engenharia de Produção Campus de Parauapebas Tipologias de Redes Rede não direcionada todos os arcos são não direcionados Rede direcionada todos os arcos da rede são direcionados nós representam um conjunto de atividades físicas com as respectivas durações minutos arcos direcionados representam as relações de precedência entre as atividades PLANO GRAFO PROBLEMA MODELO ATIVIDADE ELEMENTOS LEMBRA BIBLIOGRAF Curso de Bacharelado em Engenharia de Produção Campus de Parauapebas Caminho Hillier e Lieberman 2005 definem um caminho entre dois nós como a sequência de diferentes arcos conectando esses nós Por exemplo a sequência de arcos AB BC CE A B C E da Figura PLANO GRAFO PROBLEMA MODELO ATIVIDADE ELEMENTOS LEMBRA BIBLIOGRAF Curso de Bacharelado em Engenharia de Produção Campus de Parauapebas Caminho Hillier e Lieberman 2005 definem um caminho entre dois nós como a sequência de diferentes arcos conectando esses nós Em uma rede direcionada podese ter um caminho direcionado ou não direcionado Caminho direcionado tem uma única direção AC CD DE A C D E Caminho não direcionado pelo menos um arco do caminho tem sentido oposto aos demais AB BD DC A B D C PLANO GRAFO PROBLEMA MODELO ATIVIDADE ELEMENTOS LEMBRA BIBLIOGRAF Curso de Bacharelado em Engenharia de Produção Campus de Parauapebas Caminho Hillier e Lieberman 2005 definem um caminho entre dois nós como a sequência de diferentes arcos conectando esses nós O caminho hamiltoniano é aquele que visita cada nó uma única vez Caminho hamiltoniano AB BC CE Caminho não hamiltoniano AB BC CE ED DC A B C E D C PLANO GRAFO PROBLEMA MODELO ATIVIDADE ELEMENTOS LEMBRA BIBLIOGRAF Curso de Bacharelado em Engenharia de Produção Campus de Parauapebas Caminho Hillier e Lieberman 2005 definem um caminho entre dois nós como a sequência de diferentes arcos conectando esses nós Já um caminho que começa e finaliza no mesmo nó forma um ciclo AB BC CE EA A B C E A PLANO GRAFO PROBLEMA MODELO ATIVIDADE ELEMENTOS LEMBRA BIBLIOGRAF Curso de Bacharelado em Engenharia de Produção Campus de Parauapebas Caminho Hillier e Lieberman 2005 definem um caminho entre dois nós como a sequência de diferentes arcos conectando esses nós Em uma rede direcionada podese ter um ciclo direcionado ou não direcionado Ciclo direcionado AB BD DE EA A B D E A Ciclo não direcionado AB BC CA A B C A PLANO GRAFO PROBLEMA MODELO ATIVIDADE ELEMENTOS LEMBRA BIBLIOGRAF Árvore Curso de Bacharelado em Engenharia de Produção Campus de Parauapebas Uma rede G N A não direcionada é dita conexa quando existe um caminho entre qualquer par de nós É conexa e acíclica sem ciclos Ainda dentro do conceito de árvore afirmase que Uma árvore com n nós contém n 1 arcos Se um arco for adicionado à árvore formase um ciclo Se um arco for eliminado da árvore a rede deixa de ser conexa em vez de uma única rede conexa têmse duas redes conexas A rede G é uma árvore PLANO GRAFO PROBLEMA MODELO ATIVIDADE ELEMENTOS LEMBRA BIBLIOGRAF Árvore Curso de Bacharelado em Engenharia de Produção Campus de Parauapebas G N A é um subgrafo de G N A se o conjunto de nós de G é um subconjunto do conjunto de nós de GN está contido em N se o conjunto de arcos de G é um subconjunto do conjunto de arcos de G A está contido em A e se G é um grafo ou rede A partir da rede G NA uma árvore geradora também chamada árvore de cobertura é um subgrafo de G que tem a estrutura de uma árvore e contém todos os nós de G Árvore Geradora Uma árvore geradora mínima de G é a árvore geradora com o menor custo PLANO GRAFO PROBLEMA MODELO ATIVIDADE ELEMENTOS LEMBRA BIBLIOGRAF Curso de Bacharelado em Engenharia de Produção Campus de Parauapebas Problema Clássico de Transporte determinar as quantidades de produtos a serem transportadas por um conjunto de fornecedores para um conjunto de consumidores com um custo total de transporte minimizado Transporte Clássico Cada fornecedor fabrica um número fixo de produtos e cada consumidor tem uma demanda conhecida que será atendida O problema é modelado a partir de dois elos da cadeia de suprimentos ou seja não considera facilidades intermediárias centros de distribuição terminal porto marítimo ou fábrica Obs Caso algum dos requisitos não seja atendido operações elementares devem ser realizadas a fim de colocar o modelo na forma canônica PLANO GRAFO PROBLEMA MODELO ATIVIDADE ELEMENTOS LEMBRA BIBLIOGRAF Curso de Bacharelado em Engenharia de Produção Campus de Parauapebas Modelo de um Problema Clássico de Transporte Considere um conjunto de m fornecedores que fornecem mercadorias para um conjunto de n consumidores A quantidade máxima a ser transportada a partir de determinado fornecedor i i 1 m corresponde à sua capacidade de Cfi unidades A demanda de cada consumidor j j 1 n deve ser atendida sendo representada por dj O custo unitário de transporte do fornecedor i para o consumidor j é representado por cij O objetivo é determinar as quantidades a serem transportadas do fornecedor i para o consumidor j xij de modo a minimizar o custo total de transporte z PLANO GRAFO PROBLEMA MODELO ATIVIDADE ELEMENTOS LEMBRA BIBLIOGRAF Curso de Bacharelado em Engenharia de Produção Campus de Parauapebas Formulação Matemática do Problema de Transporte Modelo Geral de Problema Clássico de Transporte Corresponde a um problema de programação linear Dessa forma o problema poderia ser resolvido pelo método Simplex Porém a estrutura especial do problema em redes permite a obtenção de algoritmos de solução mais eficientes como o algoritmo de transporte PLANO GRAFO PROBLEMA MODELO ATIVIDADE ELEMENTOS LEMBRA BIBLIOGRAF Curso de Bacharelado em Engenharia de Produção Campus de Parauapebas Formulação Matemática do Problema de Transporte Modelo Geral de Problema Clássico de Transporte PLANO GRAFO PROBLEMA MODELO ATIVIDADE ELEMENTOS LEMBRA BIBLIOGRAF Curso de Bacharelado em Engenharia de Produção Campus de Parauapebas Formulação Matemática do Problema de Transporte Modelo Geral de Problema de Transporte Balanceado PLANO GRAFO PROBLEMA MODELO ATIVIDADE ELEMENTOS LEMBRA BIBLIOGRAF Curso de Bacharelado em Engenharia de Produção Campus de Parauapebas Formulação Matemática do Problema de Transporte Modelo Geral de Problema de Transporte DesbalanceadoDescoberto PLANO GRAFO PROBLEMA MODELO ATIVIDADE ELEMENTOS LEMBRA BIBLIOGRAF Curso de Bacharelado em Engenharia de Produção Campus de Parauapebas A Karpet Ltda é uma empresa fabricante de autopeças cujas sedes estão localizadas em Osasco Sorocaba e São Sebastião Seus clientes encontramse em São Paulo Rio de Janeiro e Curitiba conforme apresenta a Figura Exercício 01 PLANO GRAFO PROBLEMA MODELO ATIVIDADE ELEMENTOS LEMBRA BIBLIOGRAF Curso de Bacharelado em Engenharia de Produção Campus de Parauapebas Os custos unitários de transporte de cada origem para cada destino assim como a capacidade de cada fornecedor e a demanda de cada cliente encontramse na Tabela O objetivo é atender a demanda de cada consumidor final respeitando as capacidades de fornecimento de forma a minimizar o custo total de transporte Modele o problema de transporte Exercício 01 PLANO GRAFO PROBLEMA MODELO ATIVIDADE ELEMENTOS LEMBRA BIBLIOGRAF Curso de Bacharelado em Engenharia de Produção Campus de Parauapebas A TransPeso é uma empresa de transporte de correias cujas sedes estão localizadas em Belém Goiânia e Tocantins Seus clientes encontramse em Parauapebas Canaã dos Carajás e Ourilândia do Norte Os custos unitários de transporte de cada origem para cada destino assim como a capacidade de cada fornecedor e a demanda de cada cliente encontramse na Tabela O objetivo é atender a demanda de cada consumidor final respeitando as capacidades de fornecimento de forma a minimizar o custo total de transporte Modele o problema de transporte e encontre a solução ótima Exercício 02 Parauapebas Canaã Ourilândia Capacidade Belém 20 25 35 110 Goiânia 35 25 22 150 Tocantins 16 20 40 90 85 105 160 350 Demanda Fornecedor Consumidores Custo unitário de Transporte PLANO GRAFO PROBLEMA MODELO ATIVIDADE ELEMENTOS LEMBRA BIBLIOGRAF Bibliografia Básica BELFIORE P FÁVERO L P Pesquisa operacional para cursos de engenharia Rio de Janeiro Elsevier 2013 HILLIER F S LEMOS H L Introdução à pesquisa operacional 9 Ed Porto Alegre AMG 2013 ANDRADE E L de Introdução à pesquisa operacional métodos e modelos para análise de decisões 5 Ed Rio de Janeiro LTC 2015 Complementar ANDRADE E L Introdução à pesquisa operacional Rio de Janeiro LTC 2004 COLIN E C Pesquisa Operacional 170 aplicações em estratégias finanças logística produção marketing e vendas Rio de Janeiro LTC 2007 TAHA H A Pesquisa operacional 8 Ed São Paulo SP Pearson 2007 LEAL NETO J S Pesquisa operacional 1 Ed São Paulo Contentus 2020 BARBOSA M A Iniciação à pesquisa operacional no ambiente de gestão 3 Ed Curitiba Intersaberes 2015 PLANO GRAFO PROBLEMA MODELO ATIVIDADE ELEMENTOS LEMBRA BIBLIOGRAF