Dualidade

Algoritmo Dual do Simplex / Algoritmo Primal do Simplex

Primal: SBAP ------>.....----->SBAP------>SBAP X*
Dual:  SBNAP ------>.....----->SBNAD------>SBAN U*

SBAP: Solução Básica admissível no problema primal
SBNAP: Solução Básica Não admissível no problema primal

SBAD: Solução Básica admissível no dual
SBNAD: Solução Básica Não admissível no dual

Como (cj-zj) >0 o critério do óptimo ainda não está satisfeito, logo continua-se a aplicar o algoritmo do simplex bj =>0, condição de admissibilidade no primal
(cj-zj) =< a condição de admissibilidade no dual

Algoritmo dual do Simplex


Passo 1: Construir o quadro do simplex correspondente a uma solução básica admissível no dual (com uma matriz identidade)

Passo 2: Se bj=>0, o algoritmo termina, estamos na presença de uma solução óptima finita para o problema dual consequentemente para o primal. O processo continua se existir algum bj <0

Passo 3: Escolher o vector a sair da base de acordo com o critério min bj<0 (escolher a linda do elemento redutor

Passo 4: Escolher o vector a entrar na base
cj-zj / aij, aij<0
Se todos os aij=>0, o processo termina.
Esta-se perante uma solução não limitada para o problema dual e consequentemente o problema primal não possui Soluções Admissíveis
O processo continua no caso de existir algum aij < 0

Passo 5: Actualizar o quadro do simplex usando operações do Gauss- Jordan