Teoria da Dualidade

Objectivo Geral: Analisar a teoria da dualidade, destacando a sua aplicação na resoluçao de problemas de programação linear.

Fundamentação Teórica

"A cada modelo de programação linear, contendo coeficiente a_ij , b_i e c_j corresponde um outro modelo, denominado Dual, formado por esses mesmos coeficientes, porém dispostos de maneira diferente." (PUCCINI, 1942)

O problema primal e dual estão estreitamente ligados e matem entre si uma relação muito forte conforme se pode observar na tabela que se segue:

Problema  Primal	Mudança	Problema Dual
Coeficientes da função objectivo	Passam para	Termos independentes das restrições
Termos independentes das restrições	Passam para	Coeficientes da função objectivo
Matriz dos coeficientes das restrições	Passam para	Transposta dos coeficientes da função objectivo
Variavel de folga ou excesso	Passam para	Variavel essencial
Variavel essencial	Passam para	Variavel de folga ou excesso

Propriedades

1. As restrições do dual mudam de sentido com respecto ao primal,

2. Se o primal é um problema de maximo, o dual será de minimo, vice versa,

3. Em cada problema primal as restrições ter o mesmo sentido: ≥ se o problema é de mínimo e £ se é de máximo.

4. Os valores óptimos de ambas funções objectivos coincidem,

5. O dual do dual é o primal.

Na forma padrão um modelo de P.L é escrito da seguinte forma:

Max     Z =     c₁ x₁ + c₂ x₂ + .................+ c_n x_m

                        s. a                  a₁₁x₁ +  a₁₂x₂ + ........  + a_1nx_m  £ b₁             

            a₂₁x₁ +  a₂₂x₂ + ........  + a_2nx_m  £ b₂             

   .             .         .                        .         .

   .             .         .                        .         . 

           a_m1x₁ +  a_m2x₂ + ........  + a_mnx_m  £ b_m

                                                 x_{j ³} 0 ( j = 1,....., n )

Se for associado a cada restrição uma variável y_i, o problema dual pode ser escrito como:

Min      D =    b₁ y₁ + b₂ y₂ + ...............+ b_m y_m

                        s. a       (y₁)     a₁₁y₁ +  a₂₁y₂ + ........  + a_m1y_m  ³ c₁             

 (y₂)     a₁₂y₁ +  a₂₂y₂ + ........  + a_m2y_m  ³ c₂             

   .             .         .                        .         .

   .             .         .                        .         . 

 (y_m)   a_1ny₁ +  a_2ny₂ + ........  + a_mny_m  ³ c_n

               y_{i ³} 0 ( i = 1,....., n

Exemplo: 1) PRIMAL  Max            L = 4 x₁ + x₂

                        s. a     9x₁ +  x₂  £ 18                       

                       3x₁ + x₂  £  12    

                                                                        x₁ e x₂  ³ 0

                                                                      

                    DUAL       Min    D = 18y₁ + 12y₂

                           s. a:  9y₁ +  3y₂  ³ 4           

                          y₁ + y₂  ³  1  

                                                                         y₁  e y₂ ³ 0

Exemplo: 2)  PRIMAL      Max       P = 5 x₁ + 2x₂           

              s. a      x₁                     £ 3                   

                       x₂       £  4   

                                                            x₁ + 2x₂       £  9        

   DUAL            Min    D = 3y₁ + 4y₂  + 9y₃  

                s. a y₁   +  y₃  ³ 5                          

                       y₂ + 2y₃   ³ 2  

Conclusão

Com a dualidade surgem vários novos conceitos e construtos na programação linear. Resolver o Primal através do Método Simplex faz com que o dual seja resolvido automaticamente.

BIBLIOGRAFIA

1. Goldbarg, M.C. Luna, H.P.L. (2005) Otimização Combinatória e Programação Linear. Modelos e Algoritmos. 2ª Edição. Editora Campus.

2.  Hillier F. S., Lieberman G. J. (2010) Introdução à Pesquisa Operacional. 8ª Edição. Editoras Mc Graw Hill e bookman.

3. Taha, Hamdy A. (2008) Pesquisa Operacional: Uma Visão Geral. 8ª Edição. São Paulo. Pearson Prentice Hall.