PROGRAMAÇÃO LINEAR

PROGRAMAÇÃO LINEAR

RESUMO

Este artigo tem o objetivo de abordar as principais ideias sobre a programação linear: Importancia da Programação Linear, Historia e conceito da Programação Linear.

Palavras-chave: Programação Linear.

1 INTRODUÇÃO

A programação linear é de muita importância, pois com muitas aplicações e em parte, da existência de boas propostas gerais para descobrir soluções. A programação linear é útil para guiar decisões relativas negócios, empresas de engenharia industrial, software e resoluções de vários problemas do mundo atual.

2 HISTÓRIA E CONCEITO 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 70postos 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 daregiã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 de problemas de otimização funcionam resolvendo problemas de programação linear como subproblemas. Historicamente, ideias da programação linear inspiraram muitosdos conceitos centrais da teoria da otimização, tais como dualidade, decomposição, e a importância da convexidade e suas generalizações. Da mesma forma, a programação linear é muito utilizada em microeconomia e em gestão empresarial, como em planejamento, produção, transporte, tecnologia e outras questões. Embora as questões de gestão modernas estão sempre mudando, a maioria das empresas gostaria de maximizar os lucros ou minimizar os custos com recursos limitados. Portanto, muitas questões podem ser caracterizadas como problemas de programação linear.

Matemáticos envolvidos: Jean Baptiste Joseph Fourier, Leonid Vitaliyevich Kantorovich, George Bernard Dantzig, Narendra K. Karmarkar.

2.1 EXEMPLO

Aqui está um exemplo de problema de programação linear. Suponha que um fazendeiro tem um pedaço de terra de digamos,