Complexidade e Degenerescência do Simplex

• Definir uma solução básica factível degenerada: uma onde uma variável básica assume o valor zero, causada por um empate no teste da razão.
• Construir um pivô degenerado concreto, e explicar por que um pivô degenerado pode deixar o valor do objetivo completamente inalterado.
• Enunciar a regra de Bland (desempate sempre preferindo a variável de índice mais baixo) e explicar, em nível conceitual, por que ela comprovadamente previne ciclos.
• Enunciar o resultado de Klee-Minty: a regra padrão de variável de entrada do método simplex visita todos os 2ⁿ vértices de um politopo n-dimensional especificamente construído no pior caso, então o simplex não é um algoritmo de tempo polinomial no pior caso.
• Distinguir "simplex não é polinomial no pior caso" de "programação linear não é solucionável em tempo polinomial", e nomear a abordagem alternativa que fecha essa lacuna.

Toda execução de simplex traçada até agora nesta trilha terminou rapidamente, em dois ou três pivôs limpos, cada um estritamente melhorando o objetivo. Esse bom comportamento é típico na prática, mas não é garantido, e entender exatamente onde e por que pode falhar é essencial antes de confiar no simplex como uma caixa-preta em um problema genuinamente grande ou adversarialmente estruturado. Duas questões distintas valem a pena separar cuidadosamente: degenerescência, um estado específico do tableau que pode (raramente) fazer o algoritmo estagnar ou até entrar em loop para sempre sem uma salvaguarda, e comportamento exponencial de pior caso, um fato mais profundo sobre os limites teóricos da regra padrão de variável de entrada, descoberto por Klee e Minty em 1972, que remodelou como o campo inteiro entendeu a lacuna entre a velocidade prática típica de um algoritmo e sua garantia comprovada de pior caso, a mesma distinção que a disciplina de algoritmos deste currículo traçou entre o pior caso de caminho arbitrário de Ford-Fulkerson e o de Edmonds-Karp, comprovadamente limitado.

Degenerescência: um empate no teste da razão

Uma solução básica factível degenerada é uma na qual o valor de alguma variável básica é exatamente 0. Isso surge diretamente de um empate no teste da razão: quando duas ou mais linhas alcançam a mesma razão mínima, só uma delas é escolhida como a linha da variável de saída, mas a variável básica da outra linha empatada é então levada a exatamente 0 no próximo pivô de qualquer forma, sem o objetivo de fato melhorar naquele passo específico. Um pivô que não produz nenhuma mudança no valor do objetivo é chamado de pivô degenerado.

Degenerescência por si só não é um bug ou erro, é um estado de tableau perfeitamente legítimo (significa simplesmente que mais restrições estão justas no vértice atual do que o número mínimo necessário para fixá-lo, exatamente a situação que a caracterização de vértice dos conceitos anteriores permite: "pelo menos n restrições justas", não "exatamente n"). A preocupação é para onde a degenerescência pode, em casos raros e especificamente construíveis, levar: uma sequência de pivôs degenerados que revisita a mesma solução básica factível mais de uma vez, um loop infinito chamado ciclagem, que significaria que o algoritmo nunca termina de forma alguma.

A regra de Bland: prevenindo ciclagem com um desempate simples

A regra de Bland (Robert Bland, 1977) corrige isso com uma única disciplina fácil de enunciar: sempre que uma escolha precisar ser feita, seja entre várias variáveis de entrada candidatas com coeficientes de linha objetivo igualmente negativos, seja entre várias linhas empatadas no teste da razão, sempre escolha a variável com o índice mais baixo (assumindo que as variáveis são numeradas uma vez, consistentemente, no início). Essa regra pode ser provada como garantindo que o simplex termine em um número finito de pivôs, sem ciclagem, nunca, independente de como os empates acontecem de cair, embora a prova dessa garantia seja um argumento técnico cuidadoso além do que este conceito reproduz por completo; a conclusão praticamente importante é que uma correção documentada, simples e comprovadamente correta existe, e é o que implementações reais usam como reserva sempre que a degenerescência ameaça virar ciclagem (embora na prática, ciclagem seja rara o suficiente para que muitas implementações usem uma heurística de desempate mais rápida na maior parte do tempo, e só mudem para a regra de Bland se uma execução incomumente longa for detectada).

O resultado de Klee-Minty: comportamento exponencial de pior caso

