Capítulo_5.2

Prévia do material em texto

Capítulo 5 Modelos de Otimização de Redes 
Métodos Quantitativos – Ciências Contábeis Jhoab Negreiros 
1 
 
 
 
 
 
 
 
 
 
 
 
 
 
CAPÍTULO 5 
Modelos de Otimização de Redes 
 
 
 
 
 
 
 
5.1 Introdução 
 
As redes surgiram em diversos ambientes e de muitas formas distintas. Redes de 
transporte, elétricas e de comunicações são uma constante em nosso dia-a-dia. As representações 
em formato de rede são amplamente usadas para problemas em áreas tão diversas como 
distribuição, planejamento de projetos, posicionamento de instalações, administração de recursos e 
planejamento financeiro entre outras. 
Muitos modelos de otimização de redes, na verdade, são tipos especiais de problema de 
programação linear. Por exemplo, tanto o problema do transporte quanto o problema de 
designação, discutidos nos capítulos anteriores, situam-se nessa categoria em virtude de suas 
representações em forma de rede. 
 
5.2 Introdução 
 
• Grafos 
Denomina-segrafoum conjunto de pontos, chamados nós, conectados entre si porlinhas 
chamadas de arestas, como exemplo a seguir. 
 
Capítulo 5 Modelos de Otimização de Redes 
Métodos Quantitativos – Ciências Contábeis Jhoab Negreiros 
2 
 
 
Os círculos numerados de 1 a 6 são os nós do grafo e as linhas que fazem as ligações 
apontadas entre os nós são as arestas do grafo. 
 
• Grafos direcionais 
Um grafo direcionado𝐺𝐺é um par(𝑉𝑉,𝐴𝐴), onde𝑉𝑉é um conjunto finito de vértices e𝐴𝐴 é 
umarelação binária em𝑉𝑉, isto é, Uma aresta(𝑢𝑢, 𝑣𝑣)sai do vértice𝑢𝑢e entrano vértice𝑣𝑣. O 
vértice𝑣𝑣éadjacenteaovértice𝑢𝑢. 
 
 
• Rede 
É um grafo com algum tipo de fluxo fluindo entre os nós através dos arestas. Por exemplo, 
uma rede de estradas (arestas) unindo várias cidades (nós). O conjunto de veículos andando nas 
estradas é o fluxo que flui na rede. 
 
5.3 Problema de Caminho Mínimo 
 
Nesta seção é formulado um modelo de programação linear para o problema de caminho 
mínimo. O modelo é geral no sentido de que pode ser usado para achar o caminho mínimo entre 
dois nós da rede. 
Suponha que a rede de caminho mínimo inclua 𝑛𝑛 nós e que desejamos determinar o 
caminho mais curto entre quaisquer dois nós 𝑠𝑠 e 𝑡𝑡 da rede. O modelo de programação linear 
considera que uma unidade de fluxo entra na rede no nó 𝑠𝑠 e sai no nó 𝑡𝑡. 
Capítulo 5 Modelos de Otimização de Redes 
Métodos Quantitativos – Ciências Contábeis Jhoab Negreiros 
3 
Definam-se 𝑥𝑥𝑖𝑖𝑖𝑖 = 𝑞𝑞𝑢𝑢𝑞𝑞𝑛𝑛𝑡𝑡𝑖𝑖𝑞𝑞𝑞𝑞𝑞𝑞𝑞𝑞 𝑞𝑞𝑞𝑞 𝑓𝑓𝑓𝑓𝑢𝑢𝑥𝑥𝑓𝑓 𝑛𝑛𝑓𝑓 𝑞𝑞𝑎𝑎𝑎𝑎𝑓𝑓 (𝑖𝑖, 𝑖𝑖) = �1, 𝑠𝑠𝑞𝑞 𝑓𝑓 𝑞𝑞𝑎𝑎𝑎𝑎𝑓𝑓 (𝑖𝑖, 𝑖𝑖)𝑞𝑞𝑠𝑠𝑡𝑡𝑖𝑖𝑣𝑣𝑞𝑞𝑎𝑎 𝑚𝑚𝑞𝑞𝑖𝑖𝑠𝑠 𝑎𝑎𝑢𝑢𝑎𝑎𝑡𝑡𝑓𝑓0, 𝑎𝑎𝑞𝑞𝑠𝑠𝑓𝑓 𝑎𝑎𝑓𝑓𝑛𝑛𝑡𝑡𝑎𝑎á𝑎𝑎𝑖𝑖𝑓𝑓 � 
𝑎𝑎𝑖𝑖𝑖𝑖 = 𝑎𝑎𝑓𝑓𝑚𝑚𝑐𝑐𝑎𝑎𝑖𝑖𝑚𝑚𝑞𝑞𝑛𝑛𝑡𝑡𝑓𝑓 𝑞𝑞𝑓𝑓 𝑞𝑞𝑎𝑎𝑎𝑎𝑓𝑓 (𝑖𝑖, 𝑖𝑖) 
 
