Programação linear

Páginas: 12 (2915 palavras) Publicado: 19 de outubro de 2011
4. MODELOS DE 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 antiaé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 quea 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, Johnvon 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á conhecidoAlgoritmo Simplex, tanto na teoria como na prática. 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. (ONLINE, 2011). Uma dastécnicas mais utilizadas na abordagem de problemas em pesquisa operacional é a programação linear. A simplicidade do modelo envolvido e a disponibilidade de uma técnica de solução programável em computador facilitam sua aplicação. As aplicações mais conhecidas são feitas em sistemas estruturados, como os de produção, finanças, controles de estoques etc.(DA SILVA, DA SILVA, GONÇALVES, e MUROLO, 1998).4.1 Conceitos

Solução Ilimitada (unbounded): É aquela em que a função objetivo pode crescer (caso da maximização) ou decrescer (caso da minimização) indefinidamente, atendendo todas as restrições do problema. Solução Ótima: Havendo solução possível e não havendo solução ilimitada, solução ótima é a solução possível que otimiza a função objetivo. Nesse caso, poderá haver uma ou infinitassoluções ótimas; isto é, havendo mais de uma solução ótima, haverá infinitas soluções ótimas. Solução Básica: Façamos n variáveis iguais a zero, sobrando m equações a m variáveis. Se esse sistema de m equações a m variáveis tiver solução, ela será chamada de Solução Básica. Haverá, assim, um máximo de Combinação de m+n, m a m, soluções básicas. Solução Básica Possível: Se na Solução Básica, todas as mvariáveis forem não negativas, teremos uma Solução Básica Possível. Variáveis Básicas: São as m variáveis que compõem a solução básica. Variáveis Não Básicas: São as n variáveis que não compõem a solução básica. Valem, obrigatoriamente, zero, por convenção. Solução Degenerada: Se na solução básica possível alguma variável básica valer zero, a solução básica é dita degenerada. Solução Impossível: Éaquela em que não há qualquer ponto que atenda ao conjunto de restrições. (ONLINE, 2011). Diante de um problema de PL quando os problemas práticos que se pretende resolver pode ser escrito de forma de maximização (ou minimização) de uma função objetivo linear, sujeita a um conjunto de restrições que podem ser expressos sob a forma de inequações ou equações lineares. Dentre as principais...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • Programação linear
  • Programação Linear
  • Programação Linear
  • Programação linear
  • Programação linear
  • Programação linear
  • programação linear
  • Programação linear

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!