Avaliação 4 - Generação Ciclagem e Permanência Condições de Otimalidade - Otimização 2023-2

Avalia¸c˜ao 4 Genera¸c˜ao, Ciclagem e Permanˆencia; Condi¸c˜oes de Otimalidade 1. Quest˜ao 1 [5 pontos] Resolva o PPL a seguir de acordo com as etapas listadas abaixo. min −x1 + x2 − x3 + x4 s.a 2x1 − 3x2 − 5x3 + 6x4 ≤ 0 6x1 − 5x2 − 3x3 + 2x4 ≤ 0 3x1 + x2 + 2x3 + 4x4 ≤ 1 x1, x2 x3, x4 ≥ 0 (A) [4 pontos] Resolva o PPL usando a regra de Bland em todas as itera¸c˜oes. (B) [1 ponto] Se esse mesmo PPL fosse resolvido utilizando a regra Lexicogr´afica, a primeira itera¸c˜ao seria idˆentica ou diferente da que foi realizada no item (A)? 2. Quest˜ao 2 [5 pontos] Nesta quest˜ao, considere o PPL a seguir. (P) : min −5x1 − 4x2 + 3x3 s. a 4x1 + x2 − 2x3 ≥ 8 2x1 + 3x2 − x3 = 5 x1 , x2 ≥ 0, x3 ≤ 0 (A) [3,5 ponto] Escreva, da forma mais simplificada poss´ıvel, as condi¸c˜oes de otimalidade para o PPL. (B) [1,5 ponto] Sabendo que a solu¸c˜ao ´otima de (P) ´e dada por x∗ = (0; 0; −5)T, verfique que x∗ satisfaz as condi¸c˜oes de otimalidade escritas no item (A). AVALIAÇÃO 4 Questão 1. (A) min 𝑍 = − 𝑥1 + 𝑥2 − 𝑥3 + 𝑥4 s.a: 2𝑥1 − 3𝑥2 − 5𝑥3 + 6𝑥4 + 𝑥5 = 0 6𝑥1 − 5𝑥2 − 3𝑥3 + 2𝑥4 + 𝑥6 = 0 3𝑥1 + 𝑥2 + 2𝑥3 + 4𝑥4 + 𝑥7 = 1 𝑥𝑖 ≥ 0 ∀𝑖 ∈ {1, ..., 7} Aplicando simplex utilizando a regra de Bland temos que: VB x1 x2 x3 x4 x5 x6 x7 b Operação x5 2 -3 -5 6 1 0 0 0 L1<-L1/2 x6 5 -5 -3 2 0 1 0 0 L2<-L2-5L1 x7 3 1 2 4 0 0 1 1 L3<-L3-3L1 Z -1 1 -1 1 0 0 0 0 LZ<- LZ + L1 x1 1 -1,5 -2,5 3 0,5 0 0 0 L1<-L1+1,5L2 x6 0 2,5 9,5 -13 -2,5 1 0 0 L2<-L2/2,5 x7 0 5,5 9,5 -5 -1,5 0 1 1 L3<-L3-5,5L2 Z 0 -0,5 -3,5 4 0,5 0 0 0 LZ <- LZ+0,5L2 x1 1 0 3,2 -4,8 -1 0,6 0 0 L1<-L1/3,2 x2 0 1 3,8 -5,2 -1 0,4 0 0 L2<-L2-3,8L1 x7 0 0 -11,4 23,6 4 -2,2 1 1 L3<-L3+11,4L1 Z 0 0 -1,6 1,4 0 0,2 0 0 LZ<-LZ+1,6L1 x3 0,3125 0 1 -1,5 -0,3125 0,1875 0 0 L1<-L1+1,5L2 x2 -1,1875 1 0 0,5 0,1875 -0,3125 0 0 L2<-L2/0,5 x7 3,5625 0 0 6,5 0,4375 -0,0625 1 1 L3<-L3-6,5L2 Z 0,5 0 0 -1 -0,5 0,5 0 0 LZ<-LZ+L2 x3 -3,25 3 1 0 0,25 -0,75 0 0 L1<-L1+3,25L 3 x4 -2,375 2 0 1 0,375 -0,625 0 0 L2<-L2+2,375 L3 x7 19 -13 0 0 -2 4 1 1 L3<-L3/19 Z -1,875 2 0 0 -0,125 -0,125 0 0 LZ<-LZ+1,875 L3 x3 0 0,77631578 95 1 0 -0,09210526 316 -0,065789473 68 0,1710526316 0,1710526316 L1<-L1+(7/76) L2 x4 0 0,375 0 1 0,125 -0,125 0,125 0,125 L2<-8L2 x1 1 -0,68421052 63 0 0 -0,10526315 79 0,210526315 8 0,0526315789 5 0,0526315789 5 L3<-L3+(2/19) L2 Z 0 0,71710526 32 0 0 -0,32236842 11 0,269736842 1 0,0986842105 3 0,0986842105 3 LZ<-LZ+(49/15 2)L2 x3 0 1,05263157 9 1 0,73684210 53 0 -0,157894736 8 0,2631578947 0,2631578947 L1<-L1+(3/19) L3 x5 0 3 0 8 1 -1 1 1 L2<-L2+L3 x1 1 -0,36842105 26 0 0,84210526 32 0 0,105263157 9 0,1578947368 0,1578947368 L3<-(19/2)L3 Z 0 1,68421052 6 0 2,57894736 8 0 -0,052631578 95 0,4210526316 0,4210526316 LZ<-LZ+(1/19) L3 x3 1,5 0,5 1 2 0 0 0,5 0,5 L1<-L1+(3/19) L3 x5 9,5 -0,5 0 16 1 0 2,5 2,5 L2<-L2+L3 x6 9,5 -3,5 0 8 0 1 1,5 1,5 L3<-(19/2)L3 Z 0,5 1,5 0 3 0 0 0,5 0,5 LZ<-LZ+(1/19) L3 Solução ótima: ● 𝑥1 = 0 ● 𝑥2 = 0 ● 𝑥3 = 0, 5 ● 𝑥4 = 0 ● 𝑍 =− 0, 5 (B) Não, na ordem lexicográfica deveria entrar na base. 𝑥3 Questão 2. (A) Vamos inicialmente obter o modelo dual: max 8𝑢1 + 5𝑢2 s.a: 4𝑢1 + 2𝑢2 =− 5 𝑢1 + 3𝑢2 ≤− 4 − 2𝑢1 − 𝑢2 ≥ 3 𝑢1 ≥ 0, 𝑢2 Logo, as condições de otimalidade são: 4𝑥1 + 𝑥2 − 2𝑥3 ≥ 8 2𝑥1 + 3𝑥2 − 𝑥3 = 5 (8 − 4𝑥1 − 𝑥2 + 2𝑥3)𝑢1 = 0 (5 − 2𝑥1 − 3𝑥2 + 𝑥3)𝑢2 = 0 (5 + 4𝑢1 + 2𝑢2)𝑥1 = 0 (4 + 𝑢1 + 3𝑢2)𝑥2 = 0 (− 3 − 2𝑢1 − 𝑢2)𝑥3 = 0 4𝑢1 + 2𝑢2 =− 5 𝑢1 + 3𝑢2 ≤− 4 − 2𝑢1 − 𝑢2 ≥ 3 (B) (OK) 4𝑥1 + 𝑥2 − 2𝑥3 ≥ 8 => 10 ≥ 8 (OK) 2𝑥1 + 3𝑥2 − 𝑥3 = 5 => 5 = 5 (8 − 4𝑥1 − 𝑥2 + 2𝑥3)𝑢1 = 0 => − 2𝑢1 = 0 => 𝑢1 = 0 (OK) (5 − 2𝑥1 − 3𝑥2 + 𝑥3)𝑢2 = 0 => 0𝑢2 = 0 (OK) (5 + 4𝑢1 + 2𝑢2)𝑥1 = 0 => 0 = 0 (OK) (4 + 𝑢1 + 3𝑢2)𝑥2 = 0 => 0 = 0 (− 3 − 2𝑢1 − 𝑢2)𝑥3 = 0 => − 3 − 𝑢2 = 0 => 𝑢2 =− 3 (NÃO OK) 4𝑢1 + 2𝑢2 =− 5 =>− 6 ≠− 5 (OK) 𝑢1 + 3𝑢2 ≤− 4 => − 6 ≤ − 4 (OK) − 2𝑢1 − 𝑢2 ≥ 3 => 3 ≥ 3 Não é ótima, pois não satisfaz a condição 4𝑢1 + 2𝑢2 =− 5 do dual.