Programação linear

PROGRAMAÇÃO LINEAR

Para Shamblin e Stevens Jr (1979, p. 263), a programação linear é: “um meio matemático de designar um montante fixo de recursos que satisfaça certa demanda de tal modo que alguma função-objetivo seja otimizada e ainda se satisfaça a outras condições definidas”. Segundo Lachtermacer (2004, p.27) falamos que um problema de programação linear está em sua forma padrão se “tivermos uma Maximização da função-objetivo e se todas as restrições forem do tipo menor ou igual, bem como os termos constantes e variáveis de decisão não-negativos”. De forma matemática podemos representar um problema padrão por:

Maximizar: Z = c 1x1 + c 2x2 + ... + c nxn Sujeito a: a11 x1 + a 12 x2 + ... + a 1n xn ≤ b 1 a21 x1 + a 22 x2 + ... + a 2n xn ≤ b 2 . . . . . . am1 x1 + a m2 x2 + ... + a mn xn ≤ b m x1, x 2, ..., x n ≥ 0 Ou na forma reduzida:

∑ =

=

n

j

jj cxZ 1

SEGeT – Simpósio de Excelência em Gestão e Tecnologia

5

Sujeito a:

∑ =

≤=

n

j

jiij im xba

1

,...,)1,2(

x1, x 2, ..., xn ≥ 0

Shamblin e Stevens Jr (1979, p. 263) afirmam que “é possível expressar matematicamente tanto o objetivo como as restrições. Como o próprio nome da técnica sugere, estas relações devem ser todas lineares”. Para eles, a programação linear, é de forma resumida, a aplicação da álgebra matricial para resolver estas equações usando algumas regras especiais que garantem que a solução seja satisfatória à todas as condições necessárias e ainda, trazer os melhores resultados com relação ao objetivo. Lachtermacer (2004, p.28-36) diz haver outra forma de calcular um problema de programação linear que não seja pela forma algébrica. Este outro modo é a forma gráfica. Neste trabalho não será mostrado a forma gráfica, mas fica a observação que existe esta possibilidade. Para melhor se entender a formação algébrica da formulação do problema. Observe um exemplo hipotético de Montevechi: Uma fábrica produz dois tipos de brinquedos de madeira: soldados e trens. Um soldado é vendido por $27 e usa $10 de matéria prima. Cada soldado que é fabricado tem um custo adicional de $14 relativo à mão de obra. Um trem é vendido por $21 e gasta $9 de matéria prima. O custo de mão de obra adicional para cada trem é de $10. A fabricação destes brinquedos requer dois tipos de mão de obra: carpintaria e acabamento. Um soldado necessita de 2 horas para acabamento e 1 hora de carpintaria. Um trem necessita de 1hora para acabamento e 1 hora de carpintaria. Cada semana, a fábrica pode obter qualquer quantidade de matéria prima, mas tem a disposição até 100 horas de acabamento e 80 de carpintaria. A demanda por trens é ilimitada, mas a venda de soldados é de no máximo 40 por semana. A fábrica quer maximizar seu lucro diário (receitas-custo). Com estes dados, será formulado o modelo matemático que poderá auxiliar na maximização do lucro semanal. Montevechi (2006, p. 21- 25), nos ajuda a esclarecer este exemplo. Primeiramente devemos levantar a questão problemas, que é “quantos soldados e trens devem ser feitos na semana?”. Para esclarecer ainda mais, deve-se representar as variáveis de decisão. Neste caso, o número de soldados produzidos e o número de trens produzidos. Veja: X1

...