Introdução à Programação Linear
Parte IV
Elementos de
Economia Matemática 2
Prof. Alexandre Stamford
O Problema Dual
É possível verificar através da teoria da
programação matemática que para cada problema
(PRIMAL) existe um problema (DUAL).
As condições de otimalidade para os problemas
são as mesmas.
Os dois problemas são bastante entrelaçados.
É sempre possível encontrar o Dual de um
problema posto na forma padrão.
Os dois problemas têm a mesma solução.
O Problema Dual
Se o PRIMAL é de Maximização o DUAL é de
Minimização.
Se a restrição no PRIMAL é de maior ou igual, no
DUAL é de menor ou igual.
Cada variável no PRIMAL eqüivale a uma restrição
no DUAL e vice-versa.
O DUAL do DUAL é o PRIMAL.
Os problemas são resolvidos em espaços
diferentes.
Existem regras bem definidas na obtenção do
problema DUAL.
Construção do DUAL
n
Max L   c j x j
s. a
j1
a
x  b i (i  1,...,m)
ij j
xj  0  j
m
Min Z   b i yi
s. a
a
i 1
y  c j ( j  1,...,n)
ij i
yi  0  i
Exemplo
Max
x1 ,x2
L  4 x1  x2
H .H .
9 x1  x2  18 y1
H .M .
3x1  x2  12 y2
x1  0
x2  0
Min
y1 , y 2
Z  18 y1  12 y2
9 y1  3 y2  4
x1
y1  y2  1 x2
y1  0
y2  0
Exemplo
Max
x1 , x2
L  5 x1  2 x2
x1
Min
 3 y1
x2  4
y2
x1  2 x2  9
y3
x1  0
x2  0
y1 , y 2
Z  3 y1  4 y2  9 y3
y1
 y3  5
x1
y2  2 y3  2 x2
y1  0
( PUCCINI, pag.136)
y2  0
y3  0
O Problema DUAL
Min
y1 , y 2
Z  18 y1  12 y2
9 y1  3 y2  4
y1  y2  1
y1  0
y2  0
Solução Gráfica: Construindo o
conjunto de possibilidades
y2
Valores Possíveis quando
y1  0
0
y2  0
y1
Solução Gráfica: Construindo
o conjunto de possibilidades
y2
4/3
Valores Possíveis quando
9 y1  3 y2  4
9 y1  3 y2  4
0
4/9
y1
Solução Gráfica: Construindo
o conjunto de possibilidades
y2
1
Valores Possíveis quando
y1  y2  1
y1  y2  1
0
1
y1
Solução Gráfica: Construindo
o conjunto de possibilidades
y2
4/3
Conjunto de Possibilidades
0
1
y1
Solução Gráfica: Desenhando as
Curvas de Níveis do Objetivo
y2
Z  20
Z  15
Z  10
Direção de
Otimização
0
y1
Solução Gráfica: Reunindo os
componentes e resolvendo
y2
4/3
Z  13
5/6
Conjunto de Possibilidades
0
1
y1
Solução DUAL
É possível resolver o problema DUAL através do
método DUAL-SIMPLEX.
Note que:
No PRIMAL: 4.1+ 1.9=13.
No DUAL: 18.(1/6) +12.(5/6)=13.
A interpretação do DUAL é um dos conhecimentos que
mais abrem o campo mental do decisor.
Interpretação do DUAL
n
Max L   c j x j
s. a
j1
n
a
j1
x  b i (i  1,...,m)
ij j
xj  0  j
m
Min Z   b i yi
s. a
i 1
m
a
i 1
y  c j ( j  1,...,n)
ij i
yi  0  i
$
unidade do produto j
unidade do recurso i
a ij 
unidade do produto j
$
yi 
unidade do recurso i
cj 
Preço sombra ( shadon price )
Valor implícito
Preço interno ( internal price )
Efficiency price
Intrinsic value
Incremental value
Interpretação do DUAL
m
Min Z   b i yi
s. a
i 1
m
a
i 1
y  c j ( j  1,...,n)
ij i
yi  0  i
$


Z$
 unidade do recurso i 
 unidade do recurso i

• A função objetivo é um custo de oportunidade total.
•Cada restrição é uma linha de produção.
•Estas restrições viabilizam a produção.
•Se não fosse maior era melhor vender os recursos
que.produzir com eles.
Dada resposta:
L
x1
x2
x1
0
1
0
x2
0
0
1
x3
Pergunta-se:
Quanto a empresa deve fabricar de
cada produto para ter o maior lucro?
Caso se obtenha algum recurso
financeiro externo, para investimento
em expansão, em quais dos recursos a
empresa deveria aplicá-lo ?
Qual seria o impacto no lucro se alguns
trabalhadores faltassem ao trabalho
limitando as horas homens disponíveis
em 15 horas?
x4
1/6
1/6
- 1/2
5/6
- 1/6
1.5
13
1
9
4 máquinas são responsáveis
pela produção no período em
análise até quanto se deve
pagar pelo aluguel de uma
máquina se uma delas
quebrar?
Qual deveria ser o lucro líquido
fornecido para viabilizar a
fabricação um novo produto
que utiliza 5 horas de cada
recurso?
Pergunta-se
 Qual deveria ser o lucro líquido fornecido para viabilizar a fabricação
um novo produto que utiliza 5 horas de cada recurso?
 A pergunta pode ser facilmente respondida com o conhecimento do
problema DUAL.
 A restrição no problema dual seria:
5 y1  5 y2  p
A pergunta é: Quem é p?
Sabendo-se que y1=1/6 e y2 =5/6 resulta:
5( 1 6 )  5( 5 6 )  p
p5
Pergunta-se
 Qual o valor de uma variável dual cuja restrição não foi
atingida?
 Quando a restrição não é atingida é porque existe sobra.
 O preço de um recurso que está sobrando é zero.