Dualidade

Prévia do material em texto

MB – 244
PRINCÍPIOS DA 
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.
MB – 244
O PROBLEMA DUAL
Professor: Rodrigo A. Scarpel
rodrigo@ita.br
www.mec.ita.br/~rodrigo
Problemas Primal e Dual:
Para cada problema de programação linear que
resolvemos, existe um outro problema associado que
também é resolvido simultâneamente.
Este problema satisfaz algumas propriedades importantes
que podem ser usadas para resolver o problema original.
Denominaremos o problema original de PRIMAL e o novo
problema de DUAL.
Problemas Primal e Dual:
0
,...,1,







i
j
n
1i
iij
i
n
1i
i
x
mj bxa
:S.A.
xc (z) Max
PRIMAL 
0
,







j
ij
m
1j
ij
j
m
1j
j
y
n1,...,i cya
:S.A.
yb (v) Min
DUAL
Max Z = 4,0*xmad + 6,0*xalu
S.A. 1,5*xmad + 4,0*xalu  24
3,0*xmad + 1,5*xalu  21
1,0*xmad + 1,0*xalu  8
xmad, xalu  0
Min V = 24*ycorte + 21*ymont + 8*yacab
S.A. 1,5*ycorte + 3*ymont + 1*yacab  4
4*ycorte + 1,5*ymont + 1*yacab  6
ycorte, ymont, yacab  0
Primal Dual
Maximizar Minimizar
Função objetivo Termo independente (RHS)
I-ésima linha de coeficientes I-ésima coluna de coeficientes
J-ésima coluna de coeficientes J-ésima linha de coeficientes
I-ésima relação  I-ésima variável não negativa
I-ésima relação de = I-ésima variável irrestrita
I-ésima variável não negativa Restrição 
I-ésima variável irrestrita Restrição de =
Problemas Primal e Dual:
 SIMETRIA: O dual do problema dual é o problema primal.
Propriedades do problema Dual:
Max v = 4,0*xmad + 6,0*xalu
S.A. 1,5*xmad + 4,0*xalu  24
3,0*xmad + 1,5*xalu  21
1,0*xmad + 1,0*xalu  8
xmad, xalu  0
Min z = 24*ycorte + 21*ymont + 8*yacab
S.A. 1,5*ycorte + 3*ymont + 1*yacab  4
4*ycorte + 1,5*ymont + 1*yacab  6
ycorte, ymont, yacab  0
0
,







j
ij
m
1j
ij
j
m
1j
j
y
n1,...,i cya
:S.A.
yb (v) Min
DUAL
0
,...,1,







i
j
n
1i
iij
i
n
1i
i
x
mj bxa
:S.A.
xc (z) Max
PRIMAL 
 TEOREMA FRACO DA DUALIDADE
Se x e y são soluções viáveis dos problemas maximização 
(primal) e minimização (dual), respectivamente, então:
cT x bT y
 Implicações práticas: o valor da função objetivo de
qualquer solução viável de um problema dual de
minimização (maximização) fornece um limitante superior
(inferior) para o valor ótimo do problema primal de
maximização (minimização).
Propriedades do problema Dual:
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 
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 
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 
 
 
Max Z = 4,0*xmad + 6,0*xalu
S.A. 1,5*xmad + 4,0*xalu  24
3,0*xmad + 1,5*xalu  21
1,0*xmad + 1,0*xalu  8
xmad, xalu  0
Propriedades do problema Dual:
Min z = 24*ycorte + 21*ymont + 8*yacab
S.A. 1,5*ycorte + 3*ymont + 1*yacab  4
4*ycorte + 1,5*ymont + 1*yacab  6
ycorte, ymont, yacab  0
Exemplo de solução viável:
ycorte = ymont =0 e yacab = 6
z = 24*ycorte + 21*ymont + 8*yacab = 48
 TEOREMA FORTE (FUNDAMENTAL) DA DUALIDADE
Se o problema primal (dual) tem uma solução ótima finita, então o 
dual (primal) também tem uma solução finita e ótima e o valor da 
função objetivo de ambos problemas é igual. Assim, uma das 
seguintes situações é verdadeira:
i) Ambos os problemas têm solução ótima x* e y* com z* = v*;
ii) Um problema é ilimitado e o outro é inviável;
iii) Ambos os problemas são inviáveis.
Propriedades do problema Dual:
 TEOREMA DAS FOLGAS COMPLEMENTARES
