Método Simplex

Prévia do material em texto

MOQ – 43
PESQUISA 
OPERACIONAL
Professor: Rodrigo A. Scarpel
rodrigo@ita.br
www.mec.ita.br/~rodrigo
Programa do curso:
Semana Conteúdo
1 Apresentação da disciplina. Formulação em programação matemática (PM).
2
Introdução à Programação Linear. (PL) Resolução de problemas de PL pelo Método Gráfico. Introdução ao
método simplex para resolução de PPL .
3 Resolução de problemas de PL pelo Método Simplex. A matemática do método simplex.
4
Problemas com soluções iniciais (Método das 2 fases e o Big-M). Degeneração, ciclagem e convergência do
método simplex.
5 Análise de Sensibilidade. Resolução computacional de problemas de programação matemática.
6 Prova
7
O problema dual. Formulação e Interpretação econômica do problema dual. Teoremas da dualidade. Algoritmos
simplex adicionais. Análise pós-otimização.
8 Correção da prova. Princípios de programação multiobjetivo.
9 O Problema do Transporte.
10 O problema do Transbordo. O problema da Designação.
11 Programação Linear Inteira: Formulação, Método de Branch and Bound. Problemas de otimização combinatória.
12 Prova
13
Otimização em Redes. O problema do caixeiro viajante e do carteiro chinês. Os problemas do caminho mínimo e
do fluxo máximo.
14 Introdução à programação não-linear e aos métodos não exatos para resolução de problemas de PM.
15 Princípios de otimização global.
16 Correção da prova. Fechamento do curso.
MOQ – 43
PL – RESOLUÇÃO 
PELO MÉTODO 
SIMPLEX
Professor: Rodrigo A. Scarpel
rodrigo@ita.br
www.mec.ita.br/~rodrigo
Método / Algoritmo simplex:
O Simplex é um algoritmo (seqüência finita de instruções que termina em 
um número finito de operações) que faz uso de um ferramental baseado 
em álgebra linear para determinar, por um método iterativo, a solução 
ótima de um PPL.
Princípio do algoritmo:
Já vimos que a solução ótima de um PPL é um ponto extremo (solução 
básica viável).
Em grandes problemas o número de pontos extremos pode ser muito 
grande.
Como evitar o teste de todas as soluções viáveis básicas possíveis 
para garantir a otimização do sistema?
Problema de mix de produção: Ilustração
Lucro unitário: porta de madeira: R$4,00
porta de alumínio: R$6,00
 Corte Montagem Acabamento 
Madeira 1,5 h/porta 3,0 h/porta 1 h/porta 
Alumínio 4,0 h/porta 1,5 h/porta 1 h/porta 
Disponibilidade 24 h 21 h 8,75 h 
 
h
FO: Maximizar Z = 4,0*xmadeira + 6,0*xalumínio
S.A. 1,5*xmadeira + 4,0*xalumínio  24
3,0*xmadeira + 1,5*xalumínio  21
1,0*xmadeira + 1,0*xalumínio  8
xmadeira, xalumínio  0
1,5x1+ 4,0x2+ 1x3 = 24
3,0x1+ 1,5x2 + 1x4 = 21
1,0x1+ 1,0x2 + 1x5 = 8
x1, x2, x3 , x4 , x5  0
Método Simplex – Passos:
x15 10 15
x
2
5
1
0
FO: Maximizar Z = 4,0*x1 + 6,0*x2
S.A. 1,5x1+ 4,0x2+ 1x3 = 24
3,0x1+ 1,5x2 + 1x4 = 21
1,0x1+ 1,0x2 + 1x5 = 8
x1, x2, x3 , x4 , x5  0
Método simplex – forma tabular (Problema de Maximização):
FO: Max Z= 4,0*xmadeira + 6,0*xalumínio Max Z -4,0*x1-6,0*x2+0*x3+0*x4+0*x5 
=0
S.A. 1,5*xmadeira + 4,0*xalumínio  24
3,0*xmadeira + 1,5*xalumínio  21
1,0*xmadeira + 1,0*xalumínio  8
xmadeira, xalumínio  0
1,5x1+ 4,0x2+ 1x3 = 24
3,0x1+ 1,5x2 + 1x4 = 21
1,0x1+ 1,0x2 + 1x5 = 8
x1, x2, x3 , x4 , x5  0
Z x1 x2 x3 x4 x5 RHS 
1 -4 -6 0 0 0 0 
x3 1,5 4 1 0 0 24 
x4 3 1,5 0 1 0 21 
x5 1 1 0 0 1 8 
 
Z x1 x2 x3 x4 x5 RHS 
1 -4 -6 0 0 0 0 
x3 1,5 4 1 0 0 24 
x4 3 1,5 0 1 0 21 
x5 1 1 0 0 1 8 
 
