atividade49270

Prévia do material em texto

Atividades Pesquisa Operacional - Aulas 5 a 8
1. Espertinho vai trabalhar de carro todos os dias. Como acabou de concluir um curso de análise de redes, Espertinho sabe determinar o caminho mais curto até seu local de trabalho. Infelizmente, a rota escolhida é muito bem policiada e, com todas as multas por excesso de velocidade que ele recebe, o caminho mais curto pode não ser a melhor opção. Por isso, Espertinho decidiu escolher uma rota que maximizasse a probabilidade de ele não ser multado por um policial. A rede da Figura a seguir mostra as possíveis rotas entre sua casa e seu trabalho, e as probabilidades de ele não ser parado associadas com cada trecho. A probabilidade de ele não ser parado em uma rota é o produto das probabilidades associadas aos segmentos. Por exemplo, a probabilidade de não receber uma multa na rota 1 → 3 → 5 → 7 é 0,9 × 0,3 × 0,25 = 0,0675. O objetivo de Espertinho é selecionar a rota que maximize a probabilidade de ele não ser multado. 
2. Desenvolva a árvore B&B para cada um dos seguintes problemas. Por conveniência, sempre selecione x1 como a variável de ramificação no nó 0. 
(a) Maximizar z = 3x1 + 2x2
sujeito a 
2x1 + 5x2 ≤ 9
4x1 + 2x2 ≤ 9
x1 , x2 ≥ 0 e inteiras
	
	
	
	
	
	
	P L0 ⇒ P L1 e P L2
	
	P L1 - Max Z = 3x1 + 2x2
	
	
	P L2 - Max Z = 3x1 + 2x2
	
	sujeito a : 2x1 + 5x2 ≤ 9
	
	
	sujeito a : 2x1 + 5x2 ≤ 9
	
	
	4x1 + 2x2 ≤ 9
	
	
	
	
	
	4x1 + 2x2 ≤ 9
	
	
	x1 ≤ 1
	
	
	
	
	
	x1 ≥ 2
	
	x1 = 1 e x2 = 1, 4; Z= 5,8
	
	
	x1 = 2 e x2 = 0, 5; Z= 7
	
	
	
	
	
	
	P L1 ⇒ P L3 e P L4
	
	
	
	P L3 - Max Z = 3x1 + 2x2
	
	
	P L4 - Max Z = 3x1 + 2x2
	
	sujeito a : 2x1 + 5x2 ≤ 9
	
	
	sujeito a : 2x1 + 5x2 ≤ 9
	
	
	4x1 + 2x2 ≤ 9
	
	
	
	
	
	4x1 + 2x2 ≤ 9
	
	
	x1 ≤ 1
	
	
	
	
	
	x1 ≤ 1
	
	
	x2 ≤ 1
	
	
	
	
	
	x2 ≥ 2
	
	x1 = 1 e x2 = 1; Z= 5
	
	
	x1 = 0 e x2 = 1, 8; Z= 3,6
	
	
	
	
	
	
	P L2 ⇒ P L5 e P L6
	
	
	
	P L5 - Max Z = 3x1 + 2x2
	
	
	P L6 - Max Z = 3x1 + 2x2
	
	sujeito a : 2x1 + 5x2 ≤ 9
	
	
	sujeito a : 2x1 + 5x2 ≤ 9
	
	
	4x1 + 2x2 ≤ 9
	
	
	
	
	
	4x1 + 2x2 ≤ 9
	
	
	x1 ≥ 2
	
	
	
	
	
	x1 ≥ 2
	
	
	x2 = 0
	
	
	
	
	
	x2 ≥ 1
	
	x1 = 2, 25 e x2 = 0; Z=6,75
	
	x1 = 1, 75 e x2 = 1; Z= 7,25
