Programação linear – Wikipédia a enciclopédia livre

Prévia do material em texto

Exemplo de poliedro (bidimensional)
resultante das condições de um problema
de programação linear.
Programação linear
Origem: Wikipédia, a enciclopédia livre.
Em matemática, problemas de Programação Linear (PL) são
problemas de optimizaçã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 importantes o 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ância da convexidade e suas generalizações.
Índice
1 Exemplo
2 Teoria
3 Algoritmos
4 Variáveis inteiras
5 Ver também
6 Bibliografia
7 Ligações externas
Exemplo
Aqui está um exemplo de problema de programação linear. Suponha que um fazendeiro tem um pedaço de
terra de digamos, A km , para ser semeado com trigo ou cevada ou uma combinação de ambas. O fazendeiro
tem uma quantidade limitada de fertilizante F permitido e de inseticida P permitido que podem ser usados, cada
um deles sendo necessários em quantidades diferentes por unidade de área para o trigo (F , P ) e para a
cevada (F , P ). Seja S o preço de venda do trigo, e S o da cevada. Se chamarmos a área plantada com
trigo e cevada de x e x respectivamente, então o número ideal de km de plantação com trigo vs. cevada
pode ser expresso como um problema de programação linear:
maximize (maximize o lucro - esta é a "função objetivo")
sujeito a (limite da área total)
(limite do fertilizante)
2
1 1
2 2 1 2
1 2
2
(limite do insecticida)
(não se pode semear uma área negativa)
Teoria
Geometricamente, as restrições lineares definem um poliedro convexo, que é chamado de conjunto dos pontos
viáveis. Uma vez que a função objectivo é também linear, todo ótimo local é automaticamente um ótimo global.
A função objetivo ser linear também implica que uma solução ótima pode apenas ocorrer em um ponto da
fronteira do conjunto de pontos viáveis.
Existem duas situações nas quais uma solução ótima 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 ótima, já que
não pode haver solução nenhuma. Neste caso, o PL é dito inviável.
Alternativamente, o poliedro pode ser ilimitado na direção da função objetivo (por exemplo: maximizar x + 3
x sujeito a x ≥ 0, x ≥ 0, x + x ≥ 10), neste caso não existe solução ótima 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 uma constante).
Algoritmos
O algoritmo simplex resolve problemas de PL 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
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. Na verdade, por algum tempo não se soube se
problemas de programação linear eram NP-completos ou tinham solução em tempo polinomial.
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 elipsóide] da nonlinear optimization de Naum Shor, que é
uma generalização do método da elipsóide da [optimização convexa] de Arkadi Nemirovski, uma dos
ganhadores do John von Neumann Theory Prize 2003, e D. Yudin.
Entretanto, a performance 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 tornou-se o primeiro algoritmo a apresentar
um bom desempenho tanto na teoria como na prática: seu pior caso de complexidade é polimonial 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 propotos 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.
1
2 1 2 1 2
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 similiares 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.
Variáveis inteiras
Se todas as variáveis do problema pertencerem ao conjunto dos números inteiros, temos uma sub-classe da
Programação Linear chamada Programação Inteira (PI) ou programação linear inteira. Ao contrário da PL que
pode-se encontrar a solução óptima em um tempo razoável, muitos problemas de Programação Inteira são
considerados NP-difícil. Se as variáveis forem binárias, ou seja, assumirem somente os valores 0 (zero) ou 1,
temos um caso especial da PI, que também pode ser classificado como NP-difícil.
Quando somente algumas das variáveis são inteiras e outras contínuas, temos a "Programação Inteira Mista"
(PIM).
Existem no entanto algumas classes de problemas que podem ser resolvidos na perfeição em tempo polinomial,
estes têm uma estrutura matricial própria chamada Matrizes totalmente unimodulares.
Alguns algoritmos aplicados com sucesso na PI são:
branch and bound
branch and cut
branch and price
Se a estrutura do problema permitir é também possível se aplicar um algoritmo de geração de colunas
Ver também
Preço sombra
MPS, formatos de arquivos
Bibliografia
M.S. Bazaraa, J.J. Jarvis e H.D. Sherali. Linear Programming and Network Flows. Wiley, 1990.
D. Bertsimas e J.N. Tsitsiklis. Introduction to Linear Optimization. Athena Scientific, 1997.
V. Chvátal. Linear Programming. W.H. Freeman, 1983.
G.B. Dantzig. Linear Programming and Extensions. Princeton University, 1963.
A. Schrijver. Theory of Linear and Integer Programming. John Wiley and Sons, 1998.
SILVA, E. M. et al. Pesquisa operacional: programação linear. São Paulo: Atlas, 1999.
Ligações externas
Guidance on Formulating LP problems (http://people.brunel.ac.uk/~mastjjb/jeb/or/lp.html)
0-1 Integer Programming Benchmarks with Hidden Optimum Solutions
(http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/pb-benchmarks.htm)
A Tutorial on Integer Programming (http://mat.gsia.cmu.edu/orclass/integer/integer.html)
The linear programming FAQ (http://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html)Linear Program Solver (LiPS) (http://sourceforge.net/projects/lipside/) — Free easy-to-use program
intended for solving linear and integer programming problems.
HOPDM (http://www.maths.ed.ac.uk/~gondzio/software/hopdm.html)
Linear Programming - Simplex Applet (http://vinci.inesc.pt/lp/)
Obtida de "http://pt.wikipedia.org/w/index.php?title=Programação_linear&oldid=32775280"
Categoria: Optimização
Navigation menu
Esta página foi modificada pela última vez à(s) 03h25min de 29 de outubro de 2012.
Este texto é disponibilizado nos termos da licença Atribuição-Partilha nos Mesmos Termos 3.0 não
Adaptada (CC BY-SA 3.0); pode estar sujeito a condições adicionais. Consulte as condições de uso
para mais detalhes.