Assim, a função objetivo do programa linear se torna 
 
𝑀𝑀𝑖𝑖𝑛𝑛𝑖𝑖𝑚𝑚𝑖𝑖𝑀𝑀𝑞𝑞𝑎𝑎 𝑍𝑍 = � 𝑎𝑎𝑖𝑖𝑖𝑖 𝑥𝑥𝑖𝑖𝑖𝑖
𝑐𝑐𝑞𝑞𝑎𝑎𝑞𝑞 𝑡𝑡𝑓𝑓𝑞𝑞𝑓𝑓𝑠𝑠
𝑓𝑓𝑠𝑠 𝑞𝑞𝑎𝑎𝑎𝑎𝑓𝑓𝑠𝑠
𝑞𝑞𝑞𝑞𝑓𝑓𝑖𝑖𝑛𝑛𝑖𝑖𝑞𝑞𝑓𝑓𝑠𝑠 (𝑖𝑖 ,𝑖𝑖 )
 
 
As restrições representam a equação de conservação de fluxo em cada nó: 
 
𝐹𝐹𝑓𝑓𝑢𝑢𝑥𝑥𝑓𝑓 𝑡𝑡𝑓𝑓𝑡𝑡𝑞𝑞𝑓𝑓 𝑞𝑞𝑞𝑞 𝑞𝑞𝑛𝑛𝑡𝑡𝑎𝑎𝑞𝑞𝑞𝑞𝑞𝑞 = 𝐹𝐹𝑓𝑓𝑢𝑢𝑥𝑥𝑓𝑓 𝑡𝑡𝑓𝑓𝑡𝑡𝑞𝑞𝑓𝑓 𝑞𝑞𝑞𝑞 𝑠𝑠𝑞𝑞í𝑞𝑞𝑞𝑞 
 
Traduzindo matematicamente, temos, para o nó 𝑖𝑖: 
 
�
𝐸𝐸𝑛𝑛𝑡𝑡𝑎𝑎𝑞𝑞𝑞𝑞𝑞𝑞 𝑞𝑞𝑥𝑥𝑡𝑡𝑞𝑞𝑎𝑎𝑛𝑛𝑞𝑞
𝑐𝑐𝑞𝑞𝑎𝑎𝑞𝑞 𝑓𝑓 𝑛𝑛ó 𝑖𝑖 � + � 𝑥𝑥𝑖𝑖𝑖𝑖
𝑖𝑖
𝑡𝑡𝑓𝑓𝑞𝑞𝑓𝑓𝑠𝑠 𝑓𝑓𝑠𝑠
𝑞𝑞𝑎𝑎𝑎𝑎𝑓𝑓𝑠𝑠 (𝑖𝑖 ,𝑖𝑖 )
𝑞𝑞𝑞𝑞𝑓𝑓𝑖𝑖𝑛𝑛𝑖𝑖𝑞𝑞𝑓𝑓𝑠𝑠
= �𝑆𝑆𝑞𝑞í𝑞𝑞𝑞𝑞 𝑞𝑞𝑥𝑥𝑡𝑡𝑞𝑞𝑎𝑎𝑛𝑛𝑞𝑞𝑞𝑞𝑓𝑓 𝑛𝑛ó 𝑖𝑖 � + � 𝑥𝑥𝑖𝑖𝑗𝑗
𝑗𝑗
𝑡𝑡𝑓𝑓𝑞𝑞𝑓𝑓𝑠𝑠 𝑓𝑓𝑠𝑠
𝑞𝑞𝑎𝑎𝑎𝑎𝑓𝑓𝑠𝑠 (𝑖𝑖 ,𝑗𝑗)
𝑞𝑞𝑞𝑞𝑓𝑓𝑖𝑖𝑛𝑛𝑖𝑖𝑞𝑞𝑓𝑓𝑠𝑠
 
 
 
