Baixe o app para aproveitar ainda mais
Prévia do material em texto
O Problema Dual 1 – Introdução Todo problema de PL, a que chamaremos de primal, possui um segundo problema associado chamado dual. Ambos são completamente inter-relacionados, de modo que a solução ótima de um fornece informações completas sobre o outro. 2 – Montagem do dual A montagem de um problema dual parte da forma canônica do primal. Se o primal é de máximo, o dual é de mínimo e vice-versa. Considerando um modelo primal de maximização temos: A função objetivo do dual é de minimização; Os termos constantes das restrições do dual são os coeficientes da função objetivo do primal; Os coeficientes da função objetivo do dual são os termos constantes das restrições do primal; As restrições do dual são do tipo ≥ ao passo que as restrições do primal são do tipo ≤ ; O número de incógnitas do dual é igual ao número de restrições do primal; O número de restrições do dual é igual ao número de incógnitas do primal; e A matriz dos coeficientes do dual é a transposta da matriz dos coeficientes do primal. Seja o primal: Max s.a para i = 1,2,3,...,m para j = 1,2,3,....,n O dual será: Min s.a para j = 1,2,3,....,n para i = 1,2,3,...,m Exemplo 1 Achar o dual do seguinte primal: Max Z = 5x1 + 2x2 s.a x1 ≤ 3 (y1) x2 ≤ 4 (y2) x1 + 2x2 ≤ 9 (y3) x1, x2 ≥ 0 Resp: Min D = 3y1 + 4y2 + 9y3 s.a y1 + y3 ≥ 5 y2 + 2y3 ≥ 2 y1, y2, y3 ≥ 0 Se a restrição k do primal é igualdade então a variável yk do dual é sem restrição de sinal. Se a variável xp do primal é sem restrição de sinal então a restrição p do dual é uma igualdade. Exemplo 2 Achar o dual do seguinte primal: Max Z = 3x1 + 2x2 - x3 + x4 + 5x5 + 4x6 s.a x1 + x2 + x3 = 10 x4 + x5 + x6 = 15 3x1 + 2x2 + x4 + 3x5 ≤ 20 x2 + x3 + 2x4 + x6 ≤ 30 x1 + x4 + 2x6 ≥ 25 x2 + x3 + 2x5 ≥ 18 x1, x2, x3 ≥ 0 ; x4, x5, x6 quaisquer Passando para a forma canônica vem : Max Z = 3x1 + 2x2 - x3 + x4 + 5x5 + 4x6 s.a x1 + x2 + x3 = 10 (y1) x4 + x5 + x6 = 15 (y2) 3x1 + 2x2 + x4 + 3x5 ≤ 20 (y3) x2 + x3 + 2x4 + x6 ≤ 30 (y4) -x1 - x4 - 2x6 ≤ -25 (y5) -x2 - x3 - 2x5 ≤ -18 (y6) x1, x2, x3 ≥ 0 ; x4, x5, x6 quaisquer O dual será: Min D = 10y1 + 15y2 + 20y3 + 30y4 – 25y5 – 18y6 s.a y1 + 3y3 – y5 ≥ 3 y1 + 2y3 + y4 – y6 ≥ 2 y1 + y4 – y6 ≥ -1 y2 + y3 + 2y4 – y5 = 1 y2 + 3y3 – 2y6 = 5 y2 + y4 – 2y5 = 4 y1, y2 quaisquer ; y3, y4, y5, y6 ≥ 0 Reescrevendo na forma standard temos: Min D = 10y1 + 15y2 + 20y3 + 30y4 – 25y5 – 18y6 s.a y1 + 3y3 – y5 ≥ 3 y1 + 2y3 + y4 – y6 ≥ 2 -y1 - y4 + y6 ≤ 1 y2 + y3 + 2y4 – y5 = 1 y2 + 3y3 – 2y6 = 5 y2 + y4 – 2y5 = 4 y1, y2 quaisquer ; y3, y4, y5, y6 ≥ 0 Exemplo 3 Achar o dual do seguinte primal: Min Z = x1 + 5x2 + 2x3 s.a x1 ≤ 4 (y1) x2 + x3 ≤ 9 (y2) 3x1 + 2x2 – 4x3 ≥ 8 (y3) x1 qualquer ; x2, x3 ≥ 0 O dual será: Max D = -4y1 - 9y2 + 8y3 s.a -y1 + 3y3 = 1 -y2 + 2y3 ≤ 5 -y2 – 4y3 ≤ 2 y1, y2, y3 ≥ 0 Interpretação econômica do Dual Recapitulando: Seja o primal Max s.a para i = 1,2,3,...,m para j = 1,2,3,....,n O dual será: Min s.a para j = 1,2,3,....,n para i = 1,2,3,...,m Onde bi ( quantidade do recurso i para as n atividades ( bi ≥ 0); xj ( nível de produção da atividade j. Os xj são as incógnitas (variáveis) do problema; cj ( lucro unitário do produto j; aij ( quantidade do recurso i consumida na produção de uma unidade do produto j. Conclui-se então que yi será o valor unitário do recurso i. Apesar da variável yi representar o valor unitário do recurso i, nada nos garante que este valor coincida com o seu valor de mercado, é um valor implícito do recurso i que só é válido para o problema em questão. O valor ótimo de yi representa a taxa na qual o Z ótimo aumenta ou diminui de valor se a quantidade disponível do recurso i aumentar ou diminuir dentro de certos limites. Esse limite é determinado pelo intervalo de bi dentro do qual a base da solução ótima não se altera. O valor ótimo de yi recebe várias denominações tais como : valor implícito; preço de sombra; incremental value; intrinsic value; shadow price; internal price; efficiency price; etc. Exemplo Seja o primal Min Z = 10x1 + 11x2 s.a 10x1 + 20x2 ≥ 50 50x1 + 10x2 ≥ 100 x1; x2 ≥ 0 Cujo dual é: Max D = 50y1 + 100y2 s.a 10y1 + 50y2 ≤ 10 20y1 + 10y2 ≤ 11 y1; y2 ≥ 0 A resolução fica a cargo dos alunos. Resolvendo temos Z = 35 , x1 = 5/3 , x2 = 5/3 D = 35 , y1 = 1/2 , y2 = 1/10 Se eu mudar a primeira restrição do primal para 51 vem: Z’ = 71/2 , x1 = 149/90 , x2 = 155/90 Z’ – Z = 71/2 – 35 = 1/2 = y1 Voltando ao problema original, se eu mudar a segunda restrição para 101: Z’ = 3159/90 , x1 = 152/90 , x2 = 149/90 Z’ – Z = 3159/90 – 35 = 1/10 = y2 Teorema da Folga Complementar: Obtida pelo método simplex a solução ótima do primal, então: O valor ótimo da variável yi do dual é igual ao coeficiente na linha do Z ótima, da variável de folga xn+i do primal; e O valor ótimo da variável de folga ym+j do dual é igual ao coeficiente na linha do Z ótima, da variável xj do primal . Colocando-se a variável de folga xn+i na restrição i do primal temos e ym+j+ na restrição j do dual ym+1 ym+2 --------- ym+n y1 y2 --------- ym Z x1 x2 --------- xn xn+1 xn+2 --------- xn+m b base 1 c1 c2 --------- cn 0 0 --------- 0 0 xn+1 0 a11 a12 --------- a1n 1 0 --------- 0 b1 xn+2 0 a21 a22 --------- a2n 0 1 --------- 0 b2 ---- -- --------------------------- -------------------------- --- xn+m 0 am1 am2 --------- amn 0 0 --------- 1 bm Corolário do teorema da folga complementar O corolário do teorema da folga complementar pode ser expresso do seguinte modo: Na solução ótima temos: yi = 0 quando xn+i > 0 ou seja, se na solução ótima do primal a variável de folga xn+i for básica, então a variável yi do dual é não básica. Economicamente significa nem que todo recurso i está sendo consumido pelas n atividades, havendo portanto, sobra daquele recurso, e seu valor implícito é 0; yi > 0 quando xn+i = 0 ou seja, se na solução ótima do primal a variável de folga xn+i for não básica, então a variável yi do dual é básica. Economicamente significa que todo recurso i está sendo consumidopelas n atividades, não havendo portanto, sobra daquele recurso, e seu valor implícito é > 0; xj = 0 quando ym+j > 0 ou seja, se na solução ótima do primal a variável xj for não básica, então a variável de folga do dual ym+j é básica. Economicamente significa que esta atividade não será realizada xj = 0 ; e xj > 0 quando ym+j = 0 ou seja, se na solução ótima do primal a variável xj for básica, então a variável de folga do dual ym+j é não básica. Economicamente significa que esta atividade será realizada xj > 0. Aproveitando o primeiro exemplo de dual: Max Z = 5x1 + 2x2 s.a x1 ≤ 3 x2 ≤ 4 x1 + 2x2 ≤ 9 x1, x2 ≥ 0 Min D = 3y1 + 4y2 + 9y3 s.a y1 + y3 ≥ 5 y2 + 2y3 ≥ 2 y1, y2, y3 ≥ 0 Cuja solução ótima do primal é: y4 y5 y1 y2 y3 Z x1 x2 x3 x4 x5 b base 1 0 0 4 0 1 21 x1 0 1 0 1 0 0 3 x4 0 0 0 1/2 1 -1/2 1 x2 0 0 1 - 1/2 0 1/2 3 Temos : Primal Z = 21, x1 = 3 básica, x2 = 3 básica, x3 = 0 não básica, x4 = 1 básica, x5 = 0 não básica Dual D = 21, y1 = 4 básica, y2 = 0 não básica, y3 = 1 básica, y4 = 0 não básica, y5 = 0 não básica. Verifica-se que o valor intrínseco do recurso 1 é 4, do recurso 2 e 0 e do recurso 3 é 1. Portanto está sobrando recurso 2 pois x4 = 1 e o seu valor intrínseco é 0. Como exercício os alunos deverão diminuir o recurso 1 de uma unidade e verificar a alteração do Z, em seguida no problema original, aumentar o recurso 3 de uma unidade e verificar a alteração de Z. Exercício Foi apresentado um problema de PL, a um administrador, composto de: Função objetivo com três variáveis; Restrições compostas de quatro inequações, sendo a primeira referente à hora de máquinas, a segunda referente à matéria prima no 1, a terceira à matéria prima no 2 e a quarta à mão de obra; e As variáveis da função objetivo ≥ 0. Ao resolver o problema, o administrador chegou ao seguinte quadro para a solução ótima: Z x1 x2 x3 x4 x5 x6 x7 b base 1 0 0 0 2 3 1/3 0 235 x2 0 0 1 0 1 3 1 0 80 x7 0 0 0 0 2/3 1/2 2 1 2 x1 0 1 0 0 -2 -5 3/4 0 28 x3 0 0 0 1 3 -1 1/4 0 35 Pede-se: As variáveis da função objetivo do Dual; As variáveis de folga do Dual; As variáveis básicas do Dual e seus valores; As variáveis não básicas do Dual e seus valores; O valor ótimo de D; Caso a empresa precisasse reduzir custos, qual dos recursos deveria ser reduzido e em quantas unidades, de modo a não alterar o lucro máximo? _1172386734.unknown _1172386838.unknown _1173852565.unknown _1174114047.unknown _1174114229.unknown _1173852428.unknown _1172386760.unknown _1172385918.unknown _1172386465.unknown _1172384969.unknown
Compartilhar