Programação Linear 03

Prévia do material em texto

ENP153 –Programação Linear
Aula 03 –Transformando um modelo padrão em genérico
DIMENSIONAMENTO DE LOTE
 Uma empresa de malha deve atender os seguintes compromissos para os
próximos seis meses:
 JAN: 4000 peças
 FEV: 2000 peças
 MAR: 5000 peças
 ABR: 1000 peças
 MAI: 4000 peças
 JUN: 2000 peças
 Ao final de dezembro do ano anterior, a empresa terminou com um estoque de 500
peças.
 Sabe-se que a empresa tem capacidade de produzir 3000 peças mensais e que,
realizando horas extras, pode produzir 600 peças a mais que sua capacidade
nominal.
 O custo de se produzir uma peça é de $3 por peça. Ao se produzir em horas extras,
acrescenta-se um custo de $0,4 por peça. Outro ponto a se saber é que o custo de
estoque da organização é de $0,25 por peça.
 Defina um modelo matemático que represente o problema acima, buscand0 a
minimização dos custos de produção.
 Sejam:
 𝐷𝑡 → 𝑎 𝑑𝑒𝑚𝑎𝑛𝑑𝑎 𝑑𝑒 𝑝𝑟𝑜𝑑𝑢𝑡𝑜𝑠 𝑛𝑜 𝑝𝑒𝑟í𝑜𝑑𝑜 𝑡
 𝑐𝑥 → 𝑐𝑢𝑠𝑡𝑜 𝑑𝑒 𝑢𝑚𝑎 𝑢𝑛𝑖𝑑𝑎𝑑𝑒 𝑑𝑒 𝑝𝑟𝑜𝑑𝑢𝑡𝑜 𝑒𝑚 ℎ𝑜𝑟𝑎 𝑛𝑜𝑟𝑚𝑎𝑙
 𝑐𝑦 → 𝑐𝑢𝑠𝑡𝑜 𝑑𝑒 𝑢𝑚𝑎 𝑢𝑛𝑖𝑑𝑎𝑑𝑒 𝑑𝑒 𝑝𝑟𝑜𝑑𝑢𝑡𝑜 𝑒𝑚 ℎ𝑜𝑟𝑎 𝑒𝑥𝑡𝑟𝑎
 𝑐𝑠 → 𝑐𝑢𝑠𝑡𝑜 𝑢𝑛𝑖𝑡á𝑟𝑖𝑜 𝑑𝑒 𝑒𝑠𝑡𝑜𝑞𝑢𝑒
 𝑃𝑚𝑎𝑥
𝑁 → 𝑝𝑟𝑜𝑑𝑢çã𝑜 𝑚á𝑥𝑖𝑚𝑎 𝑒𝑚 ℎ𝑜𝑟𝑎 𝑛𝑜𝑟𝑚𝑎𝑙
 𝑃𝑚𝑎𝑥
𝑒 → 𝑝𝑟𝑜𝑑𝑢çã𝑜 𝑚á𝑥𝑖𝑚𝑎 𝑒𝑚 ℎ𝑜𝑟𝑎 𝑒𝑥𝑡𝑟𝑎
 𝑇 → 𝑎 𝑞𝑢𝑎𝑛𝑡𝑖𝑑𝑎𝑑𝑒 𝑑𝑒 𝑝𝑒𝑟í𝑜𝑑𝑜𝑠 𝑒𝑥𝑖𝑠𝑡𝑒𝑛𝑡𝑒𝑠
 E também:
 𝑥𝑡 → 𝑎 𝑝𝑟𝑜𝑑𝑢çã𝑜 𝑒𝑚 ℎ𝑜𝑟𝑎 𝑛𝑜𝑟𝑚𝑎𝑙 𝑛𝑜 𝑝𝑒𝑟í𝑜𝑑𝑜 𝑡
 𝑦𝑡 → 𝑎 𝑝𝑟𝑜𝑑𝑢çã𝑜 𝑒𝑚 ℎ𝑜𝑟𝑎 𝑒𝑥𝑡𝑟𝑎 𝑛𝑜 𝑝𝑒𝑟í𝑜𝑑𝑜 𝑡
 𝑠𝑡 → 𝑜 𝑒𝑠𝑡𝑜𝑞𝑢𝑒 𝑑𝑒 𝑝𝑟𝑜𝑑𝑢𝑡𝑜𝑠 𝑎𝑜 𝑓𝑖𝑛𝑎𝑙 𝑑𝑜 𝑝𝑒𝑟í𝑜𝑑𝑜 𝑡
 Temos que o objetivo é
 Minimizar o custo de produção
