Programação linear: diferenças entre revisões

← Ver a alteração anterior Ver a alteração posterior →

Conteúdo apagado Conteúdo adicionado

Em linha

Revisão das 11h20min de 19 de setembro de 2005

Em Matemática, problemas de Programação Linear (PL) são problemas de otimização nos quais a função objetivo e as restrições são todas lineares.

Programação Linear é uma importante área da otimizaçã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 otimização funcionam resolvendo problemas de PL como sub-problemas. Historicamente, idéias da programação linear inspiraram muitos dos conceitos centrais de teoria da otimização, tais como dualidade, decomposição, e a importância da convexidade e suas generalizações.

Exemplo

Aqui está um exemplo de problema de programação linear. Suponha que um fazendeiro tem um pedaço de terra de digamos, A quilômetros quadrados, 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 ótimo de quilômetros quadrados de plantação com trigo vs cevada pode ser expresso como um problema de programação linear:

maximize $S_{1}x_{1}+S_{2}x_{2}$		(maximize o lucro - esta é a "função objetivo")
sujeito a	$x_{1}+x_{2}\leq A$	(limite da área total)
	$F_{1}x_{1}+F_{2}x_{2}\leq F$	(limite do fertilizante)
	$P_{1}x_{1}+P_{2}x_{2}\leq P$	(limite do inseticida)
	$x_{1}\geq 0,\,x_{2}\geq 0$	(não se pode semear uma área negativa)

Teoria

Geometricamente, as restrições lineares definem um poliedro convexo, que é chamado a região factível. Uma vez que a função objetivo é 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 da região factível.

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, a PL é dita infeasible.

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.

Fora estas duas condições patológicas (que são frequentemente ruled out by resource constraints integral to the problem being represented, como acima), o ótimo é sempre alcançado num vértice do poliedro. Entretanto, o ótimo nem sempre é único: é possivel 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 or uniformemente igual a zero).

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 objetivo até encontrar o máximo. Embora este algoritmo seja bastante eficiente na prática, e seja garantido de encontrar um ótimo 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étido 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 ellipsoid method da nonlinear optimization de Naum Shor, que é uma generalização do método da elipsóide da convex optimization 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 é desapontadora: geralmente, o método simplex é mais eficiente. Sua grande importância é que ele encoraja a pesquisa de interior point methods. 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.

Variáveis Inteiras

Se todas as variávies 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 ótima em um tempo razoável, muitos problemas de Programação Inteira são considerados NP-dificel. 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-dificel.

Quando somente algumas das variáveis são inteiras e outras contínuas, temos a "Programação Inteira Mista" (PIM).

Existem no entando algumas classes de problemas que podem ser resolvidos na otimalidade em tempo polinomial, estes têm uma estrutura matricial própria chamada Matrizes totalmente unimodular.

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 possivel se aplicar um algorithmo de geração de colunas

Veja também

Preço sombra

Formatos de arquivos

MPS

Referências

Alexander Schrijver: "Theory of Linear and Integer Programming". John Wiley and Sons. 1998.

Predefinição:Links Externos

@@ Linha 48: / Linha 48: @@
 ==Variáveis Inteiras ==
-Se todas as variávies do problema pertencenrem 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 ótima em um tempo razoável, muitos problemas de Programação Inteira são considerados [[NP-dificel]]. Se as variáveis forem binárias, ou seja, assumirem somente os valore 0 (zero) ou 1, temos um caso especial da PI, que também pode ser classificado como [[NP-dificel]].
+Se todas as variávies 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 ótima em um tempo razoável, muitos problemas de Programação Inteira são considerados [[NP-dificel]]. 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-dificel]].
-Quanto somente algumas das variáveis são inteiras e outras permanecendo contínuas, temos a "Programação Inteira Mista" (PIM).
+Quando somente algumas das variáveis são inteiras e outras contínuas, temos a "Programação Inteira Mista" (PIM).
-Existem no entando algumas classes de problemas que podem ser resolvidos na otimalidade em tempo polinomial, estes têm uma estrutural matricial própria chamada [[Matrizes totalmente unimodular]].
+Existem no entando algumas classes de problemas que podem ser resolvidos na otimalidade em tempo polinomial, estes têm uma estrutura matricial própria chamada [[Matrizes totalmente unimodular]].
-Alguns algorithmos aplicados com sucesso na PI são:
+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 possivel se aplicar um algorithmo de [[geração de colunas]]
-<!--
-In [[1984]], [[Narendra Karmarkar|N. Karmarkar]] proposed the [[projective method]]. This is the first algorithm performing well both in theory and in practice: Its worst-case complexity is polynomial and experiments on practical problems show that it is reasonably efficient compared to the simplex algorithm. Since then, many interior point methods have been proposed and analysed. A popular interior point method is the [[Mehrotra predictor-corrector method]], which performs very well in practice even though little is known about it theoretically.
-The current opinion is that the efficiency of good implementations of simplex-based methods and interior point methods is similar for routine applications of linear programming.
-LP solvers are in widespread use for optimization of various problems in industry, such as optimization of flow in transportation networks, many of which can be transformed into linear programming problems only with some difficulty.
--->
 ==Veja também==