Prévia do material em texto
Pesquisa Operacional I
(CEP/CT025) – Aula 07
UNIVERSIDADE FEDERAL DO PIAUÍ
CAMPUS MINISTRO PETRÔNIO PORTELLA – CT
CURSO DE ENGENHARIA DE PRODUÇÃO – 2023.1
PROF. ÁLVARO LÉDO FERREIRA
CONTATO: alvaro.ferreira@ufpi.edu.br
8. O%mização em Redes
8.1. Definições;
8.2. Problema do caminho mais curto;
8.3. Problema do fluxo máximo;
8.4. Problema de Transbordo;
8.5. Problema do caminho mais longo;
8.6. Problema da árvore geradora mínima.
8.1. Definições
• Também conhecido como problema do caminho mínimo;
• Busca encontrar o menor caminho entre dois nós de uma rede;
• Pode minimizar a distância total percorrida, o custo total ou o
tempo total de viagem;
8.2. Problema do caminho mais curto
• Também conhecido como problema do caminho mínimo;
• Busca encontrar o menor caminho entre dois nós de uma rede;
• Pode minimizar a distância total percorrida, o custo total ou o
tempo total de viagem;
8.2. Problema do caminho mais curto
• Problema contém somente um nó de oferta (origem) e um nó de
demanda (desPno);
• Capacidade dos nós de oferta e demanda são iguais a 1;
• Capacidade dos outros nós iguais a 0;
8.2. Problema do caminho mais curto
• Considere:
• Existem 𝑖 ∈ 𝐼 nós;
• Os nós que chegam a 𝑖 são os nós 𝑘 ∈ 𝐾 e os nós posteriores a 𝑖 são os nós
𝑗 ∈ 𝐽;
• Nó de origem: 𝑖 = 𝑂 (capacidade igual a 1);
• Nó de des>no: 𝑖 = 𝐷 (capacidade igual a 1);
• 𝑐!" = distância entre os nós 𝑖 e 𝑗, ∀ 𝑖, 𝑗;
• 𝑥!" = 1 ou 0 𝑖, 𝑗 , ∀ 𝑖, 𝑗.
8.2. Problema do caminho mais curto
𝑀𝑖𝑛 𝑍 ='
!
'
"
𝑐!"𝑥!"
𝑠. 𝑎.
'
!
𝑥!" = 1 𝑖 = 𝑂
'
#
𝑥#! = 1 𝑖 = 𝐷
'
#
𝑥#! −'
"
𝑥!" = 0 ∀ 𝑖 ≠ 𝑂, 𝐷
𝑥!" = 0 𝑜𝑢 1 (∀ 𝑖, 𝑗)
8.2. Problema do caminho mais curto
• Exemplo: Um fornecedor de alimentos localizado em Osasco
entrega salgados e doces diariamente para uma padaria localizada
na região da Vila Formosa, em São Paulo. Para isso, o motorista pode
percorrer mais de um caminho, passando por diferentes bairros em
São Paulo. A figura abaixo apresenta os possíveis caminhos que o
veículo pode percorrer, do nó de oferta (Osasco) para o nó de
demanda (Vila Formosa), além das distâncias em km entre os nós ou
bairros. Formule o problema do caminho mais curto estudado.
8.2. Problema do caminho mais curto
8.3. Problema do fluxo máximo
• Busca maximizar o fluxo de mercadorias, materiais, energia, etc.;
• Possui um nó de origem e um nó de desPno;
• Deve respeitar os limites mínimos e máximos de fluxo nos arcos;
• Fluxo pode ser medido em duas direções:
• Fluxo máximo de saída do nó de origem, ou;
• Fluxo máximo de chegada no nó de des>no.
8.3. Problema do fluxo máximo
• Exemplos:
• Maximizar o fluxo de mercadorias em uma rede de distribuição;
• Maximizar o fluxo de óleo, gás ou água por meio de um sistema de dutos;
• Maximizar o fluxo de veículos em uma rede de transportes.
8.3. Problema do fluxo máximo
• Considere:
• Existem 𝑖 ∈ 𝐼 nós;
• Os nós que chegam a 𝑖 são os nós 𝑘 ∈ 𝐾 e os nós posteriores a 𝑖 são os nós
𝑗 ∈ 𝐽;
• Nó de origem: 𝑖 = 𝑂;
• Nó de des>no: 𝑖 = 𝐷;
• 𝑙!" = limite mínimo para o fluxo no arco 𝑖, 𝑗 , ∀ 𝑖, 𝑗;
• 𝑢!" = limite máximo para o fluxo no arco 𝑖, 𝑗 , ∀ 𝑖, 𝑗;
• 𝑥!" = fluxo no arco 𝑖, 𝑗 , ∀ 𝑖, 𝑗.
8.3. Problema do fluxo máximo
𝑀𝑎𝑥 𝑍 ='
"
𝑥$" 𝑜𝑢 𝑀𝑎𝑥 𝑍 ='
#
𝑥#%
𝑠. 𝑎.
'
#
𝑥#% −'
"
𝑋$" = 0 𝑖 = 𝑂, 𝐷
'
#
𝑥#! −'
"
𝑥!" = 0 ∀𝑖 ≠ 𝑂,𝐷
𝑙!" ≤ 𝑥!" = 𝑢!" ∀ 𝑖, 𝑗
𝑥!" ≥ 0 (∀ 𝑖, 𝑗)
8.3. Problema do fluxo máximo
• Exemplo: A empresa Petroduto transporta óleo, gás,
biocombus^veis renováveis, dentre outros produtos, por meio de
uma malha sólida de dutos de 1.000 km. A empresa busca
determinar o fluxo máximo de óleo (em 𝑚!/𝑠) que pode ser
transportado na rede da figura abaixo, que tem como nó de origem
(O) a estação de Minas e como nó de desPno (D) um consumidor
final localizado em São Paulo. Os valores nos arcos representam as
capacidades máximas em cada arco (em 𝑚!/𝑠).
8.3. Problema do fluxo máximo
8.4. Problema de Transbordo
• Extensão do problema clássico de transporte;
• Ao invés de transportar os produtos diretamente de várias origens
para vários destinos, considera pontos intermediários de transbordo;
• Pontos de transbordo podem ser, por exemplo:
• Centros de distribuição;
• Porto marítimo;
• Fábricas.
8.4. Problema de Transbordo
• Modelado a partir de 3 elos na cadeia de suprimentos;
• Transporte ocorre em duas etapas:
• Dos fornecedores para os pontos de transbordo;
• Dos pontos de transbordo para os pontos de demanda.
• Objetivo: determinar o fluxo de mercadorias transportadas de um
conjunto de origens para um conjunto de destinos via facilidades
intermediárias, a fim de minimizar o custo total de transporte;
8.4. Problema de Transbordo
• Considere:
• Quan>dade máxima transportada a par>r de um fornecedor 𝑖 𝑖 = 1,… ,𝑚 é
igual a 𝐶𝑓!;
• Demanda de cada consumidor 𝑗 𝑗 = 1,… , 𝑛 é igual a 𝑑" e deve ser atendida;
• Transbordo representados pelo índice 𝑘 𝑘 = 1,… , 𝐾 ;
• Custo unitário de transporte do fornecedor 𝑖 para o consumidor 𝑗 via ponto de
transbordo 𝑘 é igual a 𝑐!",$;
• 𝑥!",$ representa a quan>dade transportada do fornecedor 𝑖 para o
consumidor 𝑗 passando pelo ponto de transbordo 𝑘;
8.4. Problema de Transbordo
8.4. Problema de Transbordo
• Considere:
• O custo de enviar do fornecedor 𝑖 para o ponto de transbordo 𝑘 é igual a 𝑐!$;
• O custo de enviar do ponto de transbordo 𝑘 para o consumidor 𝑗 é igual a 𝑐$";
• Logo, 𝑐!",$ = 𝑐!$ + 𝑐$";
• A quantidade enviada do fornecedor 𝑖 para o ponto de transbordo 𝑘 é igual a
𝑥!$;
• A quantidade enviada do ponto de transbordo 𝑘 para o consumidor 𝑗 é igual a
𝑥$";
• Logo, 𝑥!",$ = 𝑥!$ + 𝑥$";
• Assim, temos:
8.4. Problema de Transbordo
𝑀𝑖𝑛 𝑍 ='
!"#
$
'
%"#
&
𝑐!%,(𝑥!%,(
𝑠. 𝑎.
'
%"#
&
𝑥!%,( ≤ 𝐶𝑓! 𝑖 = 1, 2, … ,𝑚
'
!"#
$
𝑥!%,( ≥ 𝑑% 𝑗 = 1, 2, … , 𝑛
'
!"#
$
𝑥!( ='
%"#
&
𝑥(% 𝑘 = 1, 2, … , 𝐾
𝑥!% ≥ 0 ∀𝑖, 𝑗
Versão desbalanceada
8.4. Problema de Transbordo
𝑀𝑖𝑛 𝑍 ='
!"#
$
'
%"#
&
𝑐!%,(𝑥!%,(
𝑠. 𝑎.
'
%"#
&
𝑥!%,( = 𝐶𝑓! 𝑖 = 1, 2, … ,𝑚
'
!"#
$
𝑥!%,( = 𝑑% 𝑗 = 1, 2, … , 𝑛
'
!"#
$
𝑥!( ='
%"#
&
𝑥(% 𝑘 = 1, 2, … , 𝐾
𝑥!% ≥ 0 ∀𝑖, 𝑗
Versão balanceada
8.4. Problema de Transbordo
𝑀𝑖𝑛 𝑍 ='
!"#
$
'
("#
)
𝑐!(𝑥!( +'
("#
)
'
%"#
&
𝑐(%𝑥(%
𝑠. 𝑎.
'
("#
)
𝑥!( = 𝐶𝑓! 𝑖 = 1, 2, … ,𝑚
'
("#
)
𝑥(% = 𝑑% 𝑗 = 1, 2, … , 𝑛
'
!"#
$
𝑥!( ='
%"#
&
𝑥(% 𝑘 = 1, 2, … , 𝐾
𝑥!% ≥ 0 ∀𝑖, 𝑗
Versão balanceada
expandida
8.4. Problema de Transbordo
• Exemplo: A companhia PetrusNortel atua no setor petroquímico e possui
duas plantas. Uma delas é responsável pela produção de polímeros e está
localizada em Recife. A outra está localizada em Manaus, sendo
responsável pela produção de resina. A fim de reduzir os custos logísLcos,
os produtos sofrem uma etapa de transbordo em um dos centros de
distribuição, localizados em São Paulo e no Rio de Janeiro. A parLr dos
centros de distribuição, os produtos são transportados para os clientes
finais, localizados em Belo Horizonte, Joinville e Porto Alegre, conforme
mostra a figura a seguir. A capacidade de produção das fábricas é de 500
unidades em Manaus e 300 em Recife. A demanda dos consumidores de
Belo Horizonte, Joinville e Porto Alegre é de 200, 250 e 350,
respecLvamente. Os custos unitários de transporte, das fábricas para os
pontos de transbordo e dos pontos de transbordo para os consumidores
finais, estão representados nas tabelas abaixo, respecLvamente. Formule
o problema de transbordo.
8.4. Problema de Transbordo
8.4. Problema de Transbordo
8.4. Problema de Transbordo
8.5. Problema do caminho mais longo
• Objetivo: determinar o caminho máximo entre dois nós no grafo;
• Formulação matemática igual à do problema de caminho mais
curto, exceto ser de maximização ao invés de minimização;
• O problema aparece com frequência em aplicações práticas como
por exemploo problema da mochila e programação de projetos
• Maximizar uma função objetivo é equivalente a minimizar o
negativo desta função;
• Portanto, o problema de caminho máximo pode ser transformado
em um problema de caminho mínimo entre esses mesmos nós.
8.5. Problema do caminho mais longo
• Exemplo: Mesmo do caminho mais curto.
8.6. Problema da Árvore Geradora Mínima
• Árvore:
• Rede 𝐺 = 𝑁, 𝐴 não direcionada;
• Conexa: existe caminho entre quaisquer dois pares de nós;
• Acíclica: sem ciclos;
• Possui 𝑛 − 1 arcos dados 𝑛 nós.
• Se um arco for direcionado tem-se um ciclo;
• Se um arco for eliminado da árvore a rede deixa de ser conexa;
8.6. Problema da Árvore Geradora Mínima
• Árvore Geradora (ou Árvore de Cobertura): subgrafo 𝑆 de 𝐺 com
uma estrutura de árvore contendo todos os nós de 𝐺;
• Suponha que cada arco da rede está associado a um fluxo (custo,
tempo, distância, tempo, etc.);
• Uma Árvore Geradora Mínima (AGM) de 𝐺 é uma árvore geradora
cuja soma total dos fluxos nos arcos seja a menor possível;
8.6. Problema da Árvore Geradora Mínima
• Objetivo é encontrar o conjunto de 𝑛 − 1 arcos que conectam todos
os 𝑛 nós, não contenha ciclo e soma do fluxo dos arcos mínima;
• Exemplos:
• Projeto de redes de telecomunicação (redes de computadores, redes de
telefonia, redes de televisão a cabo, etc);
• Projeto de rodovias, ferrovias;
• Projeto de redes de distribuição de água e esgoto;
• Projeto de redes de transmissão de energia, etc.
8.6. Problema da Árvore Geradora Mínima
• Exemplo: 𝐺 = 7,12
8.6. Problema da Árvore Geradora Mínima
• Exemplo: Árvore Geradora?
8.6. Problema da Árvore Geradora Mínima
• Exemplo: Árvore Geradora?
8.6. Problema da Árvore Geradora Mínima
• Exemplo: Árvore Geradora?
8.6. Problema da Árvore Geradora Mínima
• Considere:
• Uma rede 𝐺 = 𝑁, 𝐴 com 𝑛 nós e ;
• 𝑐!" representa o fluxo associado ao arco 𝑥!";
• 𝑥!" variável binária indicando se o arco está contido ou não na Árvore
Geradora Mínima;
• Para um subgrafo 𝑆 de 𝐺, o número de nós é representado por 𝑆 .
8.6. Problema da Árvore Geradora Mínima
• Exemplo: A topologia representada na figura abaixo mostra como
uma rede de computadores está configurada. Há um tráfego de
informações entre os computadores (nós) por meio de disposiZvos
conectados (arcos). É uma rede não direcionada, cuja topologia é
totalmente ligada, isto é, todos os computadores estão ligados entre
si através de caminhos dedicados, e a troca de informações acontece
de forma direta. Os fluxos nos arcos representam o custo de fazer
cada conexão. O objeZvo é encontrar a árvore geradora mínima
(com menor custo) a parZr dessa rede de computadores.
8.6. Problema da Árvore Geradora Mínima
Pesquisa Operacional I
(CEP/CT025) – Aula 07
UNIVERSIDADE FEDERAL DO PIAUÍ
CAMPUS MINISTRO PETRÔNIO PORTELLA – CT
CURSO DE ENGENHARIA DE PRODUÇÃO – 2023.1
PROF. ÁLVARO LÉDO FERREIRA
CONTATO: alvaro.ferreira@ufpi.edu.br