Sendo x* e y* as soluções ótimas dos problemas primal e dual:
Possibilidades:
Propriedades do problema Dual:
j e i ,0 cyax e 0 xaby j
m
1j
jiji
n
1i
iijjj 













 

****
0 cya ou x
 e
0 xab ou y
j
m
1j
jiji
n
1i
iijjj




















**
**
0
0
Exemplo de aplicação do teorema das folgas complementares:
Min Z = 2*x1 + 5*x2 + 2*x3 + 3*x4
S.A. 1*x1 + 2*x2 + 1*x3 + 3*x4  4
2*x1 + 3*x2 + 1*x3 + 1*x4  3
x1, x2 , x3 , x4  0
j e i ,0 cyax
 e 0 xab-y
j
m
1j
jiji
n
1i
iijjj




















**
**
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 
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 
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 
 
 
Max Z = 4,0*xmad + 6,0*xalu
S.A. 1,5*xmad + 4,0*xalu  24
3,0*xmad + 1,5*xalu  21
1,0*xmad + 1,0*xalu  8
xmad, xalu  0
Método simplex (problema primal):
Min z = 24*ycorte + 21*ymont + 8*yacab
S.A. 1,5*ycorte + 3*ymont + 1*yacab  4
4*ycorte + 1,5*ymont + 1*yacab  6
ycorte, ymont, yacab  0
Z ycorte ymont yacabam x4 x5 a1 a2 RHS
1 -24 -21 -8 0 0 -M -M 0
1 -24+(3/2)M -21+3M -8+M -M 0 0 -M 4M
1 -24+(11/2)M -21+(9/2)M -8+2M -M -M 0 0 10M
a1
3/2 3 1 -1 0 1 0 4
a2
4 3/2 1 0 -1 0 1 6
1 0 -12+(39/16)M -2+(5/8)M -M -6+(3/8)M 0 6-(11/8)M 36+(7/4)M
a1
0 39/16 10/16 -1 6/16 1 -6/16 28/16
ycorte
1 3/8 1/4 0 -1/4 0 1/4 3/2
1 0 0 42/39 -192/39 -162/39 (192/39)-M (162/39)-M 1740/39
ymont
0 1 10/39 -16/39 6/39 16/39 -6/39 28/39
ycorte
1 0 2/13 2/13 -4/13 -2/13 4/13 16/13
1 0 -21/5 0 -624/195 = -3,2 -936/195 = -4,8 3,2-M 4,8-M 8112/195 = 41,6
yacabam
0 39/10 1 -16/10 6/10 16/10 -6/10 28/10 = 2,8
ycorte
1 -3/5 0 26/65 -26/65 -26/65 26/65 52/65 = 0,8
Método simplex (problema dual):
PRIMAL DUAL
Problemas Primal e Dual:
Interpretação Econômica do problema dual:
Min V = 24*ycorte + 21*ymont + 8*yacab
S.A. 1,5*ycorte + 3*ymont + 1*yacab  4 (Porta de madeira)
4*ycorte + 1,5*ymont + 1*yacab  6 (Porta de alumínio)
ycorte, ymont, yacab  0ycorte : preço pago por 1 hora de corte
ymont : preço pago por 1 hora de montagem
yacab : preço pago por 1 hora de acabamento
V: preço total pago pelo 
recursos (shadow price)
Função objetivo: Minimizar o preço total pago pelos recursos.
Restrições: Mínimo a ser pago pela combinação das variáveis de decisão 
(pois com essa combinação gera-se uma unidade do produto).
1. Interpretação econômica das variáveis duais:
Interpretação Econômica do problema dual:
Z x1(m adeira) x2(alum ín io ) x3(cort e) x4(m ont agem ) x5(acabam ent o ) RHS
1 0 0 4/5 = 0,8 0 14/5 = 2,8 208/5 = 41,6
x2(alum ín io ) 0 1 2/5 0 -6/5 24/5 = 4,8
x4(m ont agem ) 0 0 3/5 1 -39/10 21/5 = 4,2
x1(m adeira) 1 0 -2/5 0 8/5 16/5 = 3,2
Z ycorte ymont yacabam x4(madeira) x5(alumínio) a1 a2 RHS
1 0 -21/5 0 -624/195 = -3,2 -936/195 = -4,8 3,2-M 4,8-M 8112/195 = 41,6
yacabam
0 39/10 1 -16/10 6/10 16/10 -6/10 28/10 = 2,8
ycorte
1 -3/5 0 26/65 -26/65 -26/65 26/65 52/65 = 0,8
1. Interpretação econômica das variáveis duais:
Interpretação Econômica do problema dual:
2. Interpretação econômica do teorema das folgas complementares:
j e i ,0 cyax e 0 xaby j
m
1j
jiji
n
1i
iijjj 













 

