Aula_03

Prévia do material em texto

PESQUISA OPERACIONAL
AULA 3 – MÉTODO SIMPLEX
Conteúdo Programático
1. Definição 
2. Método Simplex
3. Desenvolvimento do método
4. Exemplo
MÉTODO SIMPLEX – AULA 3
PESQUISA OPERACIONAL
FUNÇÃO LOGARÍTMICA - AULA 6
DEFINIÇÃO
	 O Método Simplex foi desenvolvido em1947 por George B. Dantzig.
 
	é uma técnica utilizada para se 	determinar numericamente a 
	solução ótima de um modelo de Programação Linear.
	O que o método simplex faz, em linhas gerais, é resolver 	diversas vezes um sistema de equações lineares para obter 	uma sucessão de soluções básicas viáveis, cada uma melhor 	do que a anterior, até se chegar a uma solução básica ótima.
MÉTODO SIMPLEX – AULA 3
PESQUISA OPERACIONAL
TEOREMAS IMPORTANTES
Vamos relembrar os teoremas que foram enunciados na ultima aula:
 Teorema 1. Se o problema de programação linear tem solução ótima, então esta solução está em, pelo menos, um ponto extremo do polígono de soluções viáveis. 
 Teorema 2. Se a região de soluções viáveis de um problema de programação linear é não vazia, então existe uma solução ótima. 
 Teorema 3. O conjunto de soluções viáveis de um problema de programação linear é um conjunto convexo.
 Teorema 4. O conjunto de soluções viáveis de um problema de programação linear tem um número finito de pontos extremos (vértices).
MÉTODO SIMPLEX – AULA 3
PESQUISA OPERACIONAL
O conjunto de todas as soluções do problema de programação linear é um conjunto convexo cujos vértices, ou seja, cujos pontos extremos correspondem a soluções ditas básicas viáveis.
Sabemos ainda que se a função objetivo possui um máximo finito, então pelo menos uma solução ótima é um ponto extremo do conjunto convexo.
OBSERVAÇÕES
MÉTODO SIMPLEX – AULA 3
PESQUISA OPERACIONAL
MÉTODO SIMPLEX
Vamos considerar o seguinte PPL.
Uma pequena metalúrgica deseja maximizar sua receita com a venda de dois tipos de finas fitas de aço que se diferenciam em qualidade no acabamento de corte. As fitas são produzidas a partir do corte de bobinas de grande largura. Existem duas máquinas em operação. Uma das máquinas é mais antiga e permite o corte diário de 4.000m de fita. A outra, mais nova, corta até 6.000m. A venda das chapas no mercado varia com a qualidade de cada uma. Fitas produzidas na máquina antiga permitem um lucro de 3 u.m por mil metros de produção. Fitas cortadas na máquina mais moderna produzem um lucro de 5 u.m por mil metros de produção. Cada mil metros de fita cortada na máquina antiga consome 3 homens x hora de mão-de-obra. Na máquina moderna são gastos apenas 2 homens x hora. Diariamente são disponíveis 18 homens x hora para a operação de ambas as máquinas. Determinar a produção que otimiza o lucro da metalúrgica. 
MÉTODO SIMPLEX – AULA 3
PESQUISA OPERACIONAL
MÉTODO SIMPLEX
Max Z = 3x1 + 5x2
Sujeito a:	
x1 ≤ 4
x2 ≤ 6
3x1 + 2x2 ≤ 18
x1 ≥ 0
x2 ≥ 0
MÉTODO SIMPLEX – AULA 3
PESQUISA OPERACIONAL
PASSO 1: ESCREVER O PPL NA FORMA PADRÃO
Max Z = 3x1 + 5x2
Sujeito a:	
x1 ≤ 4
x2 ≤ 6
3x1 + 2x2 ≤ 18
x1 ≥ 0
x2 ≥ 0
MÉTODO SIMPLEX – AULA 3
PESQUISA OPERACIONAL
PASSO 2: PASSAR A FORMA PADRÃO PARA O TABLEAU
	Forma Padrão da função objetivo
	Z - 3x1 - 5x2 = 0
	Forma Padrão das restrições
	x1 + x3 = 4
	x2 + x4 = 6
	3x1 + 2x2 + x5 = 18
	 							
	Coluna base							
								
								
								
MÉTODO SIMPLEX – AULA 3
PESQUISA OPERACIONAL
	 	Z	X1	X2	X3	X4	X5	b
	Coluna base	1	-3	-5	0	0	0	0
	X3	0	1	0	1	0	0	4
	X4	0	0	1	0	1	0	6
	X5	0	3	2	0	0	1	18
O quadro Q1 não é ótimo, pois temos na linha da função objetivo, dois valores negativos: -3 e -5. 
O quadro é ótimo quando todos os valores, nessa linha, são positivos.
Variável que entra na coluna da base: X2 (procure o menor valor numérico)
Variável que sai da coluna da base: X4 (menor valor encontrado na divisão)
Monte o próximo quadro realizando a troca acima.
MÉTODO SIMPLEX – AULA 3
PESQUISA OPERACIONAL
	 	Z	X1	X2	X3	X4	X5	b
	Coluna base							
								
								
								
	 	Z	X1	X2	X3	X4	X5	b
	Coluna base	1	-3	-5	0	0	0	0
	X3	0	1	0	1	0	0	4
	X4	0	0	1	0	1	0	6
	X5	0	3	2	0	0	1	18
