Programação linear

19111 palavras 77 páginas
Teoria de Optimização
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

Relacionados

  • PROGRAMAÇÃO LINEAR
    1772 palavras | 8 páginas
  • programaçao linear
    1223 palavras | 5 páginas
  • Programação linear
    1067 palavras | 5 páginas
  • Programação Linear
    1444 palavras | 6 páginas
  • Programaçaõ linear
    1154 palavras | 5 páginas
  • programação linear
    3048 palavras | 13 páginas
  • Programação linear
    2233 palavras | 9 páginas
  • Programação Linear
    579 palavras | 3 páginas
  • Programação linear
    1398 palavras | 6 páginas
  • Programacao linear
    2976 palavras | 12 páginas