****
Sendo x* e y* as soluções ótimas dos problemas primal e dual:
 NA SOLUÇÃO, SE HÁ FOLGA DE ALGUM RECURSO SEU VALOR 
(PREÇO DUAL) NECESSARIAMENTE É ZERO
 NA SOLUÇÃO, SE UM DETERMINADO RECURSO TEM VALOR (>0) 
NECESSARIAMENTE A FOLGA É ZERO
Interpretação Econômica do problema dual:
3. Interpretação econômica das restrições duais:
n1,...,i ,cya
0y
:S.A.
yb (v)Min 
ij
m
1j
ij
j
j
m
1j
j







Utilização dos recursos
Valor dos recursos
Ganho proporcionado
Um novo produto só 
será fabricado se 
ij
m
1j
ij cya 

Todo produto fabricado 
ij
m
1j
ij cya 

Lucro unitário: porta com vidro: R$5,00
 Corte Montagem Acabamento 
Madeira 1,5 h/porta 3,0 h/porta 1,0 h/porta 
Alumínio 4,0 h/porta 1,5 h/porta 1,0 h/porta 
P. com vidro 3,0 h/porta 1,0 h/porta 2,0 h/porta 
Disponibilidade 24 h 21 h 8 h 
 
Z x1 x2 x3 x4 x5 x6 RHS 
1 -4 -6 -5 0 0 0 0 
x4 1,5 4 3 1 0 0 24 
x5 3 1,5 1 0 1 0 21 
x6 1 1 2 0 0 1 8 
 
Tableau inicial: Tableau final: Z x1 x2 x3 x4 x5 x6 RHS 
1 0 0 3 4/5 0 14/5 208/5 
x2 0 1 0 2/5 0 -3/5 24/5 
x5 0 0 -5 3/5 1 -39/10 21/5 
x1 1 0 2 -2/5 0 8/5 16/5 
 
Interpretação Econômica do problema dual:
3. Interpretação econômica das restrições duais:
  35
5
28
0
5
12
5
2
1
3
 
