Aula 05 - Método Simplex

Prévia do material em texto

Ciência da Computação
Pesquisa Operacional
Pesquisa Operacional
Professor: Fernando Stela
E-mail: fernando.stela@docente.unip.br
1
mailto:fernando.stela@docente.unip.br
Ciência da Computação
Pesquisa Operacional
Método Simples
O que é o 
método simplex
Teste de 
Otimalidade
Forma Algébrica 
e Tabular
Algoritmo 
SIMPLEX
2
Ciência da Computação
Pesquisa Operacional
Método Simplex
O método simplex é um método sequencial de otimização e pode ser empregado, 
tanto para maximizar como minimizar uma resposta.
Esse método é formado por um grupo de critérios para escolha de soluções 
básicas que melhorem o desempenho do modelo, e também de um teste de 
otimalidade. 
Para isso o problema deve apresentar uma solução básica inicial e as soluções 
básicas subsequentes são calculadas com a troca de variáveis básicas por não 
básicas, gerando novas soluções
Ciência da Computação
Pesquisa Operacional
Breve Histórico
Foi desenvolvido por 1947 George Dantzig capaz de resolver qualquer problema de Programação 
Linear.
Desenvolvido quando Dantzig trabalhava na Rand Corporation no projeto SCOOP (Scientific 
Computation of Optimal Programs) para a Força Aérea Americana para resolver problema militares
O algoritmo simplex implica em uma quantidade muito grande de cálculos e, nos primeiros anos de 
uso, ele se apoiou exclusivamente na resolução manual.
Com o surgimento do computador em 1951, a programação linear encontrou seu aliado natural e foi 
expandido de uma maneira extraordinária.
Ciência da Computação
Pesquisa Operacional
Método Simplex
• Um procedimento para solucionar problemas de 
programação linear
• É um procedimento algébrico e utiliza conceitos geométricos
• Transforma o sistema de inequações em um sistema de 
equações
• Utiliza eliminações gaussianas
Ciência da Computação
Pesquisa Operacional
Restrições Método Simplex
6
Ciência da Computação
Pesquisa Operacional
P1 (0,0)
P2 (0,6) P3 (2,6)
P4 (4,3)
P5 (4,0)
[Max]
Z = 3x1 + 5x2
[S.A.]
X1 = 0
Ponto X1 X2 Z = 3x1 + 5x2
P1 0 0 0
P2 0 6 30
P3 2 6 36
P4 4 3 27
P5 4 0 12
Fábrica de Vidros
Para explicar o algoritmo SIMPLEX será 
utilizado o exemplo da fábrica de vidros 
visto nas aulas passadas
Ciência da Computação
Pesquisa Operacional
[Max]
Z = 3x1 + 5x2
[S.A.]
X1 = 0
Essa solução indica que a Wyndor Glass Co. deveria fabricar os produtos 1 
e 2 a uma taxa de, respectivamente, dois lotes por semana e seis lotes por 
semana, com um lucro total resultante de US$ 36 mil por semana. Nenhum 
outro mix de produtos seria tão lucrativo de acordo com o modelo.
Fábrica de Vidros
Resolução em aulas 
passadas
Ciência da Computação
Pesquisa Operacional
• O procedimento algébrico se baseia em sistemas de 
equações para solução
• Deve-se primeiro entender o conceito de variável de folga
• A primeira restrição: X1 = 0
Fábrica de Vidros – Método Simplex
Ciência da Computação
Pesquisa Operacional
Forma Algébrica e Tableau
• Transformando Inequação em Equação com variável de folga:
X1 = 0
Modelo na 
Forma 
Padrão
𝑚𝑎𝑥 𝑍 − 3𝑥1 − 5𝑥2 − 0𝑥3 − 0𝑥4 − 0𝑥5 = 0
𝑆. 𝐴.
1𝑥1 + 0𝑥2 + 1𝑥3 + 0𝑥4 + 0𝑥5 = 4
0𝑥1 + 2𝑥2 + 0𝑥3 + 1𝑥4 + 0𝑥5 = 12
3𝑥1 + 2𝑥2 + 0𝑥3 + 0𝑥4 + 1𝑥5 = 18
𝑥1, 𝑥2, 𝑥3, 𝑥4, 𝑥5 ≥ 0
Modelo 
Original
Algoritmo Simplex
Ciência da Computação
Pesquisa Operacional
Forma Tabular
Variável
Básica
Lado 
DireitoX1 X2 X3 X4 X5
Z -3 -5 0 0 0 0
x3 1 0 1 0 0 4
x4 0 2 0 1 0 12
x5 3 2 0 0 1 18
Algoritmo Simplex
Ciência da Computação
Pesquisa Operacional
Forma Tabular
Variável
Básica
Lado 
DireitoX1 X2 X3 X4 X5
x3 1 0 1 0 0 4
x4 0 2 0 1 0 12
x5 3 2 0 0 1 18
Z -3 -5 0 0 0 0
Determine a coluna pivô 
selecionando o Z mais 
negativo
Algoritmo Simplex
Ciência da Computação
Pesquisa Operacional
Forma Tabular
Variável
Básica
Lado 
DireitoX1 X2 X3 X4 X5
x3 1 0 1 0 0 4
x4 0 2 0 1 0 12
x5 3 2 0 0 1 18
Z -3 -5 0 0 0 0
Razão
12/2 = 6
18/2 = 9
Determine a 
linha pivô 
selecionando a 
menor razão
Algoritmo Simplex
Ciência da Computação
Pesquisa Operacional
Forma Tabular
Variável
Básica
Lado 
DireitoX1 X2 X3 X4 X5
x3 1 0 1 0 0 4
x4 0 2 0 1 0 12
x5 3 2 0 0 1 18
Z -3 -5 0 0 0 0
Razão
12/2 = 6
18/2 = 9
Determine a 
linha pivô 
selecionando a 
menor razão
Atenção: escolher a 
menor razão 
estritamente positiva
(>=0)
Algoritmo Simplex
Ciência da Computação
Pesquisa Operacional
Forma Tabular
Variável
Básica
Lado 
DireitoX1 X2 X3 X4 X5
x3 1 0 1 0 0 4
x4 0 2 0 1 0 12
x5 3 2 0 0 1 18
Z -3 -5 0 0 0 0
Razão
12/2 = 6
18/2 = 9
Determine a 
linha pivô 
selecionando a 
menor razão
Atenção: ignorar a 
linha da Eq. 0
Algoritmo Simplex
Ciência da Computação
Pesquisa Operacional
Forma Tabular
Variável
Básica
Lado 
DireitoX1 X2 X3 X4 X5
x3 1 0 1 0 0 4
x4 0 2 0 1 0 12
x5 3 2 0 0 1 18
Z -3 -5 0 0 0 0
Razão
12/2 = 6
18/2 = 9
Determine a 
linha pivô 
selecionando a 
menor razão
Atenção: ignorar se 
tiver divisão por zero
Algoritmo Simplex
Ciência da Computação
Pesquisa Operacional
Forma Tabular
Variável
Básica
Lado 
DireitoX1 X2 X3 X4 X5
x3 1 0 1 0 0 4
x4 0 2 0 1 0 12
x5 3 2 0 0 1 18
Z -3 -5 0 0 0 0
x3
x4 0 1 0 1/2 0 6
X5
Z
Iteração
0
1
Divida cada 
número da 
linha pelo
Número Pivô
Algoritmo Simplex
Ciência da Computação
Pesquisa Operacional
Forma Tabular
Variável
Básica
Lado 
DireitoX1 X2 X3 X4 X5
x3 1 0 1 0 0 4
x4 0 2 0 1 0 12
x5 3 2 0 0 1 18
Z -3 -5 0 0 0 0
x3
x2 0 1 0 1/2 0 6
x5
Z
Iteração
0
1
Algoritmo Simplex
x2 substitui x4 
como variável 
básica para a 
linha2
Ciência da Computação
Pesquisa Operacional
Forma Tabular
Variável
Básica
Lado 
DireitoX1 X2 X3 X4 X5
x3 1 0 1 0 0 4
x4 0 2 0 1 0 12
x5 3 2 0 0 1 18
Z -3 -5 0 0 0 0
x3
x2 0 1 0 1/2 0 6
x5
Z
Iteração
0
1
Eliminação Gaussiana:
Utilize operações 
elementares em linhas, 
multiplique ou divida 
uma linha por uma 
constante não-zero; 
adicione ou subtraia um 
múltiplo de uma linha 
para outra
Veja mais detalhes em:
https://www.ufrgs.br/rea
mat/CalculoNumerico/li
vro-sci/sdsl-
eliminacao_gaussiana.h
tml
Algoritmo Simplex
https://www.ufrgs.br/reamat/CalculoNumerico/livro-sci/sdsl-eliminacao_gaussiana.html
https://www.ufrgs.br/reamat/CalculoNumerico/livro-sci/sdsl-eliminacao_gaussiana.html
https://www.ufrgs.br/reamat/CalculoNumerico/livro-sci/sdsl-eliminacao_gaussiana.html
https://www.ufrgs.br/reamat/CalculoNumerico/livro-sci/sdsl-eliminacao_gaussiana.html
https://www.ufrgs.br/reamat/CalculoNumerico/livro-sci/sdsl-eliminacao_gaussiana.html
Ciência da Computação
Pesquisa Operacional
Forma Tabular
Variável
Básica
Lado 
DireitoX1 X2 X3 X4 X5
x3 1 0 1 0 0 4
x4 0 2 0 1 0 12
x5 3 2 0 0 1 18
Z -3 -5 0 0 0 0
x3
x2 0 1 0 1/2 0 6
x5
Znew -3 0 0 5/2 0 30
Iteração
0
1
Algoritmo Simplex
𝑍𝑛𝑒𝑤 = 𝑥2 ∗ 5 + 𝑍
Ciência da Computação
Pesquisa Operacional
Forma Tabular
Variável
Básica
Lado 
DireitoX1 X2 X3 X4 X5
x3 1 0 1 0 0 4
x4 0 2 0 1 0 12
x5 3 2 0 0 1 18
Z -3 -5 0 0 0 0
x3 1 0 1 0 0 4
x2 0 1 0 1/2 0 6
x5
Z -3 0 0 5/2 0 30
Iteração
0
1
Algoritmo Simplex
𝑥3 = 𝑥2 ∗ 0 + 𝑥3
Ciência da Computação
Pesquisa Operacional
Forma Tabular
Variável
Básica
Lado 
DireitoX1 X2 X3 X4 X5
x3 1 01 0 0 4
x4 0 2 0 1 0 12
x5 3 2 0 0 1 18
Z -3 -5 0 0 0 0
x3 1 0 1 0 0 4
x2 0 1 0 1/2 0 6
x5 3 0 0 -1 1 6
Z -3 0 0 5/2 0 30
Iteração
0
1
Algoritmo Simplex
𝑥5 = 𝑥2 ∗ −2 + 𝑥5
Ciência da Computação
Pesquisa Operacional
Forma Tabular
Variável
Básica
Lado 
DireitoX1 X2 X3 X4 X5
x3 1 0 1 0 0 4
x4 0 2 0 1 0 12
x5 3 2 0 0 1 18
Z -3 -5 0 0 0 0
x3 1 0 1 0 0 4
x2 0 1 0 1/2 0 6
X5 3 0 0 -1 1 6
Z -3 0 0 5/2 0 30
Iteração
0
1
Terminei a iteração pois o objetivo é 
transformar o número pivô em 1 e os 
outros números da coluna em 0
Algoritmo Simplex
Ciência da Computação
Pesquisa Operacional
Forma Tabular
Variável
Básica
Lado 
DireitoX1 X2 X3 X4 X5
x3 1 0 1 0 0 4
x4 0 2 0 1 0 12
x5 3 2 0 0 1 18
Z -3 -5 0 0 0 0
x3 1 0 1 0 0 4
x2 0 1 0 1/2 0 6
x5 3 0 0 -1 1 6
Z -3 0 0 5/2 0 30
Iteração
0
1
Determine a coluna pivô 
selecionando o Z mais 
negativo
Algoritmo Simplex
Ciência da Computação
Pesquisa Operacional
Forma Tabular
Variável
Básica
Lado 
DireitoX1 X2 X3 X4 X5
x3 1 0 1 0 0 4
x4 0 2 0 1 0 12
x5 3 2 0 0 1 18
Z -3 -5 0 0 0 0
x3 1 0 1 0 0 4
x2 0 1 0 1/2 0 6
x5 3 0 0 -1 1 6
Z -3 0 0 5/2 0 30
Iteração
0
1
Razão
4/1 = 4
6/3 = 2
Determine a 
linha pivô 
selecionando a 
menor razão
Algoritmo Simplex
Ciência da Computação
Pesquisa Operacional
Forma Tabular
Variável
Básica
Lado 
DireitoX1 X2 X3 X4 X5
x3 1 0 1 0 0 4
x4 0 2 0 1 0 12
x5 3 2 0 0 1 18
Z -3 -5 0 0 0 0
x3 1 0 1 0 0 4
X2 0 1 0 1/2 0 6
X5 3 0 0 -1 1 6
Z -3 0 0 5/2 0 30
X1 1 0 0 -1/3 1/3 2
Z
Iteração
0
1
2
Dividimos a 
linha 3 pelo 
número pivô (3)
Algoritmo Simplex
Razão
4/1 = 4
6/3 = 2
Ciência da Computação
Pesquisa Operacional
Forma Tabular
Variável
Básica
Lado 
DireitoX1 X2 X3 X4 X5
x3 1 0 1 0 0 4
x4 0 2 0 1 0 12
x5 3 2 0 0 1 18
Z -3 -5 0 0 0 0
x3 1 0 1 0 0 4
X2 0 1 0 1/2 0 6
X5 3 0 0 -1 1 6
Z -3 0 0 5/2 0 30
X1 1 0 0 -1/3 1/3 2
Znew 0 0 0 3/2 1 36
Iteração
0
1
2
Revisão de Cálculo com Frações:
-1 + 5/2 = ?
5/2 - 1 = 
5/2 - 1/1 = 
5/2 - 2/2 = 
3/2
Algoritmo Simplex
𝑍𝑛𝑒𝑤 = 𝑥1 ∗ 3 + 𝑍
Ciência da Computação
Pesquisa Operacional
Forma Tabular
Variável
Básica
Lado 
DireitoX1 X2 X3 X4 X5
x3 1 0 1 0 0 4
x4 0 2 0 1 0 12
x5 3 2 0 0 1 18
Z -3 -5 0 0 0 0
x3 1 0 1 0 0 4
X2 0 1 0 1/2 0 6
X5 3 0 0 -1 1 6
Z -3 0 0 5/2 0 30
X2 0 1 0 1/2 0 6
X1 1 0 0 -1/3 1/3 2
Z 0 0 0 3/2 1 36
Iteração
0
1
2
Algoritmo Simplex
𝑥2 = 𝑥1 ∗ 0 + 𝑥2
Ciência da Computação
Pesquisa Operacional
Forma Tabular
Variável
Básica
Lado 
DireitoX1 X2 X3 X4 X5
x3 1 0 1 0 0 4
x4 0 2 0 1 0 12
x5 3 2 0 0 1 18
Z -3 -5 0 0 0 0
x3 1 0 1 0 0 4
X2 0 1 0 1/2 0 6
X5 3 0 0 -1 1 6
Z -3 0 0 5/2 0 30
X3 0 0 1 1/3 -1/3 2
X2 0 1 0 1/2 0 6
X1 1 0 0 -1/3 1/3 2
Z 0 0 0 3/2 1 36
Iteração
0
1
2
Algoritmo Simplex
𝑥3 = 𝑥1 ∗ −1 + 𝑥3
Ciência da Computação
Pesquisa Operacional
Forma Tabular
Variável
Básica
Lado 
DireitoX1 X2 X3 X4 X5
x3 1 0 1 0 0 4
x4 0 2 0 1 0 12
x5 3 2 0 0 1 18
Z -3 -5 0 0 0 0
x3 1 0 1 0 0 4
X2 0 1 0 1/2 0 6
X5 3 0 0 -1 1 6
Z -3 0 0 5/2 0 30
X3 0 0 1 1/3 -1/3 2
X2 0 1 0 1/2 0 6
X1 1 0 0 -1/3 1/3 2
Z 0 0 0 3/2 1 36
Iteração
0
1
2
Algoritmo Simplex
Ciência da Computação
Pesquisa Operacional
Forma Tabular
Variável
Básica
Lado 
DireitoX1 X2 X3 X4 X5
x3 1 0 1 0 0 4
x4 0 2 0 1 0 12
x5 3 2 0 0 1 18
Z -3 -5 0 0 0 0
x3 1 0 1 0 0 4
X2 0 1 0 1/2 0 6
X5 3 0 0 -1 1 6
0 0 0 5/2 0 30 0
X3 0 0 1 1/3 -1/3 2
X2 0 1 0 1/2 0 6
X1 1 0 0 -1/3 1/3 2
Z 0 0 0 3/2 1 36
Iteração
0
1
2
Algoritmo Simplex
𝑥2 = 6
𝑥1 = 2
𝑍 𝑚𝑎𝑥 = 36
	Slide 1: Pesquisa Operacional
	Slide 2: Método Simples
	Slide 3: Método Simplex
	Slide 4: Breve Histórico
	Slide 5: Método Simplex
	Slide 6: Restrições Método Simplex
	Slide 7
	Slide 8
	Slide 9: Fábrica de Vidros – Método Simplex
	Slide 10: Forma Algébrica e Tableau
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32