Programa de Matematica

Método Simplex Dual
Prof. Fernando Augusto Silva Marins
Departamento de Produção
Faculdade de Engenharia – Campus de Guaratinguetá
UNESP
www.feg.unesp.br/~fmarins [e-mail] 1

Introdução
• Algoritmo proposto por C. E. Lemke baseando-se em observações da aplicação do Método Simplex (Primal) tradicional ao Dual de um modelo de Programação Linear.
• Útil em algoritmos de programação inteira, algoritmos de
Programação Não-linear, e Algoritmos Primais-Duais.
• Pode ser útil como alternativa ao Método das Duas Fases ou do “Big
M’ para inicialização do Método Simplex Primal .
• É útil para alguns casos que ocorrem na Análise de Sensibilidade e na Programação Paramétrica.
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá

2

Observações
1. Sabe-se que o vetor formado pelos coeficientes de custo relativo na
-1
aplicação do Simplex Primal, dado por C = C -  A
(onde  = CB B é o vetor dos multiplicadores do Simplex) independe do vetor de constantes das restrições, dado por b.
2. Em geral, para um modelo de Minimização, nem toda Solução Básica que tenha C  0 será viável (isto é, satisfaz as restrições), mas qualquer
Solução Básica Viável com C  0 será uma solução ótima para o modelo sob análise.

Idéia do método:
Iniciar com alguma solução básica, não viável, com C  0 . Procurar efetuar mudanças nas soluções básicas de modo que seja mantido para cada uma delas C  0, e não repetindo soluções já analisadas, pode-se achar uma solução ótima para o modelo num número finito de iterações.
Pesquisa Operacional Aplicada à Produção - UNESP / Campus de Guaratinguetá

3

Definições importantes
Considere os problemas Primal e Dual abaixo:
(Primal) Min Z = CX

sujeito a: {AX = b , X  0}

(Dual)

sujeito a: {YA  C, Y variáveis livres}

Max W = Yb

Seja B a submatriz da matriz de coeficientes tecnológicos do Primal formada pelas colunas dos coeficientes das variáveis básicas nas restrições
(denominadas colunas básicas).
Definição 1:( Base Primal