Uma preocupação muito mais profunda que a degenerescência é esta: mesmo quando todo pivô estritamente melhora o objetivo (sem empates, sem nenhuma degenerescência), quantos pivôs o simplex pode precisar no pior caso, sobre todos os problemas possíveis de um dado tamanho? Victor Klee e George Minty responderam isso em 1972 com uma família especificamente construída de programas lineares, informalmente conhecida como cubos de Klee-Minty: um politopo n-dimensional, uma versão levemente "torcida" de um hipercubo comum, com exatamente 2ⁿ vértices, construído de forma que a regra padrão de variável de entrada de Dantzig (coeficiente mais negativo) visita cada um desses 2ⁿ vértices antes de alcançar o ótimo, um pivô de cada vez. Para n = 20 variáveis, isso é mais de um milhão de pivôs; o número de pivôs necessários cresce exponencialmente no número de variáveis, não polinomialmente. Essa única família de exemplos cuidadosamente projetada prova, rigorosamente, que o método simplex padrão não é um algoritmo de tempo polinomial no pior caso, um resultado importante e historicamente surpreendente, já que o simplex já havia sido usado com sucesso na prática por mais de duas décadas quando esse pior caso foi publicado.

Reconciliando teoria e prática

O resultado de Klee-Minty não significa que o simplex é lento na prática, e a experiência do mundo real confirma esmagadoramente que não é: em essencialmente todo problema encontrado fora de construções especificamente adversariais como o próprio cubo de Klee-Minty, o simplex termina em um pequeno número de pivôs, tipicamente crescendo apenas modestamente (frequentemente relatado como aproximadamente linear ou baixo-polinomial) com o tamanho do problema. A explicação rigorosa para essa lacuna entre teoria de pior caso e prática típica é a análise suavizada (Spielman e Teng, 2004): mesmo que uma entrada seja escolhida adversarialmente, uma pequena perturbação aleatória de seus dados (modelando a pequena e inevitável imprecisão ou "ruído" presente em quase qualquer entrada numérica real) torna o tempo de execução esperado do simplex polinomial, uma ponte matematicamente rigorosa entre o limite pessimista de pior caso que o cubo de Klee-Minty estabelece e o comportamento prático otimista que todo uso real do simplex de fato exibe.

O pior caso do simplex não significa que programação linear em si é difícil

É essencial separar duas afirmações diferentes. "Simplex, com a regra padrão de variável de entrada, não é polinomial no pior caso" é um fato sobre um algoritmo específico. Não é um fato sobre o problema de programação linear em si: programação linear é, de fato, solucionável em tempo polinomial no pior caso, por uma família genuinamente diferente de algoritmos chamados métodos de pontos interiores (o método do elipsoide de Leonid Khachiyan, 1979, foi o primeiro a estabelecer isso em princípio, embora impraticavelmente lento; o algoritmo de Narendra Karmarkar de 1984 foi o primeiro método de ponto interior prático, competitivo com o simplex no uso real). Esses métodos não caminham de vértice a vértice ao longo da fronteira do politopo de forma alguma, em vez disso se movendo através do interior do politopo, e sua garantia polinomial de pior caso fecha a lacuna que o resultado de Klee e Minty abriu: programação linear como um problema é fácil no mesmo sentido de pior caso que, digamos, a garantia de fluxo máximo de Edmonds-Karp, mesmo que o simplex, o algoritmo específico que esta trilha construiu em detalhe por sua clareza geométrica e domínio prático contínuo, não seja.

Exemplo 1: construindo e traçando um pivô degenerado concreto

Problema: Resolva maximizar x₁ + x₂ sujeito a x₁ ≤ 4, x₂ ≤ 4, x₁ + x₂ ≤ 8, x₁, x₂ ≥ 0 (uma terceira restrição redundante, já que as duas primeiras já forçam x₁+x₂ ≤ 8 em toda parte de sua caixa, tocando esse limite só no único canto (4,4)), e identifique exatamente onde a degenerescência aparece.

Montagem: x₁+s₁=4, x₂+s₂=4, x₁+x₂+s₃=8, linha objetivo z - x₁ - x₂ = 0.

Iteração 1: x₁ e x₂ empatam em -1; escolha x₁. Teste da razão: linha 1, 4/1=4; linha 3, 8/1=4, outro empate (linha 2 não tem x₁, pulada). Escolhendo a linha 1 (s₁ sai): pivoteando (linha 1 já normalizada) elimina x₁ da linha 3 (linha3 - linha1): x₂ - s₁ + s₃ = 4. Eliminando x₁ da linha objetivo: z - x₂ + s₁ = 4. Solução atual: x₁=4, s₂=4, s₃=4, x₂=s₁=0, z=4.

Iteração 2, o pivô degenerado: x₂ é o único coeficiente negativo (-1), então entra. Teste da razão: linha 2, 4/1=4; linha 3 (agora x₂-s₁+s₃=4), 4/1=4, empate novamente. Escolhendo a linha 2 (s₂ sai): eliminando x₂ da linha 3 (linha3 - linha2) dá -s₁ - s₂ + s₃ = 0, então a linha de s₃ agora lê s₃ = s₁ + s₂, significando s₃ = 0 com s₁=s₂=0 ainda não básicos. s₃, embora ainda tecnicamente básico, tem valor 0, exatamente a degenerescência que este conceito define. Eliminando x₂ da linha objetivo: z + s₁ + s₂ = 8.