𝜑 = min 𝑓 𝑥, 𝑦, 𝑠 = 𝑐𝑥𝑥1 + 𝑐
𝑦𝑦1 + 𝑐
𝑠𝑠1 + 𝑐
𝑥𝑥2 + 𝑐
𝑦𝑦2 + 𝑐
𝑠𝑠2 +⋯+ 𝑐
𝑥𝑥6 + 𝑐
𝑦𝑦6 + 𝑐
𝑠𝑠6
 Temos que o objetivo é
 Minimizar o custo de produção
𝜑 = min 𝑓 𝑥, 𝑦, 𝑠 = 𝑐𝑥𝑥1 + 𝑐
𝑦𝑦1 + 𝑐
𝑠𝑠1 + 𝑐
𝑥𝑥2 + 𝑐
𝑦𝑦2 + 𝑐
𝑠𝑠2 +⋯+ 𝑐
𝑥𝑥6 + 𝑐
𝑦𝑦6 + 𝑐
𝑠𝑠6
 Restrito à:
 Cumprimento das demandas periódicas (R1)
𝑥1 + 𝑦1 + 𝑠0 ≥ 𝐷1
𝑥2 + 𝑦2 + 𝑠1 ≥ 𝐷2
…
𝑥6 + 𝑦6 + 𝑠5 ≥ 𝐷6
 Temos que o objetivo é
 Minimizar o custo de produção
𝜑 = min 𝑓 𝑥, 𝑦, 𝑠 = 𝑐𝑥𝑥1 + 𝑐
𝑦𝑦1 + 𝑐
𝑠𝑠1 + 𝑐
𝑥𝑥2 + 𝑐
𝑦𝑦2 + 𝑐
𝑠𝑠2 +⋯+ 𝑐
𝑥𝑥6 + 𝑐
𝑦𝑦6 + 𝑐
𝑠𝑠6
 Restrito à:
 Cumprimento das demandas periódicas (R1)
𝑥1 + 𝑦1 + 𝑠0 ≥ 𝐷1
𝑥2 + 𝑦2 + 𝑠1 ≥ 𝐷2
…
𝑥6 + 𝑦6 + 𝑠5 ≥ 𝐷6
 Não extrapolação da produção normal máxima (R2)
𝑥1 ≤ 𝑃𝑚𝑎𝑥
𝑁 𝑥2 ≤ 𝑃𝑚𝑎𝑥
𝑁 … | 𝑥6 ≤ 𝑃𝑚𝑎𝑥
𝑁
 Temos que o objetivo é
 Minimizar o custo de produção
𝜑 = min 𝑓 𝑥, 𝑦, 𝑠 = 𝑐𝑥𝑥1 + 𝑐
𝑦𝑦1 + 𝑐
𝑠𝑠1 + 𝑐
𝑥𝑥2 + 𝑐
𝑦𝑦2 + 𝑐
𝑠𝑠2 +⋯+ 𝑐
𝑥𝑥6 + 𝑐
𝑦𝑦6 + 𝑐
𝑠𝑠6
 Restrito à:
 Cumprimento das demandas periódicas (R1)
𝑥1 + 𝑦1 + 𝑠0 ≥ 𝐷1
𝑥2 + 𝑦2 + 𝑠1 ≥ 𝐷2
…
𝑥6 + 𝑦6 + 𝑠5 ≥ 𝐷6
 Não extrapolação da produção normal máxima (R2)
𝑥1 ≤ 𝑃𝑚𝑎𝑥
𝑁 𝑥2 ≤ 𝑃𝑚𝑎𝑥
𝑁 … | 𝑥6 ≤ 𝑃𝑚𝑎𝑥
𝑁
 Não extrapolação da produção extra máxima (R3)
𝑦1 ≤ 𝑃𝑚𝑎𝑥
𝑒 𝑦2 ≤ 𝑃𝑚𝑎𝑥
𝑒 … | 𝑦6 ≤ 𝑃𝑚𝑎𝑥
𝑒
 E seja o estoque definido por (R4)
𝑠0 = 500
𝑠1 = 𝑠0 + 𝑥1 + 𝑦1 − 𝐷1
𝑠2 = 𝑠1 + 𝑥2 + 𝑦2 − 𝐷2
…
𝑠6 = 𝑠5 + 𝑥6 + 𝑦6 − 𝐷6
 Temos o seguinte modelo para o problema proposto:
