Avaliação 2 - Solução Gráfica Formatos de Ppl e Sbvs - Otimização 2023-2

Avalia¸c˜ao 2 Solu¸c˜ao Gr´afica, Formatos de PPL e SBVs 1. Quest˜ao 1 [8 pontos] Considere o PPL dado por min 2x1 + kx2 s.a 5x1 + 3x2 ≥ 1500 3x1 + 5x2 ≥ 1500 2x1 + 2x2 ≥ 750 −2x1 + x2 ≤ 100 x1, x2 ≥ 0 (A) [1,0 ponto] Fa¸ca o desenho da regi˜ao vi´avel do PPL, deixando bem claras as fronteiras de todas as restri¸c˜oes e quais s˜ao os pontos vi´aveis. (B) [1,0 ponto] Fa¸ca o desenho do gradiente da fun¸c˜ao objetivo e de pelo menos uma curva de n´ıvel utilizando k = 1. Identifique a(s) solu¸c˜ao(˜oes), se houver. (C) [2,5 pontos] Determine para quais valores de k temos solu¸c˜ao ´unica, solu¸c˜ao alternativa (lateral ´otima) e solu¸c˜ao ilimitada. Em cada caso, indique qual(ais) ´e(s˜ao) a(s) solu¸c˜ao(˜oes). (D) [1,0 ponto] Escreva o PPL no formato padr˜ao. (E) [1,5 pontos] Considerando o PPL no formato padr˜ao do item anterior e a regi˜ao vi´avel desenhada no item (A), identifique para cada v´ertice da regi˜ao vi´avel qual(ais) ´e(s˜ao) a(s) Solu¸c˜ao(˜oes) B´asica(s) Vi´avel(eis) associada(s) (SBVs). (F) [1,0 ponto] Com base nas SBVs listadas no item anterior, indique se cada v´ertice da regi˜ao vi´avel do item (A) ´e degenerado ou n˜ao. Justifique sua resposta. 2. Quest˜ao 2 [2 pontos] Escreva o PPL a seguir no formato canˆonico de minimiza¸c˜ao max x1 + 2x2 − x3 s.a x1 + x2 + x3 = 4 3x1 − x2 + 3x3 ≥ 5 2x1 + x2 − 2x3 ≤ 8 x1 ≥ 0 x2 irrestrito x3 ≤ 0 Avaliacao 2 1) PPL min 2x1 + 3x2 Sujeito a: 5x1 + 3x2 >= 1500 3x1 + 5x2 >= 1500 2x1 + 2x2 >= 750 x1 + x2 <= 1000 (A) I) 5x1 + 3x2 = 1500 A = (0,500) B = (300,0) II) 3x1 + 5x2 = 1500 C = (0,300) D = (500,0) IV) -2x1 + x2 <= 100 G = (0,100) H = (-50,0) III) 2x1 + 2x2 = 750 E = (0,375) F = (375,0) Respeito a Solucao no primeiro quadrante Representacao de cada regra: I) II) III) Figura original 2 IV) Regiao Viavel Pontos Viaveis S1) Interseccao da rede I com IV 5x1 + 3x2 = 1500 -2x1 + x2 = 100 5x1 + 3x2 = 1500 +6x2 - 3x1 = 300 11x2 = 1200 x2 = 1200/11 x2 = 109.1 -2(109.1) + x2 = 100 x2 = 100 + 218.2 x2 = 318.2 S2) Interseccao da rede I com II 3x1 + 5x2 = 1500 -5x1 - 3x2 = 1500 5x1 + 25x2 = 7500 3(137.5) + 5x2 = 1500 5x1 = 1500 - 562.5 x1 = 937.5 x2 = 187.5 S3) -> D S3 = (500,0) S2 = (137.5,187.5) Soluções Viaveis (B) Gradiente é forca negativa e uma Curva de Nível 2x_1 + kx_2 df [ ∂f ∂f ] ∇f = ( -- , -- ) x 100 dx_1 dx_2 k = 1 boxPt = (200,100) x_1 = 0 x_2 = 1 x_1 = 2 x_2 = 0 (boxPt é mais facil de representar) 500 | 450 | 400 | 350 | 300 | 250 | 200 | 150 | 100 | 50 | 0 | --------------------------------------------------- 0 50 100 150 200 250 300 350 400 450 500 x_1 (Vetor gradiente) Curva de nível Curva de nivel é perpendicular ao vetor gradiente y₁ = m₁ (x - x₀) y₀ = m ( x - x₀) m₁ = y₂₀ m = y₂₀ m_ (1/2) (Nos há solução nesse curva) m₉ = m_c = -1 1 m_c = 1 y_c = -2 (C)(I) gráfica mostra que o ponto que deve minimizar a função 2x_1 faz deve ser valido para [aj], dö que x₁ é um ponto de minimização do vetor gradiente Assim 2x_1 + fx²x² = 2 (107,5) + k (107,5) = f f = 375 + k 107,5 valor ótimo (II) Forma Padrão 5x₂ +3x₂ > 1500 -> 5x₁ + 3x₂ - x₃ = 1500 3x₁ + 5x₂ > 1500 -> 3x₁ + 5x₂ - x₄ = 1500 2x₁ + 4x₂ > 750 -> 2x₁ + 4x₂ - x₅ = 750 -2x₁ + 1x₂ < 100 -> -2x₁ + 1x₂ + x₆ = 100 x₁, x₂ > 0 x₁, x₂, x₃, x₄, x₅, x₆ > 0 (2) max x_1 + 2x_2 - x_3 SA x_1 + 3x_2 + x_3 = 4 { 3x_1 - 2x_2 + 3x_3 >= 5 -> -x_4 2x_1 + x_3 <= 8 -> +x_5 {x_no tem restrição -> x_2 = x_2^+ - x_2^-; x_1, x_2^+, x_2^-, x_3 >= 0 x_3 <= 0 Substituicao: x_3 = x_3^1 -> x_3^1 >= 0 max -> min z = x_1 + 2x_2 - x_3 min(-z) z = -x_1 - 2x_2 + x_3 x_1 + 3x_2 + x_3 = 4 { 3x_1 - 2x_2 + 3x_3 - x_4 = 5 2x_1 + x_2 - 2x_3 + x_5 = 8 trocar as novas restriçôes (-1) z = -x_1 - 2x_2 + x_3 x_3 + (2 + x_2^+ - x_2^-) -> 4 3x_1 - x_3 - x_2^- - 3(3x_2^+ - x_2^-) + x_4 = 5 2x_1 + (x_2^+ - x_2^-) - 2(-x_1) + x_5 = 8 escrever melhor pra o ponto que deu m... minimizar -x_1 - 2x_2 + x_3 x_1 + -x_2^+ - x_2^- - x_3 = 4 3x_1 - x_2^+ + x_2^- - 3x_3 - x_4 = 5 2x_1 + x_2^+ - 2 - 2x_3 + x_5 = 8 x_1, x_2^+, x_2^-, x_3, x_4, x_5 >= 0