Programação linear
Universidade de Coimbra Professor João Soares
Optimização Linear 60 páginas 16 de Março de 2007
Optimização Linear
Optimização Linear dada função linear diz respeito ao problema de encontrar um vector
n-dimensional x que
satisfaz um dado sistema de desigualdades
Ax ≤ b
e que torna máximo o valor de uma
cx.
Este é um problema matemático que ocorre numa grande variedade
de situações práticas que ocorrem em gestão e planeamento de operações, em investigação operacional e em ciências de computação. O mais célebre algoritmo que o resolve é o
método simplex ,
concebido por G. Dantzig Em termos geométricos, o
no nal da década de 40 do século passado (Dantzig, 1951).
método simplex consiste em percorrer os vértices do poliedro
{x : Ax ≤ b},
ao longo
das arestas que os ligam, até que seja encontrado o vértice óptimo. O método simplex funciona muito bem na prática. Contudo, ainda não se provou que existe um percurso
nesse poliedro que visita, no pior dos casos, um número polinomial de vértices. A questão de saber se existe um algoritmo que em tempo polinomial resolva qualquer problema de optimização linear foi primeiro resolvida por L. Khachiyan (Ha£ijan, 1979). Este investigador propôs uma variante do método elipsóide da optimização não linear que funcionava em tempo polinomial com problemas de optimização linear. A consequência desse resultado extravasou as fronteiras da optimização linear e teve repercussão na complexidade computacional de problemas de optimização combinatória (Grötschel 1993).
et al.,
No entanto, o método veio a revelar-se muito lento na resolução de problemas
práticos. Em 1984, N. Karmarkar publicou um artigo revolucionário no qual ele propõe um método de pontos interiores (da optimização não linear) que não só funcionava em tempo polinomial como conseguia ser mais rápido do que as melhores implementações do método simplex em alguns problemas particularmente