A versão original de* esta história apareceu em Revista Quanta.
Em 1939, recém-chegando ao curso de estatística na UC Berkeley, George Dantzig, um estudante do primeiro ano de pós-graduação, escreveu dois problemas no quadro, pensando que eram tarefas 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 mais dias para concluí-lo. Algumas semanas depois, seu professor anunciou que havia resolvido dois famosos problemas abertos em estatística. O trabalho de Dantzig serviria de inspiração para sua tese de doutorado e seu filme décadas depois Boa vontade caçando.
Dantzig recebeu seu doutorado em 1946, logo após a Segunda Guerra Mundial, e logo se tornou consultor 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 baseou-se na alocação criteriosa de recursos limitados. Mas, ao contrário das guerras anteriores, esta competição foi verdadeiramente global em escala e foi vencida em grande parte pela força bruta. Os EUA só poderiam produzir mais tanques, veículos blindados e bombardeiros do que os seus inimigos. Sabendo disso, os militares têm estudado intensamente problemas de otimização, ou seja, como alocar estrategicamente recursos limitados em situações que poderiam envolver centenas ou milhares de variáveis.
A Força Aérea de Danzig tem trabalhado em novas maneiras de resolver problemas de otimização como este. A resposta é um método simples, um algoritmo que desenvolveu algumas técnicas matemáticas para resolver problemas de tableau há quase uma década.
Quase 80 anos depois, o método simples ainda está entre as ferramentas mais utilizadas quando é necessário tomar uma decisão logística ou da cadeia de abastecimento em condições complexas. É eficiente e funciona. “Ele sempre corria rápido e ninguém o via”, disse ele. Sophia Huiberts Centro Nacional Francês de Pesquisa Científica (CNRS).
Ao mesmo tempo, há um fato curioso que ofuscou por muito tempo o método de Dantzig. Em 1972, matemáticos provaram que o tempo para completar uma tarefa poderia aumentar exponencialmente com muitas restrições. Portanto, não importa quão rápido o método esteja em uso, as análises teóricas têm apresentado consistentemente os piores cenários que envolvem períodos de tempo exponencialmente mais longos. Para um método simples, “nossas ferramentas tradicionais para aprender algoritmos não funcionam”, disse Huiberts.
Mas no novo papel que será apresentado em dezembro na conferência da Computer Science Foundation, Huiberts et Eleon Bachum estudante de doutorado na Universidade Técnica de Munique, parece ter superado esse problema. Eles tornaram o algoritmo mais rápido e também forneceram razões teóricas pelas quais tempos de execução exponenciais, há muito temidos, não se materializam na prática. O trabalho que se sobrepõe quem eu me tornei de 2001 por Daniel Spielman e Shang-Hua Tengé esplêndido (e) lindo, segundo Teng.
“O trabalho técnico é muito importante, porque combina com habilidade muitas ideias desenvolvidas em linhas de pesquisa anteriores, (adicionando) algumas ideias técnicas muito legais”, disse. László Veghele não era matemático na Universidade de Bonn.
Geometria Ideal
Um método simples é projetado para os seguintes tipos de questões: Por exemplo, uma empresa de móveis fabrica armários, camas e cadeiras. Cada armário é três vezes mais útil que uma cadeira, enquanto cada cama é duas vezes mais útil. Se quiséssemos escrever isso como uma expressão, eu usaria um, be c* para fazer a quantidade de bens, digamos que todo o lucro seja proporcional a 3°um + 2b + c*.
Para maximizar os lucros, quantos itens de cada item a empresa deve produzir? A resposta depende das restrições do rosto. Digamos que a empresa consiga produzir, no máximo, 50 itens por mês, sim um + b + c* menor ou igual a 50 um é menor ou igual a 20. Cadeiras especiais requerem madeira e seu fornecimento é limitado, portanto c* deve ser inferior a 24
O método transforma uma situação simples como esta – embora muitas vezes envolva muitas variáveis – num problema geométrico. Imagine representar graficamente nossas restrições um, b e c* com três dimensões. Se * um menor ou igual a 20, podemos imaginar que o plano no gráfico tridimensional é perpendicular. um eixo, cortando em . um = 20. Queremos que nossa solução esteja em algum lugar nesse plano ou abaixo dele. Além disso, podemos combinar limites com outras restrições. Juntos, esses limites podem dividir o espaço em uma figura tridimensional complexa chamada poliedro.
