06 Dualidade Apostila Pesquisa operacional

Prévia do material em texto

6.1 O que é dualidade? 
 
Dualidade é a propriedade ou caráter do que contém em si duas naturezas, duas substâncias ou 
dois princípios. Dualidade possui significados na área da física, da eletrônica digital (e lógica 
matemática), da matemática e da filosofia. 
 
(i) Física: Dualidade partícula-onda 
A dualidade partícula-onda, também chamada de dualidade matéria-energia, é uma propriedade física das 
entidades de dimensões atômicas, que possuem tanto comportamento de partícula como de onda. Surgiu 
das observações sobre a natureza da luz que foi pensada tanto para consistir de ondas (Christian Huygens) 
ou de partículas (Isaac Newton). 
 
 
 
 
 
 
 
 
Imagem da difração (fenômeno de ondas) de elétrons 
(partículas) produzida em um microscópio eletrônico de 
transmissão (fonte: Wikipédia). 
 
(ii) Eletrônica: Dualidade das portas Lógicas 
Uma porta AND é exatamente igual a uma porta OR quando se troca o zero pelo um e o um pelo zero. 
Assim, quando fazemos um AND estamos simultaneamente fazendo um OR. O mesmo acontecendo com o 
NAND e o NOR. Uma forma se reproduz na outra. Assim quando uma porta NAND ocorre, simultaneamente 
ocorre uma porta NOR. 
 
 
 
 
A B X = A AND B A B X = A OR B 
0 0 0 0 0 0 
0 1 0 0 1 1 
1 0 0 1 0 1 
1 1 1 1 1 1 
 
(iii) Filosofia: Ying-yang 
Yin Yang é um princípio da filosofia chinesa, que admite a coexistência 
de dois princípios eternos, necessários e contrários, duas energias 
opostas: Yin significa escuridão sendo representado pelo lado pintado de 
preto, e yang a claridade. Esses dois princípios se aplicam à natureza em 
um processo de mudança contínua onde o ideal é haver um equilíbrio 
entre os dois princípios, devendo existir um pouco de negativo no 
positivo e vice-versa. Existe uma dualidade nos dois princípios, pois eles 
se complementam, onde um não existe sem o outro, ou seja: quando 
um ocorre, instantaneamente o outro também ocorre. 
Dualidade 
 
Pesquisa 
Operacional 
6 
 
AND 
A 
X 
B 
OR 
A 
X 
B 
 
 
(iv) Matemática: Dualidade dos Modelos de Programação Linear 
Em programação linear, dualidade significa a existência de um outro problema associado ao problema 
original (ou primal) também de programação linear, que designa-se problema dual (D). 
 
6.2 Introdução 
 
O algoritmo Simplex resolve o modelo linear através de operações elementares do Método de Gauss-
Jordan aplicado às linhas e colunas da sua tabela. Isso faz com que a quantidade de cálculos seja muito 
grande. Existe alguma maneira de reduzir essa quantidade de cálculos? 
 
Todo problema de programação linear é denominado “problema primal”, mas a ele está associado outro 
problema, denominado “problema dual”. 
 
 
 
 
 
 
 
 
 
Os dois problemas apresentam as seguintes propriedades: 
 A solução do dual pode ser obtida de forma mais simples do que a do primal. 
 Conhecendo o valor ótimo do dual pode-se calcular o valor ótimo do primal, e vice-versa; 
 O valor ótimo do dual tem uma curiosa interpretação econômica. 
 
Qual a maneira de se obter o dual de um problema de programação linear? 
Quais os métodos para se obter as soluções ótimas do problema, conhecendo as soluções ótimas do 
problema associado? 
 
6.3 Construção do Modelo Dual 
 
Considere o problema de programação linear “primal” que na forma padrão é: 
Max j
n
j
j xcz .
1


 
S/a ij
n
j
ij bxa 

.
1
,  mibi ,...,1,0  
  njx j ,...,1,0  
Essa a forma exige que: 
 A função objetivo seja de Maximização 
 As restrições sejam todas do tipo  
 Os termos da direita (bi) sejam todos positivos 
 As variáveis sejam todas não negativas 
 
A partir desse modelo pode-se associar outro modelo chamado “dual” do primeiro que é construído da 
seguinte maneira: 
 Cada restrição do primal corresponde a uma variável de decisão yi do dual. Exemplo: duas 
restrições no primal  duas variáveis y1 e y2 no dual 
 Se a função objetivo do primal é de Maximização  a função objetivo do dual é de Minimização (e 
vice-versa). 
Problema 
Primal 
Problema 
Dual 
Associados 
 Cada parcela da função objetivo do dual será o produto da variável yi pelo termo bi da direita da 
restrição correspondente: j
n
j
j ybD .
1


 
 Cada variável de decisão xi do primal gera uma restrição no dual. Exemplo: cinco variáveis no 
primal  gera cinco restrições no dual 
 Na restrição do dual, cada termo é o produto da variável dual yi pelo coeficiente respectivo da 
variável de decisão do primal: ai.yi 
 Se o objetivo do dual for de minimização (dirigido para baixo)  as restrições são todas do tipo “” 
(qualquer coisa é maior do que o mínimo). 
 Se o objetivo do dual for de maximização (dirigido para cima)  as restrições são todas do tipo “” 
(qualquer coisa é menor do que o máximo). 
 Se para Max da função objetivo a restrição do primal tem o sinal do tipo “”  na restrição do dual 
o sinal é do tipo “” (e vice-versa). 
 Se a restrição do primal tem o sinal do tipo “=”  a variável dual correspondente será do tipo sem 
restrição de sinal 
 Se a restrição do primal tem o sinal do tipo sem restrição de sinal  a variável dual 
