Método Simplex Revisado

1 - MÉTODO SIMPLEX REVISADO

O método simplex original é um procedimento algébrico direto. Entretanto, esta forma de resolução de problemas de programação linear executa um algoritmo que não é o procedimento computacional mais eficiente, pois calcula e armazena muitos números que não são necessários à iteração corrente, podendo estes, não se tornarem relevantes para a tomada de decisão e para iterações subseqüentes. As únicas peças de informação importantes a cada iteração são os coeficientes das variáveis não-básicas, os coeficientes das variáveis básicas e o lado direito das equações.

Essas considerações motivaram o desenvolvimento do método simplex revisado. Este método foi projetado para executar exatamente as mesmas coisas que o método simplex original, porém, de uma maneira mais eficiente, tornando-se uma versão simplificada do simplex original. Ele calcula e armazena apenas as informações que são necessárias no momento e guarda os dados essenciais numa forma mais compacta.

Dentro da apresentação deste método, três assuntos terão que ser endereçados:

1) O tempo requerido para a transformação de um tableau.
2) O espaço de armazenagem requerido.
3) A precisão numérica e o controle dos erros de arredondamento.

O método simplex revisado utiliza, explicitamente, manipulações de matrizes. Portanto, é necessário descrever o problema na notação matricial. O modelo geral para problema de programação linear torna-se então:

P: max z = cx,
s.t. Ax = b x  0

onde x é um vetor composto por todas as variáveis de decisão, artificiais, de excesso e de folga

x = ,

c é o vetor composto pelos coeficientes da função objetivo

c = ,

A é uma matriz

A =

e b é um vetor das constantes do lado direito

b = .

Durante qualquer estágio do cálculo simplex, m variáveis estão na base. Seja xB o vetor das variáveis básicas, de modo que o i-ésimo componente de xB é a variável que está na base na