Um pouco de história

Pergunta: O método Simplex é polinomial?
Resposta: NÃO! Embora o método Simplex seja extremamente eficiente na prática, sua complexidade no pior caso é exponencial. Isso ocorre porque o número de soluções básicas possíveis pode chegar a binomnm, onde m é o número de restrições e n o número de variáveis.
  • Um exemplo clássico foi apresentado por Klee e Minty (1972): Eles construíram um politopo em alta dimensão no qual o Simplex, com a regra de pivoteamento de Dantzig, precisa visitar todos os vértices do politopo, resultando em um número exponencial de passos.

Passo 1

O enunciado pergunta se o método Simplex é um algoritmo de tempo polinomial no pior caso. O conteúdo envolvido é análise de complexidade de algoritmos de programação linear. Para responder precisamos conhecer como o Simplex explora as soluções básicas (vértices do politopo) e quantas dessas soluções existem em função do número de variáveis n e de restrições m.

Passo 2

Cada solução básica corresponde a escolher um conjunto de m variáveis básicas dentre as n variáveis totais. Assim, o número máximo de vértices que o Simplex poderia visitar é dado por
binomnm,
que cresce exponencialmente quando n e m aumentam proporcionalmente. Logo, basta esse crescimento explosivo para mostrar que o Simplex não tem garantia de tempo polinomial no pior caso.

Passo 3

O exemplo clássico de Klee e Minty (1972) constrói um politopo “esticado” em alta dimensão de modo que o Simplex, usando a regra de Dantzig, percorre todos os vértices antes de chegar à solução ótima. Esse número de passos é da ordem de binomnm, exponencial em n.

Resposta

NÃO. O método Simplex tem, no pior caso, complexidade exponencial.

Exercícios relacionados