correspondente será do tipo “=” 
 O termo da direita na restrição do dual é o coeficiente cj da variável primal na função objetivo 
 As variáveis yi são todas não negativas: yi  0 
 
Propriedade: 
O dual obtido de um dual retorna ao modelo primal 
 
6.4 Quadro de Regras de construção 
 
Quadro com as regras para construir o dual de qualquer problema de programação linear. 
 
Problema Primal Problema Dual 
Função Objetivo Min Max Função Objetivo 
Restrições 
  
Variáveis =  irrestrito 
  
Variáveis 
  
Restrições Irrestrito = Irrestrito 
  
 
6.5 Exemplo-1 
 
Considere o seguinte problema de programação linear da dieta: 
Primal: 
Min 20 x1 + 25 x2 + 31 x3 + 11 x4 + 12 x5 
Sujeito a: 
x1 + + x3 + x4 + 2 x5  21 (calorias) 
 x2 + 2 x3 + x4 + x5  12 (vitaminas) 
x1, x2, x3, x4, x5  0 
xj : quantidade do alimento j. 
aij : quantidade do nutriente i por unidade de alimento j. 
 
Dual do problema de programação linear da Dieta: 
Max 21 y1 + 12 y2 
Sujeito a: 
 y1  20 
 y2  25 
 y1 + 2 y2  31 
 y1 + y2  11 
2 y1 + y2  12 
 y1, y2  0 
 
Observar que: 
 A função objetivo do problema primal é de minimização  no problema dual a função objetivo 
passou a ser de maximização. 
 Tem-se duas restrições no problema primal  no problema dual tem-se duas variáveis, isto 
significa que cada restrição do primal leva a uma variável dual associada. 
 Tem-se cinco variáveis no primal  no problema dual tem-se cinco restrições, isto significa que 
cada variável do primal leva a uma restrição dual associada 
 Os coeficientes da função objetivo do primal passaram para o lado direito das restrições no dual, e 
os valores do lado direito das restrições das restrições do primal passaram para a função objetivo 
no dual. 
 
Em notação matricial, tem-se: 















































12
21
,
11210
21101
,
12
11
31
25
20
,
5
4
3
2
1
bAc
x
x
x
x
x
x 
Define-se as variáveis duais 







2
1
y
y
Y 
Logo, utilizando notação matricial tem-se: 
 
Primal Dual 
Min cT x 
s.a. 
A x  b 
x  0 
Max bT Y 
s.a. 
AT Y  c 
Y  0 
6.6 Exemplo-2 
 
Primal: Max Z = 2.x1 + 3.x2 + x3 
s.a.: 
3.x1 + 4.x2 + 2.x3  10 
2.x1 + 6.x2 + 1.x3  20 
x1 - x2 - x3  30 
x1  0; x2  0; x3  0 
 
Como cada restrição do primal leva a uma variável dual associada, tem-se: 
Primal: Max Z = 2.x1 + 3.x2 + 1.x3 
s.a.: 3.x1 + 4.x2 + 2.x3  10  y1 
2.x1 + 6.x2 + 1.x3  20  y2 
1.x1 - x2 - x3  30  y3 
x1  0; x2  0; x3  0 
 
Dual: Min D = 10.y1 + 20.y2 + 30.y3 
s.a.: 3.y1 + 2.y2 + 1.y3  2 
4.y1 + 6.y2 - 1.y3  3 
2.y1 + 1.y2 – 1.y3  1 
y1  0; y2  0; y3  0 
 
6.7 Exemplo-3 
 
Primal: Max Z = 2.x1 + 3.x2+ x3 
s.a.: 
x1 + x2  10 
2.x1 + 4.x2 - 1.x3 = 20 
x1  0; x2  0; x3  0 
 
Como cada restrição do primal leva a uma variável dual associada, tem-se: 
Primal: Max Z = 2.x1 + 3.x2 + 1.x3 
s.a.: 1.x1 + 1.x2 + 0.x3  10  y1 
2.x1 + 4.x2 - 1.x3 = 20  y2 
x1  0; x2  0; x3  0 
 
Dual: Min D = 10.y1 + 20.y2 
s.a.: 1.y1 +2.y2  2 
1.y1 + 4.y2  3 
0.y1 + 1.y2  1 
y1  0; y2 livre 
 
6.8 Outros Exemplos 
 
6.8.1 Exemplo 1: 
 
Primal Dual 
Min cT x 
s.a. 
A x  b 
x  0 
Max bT w 
s.a. 
AT w  c 
w  0 
 
6.8.2 Exemplo 2: 
 
Primal Dual 
Min cT x 
s.a. 
A x  b 
 x  0 
Max bT w 
s.a. 
AT w  c 
w  0 
 
6.8.3 Exemplo 3: 
 
Primal Dual 
Min cT x 
s.a. 
A x = b 
 x  0 
Max bT w 
s.a. 
AT w  c 
w irrestrito 
 
6.8.4 Exemplo 4: 
 
Primal Dual 
Min cT x 
s.a. 
A x = b 
 x irrestrito 
Max bT w 
s.a. 
AT w = c 
w irrestrito. 
6.8.5 Exemplo 5: 
 
Primal Dual 
Max cT x 
s.a. 
A x  b 
 x  0 
Min bT w 
s.a. 
AT w  c 
w  0 
 
6.8.6 Exemplo 6: 
 
Primal Dual 
Max 4 x1 + 0 x2 + 6 
x3 
s.a. 
3 x1 + x2 + 3 x3  30 
2 x1 + 2 x2  40 
x1, x2, x3  0 
Min 30 w1 + 40 w2 
s.a. 
3 w1 + 2w2  4 
 w1 + 2w2  0 
