versão original de esta história apareceu em Revista Quanta.
Em 1939, George Danzig, um estudante do primeiro ano de pós-graduação que estava atrasado para um curso de estatística na Universidade da Califórnia, Berkeley, copiou dois problemas do quadro-negro, pensando que eram trabalhos de casa. Mais tarde, ele lembrou que sentiu que o dever de casa estava “mais difícil do que o normal” e pediu desculpas ao professor por ter demorado dias extras para concluí-lo. Algumas semanas depois, seu professor lhe disse que ele havia resolvido dois famosos problemas abertos de estatística. A pesquisa de Danzig serviu de base para sua tese de doutorado e décadas depois serviu de inspiração para um filme. boa vontade caçando.
Danzig recebeu seu doutorado em 1946, logo após a Segunda Guerra Mundial, e logo se tornou consultor de matemática da recém-criada Força Aérea dos Estados Unidos. Como todas as guerras modernas, vencer ou perder a Segunda Guerra Mundial dependia da alocação criteriosa de recursos limitados. Mas, ao contrário das guerras anteriores, este conflito teve um âmbito verdadeiramente global e foi vencido principalmente através do puro poder industrial. Os Estados Unidos só podem produzir mais tanques, porta-aviões e bombardeiros do que os seus inimigos. Sabendo disto, os militares tinham um grande interesse em problemas de optimização: como alocar estrategicamente recursos limitados em situações onde centenas ou mesmo milhares de variáveis podem estar envolvidas.
A Força Aérea encarregou Danzig de encontrar novas maneiras de resolver tais problemas de otimização. Em resposta a isso, ele inventou o método simplex. Este é um algoritmo que usa algumas das técnicas matemáticas que desenvolvi ao resolver problemas do quadro-negro há cerca de uma década.
Quase 80 anos depois, a metodologia simplex continua a ser uma das ferramentas mais utilizadas quando as decisões logísticas ou da cadeia de abastecimento precisam de ser tomadas sob restrições complexas. É eficiente e eficaz. “Estava sempre correndo rápido e ninguém nunca viu que não era rápido”, disse ele. Sophie Huiberts do Centro Nacional Francês de Pesquisa Científica (CNRS).
Ao mesmo tempo, há uma qualidade estranha que há muito acompanha o método de Danzig. Em 1972, matemáticos provaram que o tempo necessário para completar uma tarefa pode aumentar exponencialmente com o número de restrições. Portanto, não importa quão rápido este método seja, a análise teórica sempre forneceu um cenário de pior caso, sugerindo que poderia levar um tempo exponencialmente maior. Quanto ao método simplex, “as ferramentas tradicionais para estudar algoritmos não funcionam”, disse Heubertz.
Mas novo papel Ele será apresentado na conferência Fundamentos da Ciência da Computação em Huiberts, em dezembro. Elion BachUm estudante de doutoramento da Universidade Técnica de Munique parece ter ultrapassado este problema. Eles aceleraram o algoritmo e também forneceram uma razão teórica pela qual os tão temidos tempos de execução exponenciais podem não se materializar. Este trabalho é resultados inovadores Desde 2001 Daniel Spillman e Teng ShanhuaSegundo Teng, é “resplandecente (e) lindo”.
“Esta é uma conquista técnica muito impressionante, combinando de forma inteligente muitas ideias desenvolvidas em áreas de pesquisa anteriores, ao mesmo tempo que adiciona algumas novas ideias técnicas realmente excelentes”, disse ele. Laszlo Vegum matemático da Universidade de Bonn, não esteve envolvido no esforço.
forma ideal
O método simplex foi projetado para resolver uma série de problemas, incluindo: Suponha que uma empresa de móveis fabrice armários, camas e cadeiras. Coincidentemente, cada armário é três vezes mais rentável que cada cadeira, e cada cama é duas vezes mais rentável. Se você quiser escrever isso como uma expressão, você pode fazer assim: ser, be c Expressando a quantidade de móveis produzidos, podemos dizer que o lucro total é proporcional a 3.ser +2b + c.
Quantos de cada bem uma empresa deve produzir para maximizar os lucros? A resposta depende das restrições que enfrenta. Suponha que uma empresa possa produzir até 50 itens por mês. ser + b + c é menor ou igual a 50. Criar armários é difícil e não pode ser feito depois de 20. ser é menor ou igual a 20. A cadeira requer madeira especial, mas os suprimentos são limitados; c Deve ser inferior a 24.
O método simplex transforma essas situações (muitas vezes envolvendo mais variáveis) em um problema de geometria. Imagine gráficos de restrições. ser, b e c Em três dimensões. se ser Se for menor ou igual a 20, você pode imaginar um plano perpendicular ao gráfico tridimensional. ser corte o eixo ser = 20. Especifica que a solução deve estar em algum lugar nesse plano ou abaixo dele. Da mesma forma, você pode criar limites associados a outras restrições. A combinação desses limites nos permite dividir o espaço em formas tridimensionais complexas chamadas poliedros.
