IPO Aula 3 resolucao das listas e exercicios com LINDO

Prévia do material em texto

*
*
INTRODUÇÃO À PESQUISA OPERACIONAL 
** Programação Linear – Parte 2b **
Profa. Vitória Pureza
2º Semestre
*
*
Última Aula
Construção de modelos de programação linear
	Hoje verificaremos a modelagem dos exercícios pendentes da lista e utilizaremos uma linguagem de programação matemática para resolvê-los. 
	Nas aulas seguintes veremos a fundo o método de resolução que esta linguagem utiliza
*
*
Roteiro
Construção passo a passo de modelos de Programação Linear
Uso da linguagem de programação LINDO para resolução dos modelos
*
*
Passos para Modelagem de Programação Matemática
 Defina o objetivo do problema. Colete os dados associados
 Defina os fatores que afetam o alcance do objetivo do problema. Colete os dados associados
 Elabore uma representação informal do problema
 Elabore um modelo de programação matemática do problema
*
*
Um Problema de Transporte
	Powerco tem 3 usinas de energia elétrica que suprem a necessidade de 4 cidades. Cada usina pode suprir a seguinte quantidade de milhões de kilowatts-hora de eletricidade: U1 = 35; U2 = 50; U3 = 40. As demandas de pico nas 4 cidades ocorrem na mesma hora e são (em milhões de KWh): C1 = 45; C2 = 20; C3 = 30; C4 = 30.
	Os custos de se enviar 1 milhão de kwh de eletricidade de uma usina para uma cidade depende da distância que a eletricidade deve percorrer (tabela a seguir). Formule um PL para minimizar o custo de atender pelo menos a demanda de pico das cidades.
*
*
 Objetivo do Problema
	Minimizar custo total de suprimento da demanda de pico das cidades
*
*
 Fatores que Afetam o Alcance do Objetivo 
Limitações de capacidade produtiva das usinas
Demanda mínima das cidades
*
*
 Representação Informal do Problema
Deseja-se 
Minimizar custo total de suprimento da demanda de pico das cidades, sujeito às seguintes restrições:
a quantidade de energia elétrica enviada pelas usinas não pode exceder a produção horária das usinas
a quantidade de energia elétrica recebida pelas cidades não pode ser inferior às suas demandas de pico
*
*
 Formulação do Modelo de Programação Matemática
xi j = 106 KWh produzidos na usina i e enviados à cidade j
b) Função Objetivo (FO)
Min 8x11 + 6x12 + 10x13 + 9x14 (custo de transporte da usina 1)
+ 9x21 + 12x22 + 13x23 + 7x24 (custo de transporte da usina 2)
+ 14x31 + 9x32 + 16x33 + 5x34 (custo de transporte da usina 3)
a) Variáveis de Decisão
O custo total de transporte é determinado pela quantidade de eletricidade enviada de cada usina p/ cada cidade
*
*
 Formulação do Modelo de Programação Matemática
c) Restrições
A quantidade de energia elétrica enviada das usinas não pode exceder suas produções horárias
	Restrições de suprimento
		x11 + x12 + x13 + x14 ≤ 35	(suprimento de U1)
		x21 + x22 + x23 + x24 ≤ 50	(suprimento de U2)
		x31 + x32 + x33 + x34 ≤ 40	(suprimento de U3)
A quantidade de energia elétrica recebida pelas cidades não pode ser inferior a suas demandas de pico
	Restrições de demanda
		x11 + x21 + x31 ≥ 45 	 (demanda de C1)
		x12 + x22 + x32 ≥ 20 	 (demanda de C2)
		x13 + x23 + x33 ≥ 30 (demanda de C3)
		x14 + x24 + x34 ≥ 30 	 (demanda de C4)
*
*
 Formulação do Modelo de Programação Matemática
xij ≥ 0 (i=1..3, j=1..4) (106 KWh ) 
d) Restrições de sinal
*
*
Modelo de Programação Linear
Min 8x11+6x12+10x13+9x14+9x21+12x22+13x23+7x24+ 14x31 +9x32 +16x33 +5x34
sujeito a:
x11 + x12 + x13 + x14 ≤ 35		(restrições de suprimento) 	
x21 + x22 + x23 + x24 ≤ 50 					
x31 + x32 + x33 + x34 ≤ 40 					
x11 + x21 + x31 ≥ 45 		(restrições de demanda)		
x12 + x22 + x32 ≥ 20
x13 + x23 + x33 ≥ 30
x14 + x24 + x34 ≥ 30
xij ≥ 0 (i=1,2,3; j=1,2,3,4) 	 (restrições de sinal)
*
*
Representação Gráfica
U1
U2
U3
C1
C2
C3
C4
X11
X12
*
*
Um Problema de Planejamento da Produção
	Uma companhia possui 2 fábricas, A e B. Cada fábrica faz 2 produtos, padrão e deluxe. Uma unidade de padrão resulta em lucro de $10 e uma unidade de deluxe em um lucro de $15. 
	Cada fábrica utiliza 2 processos (lixamento e polimento) para produzir esses produtos. A fábrica A tem uma capacidade semanal de lixamento de 80 horas e de polimento de 60 horas. Para a fábrica B, essas capacidades são 60 e 75 horas semanais. Os tempos de lixamento e polimento em horas para uma unidade de cada produto em cada fábrica são dados na Tabela 2. 
	Cada unidade de produto usa 4 kgs de matéria-prima e dos 120 kgs disponíveis, 75 kgs foram alocados à fábrica A e 45 kgs à fábrica B. Formule um PL para cada fábrica que maximize o lucro.