3 w1  6 
w1, w2  0 
 
Observe como teria sido diferente o dual considerando a função objetivo do problema primal de 
minimização isto é: 
 
Primal Dual 
Min 4 x1 + 0 x2 + 6 x3 
s.a. 
3 x1 + x2 + 3 x3  30 
2 x1 + 2 x2 +  40 
x1, x2, x3  0 
Max 30 w1 + 40 w2 
s.a. 
3 w1 + 2w2  4 
 w1 + 2w2  0 
3 w1  6 
w1, w2  0 
 
Observe como muda o sentido das restrições e das variáveis quando consideramos a função objetivo do 
primal como minimização e quando consideramos maximização. Portanto, atenção à função objetivo do 
primal. 
 
6.9 Soluções do Primal e do Dual 
 
 Cada solução básica não ótima do primal corresponde uma solução básica inviável no dual 
 A solução ótima do modelo primal corresponde à solução ótima do modelo dual  Z = D 
 O coeficiente da variável de decisão na função objetivo do modelo primal é o valor da variável de 
folga correspondente na solução dual  coeficiente de xi = valor de yFi 
 O coeficiente da variável de folga na função objetivo do modelo primal é o valor da variável de 
decisão correspondente na solução dual  coeficiente de xFi = valor de yi 
 
Como a quantidade de cálculos pelo método simplex depende em grande parte do número de restrições, 
então, um problema de programação linear no qual o número de variáveis (que leva ao número de 
restrição do dual) é consideravelmente menor do que o número de restrições podem-se conseguir 
economias de cálculo resolvendo o problema dual. 
 
A solução do dual pode ser obtida facilmente observando o tableau e considerando uma propriedade 
importante que relaciona as variáveis primal-dual. 
 
PRIMAL 
Variáveis naturais Variáveis de folga 
Var. Básicas Var. Não Básicas Var. Básicas Var. Não Básicas 
DUAL 
Var. Não Básicas Var. Básicas Var. Não Básicas Var. Básicas 
Variáveis de folga Variáveis naturais 
 
A tabela acima indica que as variáveis naturais do problema primal estão associadas às variáveis de folga do 
problema dual e as variáveis de folga do problema primal estão associadas às variáveis naturais do dual. 
Portanto, segundo esta propriedade pode-se olhar para a primeira linha do tableau ótimo do simplex e 
encontrar os valores das variáveis duais 
 
6.10 Exemplo-4 
 
Primal: Max Z = 1.x1 + 2.x2 + 3.x3 
s.a.: 
1.x1 + x2 + x3  10  y1 
2.x1 + x2 + 4.x3  12  y2 
1.x1 + 3. x2 - x3  9  y3 
x1  0; x2  0; x3  0 
 
Dual: Min D = 10.y1 + 12.y2 + 9.y3 
s.a.: 
1.y1 + 2.y2 + 1.y3  1 
y1 + y2 + 3.y3  2 
y1 + 4.y2 - y3  3 
y1  0; y2  0; y3  0 
 
Colocando as variáveis de folga: 
Primal: Max Z = 1.x1 + 2.x2 + 3.x3 
s.a.: 
x1 + x2 + x3 + xF1 = 10 
2.x1 + x2 + 4.x3 + xF2 = 12 
x1 + 3. x2 - x3 + xF3 = 9 
x1  0; x2  0; x3  0 
 
Dual: Min D = 10.y1 + 12.y2 + 9.y3 
s.a.: 
1.y1 + 2.y2 + 1.y3 - yF1 = 1 
y1 + y2 + 3.y3 - yF1 = 2 
y1 + 4.y2 - y3 - yF1 = 3 
y1  0; y2  0; y3  0 
 
Montando o quadro do Simplex para o modelo Primal 
Lin. z x1 x2 x3 xF1 xF2 xF3 b 
1 1 -1 -2 -3 0 0 0 0 
2 0 1 1 1 1 0 0 10 
3 0 2 1 4 0 1 0 12 
4 0 1 3 -1 0 0 1 9 
 
 
Solução básica inicial: x1 = 0; x2 = 0; x3 = 0; xF1 = 10; xF2 = 12; xF3 = 9 
 Variáveis não básicas: x1 = 0; x2 = 0; x3 = 0 
 Variáveis básicas: Valores no vetor b  xF1 = 10; xF2 = 12; xF3 = 9 
 Valor de Z: Z = 0. 
 Coeficiente das variáveis não básicas x1, x2 e x3 na função objetivo são negativos  ainda não é a 
solução ótima 
 
Montando o quadro do Simplex para o modelo Dual 
Dual: Max -D = -10.y1 - 12.y2 - 9.y3 
s.a.: 
1.y1 + 2.y2 + 1.y3 - yF1 = 1 
y1 + y2 + 3.y3 - yF1 = 2 
y1 + 4.y2 - y3 - yF1 = 3 
y1  0; y2  0; y3  0 
 
 
 
Lin. D y1 y2 y3 yF1 yF2 yF3 b 
1 -1 10 12 9 0 0 0 0 
2 0 1 2 1 -1 0 0 1 
3 0 1 1 3 0 -1 0 2 
4 0 1 4 -1 0 0 -1 3 
 
 
Solução inviável: y1 = 0; y2 = 0; y3 = 0; yF1 = -1; yF2 = -2; yF3 = -3 
 Variáveis não básicas: y1 = 0; y2 = 0; y3 = 0 
 Variáveis básicas: -yF1 = 1  yF1 = -1 (< 0 desconsiderar); -yF2 = 2  yF2 = -2 (< 0 desconsiderar); -yF3=3 
 yF3 = -3 (< 0 desconsiderar) 
 Valor de D: D = 0. 
 Coeficiente das variáveis não básicas x1, x2 e x3 na função objetivo são positivos com todos os bs 