𝜑 = min 𝑓 𝑥, 𝑦, 𝑠 = 𝑐𝑥𝑥1 + 𝑐
𝑦𝑦1 + 𝑐
𝑠𝑠1 + 𝑐
𝑥𝑥2 + 𝑐
𝑦𝑦2 + 𝑐
𝑠𝑠2 +⋯+ 𝑐
𝑥𝑥6 + 𝑐
𝑦𝑦6 + 𝑐
𝑠𝑠6
 Sujeito à
𝑥1 + 𝑦1 + 𝑠0 ≥ 𝐷1
𝑥2 + 𝑦2 + 𝑠1 ≥ 𝐷2
…
𝑥6 + 𝑦6 + 𝑠5 ≥ 𝐷6
𝑥1 ≤ 𝑃𝑚𝑎𝑥
𝑁
𝑥2 ≤ 𝑃𝑚𝑎𝑥
𝑁
…
𝑥6 ≤ 𝑃𝑚𝑎𝑥
𝑁
𝑦1 ≤ 𝑃𝑚𝑎𝑥
𝑒
𝑦2 ≤ 𝑃𝑚𝑎𝑥
𝑒
…
𝑦6 ≤ 𝑃𝑚𝑎𝑥
𝑒
𝑠0 = 500
𝑠1 = 𝑠0 + 𝑥1 + 𝑦1 − 𝐷1
𝑠2 = 𝑠1 + 𝑥2 + 𝑦2 − 𝐷2
…
𝑠6 = 𝑠5 + 𝑥6 + 𝑦6 − 𝐷6
MODELAGEM GENÉRICA
 Conforme os sistemas se tornam mais complexos, os modelos em
formato padrão vão se tornando muito extensos de se representar
 Deste modo, a utilização da modelagem genérica se torna mais
atrativa
Convertendo R1
𝑥1 + 𝑦1 + 𝑠0 ≥ 𝐷1
𝑥2 + 𝑦2 + 𝑠1 ≥ 𝐷2
…
𝑥6 + 𝑦6 + 𝑠5 ≥ 𝐷6
Convertendo R1
𝑥1 + 𝑦1 + 𝑠0 ≥ 𝐷1
𝑥2 + 𝑦2 + 𝑠1 ≥ 𝐷2
…
𝑥6 + 𝑦6 + 𝑠5 ≥ 𝐷6
 Ao analisarmos as restrições do tipo R1, se pode observar que o atendimento da
demanda no período 𝑡 é sempre garantida pela produção normal no período 𝑡,
acrescido da produção extra no período 𝑡, acrescida, ainda, pelo valor em estoque
no período 𝑡 − 1
𝑥𝑡 + 𝑦𝑡 + 𝑠𝑡−1 ≥ 𝐷𝑡
Convertendo R1
𝑥1 + 𝑦1 + 𝑠0 ≥ 𝐷1
𝑥2 + 𝑦2 + 𝑠1 ≥ 𝐷2
…
𝑥6 + 𝑦6 + 𝑠5 ≥ 𝐷6
 Ao analisarmos as restrições do tipo R1, se pode observar que o atendimento da
demanda no período 𝑡 é sempre garantida pela produção normal no período 𝑡,
acrescido da produção extra no período 𝑡, acrescida, ainda, pelo valor em estoque
no período 𝑡 − 1
𝑥𝑡 + 𝑦𝑡 + 𝑠𝑡−1 ≥ 𝐷𝑡
 Podemos analisar também que a restrição se repete para cada período 𝑡 ∈ 𝑇
𝑥𝑡 + 𝑦𝑡 + 𝑠𝑡−1 ≥ 𝐷𝑡 ∀𝑡 ∈ 𝑇
Convertendo R2
𝑥1 ≤ 𝑃𝑚𝑎𝑥
𝑁
𝑥2 ≤ 𝑃𝑚𝑎𝑥
𝑁
…
𝑥6 ≤ 𝑃𝑚𝑎𝑥
𝑁
Convertendo R2
𝑥1 ≤ 𝑃𝑚𝑎𝑥
𝑁
𝑥2 ≤ 𝑃𝑚𝑎𝑥
𝑁
…
𝑥6 ≤ 𝑃𝑚𝑎𝑥
𝑁
 Ao analisarmos as restrições do tipo R2, se pode observar que a garantia que
