PHPSimplex

Biografia de George Bernard Dantzig

George Bernard Dantizig Ourisson, nasceu em 8 de novembro de 1914, em Portland, no estado de Oregon nos Estados Unidos. Filho de Tobías Dantzig, matemático russo e, Anja Ourisson, linguista francesa especializada em idiomas eslavos, que emigrou para os Estados Unidos em 1910, depois de se casar.

No início de 1920, a família Dantzig mudou-se de Baltimore a Washington, no estado de Maryland, onde Anja trabalhou como linguista na Biblioteca do Congresso e, Tobías ministrou aulas como professor de matemática na Universidade de Maryland, até que se aposentou deixando seu cargo de Chefe do Departamento de Matemática logo após a Segunda Guerra Mundial.

O pequeno George estudou nas escolas Powell Junior High School e Central High School. Desde sua infância, começou a mostrar um especial interesse pela geometria, também instigado por seu próprio pai, que lhe propunha complicados problemas de geometria projetiva.

George Dantzig, realizou seus estudos universitários na Universidade de Maryland, onde obteve uma licenciatura em Matemática e Física, em 1936. No entanto, sentiu-se decepcionado pelo fato de não ter visto uma única aplicação real da matemática em nenhuma das matérias que havia cursado.

No verão desse mesmo ano, casou-se com Anne Shmuner, e o casal recém-casado mudou-se para Ann Arbor. Ali continuou seus estudos, graças a uma bolsa de Horace Rackham, com um mestrado em Matemática pela Universidade de Michigan. Para ele, os cursos pareciam muito abstratos, com exceção da Estatística, de modo que desejava somente uma coisa: concluir seus estudos e concentrar-se no mundo do trabalho.

Assim, em 1937, Dantzig deixou Michigan para trabalhar em um projeto de pesquisa de mercado ("Urban study of consumer purchase") como estatístico no Bureau of Labor Statistics. No entanto, dois anos depois, decidiu completar seus estudos com um PhD em Estatística, sob a supervisão do famoso Professor Jerzy Neyman na Universidade de Berkeley, Califórnia.

Foi durante o seu primeiro ano em Berkeley, quando protagonizou uma anedota que foi considerada como uma lenda até que, anos mais tarde, Dantzig confirmou sua veracidade. Assim, em 1939, George participou de um curso de estatística ministrado pelo Professor Jerzy Neyman, que estava acostumado a propor um par de exercícios no quadro, no início de suas aulas, para que fossem resolvidos como tarefa de casa. Um dia, George chegou atrasado para a aula e anotou os dois problemas do quadro negro pensando que era dever de casa. Alguns dias depois, ele os entregou ao professor Neyman, desculpando-se por ter tardado um pouco mais que o habitual, já que, o pareceu "um pouco mais difícil do que os problemas normais". Cerca de 6 semanas mais tarde, quando Jerzy Neyman, revisou aquelas notas cuidadosamente e compreendeu a grande descoberta que poderia supor, então, em um domingo na primeira hora da manhã, apresentou-se na casa de seu aluno. Ele estava ansioso para propor à Dantzig a publicação de um artigo, com base na resolução destes exercícios, já que se tratava de dois famosos problemas não resolvidos da Estatística. Depois disso, e por sugestão de Neyman, George Dantzig desenvolveu sua tese de doutorado sobre estes problemas.

No entanto, não terminaria seu doutorado até 1946, já que o EUA entrava no combate da Segunda Guerra Mundial no final de 1941, então, interrompeu seus estudos pela segunda vez e mudou-se para Washington para se juntar à Força Aérea dos Estados Unidos. Onde ocupou o cargo de chefe da subdivisão civil de combate, no Centro de Controle Estatístico (USAF - Headquarters Statistical Control). Seu trabalho consistia na coleta e análise de dados dos combates aéreos (número de missões, bombas lançadas, aeronaves perdidas, taxas de abandono, etc.), bem como, lidar com a logística da cadeia de suprimentos e gestão de centenas de milhares de diferentes tipos de recursos materiais e humanos. Todo o planejamento foi realizado através de técnicas manuais, por isso, foram esses problemas, aparentemente insolúveis, o que estimulou a busca de um modelo matemático e lançou as bases do que se tornaria a programação linear. Pelo trabalho realizado durante a Segunda Guerra Mundial, foi premiado com a medalha de serviço civil excepcional, prestado ao Departamento de Guerra ("War Department's Exceptional Civilian Service Medal"), em 1944.

Após a guerra, ele voltou para Berkeley para terminar o seu doutorado, que havia interrompido. Uma vez obtido o título, ofereceram-lhe um cargo na Universidade, que recusou por tratar-se de um cargo modesto, embora com um bom salário ($ 14.000 por ano). Realmente foi dissuadido a aceitar a oferta de emprego por sua esposa, que não estava convencida, porque, em sua opinião, o magro salário lhe dificultaria a manter-se, pois já tinham um filho.

Assim, em junho de 1946, novamente em Washington considerava várias ofertas de emprego. Finalmente, persuadido por seus colegas da U.S.A.F. ele optou pelo cargo de assessor matemático para as Forças Aéreas. Trabalhou em uma metodologia para calcular a duração das fases de um programa de desdobramentos, treinamento e fornecimento de logística, mais rápida e eficiente à utilizada até aquele momento. Era a tentativa de mecanizar todo o processo de planejamento. Isso o levou a fazer suas grandes descobertas.

Com base no método de entrada-saída, concebido pelo economista russo Wassily Leontief em 1939 (por cujo trabalho recebeu o Prêmio Nobel), ele estabeleceu o problema geral de programação linear. No entanto, os problemas eram complexos demais para os computadores mais rápidos da época. Era necessário desenvolver um método capaz de encontrar soluções dentro de um prazo razoável. Neste ponto entra em jogo a intuição geométrica que Dantzig tinha desenvolvido em sua juventude. Conforme suas próprias declarações: "Comecei observando que a região viável é um corpo convexo, ou seja, um conjunto poliédrico. Portanto, o processo poderia ser melhorado, se os movimentos ao longo das bordas são feitos a partir de um vértice para o seguinte. No entanto, este procedimento parecia ser muito ineficiente. Em três dimensões, a região poderia ser visualizada como um diamante com faces, arestas e vértices. No caso de muitas arestas, o processo levaria a um percurso ao longo delas, antes de poderem atingir o vértice ótimo do diamante." No verão de 1947, realizou a primeira formulação do método Simplex.

O primeiro problema prático resolvido com este novo método foi o problema nutricional que havia apresentado George Joseph Stigler no final da década anterior, devido ao interesse do exército americano de encontrar uma dieta equilibrada para alimentar as suas tropas, que atendesse aos requisitos mínimos de nutrição e que fosse econômico. O problema, que consistia em 9 equações e 77 incógnitas, foi resolvido manualmente após 120 dias de trabalho. Mostrou-se que o resultado obtido se diferenciou apenas poucos cêntimos da solução encontrada anteriormente, por métodos heurísticos, resultando um sucesso o novo método Simplex.

Nessa época, mais especificamente em junho de 1947, a Força Aérea estabeleceu um grupo de trabalho dedicado a melhorar os processos de planejamento de grande escala, que foi chamado de Projeto SCOOP (Scientific Computation of Optimal Programs). Georger Dantzig permaneceu como chefe matemático deste grupo até o ano de 1952.

Em 03 de outubro de 1947, Dantzig visitou o Instituto de Estudos Avançados (IAS), uma escola de pós-graduação independente localizada em Princeton (Nova Jersey), onde eram feitas investigações em vários campos científicos. Ali conheceu John von Neumann, considerado o melhor matemático do mundo, que falou do seu trabalho com Oscar Morgenstern sobre a teoria dos jogos. Ao longo de 1944, o casal tinha realizado uma pesquisa sobre jogos de soma zero (jogos onde todos os participantes sabem a priori as estratégias e as consequências da subtração), culminando no teorema "minimax", que diz que há uma possível jogada em que minimizam a perda máxima (daí o seu nome). Como resultado de suas pesquisas, publicaram o livro " Theory of Games and Economic Behavior (Teoria dos Jogos e Comportamento Econômico)." Assim, George tomou consciência pela primeira vez da importância da Teoria da Dualidade.

No início dos anos 50, mais especificamente em junho de 1952, começou a trabalhar na RAND Corporation (Research ANd Development), uma empresa fundada em 1948 pela Força Aérea dos EUA para pesquisa e desenvolvimento. A sua tarefa era a aplicação do método Simplex em computadores, a fim de obter resultados num tempo muito mais curto.

Na imagem pode-se ver a capa de um dos memorandos da investigação publicada na RAND. Sua referência é RM-1264 e foi publicada em 1954 sob o título "Notes on Linear Programming" (Notas sobre Programação Linear): The generalized Simplex method for minimizing a linear form under linear inequality restrains. Encontra-se disponível para download, juntamente com outros documentos e memorandos sobre o site oficial da RAND: www.rand.org/pubs/research_memoranda/RM1264.html

Em 1954, Dantzig junto com outros dois companheiros matemáticos, Delbert Ray Fulkerson e Selmer Martin Johnson, alcançaram um marco matemático em otimização combinatória ao resolver o problema do viajante comercial, também conhecido como o problema do viajante, ou TSP do acrônimo Inglês Traveling Salesman Problem. Consiste em encontrar a melhor rota para um vendedor que deve visitar um determinado conjunto de cidades, cumprindo as seguintes condições: a distância total percorrida deve ser mínima, visitar cada cidade apenas uma vez e voltar ao ponto de partida uma vez que o caminho é realizado. O problema resolvido era composto por 49 cidades, uma para cada estado dos EUA (Alasca e Havaí não eram estados a até 1959). Foram aplicadas as recentes técnicas de programação linear dando lugar ao método dos Planos de Corte (Cutting-Plane method), precursor do algoritmo de Ramificação e de Corte (Branch and Bound algorithm). Os resultados desta pesquisa foram publicados no artigo "Solution of a large-scale Traveling Salesman Problem". Tais problemas têm múltiplas aplicações além de encontrar um caminho mínimo em logística, atualmente, é utilizado em áreas como design de chips, sequenciação do genoma, observações astronômicas da NASA, etc.

Em geral, os problemas têm parâmetros com elevado componente aleatório ou falta de fiabilidade dos dados, devido, entre outros fatores, que não seja possível determinar exatamente o que vai acontecer no futuro. Por exemplo, um problema de investimento no mercado de ações, o tempo afeta a solução incluindo a incerteza de saber se o valor aplicado deve ser mantido ou sofrerá uma queda desastrosa. Isto levou a uma nova área na Programação Linear em 1955, chamada de programação estocástica ou Programação sob Incerteza, amplamente desenvolvido por George Bernard Dantzig, novamente, e exposto também em seu livro "Linear Programming under Uncertainty". Evelyn Martin Lansdowne Beale também realizou, na Inglaterra, de forma paralela e independente, pesquisas nesta área.

No entanto, as investigações de George Dantzig não se limitaram apenas aos temas citados, mas também incluíram aplicações de variáveis discretas, problema da mochila, rede e rotas de caminho mais curto, o método Simplex revisado e muito mais. Um exemplo disto é um outro método amplamente utilizado hoje em dia: o princípio da decomposição, que foi desenvolvido juntamente com Philip Wolfe, entre 1959 e 1960. Conhecido como o método de decomposição de Dantzig-Wolfe, na qual fornece diretrizes para solução de grandes problemas, ou seja, que envolvem grandes quantidades de dados e variáveis. Curiosamente, há uma abordagem dual, chamada de método de Decomposição de Benders, atualmente muito utilizado na Programação Estocástica.

