Pesquisa Operacional para Engenharia de Produção II

Prévia do material em texto

*
*
PESQUISA OPERACIONAL PARA A ENGENHARIA DE PRODUÇÃO II
**Construção de Modelos de Programação Linear II **
Profa. Vitória Pureza
1º Semestre
Aulas 3 e 4
*
*
Roteiro
Definindo objetivos
Definindo restrições
Lista de Exercícios
Construção de modelos grandes combinando modelos menores
Modelos multi-instalações
Modelos multi-produtos
Modelos multi-períodos 
Williams, capítulos 3 e 4
*
*
Definindo Objetivos
maximizar lucro
minimizar custo/tempo
maximizar retorno em investimento
minimizar número de empregados
maximizar número de empregados
maximizar a satisfação do cliente
Um único objetivo
Objetivos múltiplos e conflitantes
Objetivos irrelevantes
*
*
Um Único Objetivo
Normalmente inclui apenas termos variáveis - é geralmente incorreto* adicionar custos fixos tais como custos administrativos e de equipamentos
No problema de Gepetto 
Deseja-se maximizar 3x1+ 2x2 (lucro)
O valor da função objetivo é proporcional ao valor das variáveis x1e x2 que indicam a quantidade de trens e bonecos a serem produzidos (decisões)
*
*
Objetivos Múltiplos e Conflitantes
Objetivo 1: Min h(x)=c1/x 	Objetivo 2: Min g(x)=c2x
Combinação linear dos objetivos: Min f(x)=g(x) + h(x)
Programação Multiobjetivo 
Manter apenas o objetivo mais relevante e tranformar os demais em restrições do modelo: 
Min g(x)  g(x) ≤ M
*
*
Definindo Restrições
Capacidade produtiva
Máximo de 100 horas de acabamento disponíveis por semana
2x1 + x2 ≤ 100 (horas/semana)
Disponibilidade de matéria-prima
Máximo de 4500 kgs de aço disponíveis por mês
3x1 + 4x2 ≤ 4500 (kgs/mês)
Demanda mínima
Mínimo de 10000 barris de gasolina 1 produzidas por mês
x1 ≥ 10000 (barris/mês)
Limitações de mercado
Máximo de 40 bonecos vendidos por semana
 x2 ≤ 40 (unidades/semana)
Balanço de material ou massa
Balanço trimestral de estoque de barcos 
Et-1 + xt = Dt + Et (unidades/trimestre)
Especificações do produto
Octanagem, resistência, condutividade, porcentagem de nutrientes
*
*
Restrições Soft e Hard
limitações da capacidade produtiva e disponibilidade de mão-de-obra : podem ser desobedecidas soft.
restrições tecnológicas: não podem ser desobedecidas  hard.
Restrições
soft e hard
conflitantes
redundantes
pouco usuais
*
*
Restrições Redundantes
restrições inativas, identificadas por métodos de detecção
Restrições Conflitantes
o problema é infactível
Programação por Metas : procura-se satisfazer ao máximo as restrições  a função objetivo passa a ser “o custo” resultante das violações das restrições, e que deve ser minimizado
*
*
	Uma agência de publicidade quer determinar uma programação de anúncios na TV para uma concessionária de carros. A concessionária tem 3 metas:
(1 ) seus anúncios devem ser vistos por pelo menos 40 milhões de homens classe A (H-A).
(2) seus anúncios devem ser vistos por pelo menos 60 milhões de pessoas classe C (P-C).
(3) seus anúncios devem ser vistos por pelo menos 35 milhões de mulheres classe A (M-A).
	A agência pode comprar dois tipos de anúncios: os mostrados durante jogos de futebol e os mostrados durante novelas. No máximo $600.000,00 podem ser gastos em anúncios. Os custos de propaganda (em milhares de $) e suas audiências potenciais (em milhões de pessoas) de um anúncio de 1 minuto são mostrados abaixo. A agência precisa determinar quantos anúncios de cada tipo devem ser comprados.