*
*
 Objetivo do Problema
	Maximizar o lucro com a venda dos produtos padrão e deluxe
*
*
 Fatores que Afetam o Alcance do Objetivo 
Limitações de capacidade produtiva das fábricas
*
*
 Representação Informal do Problema
Deseja-se (para cada uma das fábricas!)
Maximizar o lucro com a venda dos produtos padrão e deluxe, sujeito às seguintes restrições:
as horas semanais de lixamento para fabricação dos produtos não podem exceder a disponibilidade semanal
as horas semanais de polimento para a fabricação dos produtos não podem exceder a disponibilidade semanal
a quantidade de matéria-prima para fabricação dos produtos não podem exceder a disponibilidade semanal
*
*
 Formulação do Modelo de Programação Matemática (para a Fábrica A)
a) Variáveis de Decisão
O lucro é determinado pela quantidade de produto padrão e deluxe produzidos na fábrica
x1 = quantidade de produtos padrão produzidos na fábrica A /semana
x2 = quantidade de produtos deluxe produzidos na fábrica A /semana
b) Função Objetivo (FO)
Max { 10x1 + 15x2 } ($/semana) (para a fábrica A)
*
*
 Formulação do Modelo de Programação Matemática
c) Restrições
As horas semanais de lixamento para fabricação dos produtos não podem exceder a disponibilidade semanal
		 4x1 	+ 2x2 	≤ 80 (hrs/semana)
		
As horas semanais de polimento para a fabricação dos produtos não podem exceder a disponibilidade semanal
		2x1 	+ 5x2 	≤ 60	(hrs/semana)
A quantidade de matéria-prima para fabricação dos produtos não podem exceder a disponibilidade semanal
		4x1 	+ 4x2 	≤ 75	 (kgs/semana)
d) Restrições de sinal
		xi ≥ 0 (i=1..2) (unidades de produto/semana) 
*
*
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
*
*
Um Problema da Dieta
	Minha dieta requer que toda a comida que eu coma venha dos 4 grupos alimentares básicos (chocolate, sorvete, refrigerante e torta). No momento, os 4 alimentos seguintes estão disponíveis para consumo: brownies, sorvete de chocolate, coca-cola e torta de abacaxi. Cada brownie custa 0,50, cada bola de sorvete de chocolate custa 0,20, cada garrafa de coca-cola custa 0,30 e cada pedaço de torta de abacaxi custa 0,80. 
	A cada dia, preciso ingerir pelo menos 500 calorias, 6 onças de chocolate, 10 onças de açúcar e 8 onças de gordura. O conteúdo nutricional por unidade de cada alimento é mostrado abaixo. Formule um PL que possa ser usado para satisfazer meus requerimentos nutricionais diários a um custo mínimo.
*
*
 Objetivo do Problema
	Minimizar o custo com a compra dos alimentos
*
*
 Fatores que Afetam o Alcance do Objetivo 
Requerimentos nutricionais diários
*
*
 Representação Informal do Problema
Deseja-se
Minimizar o custo com a compra dos alimentos de minha dieta, sujeitoàs seguintes restrições:
a quantidade de calorias ingeridas diariamente não podem ser inferiores ao requerimento diário
a quantidade de chocolate ingerido diariamente não pode ser inferior ao requerimento diário
a quantidade de açúcar ingerido diariamente não pode ser inferior ao requerimento diário
a quantidade de gordura ingerida diariamente não pode ser inferior ao requerimento diário
*
*
 Formulação do Modelo de Programação Matemática
a) Variáveis de Decisão
O custo total de minha dieta é determinado pela quantidade de alimentos de cada tipo comprados.
x1 = quantidade de brownies comprados /dia
x2 = bolas de sorvete de chocolate compradas /dia
x3 = garrafas de coca-cola compradas /dia
x4 = pedaços de torta de abacaxi compradas /dia
b) Função Objetivo (FO)
Min 0,50x1+ 0,20x2+ 0,30x3+ 0,80x4 ($/dia)
*
*
 Formulação do Modelo de Programação Matemática
c) Restrições
A quantidade de calorias ingeridas diariamente não podem ser inferiores ao requerimento diário
		 400x1+200x2+150x3+500x4 ≥ 500	(cal/dia)
		
A quantidade de chocolate ingerida diariamente não pode ser inferior ao requerimento diário
		3x1 + 2x2 ≥ 6	(on/dia)
A quantidade de açúcar ingerida diariamente não pode ser inferior ao requerimento diário
		2x1 + 2x2 + 4x3 + 4x4 ≥ 10	(on/dia)
A quantidade de gordura ingerida diariamente não pode ser inferior ao seu requerimento diário
		2x1 + 4x2 + x3 + 5x4 ≥ 8	(on/dia)
*
*
 Formulação do Modelo de Programação Matemática
d) Restrições de sinal
		
	xi ≥ 0 (i=1..4) (unidades de alimento/dia) 
*
*
Modelo de Programação Linear
Min 0,50x1+ 0,20x2+ 0,30x3+ 0,80x4
sujeito a:
	400x1+200x2+150x3+500x4 ≥ 500		(requerimento de calorias) 
	 3x1 + 2x2 ≥ 6		 (requerimento de chocolate) 
	 2x1 + 2x2 + 4x3 + 4x4 ≥ 10		 (requerimento de açúcar) 
 2x1 + 4x2 + x3 + 5x4 ≥ 8	 (requerimento de gordura) 
	 xi ≥ 0 (i=1..4)	 	 	 (restrições de sinal)
*
*
*
*
*
*
*
*
*
*