Capítulo_5_-_Modelos_de_Otimiz

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 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 
2
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ó �: 
 
01����
� ����������� � �ó � 3 + " ����
&'(') ')
$%*') ��,��
(+,�-�(')
= 05�í
� �������
� �ó � 3 + " ��66&'(') ')
$%*') ��,6�
(+,�-�(')
 
 
 
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 
3
 
 
5.3 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 �� 7 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 
4
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úmero mínimo de quilômetros de linhas instaladas. 
 
 
 
 
 
 
 
 
 
 
 
 
5.4 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 
5
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.