MOQ – 43

PESQUISA
OPERACIONAL

Professor: Rodrigo A. Scarpel

rodrigo@[Link]
[Link]/~rodrigo
Programa do curso:
Semana Conteúdo

1 Apresentação da disciplina. Formulação em programação matemática (PM).

Introdução à Programação Linear. (PL) Resolução de problemas de PL pelo Método Gráfico. Introdução ao
2
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.

Problemas com soluções iniciais (Método das 2 fases e o Big-M). Degeneração, ciclagem e convergência do
4
método simplex.
5 Análise de Sensibilidade. Resolução computacional de problemas de programação matemática.
6 Prova 1
7 O problema dual. Formulação e Interpretação econômica do problema dual. Teoremas da dualidade.
8 Algoritmos simplex adicionais. Análise pós-otimização.
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
Otimização em Redes. O problema do caixeiro viajante e do carteiro chinês. Os problemas do caminho mínimo e
13
do fluxo máximo.
14 Introdução à programação não-linear.
15 Princípios de otimização global. Métodos não exatos para resolução de problemas de PM.
16 Princípios de programação multiobjetivo. Fechamento da disciplina.
MOQ – 43
PL – RESOLUÇÃO
PELO MÉTODO
SIMPLEX

Professor: Rodrigo A. Scarpel

rodrigo@[Link]
[Link]/~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

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 h h
8,75
Lucro unitário: porta de madeira: R$4,00
porta de alumínio: R$6,00

FO: Maximizar Z = 4,0*xmadeira + 6,0*xalumínio

S.A. 1,5*xmadeira + 4,0*xalumínio  24 1,5x1+ 4,0x2+ 1x3 = 24

3,0*xmadeira + 1,5*xalumínio  21 3,0x1+ 1,5x2 + 1x4 = 21
1,0*xmadeira + 1,0*xalumínio  8 1,0x1+ 1,0x2 + 1x5 = 8
xmadeira, xalumínio  0 x1, x2, x3 , x4 , x5  0
Método Simplex – Passos:

FO: Maximizar Z = 4,0*x1 + 6,0*x2

x2

S.A. 1,5x1+ 4,0x2+ 1x3 = 24

10

3,0x1+ 1,5x2 + 1x4 = 21

1,0x1+ 1,0x2 + 1x5 = 8
x1, x2, x3 , x4 , x5  0
5

5 10 15 x1
 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 1,5x1+ 4,0x2+ 1x3 = 24

3,0*xmadeira + 1,5*xalumínio  21 3,0x1+ 1,5x2 + 1x4 = 21
1,0*xmadeira + 1,0*xalumínio  8 1,0x1+ 1,0x2 + 1x5 = 8
xmadeira, xalumínio  0 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
Método Simplex – Forma Tabular:

Z x1 x2 x3 x4 x5 RHS
1 -4 -6 0 0 0 0
x3 1,5 4 1 0 0 24 = 24/4 = 6
x4 3 1,5 0 1 0 21 = 21/1,5 = 14
x5 1 1 0 0 1 8 = 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
5
xalumínio(x2)

xmadeira(x1) 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 = 6/0,375 = 16
x4 39/16 0 -3/8 1 0 12 = 12/2,44 = 4,9
x5 5/8 0 -1/4 0 1 2 = 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

 Solução ótima:
5

x1 (madeira) = 16/5 = 3,2

xalumínio(x2)

x2 (alumínio) = 24/5 = 4,8

Lucro = 208/5 = 41,6

xmadeira(x1) 5
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.
 bi 
Se yk  0 determine o índice r como: r  Minimo  : y ik  0
1i  m
 y ik 
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
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 X3 X4 RHS

x1, x2  0
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.
 bi 
Se yk  0 determine o índice r como: r  Minimo  : y ik  0
1i  m
 y ik 
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
Método Simplex para problemas de minimização:
ALTERNATIVAS:

2. MODIFICAR O MÉTODO SIMPLEX

FO: MIN Z = 2*x1 - 3*x2

S.A. x1 + x2  4
x1 - x2  6 X1 X2 X3 X4 RHS
x1, x2  0
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
 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
xalumínio

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
6 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
6 xmadeira 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
 Casos – Solução ilimitada:
x2

Max Z= x1 + x2 Max Z - x1 - x2 = 0
S.A. x2  2 1x2 + x3 =2

-x1 + 2x2  4 -x1 + 2x2 + x4 = 4