Resultado: A linha objetivo z + s₁ + s₂ = 8 não tem coeficientes negativos, ótimo em x₁=4, x₂=4, z=8, correspondendo corretamente ao canto onde a terceira restrição redundante toca. A degenerescência (s₃=0 enquanto básico) não causou ciclagem aqui, esse problema específico acontece de terminar limpamente em exatamente 2 pivôs apesar do empate, ilustrando que degenerescência é uma condição de tableau real e identificável, não automaticamente um sintoma de um algoritmo travado ou quebrado.

Exemplo 2: dimensionando o pior caso de Klee-Minty concretamente

Problema: Para um cubo de Klee-Minty com n = 30 variáveis, compare o número de pivôs que a regra padrão de variável de entrada poderia precisar no pior caso contra o número de vértices que um politopo comum tipo hipercubo 30-dimensional tem.

Cálculo: O resultado de Klee-Minty dá um pior caso de 2ⁿ = 2³⁰ = 1.073.741.824, mais de um bilhão de pivôs, para um problema com apenas 30 variáveis de decisão, um tamanho de problema surpreendentemente pequeno para uma contagem de pivô de pior caso tão enorme. Essa é a escala concreta da lacuna que a análise suavizada explica para problemas reais, não construídos adversarialmente: um problema desse tamanho é resolvido pelo simplex na prática usando um número de pivôs tipicamente na casa das dezenas ou baixas centenas, não chegando nem perto de um bilhão.

• "Degenerescência significa que o algoritmo falhou ou travou." O Exemplo 1 mostra um pivô genuinamente degenerado (s₃=0 enquanto básico) que ainda termina corretamente no verdadeiro ótimo em exatamente 2 pivôs; degenerescência é um estado de tableau, não uma falha, e só se torna um problema se especificamente levar a ciclagem, um fenômeno raro, separado, e separadamente prevenível (via a regra de Bland).
• "Já que Klee-Minty provou que o simplex leva tempo exponencial, usar simplex em qualquer problema real é uma má ideia." O pior caso de um bilhão de pivôs do Exemplo 2, para um problema de meros 30 variáveis, é precisamente o tipo de cenário adversarialmente projetado que essencialmente nunca surge de modelagem real; a análise suavizada dá uma explicação rigorosa, não meramente anedótica, de por que o simplex permanece uma escolha rápida, confiável e ainda amplamente usada na prática.
• "Programação linear em si é um problema de tempo exponencial, já que seu algoritmo mais famoso é." Isso confunde o pior caso de um algoritmo específico com a dificuldade inerente do problema; métodos de pontos interiores (o método do elipsoide de Khachiyan, e na prática, o algoritmo de Karmarkar) resolvem programação linear em tempo polinomial no pior caso, então o problema de programação linear é eficientemente solucionável no sentido estrito da teoria da complexidade, mesmo que o algoritmo simplex especificamente não seja.
• "A regra de Bland deveria ser usada em todo pivô único, em toda implementação, para segurança." A regra de Bland garante terminação mas é tipicamente mais lenta na prática que heurísticas de desempate mais simples na vasta maioria de problemas reais, não degenerados ou levemente degenerados; a maioria das implementações de produção usa uma heurística mais rápida por padrão e reserva a regra de Bland (ou uma salvaguarda anti-ciclagem semelhante) especificamente para situações onde uma execução incomumente longa sinaliza que ciclagem pode de fato estar ocorrendo.

Uma solução básica factível degenerada tem uma variável básica no valor 0, surgindo de um empate no teste da razão, como o Exemplo 1 constrói concretamente e traça até um ótimo correto (embora degenerado); degenerescência sozinha não é uma falha, mas pode, em casos raros especificamente construídos, levar a ciclagem, um loop infinito que a regra de Bland (sempre desempatar pelo índice de variável mais baixo) comprovadamente previne. Separadamente e mais profundamente, o resultado de Klee e Minty de 1972 mostra que a regra padrão de variável de entrada pode exigir 2ⁿ pivôs no pior caso, visitando todo vértice de um politopo n-dimensional especificamente torcido, provando que o simplex não é um algoritmo de tempo polinomial no pior caso, um fato que a análise suavizada (Spielman e Teng, 2004) reconcilia com o desempenho prático esmagadoramente bom do simplex mostrando que uma pequena perturbação aleatória de qualquer entrada torna seu tempo de execução esperado polinomial. Crucialmente, esse pior caso pertence ao algoritmo simplex, não à programação linear como problema: métodos de pontos interiores resolvem programação linear em tempo polinomial de pior caso genuíno, fechando a lacuna que a construção de Klee e Minty abriu, mesmo que o simplex, por sua clareza geométrica, velocidade típica, e décadas de domínio prático contínuo, permaneça o método que esta trilha construiu com mais detalhe. O próximo conceito se volta para uma pergunta genuinamente diferente e profundamente informativa sobre todo programa linear: seu dual.