Aula Modelagem

Prévia do material em texto

Modelagem
PROGRAMAÇÃO LINEAR - ENP153
Alexandre Xavier Martins
Departamento de Engenharia de Produção, UFOP
LASOS - Laboratório de Simulação e Otimização de Sistemas
5 de março de 2015
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 5 de março de 2015 1 / 19
Modelagem
Modelagem
Problema das ligas Metálicas
Uma metalúrgica deseja maximizar sua receita bruta. A Tabela 1
ilustra a proporção de cada material na mistura para a obtenção das
ligas possíveis de fabricação. O preço está cotado em reais por
tonelada da liga fabricada. Também em toneladas estão expressas as
restrições de disponibilidade de matérias-prima. Formular o modelo
de programação matemática que maximiza a receita da empresa
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 5 de março de 2015 2 / 19
Modelagem
Modelagem
Problema das ligas Metálicas
Tabela : Parâmetros do Problema das ligas Metálicas
Liga Baixa Liga Alta Disponibilidade
Resistência Resistência
Cobre 0,50 0,20 16 ton
Zinco 0,25 0,30 11 ton
Chumbo 0,25 0,50 15 ton
Preço de Venda 3.000 5.000
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 5 de março de 2015 3 / 19
Modelagem
Modelagem
Problema das ligas Metálicas
1 Definição da variável (ou variáveis) de decisão;
2 Formulação da função objetivo;
3 Formulação das restrições.
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 5 de março de 2015 4 / 19
Modelagem
Modelagem
Problema das ligas Metálicas
Definição da variável de decisão: para o problema em questão o
tomador de decisões deve decidir qual a quantidade de cada tipo
de liga ele deve produzir. Seja xi a quantidade a ser produzida da
liga i , onde i = 1 para a liga de baixa resistência e i = 2 para a
liga de alta resistência.
Formulação da função objetivo: o objetivo do tomador de
decisões no problema acima é definir valores para x1 e x2 de
maneira que o lucro desta decisão seja o maior possível.
Sabemos que para cada tonelada fabricada de x1 o retorno é de
3.000 enquanto para x2 o lucro é de 5.000. Dessa forma,
podemos definir o nosso objetivo como maximizar
Q(x) = 3.000x1 + 5.000x2.
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 5 de março de 2015 5 / 19
Modelagem
Modelagem
Problema das ligas Metálicas
Definição da variável de decisão: para o problema em questão o
tomador de decisões deve decidir qual a quantidade de cada tipo
de liga ele deve produzir. Seja xi a quantidade a ser produzida da
liga i , onde i = 1 para a liga de baixa resistência e i = 2 para a
liga de alta resistência.
Formulação da função objetivo: o objetivo do tomador de
decisões no problema acima é definir valores para x1 e x2 de
maneira que o lucro desta decisão seja o maior possível.
Sabemos que para cada tonelada fabricada de x1 o retorno é de
3.000 enquanto para x2 o lucro é de 5.000. Dessa forma,
podemos definir o nosso objetivo como maximizar
Q(x) = 3.000x1 + 5.000x2.
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 5 de março de 2015 5 / 19
Modelagem
Modelagem
Problema das ligas Metálicas
Formulação das restrições: em nosso exemplo temos três
restrições associadas à disponibilidade de matéria-prima. Para o
cobre temos 16 toneladas disponíveis. Pela Tabela 1 sabemos
que para cada tonelada fabricada da liga de baixa resistência (x1)
são consumidas 0, 5 toneladas de cobre, enquanto para a outra
liga (x2) são consumidas 0, 2 toneladas. Assim temos que
0, 5x1 + 0, 2x2 ≤ 16. As outras restrições que dizem respeito às
matérias-primas podem ser contruídas de forma análoga, assim
para o zinco temos que 0, 25x1 + 0, 3x2 ≤ 11 e para o chumbo
temos 0, 25x1 + 0, 5x2 ≤ 15. Em todos os problemas de
programação linear, acrescentamos restrições triviais que
chamamos de restrições de não-negatividade. Essas restrições
indicam que as variáveis de decisão não podem assumir valores
negativos, assim temos que x1 ≥ 0 e x2 ≥ 0
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 5 de março de 2015 6 / 19
Modelagem
Modelagem
Problema das ligas Metálicas
O modelo completo é dado a seguir:
Maximize Q(x) = 3.000x1 + 5.000x2
Sujeito a:
0, 5x1 + 0, 2x2 ≤ 16
0, 25x1 + 0, 3x2 ≤ 11
0, 25x1 + 0, 5x2 ≤ 15
x1 ≥ 0, x2 ≥ 0
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 5 de março de 2015 7 / 19
Modelagem
Modelagem
Problema da dieta
O objetivo do presente programa é determinar, em uma dieta para a
redução calórica, as quantidades de certos alimentos que deverão ser
ingeridos diariamente, de modo que determinados requisitos
nutricionais sejam satisfeitos a custo mínimo. Suponha que uma certa
dieta alimentar esteja restrita a leite desnatado, carne de boi, carne de
peixe e uma salada de composição conhecida. Sabendo-se ainda que
os requisitos nutricionais serão expressos em termos de vitamina A, C
e D e controlados por suas quantidades mínimas (em miligramas),
uma vez que são indispensáveis à saúde da pessoa que estará se
submetendo à dieta. A Tabela 2 resume a quantidade de cada
vitamina em disponibilidade nos alimentos e a sua necessidade diária
para a boa saúde
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 5 de março de 2015 8 / 19
Modelagem
Modelagem
Problema da dieta
Tabela : Parâmetros do Problema da Dieta
Vitamina Leite (litro) Carne (Kg) Peixe (Kg) Salada (100g) Req. Mín.
A 2 mg 2 mg 10 mg 20 mg 11 mg
C 50 mg 20 mg 10 mg 30 mg 70 mg
D 80 mg 70 mg 10 mg 80 mg 250 mg
Custo 2 4 1,5 1
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 5 de março de 2015 9 / 19
Modelagem
Modelagem
Problema da dieta
A solução do problema é:
Minimize Q(x) = 2xl + 4xc + 1, 5xp + 1xs
Sujeito a:
2xl + 2xc + 10xp + 20xs ≥ 11
50xl + 20xc + 10xp + 20xs ≥ 70
80xl + 70xc + 10xp + 80xs ≥ 250
xl ≥ 0, xc ≥ 0, xp ≥ 0, xs ≥ 0
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 5 de março de 2015 10 / 19
Modelagem
Modelagem
Problema do Planejamento de Produção I
Uma determinada empresa está interessada em maximizar o lucro
mensal proveniente de quatro de seus produtos, designados por I, II,
III, IV. Para fabricar esses quatro produtos, ela utiliza dois tipos de
máquinas (M1 e M2) e dois tipos de mão-de-obra (MO1 e MO2). As
disponibilidades destes recursos são apresentados na Figura 1. Os
dados de utilização dos recursos para a produçao de cada produto
fornecidos pelo setor técnico da empresa são dados pela Figura 2. O
setor comercial da empresa forneceu as informações referentes à
demanda máxima e o lucro de cada produto na Figura 3. Deseja-se
saber a produção mensal dos produtos I, II, III e IV para que o lucro
mensal seja máximo. Formule um modelo de programação linear que
expresse o objetivo e as restrições desse empresa.
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 5 de março de 2015 11 / 19
Modelagem
Modelagem
Problema do Planejamento de Produção I
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 5 de março de 2015 12 / 19
Modelagem
Modelagem
Problema do Planejamento de Produção I
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 5 de março de 2015 13 / 19
Modelagem
Modelagem
Problema do Planejamento de Produção I
A solução para este problema é:
Maximize Q(x) = 10xI + 8xII + 9xII + 7xIV
Sujeito a:
5xI + 4xII + 8xIII + 9xIV ≤ 80
2xI + 6xII + 0xIII + 8xIV ≤ 20
2xI + 4xII + 2xIII + 8xIV ≤ 120
7xI + 3xII + 0xIII + 7xIV ≤ 160
xI ≤ 70
xII ≤ 60
xIII ≤ 40
xIV ≤ 20
xI ≥ 0, xII ≥ 0, xIII ≥ 0, xIV ≥ 0
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 5 de março de 2015 14 / 19
Modelagem
Modelagem
Problema do sítio
Um sitiante está planejando sua estratégia de plantio para o próximo
ano. Por informações obtidas nos órgãos governamentais, sabe que
as culturas de trigo, arroz e milho serão as mais rentáveis na próxima
safra. Porexperiência, sabe que a produtividade de sua terra para as
culturas desejadas é constante na tabela a seguir. Por falta de um
local de armazenamento próprio, a produção máxima, em toneladas,
está limitada a 60 toneladas. A área cultivável do sítio é de
200.000m2. Para atender às demandas de seu próprio sítio, é
imperativo que se plante no mínimo 400m2 de trigo, 800m2 de arroz e
10.000m2 de milho. O objetivo é construir um modelo que maximize o
lucro
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 5 de março de 2015 15 / 19
Modelagem
Modelagem
Problema do sítio
Tabela : Parâmetros do Problema do sítio
Cultura Produtividade Lucro por
em Kg por m2 Kg de produção
Trigo 0,2 10,80
Arroz 0,3 4,20
Milho 0,4 2,03
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 5 de março de 2015 16 / 19
Modelagem
Modelagem
Problema do sítio
Muitos problemas podem exibir formulações diferentes que podem ser
ou não mais eficientes que as outras. A eficiência de um modelo pode
ser em termos de tempo computacional exigido para sua resolução,
ou pode ser em termos de limites em casos de problemas de
programação inteira. No exemplo do sítio podemos ter dois modelos
dependendo da variável de decisão escolhida. Por exemplo, seja xi a
quantidade em Kg para cada cultura, onde i = {T ,A,M}, o modelo é
dado a seguir
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 5 de março de 2015 17 / 19
Modelagem
Modelagem
Problema do sítio
Maximize Q(x) = 10, 80xT + 4, 20xA + 2, 03xM
Sujeito a:
xT + xA + xM ≤ 60.000
5xT + 3, 33xA + 2, 5xM ≤ 200.000
5xT ≥ 400
3, 33xA ≥ 800
2, 5xM ≥ 10.000
xT ≥ 0, xA ≥ 0, xM ≥ 0
Resolvendo o modelo acima obteriamos a seguinte solução, xT = 37.840Kg,
xA = 240Kg e xM = 4.000Kg com um lucro de 417.800.
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 5 de março de 2015 18 / 19
Modelagem
Modelagem
Problema do sítio
Se ao invés de Kg, resolvermos expressar a variável de decisão em termos de área,
ou seja, xi é a quantidade de área em m2 disponibilizada para a cultura i teríamos a
formulação abaixo:
Maximize Q(x) = 2, 16xT + 1, 26xA + 0, 812xM
Sujeito a:
0, 2xT + 0, 3xA + 0, 4xM ≤ 60.000
xT + xA + xM ≤ 200.000
xT ≥ 400
xA ≥ 800
xM ≥ 10.000
xT ≥ 0, xA ≥ 0, xM ≥ 0
Este modelo apresenta a seguinte solução: xT = 189.200m2, xA = 800m2 e
xM = 10.000m2 com um lucro de 417.800.
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 5 de março de 2015 19 / 19
	Modelagem