Método Simplex – Forma Tabular:
= 24/4 = 6
= 21/1,5 = 14 
= 8/1 = 8 Z x1 x2 x3 x4 x5 RHS 
1 -7/4 0 3/2 0 0 36 
x2 3/8 1 1/4 0 0 6 
x4 39/16 0 -3/8 1 0 12 
x5 5/8 0 -1/4 0 1 2 
 
xmadeira(x1) 5
x
a
lu
m
ín
io
(x
2
)
5
Método Simplex – Forma Tabular:
Z x1 x2 x3 x4 x5 RHS 
1 -7/4 0 3/2 0 0 36 
x2 3/8 1 1/4 0 0 6 
x4 39/16 0 -3/8 1 0 12 
x5 5/8 0 -1/4 0 1 2 
 
= 6/0,375 = 16
= 12/2,44 = 4,9 
= 2/0,625 = 3,2 Z x1 x2 x3 x4 x5 RHS 
1 0 0 4/5 0 14/5 208/5 
x2 0 1 2/5 0 -3/5 24/5 
x4 0 0 3/5 1 -39/10 21/5 
x1 1 0 -2/5 0 8/5 16/5 
 
xmadeira(x1) 5
x
a
lu
m
ín
io
(x
2
)
5  Solução ótima:
x1 (madeira) = 16/5 = 3,2
x2 (alumínio) = 24/5 = 4,8
Lucro = 208/5 = 41,6
Método Simplex – Formalização (Problema de Maximização):
Inicialização:
Encontrar uma solução básica viável ( B).
Passo principal:
Seja zk - ck = Mínimo {zj - cj: j  R}. Se zk - ck  0 pare - a solução é ótima.
Caso contrário examine yk.
Se yk  0 pare – a solução ótima é ilimitada. 
Se yk  0 determine o índice r como:
Atualize o tableau pivotando em yik (atualize as variáveis básicas e as não 
básicas com xk que entra na base e xi que sai).
Repita o passo principal








0:
1
ik
ik
i
mi
y
y
b
Minimor
Método Simplex para problemas de minimização:
ALTERNATIVAS:
1. RESOLVER COMO UM PROBLEMA DE MAXIMIZAÇÃO DE - Z
FO: MIN Z = 2*x1 - 3*x2 MAX -Z = -2*x1 + 3*x2
S.A. x1 + x2  4
x1 - x2  6
x1, x2  0
X1 X2 X3 X4 RHS
Z 2 -3 0 0 0
X3 1 1 1 0 4
X4 1 -1 0 1 6
Z 5 0 3 0 12
X3 1 1 1 0 4
X4 2 0 1 1 10
COMO – Z=12  Z= – 12
Método Simplex para problemas de minimização:
ALTERNATIVAS:
2. MODIFICAR O MÉTODO SIMPLEX
Inicialização:
Encontrar uma solução básica viável ( B).
Passo principal:
Seja zk - ck = Máximo {zj - cj: j  R}. Se zk - ck  0 pare - a solução é ótima.
Caso contrário examine yk. 
Se yk  0 pare – a solução ótima é ilimitada. 
Se yk  0 determine o índice r como:
Atualize o tableau pivotando em yik (atualize as variáveis básicas e as não 
básicas com xk que entra na base e xi que sai).
Repita o passo principal








0:
1
ik
ik
i
mi
y
y
b
Minimor
X1 X2 X3 X4 RHS
Z -2 3 0 0 0
X3 1 1 1 0 4
X4 1 -1 0 1 6
Z -5 0 -3 0 -12
X3 1 1 1 0 4
X4 2 0 1 1 10
FO: MIN Z = 2*x1 - 3*x2 
S.A. x1 + x2  4
x1 - x2  6
x1, x2  0
Método Simplex para problemas de minimização:
ALTERNATIVAS:
2. MODIFICAR O MÉTODO SIMPLEX
Condições especiais – múltiplas soluções ótimas:
Maximizar Lucro = Z = 6,0*xmadeira + 6,0*xalumínio Z x1 x2 x3 x4 x5 RHS 
1 -6 -6 0 0 0 0 
x3 1,5 4 1 0 0 24 
x4 3 1,5 0 1 0 21 
x5 1 1 0 0 1 8 
 
xmadeira
x
a
lu
m
ín
io
6
6
Z x1 x2 x3 x4 x5 RHS 
1 -15/4 0 3/2 0 0 36 
x2 3/8 1 1/4 0 0 6 
x4 39/16 0 -3/8 1 0 12 
x5 5/8 0 -1/4 0 1 2 
 
Z x1 x2 x3 x4 x5 RHS 
1 0 0 0 0 6 48 
x2 0 1 2/5 0 -3/5 24/5 
x4 0 0 3/5 1 -39/10 21/5 
x1 1 0 -2/5 0 8/5 16/5 
 
Z x1 x2 x3 x4 x5 RHS 
1 0 0 0 0 6 48 
x2 0 1 0 -2/3 2 2 
x3 0 0 1 5/3 -13/2 7 
x1 1 0 0 2/3 -1 6 
 
 x1 x2 x3 x4 RHS 