5
140
5
4 










  5
)1(2
)1(1
)1(3
 
5
140
5
4
3
2
1














r
r
r
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 
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 
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 
 
 
Max Z = 4,0*xmad + 6,0*xalu
S.A. 1,5*xmad + 4,0*xalu  24
3,0*xmad + 1,5*xalu  21
1,0*xmad + 1,0*xalu  8
xmad, xalu  0
Método Simplex: problemas primal e dual
Min z = 24*ycorte + 21*ymont + 8*yacab
S.A. 1,5*ycorte + 3*ymont + 1*yacab  4
4*ycorte + 1,5*ymont + 1*yacab  6
ycorte, ymont, yacab  0
 A teoria da dualidade proporciona um suporte teórico que 
permite:
 Calcular limites superiores (em problemas de 
maximização) e inferiores (em problemas de 
minimização) para o valor da função objetivo.
 Interpretação econômica dos resultados da 
otimização.
 Desenvolvimento de métodos mais eficientes para 
resolver problemas reais.
Dualidade:
MB – 244
ALGORITMOS SIMPLEX 
ADICIONAIS
Professor: Rodrigo A. Scarpel
rodrigo@ita.br
www.mec.ita.br/~rodrigo
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:
• Condições de Viabilidade X Condições de Otimalidade
• Opção A: O simplex pode ser visto como um método que
busca atender as condições de otimalidade mantendo as
condições de viabilidade.
• Opção B: O simplex pode ser visto como um método que
busca a viabilidade do problema dual mantendo a
viabilidade do problema primal.
Método Dual Simplex (PPL primal de Maximização):
Inicialização:
Encontrar uma solução básica que atenda as condições de otimalidade, 
mas que não atenda as condições de viabilidade.
Passo principal:
Seja xB a solução corrente. Se o termo de xB  0 pare - a solução é ótima.
Caso contrário escolha o termo de xB mais negativo para sair da base.
Determine a variável que vai entrar na base por
Se todos yik  0 pare  o problema não tem solução viável
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
ii
mi
y
y
cz
mínimo
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 
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 
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 
 
 
Max Z = 4,0*xmad + 6,0*xalu
S.A. 1,5*xmad + 4,0*xalu  24
3,0*xmad + 1,5*xalu  21
1,0*xmad + 1,0*xalu  8
xmad, xalu  0
Min V = 24*ycorte + 21*ymont + 8*yacab
S.A. 1,5*ycorte + 3*ymont + 1*yacab  4
4*ycorte + 1,5*ymont + 1*yacab  6
ycorte, ymont, yacab  0
V y1 y2 y3 y4 y5 RHS 
1 -24 -21 -8 0 0 0 
y4 -1,5 -3 -1 1 0 -4 
y5 -4 -1,5 -1 0 1 -6 
1 0 -12 -2 0 -6 36 
y4 0 -39/16 -5/8 1 -3/8 -7/4 
y1 1 3/8 1/4 0 -1/4 3/2 
1 0 -21/5 0 -16/5 -24/5 208/5 
y3 0 39/10 1 -8/5 3/5 14/5 
y1 1 3/5 0 2/5 -2/5 4/5 
 
 
Método Dual Simplex (PPL primal de Maximização):
O dual simplex pode ser visto como um método que busca atender as 
condições de viabilidade mantendo as condições de otimalidade
Generalização do Método Simplex:
• Opção A: O simplex pode ser visto como um método que
busca atender as condições de otimalidade mantendo as
condições de viabilidade.
• Opção B: O simplex pode ser visto como um método que
busca a viabilidade do problema dual mantendo a viabilidade
do problema primal.
• Opção C: O simplex pode ser visto como um método que
busca atender as condições de viabilidade mantendo as
condições de otimalidade.
Essas opções podem ser combinadas de acordo com
a necessidade para “talhar” novos métodos
(exemplos: método primal-dual, método simétrico,
método entrecruzado e método multiplex).
MB – 244
ANÁLISE PÓS-
OTIMIZAÇÃO
Professor: Rodrigo A. Scarpel
rodrigo@ita.br
www.mec.ita.br/~rodrigo
Princípios:
• Em problemas reais as alterações (disponibilidade dos
recursos, preço dos insumos,…) demandam o recálculo
periódico da solução ótima.
• A análise de pós-otimização auxilia na determinação da nova
solução de modo eficiente.
ALTERNATIVAS POSSÍVEIS MOTIVOS AÇÃO RECOMENDADA
SOLUÇÃO ATUAL(BASE) 
PERMANECE ÓTIMA E VIÁVEL
- NENHUMA
ALTERAÇÕES NO RHS (RECURSOS)
ADIÇÃO DE NOVAS RESTRIÇÕES
ALTERAÇÕES NOS COEFIC. DA F.O.
ADIÇÃO DE UMA NOVA ATIVIDADE
SOLUÇÃO ATUAL SE TORNA 
NÃO-ÓTIMA E INVIÁVEL
COMBINAÇÃO DOS ITENS ANTERIORES
USAR, SE POSSÍVEL, O SIMPLEX 
GENERALIZADO PARA OBTER NOVA 
SOLUÇÃO
SOLUÇÃO ATUAL SE 
TORNA INVIÁVEL
USAR O DUAL SIMPLEX PARA 
RECUPERAR A VIABILIDADE
SOLUÇÃO ATUAL SE 
TORNA NÃO-ÓTIMA
USAR O SIMPLEX (PRIMAL) PARA 
RECUPERAR A OTIMALIDADE
Alterações no RHS (recursos):
Recurso gargalo:
A base fica inalterada: -7  A  8
 Função objetivo:
(B e C: ctes)
208/5 + 
4/5 A + 0 B + 
14/5 C
xmadeira
5
x
a
lu
m
ín
io
5
A = +10 (há alteração na base)
Z x1 x2 x3 x4 x5 RHS 
1 0 0 4/5 0 14/5 
208
/5 + 
4
/5 A + 0 B + 
14
/5 C 
x2 0 1 2/5 0 -3/5 
24
/5 + 
2
/5 A + 0 B - 
3
/5 C 
x4 0 0 3/5 1 -39/10 
21
/5 + 
3
/5 A + 1 B - 
39
/10 C 
x1 1 0 -2/5 0 8/5 
16
/5 - 
2
/5 A + 0 B + 
8
/5 C 
 
Alterações no RHS (recursos):
Z x1 x2 x3 x4 x5 RHS 
1 0 0 4/5 0 14/5 
248
/5 
x2 0 1 2/5 0 -3/5 
44
/5 
x4 0 0 3/5 1 -39/10 
51
/5 
x1 1 0 -2/5 0 8/5 
-4
/5 
1 2 0 0 0 6 48 + 6C 
x2 1 1 0 0 1 8 + C 
x4 3/2 0 0 1 -1,5 9 +B – 1,5 C 
x3 -5/2 0 1 0 -4 2 + A – 4C 
 
5
x
a
lu
m
ín
io
5
FO: Max Z = 4,0*x1 + 6,0*x2
S.A. 1,5x1+ 4,0x2+ 1x3 = 34 + A 
3,0x1+ 1,5x2 + 1x4 = 21 + B 
1,0x1+ 1,0x2 + 1x5 = 8 + C 
x1, x2, x3 , x4 , x5  0
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
Adição de novas restrições:
• Quando novas restrições são adicionadas, há 2 possibilidades:
• A restrição ser redundante
• A solução atual se tornar inviável
Nova restrição: Demanda xmadeira  4 (Restrição é redundante)
xmadeira  3 (Solução atual é inviável)
 Solução ótima:
x1 (madeira) = 16/5 = 3,2
x2 (alumínio) = 24/5 = 4,8
Lucro = 208/5 = 41,6
FO: Max Z = 4,0*x1 + 6,0*x2
S.A. 1,5x1+ 4,0x2+ 1x3 = 34 
3,0x1+ 1,5x2 + 1x4 = 21 
1,0x1+ 1,0x2 + 1x5 = 8
1,0x1 + 1x6 = 3
x1, x2, x3 , x4 , x5 , x6  0
Adição de novas restrições:
Z x1 x2 x3 x4 x5 x6 RHS 
1 0 0 4/5 0 14/5 0 208/5 
x2 0 1 2/5 0 -3/5 1 24/5 
x4 0 0 3/5 1 -39/10 0 21/5 
x1 1 0 -2/5 0 8/5 0 16/5 
x6 1 0 0 0 0 1 3 
1 0 0 4/5 0 14/5 0 208/5 
x2 0 1 2/5 0 -3/5 1 24/5 
x4 0 0 3/5 1 -39/10 0 21/5 
x1 1 0 -2/5 0 8/5 0 16/5 
x6 0 0 2/5 0 -8/5 1 -1/5 
 
Adição de novas restrições:
Z x1 x2 x3 x4 x5 x6 RHS 
1 0 0 4/5 0 14/5 0 208/5 
x2 0 1 2/5 0 -3/5 1 24/5 
x4 0 0 3/5 1 -39/10 0 21/5 
x1 1 0 -2/5 0 8/5 0 16/5 
x6 0 0 2/5 0 -8/5 1 -1/5 
1 0 0 3/2 0 0 7/4 825/20 
x2 0 1 1/4 0 0 -3/8 195/40 
x4 0 0 -15/40 1 0 -195/80 375/80 
x1 1 0 0 0 0 1 3 
x5 0 0 -1/4 0 1 -5/8 1/8 
 
 Solução ótima:
x1 (madeira) = 3
x2 (alumínio) = 4,875
Lucro = 208/5 = 41,25
xmadeira(x1)5
x
a
lu
m
ín
io
(x
2
)
5
Para casa:
• Lista de Exercícios 6
• Leitura Taha: 4.1 a 4.5
Winston: 6.5 a 6.10
Este material refere-se às notas de aula do curso 
MB-244 (Princípios da 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.
OBSERVAÇÃO