Exemplo de utilização de 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 brinquedo 1 gera $10 de lucro, o 2 gera $8, o 3 gera $9 e o 4 gera $7. A função que determina o lucro da empresa é:

${\displaystyle Z=10x_{1}+8x_{2}+9x_{3}+7x_{4}}$

Assumindo que as variáveis são a quantidade de cada brinquedo que é vendida.

Esta é uma função linear, pois cada um dos termos da equação que a forma é uma constante ou um produto entre uma constante e um valor variável. Suponha agora que nós estamos interessados em descobrir qual é o maior lucro possível para esta empresa assumindo que o número máximo de vendas do brinquedo 1 é 100, do brinquedo 2 é 60, do brinquedo 3 é 40 e do brinquedo 4 é 70. Podemos então expressar este problema da seguinte forma:

Máx ${\displaystyle Z=10x_{1}+8x_{2}+9x_{3}+7x_{4}}$ (Função Objetivo)

${\displaystyle 1x_{1}+0x_{2}+0x_{3}+0x_{4}\leq 100}$ (Restrição 1)

${\displaystyle 0x_{1}+1x_{2}+0x_{3}+0x_{4}\leq 60}$ (Restrição 2)

${\displaystyle 0x_{1}+0x_{2}+1x_{3}+0x_{4}\leq 40}$ (Restrição 3)

${\displaystyle 0x_{1}+0x_{2}+0x_{3}+1x_{4}\leq 70}$ (Restrição 4)

${\displaystyle x_{1},x_{2},x_{3},x_{4}\geq 0}$ (As variáveis de decisão são não-negativas)

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 menor valor possível em uma função linear cujas variáveis possuem restrições.

Assim, o problema geral de programação linear pode ser definido por:

Maximizar (ou minimizar) a função objetivo:

${\displaystyle Z=c_{1}\cdot x_{1}+c_{2}\cdot x_{2}+...+c_{n}\cdot x_{n}\,\!}$

sujeita às restrições:

${\displaystyle a_{11}\cdot x_{1}+a_{12}\cdot x_{2}+...+a_{1n}\cdot x_{n}\leq b_{1}\,\!}$
${\displaystyle a_{21}\cdot x_{1}+a_{22}\cdot x_{2}+...+a_{2n}\cdot x_{n}\leq b_{2}\,\!}$
${\displaystyle a_{31}\cdot x_{1}+a_{32}\cdot x_{2}+...+a_{3n}\cdot x_{n}\leq b_{3}\,\!}$
a
${\displaystyle a_{m1}\cdot x_{1}+a_{m2}\cdot x_{2}+...+a_{mn}\cdot x_{n}\leq b_{m}\,\!}$

considerando que todas as variáveis de decisão assumem valores positivos:

 ${\displaystyle x_{1},x_{2},x_{n}\geq 0\,\!}$