Os problemas primal e dual estão intrinsecamente ligados na teoria da dualidade em programação linear. Eles representam duas formulações diferentes de um mesmo problema de otimização linear, sendo inter-relacionados de maneira específica.
Problema Primal
O problema primal é a formulação original do problema de otimização linear. Geralmente, é expresso na forma padrão:
\[\text{Maximize } \quad c^Tx\] \[\text{sujeito a } \quad Ax \leq b\] \[x \geq 0\]
onde:
- $c$ é um vetor de coeficientes da função objetivo,
- $x$ é o vetor de variáveis de decisão,
- $A$ é uma matriz de coeficientes das restrições,
- $b$ é o vetor de limites das restrições.
A meta é maximizar ou minimizar a função objetivo $c^Tx$ sujeita a um conjunto de restrições lineares.
Problema Dual
O problema dual é uma formulação alternativa derivada do problema primal usando a teoria de dualidade. Introduz-se multiplicadores de Lagrange para as restrições do problema primal, gerando assim o problema dual. A formulação geral do problema dual é:
\[\text{Minimize } \quad b^Ty\] \[\text{sujeito a } \quad A^Ty \geq c\] \[y \geq 0\]
onde:
- $y$ é o vetor de multiplicadores de Lagrange (ou variáveis duais),
- $b$ é o vetor de termos constantes das restrições do primal,
- $A^T$ é a matriz transposta de $A$,
- $c$ é o vetor de coeficientes da função objetivo do primal.
O objetivo do problema dual é encontrar os multiplicadores de Lagrange que minimizam $b^Ty$ sujeito às restrições lineares.
Relação de Dualidade
A relação fundamental entre os problemas primal e dual é expressa pelo Teorema da Dualidade, que estabelece que o valor ótimo do problema primal é sempre maior ou igual ao valor ótimo do problema dual, e vice-versa. Matematicamente, isso é expresso como:
\[\text{Para todo } x \text{ factível no primal e para todo } y \text{ factível no dual, temos } c^Tx \geq b^Ty\]
Se ambos os problemas alcançam seus valores ótimos, então há igualdade entre eles. Esta relação é conhecida como dualidade forte.
A dualidade não apenas fornece uma maneira de verificar a solução ótima, mas também oferece informações valiosas sobre a sensibilidade do problema às mudanças nos parâmetros e fornece soluções alternativas.