Pesquisa operacional/Introdução à Programação Linear: diferenças entre revisões
| [edição não verificada] | [edição não verificada] |
Conteúdo apagado Conteúdo adicionado
Nova página: ==O que é Programação Linear?== Suponha que uma empresa produza quatro modelos diferentes de brinquedos. Cada um deles gera uma quantidade de lucro diferente ao ser vendida. O brin... |
|||
Linha 22:
O que temos acima é um modelo de Programação Linear. Ele é formado sempre por uma função linear (que é a função objetivo) e por um conjunto de ineqüações lineares (restrições do problema). No exemplo acima, desejamos obter o maior lucro possível (maior valor de Z). O objetivo da programação linear é justamente fornecer ferramentas para resolver o desafio de encontrar o maior ou o menos valor possível em uma função linear cujas variáveis possuem restrições.
==A História da Programação Linear==
O desenvolvimento de técnicas algébricas para se lidar com inequações lineares é algo bastante antigo. Durante o século XVIII, o matemático e físico Jean-Baptiste Joseph Fourier desenvolveu vários métodos inovadores para se resolver sistemas de ineqüações. Um dos principais algoritmos desenvolvido por Fourier foi o Método de Eliminação de Fourier–Motzkin.
Durante a Segunda Guerra Mundial, novas tecnologias bélicas levaram à criação de grupos acadêmicos com o objetivo de resolver problemas como o uso eficiente de radares, canhões anti-aéreos, escoltas navais, etc. O objetivo era sempre reduzir custos militares e buscar maximizar as baixas inimigas. Para resolver estes problemas, a Programação Linear mostrou-se extremamente útil. Os grupos acadêmicos que a utilizavam eram sempre mantidos secretos até o ano de 1947, após o término da guerra. Foi quando a Programação Linear passou a ser muito usada em empresas com o objetivo de reduzir despesas e maximizar lucros.
Também no ano de 1947, o matemático George Dantzig desenvolveu o '''Algoritmo Simplex''', a maneira mais eficiente conhecida de se resolver modelos de Programação Linear. No mesmo ano, John von Neumann desenvolveu a teoria da dualidade e Leonid Kantorovich foi a primeira pessoa a aplicar a Programação Linear à Economia.
Em 1979, Leonid Khachiyan desenvolveu um novo algoritmo para resolver modelos de programação linear: o Algoritmo Elipsóide. O seu algoritmo foi o primeiro criado que era capaz de resolver problemas em tempo polinomial. Apesar disso, era mais lento que o já conhecido Algoritmo Simplex, tanto na teoria como na prática.
Em 1984, surge mais um método de se resolver problemas de pesquisa operacional: o Algoritmo do Ponto Interior, criado por Narendra Karmarkar. Assim como o Algoritmo Elipsóide, ele era polinomial. A diferença é que ele era bem mais rápido e conseguia competir com o Algoritmo Simplex.
| |||