negativos  solução básica inviável 
 
Correspondências: 
Primal Dual Primal Dual 
Coeficiente de x1 = -1  valor de yF1 = -1 Valor de x1 = 0  Coeficiente de yF1 = 0 
Coeficiente de x2 = -2  valor de yF2 = -2 Valor de x2 = 0  Coeficiente de yF2 = 0 
Coeficiente de x3 = -3  valor de yF3 = -3 Valor de x3 = 0  Coeficiente de yF3 = 0 
Coeficiente de xF1 = 0  valor de y1 = 0 Valor de xF1 = 10  Coeficiente de y1 = 10 
Coeficiente de xF2 = 0  valor de y2 = 0 Valor de xF2 = 12  Coeficiente de y2 = 12 
Coeficiente de xF3 = 0  valor de y3 = 0 Valor de xF3 = 9  Coeficiente de y3 = 9 
 
Resolvendo o primal: 
Lin. z x1 x2 x3 xF1 xF2 xF3 b 
1 1 -1 -2 -3 0 0 0 0 
2 0 1 1 1 1 0 0 10 
3 0 2 1 4 0 1 0 12 
4 0 1 3 -1 0 0 1 9 
 Entra 
 
Nova solução básica 
 Entra na base a variável com coeficiente negativo de maior valor absoluto na função objetivo  Entra 
a variável x3 
 Sai da base a variável que primeiro se anula com a variável escolhida para entrar na base  Dividindo-
se os termos da direita das restrições pelos coeficientes positivos da variável que entra na restrição: 
 
Lin. z x1 x2 x3 xF1 xF2 xF3 b 
1 1 -1 -2 -3 0 0 0 0 
2 0 1 1 1 1 0 0 10 10 / 1 = 10 
3 0 2 1 4 0 1 0 12 12 / 4 = 3  menor  Sai 
4 0 1 3 -1 0 0 1 9 9 / -1 = -9 
 Entra 
 
Elemento pivô = 4 – é identificado pela coluna da variável que entra e a linha da variável que sai nas 
restrições 
Dividindo a linha do pivô pelo pivô: 
Lin. z x1 x2 x3 xF1 xF2 xF3 b 
1 1 -1 -2 -3 0 0 0 0 
2 0 1 1 1 1 0 0 10 
3 0/4 2/4 1/4 4/4 0/4 1/4 0/4 12/4 Sai 
4 0 1 3 -1 0 0 1 9 
 Entra 
 
 
 
 
 
Incluindo x3 na base (coeficiente zero na FO e nas restrições) 
Li. z x1 x2 x3 xF1 xF2 xF3 b 
1 1-(-3).0 -1-(-3)0,5 -2-(-3)0,25 -3-(-3)1 0-(-3)0 0-(-3)0,25 0-(-3)0 0-(-3)3 
2 0-1.0 1-1.0,5 1-1.0,25 1-1.1 1-1.0 0-1.0,25 0-1.0 10-1.3 
3 0 0,5 0,25 1 0 0,25 0 3 Sai 
4 0-(-1).0 1-(-1)0,5 3-(-1).0,25 -1-(-1).1 0-(-1).0 0-(-1)0,25 1-(-1).0 9-(-1)3 
 Entra 
 
Li. z x1 x2 x3 xF1 xF2 xF3 b 
1 1 0,5 -1,25 0 0 0,75 0 9 
2 0 0,5 0,75 0 1 -0,25 0 7 
3 0 0,5 0,25 1 0 0,25 0 3 
4 0 1,5 3,25 0 0 0,25 1 12 
 
 
Para o Dual associado: 
Coeficientes de xi (x1=0,5; x2=-1,25; x3=0) valores de yFi (b1=0,5; b2=-1,25; b3=0) 
Coeficientes de xFi (xF1=0; xF2=0,75; xF3=0) valores de yi (y1=0; y2=0,75; y3=0)  y1=0 e y3=0 não 
pertencem à solução básica 
Valores de xi (x1=0; x2=0; x3=3) coeficientes de yFi (yF1=0; yF2=0; yF3=3)  coef.yF1=0 e coef.yF2=0 
pertencem à solução básica 
Valores de xFi (xF1=7; xF2=0; xF3=12) coeficientes de yi (y1=7;y2=0; y3=12)  coef.y2=0 pertence à solução 
básicaAssim, o quadro simplex para o Dual fica: 
Lin. D y1 y2 y3 yF1 yF2 yF3 b 
1 -1 7 0 12 0 0 3 
2 0 1 0 0,5 
3 0 0 1 -1,25 
4 1 0 0 0 
 
 
Nova solução básica para o Primal 
 Entra na base a variável com coeficiente negativo de maior valor absoluto na função objetivo  Entra 
a variável x2 
 Sai da base a variável que primeiro se anula com a variável escolhida para entrar na base  Dividindo-
se os termos da direita das restrições pelos coeficientes positivos da variável que entra na restrição: 
 
Li. z x1 x2 x3 xF1 xF2 xF3 b 
1 1 0,5 -1,25 0 0 0,75 0 9 
2 0 0,5 0,75 0 1 -0,25 0 7 9,333 
3 0 0,5 0,25 1 0 0,25 0 3 12 
4 0 1,5 3,25 0 0 0,25 1 12 3,69  menor  Sai 
 Entra 
 
