Dualidade

Uma dos conceitos mais importantes em programação linear é o de dualidade. Qualquer
problema de PL tem associado um outro problema de PL, chamado o Dual. Neste contexto, o
problema original denomina-se por Primal.
Um dos principais papéis da teoria da dualidade é a interpretação e implementação da análise
de sensibilidade, que é uma parte muito importante de um estudo de PL.

Exemplo:

Considere o problema clássico da dieta: (problema primal): Quer-se consumir quantidades de determinados alimentos de tal forma a satisfazer as necessidades mínimas de nutrientes exigidas a um custo mínimo dispendido, problema este ilustrado pelo quadro seguinte.

                                   alimentos                                      necessidades mín. de
                                                                                      nutrientes
a1 a2 a3 a4 a5
proteínas (g)                  3   4   5   3  6                                    42 (4.1)
sais minerais (g)              2   3   4  3   3                                    24
custo (R$)                      25 35 50 33 36

Considerando-se:
aij : percentual do componente i presente no alimento j;
xj : quantidade do componente j presente na dieta a ser feita;
cj : preço por grama de cada ingrediente;
bi : quantidade mínima de cada ingrediente a ser consumida na dieta.
aj: coluna j da matriz do sistema;

Então, o Modelo Primal pode ser sistematizado da seguinte forma:
minimizar            25 x1 + 35 x2 + 50 x3 + 33 x4 + 36 x5
                             3 x1 + 4 x2 + 5 x3 + 3 x4 + 6 x5 ≥ 42
sujeito a :             2 x1 + 3 x2 + 4 x3 + 3 x4 + 3 x5 ≥ 24
                             
                               x1 ; x2 ; x3 ; x4 ; x5 ≥ 0

Formulação do modelo dual

Suponha que um vendedor de pílulas e sais minerais propõe substituir a
dieta de alimentos expressa de acordo com o quadro (4.1), por uma dieta de
pílulas, com as seguintes condições:
1- a pílula de uma unidade (g) de proteína custará w1 ;
2- “ “ “ “ “ “ “ sais minerais “ w2 ;
3- os preços w1 e w2 serão fixados arbitrariamente;
4- o vendedor garante que as pílulas terão preços iguais ou mais baratos que
qualquer alimento;
5- o vendedor pretende , é claro, maximizar sua renda de modo a satisfazer a
necessidade da dieta;

Para o problema posto, tem-se o modelo visto a seguir:

maximizar           42 w1 + 24 w2

    3 w1 + 2 w2 ≤ 25
                    4 w1 + 3 w2 ≤ 35
sujeito a:     5 w1 + 4 w2 ≤ 50 (4.2)
                    3 w1 + 3 w2 ≤ 33
                    6 w1 + 3 w2 ≤ 36

                        w1 ; w2 ≥ 0

A cada modelo de Programação Linear, contendo coeficientes aij, bi e cj,
corresponde um outro modelo, formado por esses mesmos coeficientes, porém
dispostos de maneira diferente. Ao modelo original, visto em 4.1, dá-se o nome de
“ Modelo Primal”, enquanto qua ao outro modelo visto em (4.2),denomina-se de
“Modelo Dual”. Sobre estes dois modelos estão relacionadas propriedades que
estabelecem que:

a) se a função objetivo do primal é de minimização, então a função objetivo do
dual é de maximização;
b) os termos independentes das restrições do dual são coeficientes da função
objetivo do primal;
c) os coeficientes da função objetivo do dual são os termos independentes das
restrições do primal;
e) o número de variáveis do dual é igual ao número de restrições do primal;
f) o número de restrições do dual é igual ao número de variáveis do primal;
g) a matriz dos coeficientes do dual é a transposta da matriz dos coeficientes do
primal;