Método Duas Fases

O Método das Duas Fases

O Método das Duas Fases é um procedimento para zerar as variáveis artificiais. Nesta variante, o problema de PL é resolvido em duas fases distintas: na primeira, procura-se determinar se existem soluções admissíveis para o problema inicial e, caso existam, obtém-se uma SBA que será a solução de partida (inicial), da fase seguinte; a segunda consiste simplesmente na aplicação do algoritmo do Simplex.

FASE I

A 1ª fase consiste em remover da base todas as variáveis artificiais, de forma a obter uma SB apenas com variáveis não artificiais do problema. Para tal, resolve-se o seguinte problema de PL (problema auxiliar), começando com (X, Xa) = (0, b) como SBA :

Minimizar Z’ = ∑ Xa
Sujeito a: A X = b X≥ 0

em que Xa é o vetor das variáveis artificiais e o objetivo consiste, nesta fase, em minimizar a sua soma (função objetivo artificial), quer o problema inicial seja de maximização quer seja de minimização. Portanto, obtida uma solução para o problema auxiliar com as variáveis artificiais nulas, fica determinada a SBA de partida para o problema inicial. É evidente que uma solução nestas condições só se verifica com o valor da FO artificial igual a zero (Z’ = 0). No entanto, outras situações podem acontecer. Portanto, no fim do 1ª fase, em que se atingiu a solução ótima do problema auxiliar, está-se numa das situações seguintes:

i) z’ > 0 existe pelo menos uma variável artificial básica com valor estritamente positivo ⇒ o problema inicial é impossível (região admissível vazia);

ii) z’ = 0

com todas as variáveis artificiais não básicas, a solução em presença é uma SBA de partida para o problema inicial ⇒ passar diretamente à 2ª fase. iii) z’ = 0 com pelo menos uma variável artificial básica (nula) a solução encontrada é uma solução admissível para o problema inicial. Se existir algum vetor não artificial fora da base em condições de substituir um vetor artificial procede-se à substituição, sendo