Pergunta: O método Simplex é polinomial?

Passo 1

O enunciado pergunta se o método Simplex para Programação Linear é um algoritmo polinomial. O conteúdo aqui é Complexidade de Algoritmos e vamos precisar da definição de algoritmo polinomial em termos de tempo de execução no pior caso.

Passo 2

Um algoritmo é dito polinomial se o seu tempo de execução T(n) sobre instâncias de tamanho n satisfaz
T(n) = Ol(n^kr)
para algum inteiro k. Em outras palavras, cresce no máximo como uma potência de n.

Passo 3

No caso do Simplex, embora ele seja muito eficiente na prática, existe a construção clássica de Klee e Minty que mostra que, para certas instâncias especialmente construídas, o Simplex pode visitar todas as vértices da região viável. Isso leva a um tempo de execução que cresce exponencialmente, algo como
T(n) = Ol(2^nr)
no pior caso. Logo, não atende à definição de algoritmo polinomial.

Passo 4

Vale observar que existem outros algoritmos de Programação Linear com complexidade provadamente polinomial, como o método do ponto interior de Karmarkar e o método do elipsoide de Khachiyan. Mas o Simplex clássico, com regras de pivoteamento usuais, não é polinomial no pior caso.

Resposta

Não. O método Simplex clássico tem complexidade exponencial no pior caso e, portanto, não é um algoritmo polinomial.

Exercícios relacionados