Buscar

Exercícios de Otimização em Programação Linear

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 5 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

Faculdade de Computac¸a˜o Universidade Federal de Uberlaˆndia
GSI027 – Otimizac¸a˜o
Segunda Lista de Exerc´ıcios
Exerc´ıcio 1: Considere o seguinte problema:
maximizar z = x1 + 5x2 + 3x3
sujeito a x1 + 2x2 + x3 = 3
2x1 − x2 = 4
x1, x2, x3 > 0.
A varia´vel x3 desempenha o papel de uma folga. Assim, nenhuma varia´vel
de folga e´ necessa´ria na primeira restric¸a˜o. Na segunda restric¸a˜o e´ necessa´ria
uma varia´vel artificial. Resolva o problema com o Me´todo do M-grande e com
o Me´todo das Duas Fases.
Exerc´ıcio 2: Considere o seguinte problema:
maximizar z = 2x1 + 2x2 + 4x3
sujeito a 2x1 + x2 + x3 6 2
3x1 + 4x2 + 2x3 > 8
x1, x2, x3 > 0.
Resolva com o Me´todo das Duas Fases e com o Me´todo Dual Simplex.
Exerc´ıcio 3: Analise o problema a seguir graficamente.
maximizar z = 2x1 + 5x2
sujeito a 3x1 + 2x2 > 6
2x1 + x2 6 2
x1, x2 > 0.
• Mostre como o Me´todo do M-grande vai indicar que o problema a seguir
na˜o tem nenhuma soluc¸a˜o via´vel.
• Mostre como o Me´todo das Duas Fases vai indicar que o problema a seguir
na˜o tem nenhuma soluc¸a˜o via´vel.
• Mostre como o Me´todo Dual Simplex vai indicar que o problema a seguir
na˜o tem nenhuma soluc¸a˜o via´vel.
Exerc´ıcio 4: Escreva o problema dual para cada um dos seguintes problemas
primais:
maximizar z = −5x1 + 2x2
sujeito a −x1 + x2 6 −2
2x1 + 3x2 6 5
x1, x2 > 0.
maximizar z = 6x1 + 3x2
sujeito a 6x1 − 3x2 + x3 > 2
3x1 + 4x2 + x3 > 5
x1, x2, x3 > 0.
maximizar z = x1 + x2
sujeito a 2x1 + x2 = 5
3x1 − x2 = 6
x1, x2 irrestritas.
Exerc´ıcio 5: Ache o valor o´timo da func¸a˜o objetivo para o seguinte problema,
atrave´s da inspec¸a˜o de seu dual.
minimizar z = 10x1 + 4x2 + 5x3
sujeito a 5x1 − 7x2 + 3x3 > 50
x1, x2, x3 > 0.
Exerc´ıcio 6: Resolva o dual do seguinte problema e enta˜o ache sua soluc¸a˜o
o´tima com base na soluc¸a˜o dual. A soluc¸a˜o do problema duas oferece vantagens
de ca´lculo em relac¸a˜o a` resoluc¸a˜o direta do problema primal? Justifique.
minimizar z = 5x1 + 6x2 + 3x3
sujeito a 5x1 + 5x2 + 3x3 > 50
x1 + x2 − x3 > 20.
7x1 + 6x2 − 9x3 > 30.
5x1 + 5x2 + 5x3 > 35.
2x1 + 4x2 − 15x3 > 10.
12x1 + 10x2 > 90.
x2 − 10x3 > 20.
x1, x2, x3 > 0.
Exerc´ıcio 7: Considere o seguinte problema:
minimizar z = 5x1 + 2x2
sujeito a x1 − x2 > 3
2x1 + 3x2 > 5.
x1, x2 > 0.
Pede-se:
• Resolva graficamente
• Resolva atrave´s do Me´todo Dual Simplex
• Se o lado direito da primeira restric¸a˜o for aumentado de 3 para 4, qual o
impacto na func¸a˜o objetivo?
• Se o lado direito da segunda restric¸a˜o for aumentado de 5 para 6, qual o
impacto na func¸a˜o objetivo?
• Quais os valores das varia´veis duais?
Exerc´ıcio 8: Considere o seguinte problema:
maximizar z = 6x1 + 3x2
sujeito a 6x1 − 3x2 + x3 > 2
3x1 + 4x2 + x3 > 5
x1, x2, x3 > 0.
Pede-se:
• Resolva graficamente
• Resolva atrave´s do Me´todo Dual Simplex
• Se o lado direito da primeira restric¸a˜o for aumentado de 2 para 3, qual o
impacto na func¸a˜o objetivo?
• Se o lado direito da segunda restric¸a˜o for aumentado de 5 para 6, qual o
impacto na func¸a˜o objetivo?
• Quais os valores das varia´veis duais?
Exerc´ıcio 9: A figura a seguir, representa uma rede de comunicac¸a˜o entre
duas estac¸o˜es (1 e 7).
A probabilidade de uma conexa˜o operar sem falhas e´ mostrada em cada arco.
Mensagens sa˜o enviadas da estac¸a˜o 1 a` estac¸a˜o 7, e o objetivo e´ determinar a rota
que maximizara´ a probabilidade de uma transmissa˜o bem sucedida. Formule
a situac¸a˜o como um problema de PL para Caminho Mı´nimo e determine sua
soluc¸a˜o atrave´s dos me´todos:
• Algoritmo de Dijkstra
• Algoritmo de Floyd
Exerc´ıcio 10: Uma empresa de telefonia celular atende 6 a´reas geogra´ficas.
As distaˆncias de sate´lite (em milhas) entre as 6 a´reas sa˜o dadas pela figura a
seguir. A empresa precisa determinar as rotas de mensagens mais eficientes que
devem ser estabelecidas entre cada duas a´reas da rede. Resolva utilizando o
Algoritmo de Floyd.
Exerc´ıcio 11: A figura a seguir da´ a distaˆncia em milhas entre pares de
cidades.
Use o Algoritmo de Dijkstra para achar o caminho mais curto entre as
seguintes cidades:
• 1 e 8
• 1 e 6
• 1 e 4