dual-simplex

Definição

O método Dual-Simplex lida diretamente com soluções básicas incompatíveis porém “melhor que a ótima”, e procura achar a compatibilidade do problema. Ele lida com um problema exatamente como se o método simplex estivesse sendo, simultaneamente, aplicado ao seu problema dual. O método dual-simplex trabalha com o mesmo quadro de problema primal e aplica os mesmos método do simplex clássico.

As regras de transformação que se aplicaram, foram as seguintes

1) A cada variável do primal corresponde uma restrição no dual;
2) A cada restrição do primal corresponde uma variável do dual;
3) Os coeficientes da função objetiva do primal correspondem aos termos independentes das restrições do dual;
4) Os termos independentes das restrições do primal correspondem aos coeficientes da função objetiva do dual;
5) A transposta da matriz das restrições do primal, é a matriz das restrições do dual;
6) Se o primal for um problema de maximização (minimização) na forma típica, então o problema dual será um problema de minimização (maximização) na forma típica.
Relações Primal−Dual.

Comparando os modelos primal e dual, verificamos que:
- As restrições do dual são do tipo , ao passo que as do primal são do tipo ;
- O número de incógnitas do dual (m valores de yi) é igual ao número de restrições do primal;
- O número de restrições do dual é igual ao numero de incógnitas do primal (n valores de xj);
- A matriz dos coeficientes do dual é a transposta da matriz dos coeficientes do primal;
- A função objetivo do dual é de minimização, ao passo que a do primal é de maximização;
- Os termos constantes das restrições do dual são os coeficientes da função objetivo do primal; e
- Os coeficientes da função objetivo do dual são os termos constantes das restrições do primal.

Para exemplificar o método Dual-Simplex, vamos utilizar o mesmo exemplo:

X1 + 2 X 2  3