MÉTODO SIMPLEX – AULA 3
PESQUISA OPERACIONAL
	 	Z	X1	X2	X3	X4	X5	b
	Coluna base	1	-3	0	0	5	0	30
	X3	0	1	0	1	0	0	4
	X2	0	0	1 	0	1	0	6
	X5 	0	3 	0	0	-2	1	6
MÉTODO SIMPLEX – AULA 3
PESQUISA OPERACIONAL
	 	Z	X1	X2	X3	X4	X5	b
	Coluna base							
								
								
								
	 	Z	X1	X2	X3	X4	X5	b
	Coluna base	1	-3	0	0	5	0	30
	X3	0	1	0	1	0	0	4
	X2	0	0	1 	0	1	0	6
	X5 	0	3 	0	0	-2	1	6
MÉTODO SIMPLEX – AULA 3
PESQUISA OPERACIONAL
	 	Z	X1	X2	X3	X4	X5	b
	Coluna base	1	0	0	0	3	1	36
	X3	0	0	0	1	2/3	-1/3	2
	X2	0	0	1	0	1	0	6
	X1 	0	1	0	0	-2/3	1/3	2
O quadro é ótimo.
Z=36 x1=2 x2=6 x3=2 x4=0 x5=0
MÉTODO SIMPLEX – AULA 3
PESQUISA OPERACIONAL
Um carpinteiro dispõe de 90, 80 e 50 metros de compensado, pinho e cedro, respectivamente. O produto A requer 2, 1 e 1 metro de compensado, pinho e cedro, respectivamente. O produto B requer 1, 2 e 1 metros, respectivamente. 
Se A é vendido por $ 120,00 e B por $ 100,00, quanto de cada produto ele deve fazer para obter um rendimento bruto máximo? 
EXEMPLO 1
MÉTODO SIMPLEX – AULA 3
PESQUISA OPERACIONAL
EXEMPLO 1 
Max Z = 120x1 + 100x2
Sujeito a:
2x1 + x2 ≤ 90 
 
x1 + 2x2 ≤ 80 
 
x1 + x2 ≤ 50 
x1 ≥ 0
x2 ≥ 0
MÉTODO SIMPLEX – AULA 3
PESQUISA OPERACIONAL
	 	Z	X1 entra	X2 	X3	X4	X5	b
	Coluna base	1	-120	-100	0	0	0	0
	X3 90/2 sai	0	2 pivô	1	1	0	0	90
	X4 80/1	0	1	2	0	1	0	80
	X5 50/1	0	1	1 	0	0	1	50
	 	Z	X1 	X2 entra	X3	X4	X5	b
	Coluna base	1	0	-40	60	0	0	5400
	X1 45/0,5	0	1	1/2	1/2	0	0	45
	X4 35/1,5	0	0	3/2	-1	1	0	35
	X2 5/0,5 sai	0	0	½ pivô	-1/2	0	1	5
	 	Z	X1	X2 	X3	X4	X5	b
	 Coluna base	1	0	0	20	0	80	5800
	X1	0	1 	0	1	0	0	40
	X4 	0	0	0	1/2	1	-3	20
	X2	0	0	1 pivô	-1	0	2	10
Z=5800 x1=40 x2=10 x3=0 x4=20 x5=0
EXEMPLO 1 
MÉTODO SIMPLEX – AULA 3
PESQUISA OPERACIONAL
EXEMPLO 2
A Esportes Radicais S.A. produz pára-quedas e asa-deltas em 2 linhas de montagem. A 1ª. linha de montagem tem 100 horas semanais disponíveis para fabricação dos produtos, e a 2ª. linha tem um limite de 42 horas semanais. Cada um dos produtos requer 10 horas de processamento na linha 1, enquanto que na linha 2 o pára-quedas requer 3 horas e a asa-delta requer 7 horas. Sabendo que o mercado está disposto a comprar toda a produção da empresa e que o lucro pela venda de cada pára-quedas é de R$ 60 e para cada asa-delta vendida é de R$ 40, encontre a programação de produção que maximize o lucro da Esportes Radicais S.A. 
MÉTODO SIMPLEX – AULA 3
PESQUISA OPERACIONAL
Max Z = 60x1 + 40x2
		
Sujeito a:
10x1 + 10x2 ≤ 100 
 
3x1 + 7x2 ≤ 42
x1 ≥ 0
x2 ≥ 0
EXEMPLO 2 
MÉTODO SIMPLEX – AULA 3
PESQUISA OPERACIONAL
EXEMPLO 2 
	 	Z	X1 entra	X2 	X3	X4	b
	Coluna base	1	-60	-40	0	0	0
	X3 100/10 sai	0	10 pivô	10	1	0	100
	X4 42/3 	0	3 	7	0	1	42
	 	Z	X1 	X2 	X3	X4	b
	Coluna base	1	0	20	6	0	600
	X1 	0	1	1	1/10	0	10
	X4 	0	0	-23	-3	1	12
Z=600 x1=10 x2=0 x3=0 x4=12
MÉTODO SIMPLEX – AULA 3
PESQUISA OPERACIONAL
RESUMINDO
MÉTODO SIMPLEX – AULA 3
PESQUISA OPERACIONAL
MÉTODO SIMPLEX – AULA 3
PESQUISA OPERACIONAL