Elemento pivô = 3,25 – é identificado pela coluna da variável que entra e a linha da variável que sai 
Dividindo a linha do pivô pelo pivô: 
Li. z x1 x2 x3 xF1 xF2 xF3 b 
1 1 0,5 -1,25 0 0 0,75 0 9 
2 0 0,5 0,75 0 1 -0,25 0 7 
3 0 0,5 0,25 1 0 0,25 0 3 
4 0/3,25 1,5/3,25 3,25/3,25 0/3,25 0/3,25 0,25/3,25 1/3,25 12/3,25 Sai 
 Entra 
 
 
 
 
Incluindo x2 na base (coeficiente zero na FO e nas restrições) 
L z x1 x2 x3 xF1 xF2 xF3 b 
1 1-(-1,25)0 0,5-(-1,25)0,461 -1,25-(-1,25)1 0-(-1,25)0 0-(-1,25)0 0,75-(-1,25)0,077 0-(-1,25)0,308 9-(-1,25)3,7 
2 0-0,75.0 0,5-0,75.0,461 0,75-0,75.1 0-0,75.0 1-0,75.0 -0,25-0,75.0,077 0-0,75.0,308 7-0,75.3,69 
3 0-0,25.0 0,5-0,25.0,461 0,25-0,25.1 1-0,25.0 0-0,25.0 0,25-0,25.0,077 0-0,25.0,308 3-0,25.3,69 
4 0 0,461 1 0 0 0,077 0,308 3,692 
 Entra 
 
L z x1 x2 x3 xF1 xF2 xF3 b 
1 1 1,077 0 0 0 0,846 0,385 13,615 
2 0 0,154 0 0 1 -0,308 -0,231 4,231 
3 0 0,125 0 1 0 0,231 -0,077 2,077 
4 0 0,461 1 0 0 0,077 0,308 3,692 
 Entra 
 
Nova solução: 
 Variáveis não básicas: x1 = 0; xF2 = 0; xF3 = 0 
 Variáveis básicas: Valores no vetor b  x2 = 3,692; x3 = 2,077; xF1 = 4,231 
 Valor de Z: Z = 13,615. 
 Todos os coeficientes das variáveis não básicas na função objetivo são positivos  a solução é ótima 
 
Para o Dual associado: 
Coeficientes de xi (x1=1,077; x2=0; x3=0) valores de yFi (b1=1,077; b2=0; b3=0) 
Coeficientes de xFi (xF1=0; xF2=0,846; xF3=0,385) valores de yi (y1=0; y2=0,846,75; y3=0,385)  y1=0 não 
pertence à solução básica 
Valores de xi (x1=0; x2=3,692; x3=2,077) coeficientes de yFi (yF1=0; yF2=3,692; yF3=2,077)  coef.yF1=0 
pertence à solução básica 
Valores de xFi (xF1=4,231; xF2=0; xF3=0) coeficientes de yi (y1=4,321;y2=0; y3=0)  coef.y2=0 e coef.y3=0 
pertencem à solução básica 
 
Assim, o quadro simplex para o Dual fica: 
Lin. D y1 y2 y3 yF1 yF2 yF3 b 
1 -1 4,231 0 0 0 3,692 2,077 -13,615 
2 0 0 0 1 0 1,077 
3 0 1 0 0 -1 0,846 
4 0 0 1 0 0 0,385 
 
 
6.11 Solução do Dual pelo Tableau do Simplex 
 
Considere o seguinte PPL 
Min 2 x1 + x2 + x3 
s.a. 
3 x1 + 2 x2  2 
 x3  5 
x1, x2, x3  0 
 
Problema dual: 
Max 2 y1 + 5 y2 
s.a. 
y1  2 
y1  1 
 y2  1 
y1, y2  0 
 
 
 
 
Então o tableau correspondente ao problema primal é: 
L z x1 x2 x3 xF1 xF2 b 
1 1 2 1 1 0 0 0 
2 0 3 2 0 -1 0 2 
4 0 0 0 1 0 -1 5 
 
 
O tableau que corresponde à solução ótima para este problema é: 
L z x1 x2 x3 xF1 xF2 b 
1 1 1 0 0 1 1 -7 
2 0 1 1 0 -1 0 2 
4 0 0 0 1 0 -1 5 
 
 
A solução do dual pode ser obtida facilmente observando o tableau e considerando uma propriedade 
importante que relaciona as variáveis primal-dual. 
 
PRIMAL 
Variáveis naturais Variáveis de folga 
Var. Básicas Var. Não Básicas Var. Básicas Var. Não Básicas 
DUAL 
Var. Não Básicas Var. Básicas Var. Não Básicas Var. Básicas 
Variáveis de folga Variáveis naturais 
 
A tabela acima indica que as variáveis naturais do problema primal estão associadas às variáveis de folga do 
problema dual e as variáveis de folga do problema primal estão associadas às variáveis naturais do dual. 
Portanto, segundo esta propriedade pode-se olhar para a primeira linha do tableau ótimo do simplex e 
encontrar os valores das variáveis duais, isto é: 
 
L z x1 x2 x3 xF1 xF2 b 
1 1 1 0 0 1 1 -7 
2 0 1 1 0 -1 0 2 
4 0 0 0 1 0 -1 5 
 D yF1 yF2 yF3 y1 y2 b 
 
Por outro lado, uma outra propriedade diz que a solução ótima do primal é igual à solução ótima do dual, 
isto pode ser facilmente confirmado substituindo os valores das variáveis na função objetivo do poblema 
dual original: 
Max D = 2 y1 + 5 y2 
s.a. 
y1  2 
y1  1 
 y2  1 
y1, y2  0 
 
6.12 Solução do Dual através das Folgas Complementares 
 