nenhuma produção máxima, em horário normal, é feita ao obrigar-se que a
produção no horário normal do período 𝑡 seja menor que uma constante 𝑃𝑚𝑎𝑥
𝑁
𝑥𝑡 ≤ 𝑃𝑚𝑎𝑥
𝑁
Convertendo R2
𝑥1 ≤ 𝑃𝑚𝑎𝑥
𝑁
𝑥2 ≤ 𝑃𝑚𝑎𝑥
𝑁
…
𝑥6 ≤ 𝑃𝑚𝑎𝑥
𝑁
 Ao analisarmos as restrições do tipo R2, se pode observar que a garantia que
nenhuma produção máxima, em horário normal, é feita ao obrigar-se que a
produção no horário normal do período 𝑡 seja menor que uma constante 𝑃𝑚𝑎𝑥
𝑁
𝑥𝑡 ≤ 𝑃𝑚𝑎𝑥
𝑁
 Podemos analisar também que a restrição se repete para cada período 𝑡 ∈ 𝑇
𝑥𝑡 ≤ 𝑃𝑚𝑎𝑥
𝑁 ∀𝑡 ∈ 𝑇
Convertendo R3
𝑥1 ≤ 𝑃𝑚𝑎𝑥
𝑒
𝑥2 ≤ 𝑃𝑚𝑎𝑥
𝑒
…
𝑥6 ≤ 𝑃𝑚𝑎𝑥
𝑒
Convertendo R3
𝑥1 ≤ 𝑃𝑚𝑎𝑥
𝑒
𝑥2 ≤ 𝑃𝑚𝑎𝑥
𝑒
…
𝑥6 ≤ 𝑃𝑚𝑎𝑥
𝑒
 Ao analisarmos as restrições do tipo R3, se pode observar que a garantia que
nenhuma produção máxima, em horário extra, é feita ao obrigar-se que a produção
no horário normal do período 𝑡 seja menor que uma constante 𝑃𝑚𝑎𝑥
𝑒
𝑥𝑡 ≤ 𝑃𝑚𝑎𝑥
𝑒
Convertendo R3
𝑥1 ≤ 𝑃𝑚𝑎𝑥
𝑒
𝑥2 ≤ 𝑃𝑚𝑎𝑥
𝑒
…
𝑥6 ≤ 𝑃𝑚𝑎𝑥
𝑒
 Ao analisarmos as restrições do tipo R3, se pode observar que a garantia que
nenhuma produção máxima, em horário extra, é feita ao obrigar-se que a produção
no horário normal do período 𝑡 seja menor que uma constante 𝑃𝑚𝑎𝑥
𝑒
𝑥𝑡 ≤ 𝑃𝑚𝑎𝑥
𝑒
 Podemos analisar também que a restrição se repete para cada período 𝑡 ∈ 𝑇
𝑥𝑡 ≤ 𝑃𝑚𝑎𝑥
𝑒 ∀𝑡 ∈ 𝑇
Convertendo R4
𝑠1 = 𝑠0 + 𝑥1 + 𝑦1 − 𝐷1
𝑠2 = 𝑠1 + 𝑥2 + 𝑦2 − 𝐷2
…
𝑠6 = 𝑠5 + 𝑥6 + 𝑦6 − 𝐷6
Convertendo R4
𝑠1 = 𝑠0 + 𝑥1 + 𝑦1 − 𝐷1
𝑠2 = 𝑠1 + 𝑥2 + 𝑦2 − 𝐷2
…
𝑠6 = 𝑠5 + 𝑥6 + 𝑦6 − 𝐷6
 Ao analisarmos as restrições do tipo R4, se pode observar que o estoque ao final do
período 𝑡 é dado pelo valore do estoque ao final do período 𝑡 − 1, somado a
produção em hora normal no período 𝑡, somado, ainda, a produção em hora extra
no período 𝑡 e, por fim, subtraindo-se a demanda existente no período 𝑡
𝑠𝑡 = 𝑠𝑡−1 + 𝑥𝑡 + 𝑦𝑡 − 𝐷𝑡
Convertendo R4
𝑠1 = 𝑠0 + 𝑥1 + 𝑦1 − 𝐷1
𝑠2 = 𝑠1 + 𝑥2 + 𝑦2 − 𝐷2
…
𝑠6 = 𝑠5 + 𝑥6 + 𝑦6 − 𝐷6
 Ao analisarmos as restrições do tipo R4, se pode observar que o estoque ao final do