PL4 ⇒ PL7
P L7 - Max Z = 3x1 + 2x2
sujeito a : 2x1 + 5x2 ≤ 9
4x1 + 2x2 ≤ 9
x1 ≤ 1
x2 ≤ 2
x2 ≤ 1
x1 = 0 e x2 = 1; Z = 2
	
	
	
	
	P L5 ⇒ P L8 e P L9
	P L8 - Max Z = 3x1 + 2x2
	
	
	P L9 - Max Z = 3x1 + 2x2
	sujeito a : 2x1 + 5x2 ≤ 9
	
	
	sujeito a : 2x1 + 5x2 ≤ 9
	
	4x1 + 2x2 ≤ 9
	
	
	4x1 + 2x2 ≤ 9
	
	x1 ≥ 2
	
	
	x1 ≥ 2
	
	x2 = 0
	
	
	x2 = 0
	
	x1
	≤ 2
	
	
	x2 ≥ 3
	x1 = 2, 25 e x2 = 0; Z=6,75
	
	x1 = 2 e x2 = 0; Z= 6
	PL6 ⇒ PL10
	
	
	PL8 ⇒ PL11
	P L10 - Max Z = 3x1 + 2x2
	
	
	P L11 - Max Z = 3x1 + 2x2
	sujeito a : 2x1 + 5x2 ≤ 9
	
	
	sujeito a : 2x1 + 5x2 ≤ 9
	
	4x1 + 2x2 ≤ 9
	
	
	4x1 + 2x2 ≤ 9
	
	x1
	≥ 2
	
	
	x1 ≥ 2
	
	x2
	≥ 1
	
	
	x2 = 0
	
	x1
	≤ 1
	
	
	x1 ≤ 2
	
	
	
	
	
	
	x1 ≥ 3
	x1 = 1 e x2 = 1; Z = 5
	
	IMPOSSIVEL
	
	
	
	
	
	
	
	
	
	
Max Z = 3x1 + 2x2
sujeito a : 2x1 + 5x2 ≤ 9
4x1 + 2x2 ≤ 9
	
	
	
	x1, x2 ≥ 0 e inteiras
	
	P L0 - x1 = 1, 6875 e x2 = 1, 125 ; Z = 7,3125
	
	
	
	P L0 ⇒ P L1 e P L2
	P L1 - Max Z = 3x1 + 2x2
	
	
	P L2 - Max Z = 3x1 + 2x2
	sujeito a : 2x1 + 5x2 ≤ 9
	
	
	
	sujeito a : 2x1 + 5x2 ≤ 9
	
	4x1 + 2x2 ≤ 9
	
	
	
	
	4x1 + 2x2 ≤ 9
	
	x2 ≤ 1
	
	
	
	
	x2 ≥ 2
	x1 = 1, 75 e x2 = 1; Z=7,25
	
	
	x1 = 0 e x2 = 1, 8; Z= 3,60
	
	
	
	P L1 ⇒ P L3 e P L4
	
	
	P L3 - Max Z = 3x1 + 2x2
	
	
	P L4 - Max Z = 3x1 + 2x2
	sujeito a : 2x1 + 5x2 ≤ 9
	
	
	
	sujeito a : 2x1 + 5x2 ≤ 9
	
	4x1 + 2x2 ≤ 9
	
	
	
	
	4x1 + 2x2 ≤ 9
	
	x2 ≤ 1
	
	
	
	
	x2 ≤ 1
	
	x1 ≤ 1
	
	
	
	
	x2 ≥ 2
	x1 = 1 e x2 = 1; Z=5
	
	
	
	x1 = 0 e x2 = 1; Z= 2
	
	
	
	
