Baixe o app para aproveitar ainda mais
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
Compartilhar