Dualidade

A dualidade é um conceito fundamental em programação linear que oferece uma relação simbiótica entre um problema de otimização original (chamado problema primal) e um problema derivado (chamado problema dual). Este relacionamento permite que insights e soluções sejam transferidos de um problema para o outro.

O problema primal em Programação Linear pode ser formulado da seguinte maneira:

onde , , e.

Dual através do Lagrangeano

Para construir o problema dual através da teoria do Lagrangeano, introduzimos multiplicadores Lagrangeanos para as restrições .

O Lagrangeano é então dado por:

Problema Dual de Lagrange

O problema dual associado envolve a maximização do limite inferior do problema primal, dado por:

Para resolver isso, precisamos encontrar o infimo de para cada. No caso da programação linear, isso é feito resolvendo:

Se , então o infimo é alcançado quando se tal existir, ou caso contrário. Portanto, o problema dual se torna:

Relações entre Primal e Dual

1. Dual Unbounded: Se o problema dual é ilimitado, então isso implica que o problema primal é inviável.

2. Dual Optimal: Se o problema dual tem uma solução ótima, então o problema primal também tem, e seus valores objetivos são iguais. Isso é conhecido como "dualidade forte".

Variáveis Básicas e Não Básicas

Na programação linear, especialmente na forma padrão, uma base é um conjunto de colunas linearmente independentes de . As variáveis correspondentes a essas colunas são chamadas de variáveis básicas. O restante das variáveis são chamadas de variáveis não básicas e são geralmente definidas como zero para encontrar uma solução básica viável.

Custos Reduzidos

O custo reduzido de uma variável não básica em um simplex é dado por:

onde é o coeficiente de custo da variáveleé o vetor de preços sombra.fornece informações sobre o quanto a função objetivo irá melhorar se for aumentada a partir de zero.

Dualidade Fraca

A dualidade fraca, em termos de variáveis básicas e custos reduzidos, pode ser vista como uma afirmação de que se é uma solução viável do dual, então (onde são os custos das variáveis básicas e é a matriz básica), e para todas as variáveis não básicas .

Dualidade Forte

Se e são soluções ótimas para o dual e o primal, respectivamente, e ambos os problemas têm uma solução finita, então:

Isso implica que os custos reduzidos para todas as variáveis não básicas devem ser exatamente zero, e deve satisfazer .

Complementaridade Slack

Na solução ótima, as condições de complementaridade slack são satisfeitas:

Aqui é a folga na restrição -ésima do primal, e é o multiplicador de Lagrange dual associado a essa restrição. Isso significa que se uma variável não básica é positiva na solução ótima, então o custo reduzido correspondente deve ser zero.

Essas são maneiras mais rigorosas de ver a dualidade e a complementaridade slack em termos de programação linear, levando em consideração as variáveis básicas e os custos reduzidos.