*
*
Variáveis de decisão:	x1= no de anúncios de 1 minuto em jogos
				x2= no de anúncios de 1 minuto em novelas
Min 100x1 + 60x2
s.a:
7x1 + 3x2 ≥ 40		Metas de mercado
10x1 + 5x2 ≥ 60
5x1 + 4x2 ≥ 35
100x1 + 60x2≤ 600	Orçamento
x1,x2 ≥ 0
NOVO MODELO
Variáveis de decisão adicionais:	si- = montante a menos da meta i
					si+ = montante a mais da meta i (i=1..3)
Min 200s1- + 100 s2- + 50 s3-
s.a:
7x1 + 3x2 + s1- - s1+= 40		
10x1 + 5x2 + s2- - s2+= 60
5x1 + 4x2 + s3- - s3+= 35
100x1 + 60x2 ≤ 600	
todas as variáveis ≥ 0
Infactível !
Solução ótima:
x1=6	 x2=0
s1+ =2	 s1- =0
s2+ =0	 s2- =0
s3+ =0	 s3- =5
*
*
Restrições Pouco Usuais
	“Pode-se produzir produto 1 se o produto 2 for produzido mas não se os produtos 3 e 4 forem produzidos”
*
*
 Lista 2
No exercício 2 da lista 2, suponha que se tenha decidido não fazer a alocação prévia de matéria-prima para as fábricas. Quanto produzir para maximizar o lucro total ? 
*
*
Modelo da Fábrica A
Max 15x1 + 20x2 	(lucro da fábrica)
sujeito a:
		4x1 	+ 2x2 	≤ 80 (lixamento)
 		2x1 	+ 5x2 	≤ 60 (polimento)
 		4x1 	+ 4x2 	≤ 75 	 (matéria-prima)
 		x1 		≥ 0 (sinal)
 	 x2 	 ≥ 0
Modelo da Fábrica B
Max 15x3 + 20x4 	(lucro da fábrica)
sujeito a:
		5x3 	+ 3x4 	≤ 60 	(lixamento)
 		5x3 	+ 6x4 	≤ 75 	(polimento)
 		4x3 	+ 4x4 	≤ 45 	(matéria-prima)
 		x3 		 ≥ 0 (sinal)
 	 x4 	 ≥ 0
*
*
Modelo da Fábrica A
Max 15x1 + 20x2 	(lucro da fábrica)
sujeito a:
		4x1 	+ 2x2 	≤ 80 (lixamento)		Solução ótima: 	
		2x1 	+ 5x2 	≤ 60 (polimento)		x*=(10,8) fo*=310
 		4x1 	+ 4x2 	≤ 75 	 (matéria-prima)
 		x1 		≥ 0 (sinal)
 	 x2 	 ≥ 0
Modelo da Fábrica B
Max 15x3 + 20x4 	(lucro da fábrica)
sujeito a:
		5x3 	+ 3x4 	≤ 60 	(lixamento)	 Solução ótima: 	
 		5x3 	+ 6x4 	≤ 75 	(polimento) 	x*=(0,11) fo*=220
 		4x3 	+ 4x4 	≤ 45 	(matéria-prima)
 		x3 		≥ 0 (sinal)
 	 x4 	 ≥ 0
*
*
O modelo divide a matéria-prima disponível otimamente
 Lucro(Fábrica A) + Lucro(Fábrica B) < Lucro(Fábrica A + Fábrica B)
 O maior lucro total foi obtido, designando maior quantidade de matéria-prima para a Fábrica B  complexidade de sistemas de grande porte
