Programação Linear

PROGRAMAÇÃO LINEAR

.

1. INTRODUÇÃO

Programação Linear é uma técnica de Otimização bastante utilizada na resolução de problemas quantitativos que tenham seus modelos representados por expressões lineares, sendo elas equações e/ou inequações. Pela sua simplicidade e a possibilidade de aplicação em uma considerável diversidade de problemas, tornou-se um recurso bastante difundido. Sem dúvida nenhuma a Programação Linear é uma das técnicas da Pesquisa Operacional das mais utilizadas em se tratando de problemas de otimização.

Os problemas de Programação Linear (PL) buscam a distribuição eficiente de recursos limitados para atender um determinado objetivo, em geral, maximizar lucros ou minimizar custos. Em se tratando de PL, esse objetivo é expresso através de uma função linear, denominada de "Função Objetivo".

É necessário também que se defina quais as atividades que consomem recursos e em que proporções os mesmos são consumidos. Essas informações são apresentadas em forma de equações as inequações lineares, uma para cada recurso. Ao conjunto dessas equações e/ou inequações, denomina-se "Restrições do Modelo".

Normalmente se tem inúmeras maneiras de distribuir os recursos escassos entre as diversas atividades em estudo, bastando para com isso que essas distribuições estejam coerentes com as restrições do modelo. No entanto, o que se busca, num problema PL é a função objetivo, isto é, a maximização do lucro ou a minimização dos custos. A essa solução dá-se o nome de solução ótima.

Assim, a Programação linear se incube de achar a solução ótima de um problema, uma vez definida o modelo linear, ou seja, a função objetivo e as restrições lineares.

2. HISTÓRIA DA PROGRAMAÇÃO LINEAR

O problema de resolver um sistema de inequações lineares remonta pelo menos a Fourier. A primeira programação linear foi desenvolvida por Leonid Kantorovich, um russo, em 1939. Leonid Kantorovich desenvolveu os primeiros problemas de programação linear em 1939 para uso durante a Segunda Guerra Mundial para planejar gastos e retornos, a fim de reduzir os custos para o exército e aumentar as perdas para o inimigo. O método foi mantido em segredo até 1947, quando George B. Dantzig (norte americano) publicou o método simplex e John von Neumann (húngaro) desenvolveu a teoria da dualidade como uma solução de otimização linear. Após a guerra, muitas indústrias encontraram o seu uso em seu planejamento diário.

O problema de programação linear foi exibido pela primeira vez para ser resolvido por Leonid Khachiyan (russo) em 1979, mas um maior avanço teórico e prático no campo veio em 1984, quando Narendra Karmarkar (indiano) introduziu um novo método projetivo para a solução de problemas de programação linear.

O exemplo original de Dantzig era encontrar a melhor atribuição de 70 pessoas para 70 postos de trabalho. O poder de computação necessária para testar todas as permutações de selecionar a melhor atribuição é grande, o número de configurações possíveis excede o número de partículas no universo observável. No entanto, é preciso apenas um momento para encontrar a melhor solução, colocando o problema como um programa linear e aplicar o algoritmo Simplex . A teoria por trás de programação linear reduz drasticamente o número de possíveis soluções ideais que devem ser verificados

O algoritmo simplex resolve problemas de programação linear construindo uma solução admissível no vértice do poliedro, e então percorre os vértices do poliedro que sucessivamente possuem valores mais altos da função objetivo até encontrar o máximo. Embora este algoritmo seja bastante eficiente na prática, e seja garantido de encontrar um ótimo global se certa condição para se evitar ciclos for assumido, ele é fraco no pior-caso: é possível construir um problema de programação linear prático para o qual o método simplex realiza uma quantidade exponencial de passos em relação ao tamanho do problema.

O primeiro algoritmo de programação linear em tempo polinomial no pior caso foi proposto por Leonid Khachiyan em 1979. Foi baseado no método do elipsoide da otimização não linear de Naum Shor, que é uma generalização do método da elipsoide de otimização convexa de Arkadi Nemirovski, uma dos ganhadores do John von Neumann Theory Prize 2003, e D. Yudin.

Entretanto, a desempenho prática do algoritmo de Khachiyan é desapontante: geralmente, o método simplex é mais eficiente. Sua grande importância é que ele encoraja a pesquisa dos métodos de pontos interiores. Ao contrário de algoritmo simplex, que apenas evolui ao longo de pontos na fronteira da região factível, métodos de ponto interior podem se mover pelo interior da região factível.

Em 1984, Narendra Karmarkar propôs seu método projetivo, que se tornou o primeiro algoritmo a apresentar um bom desempenho tanto na teoria como na prática: seu pior caso de complexidade é polinomial e os problemas práticos de experiência mostram que ele é razoavelmente eficiente em comparação com o algoritmo simplex.

Desde o método de Karmarkar, muitos outros métodos de pontos interiores têm sido propostos e analisados. Um método bastante popular é o Método Preditor-Corretor de Mehrotra, cuja atuação possui bom desempenho na prática, ainda que pouco se saiba sobre ele na teoria.

A opinião mais recente entre os estudiosos é que a eficiência das boas implementações dos métodos baseados em simplex e dos pontos interiores são similares para a aplicação de rotina no programa linear.

As soluções do programa linear estão em uso generalizado de otimização de diversos problemas na indústria, como a otimização de fluxo de transporte, que pode ser transformada em problemas de programação linear sem muitas dificuldades.

A programação linear é um campo importante de otimização, por diversas razões. Muitos problemas práticos em pesquisas operacionais podem ser expressos como problemas de programação linear. Certos casos especiais de programação linear, tais como network flow problems e multicommodity flow são considerados importantes o suficiente para ter gerado muita pesquisa em algoritmos especializados para a sua solução. Uma série de algoritmos para outros tipos