O que é o Dualidade?

​

O PROBLEMA DUAL
 
Uma das mais importantes descobertas no início do desenvolvimento da Programação Linear foi o conceito de dualidade e suas muitas ramificações importantes. Esta descoberta revelou que todo o problema de Programação Linear tem associado a ele outro problema de Programação Linear chamado dual. As relações entre o problema dual e o problema original (chamado de primal) provam ser úteis de diversas maneiras. O problema dual é um modelo associado ao original, que traz a interpretabilidade econômica para os valores de recursos e para os coeficientes da função objetivo. Esta interpretabilidade serve para amenizar essas dúvidas impostas pela hipótese de certeza do problema de programação linear.

​

​

COMPARAÇÃO DA FORMA DOS PROBLEMAS PRIMAL E DUAL

A cada modelo de Programação Linear, corresponde um outro modelo, denominado dual, formado por esses mesmos coeficientes, porém dispostos de maneira diferente, utilizando-se o conceito de matriz transposta.
Seja o problema primal assim definido:

a 11 x 1 + a 12 x 2 + .......... + a 1n x n   <=   b 1    (y 1)
a 21 x 1 + a22 x 2 + .......... + a n2 x n  <=  b 2    (y 2)
................................................................................
a m1 x 1  + a m2 x 2 + ......... + a mn x n  <=  b m    (y m)
 
Z Max = c 1 x 1  +  c 2 x 2    + ......... + c n x n

 

 

Associando-se a cada restrição i do primal uma variável y 1, conforme o indicado acima, o problema dual é assim definido:
  
a 11 y 1    + a2 1  y 2 + .......... +  am 1 y  m    <=   c 1    
a 12 y 1  + a 2  2y 2 + .......... + a m 2 y  m    <=  c 2    
................................................................................
a 1n y 1  + a2n  y 2 + .........  + a mn x m      <= c n    
 
Z Mín =  b 1 y 1  +  b 2 y 2    + ......... + bn  x m

 

 

Para ilustrar a teoria, vejamos agora um exemplo numérico:
-         Modelo matemático primal:
        2 X1     +     X2         16     
            X1     +   2X2         11      
            X1     +   3X2         15     
 
  ZMáx.  = 300 X1 + 500 X2 
 
-         O modelo matemático dual associado ao modelo matemático primal:
  2 Y 1 +  Y 2  +   Y 3   <= 300
     Y 1 + 2Y 2 + 3Y 3 <= 500

​

 Z Min = 16 Y 1 + 11Y 2 + 15 Y 3

 

Comparando os modelos primal e dual, verificamos que:

-         As restrições do dual são do tipo >=, ao passo que as do primal são do tipo <=;
-         O número de incógnitas do dual (m valores de yi) é igual ao número de restrições do primal;
-         O número de restrições do dual é igual ao numero de incógnitas do primal (n valores de xj);
-         A matriz dos coeficientes do dual é a transposta da matriz dos coeficientes do primal;
-         A função objetivo do dual é de minimização, ao passo que a do primal é de maximização;
-         Os termos constantes das restrições do dual são os coeficientes da função objetivo do primal; e
-         Os coeficientes da função objetivo do dual são os termos constantes das restrições do primal.
 

​

​

Exemplo de Resolução Gráfica

​

Para facilitar o entendimento, vamos utilizar um exemplo de modelo matemático primal com duas variáveis (X1 e X2), com apenas duas inequações: 

- Primal                                                                 - Dual
        X1  +  2 X 2  <=  3   (3; 1,5)            Y1  +    Y 2   >=  5    (5; 5)    
        X1  +     X 2  <=  2   (2;  2)              2 Y1  +   Y 2   >=  7    (3,5; 7)

  
Z: máx = 5 X 1 + 7 X 2                           Z: mín = 3 Y 1 + 2 Y 2 

​

​

​
 

Método Dual Simplex

​

O método Dual-Simplex lida diretamente com soluções básicas incompatíveis, porém “melhores que a ótima”, e procura achar a compatibilidade do problema. Ele lida com o problema exatamente como se o método simplex estivesse sendo, simultaneamente aplicado ao seu problema dual.
 

O método Dual-Simplex é bastante empregado em análise de sensibilidade, quando são feitas pequenas modificações no modelo. Além disso, algumas vezes é mais fácil começar com uma solução básica incompatível, porém “melhor que a ótima” e procurar a compatibilidade, do que obter uma solução compatível básica inicial e depois otimizá-la, como se faz no método simplex.

​

Para exemplificar o método Dual-Simplex, vamos utilizar o mesmo exemplo:
    X1  +  2 X 2  <=  3   
    X1  +    X 2  <=   2   
Z: máx o lucro= 5 X 1 + 7 X 2

Colocando as variáveis de folga nas inequações do modelo matemático primal e multiplicando a função objetivo por (-1):
 

X1  +  2 X 2  + X3    =  3   
X1  +    X 2   +   X4  =  2   
Z: máx o lucro = -5 X 1 - 7 X 2

 

Construindo o primeiro quadro do simplex:

​

BASE    X1        X2    X3      X4    b
__________________________________
  X3        1          2       1       0       3
  X4        1          1       0       1       2
_________________________________
  -Z        -5        -7      0     0      0

​

 

Aplicando as regras do simplex, chegamos ao 2º quadro do simplex:
BASE    X1        X2    X3     X4    b
__________________________________
  X2         ½         1    ½      0    3/2
  X4         ½         0    -1/2    1    1/2
_________________________________
  -Z         -3/2       0    7/2    0    21/2

​

​

Aplicando as regras do simplex, chegamos ao 3º quadro do simplex:
BASE    X1       X2    X3       X4    b
__________________________________
  X2        0        1       1       -1/2    1
  X1        1        0       -         2       1
_________________________________
  -Z                  0       0    2        3    12

​

​

Colocando as variáveis de folga nas inequações do modelo matemático dual e multiplicando a função objetivo por (-1):
Y1  +    Y 2  - Y3   =  5  
2 Y1  +    Y 2    - Y4  =  7     

- Zmín o custo = -3 Y 1 - 2 Y 2 

 

Para identificarmos a solução do dual, basta colocar no último quadro do simplex primal, onde temos as variáveis originais do modelo primal, as variáveis de folga do dual e onde ficam as variáveis de folga do primal, as variáveis originais do dual.

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​