Baixe o app para aproveitar ainda mais
Prévia do material em texto
Programação linear A programação linear consiste em uma das mais importantes técnicas de otimização pertencentes à pesquisa operacional. Muitos problemas de otimização estão sujeitos a restrições tais como limitações de investimentos, mão de obra, matéria-prima, entre outras. Matematicamente essas restrições, bem como a função objetivo podem ser lineares ou não lineares. A programação linear, como a própria nomenclatura diz, tem como objetivo abordar problemas de otimização dotados de uma função objetivo linear e de restrições também lineares. Mas o que é uma restrição ou uma função objetivo linear? Uma função objetivo ou uma restrição são ditas lineares quando cada aumento de uma unidade em uma das variáveis do problema corresponde a um aumento constante por unidade no recurso associado a essa variável. Graficamente, uma expressão linear com duas variáveis é representada por uma reta. No caso de três variáveis, a representação gráfica é um plano. Para quatro ou mais variáveis temos hiperplanos, mas que infelizmente não podem ser representados graficamente. No entanto, independente do número de variáveis do problema, as características lineares são preservadas. Para ilustrarmos a característica linear de um problema, vamos imaginar a seguinte situação: em um determinado supermercado, uma caixa de leite custa R$ 2,00. Nesse caso, duas caixas custam R$ 4,00, três caixas custam R$ 6,00 e assim por diante, ou seja, a cada aumento de uma unidade na quantidade de caixas de leite, temos um aumento de R$ 2,00 no preço total. Como o aumento é constante, independente do número de caixas de leite, a relação entre quantidade de caixas de leite e o preço total é dita linear. A forma geral de um problema de programação linear é 1 1 2 2 11 1 12 2 1 1 21 1 22 2 2 2 1 1 2 2 1 2 max ... . . ... ... ... , 0, 0,..., 0 n n n n n n m m mn n m n z c x c x c x s a a x a x a x b a x a x a x b a x a x a x b x x x Onde: Os termos ija , ib e jc são números que descrevem o problema; As variáveis jx são escolhidas de forma que as restrições sejam satisfeitas e a função objetivo otimizada; O termo “s.a.” significa “sujeito à”. Essa forma geral tem alguns elementos característicos que sempre aparecerão nos problemas de PL: A função objetivo pode ser escrita nas duas formas que apresentamos a seguir: 1. se o problema for maximizar z: 1 1 2 2max ... n nz c x c x c x 2. se o problema for minimizar z: 1 1 2 2min ... n nz c x c x c x Em ambos os casos, onde 1 2, ,..., nc c c são números reais e 1 2, ,..., nx x x são as variáveis do problema. Nos problemas de PL, além da função objetivo, que consiste em uma expressão matemática que representa a meta a ser alcançada, temos também as restrições. Para você entender melhor, pode imaginar uma indústria de laticínios que deseja otimizar (maximizando) a sua produção. Nesse caso, as limitações de ordem prática encontradas para fazer a otimização da produção (função objetivo) serão as restrições do problema em PL. Entre outras: quantidade disponível de matéria-prima; capacidade do setor produtivo; mão de obra; limitações no preço. Em outros problemas de PL podem existir diferentes limitações, tais como limitações de localidade ou de espaço físico, distância entre localizações, além de outras. Nesse contexto, podemos encontrar, por exemplo: um agricultor que deseja plantar diversas culturas, no entanto ele tem um limite de espaço a ser cultivado, ou seja, uma restrição espacial; um investidor que deseja diversificar suas aplicações, mas ele possui apenas certa quantia a ser aplicada, portanto possui uma restrição de capital; uma transportadora que tem como objetivo otimizar as entregas, contudo ela deve considerar o fato de contar com um determinado número de veículos, o que significa uma restrição de quantidade disponível (de veículos). No cenário das restrições, encontramos as restrições de igualdade ou as de desigualdade. Veja como são representadas nas equações a seguir. 11 1 12 2 1 1... n na x a x a x b 11 1 12 2 1 1... n na x a x a x b ou 11 1 12 2 1 1... n na x a x a x b Tanto a função objetivo quanto as restrições são facilmente encontradas a partir de uma análise cuidadosa do problema de PL a ser formulado.
Compartilhar