período 𝑡 é dado pelo valore do estoque ao final do período 𝑡 − 1, somado a
produção em hora normal no período 𝑡, somado, ainda, a produção em hora extra
no período 𝑡 e, porfim, subtraindo-se a demanda existente no período 𝑡
𝑠𝑡 = 𝑠𝑡−1 + 𝑥𝑡 + 𝑦𝑡 − 𝐷𝑡
 Podemos analisar também que a restrição se repete para cada período 𝑡 ∈ 𝑇
𝑠𝑡 = 𝑠𝑡−1 + 𝑥𝑡 + 𝑦𝑡 − 𝐷𝑡 ∀𝑡 ∈ 𝑇
Convertendo 𝜑
𝜑 = min 𝑓 𝑥, 𝑦, 𝑠 = 𝑐𝑥𝑥1 + 𝑐
𝑦𝑦1 + 𝑐
𝑠𝑠1 + 𝑐
𝑥𝑥2 + 𝑐
𝑦𝑦2 + 𝑐
𝑠𝑠2 +⋯+ 𝑐
𝑥𝑥6 + 𝑐
𝑦𝑦6 + 𝑐
𝑠𝑠6
Convertendo 𝜑
𝜑 = min 𝑓 𝑥, 𝑦, 𝑠 = 𝑐𝑥𝑥1 + 𝑐
𝑦𝑦1 + 𝑐
𝑠𝑠1 + 𝑐
𝑥𝑥2 + 𝑐
𝑦𝑦2 + 𝑐
𝑠𝑠2 +⋯+ 𝑐
𝑥𝑥6 + 𝑐
𝑦𝑦6 + 𝑐
𝑠𝑠6
 Ao analisarmos a função objetivo observamos que, para cada período 𝑡, o
custo de produção é dado pela soma dos custos: total de produção em horário
normal; total de produção em horário extra; total de estoque ao final do
período. Sabe que o custo total é dado pela multiplicação entre o custo
unitário e a quantidade
𝑐𝑥𝑥𝑡 + 𝑐
𝑦𝑦𝑡 + 𝑐
𝑠𝑠𝑡
Convertendo 𝜑
𝜑 = min 𝑓 𝑥, 𝑦, 𝑠 = 𝑐𝑥𝑥1 + 𝑐
𝑦𝑦1 + 𝑐
𝑠𝑠1 + 𝑐
𝑥𝑥2 + 𝑐
𝑦𝑦2 + 𝑐
𝑠𝑠2 +⋯+ 𝑐
𝑥𝑥6 + 𝑐
𝑦𝑦6 + 𝑐
𝑠𝑠6
 Ao analisarmos a função objetivo observamos que, para cada período 𝑡, o custo de
produção é dado pela soma dos custos: total de produção em horário normal; total
de produção em horário extra; total de estoque ao final do período. Sabe que o
custo total é dado pela multiplicação entre o custo unitário e a quantidade
𝑐𝑥𝑥𝑡 + 𝑐
𝑦𝑦𝑡 + 𝑐
𝑠𝑠𝑡
 Podemos analisar, também, que estes valores são somados ao longo de todos os
períodos 𝑡 ∈ 𝑇
෍
𝑡=1
𝑇
𝑐𝑥𝑥𝑡 + 𝑐
𝑦𝑦𝑡 + 𝑐
𝑠𝑠𝑡 𝑜𝑢 ෍
𝑡∈𝑇
𝑐𝑥𝑥𝑡 + 𝑐
𝑦𝑦𝑡 + 𝑐
𝑠𝑠𝑡
 Assim, temos o seguinte modelo para o problema proposto:
𝜑 = min𝑓 𝑥, 𝑦, 𝑠 =෍
𝑡∈𝑇
𝑐𝑥𝑥𝑡 + 𝑐
𝑦𝑦𝑡 + 𝑐
𝑠𝑠𝑡
 Sujeito à
𝑥𝑡 + 𝑦𝑡 + 𝑠𝑡−1 ≥ 𝐷𝑡 ∀𝑡 ∈ 𝑇
𝑥𝑡 ≤ 𝑃𝑚𝑎𝑥
𝑁 ∀𝑡 ∈ 𝑇
𝑥𝑡 ≤ 𝑃𝑚𝑎𝑥
𝑒 ∀𝑡 ∈ 𝑇
𝑠𝑡 = 𝑠𝑡−1 + 𝑥𝑡 + 𝑦𝑡 − 𝐷𝑡 ∀𝑡 ∈ 𝑇
𝑠0 = 500