PL2 ⇒ PL5
	
	
P L5 - Max Z = 3x1 + 2x2
sujeito a : 2x1 + 5x2 ≤ 9
4x1 + 2x2 ≤ 9
x2 ≥ 2
x2 ≤ 1
Conclui-se que a função Z atinge seu máximo quando x1 = 2 e x2 = 0 com valor funcional Z = 6.
(b) Minimizar z = 5x1 + 4x2
sujeito a 
3x1 + 2x2 ≥ 5 
2x1 + 3x2 ≥ 7 
x1 , x2 ≥ 0 e inteiras 
	
	P L0 - x1 = 0, 2 e x2 = 2, 2 ; Z = 9,8
	
	
	
	
	
	
	
	
	
	
	
	
	P L0 ⇒ P L1 e P L2
	
	
	
	
	
	
	
	P L1 - Min Z = 5x1 + 4x2
	
	
	P L2 - Min Z = 5x1 + 4x2
	sujeito a : 3x1 + 2x2 ≥ 5
	
	
	sujeito a : 3x1 + 2x2 ≥ 5
	
	2x1 + 3x2 ≥ 7
	
	
	
	2x1 + 3x2 ≥ 7
	
	x1 = 0
	
	
	
	x1 ≥ 1
	x1 = 0 e x2 = 2, 5; Z= 10
	x1 = 1 e x2 = 1, 66; Z= 11,66
	
	
	
	
	
	
P L1 ⇒ P L3 e P L4
	
	
	
	
	
	
	
	P L3 - Min Z = 5x1 + 4x2
	
	
	P L4 - Min Z = 5x1 + 4x2
	sujeito a : 3x1 + 2x2 ≥ 5
	
	
	sujeito a : 3x1 + 2x2 ≥ 5
	
	2x1 + 3x2 ≥ 7
	
	
	
	2x1 + 3x2 ≥ 7
	
	x1 = 0
	
	
	
	x1 ≥ 1
	
	x2 ≤ 2
	
	
	
	x2 ≥ 3
	x1 = 0 e x2 = 2; Z= 8
	
	x1 = 0 e x2 = 3; Z= 12
	
	
	
	
	
	
P L2 ⇒ P L5 e P L6
	
	
	
	
	
	
	
	P L5 - Min Z = 5x1 + 4x2
	
	
	P L6 - Min Z = 5x1 + 4x2
	sujeito a : 3x1 + 2x2 ≥ 5
	
	
	sujeito a : 3x1 + 2x2 ≥ 5
	
	2x1 + 3x2 ≥ 7
	
	
	
	2x1 + 3x2 ≥ 7
	
	x1 = 0
	
	
	
	x1 ≥ 1
	
	x2 ≤ 2
	
	
	
	x2 ≥ 3
	x1 = 2 e x2 = 1; Z= 14
	
	
	
	x1 = 1 e x2 = 2; Z= 13
	
Min Z = 5x1 + 4x2
	
	
	
	sujeito a : 3x1 + 2x2 ≥ 5
	
	
	
	
	2x1 + 3x2 ≥ 7
	
	
	
	
	x1, x2 ≥ 0 e inteiras
	
	P L0 - x1 = 0, 2 e x2 = 2, 2 ; Z = 9,8
	
	
	
	
	P L0 ⇒ P L1 e P L2
	P L1 - Min Z = 5x1 + 4x2
	
	
	
	
	P L2 - Min Z = 5x1 + 4x2
	sujeito a : 3x1 + 2x2 ≥ 5
	
	
	
	
	sujeito a : 3x1 + 2x2 ≥ 5
	
	2x1 + 3x2 ≥ 7
	
	
	
	
	
	2x1 + 3x2 ≥ 7
	
	x1 ≤ 2
	
	
	
	
	
	x2 ≥ 3
	x1 = 0, 5 e x2 = 2; Z= 10,5
	
	
	
	
	x1 = 0 e x2 = 3; Z= 12
	
	
	
	
	