Modelos de Programação Linear Estruturada 
Multi-instalações
Max 
15x1 + 20x2 + 15x3 + 20x4 (lucro de A e B)
sujeito a:
		4x1 	+ 2x2 			≤ 80 (lixamento - A)
 		2x1 	+ 5x2 			≤ 60 (polimento - A)
				5x3 	+ 3x4 	≤ 60 (lixamento - B)
 				5x3 	+ 6x4 	≤ 75 (polimento - B)
 		4x1 	+ 4x2 	+ 4x3 	+ 4x4 	≤ 120 	(matéria-prima)
		x1 				≥ 0 (sinal)
 	 	 x2 			≥ 0
 				 x3 		≥ 0 
	 			x4 	≥ 0
Solução ótima:
x=(10, 8, 0, 12) fo*=550
*
*
 
Modelos Multi-produtos - Problema da Mistura
	Uma refinaria produz três tipos de gasolina (G1, G2, G3) a partir de três tipos de óleo cru (O1, O2, O3). Há 5.000 barris de óleo cru de cada tipo disponíveis diariamente, e a refinaria pode produzir no máximo 14.000 barris diários de gasolina. Os produtos finais devem ter a qualidade exigida. 
	Cada barril de gasolina produzida incorre em um custo de $4. Há uma demanda fixa diária de 3.000 barris de G1, 2.000 barris de G2 e 1.000 barris de G3, e esta pode ser estimulada através de propaganda. Cada $ gasto em propaganda em um dado tipo de gasolina, aumenta a demanda diária por esse tipo em 10 barris. Faça um modelo de programação matemática para determinar o quanto produzir de cada tipo de gasolina com o maior lucro total.
*
*
Objetivo: Maximizar o lucro total diário = { receita de vendas para clientes cativos e com demanda estimulada por propaganda - custos de matéria-prima - custos de produção - custos de propaganda } com as gasolinas G1, G2, e G3
Demanda estimulada: 10 barris/$ 
*
*
Fatores que afetam o alcance do objetivo 
Capacidade de refinamento: 14.000 barris diários
Disponibilidade (suprimento) dos óleos: 5.000 (O1, O2 e O3) barris diários
Demanda mínima das gasolinas: 3.000 (G1), 2.000 (G2) e 1.000 (G3) barris diários
Qualidade das gasolinas
*
*
 Representação informal do problema 
Deseja-se 
Maximizar lucro diário = { receita de vendas para clientes cativos e com demanda estimulada por propaganda - custos de matéria-prima - custos de produção – custos de propaganda} com as gasolinas G1, G2, e G3}, sujeito às seguintes restrições:
a produção das gasolinas não pode exceder a capacidade diária de refinamento
a produção das gasolinas não pode exceder a disponibilidade diária de óleos crus
a produção das gasolinas deve atender a demanda diária de clientes cativos
a qualidade das gasolinas produzidas deve ser satisfeita
*
*
Restrições de qualidade
Suponha que misturássemos 1 barril de O1 e 1 barril de O2. Qual a octanagem da gasolina resultante?
12 (octanas/barril)*1 barril + 6(octanas/barril)* 1 barril = 9 octanas
(1 + 1) barris 
E se misturássemos: 
1 barril de O1 e 0,5 barril de O2?
1 barril de O1, 1 barril de O2 e 1 barril de O3?
x1 barris de O1, x2 barris de O2 e x3 barris de O3?
Note que para conhecermos a qualidade de uma determinada gasolina, precisamos saber as quantidades de cada tipo de óleo utilizado na sua produção. Mas como saber a quantidade de cada tipo de gasolina produzida?Mas como saber a quantidade de
 
*
*
Decisão: A refinaria precisa definir quanto de cada óleo deve usar em cada gasolina e o quanto gastar em propaganda com cada gasolina
xi j = número de barris de oleo cru i usado na producao 
	da gasolina j (i=1,2,3; j=1,2,3)
yj = custo de propaganda com demanda estimulada da 
	gasolina j (j=1,2,3)