Uma das relações mais importantes dos problemas primal e dual é a correspondência direta entre as suas 
soluções básicas. A chave é a última fila do tableau simplex. 
Então para ver uma solução básica do dual devemos observar a última fila do tableau simplex. Isto, pois 
cada variável do primal é uma variável associada no problema dual: 
 
Variável Primal Variável dual associada 
(Variável Original) xj 
(Variável de folga) xFn+j 
yFm+i (variável adicional) j = 1, 2, .. , n 
yi (variável original) i = 1, 2, .. , m 
 
O nome das folgas complementares diz que para cada par de variáveis associadas, se uma delas tiver folga 
na sua restrição de não negatividade (variáveis básicas > 0) então a outra não deve ter folga (variável não 
básica = 0), isto é equivalente a: 
 xj . yFm+i = 0, j = 1, 2, ... , n 
xFn+j . yi = 0, i = 1, 2, ... , m 
 
Considere o seguinte problema primal: 
Min 2 x1 + 3 x2 + 4 x3 + 2 x4 
s.a. 
x1 + x2 - 2 x3 + 2 x4  1 
2 x1 – 2 x2 + x3 + x4  1 
x1, x2, x3, x4  0 
A solução deste problema pelo método simplex pode ser muito demorada, dado o número de variáveis e 
o número de restrições. 
Ao invés de resolver o primal, pode-se determinar o dual do problema: 
Max y1 + y2 
Sujeito a: 
 y1 + 2 y2  2 
 y1 + 2 y2  3 
- 2 y1 + y2  4 
 2 y1 + y2  2 
y1, y2  0 
Podemos obter a solução do dual pelo método gráfico, onde determina-se os valores de y1 = 2/3 e y2 = 2/3, 
e o valor da função objetivo igual a 4/3, para obter os valores das variáveis de folga passa-se as restrições 
para a forma padrão, e obtém-se: 
 y1 + 2 y2 + yF1 = 2 
 y1 + 2 y2 + yF2 = 3 
- 2 y1 + y2 + yF3 = 4 
 2 y1 + y2 + yF4 = 2 
Logo: 










































0
3/14
3/11
0
3/2
3/2
*
4
3
2
1
2
1
yF
yF
yF
yF
y
y
y 
Para achar os valores das variáveis primais utiliza-se o teorema das folgas complementares, que diz que 
quando na solução ótima, tem-se: 









2
1
4
3
2
1
..
..
xF
xF
FV
x
x
x
x
OV
 
..
..
2
1
4
3
2
1
OV
y
y
FV
yF
yF
yF
yF









 
Isto é: 
2
1
4
3
2
1
xF
xF
x
x
x
x
0
0
0
0
0
0
2
1
4
3
2
1






y
y
yF
yF
yF
yF
 
Sendo que os valores de yF2, yF3, y1, y2 são diferentes de zero, então x2 = x3 = xF1 = xF2 = 0. Para obter os 
valores que faltam, coloca-se as restrições na forma padrão incrementando as variáveis de folga: 
x1 + x2 - 2 x3 + 2 x4 – xF1 = 1 
2 x1 – 2 x2 + x3 + x4 – xF2 = 1 
Agora, substituem-se os valores já achados nestas restrições e tem-se: 
x1 + 2 x4 = 1 
2 x1 + x4 = 1 
resolvendo este sistema de equações tem-se que x1 = 1/3 e x4 = 1/3 e o valor da função objetivo sendo 4/3 
 
6.13 Teoremas e Propriedades 
 
A teoria da Dualidade consiste no estudo do conjunto de técnicas e características que envolvem o par: 
problema primal-dual. 
 
Seja o problema primal: 
Max cT x 
s.a. 
A x  b 
 x  0 
 
e o seu dual 
Min bT y 
s.a. 
AT y  c 
 y  0 
Têm-se as seguintes propriedades: 
 
(i) Propriedade da Dualidade Fraca 
Seja x uma solução viável para o problema primal e y seja uma solução viável para o problema dual, então: 
cTx  bT y 
Isto se explica devido a que o valor viável máximo de cTx é igual ao valorviável mínimo de bTy. 
 
(ii) Propriedade da Dualidade Forte 
Se x* é uma solução ótima para o problema primal e y* é uma solução ótima para o problema dual, então: 
cTx* = bT y* 
 
(iii) Propriedade das soluções complementares 
Em cada iteração, o método simplex identifica simultaneamente uma solução viável x para o problema 
primal e uma solução complementar y para o problema dual onde: 
cTx = bTy 
Se x não é ótimo para o problema primal, então y não é viável para o problema dual. 
 
(iv) Propriedade das soluções ótimas complementares 
Na iteração final, o método simplex identifica simultaneamente uma solução ótima x* para o problema 
primal e a solução ótima complementar y* para o problema dual (que pode ser achado na última linha do 
tableau), onde: 
cT x* = bTy* 
 O yi* são os preços sombra para o problema primal. 
 
(v) Propriedade da Simetria 
Para qualquer problema e seu problema dual, todas as relações entre eles devem ser simétricas pois o dual 
do problema dual é o problema primal. 
 
 
 
(vi) Folgas complementares 
Uma das relações mais importantes dos problemas primal e dual é a correspondência direta entre as suas 
soluções básicas. A chave é a última fila do tableau simplex. 
Então para ver uma solução básica do dual devemos observar a última fila do tableau simplex. Isto devido a 
que cada variável do primal é uma variável associada no problema dual tal como é mostrado na tabela a 
seguir: 
Variável Primal Variável dual associada 
(Variável Original) xj 
(Variável de folga) xFn+j 
yFm+i (variável adicional) j = 1, 2, .. , n 
yi (variável original) i = 1, 2, .. , m 
 