P L1 ⇒ P L3 e P L4
	
	
	P L3 - Min Z = 5x1 + 4x2
	
	
	
	
	P L4 - Min Z = 5x1 + 4x2
	sujeito a : 3x1 + 2x2 ≥ 5
	
	
	
	
	sujeito a : 3x1 + 2x2 ≥ 5
	
	2x1 + 3x2 ≥ 7
	
	
	
	
	
	2x1 + 3x2 ≥ 7
	
	x2 ≤ 2
	
	
	
	
	
	x2 ≥ 3
	
	x1 = 0
	
	
	
	
	
	x1 ≥ 1
	x1 = 0 e x2 = 2; Z= 8
	
	
	x1 = 1 e x2 = 1, 66; Z=11,66
	
	
	
	
	P L4 ⇒ P L5 e P L6
	
	
	P L5 - Min Z = 5x1 + 4x2
	
	
	
	
	P L6 - Min Z = 5x1 + 4x2
	sujeito a : 3x1 + 2x2 ≥ 5
	
	
	
	
	sujeito a : 3x1 + 2x2 ≥ 5
	
	2x1 + 3x2 ≥ 7
	
	
	
	
	
	2x1 + 3x2 ≥ 7
	
	x2 ≤ 2
	
	
	
	
	
	x2 ≤ 2
	
	x1 ≥ 1
	
	
	
	
	
	x1 ≥ 1
	
	x2 ≤ 1
	
	
	
	
	
	x2 ≥ 2
	x1 = 2 e x2 = 1; Z= 14
	
	
	
	
	x1 = 1 e x2 = 2; Z= 13
	
Função Z atinge seu mínimo quando x1 = 0 e x2 = 3 com valor funcional Z = 12. Note que para x1 = 0 e x2 = 2 com valor funcional Z = 8 não atende as nossas restrições.
3. Escreva ao menos 2 exemplos de programação não linear que um engenheiro ou administrador pode encontrar no dia a dia de trabalho.
Ex. 1. Um dos exemplos seria o transporte de produtos de petróleo dada uma seleção ou combinação de gasodutos, ou escolha de modal ônibus ou automóvel transportando passageiros entre pontos da rede em uma cidade. Devido à peculiaridade de cada problema as Funções Objetivos podem ter pontos de Descontinuidades, isto significa que estas Funções não possuem Derivadas nestes ponto e assim, estes problemas sendo tratados de maneira diferente dos que a Função Objetivo é Diferenciável.
Ex. 2. O escoamento das aguas em tubulações é dito como escoamento forcado, pois todo o contorno do fluxo está em contato com a parede do conduto e está excercendo nela uma presões atmosferica exterior. Na classificação hidráulica, os escoamento podem ser de diversos tipo de função de suas caracteristicas, como: laminar, turbulento, unidimenssional, bidimensional, rotacional, irrotacional, permanente, variavel, uniforme, variado livre, forçado, fluvial, torrencional, etc (Porto, 1999). O escoamento da água é dito como permanente quando suas caracteristicas fisicas (velocidade, pressão, temperatura e massa especifica) permanecem invariáveis ao longo do tempo e em qualquer ponto do fluxo, caso contrário o escoamento será nao permannte. Se o escoamento for permanente, ele pode ser uniforme ou variado, dependendo da velocodade. Será uniforme aquele escoamento em que os vetores velocidade, em módulo, direção e sentido, são idênticos em todos os pontos, e permanecem constantes ao longo das trajetórias da particula.
 
4. Resolva o Exemplo 1.1 da aula 8 considerando que são usadas as seguintes rotas: d(1, 2) = 5, d(1, 3) = 9, d(1, 4) = 8 d(2, 5) = 10, d(2, 6) = 17 d(3, 5) = 4, d(3, 6) = 10 d(4, 5) = 9, d(4, 6) = 9 d(5, 7) = 8 d(6, 7)= 9 
Estagio 1
D(1,2)=5 D(1,3)=9 D(1,4)=8
Estagio 2
D(2,5)=10 D(2,6)=17 D(3,5)=4 D(3,6)=10 D(4,5)=9 D(4,6)=9
Estagio 3
D(5,7)=8 D(6,7)=9
Logo o caminho mais curto e 1-3-5-7 21 minhas.