Pesquisa Operacional

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
PROF. ÁLVARO LÉDO FERREIRA
CONTATO: a lvaro.ferre i ra@ufpi .edu.br 
8. O%mização em Redes
8.1. Problema do caminho mais curto;
8.2. Problema do fluxo máximo;
8.3. Problema de Transbordo;
8.4. Problema do caminho mais longo;
8.5. Problema da árvore geradora mínima.
8.1. 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.1. Problema do caminho mais curto
• Problema contém somente um nó de oferta (origem) e um nó de 
demanda (desKno);
• Capacidade dos nós de oferta e demanda são iguais a 1;
• Capacidade dos outros nós iguais a 0;
8.1. 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.1. Problema do caminho mais curto
𝑀𝑖𝑛	𝑍 ='
!
'
"
𝑐!"𝑥!" 	
𝑠. 𝑎.
'
!
𝑥!" = 1	 𝑖 = 𝑂
	'
#
𝑥#! = 1	 𝑖 = 𝐷
	
'
#
𝑥#! −'
"
𝑥!" = 0	 ∀	𝑖 ≠ 𝑂, 𝐷
𝑥!" = 0	𝑜𝑢	1	(∀	𝑖, 𝑗)
8.1. 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.1. Problema do caminho mais curto
8.2. Problema do fluxo máximo
• Busca maximizar o fluxo de mercadorias, materiais, energia, etc.;
• Possui um nó de origem e um nó de destino;
• 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 destino.
8.2. 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.2. 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 destino: 𝑖 = 𝐷;
• 𝑙!" = limite mínimo para o fluxo no arco 𝑖, 𝑗 , ∀	𝑖, 𝑗;
• 𝑢!" = limite máximo para o fluxo no arco 𝑖, 𝑗 , ∀	𝑖, 𝑗;
• 𝑥!" = fluxo no arco 𝑖, 𝑗 , ∀	𝑖, 𝑗.
8.2. Problema do fluxo máximo
𝑀𝑎𝑥	𝑍 ='
"
𝑥$" 	𝑜𝑢	𝑀𝑎𝑥	𝑍 ='
#
𝑥#%
𝑠. 𝑎.
	'
#
𝑥#% −'
"
𝑋$" = 0	 𝑖 = 𝑂, 𝐷
	
'
#
𝑥#! −'
"
𝑥!" = 0	 ∀𝑖 ≠ 𝑂,𝐷
𝑙!" ≤ 𝑥!" = 𝑢!" 	 ∀	𝑖, 𝑗
𝑥!" ≥ 0	(∀	𝑖, 𝑗)
8.2. Problema do fluxo máximo
• Exemplo: A empresa Petroduto transporta óleo, gás, 
biocombustí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 destino (D) um consumidor 
final localizado em São Paulo. Os valores nos arcos representam as 
capacidades máximas em cada arco (em 𝑚!/𝑠).
8.2. Problema do fluxo máximo
8.3. 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 desKnos, considera pontos intermediários de transbordo;
• Pontos de transbordo podem ser, por exemplo:
• Centros de distribuição;
• Porto marí4mo;
• Fábricas. 
8.3. 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.3. 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.3. Problema de Transbordo
8.3. 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 quan>dade enviada do fornecedor 𝑖 para o ponto de transbordo 𝑘 é igual a 
𝑥!$;
• A quan>dade enviada do ponto de transbordo 𝑘 para o consumidor 𝑗 é igual a 
𝑥$";
• Logo, 𝑥!",$ = 𝑥!$ + 𝑥$";
• Assim, temos:
8.3. Problema de Transbordo
𝑀𝑖𝑛	𝑍 ='
!"#
$
'
%"#
&
𝑐!%,(𝑥!%,( 	
𝑠. 𝑎.
	'
%"#
&
𝑥!%,( ≤ 𝐶𝑓! 	 𝑖 = 1, 2, … ,𝑚
	
'
!"#
$
𝑥!%,( ≥ 𝑑% 	 𝑗 = 1, 2, … , 𝑛
	
'
!"#
$
𝑥!( ='
%"#
&
𝑥(% 	 𝑘 = 1, 2, … , 𝐾
𝑥!% ≥ 0	 ∀𝑖, 𝑗
Versão desbalanceada
8.3. Problema de Transbordo
𝑀𝑖𝑛	𝑍 ='
!"#
$
'
%"#
&
𝑐!%,(𝑥!%,( 	
𝑠. 𝑎.
	'
%"#
&
𝑥!%,( = 𝐶𝑓! 	 𝑖 = 1, 2, … ,𝑚
	
'
!"#
$
𝑥!%,( = 𝑑% 	 𝑗 = 1, 2, … , 𝑛
	
'
!"#
$
𝑥!( ='
%"#
&
𝑥(% 	 𝑘 = 1, 2, … , 𝐾
𝑥!% ≥ 0	 ∀𝑖, 𝑗
Versão balanceada
8.3. Problema de Transbordo
𝑀𝑖𝑛	𝑍 ='
!"#
$
'
("#
)
𝑐!(𝑥!( +'
("#
)
'
%"#
&
𝑐(%𝑥(% 	
𝑠. 𝑎.
	'
("#
)
𝑥!( = 𝐶𝑓! 	 𝑖 = 1, 2, … ,𝑚
	
'
("#
)
𝑥(% = 𝑑% 	 𝑗 = 1, 2, … , 𝑛
	
'
!"#
$
𝑥!( ='
%"#
&
𝑥(% 	 𝑘 = 1, 2, … , 𝐾
𝑥!% ≥ 0	 ∀𝑖, 𝑗
Versão balanceada 
expandida
8.3. 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ís4cos, 
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 par4r 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, 
respec4vamente. 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, respec4vamente. Formule 
o problema de transbordo.
8.3. Problema de Transbordo
8.3. Problema de Transbordo
8.3. Problema de Transbordo
8.4. 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 exemplo o 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 entreesses mesmos nós.
8.4. Problema do caminho mais longo
• Exemplo: Mesmo do caminho mais curto.
8.5. 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.5. 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.5. 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.5. Problema da Árvore Geradora Mínima
• Exemplo: 𝐺 = 7,12
8.5. Problema da Árvore Geradora Mínima
• Exemplo: Árvore Geradora?
8.5. Problema da Árvore Geradora Mínima
• Exemplo: Árvore Geradora?
8.5. Problema da Árvore Geradora Mínima
• Exemplo: Árvore Geradora?
8.5. 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á con>do ou não na Árvore 
Geradora Mínima;
• Para um subgrafo 𝑆 de 𝐺, o número de nós é representado por 𝑆 .
8.5. 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 dispositivos 
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 objetivo é encontrar a árvore geradora mínima 
(com menor custo) a partir dessa rede de computadores.
8.5. 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
PROF. ÁLVARO LÉDO FERREIRA
CONTATO: a lvaro.ferre i ra@ufpi .edu.br