*
*
Modelo 
Variáveis de decisão
xi j = número de barris de oleo cru i usado na producao da gasolina j (i=1,2,3; j=1,2,3)
yj = custo de propaganda com demanda estimulada da gasolina j (j=1,2,3)
Função objetivo
Max 70(x11 + x21 + x31) (receita da venda de G1)
	+ 60(x12 + x22 + x32) (receita da venda de G2)
	+ 50(x13 + x23 + x33) (receita da venda de G3)
	- 45(x11 + x12 + x13) (custo de compra de O1)
	- 35(x21 + x22 + x23) (custo de compra de O2)
	- 25(x31 + x32 + x33) (custo de compra de O3)
 - 4(x11 + x21 + x31 + x12 + x22 + x32 + x13 + x23 + x33) (custos de produção)
 - y1 – y2 – y3 (custo de propaganda com G1, G2 e G3)
*
*
x11 + x12 + x13 ≤ 5.000		(restrições de suprimento dos óleos) 	
x21 + x22 + x23 ≤ 5.000					
x31 + x32 + x33 ≤ 5.000					
x11 + x21 + x31 ≥ 3.000 		(restrições de demanda das gasolina)	
x12 + x22 + x32 ≥ 2.000
x13 + x23 + x33 ≥ 1.000
x11 + x21 + x31 + x12 + x22 + x32 + x13 + x23 + x33 ≤ 14.000 (restrição de capacidade de 							refinamento)
x11 + x21 + x31 = 3.000 + 10*y1 		(restrições de demanda estimulada)	
x12 + x22 + x32 = 2.000 + 10*y2
x13 + x23 + x33 = 1.000 + 10*y3 
					 (restrições de qualidade)
12x11 + 6x21 + 8x31 ≥ 10 12x12 + 6x22 + 8x32 ≥ 8		12x13 + 6x23 + 8x33 ≥ 6
(x11 + x21 + x31)		(x12 + x22 + x32)		(x13 + x23 + x33)
0,5 x11 + 2x21 + 3x31 ≤ 1 0,5x12 + 2x22 + 3x32 ≤ 2		0,5x13 + 2x23 + 3x33 ≤ 1
(x11 + x21 + x31)		(x12 + x22 + x32)		(x13 + x23 + x33)
xij ≥ 0 , yj ≥ 0 (i=1,2,3; j=1,2,3) 	(restrições de sinal)
*
*
Modelos Multi-períodos
	
	Uma empresa precisa determinar quantos barcos produzir durante cada um dos próximos 4 trimestres. A demanda de cada trimestre é 40, 60, 75 e 25. Deve-se atender a demanda sem atrasos. 
	
	No início, a empresa tem em estoque 10 barcos. Assume-se que os barcos produzidos durante um período podem ser usados para atender a demanda daquele período. Durante cada período, a empresa pode produzir 40 barcos com mão-de -obra regular a um custo total de $400/barco. Se utilizadas horas extras, pode-se produzir barcos extras a um custo total de $450 por barco. No fim de cada período (depois da produção ter ocorrido e a demanda do período corrente ter sido satisfeita), incorre-se em um custo de estoque de $20 por barco. 
	Como minimizar a soma de custos de estoque e produção?
*
*
Restrições de balanço
	Seja it o estoque de barcos advindo do período t, xt a produção de barcos no período t e dt a demanda de barcos no período t.
	barcos em estoque em t-1 + barcos produzidos em t = barcos vendidos em t + barcos em estoque em t 
it-1+ xt =dt + it
*
*
Solução: fo=$78.450 
Utilização de modelos multi-períodos na prática (horizonte rolante)
	Seja T, o número de períodos do horizonte de planejamento
Resolução do modelo para t=1 a T
Implementação das decisões do(s) primeiro(s) período(s), por exemplo dos períodos 1 e 2. Decisões de períodos posteriores são consideradas provisórias
Após um ou mais períodos (por exemplo, após período 2), o modelo é novamente resolvido com dados atualizados, por exemplo, para 3 a T+3
*
*
*