Exemplo 1. O sistema de visitação em um parque, é feito por carros elétricos dirigidos pelos 
guardas florestais. Esse sistema de estradas é mostrado na figura a seguir, na qual o local O é à 
entrada do parque; outras letras designam os locais de postos de guardas florestais. Os números 
fornecem as distâncias em quilômetros dessas estradas. 
 O parque tem uma vista panorâmica de destaque no posto T. Um pequeno número de 
carrinhos é usado para levar e trazer visitantes da entrada do parque para o posto T. 
 A gerência do parque está se deparando com o problema de determinar que rota da entrada 
do parque até o posto T tem a menor distância total para operação dos carrinhos. 
Capítulo 5 Modelos de Otimização de Redes 
Métodos Quantitativos – Ciências Contábeis Jhoab Negreiros 
4 
 
 
5.4 O Problema da Árvore de Expansão Mínima 
 
 O problema da árvore de expansão mínima pode ser sintetizado como segue: 
 
i. São fornecidos os nós de uma rede mas não as ligações. Em vez disso, são fornecidas as 
ligações potenciais e o comprimento positivo para cada uma delas se inseridas na rede; 
 
ii. Deseja desenhar a rede inserindo ligações suficientes para satisfazer à necessidade de que 
haja um caminho entre cada para de nós; 
 
iii. O objetivo é satisfazer essa necessidade de maneira a minimizar o comprimento total das 
ligações inseridas na rede. 
 
 Uma rede com 𝑛𝑛 nós requer apenas (𝑛𝑛 − 1) ligações para fornecer um caminho entre 
cada para de nós. Não precisam ser usadas ligações extras, já que isso aumentaria 
desnecessariamente o comprimento total das ligações escolhidas. 
 
 Algoritmo para o Problema da Árvore de Expansão Mínima 
 
i. Selecione qualquer nó arbitrariamente e depois o conecte (isto é, acrescente uma ligação) ao 
nó distinto mais próximo; 
 
ii. Identifique o nó sem conexão que esteja mais próximo a um nó conectado e, em seguida, 
conecte esse dois nós (isto é, acrescente uma ligação entre eles). Repita essa etapa até que 
todos os nós tenham sido conectados. 
 
iii. Desempate: Os empates para o nó distinto mais próximo (passo i) ou o nó não conectado mais 
próximo (passo ii) podem ser desfeitos de forma arbitrária e o algoritmo ainda deve conduzir a 
uma solução ótima. Entretanto, tais empates são sinal de que podem existir (mas não 
necessariamente) soluções ótimas múltiplas. Todas essas soluções ótimas podem ser 
eliminadas buscando-se todas as maneiras para se desempatar até sua conclusão. 
 
Capítulo 5 Modelos de Otimização de Redes 
Métodos Quantitativos – Ciências Contábeis Jhoab Negreiros 
5 
Exemplo 2. Retornando ao exemplo 1, temos o problema de instalar em cada postos dos guardas 
florestais um telefone. A questão é onde as linhas devem ser colocadas para que atenda a um 
númeromínimo de quilômetros de linhas instaladas. 
 
 
 
 
 
 
 
 
 
 
5.5 O problema do fluxo máximo 
 
Um dos problemas mais comuns a serem resolvidos em redes é determinar o fluxo máximo 
que pode fluir em determinada rede.O exemplo a seguir ilustra este tipo de problema. A rede a 
seguir ilustra a captação de água de um determinado manancial até umgrande reservatório de 
distribuição. 
 
 
O nó inicial1é chamado de nó origem ou nó fonte. O nó final6é chamado de nódestino ou nó 
sumidouro. Existem 10 arcos na rede sendo que podemos representar os arcos da seguinte forma 
(nó inicial, nó final): (1, 2); (1, 3); (2, 3); etc.. 
 
