PHPSimplex

Otimizar os recursos com Programação Linear



Entrevista de George Bernard Dantzig publicado em The College Mathematical Journal, em março de 1986.

«Considere o problema de atribuir 70 homens a 70 empregos. Uma 'atividade' consiste em atribuir o i-ésimo homem ao j-ésimo emprego. As restrições são duas: primeiro, há 70 homens, e para cada um deve ser atribuído um cargo, e em segundo lugar, cada um dos 70 postos de trabalho existentes deve ser ocupado. O nível de uma atividade pode ser 1, que indica que está sendo usado, ou 0 que indica que não. Consequentemente, há 2 x 70 = 140 restrições e 70 x 70 = 4.900 atividades com 4900 variáveis de decisão correspondente de um-zero. Infelizmente, também há 70 permutações fatoriais ou maneiras de fazer as atribuições. O problema consiste em comparar estes fatoriais de 70 formas e escolher o que é ideal ou "melhor" de acordo com alguns critérios previamente estabelecidos.»

«No exemplo acima, o fatorial de 70 é um número muito grande. Com o objetivo de ter uma ideia do real tamanho, suponha que existisse um computador IBM do tipo main-frame no momento em que aconteceu o Big Bang, há quinze milhões de anos. Seria possível, naquele momento e agora, examinar todas possíveis soluções? Não! No entanto, suponha que houvesse um computador ainda mais poderoso, que pudesse examinar bilhões de atribuições por segundo. A resposta continuaria sendo negativa. Mesmo se a terra estivesse cheia de computadores, em que sua rapidez fosse nanossegundos, todos eles trabalhando de forma paralela, a resposta ainda seria não. No entanto, se existisse dez terras, todas cheias de computadores do tipo mencionado, todos programados em paralelo a partir do instante do Big Bang até que o sol fosse uma esfera fria, então talvez a resposta poderia ser sim. O mais extraordinário é que o método simplex, com a ajuda de um computador moderno, pode resolver este problema em uma fração de segundo.»

Foto de George Bernard Dantzig

«Quando o problema de planejamento foi inicialmente desenvolvido para a Força Aérea, não havia nenhuma noção exata de uma função objetivo, a ideia de uma meta claramente definida. Evidentemente, tínhamos um falso respeito pelo conceito de objetivo. No discurso dos militares, escutei muitas vezes dizerem, ‘nosso objetivo é ganhar a guerra’. No mundo dos negócios, possivelmente ouviríamos, ‘nosso objetivo é lucrar’. No entanto, era impossível encontrar qualquer ligação direta entre a meta fixada e as medidas tomadas para esse fim.»

«Se estudássemos cuidadosamente o próximo passo, era possível notar que algum líder tinha passado um monte de regras básicas que, em sua opinião, conduziriam à meta. Isto ficava muito distante do que seria honestamente estudar todas as combinações alternativas de ações a serem tomadas para escolher a melhor combinação. As pessoas que governam, normalmente, movimentam suas mãos e dizem "Considerei todas as alternativas". Porém isto, quase sempre é lixo. Provavelmente, não puderam estudar todas as combinações. Antes de 1947, era inconcebível pensar na existência de uma ferramenta como a programação linear que permitisse examinar milhões de combinações. Não havia nenhum algoritmo ou ferramenta computacional que poderia fazer isso.»

«Não descobri o modelo da programação linear em um instante, mas foi um processo de evolução. Dediquei-me um ano inteiro para decidir se o meu modelo poderia ser usado na formulação de distribuição de tempos de problemas práticos. Como você sabe, o planejamento e a distribuição de tempos foram implementadas em grandes proporções durante a guerra. A operação da Força Aérea foi equivalente ao funcionamento da economia de uma nação. Houve a intervenção de milhares de pessoas neste processo. Para alguém que não esteve ali, é difícil de entender a magnitude que chegou a logística. Meu colega Marshall Wood e eu revisamos milhares de situações tomadas da nossa experiência durante a guerra.»

«As regras básicas empregadas no planejamento foram expressas em um formato muito diferente do que é empregado na atualidade para formular um programa linear. O que fizemos foi rever essas regras, uma a uma, e mostrar que quase todas elas poderiam ser reformuladas aceitavelmente em um formato de programação linear. Mas, não todas. Em alguns casos, foi necessário levar em conta o caráter discreto das variáveis e as não-convexidades.»

«Quando eu formulei o meu primeiro modelo de programação linear, o fiz sem uma função objetivo. Estive lutando por algum tempo com a adição de regras básicas para escolher entre as soluções viáveis, a que em algum sentido fosse 'ótima'. Porém, logo abandonei esta ideia e a substituí por uma função objetivo a ser maximizada. O modelo que formulei não foi feito especificamente para fins militares. Podia ser aplicado em todo tipo de problemas de planejamento; tudo o que tinha que ser feito era mudar os nomes das colunas e as linhas, e assim poderia ser aplicado em um problema de planejamento econômico e, da mesma forma, em um problema de planejamento industrial.»


Copyright ©2006-2017 PHPSimplex. Todos os direitos reservados. Termos e condições.
Siga-nos no Twitter
X

PHPSimplex
Versão 0.81

Copyright ©2006-2017. Todos os direitos reservados.

Desenvolvido por:
Daniel Izquierdo Granja
Juan José Ruiz Ruiz

Tradução para o Inglês por:
Luciano Miguel Tobaria

Tradução para o Francês por:
Ester Rute Ruiz

Tradução para o Português por:
Rosane Bujes