x1, x2  0
x1, x2  0
5

x1
5

x1 x2 x3 x4 RHS x1 x2 x3 x4 RHS
Z -1 -1 0 0 0 z -1 0 -1 0 -2
x3 0 1 1 0 2 x2 0 1 1 0 2
x4 -1 2 0 1 4 x4 -1 0 -2 1 0
MOQ – 43
A MATEMÁTICA DO
MÉTODO SIMPLEX

Professor: Rodrigo A. Scarpel

rodrigo@[Link]
[Link]/~rodrigo
A matemática do método simplex:
FO: Maximizar Z = 4,0*xmadeira + 6,0*xalumínio

S.A. 1,5*xmadeira + 4,0*xalumínio  24 1,5x1+ 4,0x2+ 1x3 = 24

3,0*xmadeira + 1,5*xalumínio  21 3,0x1+ 1,5x2 + 1x4 = 21
1,0*xmadeira + 1,0*xalumínio  8 1,0x1+ 1,0x2 + 1x5 = 8
xmadeira, xalumínio  0 x1, x2, x3 , x4 , x5  0
 x1   4
   
 x2  6 1,5 4 1 0 0   24 
   
   
x  x3 , c  0 , A   3 1,5 0 1 0  , b   21 
     1 1 0 0 1 8
 x4  0    
x  0
 5  

Maximizar cTx
S.A. Ax=b, x0
A matemática do método simplex:

 x1   4
   
 x2  6 1,5 4 1 0 0   24 
   
   
x  x3 , c  0 , A   3 1,5 0 1 0  , b   21 
     1 1 0 0 1 8
 x4  0    
x  0
 5  

Em cada iteração:
xB = B-1.b

w = cBT.B-1
B R
z = w.b = cB.B-1.b
zj - cj = [Link] - cj
cB
yk = B-1. ak
A matemática do método simplex:
Tableau inicial
x1 x2 x3 x4 w x5 RHS
Z -4 -6 0 0 0 0 w.b
x3 1,5 4 1 0 0 24
x4 3 1,5 0 1 0 21
x5 1 1 0 0 1 8
B-1 B-1.b
Base: x3, x4 e x5

1,5 4 1 0 0  0  1 0 0   24   24 
  c  0     
A   3 1,5 0 1 0  , b   x B  B b   0 1 0   21    21 
1

 1 1 0 0 1 0 0 0 1  8   8 
        
1 1 0 0
1 0 0 1 0 0  
    w  cb B  0 0 0 0 1 0   0 0 0
T 1
B 1  0 1 0   0 1 0 0 0 1
0 0 1 0 0 1  
    Z=wb=0
 A matemática do método simplex:
Após 1 iteração
Z x1 x2 x3 x4 w x5 RHS
1 -7/4 0 3/2 0 0 36 w.b
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
B-1 B-1.b

 1 / 4 0 0   24   6 
Base: x2, x4 e x5

6     
1,5 4 1 0 0 
 c  0 xB  B b    3 / 8 1 0   21   12 
1

A   3 1,5 0 1 0  , b    1/ 4 0 1   8   2 
0     
 1 1 0 0 1  
   1/ 4 0 0 
 
 4 0 0
1
 1/ 4 0 0 w  cb B  6 0 0  3 / 8 1 0 
T 1

     1/ 4 0 1 
B 1   3 / 2 1 0     3 / 8 1 0  
 1 0 1  1/ 4 0 1  w  3 / 2 0 0
   
Z = w b = 36
 A matemática do método simplex:
Tableau final
Z x1 x2 x3 x4 w x5 RHS
1 0 0 4/5 0 14/5 208/5 w.b
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

 2 / 5 0  3 / 5   24   4,8 
Base: x2, x4 e x1

6     
1,5 4 1 0 0  xB  B 1b   3 / 5 1  3,9   21    4,2 
  c  0
A   3 1,5 0 1 0  , b     2 / 5 0 8 / 5   8   3,2 
    
 1 1 0 0 1  4
     2 / 5 0  3 / 5
 
1 w  cb B  6 0 4 3 / 5 1  3,9 
T 1
 4 0 3 / 2  2 / 5 0  3 / 5  2/5 0 8/5 
     
B 1   3 / 2 1 3    3 / 5 1  3,9 
 1 0 1   2/5 0 8/5  w  0,8 0 2,8
   
Z = w b = 41,6
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.