POII - Otimização em redes - parte 2 - Marcela Luiza

Prévia do material em texto

1 
 
 
 
 
 
 
FACULDADE PROFESSOR MIGUEL ÂNGELO DA SILVA SANTOS – FeMASS 
 
 
 
 
 
 
 
 
 
 
 
 
PROBLEMAS DE OTIMIZAÇÃO EM REDES 
Parte 2 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
MACAÉ 
2020 
 
 
 
2 
 
 
 
 
 PESQUISA OPERACIONAL II 
 
 
 
 
PROBLEMAS DE OTIMIZAÇÃO EM REDES 
Parte 2 
 
 
 
 
 
 
POR: 
MARCELA LUIZA C. SANTOS 
 
 
 
 
 
Trabalho apresentado ao Curso de Engenharia de 
Produção da Faculdade Professor Miguel Ângelo da 
Silva Santos apresentado, à disciplina de Pesquisa 
Operacional II. Professor Orientador: Irineu de A. Lima 
 
 
 
 
 
 
 
MACAÉ 
2020 
 
 
3 
 
 
 
 
 
1) Formulação em PL para solução do Caminho Mínimo 
Revisite o exemplo 6.3-6 (Livro Taha, Cap. 6 – p. 116), cuja rede é apresentada 
abaixo. Logo, escreva o modelo de PL e restrições para solução e aplique o software 
LINGO para determinar a solução de caminho mínimo, entre os pares de nós origem-
destino abaixo: 
 
 
a) Nó 1 ao Nó 5. 
Pelo método simplex a solução ótima foi 90 e o caminho mínimo 1-3-5. 
LINDO 
 
 
 
 
 
 
 
 
 
4 
 
 
 
 
 SOLUÇÃO ÓTIMA 
 
INTERPRETAÇÃO 
Após realização do modelo e desenvolvimento no programa LINDO, verificou-
se que na página Solution Report, foram apresentados valores binários, sendo o 1 
representando a ligação dos nós do caminho mínimo para a solução ótima, sendo 
as ligações para essa solução x13 e x35, dessa forma o caminho encontrado foi 1-
3-5. 
 
b) Nó 2 ao Nó 5. 
Pelo método simplex a solução ótima foi 80 e o caminho mínimo 2-3-5. 
LINDO 
 
 
 
5 
 
 
 
 
 
SOLUÇÃO ÓTIMA 
 
INTERPRETAÇÃO 
Após realização do modelo e desenvolvimento no programa LINDO, verificou-
se que na página Solution Report, foram apresentados valores binários, sendo o 1 
representando a ligação dos nós do caminho mínimo para a solução ótima, sendo 
as ligações para essa solução x23 e x35, dessa forma o caminho encontrado foi 2-
3-5. 
 
2) Formulação em PL para solução de Fluxo Máximo 
Analise as redes de fluxo nos três casos abaixo, que representam ambientes em que 
se desejam estimar o fluxo máximo (F) entre os nós origem e destino indicados. 
Logo, para cada caso, faça: - Escreva o modelo de PL e restrições para solução; - 
Aplique o software LINGO para determinar a solução de fluxo máximo e quantidades 
inerentes aos caminhos possíveis. Obs.: Capriche na interpretação e relatório de 
documentação para justificar a solução ótima alcançada. 
 
 
 
 
 
 
 
6 
 
 
 
 
 Caso 1) 
 
Pelo método simplex a solução ótima foi: xa1=x4b=40, xa2=x13=x14=x3b=20, e o 
fluxo máximo 60. 
 
LINDO 
 
 
SOLUÇÃO ÓTIMA 
 
 
 
7 
 
 
 
 
 
 
INTERPRETAÇÃO 
Após realização do modelo e desenvolvimento no programa LINDO, verificou-
se que na página Solution Report, a solução ótima para maior fluxo na variável de 
valor maior que zero, obtendo, portanto, como soluções ótima xa1=x4b=40, 
xa2=x13=x14=x3b=20, e o fluxo máximo 60. 
 
Caso 2) 
 
Pelo método simplex a solução ótima foi: x12=x24=x43=7, x13=14, x15=x23=4, 
x32=x35=10, x25=6, x34=x45=5 e o fluxo máximo 25. 
LINDO 
 
 
 
8 
 
 
 
 
 
 
SOLUÇÃO ÓTIMA 
 
INTERPRETAÇÃO 
 
 
9 
 
 
 
 
 Após realização do modelo e desenvolvimento no programa LINDO, verificou-
se que na página Solution Report, a solução ótima para maior fluxo na variável de 
valor maior que zero, obtendo, portanto, como soluções ótima x12=x24=x43=7, x13=14, 
x15=x23=4, x32=x35=10, x25=6, x34=x45=5 e o fluxo máximo 25. 
 
Caso 3) 
 
Pelo método simplex a solução ótima foi: x12=9, x13=x57=8, x47=7, x24=4, 
x26=x35=6, x32=x36=1, x65=x67=2, x64=3, e o fluxo máximo 17. 
LINDO 
 
 
SOLUÇÃO ÓTIMA 
 
 
10 
 
 
 
 
 
 
INTERPRETAÇÃO 
Após realização do modelo e desenvolvimento no programa LINDO, verificou-
se que na página Solution Report, a solução ótima para maior fluxo na variável de 
valor maior que zero, obtendo, portanto, como soluções ótima x12=9, x13=x57=8, 
x47=7, x24=4, x26=x35=6, x32=x36=1, x65=x67=2, x64=3, e o fluxo máximo 17.