O nome das folgas complementares diz que para cada par de variáveis associadas, se uma delas tiver folga 
na sua restrição de não negatividade (variáveis básicas > 0) então a outra não deve ter folga (variável não 
básica = 0), isto é equivalente a: 
xj . yFj = 0, j = 1, 2, ... , n 
xFi . yi = 0, i = 1, 2, ... , m 
 
6.14 Interpretação Econômica do Dual 
 
Pode-se utilizar os preços sombra obtidos no tableau simplex (ultima fila do tableu), 
Preços sombra: Os problemas de programação linear são na maior parte dos casos interpretados como a 
alocação de recursos à atividades, onde tem-se restrição às quantidades dos respectivos recursos para cada 
atividade. Em muitos casos, podem ficar disponíveis unidades de recursos, mas só depois de consideração 
de parte da gerencia. Em consequência, é importante ter informação disponível sobre a contribuição 
econômica de cada recurso para a função objetivo. 
Logo, o preço sombra mede o valor marginal do recurso associado, i.e. a quantidade em que a função 
objetivo será incrementada (ou diminuída, dependendo da função objetivo), incrementado (ou 
diminuindo) a quantidade disponível do recurso bi 
 
6.14.1 Exemplo-1: Problema da dieta 
Tem-se 5 tipos de alimentos, os nutrientes de cada um destes alimentos e o seu custo, sendo o objetivo 
minimizar o custo dos alimentos, sujeito a requerimentos diários mínimos de calorias e vitaminas. 
 
Problema Primal da dieta 
Min 20 x1 + 25 x2 + 31 x3 + 11 x4 + 12 x5 
Sujeito a: x1 + + x3 + x4 + 2 x5  21 (calorias) 
 x2 + 2 x3 + x4 + x5  12 (vitaminas) 
x1, x2, x3, x4, x5  0 
xj : quantidade do alimento j. 
aij : quantidade do nutriente i por unidade de alimento j. 
 
Problema Dual da Dieta 
O problema dual associado ao problema da dieta poderia ser descrito como segue: 
Um fabricante de comprimidos deseja fabricar uma pílula de vitamina e uma de caloria que possam 
competir com os alimentos oferecidos e maximizar sua receita. 
 
y1 : preço da pílula de caloria 
y2 : preço da pílula de vitamina 
 
Max 21 y1 + 12 y2 
Sujeito a: y1  20 
 y2  25 
 y1 + 2 y2  31 
 y1 + y2  11 
2 y1 + y2  12 
 y1, y2  0 
 
6.14.2 Exemplo-2: Problema da Refinaria 
Uma refinaria tem 3 processos para produzir gasolina nas quantidades xi (em 100 galões). 
 
 Regular S/chumbo Premium Custo x hora 
Processo-1 3 4 2 160 
Processo-2 6 6 8 400 
Processo-3 6 3 4 300 
Demanda 36 20 30 
 
O problema Primal trata-se de um problema de minimização de custo 
Min 160 x1 + 400 x2 + 300 x3 
Sujeito a: 
3 x1 + 6 x2 + 6 x3  36 .................. Tipo de gasolina regular 
4 x1 + 6 x2 + 3 x3  20 .................. Tipo de gasolina sem chumbo 
2 x1 + 8 x2 + 4 x3  20 .................. Tipo de gasolina premium 
x1, x2, x3, x4, x5  0 
xj : número de horas de operação do processo j. 
 
O dual deste problema é um problema de maximização do preço da gasolina do tipo i. 
Max 36 y1 + 20 y2 + 30 y3 
Sujeito a: 
3 y1 + 4 y2 + 2 y3  160 .................. Processo 1 
6 y1 + 6 y2 + 8 y3  400 .................. Processo 2 
6 y1 + 3 y2 + 4 y3  300 .................. Processo 3 
y1, y2, y3  0 
yi : R$/g da gasolina i 
 
Se a demanda de algum tipo de gasolina diminuir, qual será o cenário mais conveniente, i.e. o que poderia 
ocasionar a maior diminuição de custos? 
Resposta: 
Para resolver este problema observa-se os preços sombra correspondentes a cada restrição, y1, y2 e y3, o 
que tiver o maior valor, a restrição associada, ou seja o processo associado tem o maior valor marginal, o 
que ocasionará a maior diminuição 
 
Para visualizar melhor considere o seguinte problema de maximização de lucro: 
Max 3 x1 + 5 x2 
s.a. 
x1  4 
 2x2  12 
3x1 + 2x2  18 
x1, x2  0 
A solução ótima deste problema é: 
x1 = 2, x2 = 6, x3 = 2 
onde os preços sombra para os recursos 1, 2 e 3 (valores das variáveis duais) são: y1* = 0, y2* = 3/2, y3* = 1. 
 
Tableau ótimo para o problema anterior: 
L z x1 x2 x3 xF1 xF2 b 
1 1 0 0 0 1,5 1 36 
2 0 0 0 1 0,333 -0,333 2 
3 0 0 1 0 0,5 0 6 
4 0 1 0 0 -0,333 0,333 2 
 
 
Logo, se puder ficar disponível um recurso, aquele com maior valor marginal deve ser priorizado, neste 
caso o recurso 2. 
 
6.15 Exercícios 
 
Formulação do Problema Dual associado ao Primal dos seguintes Problemas de Programação Linear 
 
