Slide - Dualidade 2020-2

Programa¸c˜ao Linear e Inteira ENP012 Prof. Dr. Alexandre Xavier Martins LASOS - DEENP - ICEA Dualidade ▶ Para cada PPL que resolvemos, existe um outro PPL associado que ´e resolvido simultaneamente; ▶ Este outro PPL traz algumas propriedades importantes e que nos d´a algumas interpreta¸c˜oes econˆomicas valiosas; ▶ Chamamos o PPL original de problema Primal, enquanto o PPL associado ao Primal recebe o nome de Dual; 2 / 40 Dualidade Exemplo Uma certa ind´ustria disp˜oes de 3 recursos A, B e C em quantidades limitadas. Com esses recursos, a ind´ustria pretende produzir 2 produtos: P1 e P2. Para fazer uma unidade de P1 ´e utilizado 1 unidade A, 1 de B e 7 de C, enquanto cada unidade de P2 se usa 2 unidades de A, 1 de B e 4 de C. A disponibilidade de A, B e C ´e de 14, 9 e 56, respectivamente. A ind´ustria sabe que cada unidade produzida de P1 d´a um lucro de 5 e cada unidade de P2 d´a um lucro de 6. O problema de programa¸c˜ao da empresa ´e determinar a quantidade a ser produzida de P1 e P2 de modo a maximizar o lucro total. 3 / 40 Dualidade Exemplo Max Q(x) = 5x1 + 6x2 Sujeito a: x1 + 2x2 ≤ 14 x1 + x2 ≤ 9 7x1 + 4x2 ≤ 56 x1, x2 ≥ 0 4 / 40 Dualidade Exemplo Antes de resolver o modelo, vamos pensar nas seguintes situa¸c˜oes: ▶ A empresa ao inv´es de produzir P1 e P2 deseja vender seu estoque de mat´eria-prima; ▶ A empresa deseja adquirir mais mat´eria-prima; Para cada uma dessas situa¸c˜oes o que se deseja saber ´e: Qual o valor dos recursos A, B e C? 5 / 40 Dualidade Exemplo ▶ Lembrando que as quantidades de A, B e C s˜ao 14, 9 e 56; ▶ Vamos dizer que y1, y2 e y3 s˜ao os valores associados `as mat´erias-primas; ▶ Assim, o valor total ´e dado por Q(y) = 14y1 + 9y2 + 56y3 6 / 40 Dualidade Exemplo ▶ Ao produzir uma unidade de P1 a empresa obtem um lucro de 5; ▶ Para isso, o consumo ´e de 1 unidade de A, 1 de B e 7 de C; ▶ Dessa forma, se a empresa deseja vender essa combina¸c˜ao de recuros o valor somado deve ser pelo menos o lucro de P1; ▶ Assim, temos que: y1 + y2 + 7y3 ≥ 5 ▶ Pelo mesmo racioc´ınio temos que: 2y1 + y2 + 4y3 ≥ 6 ▶ Sabemos que os valores dos recursos devem ser maiores que zero, assim: y1, y2, y3 ≥ 0 7 / 40 Dualidade Exemplo Min Q(y) = 14y1 + 9y2 + 56y3 Sujeito a: 1y1 + 1y2 + 7y3 ≥ 5 2y1 + 1y2 + 4y3 ≥ 6 y1, y2, y3 ≥ 0 8 / 40 Dualidade Exemplo Note que existe exatamente uma vari´avel Dual para cada restri¸c˜ao do Primal e exatamente uma restri¸c˜ao do Dual para cada vari´avel do Primal. Exerc´ıcio Antes de prosseguirmos resolva os modelos no LINGO e verifique as solu¸c˜oes obtidas. 9 / 40 Dualidade Forma Canˆonica Primal: Max Q(x) = cx Sujeito a: Ax ≤ b x ≥ 0 Dual: Min Q(y) = yb Sujeito a: yA ≥ c y ≥ 0 10 / 40 Dualidade Dual do dual Dual: Min yb Sujeito a: yA ≥ c y ≥ 0 Transformando num problema de maximiza¸c˜ao temos: Max (−bt)yt Sujeito a: (−At)yt ≤ (−ct) yt ≥ 0 11 / 40 Dualidade Dual do dual Dual: Max (−bt)yt Sujeito a: (−At)yt ≤ (−ct) yt ≥ 0 Dual do dual Min xt(−ct) Sujeito a: xt(−At) ≥ (−bt) xt ≥ 0 12 / 40 Dualidade Dual do dual Defini¸c˜ao: O Dual do dual ´e o Primal. Max cx Sujeito a: Ax ≤ b x ≥ 0 13 / 40 Dualidade Dual de qualquer problema Considere o seguinte PPL Max c1x1 + c2x2 + c3x3 Sujeito a: A11x1 + A12x2 + A13x3 ≤ b1 A21x1 + A22x2 + A23x3 ≥ b2 A31x1 + A32x2 + A33x3 = b3 x1 ≥ 0, x2 ≤ 0, x3 livre 14 / 40 Dualidade Dual de qualquer problema Para colocar o problema na forma canˆonica devemos: ▶ Multiplicar a segunda restri¸c˜ao por (-1); ▶ Substituir a terceira equa¸c˜ao por duas inequa¸c˜oes de sinais opostos; ▶ Substituir x2 por −x′ 2; ▶ Substituir x3 por x′ 3 − x′′ 3 15 / 40 Dualidade Dual de qualquer problema Assim temos: Max c1x1 − c2x′ 2 + c3x′ 3 − c3x′′ 3 Sujeito a: A11x1 − A12x′ 2 + A13x′ 3 − A13x′′ 3 ≤ b1 −A21x1 + A22x′ 2 − A23x′ 3 + A23x′′ 3 ≤ −b2 A31x1 − A32x′ 2 + A33x′ 3 − A33x′′ 3 ≤ b3 −A31x1 + A32x′ 2 − A33x′ 3 + A33x′′ 3 ≤ −b3 x1 ≥ 0, x′ 2 ≥ 0, x′ 3 ≥ 0, x′′ 3 ≥ 0 16 / 40 Dualidade Dual de qualquer problema Considerando as vari´aveis duais associadas a cada uma das restri¸c˜oes como y1, y′ 2, y′ 3 e y′′ 3 , obtemos o seguinte problema dual: Min y1b1 − y′ 2b2 + y′ 3b3 − y′′ 3 b3 Sujeito a: y1A11 − y′ 2A21 + y′ 3A31 − y′′ 3 A31 ≥ c1 −y1A12 + y′ 2A22 − y′ 3A32 + y′′ 3 A32 ≥ −c2 y1A13 − y′ 2A23 + y′ 3A33 − y′′ 3 A33 ≥ c3 −y1A13 + y′ 2A23 − y′ 3A33 + y′′ 3 A33 ≥ −c3 y1 ≥ 0, y′ 2 ≥ 0, y′ 3 ≥ 0, y′′ 3 ≥ 0 17 / 40 Dualidade Dual de qualquer problema Podemos verificar que as duas ´ultimas restri¸c˜oes formam uma igualdade. Finalmente, fazendo y2 = −y′ 2, y3 = y′ 3 − y′′ 3 , temos: Min y1b1 + y2b2 + y3b3 Sujeito a: y1A11 + y2A21 + y3A31 ≥ c1 y1A12 + y2A22y3A32 ≤ c2 y1A13 + y2A23 + y3A33 = c3 y1 ≥ 0, y2 ≤ 0, y3 livre 18 / 40 Dualidade Dual de qualquer problema Tabela: Quadro de transforma¸c˜ao Primal-Dual Minimiza¸c˜ao Maximiza¸c˜ao ≥ 0 ≤ Vari´aveis ≤ 0 ≥ Restri¸c˜oes Livre = ≥ ≥ 0 Restri¸c˜oes ≤ ≤ 0 Vari´aveis = Livre 19 / 40 Dualidade Exerc´ıcio Encontre o dual do seguinte PPL: Max Q(x) = 8x1 + 3x2 − 2x3 Sujeito a: x1 − 6x2 + x3 ≥ 2 5x1 + 7x2 − 2x3 = −4 x1 ≤ 0, x2 ≥ 0, x3 livre 20 / 40 Dualidade Rela¸c˜oes Primais-Duais ▶ Sejam os problemas primal/dual de maximizar Q(x)/minimizar Q(y); ▶ Sejam x0 e y0 solu¸c˜oes vi´aveis quaisquer para os problemas primal e dual respectivamente; ▶ Para o problema de maximiza¸c˜ao temos que (1) Ax0 ≤ b, x0 ≥ 0 e para o dual temos que (2) y0A ≥ c, y0 ≥ 0; ▶ Multiplicando (1) por y0 e (2) por x0 temos que: cx0 ≤ y0Ax0 ≤ y0b; ▶ Este resultado ´e conhecido como propriedade da dualidade fraca. 21 / 40 Dualidade Rela¸c˜oes Primais-Duais A fun¸c˜ao objetivo de qualquer solu¸c˜ao vi´avel de um problema de minimiza¸c˜ao ´e sempre maior ou igual que qualquer fun¸c˜ao objetivo do problema dual de maximiza¸c˜ao associado Teorema Fundamental da Dualidade ▶ Ambos possuem solu¸c˜ao ´otima e cx∗ = y∗b; ▶ Um problema ´e ilimitado e o outro n˜ao tem solu¸c˜ao vi´avel; ▶ Os dois problemas podem ser invi´aveis; 22 / 40 Dualidade Teoremas das Folgas Complementares Se x∗ ´e o ´otimo do problema primal e y∗ o ´otimo do problema dual, ent˜ao: (y∗A − c)x∗ = 0 e y∗(Ax∗ − b) = 0. ▶ Esse teorema implica que se uma restri¸c˜ao do primal apresenta folga a vari´avel dual associada ´e igual a zero; ▶ Se a restri¸c˜ao ´e justa, ent˜ao a vari´avel associada pode ser diferente de zero; 23 / 40 Dualidade Exemplo Max Q(x) = 4x1 + 5x2 + 3x3 Sujeito a: x1 + 2x2 + 2x3 ≤ 100 6x1 + 6x2 + 4x3 ≤ 360 8x1 + 4x2 + 4x3 ≤ 400 x1, x2, x3 ≥ 0 Seja a solu¸c˜ao Q(x∗) = 280 com x = (20 40 0)t. 24 / 40 Dualidade Exemplo O problema dual associado ´e: Min Q(y) = 100y1 + 360y2 + 400y3 Sujeito a: y1 + 6y2 + 8y3 ≥ 4 2y1 + 6y2 + 4y3 ≥ 5 2y1 + 4y2 + 4y3 ≥ 3 y1, y2, y3 ≥ 0 25 / 40 Dualidade Exemplo ▶ Como 20 + 2(40) + 2(0) = 100 → y1 =? ▶ Como 6(20) + 6(40) + 4(0) = 360 → y2 =? ▶ 8(20) + 4(40) + 4(0) ≤ 400 → y3 = 0 ▶ Como x1 > 0 → y1 + 6y2 + 8(0) = 4 ▶ Como x2 > 0 → 2y1 + 6y2 + 4(0) = 5 ▶ Resolvendo temos que y1 = 1, y2 = 1 2 e y3 = 0. 26 / 40 Dualidade Exerc´ıcio Min Q(x) = 2x1 + 3x2 + 5x3 + 2x4 + 3x5 Sujeito a: x1 + 2x2 + 2x3 + x4 + 3x5 ≥ 4 2x1 − 2x2 + 3x3 + x4 + x5 ≥ 3 x1, x2, x3, x4, x5 ≥ 0 ▶ Encontre o dual e o resolva graficamente; ▶ Encontre a solu¸c˜ao do Primal usando o teorema das folgas complementares. 27 / 40 eee Dualidade Interpretacao Econémica Seja o seguinte PPL, que tem por objetivo maximizar o lucro de producao de alguns produtos sujeito a restricdes operacionais. Max Q(x) = Oy Gx; Sujeito a: et ajxXj < b),V; =1,2,...,m xj 2 0,V; =1,2,...,0 28 / 40 eee Dualidade Interpretagao Econémica E o seu Dual é definido por: Min Q(y) = er, iyi Sujeito a: ey ay) < G,Vj =1,2,...,0 yi = 0, Vi = 1, 2, rey A 29 / 40 eee Dualidade Interpretacao Econémica Suponhamos que x* e y* sejam solucdes dtimas dos problemas primal e dual respectivamente. Entao pelo teorema basico da dualidade, temos: P Q(x*) = Q(y*) = oe") biy; > Se a quantidade do recurso i for alterada de b; para bi = b; + Abj, a variagao de Q(x) é dada por AQ = (Abj)y;’. > Entdo y; é a taxa de variacdo do valor étimo de Q(x*) da fun¢do objetivo para a variacdo de uma unidade na disponibilidade do recurso 1; > Este é 0 preco-sombra, ‘shadow price’, valor incremental, ou seja, O preco extra que se esta disposto a pagar por uma unidade adicional do recurso | 30 / 40 Dualidade Exemplo Voltando ao exemplo: Max Q(x) = 4x1 + 5x2 + 3x3 Sujeito a: x1 + 2x2 + 2x3 ≤ 100 6x1 + 6x2 + 4x3 ≤ 360 8x1 + 4x2 + 4x3 ≤ 400 x1, x2, x3 ≥ 0 Com a solu¸c˜ao dual dada por y∗ = (1 1 2 0) 31 / 40 Dualidade Exemplo ▶ O significado do valor ´otimo de uma vari´avel dual ´e o limite que devo pagar por uma unidade adicional do recurso associado `a vari´avel ▶ Assim, temos que ao incrementar o recurso da primeira restri¸c˜ao do primal de 100 para 101, iremos passar a fun¸c˜ao objetivo de 280 para 281; ▶ Para o recurso da segunda de 360 para 361 a fun¸c˜ao objetivo passar´a a ser 280, 5; ▶ Para a terceira restri¸c˜ao n˜ao h´a incremento na fun¸c˜ao objetivo; ▶ Essas varia¸c˜oes s˜ao verdadeiras at´e um determinado limite que tamb´em varia de problema para problema. 32 / 40 Dualidade Leitura do Quadro Simplex y4 y5 y1 y2 y3 VB x1 x2 x3 x4 x5 b x2 0 1 1 -1 0 5 x1 1 0 -1 2 0 4 x5 0 0 3 -10 1 8 0 0 1 4 0 Q′(x) + 50 33 / 40 Dualidade Algoritmo Dual Simplex Min Q(x) = 2x1 + 3x2 + 4x3 Sujeito a: −x1 − 2x2 − x3 ≤ −3 −2x1 + x2 − 3x3 ≤ −4 x1, x2, x3 ≥ 0 34 / 40 Dualidade Algoritmo Dual Simplex VB x1 x2 x3 x4 x5 b x4 -1 -2 -1 1 0 -3 x5 -2 1 -3 0 1 -4 2 3 4 0 0 Q(x) Repare que esta solu¸c˜ao ´e vi´avel no Dual e invi´avel no Primal. Neste caso podemos restabelecer a viabilidade do primal ao mesmo tempo em que se mantem a viabilidade do dual. 35 / 40 Dualidade Algoritmo Dual Simplex ▶ O primeiro passo ´e escolher uma vari´avel para sair da base; ▶ Como no primal simplex, escolhemos a vari´avel mais negativa, no exmplo, x5; ▶ Para entrar na base, neste caso, devemos escolher uma vari´avel com coeficiente menor que zero na linha, pois s´o assim ´e poss´ıvel gerar uma viabilidade no primal; ▶ Se n˜ao existir nenhum coefciente negativo na linha da vari´avel que sai da base, o dual ´e ilimitado, logo o primal ´e invi´avel; 36 / 40 Dualidade Algoritmo Dual Simplex ▶ Dado que exista mais de uma op¸c˜ao para entrar na base devemos utilizar o teste da raz˜ao, mas dessa vez usando o coeficiente da fun¸c˜ao objetivo como numerador; ▶ No caso, temos que escolher entre |2/(−2)| e |4/(−3)|; ▶ O menor valor em m´odulo ser´a o escolhido, no exemplo, x1; 37 / 40 Dualidade Algoritmo Dual Simplex Com as seguintes opera¸c˜oes: L′ 2 = L2/(−2), L′1 = L1 + L′ 2 e L′ 3 = L3 + L2 temos: VB x1 x2 x3 x4 x5 b x4 0 -5/2 1/2 1 -1/2 -1 x1 1 -1/2 3/2 0 -1/2 2 0 4 1 0 1 Q(x) − 4 Agora devemos retirar x4 da base e as candidatas a entrar s˜ao x2 e x5. Pelo teste da raz˜ao escolhemos x2 para entrar na base. 38 / 40 Dualidade Algoritmo Dual Simplex Com as seguintes opera¸c˜oes: L′′ 1 = L′ 1/(−5/2), L′′2 = L′ 2 + (1/2)L′′ 1 e L′′ 3 = L′ 3 − 4L′′ 1 temos: VB x1 x2 x3 x4 x5 b x2 0 1 -1/5 -2/5 1/5 2/5 x1 1 0 7/5 -1/5 -2/5 11/5 0 0 9/5 8/5 1/5 Q(x) − 28/5 Agora temos uma solu¸c˜ao vi´avel no dual e no primal, logo a solu¸c˜ao ´e ´otima. 39 / 40 Dualidade Exerc´ıcio Resolva o modelo a seguir usando o Dual Simplex: Min Q(y) = 100y1 + 360y2 + 400y3 Sujeito a: −y1 − 6y2 − 8y3 ≤ −4 −2y1 − 6y2 − 4y3 ≤ −5 −2y1 − 4y2 − 4y3 ≤ −3 y1, y2, y3 ≥ 0 40 / 40