Os números em cima de cada arco dão aCapacidade do arco, ou seja, o fluxo máximo que 
pode passar no arco. Assim, por exemplo, no arco (3,4), o número 5 éa indicação de que sua 
capacidade é de 5 litros/segundo sendo esta, a quantidademáxima de água que pode passar 
naquele trecho de encanamento (arco).O problema que queremos resolver é achar o fluxo máximo, 
em litros/segundo, que podeser levado do nó 1 ao nó 6. 
Antesdecomeçarmosavercomoresolveroproblemavamosestabelecerpré-requisitosque, 
embora normalmente não explicitados, fazem parte do problema. São eles: 
Capítulo 5 Modelos de Otimização de Redes 
Métodos Quantitativos – Ciências Contábeis Jhoab Negreiros 
6 
 Todos os arcos são direcionados, ou seja, no arco (2 – 3), por exemplo, o fluxo só pode passar 
no sentido 2⇒ 3; 
 Assume-se conservação de fluxo, ou seja, todo fluxo que chega a um nó, sairá dele. 
 
Exemplo 3 – Resolva o problema de fluxo máximo mencionado acima. 
 
 
 
 
 
 
 
 
 
5.6 Atividades 
 
Exercício 1. Tomando como base o grafo seguir determine o caminho mínimo do nó 1 ao nó 6. 
 
 
 
 
Exercício 2. Use o Solver para determinar o caminho mais curto do nó 1 ao nó 7. 
 
 
Capítulo 5 Modelos de Otimização de Redes 
Métodos Quantitativos – Ciências Contábeis Jhoab Negreiros 
7 
Exercício 3. Determine a árvore de expansão mínima para o exercício 1. 
 
 
 
 
 
 
 
 
 
 
 
Exercício 4. Determine a árvore de expansão mínima para o exercício 2. 
 
 
 
 
 
 
 
 
 
Exercício 5. Três refinarias enviam um produto à base de gasolina a dois terminais de distribuição 
por meio de uma rede de tubulações. Qualquer demanda que não puder ser satisfeita pela rede é 
adquirida de outras fontes. A rede de tubulações é atendida por três estações de bombeamento, 
como mostrado no grafo a seguir. O produto flui pela rede na direção mostrada pelas setas. A 
capacidade de cada segmento de tubulação (mostrada diretamente nos arcos) é dada em milhões 
de barris por dia. Determine o seguinte: 
 
 
 
(a) A produção diária em cada refinaria que combina com a máxima capacidade da rede. 
 
 
 
 
(b) A demanda diária em cada terminal que combina com a máxima capacidade da rede. 
 
 
 
Capítulo 5 Modelos de Otimização de Redes 
Métodos Quantitativos – Ciências Contábeis Jhoab Negreiros 
8 
Exercício 6. Certo tipo de ração para frangos é transportado por caminhões de três silos a quatro 
granjas. Alguns dos silos não podem enviar ração diretamente para algumas das granjas. As 
capacidades das outras rotas estão limitadas pelo número de caminhões disponíveis e pelo número 
de viagens diárias. A tabela a seguir mostra as quantidades diárias fornecidas nos silos e as 
demandas nas granjas (em milhares de quilogramas). As entradas nas células da tabela 
especificam as capacidades diárias das rotas associadas. 
 
 Granjas 
 1 2 3 4 
Silos 
1 30 5 0 40 20 
2 0 0 5 90 20 
3 100 40 30 40 200 
 200 10 60 20 
 
 
(a) Determine a programação que satisfaça a maior demanda. 
 
 
 
 
(b) A programação proposta satisfará todas as demandas nas granjas? 
 
 
 
 
Exercício 7. No exercício 6, suponha que seja permitido transbordo entre os silos 1 e 2 e entre os 
silos 2 e 3. Suponhas também que o transbordo seja permitido entre as granjas 1 e 2, 2 e 3, e 3 e 4. 
A capacidade máxima diária nas duas vias nas rotas de transbordo propostas é de 50 (mil) kg. Qual 
é o efeito do transbordo sobre as demandas não satisfeitas nas granjas? 
	CAPÍTULO 5
	Modelos de Otimização de Redes