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
, onde
é o número de restrições e
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.
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
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
e de restrições
.
Passo 2
Cada solução básica corresponde a escolher um conjunto de
variáveis básicas dentre as
variáveis totais. Assim, o número máximo de vértices que o Simplex poderia visitar é dado por
que cresce exponencialmente quando
e
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
, exponencial em
.
Resposta
NÃO. O método Simplex tem, no pior caso, complexidade exponencial.