6.15.1 Um distribuidor de ferragens planeja vender pacotes com porcas e parafusos misturados. Cada 
pacote pesa pelo menos 2 Kg. Três tamanhos de porcas e parafusos compõem o pacote e se compram em 
lotes de 200 Kg. Os tamanhos 1, 2 e 3 custam respectivamente R$ 20, R$ 80 e R$ 12. O peso combinado de 
unidades de tamanhos 1 e 3 deve ser pelo menos a metade do peso total do pacote. O peso combinado de 
unidades de tamanhos 1 e 2 não deve ser maior que 1,6 Kg. O peso de unidades de qualquer tamanho 
deve ser pelo menos 10 % do peso total do pacote. 
Qual será a composição do pacote de forma que o custo seja mínimo, considerando-se a unidade = porca + 
parafuso? 
 
6.15.2 Uma microempresa tem disponíveis os seguintes tecidos: 16 m2 de algodão, 11 m2 de seda e 15 m2 
de lã. Para confeccionar um terno padrão, são necessários 2 m2 de algodão, 1m2 de seda e 1 m2 de lã. Para 
um vestido padrão, são necessários 1 m2 de algodão, 2 m2 de seda e 3 m2 de lã. Se o lucro líquido de um 
terno é de $300 e de um vestido de $500, quantas peças de cada tipo a microempresa deve fabricar para 
ter o maior lucro possível? 
 
6.15.3 Um nutricionista precisa estabelecer uma dieta contendo, pelo menos, 10 unidades de vitamina A, 
30 unidades de vitamina B e 18 unidades de vitamina C. Essas vitaminas estão contidas em quantidades 
variadas em cinco alimentos (I, II, III, IV e V). A tabela seguinte fornece o número de unidades das 
vitaminas A, B e C em cada unidade desses cinco alimentos, bem como seu custo ($) por unidade. 
 
 I II III IV V 
Vitamina A 0 1 5 4 3 
Vitamina B 2 1 0 3 2 
Vitamina C 3 1 0 9 0 
Custo ($) 4 2 1 10 5 
 
Quais as quantidades dos cinco alimentos que devem ser incluídas na dieta diária, a fim de encontrarmos 
esses teores de vitaminas com o menor custo? Construa o modelo. 
 
6.15.4 Um fábrica de papel recebeu três pedidos, mostrados na tabela a seguir. 
 
Encomenda Largura (m) Comprimento (m) 
I 5 10000 
II 7 30000 
III 920000 
 
Para produzir estes padrões, dispões de dois rolos de 10m e 20m de largura, que não podem ser 
emendados na largura. Formular o problema que dá o esquema de corte com perda mínima em área. 
 
6.15.5 Uma pequena fábrica de papel toalha manufatura três tipos de produtos A, B e C. A fábrica recebe 
o papel em grandes rolos. O papel é cortado, dobrado e empacotado. Dada a pequena escala da fábrica, o 
mercado absorverá qualquer produção a um preço constante. O lucro unitário de cada produto é 
respectivamente R$ 1,00, R$ 1,50, e R$ 2,00. 
O quadro abaixo identifica o tempo requerido para operação (em horas) em cada seção da fábrica, bem 
como a quantidade de máquinas disponíveis, sendo que cada máquina trabalha 40 horas por semana. 
Planeje a produção semanal da fábrica, para que o lucro seja máximo. 
 
Seção Produto A Produto B Produto C No de Máquinas 
Corte 8 5 2 3 
Dobra 5 10 4 10 
Empacotamento 0,7 1 2 2 
 
6.15.6 A editora Bücher está lançando um novo livro de Programação Linear no mercado, com edições em 
capa dura e comum. O custo com cada edição de capa dura é de $5, enquanto que a capa comum custa $3. 
Cada finalização do livro em capa dura demora 3 minutos, enquanto que a edição comum consome apenas 
2 minutos. O tempo total disponível para finalização é de 800 horas. 
Através de sua experiência, o editor sabe que ele necessita de pelo menos 10000 unidades do livro em capa 
dura e não mais de 6000 unidades da edição comum. O preço de venda das unidades de capa dura e 
comum será, respectivamente, $ 9 e $6. 
Modelo o PPL que permite encontrar o número de edições em capa dura e comum, de modo que o lucro 
obtido pela editora seja máximo. 
 
6.16 Bibliografia 
 
[01] LACHTERMACHER, Gerson, Pesquisa Operacional na Tomada de Decisão, Rio de Janeiro, ed. Campus, 
2002. 
[02] GOLDBARG, Marcos. C., LUNA, Henrique Pacca, Otimização Combinatória e Programação Linear, Rio de 
Janeiro, ed. Campus, 2000. 
[03] ANDRADE, Eduardo Leopoldino, Introdução à Pesquisa Operacional, Ed. LTC, Rio de Janeiro, 2000. 
[04] SILVA, Ermes Medeiros .et al., Pesquisa Operacional, Ed. Atlas, São Paulo, 1998. 
[05] BREGALDA, Paulo. F., OLIVEIRA, Antônio. A., BORNSTEIN, Cláudio, Introdução à Programação Linear, 
Rio de Janeiro, ed. Campus, 1988. 
[06] PUCCINI, Abelardo, Introdução à Programação Linear, São Paulo,ed. LTC, 1983. 
[07] HAMACHER, Silvio, LUSTOSA, Leonardo., Sistemas de Modelagem: Evolução e Perspectivas, 
Proceedings of the IX CLAIO , Buenos Aires,1998. 
[08] HILLIER, F. S., LIEBERMAN, G.J., Introdução à Pesquisa Operacional, Rio de Janeiro, ed Campus, 1988. 
[09] NEMHAUSER, L. G., Integer and Combinatorial Optimization, Wolsey Wiley-Interscience, 1999. 
[10] TAHA, H., Operations Research : an introduction, Prentice Hall, 1996. 
[11] WILLIAMS, H. P., Model Building in Mathematical Programming, John Wiley & Sons, 1999.