Módulo 5 - Dualidade

Prévia do material em texto

Módulo - 5
49
Dualidade
Prof. Ms. Antonio dos Santos
Dualidade
� Introdução:
� Uma das mais importantes descobertas no início do
desenvolvimento da programação linear foi o conceito de
dualidade.
50
� Esta descoberta revelou que todo o problema de
programação linear tem associado a ele outro problema de
programação linear chamado de dual.
� As relações entre o problema dual e o problema original
(chamado de primal) provam ser extremamente úteis.
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
Dualidade
Introdução:
� Dualidade é um fenômeno que ocorre freqüentemente na
formulação de problemas.
51
� As variáveis duais y, podem ser interpretadas como sendo os
preços associados às restrições do problema primal.
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
Dualidade
P Max Z = Σcj xj
s. a:
Σa x < b (i=1, ..., m)
n
n
j=1
D Min D = Σbi yi
s. a:
Σaij yj > cj (j=1, ..., n)
m
i=1
m
i=1
52
Σaij xj < bi (i=1, ..., m)
xj > 0 (j= 1, ..., n)
j=1
PRIMAL n variáveis
m restrições
ij j j
yi > 0 (i= 1, ..., m)
i=1
DUAL m variáveis
n restrições
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
Dualidade
� Alguns exemplos:
� Dado o Primal:
Max Z = 2x1+ x2
s.a:
O Dual associado é:
53
s.a:
x1 + x2 < 5
x1 + 2x2 < 8
x1 < 4
X1>0; X2>0
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
Dualidade: Problema da Dieta
Sabe-se que os alimentos leite, carne e ovos fornecem as
quantidades de vitaminas dadas na tabela abaixo. Deseja-se
calcular as quantidades de leite, carne e ovos a fim de satisfazer
as quantidades mínimas a um mínimo custo.(Primal)
54
Vitaminas Leite (litro)
Carne 
(kg)
Ovos 
(dúzia)
Quantidade 
diária mínima 
(mg)
A 1 3 2 6
C 5 30 20 60
D 10 50 25 100
Custo 
Unitário (R$) 2 12,5 7,5
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
Dualidade
Interpretação Econômica do Problema Dual
� Imagine que uma companhia farmacêutica fabrica vitaminas
e que deseja que o público obtenha os nutrientes a partir de
pílulas, em vez dos alimentos.
� O problema é determinar os preços máximos yA, yC, yD, por
55
� O problema é determinar os preços máximos yA, yC, yD, por
miligrama, para as pílulas, de modo a maximizar a renda e,
assim mesmo manter competitivo com os alimentos em
forma natural.
� Para manter-se competitivo, o custo dos nutrientes sintéticos
oriundos de pílulas não pode ser superior ao custo cj dos
mesmos nutrientes a partir de alimentos verdadeiros.
� Modelar e resolver o problema Dual
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos