Programação Linear

O problema básico de programação linear consiste no seguinte: dada uma matriz e vetores e , encontrar um vetor tal que

       

Dois mil anos antes de Cristo exemplos especiais de equações lineares já tinham sido estudadas por egípcios e babilônios. Os babilônios também consideraram duas equações lineares em duas variáveis. Babilônios, gregos e chineses conheciam a idéia de eliminação de variáveis para resolver equações lineares (ou quadráticas).

O que hoje é conhecido como o método de eliminação gaussiana foi descrito explicitamente no `Nove Livros de Aritmética' chinês que foi escrito entre 202 A.C. e 9 D.C. e descreve métodos que provavelmente foram escritos muito antes. Equações lineares e eliminação de variáveis também foram estudadas por Diophantos de Alexandria (aprox. terceiro século D.C.).

O nome eliminação gaussiana é devido a alguns artigos de Gauss onde eliminação é aplicada. Gauss estudou equações lineares para estimar as órbitas de corpos celestes e observou que, se um sistema de equações e incógnitas não admite solução ou admite várias soluções, então existe um vetor tal que (que é uma espécie de afirmação `dual'). Em um de seus artigos Gauss também descreveu o que é hoje conhecido como processo de ortogonalização de Gram-Schmidt, que decompõe uma matriz como , onde é uma matriz ortogonal (i.e. e é triangular superior. Logo, pode ser trocado por , que é mais fácil de ser resolvido.

Enquanto resolver vários tipos de equações foi um tópico central em matemática, até recentemente pouca atenção foi dada a encontrar uma solução `ótima'. As aplicações em problemas de transporte na década de 40 (em particular, pelas forças armadas durante a segunda grande guerra mundial) foi um primeiro passo importante na criação da programação linear. Entre os pioneiros que fizeram o desenvolvimento da área estão George Dantzig em Washington e Leonid Kantorovich em Leningrado. Ambos ilustraram muito bem as fontes de aplicações da programação linear; Dantzig trabalhava para o Pentágono (inclusive durante o período da guerra entre 1941 e 1945), enquanto Kantorovich foi motivado pelo plano econômico Soviético. Outros pioneiros são Von Neumann (Game Theory), Wassily Leontief (Input-Output Model of the Economy) e Tjalling Koopmans (Theory of Optimum Allocation of Resources). Kantorovich, Koopmans e Leontief receberam o prêmio Nobel em economia; sobre isto, em Chvátal [2] encontramos o seguinte:

``...On October 14, 1975, the Royal Sweden Academy of Sciences awarded the Nobel Prize in economic science to L.V. Kantorovich and T.C. Koopmans ``for their contributions to the theory of optimum allocation of resources.'' (As the reader may know, there is no Nobel Prize in mathematics. Apparently the Academy regarded the work of G.B. Dantzig, who is universally recognized as the father of linear programming, as being too mathematical.)...''

Em 1946 Dantzig era consultor para a US Air Force Comptroller no Pentágono. Foi no Pentágono que Dantzig recebeu dos seus colegas D. Hitchcock e M. Wood o desafio de tentar mecanizar o processo de planejamento. No verão de 1947 Dantzig propôs o método simplex que tornou possível a solução de problemas de otimização de vários tipos, como transporte, produção, alocação de recursos e problemas de escalonamento (scheduling). O desenvolvimento dos computadores permitiu a aplicação do método simplex a problemas de grande porte, enquanto que, por outro lado, o método revelou alguns dos problemas numéricos que podem ocorrer em cálculos feitos por um computador -- o que motivou a busca de soluções para estes problemas.

No início da década de 50 começaram a surgir várias áreas as quais chamamos hoje coletivamente de programação matemática. Essas subáreas de programação matemática cresceram rapidamente -- com programação linear desempenhando um papel fundamental nesse desenvolvimento. Entre essas subáreas estão: programação não-linear (começou por volta de 1951 com a famosa condição de Karush-Kuhn-Tucker); aplicações comerciais; fluxos em redes; métodos de grande porte; programação estocástica; e programação inteira.

Dantzig [4] descreve a origem de certos termos:

``Here are some stories about how various linear programming terms arose. The military refer to their various plans or proposed schedules of training, logistical supply and deployment of combat units as a program. When I had first analyzed the Air Force planning problem and saw that it could be formulated as a system of linear inequalities, I called my first paper Programming in a Linear Structure. Note that the term `program' was used for linear programs long before it was used as the set of instructions used by a computer to solve problems. In the early days, these instructions were called codes.

In the summer of 1948, Koopmans and I visited the Rand Corporation. One day we took a stroll along the Santa Monica beach. Koopmans said: ``Why not shorten `Programming in a Linear Structure' to `Linear Programming'?'' I replied: ``That's it! From now on that will be its name.'' Later that day I gave a talk at Rand, entitled `Linear Programming'; years later Tucker shortened it to Linear Program.

The term Mathematical Programming is due to Robert Dorfman of Harvard, who felt as early as 1949 that the term Linear Programming was too restrictive.

The term simplex method arose out of a discussion with T. Motzkin who felt that the approach that I was using, when viewed in the geometry of the columns, was best described as a movement from one simplex to a neighboring one. Mathematical programming is also responsible for many terms which are now standard in mathematical literature, terms like Arg Min, Arg Max, Lexico-Max, Lexico-Min. The term dual is an old mathematical term. But suprisingly the term primal is new and was proposed by my father Tobias Dantzig around 1954 after William Orchard-Hays stated the need for a word to call the original problem whose dual was such and such.''

Apesar de, em termos teóricos, o algoritmo simplex (algoritmo simplex = método simplex + mecanismo que force a convergência) não ser um algoritmo eficiente, já que o número de operações executadas pelo algoritmo no pior caso é exponencial no número de digitos do problema, na prática o desempenho do algoritmo é muito bom e isto foi decisivo no sucesso da programação linear.

Em 1979 L.G. Khachiyan mostrou que um método de otimização não-linear devido a N.Z. Shor, D.B. Yudin e A.S. Nemirovskii, que não era amplamente conhecido, podia ser adaptado para resolver problemas de programação linear em tempo polinomial. Este método ficou conhecido como método dos elipsóides.

Mais recentemente, em 1984, N. Karmarkar desenvolveu um novo algoritmo polinomial para resolver problemas de programação linear. Nasciam assim os chamados métodos de pontos interiores.

Observação. O que foi brevemente tratado nesta introdução foi extraído de [4], dos prefácios de [5] e de [6], das notas históricas em [13] e de [10].

Aviso-propaganda. No próximo semestre a professora Cristina Gomes Fernandes oferecerá a disciplina Algoritmos de Aproximação. Os assuntos que estudaremos em Programação Linear, principalmente o conceito dualidade, serão utilizado repetidas vezes na disciplina Algoritmos de Aproximação.

Esta disciplina apresenta um visão introdutória de programacao linear, uma técnica quantitativa comumente utilizada para ajudar em tomada de decisões e planejamento. Os objetivos principais desta disciplina sao:

a)

transformar o estudante em um usuário de técnicas de programação linear;

b)

apresentar algoritmos programacao linear, em particular o Simplex, e dar uma visão geral da teoria por detras dos algoritmos comumente utilizados para a solução de problemas de programação linear.

A ênfase nesta disciplina é em algoritmos e teoria, entretanto, é de particular importância que você entenda como programação linear pode ser aplicada em problemas do `mundo real' e que você esteja ciente de suas limitações.

Esta é uma primeira disciplina em otimização, disciplinas que podem seguir-se a esta são: Otimização Combinatória; Métodos de Otimização em Finanças; e Programação Não-Linear.