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
sobre instâncias de tamanho
satisfaz
para algum inteiro
. Em outras palavras, cresce no máximo como uma potência de
.
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
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.