20100324 - Dossiê Pesquisa Operacional

Prévia do material em texto

UNIVERSIDADE DO ESTADO DE MINAS GERAIS
FACULDADE DE ENGENHARIA
JOÃO MONLEVADE – MG
ALINNE JÚLIA DE ARAÚJO SOUZA
WESLEY MACHADO DE ALMEIDA
Pesquisa Operacional
Dossiê – Aulas Professor Paulino
João Monlevade
2010
Data: 10/02/10
Apresentação do professor, da disciplina “Pesquisa Operacional” e do método de avaliação durante o curso.
A função Básica de uma Pesquisa Operacional é fornecer informações sobre Otimização de um Sistema.
Conceito Otimização: Escolher a melhor alternativa, dado um conjunto de possibilidade.
	Critério – Função Objetivo
	Restrições – Limitações
	Possibilidades ( X
	Critério ( Y
	Y = f(x)
	Maximizar/minimizar y (sujeito a restrições)
Data: 22/02/10
Modelagem de Programação Linear
Etapas:
01 – Especificar Função Objetivo
	 Minimizar z = f (x1, x2)
	ou Maximizar z = g (x1, x2, x3)
02 – Estabelecer as variáveis de controle/decisão
	(x1, x2, x3, ...)
03 – Definir restrições, declarar as limitações do sistema.
Aplicação da Programação da Produção:
Uma indústria produz mesas e armários e para tal tem limitações de couro e madeira, cujo estoque é de 12m² e 18m², respectivamente. Para fabricar mesas gasta-se 2m² de couro e 3m² de madeira, e para a fabricação dos armários gasta-se 1m² de couro e 4m² de madeira. Sabendo-se que cada mesa é vendida a 5 U.M., pede-se a produção que otimiza a receita da fábrica.
Explicação:
	Incógnitas ( X (insumos)
		 Y (saídas)
No exemplo, desejamos o máximo de y ( y = f (x1, x2, x3, ...)
Programação Linear: Técnica mais simplificada para trabalhar com a Pesquisa Operacional
1º) Objetivo: Maximizar Lucro
2º) Variáveis de controle / decisão
3º) Restrições / Limitações do Sistema
Solução: Modelagem do exercício – Representação do sistema informado em modelo matemático.
1º) Objetivo
 Maximizar receita (z = receita)
2º) Variáveis de controle / decisão
 X1 = mesas
 X2 = armários
3º) Restrições
 R1 = limite estoque de couro < 12
 R2 = limite estoque de madeira < 18
Refinamento da Modelagem
FO: z = 5x1 + 6x2
SA
 2x1 + x2 < 12
	 3x1 + 4x2 < 18
	 x1 > 0
	 x2 > 0
Conceito de Programação Linear
F.O.: Max z = c1.x1 c2.x2 + ... cn.xn
SA
 a11x1 + a12x2 + ... a1nxn < b1
 a21x1 + a22x2 + ... a2nxn < b2
	 
	 am1x1 + am2x2 + ... amnxn < bm
 X1 > 0 x2 > 0 ... xn > 0
Formato Matricial
Max z = CTX
 Ax < b
 X > 0
C = C1 X = X1 
 C2 X2 
 Cn Xn 
	A = (aij) i = 1, …, M 
 j = 1, …, N
Revisão Álgebra Linear
1- Dado 
C = 2 , x = x1 e d=8, elaborar o gráfico de CTX < d
 4 x2
