SIMPLEX DUAL
Bases complementares
Simplex dual
• O DLC tem matriz [At –In] cuja inversa de base é de dimensão nxn
• Mas conhecendo uma base primal B=(j1,j2,...jm) e reordenando as
linhas de forma a j1 ser a primeira,j2 ser a segunda,..e a mésima linha
ser jm a matriz do DLC fica:
[ATB : -Im : 0 ]
[ ÃT : 0 :-In-m ]
Onde as primeira m colunas de AT (linhas de A) estão associadas a u e
as colunas de
-identidade estão associadas às residuais no dual
Bases complementares
• Vem de folgas complementares que para o par
PLC-DLC são :
xj .urj =0
o que em termos de bases complementares
será:
xj está na base primal↔urjnão está na base dual
Bases complementares
• Base primal
B=(j1,j2,...jm)
• Base dual complementar
B=(u1,...um, // urj(m+1) , urj(m+2),..........., urjn)
O que se ganha com isto????????????
Cálculos do simplex no dual
mais baratos que fazer simplex no dual
• Teste de otimalidade
• Quem entra na base e qual seu impacto
• Quem sai da base e seu impacto
• Nova base
Cálculos do simplex no dual
mais baratos que fazer simplex no dual
• Teste de otimalidade b’ não negativo
• Quem entra na base e qual seu impacto
• Quem sai da base e seu impacto
• Nova base
Cálculos do simplex no dual
mais baratos que fazer simplex no dual
• Teste de otimalidade b’ não negativo
• Quem entra na base e qual seu impacto
Se b’i<0 (associado a xji),
entra na base urj complementar a xji
(qual impacto na complementariedade?)
• Quem sai da base e seu impacto
• Nova base
Cálculos do simplex no dual
mais baratos que fazer simplex no dual
• Teste de otimalidade b’ não negativo
• Quem entra na base e qual seu impacto
Se b’i<0 (associado a xji),
entra na base urj complementar a xji
(qual impacto na complementariedade?)
• Quem sai da base e seu impacto
Qual o vetor equivalente ao π do simplex?
Qual o pivot???
• Nova base
Cálculos do simplex no dual
mais baratos que fazer simplex no dual
• Teste de otimalidade b’ não negativo
• Quem entra na base e qual seu impacto
Se b’i<0 (associado a xji),
entra na base urj complementar a xji
(qual impacto na complementariedade?)
• Quem sai da base e seu impacto
Qual o vetor equivalente ao π do simplex?
Qual o pivot???
• Nova base COMEÇAR DE NOVO
Espaço de memória e pivotações
• Espaço de memória
tableau primal.
Espaço de memória e pivotações
• Espaço de memória
tableau primal.
Pivot negativo
Fazer b’i<0 definir linha do pivot
Pivotar mantendo viabilidade DUAL verificada
pelo sinal de
Γ= c-ATu