O que é Programação Linear?

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

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

Comentários

Postagens mais visitadas deste blog

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 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 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 ...

Método Gráfico (parte 2) - Exemplo

Solução através do método gráfico o seguinte problema: Maximizar Z = f(x,y) = 3x + 2y sujeita às restrições: 2x + y ≤ 18 2x + 3y ≤ 42 3x + y ≤ 24 x ≥ 0 , y ≥ 0 1.Inicialmente, o sistema de coordenadas da associação de um eixo com variável "X" e o outro o "Y" é desenhado (geralmente associa-se "x" em relação ao eixo horizontal e o "y" ao vertical), como pode ser visto na figura. 2.Nestes eixos, marca-se uma escala numérica apropriada aos valores que podem assumir as variáveis conforme as restrições do problema. Para isto, em cada restrição anulam-se todas as variáveis, exceto aquelas que correspondem a um eixo concreto, estabelecendo o valor adequado para este eixo. Este processo é repetido para cada um dos eixos. 3.As restrições são representadas a seguir. Primeiramente, desenha-se a reta que é obtida ao considerar a restrição como uma igualdade. Ela é representada como o segmento que une A com B e região que delimita esta ...

Matrizes

Matrizes são organizações de informações numéricas em uma tabela retangular formada por linhas e colunas. Essa organização em uma tabela facilita que se possa efetuar vários cálculos simultâneos com as informações contidas na matriz. Definição de matrizes Toda matriz tem o formato m x n (leia-se: m por n, com n e m ∈ N*), onde m é o número de linhas e n o número de colunas. Representação de matrizes Existem diversas maneiras de representarmos matrizes, veja quais são: Colchetes: [ ] Parênteses: ( ) Barras Simples: | | Barras Duplas: || || Essas são as representações mais comuns que encontramos na literatura. Exemplos: Elementos de uma matriz Seja a matriz genérica Amxn, isto é, m representa as linas e n o número de colunas. Então, temos: Elementos de uma matriz Seja a matriz genérica Amxn, isto é, m representa as linas e n o número de colunas. Então, temos: Dessa forma, os elementos da matriz A são indicados por aij, onde o i representa o índice da linha e j...

PROGRAMAÇÃO LINEAR

Pesquisar este blog