Solução: CT = (2 4)
	 CTx ( (2 4) x x1 ( 2x1 + 4x2
 X2
	 CTX < d ( 2x1 + 4x2 < 8
 2x1 + 4x2 = 8
	 Para x1 = 0 ( x2 = 2
 Para x2 = 0 ( x1 = 4
( Escolher um ponto qualquer (onde a reta não passa). Por exemplo, ponto (0,0)
( Levar o ponto na desigualdade: 2x1 + 4x2 < 9 ( 0 < 8 (Verdadeiro)
Data: 24/02/10
Revisão Álgebra Linear
1) Resolver sistema de desigualdade
2) Traçar curvas de nível de uma função de várias variáveis.
Exemplo: Traçar as isolinhas, isto é, curvas de nível da função z = (x1, x2) = 2x1 + 2x2.
Solução:
Lembrete ( 2x1 + 2x2 = CTx, onde C = 2 e x = x1
 2 x2
( z = 2x1 + 2x2 = constante
 Devemos arbitrar valores para a constante
 Seja a constante = 2
 4
 1º: 2x1 + 2x2 = 2 (equação linear ( reta)
	 para x1 = 0, x2 = 1
	 para x2 = 0, x1 = 1
 2º: 2x1 + 2x2 = 4
	 para x1 = 0, x2 = 2
 	 para x2 = 0, x1 = 2
Conclusão: Curvas de nível são retas paralelas
Propriedades
O gradiente da função z (x1, x2) será sempre perpendicular à curva de nível
Resolver graficamente o sistema:
Ax < b
Sendo: A = 2 0 X = x1 e b = 4
 0 4 x2 8
 0 
 0
Solução: 
		Ax < b
	2 0 x1 < 4 ( 2 x1 < 4
 0 4 x2 8 4 x2 8
 -1 0 0 - x1 0
 0 -1 0 - x2 0
 
	2 x1 < 4
 	4 x2 < 8
	- < 0
	- x2 < 0
Qualquer solução viável deve estar dentro deste quadrado
Por analogia: x1 < 2
			x2 < 2
			x3 < 2
			x1 > 0
			x2 > 0
			x3 > 0
A = (2,2,0) ; B = (2,2,2) ; C = (0,2,2) ; D = (2,0,2)
Data: 01/03/10
PPL = Problema de Programação Linear
	Forma canônica
	Otimizar xo= CTX
	SA
	 Ax (<, >) d
	 X > 0
Forma Padrão
	Min z = CTX
	SA
	Ax = d
	x > 0
	d > 0
Exemplos de Forma Padrão
	Dado o PPL, encontre a forma padrão:
	Max z = 2 x1 + 3 x2
	SA
	 5 x1 + 2 x2 < 100
	 4 x1 + 3 x2 < 120
	 x1, x2 > 0
	Sua Forma Padrão será:
	Min z = -2 x1 - 3 x2
	SA
	 5 x1 + 2 x2 + x3 = 100
	 4 x1 + 3 x2 + x4 = 120
	 x1, x2, x3, x4 > 0
	Quadro Simplex Tableaux
	VB
	X1
	X2
	X3
	X4
	 
	X1
	5
	2
	1
	0
	100
	X2
	4
	3
	0
	1
	120
	F.O.
	-2
	-3
	0
	0
	 
Vb significa variáveis básicas
Base é a matriz identidade
	1 0
 0 1
Assim, x3 e x4 são as Vb.
01) Resolver o Sistema:
A) 2 x1 + 5 x2 < 100
 x1, x2 > 0
	2 x1 + 5 x2 = 100 (reta)
para x1 = 0, x2 = 20
	para x2 = 0, x1 = 50
B) 2 x1 + 2 x2 + 2 x3 < 100
 x1, x2, x3 > 0
	para x1 e x2 = 0, x3 = 50
	para x1 e x3 = 0, x2= 50
	para x2 e x3 = 0, x1 = 50
C) 2 x2 + x3 < 10
 x1 < 20
 x1, x2, x3 > 0
para x2 = 0, x3 = 10
	para x3 = 0, x2= 5
	Vértices
	A = (20,0,10)
	B = (20,5,0)
	C = (20,0,0)
	D = (0,0,10)
	E = (0,5,0)
	O = (0,0,0)
Data: 03/03/10
Exemplo 01 - Sítio
Trigo, Arroz e Milho
	Cultura
	Produtividade (Kg/m²)
	Lucro
	Trigo (x1)
	0,2
	10,8 centavos
	Arroz (x2)
	0,3
	4,2 centavos
	Milho (x3)
	0,4
	2,03 centavos
Produção máxima: 60 toneladas
Área: 200.000m²
Demandas: Trigo: 400m²
	 Arroz: 800m²
	 Milho: 10000m²
Modelagem Dados de Sistema
1º Função Objetivo
	Maximizar lucro
	10,8 x 0,2 x1
	4,2 x 0,3 x2
	2,03 x 0,4 x3
	Restrições:
	x1 > 400
	x2 > 800
	x3 > 10000
	x1, x2, x3 > 0
Exemplo 02
Deseja-se simular a produção de uma liga de níquel a base de aço e latão. A liga deve ter no mínimo 6% de níquel e um peso de 100 toneladas. Simular a liga de mínimo custo.
	Recursos
	% Níquel
	Disponibilidade
	Custo / ton
	Aço (X1)
	8
	50 ton
	1800
	Latão (X2)
	4
	80 ton
	1200
FO: Mínimo Custo ( 1800x1 + 1200x2
Restrições: x1 < 50
	 x2 < 80
	 x1 + x2 = 100
	 0,08x1 + 0,04x2 > 6
	 x1, x2 > 0
Exemplo 03
Uma empresa possui um estoque de produtos conforme abaixo:
	Produto
	Peso (ton)
	Ganho ($/ton)
	P1
	20
	4
	P2
	25
	4
	P3
	30
	5
	P4
	10
	2
	P5
	40
	6
Um veículo comporta no máximo 80 toneladas. Quais produtos transportar a fim de obter o melhor ganho total?
FO: Custo mínimo ( 4x1 + 4x2 + 5x3 + 2x4 + 6x5
AS
 20x1 + 25x2 + 30x3 + 10x4 + 40x5 < 80
	 X1 < 1
	 X2 < 1
	 X3 < 1
	 X4 < 1
	 X5 < 1X1, x2, x3, x4, x5 > 0
Data: 10/03/10
Utilização do MatLab
Lembrete: Todo programa MatLab deve utilizar função objetivo para mínimo
01) Resolver: Máx z = 10x1 + 10x2
 SA:
	 200x1 + 100x2 < 500
		 x1 > 0
		 x2 > 0
	Solução: Min f = (-10 -10) x1
					 x2
		 AS: (200 100) x1 < 500
 x2
		 x1 > 0
 x2
	Passos MatLab:
	- Montar um Script
	- Arquivo ( Novo ( M-File
	- Colocar comentário ( % TESTE PPL1
	- Digitar a função objetivo ( f = [-10; -10]
	- Digitar as restrições ( A = [200 100]
	 b = [500]
	- limite inferior ( lb = zeros (2,1)
	- Acionamento do comando para o Simplex:
	 [x,fval,flag,output,lambda] = linprog(f,A,b,[],[],lb)
	- Salvar
	- Minimizar a área e no MatLab digitar o nome do arquivo salvo.
02) Resolver: Máx z = 20x1 + 10x2
 SA:
	 200x1 + 100x2 < 500
	 100x1 + 200x2 < 500
		 x1 > 0
		 x2 > 0
	MatLab
	% Teste PPL2
	% Vetor FO
	F = [-20 ; -10]
	% Matriz da restrição
	A = [ 200 100; 100 200]
	% Vetores termos independentes
	B = [500 600]
	% Vetor limites inferiores
	Lb = zeros (2,1) 
 [x,fval,flag,output,lambda] = linprog(f,A,b,[],[],lb)
Data: 15/03/10
03) Resolver PPL: Máx z = x1 + x2
 SA:
	 	 2x1 + 5x2 < 200
			 x1 > 0
			 x2 > 0
	1º Curvas de Nível
	x1 + x2 = constante 10
 20
	2º Região Viável
	2x1 + 5x2 = 200 (reta)
	Para x1 = 0, x2 = 40
	Para x2 = 0, x1 = 100
	3º Pontos permitidos
	
	Resposta: x1 = 100
		 x2 = 0
 f = 100
Resolução do problema no MatLab
	% Teste PPL
	f = [-1 ; -1]
	A = [2 5]
	b = [200]
	lb = zeros (2,1)
	[x,fval,flag,output,lambda] = linprog(f,A,b,[],[],lb)
02) Resolver PPL: 	Máx z = 2x1 + 5x2 + 2x3
 SA:
	 	 x1 > 10
			 x2 + x3 < 20
			 x1, x2, x3 > 0
	Problema sem solução ótima!
	Resolução no MatLab
	f = [-2; -5; -2]
	A = [1 0 0; 0 1 1]
	b = [20;10]
	lb = zeros (3,1)
	[x,fval,flag,output,lambda] = linprog(f,A,b,[],[],lb)
	Problema sem solução ótima!
03) Resolver PPL: Máx z = 2x3
 SA:
	 	 2x1 + 4x2 = 100
			 X1 + 5x2 = 200
			 x1 + 2x2 + 4x3 < 400
 x1, x2, x3 > 0
	
	Resolução no MatLab
% Teste PPL5
	f = [0; 0; -2]
	Aeq = [2 4 0; 1 5 0]
	A = [1 2 4]
	beq = [100; 200]
	b = [400]
	lb = zeros (3,1)
	[x,fval,flag,output,lambda] = linprog(f,A,b,Aeq,beq,lb)
Data 17/03/10
Revisão PPL
	Max f = CTx
	SA
	 Ax < b
 	 x > 0
	Passo a Passo:
	1º Curvas de Nível da função objetivo	
		F = constante (2 valores)
		 f _|_ curva de nível
	2º Região Viabilidade
	 Gráfico região de viabilidade (intercessão das restrições)
	3º Conclusão
	 Encontrar o ponto ótimo
	 (Montar um gráfico só)
Casos
01) Ponto Ótimo 02) Ilimitado 03) Inviável
Exercício: Encontrar todos os vértices
	
Min x1
	As
	 x1 + x2 < 100
	 x1 – x2 < 50
 x1, x2 > 0
	
Resolução:
	Min x1
	X1 + x2 + x3 = 100
	X1 – x2 + x4 = 50
	N = 4
	M = 2
N – M = 4 – 2 = 2 (Zerar duas variáveis para encontrar todas as possibilidades.
 
	Vértice 01
	Vértice 02
	Vértice 03
	x1 = x2 = 0
	x2 = x4 = 0
	x2 = x3 = 0
	x3 = 100
	x1 = 50
	x1 = 100
	x4 = 50
	x3 = 50
	x4 = -50
	
	
	
	
	
	
	Vértice 04
	Vértice 05
	Vértice 06
	x1 = x3 = 0
	x1 = x4 = 0
	x4 = x3 = 0
	x2 = 100
	x2 = -50 (*)
	x1 = 75
	x4 = 150
	x3 = 150
	x2 = 25
(*) Ponto fora da região viável
-50
O Máximo é infinito. Sem Solução!
50
Região Viável
100
100
Informação:
>> help linprog
Min f’*x
Ax < b
Aeqx = beq
C 4,2 = 4 = 4! = 6 (vértices)
 2 2! (4 – 2!)
Passo a Passo:
-Colocar na Forma Padrão
- Fazer todas as combinações de N variáveis, tomadas N - M
0,2 x1 + 0,3x2 + 0,4x3 < 60000
Equação linear cujo gráfico é uma reta
Restrição de não negatividade
Ponto Ótimo
�PAGE �
�PAGE �2