George voltou para a Universidade de Berkeley em 1960, onde deu início a uma brilhante carreira como professor do departamento de Engenharia Industrial, tutor e assessor dos estudantes de doutorado. Neste mesmo ano, fundou o Centro de Pesquisa Operacional (Operations Research Center) e foi estabelecido como diretor do mesmo.

Durante este período, em Berkeley escreveu seu grande livro de referência "Linear Programming and Extensions", publicado em agosto de 1963. Esta publicação apresenta o trabalho realizado no Pentágono e na RAND Corporation descrevendo, entre outros, o método Simplex a partir de sua teoria mais básica até seu uso para solucionar problemas reais vários tipos. Este livro poder ser baixado em formato PDF na página oficial da RAND: www.rand.org/pubs/reports/R366.html.

Por volta de 1963, Dantzig propôs para a administração da Universidade de Stanford (Palo Alto), a criação de um programa interdepartamental de Pesquisa Operacional entre ambas universidades, porém a proposta foi rejeitada. Três anos mais tarde, Dantzig começou a trabalhar na Universidade de Stanford como professor no Departamento de Pesquisa Operacional e Ciência da Computação. Através de uma anedota, George Explica, que uma das razões para sua mudança de Berkeley para Stanford era um espaço de estacionamento situado à porta do departamento onde trabalhava. No entanto, teve a má sorte de que ao mudar-se todo o estacionamento já não existia, inclusive sua almejada vaga.

Os avanços em computação na década de 60, permitiram enfrentar a resolução de problemas reais em tempo finito. Motivado por isso, Dantzig fundou em 1967 na Universidade de Stanford, o Systems Optimization Laboratory (SOL) para a pesquisa básica e aplicada de programação matemática em grande escala: desenvolvimento de algoritmos, formulação de modelos, e produção de software. O trabalho deste laboratório incluía problemas de planejamento de investimentos ao longo do tempo, projetos de engenharia e otimização, sistemas físicos, biológicos e ecológicos, planejamento urbano e sistemas de transporte. Entre os projetos de SOL destaca-se o projeto PILOT destinado a um melhor planejamento e à economia no setor de energia nos EUA.

George Dantzig visitou várias vezes o International Institute of Applied Systems Analysis (IIASA), localizado em Laxemburgo (cidade a 30 km de Viena, Áustria). O IIASA é uma organização de pesquisa não-governamental, onde estudos científicos são realizados em várias áreas como a econômica, tecnológica, ambiental e social. Em 1973, passou um ano sabático com sua esposa Anne, colaborando como chefe do grupo de metodologia nas instalações do IIASA. Uma anedota protagonizada por George Dantzig expressa seu interesse na otimização de problemas reais. Durante sua estadia, um dia George notou um longo caminhão parado em frente a seu escritório e, colocando em dúvida as vantagens do seu comprimento, perguntou ao gerente Ruth Steiner sobre o conteúdo do caminhão, sua origem, rota, e questionou como era possível que circulasse nas estreitas ruas. Ruth respondeu que o caminhão transportava móveis de Salzburgo, viajando pela rodovia e, manobrando para passar pelas ruas. Então, George estudou os dados e, pouco depois, disse a Ruth que a transportadora poderia economizar 40% dos gastos usando 4 caminhões menores e sugeriu informar isto à empresa.

George continuou seu trabalho como professor na Universidade de Stanford até 1973, quando se tornou professor C. A. Criley em Ciências do Transporte ("C. A. Criley cátedra em Ciência do Transporte"). Ele se aposentou oficialmente em 1977, mas permaneceu ativo até 1985 como professor emérito.

O excelente e enorme trabalho de investigação que desenvolveu toda a sua vida e os fascinantes resultados, descobertas e contribuições à ciência foram cruciais para ser digno de um grande número de prêmios, mas não conseguiu obter o Prêmio Nobel.

Então, em 1975, George Bernard Dantzig foi o primeiro a receber o Prêmio John von Neumann Theory Prize, concedido pelo Instituto de Pesquisa Operacional e Ciências de Gestão pelo seu trabalho continuado e contribuição fundamental nestes campos.

