Problemas de Rede: Modelagem e Resolução

Prévia do material em texto

Redes
Prof. Arinéia Assis, Ma
Bibliografia da Aula 
• LACHTERMACHER, Gerson. Pesquisa Operacional na 
tomada de decisões: modelagem em Excel. Rio de Janeiro: 
Elsevier.
Problema de Redes
• Redes são diagramas compostos por uma coleção de vértices ou 
nós ligados entre si por um conjunto de arcos;
• Os nós são simbolizados por círculos e representam os pontos de 
junção que conectam os arcos;
• Os arcos são representados por linhas, conectam os nós e podem 
revelar a direção do fluxo de um ponto para outro;
• Os problemas modelados como redes geralmente apresentam 
números associados aos nós e aos arcos;
Problema de Redes
• Em problemas de transportes modelados como redes, por 
exemplo, os números associados aos nós podem representar a 
quantidade de produtos ofertada ou demandada pelo nó, ao passo 
que os valores dos arcos podem refletir o custo de transporte (ou 
o tempo, ou a distância) entre um nó e outro;
Problema de Redes
• Diversos problemas de tomada de decisão no mundo real estão 
categorizados como Problemas de Rede:
• Problemas de Transporte;
• Escala de Produção;
• Rede de Distribuição;
• Problemas do Menor Caminho;
• Problemas de Fluxo Máximo;
• Problemas de Caminho Crítico.
Problema de Redes
Problemas de Transporte
• Esta classe de problemas recebeu este nome porque seu método 
de resolução, denominado Método de Transporte;
• O Problema de Transporte básico é aquele em que queremos 
determinar, dentre as diversas maneiras de distribuição de um 
produto, a que resultará no menor custo de transporte entre as 
fábricas e os centros de distribuição;
Problemas de Transporte
• onde:
• xij: é a quantidade de itens transportados da fábrica i para o 
destino / (variáveis de decisão);
• cij: é o custo unitário de transporte da fábrica i para o destino; 
(constantes);
• m é o número de fábricas;
• n é o número de destinos (centros de consumidores).
Problemas de Transporte - Exemplo
Problemas de Transporte - Exemplo
Problemas de Transporte - Exemplo
• Restrição de Oferta:
Problemas de Transporte - Exemplo
• Restrição de Demanda:
• Restrições de Não-negatividade:
Problemas de Rede de Distribuição
• Problemas que consideram múltiplas fontes, centros 
consumidores e locais intermediários por onde os produtos 
simplesmente passam são denominados de problemas de rede de 
distribuição;
• Os problemas de transporte podem ser vistos como uma 
simplificação do problema de rede de distribuição de custo 
mínimo, onde as localizações intermediárias não existem.
Problemas de Rede de Distribuição - Exemplo
Problemas de Rede de Distribuição - Exemplo
Problemas de Rede de Distribuição - Exemplo
Problemas de Rede de Distribuição - Exemplo
Exercício 1
• Analise a rede abaixo e faça o que é pedido:
Exercício 1
• Considere que os números indicados em cada aresta significam o 
número de quilômetros necessários para um automóvel percorrer 
a estrada entre duas cidades indicadas pelos nós extremos das 
arestas observadas. Monte o modelo que determine a rota que um 
automóvel deve seguir para sair de Chapecó e chegar a Porto 
Alegre, percorrendo a menor quantidade de quilômetros possível.
Problemas de Escala de Produção
• A forma de modelagem dos problemas de transporte não se 
aplica somente a transportes; também pode ser utilizada em 
problemas de escala de produção designação;
• O importante aqui é a forma de se visualizar o problema;
Problemas de Escala de Produção - Exemplo
Problemas de Escala de Produção - Exemplo
• As variáveis de decisão serão do 
tipo xj e representarão o 
número de motores que serão 
produzidos no trimestre i e 
entregues no trimestre j:
Problemas de Escala de Produção - Exemplo
PPL especiais: variáveis inteiras
PPL especiais: variáveis binárias
Problemas de Menor Caminho
• É um caso especial de problemas de redes;
• Os arcos significam a distância entre dois pontos (nós);
• Quando desejamos achar a rota que une estes pontos com 
distância mínima entre as possíveis, teremos um problema do 
tipo do menor caminho;
• Nestes problemas sempre haverá dois tipos de nós especiais: de 
origem e destino;
Problemas de Menor Caminho
• Entre um nó de origem e um nó de destino geralmente existem 
nós intermediários, que podem representar cidades que conectam 
rodovias, subestações em problemas de distribuição de energia;
• A modelagem do problema terá variáveis binárias do tipo 
indicando o sentido da cidade i para a cidade j;
• Se o valor da variável for igual a um, trecho deve ser percorrido;
Problemas de Menor Caminho - Exemplo
Problemas de Menor Caminho - Exemplo
Problemas de Menor Caminho - Exemplo
Problemas de Fluxo Máximo
• O tipo de Problema de Fluxo Máximo é utilizado quando 
queremos maximizar a quantidade de fluxo de um ponto de 
origem para um ponto de destino e estamos sujeitos a restrições 
de capacidade de fluxo nos arcos;
Problemas de Fluxo Máximo - Exemplo
Problemas de Fluxo Máximo - Exemplo
Problemas de Fluxo Máximo - Exemplo
Problemas de Fluxo Máximo - Exemplo
• A composição das restrições seguirá as seguintes condições:
– a) O fluxo em cada arco deverá ser maior ou igual a zero.
– b) O fluxo em cada arco deverá ser menor ou igual à 
capacidade do arco.
– c) O fluxo que chega em cada nó deverá ser igual ao fluxo que 
sai do mesmo.
– d) O fluxo do arco artificial (desconhecido) deve ser grande o 
bastante para assumir qualquer valor possível, já que este será 
maximizado.
Problemas de Fluxo Máximo - Exemplo
• As restrições de capacidade:
• As restrições de fluxo
Trabalho de PO
Exercício 2
Exercício 2
Exercício 2
Exercício 3
A PowerCo tem três usinas elétricas para suprir as necessidades de quatro 
cidades: Feira de Santana, Milagres, Itabuna e Maiquinique, sendo suas 
potências instaladas, respectivamente, de: 35 milhões kw/hora; 50 milhões 
kw/hora e 40 milhões kw/hora. A demanda de energia atinge o pico nas 
cidades no mesmo momento (19:00h) e é o seguinte (em kw/hora): Feira de 
Santana, 45 milhões; Milagres, 20 milhões; Itabuna, 30 milhões e 
Maiquinique, 30 milhões. O custo de enviar um milhão de kw/hora de 
eletricidade de cada usina para cada uma das cidades está disponível na 
tabela a seguir: R$82,00, R$92,00, R$84,00 e R$86,00, nas fábricas 1,2,3,4 
e 5, respectivamente. O custo unitário de fabricação do segundo produto 
seria de R$62,00, R$58,00, R$64,00, R$56,00 e R$58,00, nas fábricas 
1,2,3,4 e 5, respectivamente. O custo unitário de fabricação do terceiro 
produto seria de R$76,00, R$70,00 e R$80,00 nas fábricas 1,2 e 3, 
respectivamente, sendo que as fábricas 4 e 5 não estão equipadas para 
produzir este produto. As previsões de vendas indicam que deveriam ser 
produzidas por dia 5.000, 3.000 e 4.000 unidades dos produtos 1, 2 e 3, 
respectivamente. 
Exercício 3
As fábricas 1, 2, 3, 4 e 5 têm a capacidade de produzir 2.000, 3.000, 2.000, 
3.000 e 5.000 unidades diárias, respectivamente, independentemente do produto 
ou combinação de produtos envolvidos. A gerência deseja saber como alocar os 
novos produtos às fábricas de níodo a minimizar o custo total de fabricação. 
Formule este problema como um problema de transporte, construindo a tabela 
de custos e requisições apropriada, e resolva-o utilizando o Solver e interprete o 
resultado. 4. A organização não-governamental Criança Renascer está 
organizando a festa dos aniversariantes deste mês. Para isto, ela começa a 
pesquisar o preço de doces e salgados em cinco diferentes bufês do Rio de 
Janeiro. Como a festa será realizada com o dinheiro de doações, ela deseja ter 
os menores custos possíveis. Dada a tabela abaixo, que relaciona os custos decada item por empresa, bem como as quantidades requeridas para a festa 
(demanda) e as capacidades de produção de cada empresa, determine quantos 
doces e salgados a organização deve ncomendar a cada empresa (resolva com o 
auxílio do Solver). Formule como um problema de transporte e resolva-o 
utilizando o Solver. Interprete o significado das variáveis e os resultados 
obtidos. 6. A Pitaf Motores fornece
Exercício 3
Exercício 4
• A Oleobrás dispõe de uma série de oleodutos que servem para 
transportar óleo do campo produtor para as refinarias. 
Considere o esquema abaixo onde são mostradas as possíveis 
ligações entre o campo С e a refinaria R, onde os círculos 
numerados são estações de bombeamento e os quadrados 
numerados indicam o fluxo máximo de óleo que pode ser 
bombeado entre duas estações. Formule o problema de 
maneira a determinar o fluxo máximo de óleo que pode chegar 
à refinaria R.
Exercício 4
Exercício 5
A Sunshine Investimentos S.A. deve determinar a sua estratégia de 
investimento para os próximos três anos. No presente (ano 0) estão 
disponíveis R$150.000,00 reais para investimento. A Sunshine está 
estudando a aplicação de seus recursos em cinco diferentes tipos de 
investimento (A, B, C, D e E). O fluxo de caixa, para cada real 
investido nos cinco tipos de aplicação, é mostrado na tabela abaixo. A 
política de diversificação de risco da Sunshine requer que, no máximo 
R$75.000,00 sejam investidos em apenas uma aplicação. A Sunshine
pode, além destes investimentos, receber juros de 8% a.a. mantendo o 
dinheiro investido em uma aplicação de renda fixa prefixada Os 
retornos dos investimentos podem ser imediatamente reinvestidos. 
Devido a uma política de não-endividamento, todos os recursos 
utilizados devem ser de capital próprio da empresa. Formule o 
problema de maneira a maximizar o disponível ao final do terceiro 
ano.
Exercício 5