Método Simplex em Pesquisa Operacional

Prévia do material em texto

PESQUISA OPERACIONAL
AULA 3 – MÉTODO SIMPLEX
Tema da Apresentação
MÉTODO SIMPLEX – AULA 3
PESQUISA OPERACIONAL
Conteúdo Programático
1. Definição 
2. Método Simplex
3. Desenvolvimento do método
4. Exemplo
Tema da Apresentação
MÉTODO SIMPLEX – AULA 3
PESQUISA OPERACIONAL
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.
Tema da Apresentação
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).
Tema da Apresentação
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
Tema da Apresentação
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. 
Tema da Apresentação
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
Tema da Apresentação
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
Tema da Apresentação
MÉTODO SIMPLEX – AULA 3
PESQUISA OPERACIONAL
PASSO 2: PASSAR A FORMA PADRÃO PARA O TABLEAU
Tema da Apresentação
MÉTODO SIMPLEX – AULA 3
PESQUISA OPERACIONAL
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.
Tema da Apresentação
MÉTODO SIMPLEX – AULA 3
PESQUISA OPERACIONAL
Tema da Apresentação
MÉTODO SIMPLEX – AULA 3
PESQUISA OPERACIONAL
Tema da Apresentação
MÉTODO SIMPLEX – AULA 3
PESQUISA OPERACIONAL
Tema da Apresentação
MÉTODO SIMPLEX – AULA 3
PESQUISA OPERACIONAL
O quadro é ótimo.
Z=36 x1=2 x2=6 x3=2 x4=0 x5=0
Tema da Apresentação
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
Tema da Apresentação
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
Tema da Apresentação
MÉTODO SIMPLEX – AULA 3
PESQUISA OPERACIONAL
Z=5800 x1=40 x2=10 x3=0 x4=20 x5=0
EXEMPLO 1 
Tema da Apresentação
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. 
Tema da Apresentação
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 
Tema da Apresentação
MÉTODO SIMPLEX – AULA 3
PESQUISA OPERACIONAL
EXEMPLO 2 
Z=600 x1=10 x2=0 x3=0 x4=12
Tema da Apresentação
MÉTODO SIMPLEX – AULA 3
PESQUISA OPERACIONAL
RESUMINDO
Tema da Apresentação
MÉTODO SIMPLEX – AULA 3
PESQUISA OPERACIONAL
Tema da Apresentação
FUNÇÃO LOGARÍTMICA - AULA 6
FUNÇÃO LOGARÍTMICA - AULA 6