versão original de esta história apareceu em Revista Quanta.
George Dantzig, um estudante de pós-graduação que chegou atrasado ao curso de estatística na UC Berkeley em 1939, copiou dois problemas no quadro, pensando que eram trabalhos de casa. Mais tarde, ele lembrou que o dever de casa estava “mais difícil do que o normal” e pediu desculpas ao professor por demorar mais alguns dias para concluí-lo. Algumas semanas depois, seu professor lhe disse que ele havia resolvido dois famosos problemas não resolvidos de estatística. O trabalho de Dantzig serviu de base para sua tese de doutorado e serviu de inspiração para um 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 de matemática da recém-criada Força Aérea dos EUA. Como todas as guerras modernas, o resultado da Segunda Guerra Mundial dependeu da alocação cuidadosa de recursos limitados. Mas, ao contrário das guerras anteriores, esta foi verdadeiramente global em escala e foi vencida em grande parte através do puro poder industrial. Os Estados Unidos podem produzir mais tanques, porta-aviões e bombardeiros do que os seus inimigos. Sabendo disto, os militares têm tido um grande interesse em problemas de optimização: como alocar estrategicamente recursos limitados em situações que podem envolver centenas ou milhares de variáveis.
A Força Aérea encarregou Dantzig de encontrar novas maneiras de resolver problemas de otimização como este. Em resposta, ele inventou o método simplex, um algoritmo que utilizava algumas das técnicas matemáticas que ele havia desenvolvido ao resolver problemas do quadro-negro quase uma década antes.
Quase 80 anos depois, os métodos simples continuam a ser uma das ferramentas mais utilizadas quando as decisões logísticas ou da cadeia de abastecimento devem ser tomadas sob restrições complexas. É eficiente e funciona. “Ele está sempre indo rápido e ninguém nunca o viu não rápido”, disse ele. Sophie Huberts Afiliado ao Centro Nacional Francês de Pesquisa Científica (CNRS).
Ao mesmo tempo, há uma característica interessante que há muito tempo lança uma sombra sobre o método de Dantzig. Em 1972, matemáticos demonstraram 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 o método seja na prática, a análise teórica tem apresentado consistentemente um pior cenário que sugere que poderia levar exponencialmente mais tempo. Para métodos simples, “as ferramentas existentes para estudar algoritmos não funcionam”, disse Huiberts.
mas novo papel Isso será realizado em dezembro na Conferência de Fundamentos da Ciência da Computação, Huiberts e 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 uma razão teórica pela qual o tão temido tempo de execução exponencial pode não ser uma realidade na prática. Uma obra criada com base resultados inovadores Desde 2001 Daniel Spielman e Teng SanghwaDe acordo com Teng, é “lindo (e) lindo”.
“Este é um trabalho técnico muito impressionante que combina habilmente muitas das ideias desenvolvidas em linhas de pesquisa anteriores, ao mesmo tempo que adiciona algumas novas ideias técnicas realmente interessantes”, disse ele. Laszlo imploraUm matemático da Universidade de Bonn que não esteve envolvido neste esforço.
geometria ideal
Métodos simples são projetados para resolver os seguintes tipos de problemas: Digamos que uma empresa de móveis fabrica armários, camas e cadeiras. Acontece que cada cômoda é três vezes mais lucrativa que uma cadeira, e cada cama é duas vezes mais lucrativa. Se você quiser escrever isso como uma expressão, use: sem chance, chuvae aspirar Para expressar a quantidade de móveis produzidos, podemos dizer que o lucro total é proporcional a 3.sem chance + 2chuva + aspirar.
Quantas unidades de cada item a empresa deve produzir para maximizar o lucro? A resposta depende das restrições que você enfrenta. Digamos que sua empresa consiga produzir até 50 itens por mês. sem chance + chuva + aspirar Existem 50 ou menos. Armário é mais difícil de fazer. Você não pode produzir mais de 20 peças. sem chance São menos de 20. A cadeira requer madeira especial e tem fornecimento limitado. aspirar Deve ser inferior a 24.
Os métodos simplex transformam situações como esta (muitas vezes envolvendo mais variáveis) em problemas geométricos. Imagine representar restrições como um gráfico. sem chance, chuva e aspirar Em três dimensões. se sem chance Se for menor ou igual a 20, você pode imaginar um plano perpendicular a um gráfico tridimensional. sem chance Corte o eixo. sem chance = 20. Estipulamos que a solução deve estar em algum lugar acima ou abaixo desse plano. Da mesma forma, você pode criar limites que envolvam outras restrições. A combinação desses limites nos permite dividir o espaço em formas tridimensionais complexas chamadas poliedros.
