Solução do problema dual
O problema dual altera transforma os problemas tornando:
- os coeficientes da função principal em valores das restrições e vice-versa
- e rodando os coeficientes das restrições em termos das coeficientes em vez de ser de termos das restrições
A solução do problema dual é igual à solução do problema primal.
Como o problema é duplo nos termos das restrições e as probabilidades de serem emitidas, elas podem ser consideradas como parte da restrição de variação.
Exercício resolvido — Conversão primal → dual
Considera o seguinte problema primal de minimização:
Min Z = 6x₁ + 4x₂ + 8x₃
s.a. 3x₁ + x₂ + 2x₃ ≥ 9
x₁ + 2x₂ + x₃ ≥ 6
x₁, x₂, x₃ ≥ 0
Regras de conversão
| Primal (Min) | Dual (Max) |
|---|---|
| Função Min | Função Max |
| Coeficientes objectivo (6, 4, 8) | Termos independentes do dual |
| Termos independentes (9, 6) | Coeficientes objectivo do dual |
| Restrição ≥ | Variável dual ≥ 0 |
| 2 restrições | 2 variáveis duais (y₁, y₂) |
| 3 variáveis | 3 restrições duais |
Problema dual
Max W = 9y₁ + 6y₂
s.a. 3y₁ + y₂ ≤ 6 (coluna x₁ do primal)
y₁ + 2y₂ ≤ 4 (coluna x₂ do primal)
2y₁ + y₂ ≤ 8 (coluna x₃ do primal)
y₁, y₂ ≥ 0
Verificação da simetria
| Primal | Dual |
|---|---|
| Min Z = 6x₁ + 4x₂ + 8x₃ | Max W = 9y₁ + 6y₂ |
| 2 restrições | 2 variáveis duais |
| 3 variáveis | 3 restrições |
| Restrições ≥ | Variáveis ≥ 0 |
| Variáveis ≥ 0 | Restrições ≤ |
Pelo teorema da dualidade forte, na óptimo do primal e do dual os valores são iguais: Z* = W*.