A versão original de esta história apareceu em Revista Quanta.
Em 1939, ao chegar atrasado ao seu curso de estatística na UC Berkeley, George Dantzig – um estudante do primeiro ano de pós-graduação – copiou dois problemas do quadro-negro, pensando que eram uma tarefa de casa. Ele achou o dever de casa “mais difícil de fazer do que o normal”, contaria mais tarde, e pediu desculpas ao professor por ter demorado alguns dias extras para concluí-lo. Algumas semanas depois, seu professor lhe disse que ele havia resolvido dois famosos problemas abertos de estatística. O trabalho de Dantzig serviria de base para sua tese de doutorado e, décadas depois, de inspiração para o filme Caça à Boa Vontade.
Dantzig recebeu seu doutorado em 1946, logo após a Segunda Guerra Mundial, e logo se tornou conselheiro matemático da recém-formada Força Aérea dos EUA. Tal como acontece com todas as guerras modernas, o resultado da Segunda Guerra Mundial dependeu da alocação prudente de recursos limitados. Mas, ao contrário das guerras anteriores, este conflito foi verdadeiramente de escala global e foi vencido em grande parte através do puro poder industrial. Os EUA poderiam simplesmente produzir mais tanques, porta-aviões e bombardeiros do que os seus inimigos. Sabendo disso, os militares estavam intensamente interessados em problemas de otimização – isto é, como alocar estrategicamente recursos limitados em situações que poderiam envolver centenas ou milhares de variáveis.
A Força Aérea encarregou Dantzig de descobrir novas maneiras de resolver problemas de otimização como esses. Em resposta, ele inventou o método simplex, um algoritmo que se baseou em algumas das técnicas matemáticas que ele desenvolveu ao resolver seus problemas no quadro-negro quase uma década antes.
Quase 80 anos depois, o método simplex ainda está entre as ferramentas mais utilizadas quando é necessário tomar uma decisão logística ou da cadeia de abastecimento sob restrições complexas. É eficiente e funciona. “Ele sempre correu rápido e ninguém viu que não era rápido”, disse Sophie Huiberts do Centro Nacional Francês de Pesquisa Científica (CNRS).
Ao mesmo tempo, há uma propriedade curiosa que há muito tempo lança uma sombra sobre o método de Dantzig. Em 1972, matemáticos provaram que o tempo necessário para completar uma tarefa poderia aumentar exponencialmente com o número de restrições. Portanto, não importa quão rápido o método possa ser na prática, as análises teóricas têm oferecido consistentemente os piores cenários, o que implica que poderá demorar exponencialmente mais tempo. Para o método simplex, “nossas ferramentas tradicionais para estudar algoritmos não funcionam”, disse Huiberts.
Mas em um novo papel que será apresentado em dezembro na conferência Foundations of Computer Science, Huiberts e Eleon Bachestudante de doutorado na Universidade Técnica de Munique, parecem ter superado esse problema. Eles tornaram o algoritmo mais rápido e também forneceram razões teóricas pelas quais os tempos de execução exponenciais que há muito temiam não se materializam na prática. O trabalho, que se baseia em uma resultado marcante de 2001 por Daniel Spielman e Shang-Hua Tengé “brilhante (e) bonito”, de acordo com Teng.
“É um trabalho técnico muito impressionante, que combina com maestria muitas das ideias desenvolvidas em linhas de pesquisa anteriores, (ao mesmo tempo em que adiciona) algumas novas ideias técnicas genuinamente boas”, disse László Veghum matemático da Universidade de Bonn que não esteve envolvido neste esforço.
Geometria Ideal
O método simplex foi projetado para resolver uma classe de problemas como este: Suponha que uma empresa de móveis fabrice armários, camas e cadeiras. Coincidentemente, cada armário é três vezes mais lucrativo que cada cadeira, enquanto cada cama é duas vezes mais lucrativa. Se quiséssemos escrever isso como uma expressão, usando um, be c para representar a quantidade de móveis produzidos, diríamos que o lucro total é proporcional a 3um + 2b + c.
Para maximizar os lucros, quantos itens de cada item a empresa deve produzir? A resposta depende das restrições que enfrenta. Digamos que a empresa consiga produzir no máximo 50 itens por mês, então um + b + c é menor ou igual a 50. Armários são mais difíceis de fazer – não mais do que 20 podem ser produzidos – então um é menor ou igual a 20. As cadeiras requerem madeira especial e seu fornecimento é limitado, então c deve ser inferior a 24.
O método simplex transforma situações como essa – embora muitas vezes envolvam muito mais variáveis – em um problema de geometria. Imagine representar graficamente nossas restrições para um, b e c em três dimensões. Se um é menor ou igual a 20, podemos imaginar um plano em um gráfico tridimensional que é perpendicular ao um eixo, cortando-o em um = 20. Estipularíamos que nossa solução deveria estar em algum lugar nesse plano ou abaixo dele. Da mesma forma, podemos criar limites associados a outras restrições. Combinados, esses limites podem dividir o espaço em uma forma tridimensional complexa chamada poliedro.