Z -1 -1 0 0 0 
x3 0 1 1 0 2 
x4 -1 2 0 1 4 
 
Casos – Solução ilimitada:
x2
5
5
x1
Max Z= x1 + x2 Max Z - x1 - x2 = 0
S.A. x2  2
-x1 + 2x2  4
x1, x2  0
1x2 + x3 = 2
-x1 + 2x2 + x4 = 4
x1, x2  0
 x1 x2 x3 x4 RHS 
z -1 0 -1 0 -2 
x2 0 1 1 0 2 
x4 -1 0 -2 1 0 
 
MOQ – 43
A MATEMÁTICA DO 
MÉTODO SIMPLEX
Professor: Rodrigo A. Scarpel
rodrigo@ita.br
www.mec.ita.br/~rodrigo
FO: Maximizar Z = 4,0*xmadeira + 6,0*xalumínio
S.A. 1,5*xmadeira + 4,0*xalumínio  24
3,0*xmadeira + 1,5*xalumínio  21
1,0*xmadeira + 1,0*xalumínio  8
xmadeira, xalumínio  0
1,5x1+ 4,0x2+ 1x3 = 24
3,0x1+ 1,5x2 + 1x4 = 21
1,0x1+ 1,0x2 + 1x5 = 8
x1, x2, x3 , x4 , x5  0
Maximizar cTx
S.A. Ax=b, x0











10011
0105,13
00145,1
A











821
24
b,

















5
4
3
2
1
x
x
x
x
x
x
,

















0
0
0
6
4
c
,
A matemática do método simplex:











10011
0105,13
00145,1
A











8
21
24
b,

















5
4
3
2
1
x
x
x
x
x
x
,

















0
0
0
6
4
c
,
B R
Em cada iteração:
xB = B
-1.b
cB
w = cB
T.B-1
z = w.b = cB.B
-1.b
zj - cj = w.aj - cj
yk = B
-1. ak
A matemática do método simplex:
A matemática do método simplex:
 x1 x2 x3 x4 x5 RHS 
Z -4 -6 0 0 0 0 
x3 1,5 4 1 0 0 24 
x4 3 1,5 0 1 0 21 
x5 1 1 0 0 1 8 
 
Tableau inicial
B-1 B-1.b
w
Base: x3, x4 e x5











10011
0105,13
00145,1
A
,
























100
010
001
100
010
001
1
1B











0
0
0
bc































 
8
21
24
8
21
24
 
100
010
001
1bBxB
   000
100
010
001
0001 










 Bcw
T
b
Z = w b = 0
w.b
 
 002/3
104/1
018/3
004/1
0061












 
w
Bcw
T
b
Z x1 x2 x3 x4 x5 RHS 
1 -7/4 0 3/2 0 0 36 
x2 3/8 1 1/4 0 0 6 
x4 39/16 0 -3/8 1 0 12 
x5 5/8 0 -1/4 0 1 2 
 
A matemática do método simplex:
Após 1 iteração
B-1 B-1.b
w
Base: x2, x4 e x5
,

























104/1
018/3
004/1
101
012/3
004
1
1B











0
0
6
bc 































 
2
12
6
8
21
24
 
104/1
018/3
004/1
1bBxB
Z = w b = 36











10011
0105,13
00145,1
A
w.b
Tableau final Z x1 x2 x3 x4 x5 RHS 
1 0 0 4/5 0 14/5 208/5 
x2 0 1 2/5 0 -3/5 24/5 
x4 0 0 3/5 1 -39/10 21/5 
x1 1 0 -2/5 0 8/5 16/5 
 B-1 B-1.b
w.b
w
A matemática do método simplex:
 
 8,208,0
5/805/2
9,315/3
5/305/2
4061














 
w
Bcw
T
b
Base: x2, x4 e x1
,



























5/805/2
9,315/3
5/305/2
101
312/3
2/304
1
1B











4
0
6
bc


































 
2,3
2,4
8,4
8
21
24
 
5/805/2
9,315/3
5/305/2
1bBxB
Z = w b = 41,6











10011
0105,13
00145,1
A
Para casa:
• Leitura Taha: 3.1, 3.2, 3.3, 3.5.2, 3.5.3 e 7.1
Winston: 4.3 a 4.8
• Lista de Exercícios 3
OBSERVAÇÃO
Este material refere-se às notas de aula do curso 
MOQ-43 (Pesquisa Operacional) do Instituto 
Tecnológico de Aeronáutica (ITA). Não substitui o 
livro texto, as referências recomendadas e nem as 
aulas expositivas. Este material não pode ser 
reproduzido sem autorização prévia do autor. 
Quando autorizado, seu uso é exclusivo para 
atividades de ensino e pesquisa em instituições 
sem fins lucrativos.