Programação Linear: Maximização de Lucros

Prévia do material em texto

Programação linear (PL)
✓ A programação linear (PL) é uma das técnicas da PO
mais utilizadas em se tratando de problemas de
otimização.
✓ Os problemas de PL buscam a distribuição eficiente de
recursos limitados para atender um determinado
objetivo, em geral, maximizar lucros ou minimizar
custos.
Programação linear (PL)
✓ É necessário que se definam quais as atividades que 
consomem recursos e em proporções que os mesmos 
são consumidos. (Restrições do modelo)
✓ Busca-se num problema de PL a solução ótima. 
(Função objetivo)
Programação linear (PL)
Obtenção da função objetivo – Ex0 ClaretKids
• ClaretKids entrega 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 de
carpintaria. Um trem necessita de 1 hora para acabamento e 1 hora de
carpintaria. Cada semana, ClaretKids 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. ClaretKids quer maximizar seu lucro diário (receitas-custo).
Formular o modelo matemático que poderá ser usado por ClaretKids para
maximizar seu lucro semanal.
Definindo o objetivo
Sabendo que a matéria prima necessária é obtida sem
problemas, ClaretKids tem como objetivo maximizar
o lucro semanal (receitas - custos).
Vamos então formular matematicamente a situação de
ClaretKids com o objetivo de maximizar o lucro semanal.
Variáveis de decisão
Em qualquer modelo de PL, as variáveis de decisão
devem descrever completamente as decisões a serem
feitas.
Caso de ClaretKids: quantos soldados e trens devem ser
feitos e entregues na semana?
Variáveis de decisão
X1 = número de soldados produzidos cada semana;
X2 = número de trens produzidos a cada semana
Segundo ponto – Função objetivo
Em qualquer modelo de PL, o decisor quer maximizar ou
minimizar alguma função das variáveis de decisão.
Caso da ClaretKids: custos fixos (aluguel, seguro) não
depende dos valores de X1 e X2, assim ele pode se
concentrar em maximizar e entregar a venda da semana.
Função objetivo
Receitas e custos: podem ser expressos em termos
das variáveis X1 e X2.
Receita da semana = receita dos soldados + receita dos
trens.
Função objetivo
Receita da semana = $soldado x soldado/semana +
$/trem * trem/semana
Receita por semana = 27 * X1 + 21 * X2
Também podemos escrever
Custos de MP = 10*X1 + 9*X2
Custos de MO = 14*X1 + 10*X2
Então ClaretKids que maximizar
(27X1 + 21X2) – (10X1 + 9X2) – (14X1 + 10X2) = 3X1 + 2X2
Assim o objetivo da ClaretKids é escolher X1 e X2 
para maximizar 3X1 + 2X2
Função objetivo
Maximizar Z = 3X1 + 2X2
Ou 
Max Z = 3X1 + 2X2
Variável usualmente 
utilizada
Restrições
Se X1e X2 aumentam, a função objetivo de ClaretKids 
será sempre maior. Mas infelizmente X1 e X2 são 
limitados pelas seguintes restrições:
1. Cada semana, não mais que 100 horas de 
acabamento;
2. Cada semana, não mais que 80 horas de 
carpintaria;
3. Limitação de demanda, não mais de 40 soldados 
por semana
Restrições
MP ilimitada, portanto não há restrições.
Próximo passo: é necessário expressar as restrições 1, 2 
e 3, em termo das variáveis de decisão: X1 e X2.
Restrição 1
Não mais de 100 h de acabamento
Restrição 1: 2X1 + X2 ≤ 100
Total de h de acab./semana = horas de aca./sold. * sold. 
feitos/semana + horas de acab./trem * trens feitos/semana
Total de h de acab./semana = 2X1 + 1X2
Restrição 2
Não mais de 80 h de carpintaria
Restrição 2: X1 + X2 ≤ 80
Total de h de carp./semana = horas de carp../sold. * sold. 
feitos/semana + horas de carp../trem * trens feitos/semana
Total de h de carp../semana = 1X1 + 1X2
Restrição 3
Máximo de 40 soldados
Restrição 3: X1 ≤ 40
Venda máxima de soldados: 40
Conjunto das restrições
1. 2x1 + X2 ≤ 100
2. X1 + X2 ≤ 80
3. X1 ≤ 40 }
Restrições 
para o 
problema 
de PL de 
ClaretKids
X1 e X2 são os coeficientes tecnológicos: Refletem a quantia 
usada para diferentes produtos.
Usualmente representam a quantidade de recursos 
disponíveis
Restrições adicionais
✓ X1 ≥ 0
✓ X2 ≥ 0
Para completar a formulação do problema:
Resumindo
Max Z = 3X1 + 2X2
Sujeito a:
2X1 + X2 ≤100
X1 + X2 ≤ 80
X1 ≤ 40
X1 ≥ 0
X2 ≥ 0
Para completar a formulação do problema:
Significa que X1 e X2 
precisam satisfazer todas as 
restrições 
Resumindo
✓Todos os termos X são de expoente 1 e as restrições 
são equações lineares; 
✓ O problema de ClaretKids é típico de muitos 
outros, onde precisa-se maximizar lucros sujeitos a 
recursos limitados.
Exemplo 1 PPL
• Dona Maria possui uma confecção que produz apenas dois
tipos de roupas: calças e camisetas. A calça é vendida a
R$40,00 e na sua fabricação, são gastos R$15,00 em tecido
(matéria prima). Já a camiseta é vendida a R$22,00 e o gasto
com tecido é de R$8,00.
• Dona Maria também já calculou o custo relativo a mão de
obra . Para a calça o gasto é de R$12,00 e para a camiseta,
de R$10,00.
Exemplo 1 PPL
• Outra informação importante é que as roupas precisam de
mão de obra especializada. Ambas passam inicialmente por
costureiras que cortam os tecidos (que vamos chamar de
corte) e posteriormente por outras que fazem a costura e
dão o acabamento (que vamos chamar de acabamento).
• Para confeccionar a calça é preciso de 2h de corte e 1h de
acabamento, enquanto que para a camiseta é preciso 1h de
corte e 1h de acabamento.
• A disponibilidade do corte é de 80h por semana. O
acabamento dispõe apenas de 60h.
Exemplo 1 PPL
•A confecção da Dona Maria é muito próxima de
uma grande loja de tecidos, por isso a matéria
prima não é problema para ela.
•Finalmente, por ser um pouco mais cara, a calça
tem uma demanda limitada a 50 peças por semana.
Já a camiseta não tem limite de demanda.
•Como Dona Maria deveria balancear sua
confecção?
Exemplo 1 PPL
• Resolução:
• 1. Variáveis de decisão:
• Quais são as incógnitas do meu problema?
• O que Dona Maria precisa saber ao final desse exercício?
X1: QUANTIDADE DE CALÇAS PRODUZIDAS SEMANALMENTE
X2: QUANTIDADE DE CAMISETAS PRODUZIDAS
SEMANALMENTE
Exemplo 1 PPL
• Resolução:
• 2. Função objetivo
• É a equação matemática que vai modelar nossa busca
• Numa programação linear, nós sempre buscaremos
minimizar ou maximizar essa equação.
• Nesse caso o que queremos ? O maior lucro? Menor custo
de mão de obra? Neste caso o maior lucro.
• Assim inicialmente, temos:
• L=40X1+22X2
• Mas e os gastos?
Exemplo 1 PPL
• Os gastos são:
• Matéria-Prima: 15x1+8x2
• Mão de obra: 12x1+10x2
Assim o lucro é:
L=40x1+22x2-(15x1+8x2)-(12x1+10x2)
L=13x1+4x2
Nós queremos o máximo ou mínimo lucro?
Então a função objetivo é:
Max L= 13x1+4x2
Exemplo 1 PPL
• Resolução:
• 3. Restrições:
• Em geral, qualquer processo possui limitações, que podem
ser a quantidade matérias primas, as horas de produção, a
quantidade absorvida pelo mercado, etc.
• No nosso exemplo, também temos limitações que
precisamos definir matematicamente, que são:
Exemplo 1 PPL
• Resolução:
• 3. Restrições:
• Dispomos apenas de 80h de corte por semana
• Dispomos apenas de 60h de acabamento por semana
• Por mais que produzimos calças, conseguiremos vender
apenas 50 delas a cada semana.
Exemplo 1 PPL
• Resolução:
• 3. Restrições:
• Vejamos como ficaria a restrição 1, que é o tempo de corte:
• A quantidade de calças produzidas (x1) vezes o tempo de corte
utilizado para produzir cada calça (2h), somado à quantidade de
camisetas produzidas (x2) vezes o tempo utilizado para produzir
cada camiseta (1h) deve ser menor que o tempo total disponível
pelo corte(80h) ou seja:
• 2x1+1x2<=80
Exemplo 1 PPL
• Usamos o mesmo raciocínio para a restrição 2, que é o
tempo de acabamento, teremos:
• A quantidade de calças produzidas (x1) vezes o tempo de
acabamento utilizado para produzir cada calça (1h), somado
a quantidade de camisetas produzidas (x2) vezes o tempo
utilizado para produzir cada camiseta (1h) deve ser menor
que o tempo total disponível pelo acabamento (60h), ou
seja:
• X1+X2<=60.
Exemplo 1 PPL
• E para a restrição 3, que é a demanda de calças, não
podemos permitir que a quantidade de calças produzidas
(x1) seja maior que o que será vendido (50 peças), temos:
• X1<=50
• Finalmente, para que esse processo seja real, não podemos
permitir uma produção negativa, então
• X1>=0 e x2>=0
• Essa restrição adicional sempre deve ser colocada nos
modelos.
Exemplo 1 PPL
• As restrições então são:
• Corte: 2x1 + x2 <=80
• Acabamento: x1 + x2 <=60
• Demanda: x1<=50
• X1>=0
• X2>=0
Exemplo 1 PPL
• Resumo:
• Max L: 13x1 + 4x2
• Sujeito a:
• 2x1 + x2 <=80
• x1 + x2 <=60
• x1<=50
• X1>=0
• X2>=0
Exemplo 2 PPL
Exemplo 2 PPL