MÉTODO SIMPLEX

Prévia do material em texto

D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Pesquisa Operacional
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Profª Drª Leoni Pentiado Godoy Prof Dr. Marcelo Battesini
leoni@smail.ufsm.br marcelo-battesini@ufsm.br
Aula 6 - Programação Linear
Solução de problemas de PL pelo 
Método Simplex
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Estrutura aula
• Solução de problemas de PL pelo Método 
Simplex
• Tabela Simplex para problemas com forma a 
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Profª Drª Leoni Pentiado Godoy Prof Dr. Marcelo Battesini
leoni@smail.ufsm.br marcelo-battesini@ufsm.br
• Tabela Simplex para problemas com forma a 
Padrão
• Algoritmo Simplex
• Solução de problemas com forma Padrão
• Exemplo
• Exercícios 
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Algoritmo Simplex: problemas com forma
Padrão
• A solução através da Tabela Simplex pode ser 
sumarizada em um conjunto de passos (algoritmo) 
–equivalentes a utilização de expressões algébrico-matriciais 
indicadas no formato padrão do Tabela Simplex
• Passo 1, montar Tabela Simplex para base inicial escolhida
–coeficientes das variáveis da f.o. na linha zero com sinal 
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Profª Drª Leoni Pentiado Godoy Prof Dr. Marcelo Battesini
leoni@smail.ufsm.br marcelo-battesini@ufsm.br
–coeficientes das variáveis da f.o. na linha zero com sinal 
invertido 
• zj-cj, como zj=0 na base inicial (cBt=0) → -cj
–valor de z=0
–coeficientes aij no LHS → aqueles das variáveis nas 
restrições da modelagem
–valores no RHS → limites das restrições da modelagem
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Algoritmo Simplex: problemas com forma
Padrão
Exemplo 1• Função Objetivo
Max z = 1*x1+1,5*x2
sujeito às restrições:
2*x1 + 2*x2 ≤ 160
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Profª Drª Leoni Pentiado Godoy Prof Dr. Marcelo Battesini
leoni@smail.ufsm.br marcelo-battesini@ufsm.br
2*x1 + 2*x2 ≤ 160
1*x1 + 2*x2 ≤ 120
4*x1 + 2*x2 ≤ 280
Sendo: x1, x2, f1, f2 e f3 ≥ 
0
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Algoritmo Simplex: problemas com forma
Padrão
Exemplo 1• Função Objetivo
Max z = 1*x1+1,5*x2
sujeito às restrições:
2*x1 + 2*x2 ≤ 160
Max z = 1*x1+1,5*x2+0*f1+0*f2+0*f3
⇒ z -1*x1- 1,5*x2- 0*f1- 0*f2- 0*f3 = 0
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Profª Drª Leoni Pentiado Godoy Prof Dr. Marcelo Battesini
leoni@smail.ufsm.br marcelo-battesini@ufsm.br
2*x1 + 2*x2 ≤ 160
1*x1 + 2*x2 ≤ 120
4*x1 + 2*x2 ≤ 280
Sendo: x1, x2, f1, f2 e f3 ≥ 
0
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Algoritmo Simplex: problemas com forma
Padrão
Exemplo 1• Função Objetivo
Max z = 1*x1+1,5*x2
sujeito às restrições:
2*x1 + 2*x2 ≤ 160
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Profª Drª Leoni Pentiado Godoy Prof Dr. Marcelo Battesini
leoni@smail.ufsm.br marcelo-battesini@ufsm.br
2*x1 + 2*x2 ≤ 160
1*x1 + 2*x2 ≤ 120
4*x1 + 2*x2 ≤ 280
Sendo: x1, x2, f1, f2 e f3 ≥ 
0
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
x2
Método Algébrico Simplex
Exercício 2Max z = 1*x1+1,5*x2
x1 x2 f1 f2 f3 RHS
z -1 -1,5 0 0 0 0
f1 2 2 1 0 0 160
f2 1 2 0 1 0 120
Passo 1
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Profª Drª Leoni Pentiado Godoy Prof Dr. Marcelo Battesini
leoni@smail.ufsm.br marcelo-battesini@ufsm.br
100
50 75 100 125 x1
2
25
25
75
50
125
Valores 
viáveis
B
A
C
f3 4 2 0 0 1 280
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Método Algébrico Simplex
Exercício 2
x1 x2 f1 f2 f3 RHS
z -1 -1,5 0 0 0 0
f1 2 2 1 0 0 160
f2 1 2 0 1 0 120
Passo 2
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Profª Drª Leoni Pentiado Godoy Prof Dr. Marcelo Battesini
leoni@smail.ufsm.br marcelo-battesini@ufsm.br
f2 1 2 0 1 0 120
f3 4 2 0 0 1 280
Escolhe a variável que entra na base: X2
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Método Algébrico Simplex
Exercício 2
x1 x2 f1 f2 f3 RHS Min Razão
z -1 -1,5 0 0 0 0
f1 2 2 1 0 0 160 160/2=80
f2 1 2 0 1 0 120 120/2=60
Passo 3
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Profª Drª Leoni Pentiado Godoy Prof Dr. Marcelo Battesini
leoni@smail.ufsm.br marcelo-battesini@ufsm.br
f34 2 0 0 1 280 280/2=140
Definida a coluna Pivô – calcular Min razão
Linha Pivô – Min Razão – L2
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Método Algébrico Simplex
Exercício 2
x1 x2 f1 f2 f3 RHS
z -1 -1,5 0 0 0 0
f1 2 2 1 0 0 160
f2 1 2 0 1 0 120
linha Pivô
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Profª Drª Leoni Pentiado Godoy Prof Dr. Marcelo Battesini
leoni@smail.ufsm.br marcelo-battesini@ufsm.br
f3 4 2 0 0 1 280
Coluna Pivô – Elemento pivô intersecção da 
coluna e linha pivô (2)
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Método Algébrico Simplex
Exercício 2
x1 x2 f1 f2 f3 RHS Operações
z -1 -1,5 0 0 0 0
f1 2 2 1 0 0 160
f2 1 2 0 1 0 120
Passo 4
v v
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Profª Drª Leoni Pentiado Godoy Prof Dr. Marcelo Battesini
leoni@smail.ufsm.br marcelo-battesini@ufsm.br
f3 4 2 0 0 1 280
x1 x2 f1 f2 f3 RHS
z
f1
x2 1/2 1 0 1/2 0 60
f3
L2 = L2/2
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Método Algébrico Simplex
Exercício 2
x1 x2 f1 f2 f3 RHS Operações
z -1 -1,5 0 0 0 0 L0 –L0+1,5L2
f1 2 2 1 0 0 160 L1= L1-2L2
f2 1 2 0 1 0 120
Passo 4
v v
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Profª Drª Leoni Pentiado Godoy Prof Dr. Marcelo Battesini
leoni@smail.ufsm.br marcelo-battesini@ufsm.br
f3 4 2 0 0 1 280 L3 = L3-2L2
x1 x2 f1 f2 f3 RHS
z -1/4 0 0 3/4 0 90
f1 1 0 1 -1 0 40
x2 ½ 1 0 1/2 0 60
f3 3 0 0 -1 1 160
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Método Algébrico Simplex
Exercício 2
x1 x2 f1 f2 f3 RHS
z -1/4 0 0 3/4 0 90
f1 1 0 1 -1 0 40
x2 ½ 1 0 1/2 0 60
Passo 4
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Profª Drª Leoni Pentiado Godoy Prof Dr. Marcelo Battesini
leoni@smail.ufsm.br marcelo-battesini@ufsm.br
f3 3 0 0 -1 1 160
Leitura Tabela Simplex na base atual:
f1= ?
x2= ?
f3= ?
z= ? ⇒ fora da base x1= ? e f1= ?
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Método Algébrico Simplex
Exercício 2
x1 x2 f1 f2 f3 RHS
z -1/4 0 0 3/4 0 90
f1 1 0 1 -1 0 40
x2 ½ 1 0 1/2 0 60
x2
125
Passo 5
↓
Retorne ao Passo 2
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Profª Drª Leoni Pentiado Godoy Prof Dr. Marcelo Battesini
leoni@smail.ufsm.br marcelo-battesini@ufsm.br
f3 3 0 0 -1 1 160
Leitura Tabela Simplex na base atual:
f1= 40
x2= 60
f3= 160
z= 90 ⇒ fora da base x1= 0 e f1= 0
100
50 75 100 125 x1
25
25
75
50
125
Valores 
viáveis
B
A
C
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Método Algébrico Simplex
Exercício 2
x1 x2 f1 f2 f3 RHS
z -1/4 0 0 3/4 0 90
f1 1 0 1 -1 0 40
x2 ½ 1 0 1/2 0 60
Passo 2
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Profª Drª Leoni Pentiado Godoy Prof Dr. Marcelo Battesini
leoni@smail.ufsm.br marcelo-battesini@ufsm.br
f3 3 0 0 -1 1 160
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Método Algébrico Simplex
Exercício 2
x1 x2 f1 f2 f3 RHS Min Razão
z -1/4 0 0 3/4 0 90
f1 1 0 1 -1 0 40 40/(1)=40
x2 ½ 1 0 1/2 0 60 60/(1/2)=120
Passo 3
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Profª Drª Leoni Pentiado Godoy Prof Dr. Marcelo Battesini
leoni@smail.ufsm.br marcelo-battesini@ufsm.br
f3 3 0 0 -1 1 160 160/(3)=53,3
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Método Algébrico Simplex
Exercício 2
x1 x2 f1 f2 f3 RHS
z -1/4 0 0 3/4 0 90
f1 1 0 1 -1 0 40
x2 ½ 1 0 1/2 0 60 linha Pivô
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Profª Drª Leoni Pentiado Godoy Prof Dr. Marcelo Battesini
leoni@smail.ufsm.br marcelo-battesini@ufsm.br
f3 3 0 0 -1 1 160
Coluna Pivô
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Método Algébrico Simplex
Exercício 2 
x1 x2 f1 f2 f3 RHS Operações
z -1/4 0 0 3/4 0 90
f1 1 0 1 -1 0 40
x2 ½ 1 0 1/2 0 60
Passo 4
v v
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Profª Drª Leoni Pentiado Godoy Prof Dr. Marcelo Battesini
leoni@smail.ufsm.br marcelo-battesini@ufsm.br
f3 3 0 0 -1 1 160
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Método Algébrico SimplexExercício 2 
x1 x2 f1 f2 f3 RHS Operações
z -1/4 0 0 3/4 0 90
f1 1 0 1 -1 0 40 L1
Nova= L1
x2 ½ 1 0 1/2 0 60
Passo 4
v v
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Profª Drª Leoni Pentiado Godoy Prof Dr. Marcelo Battesini
leoni@smail.ufsm.br marcelo-battesini@ufsm.br
f3 3 0 0 -1 1 160
x1 x2 f1 f2 f3 RHS
z
x1 1 0 1 -1 0 40
x2
f3
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Método Algébrico Simplex
Exercício 2 
x1 x2 f1 f2 f3 RHS Operações
z -1/4 0 0 3/4 0 90 L0Nova=L0+(1/4)L1
f1 1 0 1 -1 0 40 L1
Nova= L1
x2 ½ 1 0 1/2 0 60 L2
Nova=L2- (1/2)L1
Passo 4
v v
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Profª Drª Leoni Pentiado Godoy Prof Dr. Marcelo Battesini
leoni@smail.ufsm.br marcelo-battesini@ufsm.br
f3 3 0 0 -1 1 160 L3
Nova=L3- (3)L1
x1 x2 f1 f2 f3 RHS
z 0 0 1/4 1/2 0 100
x1 1 0 1 -1 0 40
x2 0 1 -1/2 1 0 40
f3 0 0 -3 2 1 40
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Método Algébrico Simplex
Exercício 2
x1 x2 f1 f2 f3 RHS
z 0 0 1/4 1/2 0 100
x1 1 0 1 -1 0 40
x2 0 1 -1/2 1 0 40
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Profª Drª Leoni Pentiado Godoy Prof Dr. Marcelo Battesini
leoni@smail.ufsm.br marcelo-battesini@ufsm.br
f3 0 0 -3 2 1 40
Leitura Tabela Simplex na base atual:
x1=?
x2=?
f3=?
z=? ⇒ fora da base f1=? e f2=?
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Método Algébrico Simplex
Exercício 2
x1 x2 f1 f2 f3 RHS
z 0 0 1/4 1/2 0 100
x1 1 0 1 -1 0 40
x2 0 1 -1/2 1 0 40
Passo 5
↓
Retorne ao Passo 2
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Profª Drª Leoni Pentiado Godoy Prof Dr. Marcelo Battesini
leoni@smail.ufsm.br marcelo-battesini@ufsm.br
f3 0 0 -3 2 1 40
Leitura Tabela Simplex na base atual:
x1=40
x2=40
f3=40
z=100⇒ fora da base f1=0 e f2=0
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Interpretação
• Produzir 40 unidades de P1 e 40 de P2 
atingindo lucro de $ 100.
• Dpto C: folga de 40 horas-homem/semana.
• Dpto. A e Dpto. B não possuem folga.
D
e
p
a
r
t
a
m
e
n
t
o
 
d
e
 
E
n
g
e
n
h
a
r
i
a
 
d
e
 
P
r
o
d
u
ç
ã
o
 
e
 
S
i
s
t
e
m
a
s
Profª Drª Leoni Pentiado Godoy Prof Dr. Marcelo Battesini
leoni@smail.ufsm.br marcelo-battesini@ufsm.br