Textualmente, "por inventar a Programação Linear e descobrir métodos que levaram a grandes aplicações científicas e técnicas em grande escala em problemas importantes de logística, planejamento e otimização de redes, e pelo uso de computadores para fazer uso eficiente da teoria matemática descoberta", foi concedido em 1975 a Medalha Nacional de Ciências na disciplina de matemática, estatística e computação (" National Medal of Science in the Mathematical, Statistical, and Computer Sciences discipline"). Esta é maior homenagem concedida em Ciências nos Estados Unidos, assim a cerimônia ocorreu em 18 de outubro de 1976, na Casa Branca, onde o presidente Gerald Ford, conferiu o prêmio.

George recebeu doutorados "honoris causa" em várias universidades ao redor do mundo. Cabe destacar o concedido por sua universidade Alma Mater de Maryland em 1976, com a seguinte citação: "A Programação Linear de Dantzig tem sido uma das principais forças motrizes do surgimento de uma nova disciplina matemática para a tomada de decisão chamada Pesquisa Operacional na década de 50".

Em reconhecimento da sua dedicação, obteve diversos prêmios nacionais e internacionais. Alguns deles eram o Prêmio da Academia Nacional de Ciências em Matemática Aplicada e Análise Numérica ("National Academy of Science Award in Applied Mathematics and Numerical Analysis") em 1977, o Prêmio Harvey em Ciência e Tecnologia da Universidade de Technion (" Harvey Prize in Science and Technology ") de Israel, em 1985, e a Medalha de prata da Sociedade Britânica de Pesquisa Operacional ("Silver Medal of the British Operational Research Society ") em 1986. Teve a honra de ser a primeira pessoa incluída no Hall da Fama - Fame de la International Federation of Operational Research Societies (IFORS).

O grupo de ex-alunos do professor Dantzig formado por R. W. Cottle, E. L. Johnson, R. M. van Slyke e R. J. B. Wets, fundaram em sua honra o Prêmio Dantzig Price, em 1982. Este prêmio é atribuído a cada três anos pela Mathematical Optimization Society (MOS) e pela Society for Industrial and Applied Mathematics (SIAM)..

Ao longo de sua vida, publicou muitos trabalhos e vários livros. No entanto, o livro "Linear Programming" composto por dois volumes, que expressou as principais ideias de seus estudos e pesquisas, que é considerado como a Bíblia da Programação Linear e Pesquisa Operacional. O primeiro, com o subtítulo "Introduction", foi publicado em 1997, enquanto o segundo, "Theory and Extensions" não apareceu até 2003. Ambos foram escritos de forma conjunta com Mukund N. Thapa. O primeiro volume, como indica seu nome, trata dos aspectos básicos da Programação Linear e suas aplicações reais. Enquanto, o segundo amplia a teoria, e são incluídas variantes do método simplex, métodos de pontos interiores e até mesmo a teoria dos jogos, entre outros.

O próprio Dantzig surpreendeu-se de que o método Simplex fosse tão eficiente, como pôde-se observar em uma entrevista em 1999. Citando suas próprias palavras: "Na maioria das vezes, o método Simplex resolvia problemas de m equações em 2m ou 3m etapas, algo realmente impressionante. Eu realmente nunca pensei que ia ser tão eficiente. Naquela época, eu ainda tinha pouca experiência com problemas grandes e não confiava em minha intuição geométrica. Por exemplo, pensava que o procedimento exigiria muitos passos de um vértice para o próximo. Mas, na prática são poucos passos. Em poucas palavras, a intuição em grandes espaços não é um bom guia. Somente, 52 anos depois do método Simplex ser proposto pela primeira vez, as pessoas estão começando a ter uma ideia do motivo pelo qual o método funciona tão bem".

George Bernard Dantzig, morreu aos 90 anos, em 13 de maio de 2005, em sua casa de Stanford devido a complicações com a diabete e problemas cardiovasculares.