Programação linear

Programação linear

Origem: Wikipédia, a enciclopédia livre.

Exemplo de poliedro (bidimensional) resultante das condições de um problema de 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 todaslineares.

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 de programação linear, 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.

Aqui está um exemplo de problema de programação linear. Suponha que um fazendeiro tem um pedaço de terra de digamos, A km2, para ser semeado com trigo ou cevada ou uma combinação de ambas. O fazendeiro tem uma quantidade limitada de fertilizante F permitido e de inseticida Ppermitido que podem ser usados, cada um deles sendo necessários em quantidades diferentes por unidade de área para o trigo (F1, P1) e para a cevada (F2, P2). Seja S1 o preço de venda do trigo, e S2 o da cevada. Se chamarmos a área plantada com trigo e cevada de x1 e x2respectivamente, então o número ideal de km2 de plantação com trigo vs. cevada pode ser expresso como um problema de programação linear:

maximize (maximize o lucro - esta é a "função objetivo")

sujeito a (limite da área total)

(limite do fertilizante)

(limite do insecticida)

(não se pode semear uma área negativa)