Programacao linear

Disponível somente no TrabalhosFeitos
  • Páginas : 12 (2976 palavras )
  • Download(s) : 0
  • Publicado : 10 de julho de 2012
Ler documento completo
Amostra do texto
Ìndice

Introdução 2
Programação linear 3
Algoritmos 4
Variáveis inteiras 5
Método Simplex 5
Algoritmo simplex 7
Procedimentos 7
Exemplo 8
Alguns Exercício resolvido com inequação 8
Conclusão 13
Bibliografia 14

Introdução
Com o presente tema em abordagem Programação Linear, iremos definir, trareremos tambem mais detalhes inerentes ao tema. É uma importante área daoptimização por várias razões. Muitos problemas práticos em pesquisa operacional podem ser expressos como problemas de programação linear. Certos casos especiais de programação linear, tais como problemas de network flow e problemas de multicommodity flow são considerados importantes o suficiente para que se tenha gerado muita pesquisa em algoritmos especializados para suas soluções. Vários algoritmospara outros tipos de problemas de optimização funcionam resolvendo problemas de PL como sub-problemas. Historicamente, ideias da programação linear inspiraram muitos dos conceitos centrais de teoria da optimização, tais como dualidade,  decomposição, e a importância daconvexidade e suas generalizações.

Programação linear
Em matemática, problemas de Programação Linear (PL) são problemasdeoptimização nos quais a função objetivo e as restrições são todas lineares.
Programação Linear é uma importante área da optimização por várias razões. Muitos problemas práticos em pesquisa operacional podem ser expressos como problemas de programação linear. Certos casos especiais de programação linear, tais como problemas de network flow e problemas de multicommodity flow são considerados importanteso suficiente para que se tenha gerado muita pesquisa em algoritmos especializados para suas soluções. Vários algoritmos para outros tipos de problemas de optimização funcionam resolvendo problemas de PL como sub-problemas. Historicamente, ideias da programação linear inspiraram muitos dos conceitos centrais de teoria da optimização, tais como dualidade,  decomposição, e a importânciadaconvexidade e suas generalizações.
Geometricamente, as restrições lineares definem um poliedro convexo, que é chamado de conjunto dos pontos viáveis. Uma vez que a função objectiva é também linear, todo óptimo local é automaticamente um óptimo global. A função objectivo ser linear também implica que uma solução óptima pode apenas ocorrer em um ponto da fronteira do conjunto de pontos viáveis.
Existem duassituações nas quais uma solução óptima não pode ser encontrada. Primeiro, se as restrições se contradizem (por exemplo, x ≥ 2 e x ≤ 1) logo, a região factível é vazia e não pode haver solução óptima, já que não pode haver solução nenhuma. Neste caso, o PL é dito inviável.
Alternativamente, o poliedro pode ser ilimitado na direcção da função objectivo (por exemplo: maximizar x1 + 3 x2 sujeitoa x1 ≥ 0, x2 ≥ 0,x1 + x2 ≥ 10), neste caso não existe solução óptima uma vez que soluções arbitrariamente grandes da função objetivo podem ser construídas, e o problema é dito ilimitado.
Fora estas duas condições patológicas (que são frequentemente eliminadas por limitações dos recursos inerentes ao problema que está sendo modelado, como acima), o óptimo é sempre alcançado num vértice do poliedro.Entretanto, o ótimo nem sempre é único: é possível ter um conjunto de soluções ótimas cobrindo uma aresta ou face do poliedro, ou até mesmo o poliedro todo (Esta última situação pode ocorrer se a função objetivo for uniformemente igual a zero).

Exemplo de poliedro (bidimensional) resultante das condições de um problema de programação linear.

Algoritmos
O algoritmo simplex resolve problemas dePL 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 objectivo até encontrar o máximo. Embora este algoritmo seja bastante eficiente na prática, e seja garantido de encontrar um óptimo global se certas condições para se evitar ciclos forem assumidas, ele é fraco no pior-caso: é possível...
tracking img