Dualidade em Programação Linear

Prévia do material em texto

Capítulo 3. Dualidade e Análise de Sensibilidade 
 
 Apontamentos de Investigação Operacional 39 Alberto Mulenga 
 
 
3. DUALIDADE E ANÁLISE DE SENSIBILIDADE 
 
3.1 DUALIDADE EM PROGRAMAÇÃO LINEAR 
 
Todo o problema de programação linear, a que chamamos primal, tem associado a ele um 
correspondente problema, chamado dual; ambos são complementares e relacionados de 
forma que a solução óptima de um fornece informações completas sobre o outro. 
 
3.1.1 TRANSFORMAÇÃO DE UM PROBLEMA PRIMAL EM DUAL 
 
Seja dado o seguinte problema de programação linear, na forma literal ou canónica, 
problema primal. 
 
Maximizar z = c1x1+c2x2+c3x3+...+cmxm 
Sujeito à 














njmix
bxaxaxaxa
bxaxaxaxa
bxaxaxaxa
i
nmnmnnn
mm
mm
,1 ; ,1 ;0
...
...
...
332211
22323222121
11313212111
 
 
O seu problema dual pode ser escrito na forma canónica assim. 
Minimizar w = b1y1+b2y2+b3y3+...+bnyn 
Sujeito à 














njmiy
cyayayaya
cyayayaya
cyayayaya
i
mnnmmmm
nn
nn
,1 ; ,1 ;0
...
...
...
332211
22332222112
11331221111
 
 
As variáveis yj são chamadas variáveis duais. 
 
O problema dual, para os modelos em que o conjunto das restrições tem um único tipo de 
desigualdades por exemplo  ou , é construído a partir do primal da seguinte forma: 
 
Regras: 
Regra 1. Cada linha do problema primal (restrição), corresponde a uma variável no dual 
(coluna); 
Regra 2. Os termos independentes das restrições (recursos), passam para coeficientes da 
função objectivo no dual; 
Regra 3. Se o primal é um problema de maximização, o seu dual será um problema de 
minimização e vice- versa; 
Regra 4. As variáveis do primal e dual são não negativas. 
 
Capítulo 3. Dualidade e Análise de Sensibilidade 
 
 Apontamentos de Investigação Operacional 40 Alberto Mulenga 
 
 
Exemplo 3.1. Apresentar o problema dual do seguinte problema de maximização de 
programação linear. 
 
Max z = x1 + 2x2 
Sujeito à 














0
80
2025
152
185
21
21
21
21
ix
xx
xx
xx
xx
 
 
O problema dual correspondente é: Min w = 18y1+15y2+20y3+8y4 
 Sujeito à 








0
2125
1052
4321
4321
iy
yyyy
yyyy
 
 
Voltando a transformação de um primal no seu dual, consideremos a forma matricial dos 
problemas: 
 
Problema Primal Problema Dual 
Max z =  















m
m
x
x
x
ccc
...
 ... 
2
1
21 
Suj à 












































nm b
b
b
x
x
x
......
a ... a a
.....................
a ... a a
a ... a a
2
1
2
1
nmn2n1
2m2221
1m1211
 
Min  















n
n
y
y
y
bbbw
...
 ... 
2
1
21 
Suj à












































mn c
c
c
y
y
y
......
a ... a a
.....................
a ... a a
a ... a a
2
1
2
1
nm2m1m
n22212
n12111
 
 
A seguinte tabela mostra as relações entre o problema primal e dual. 
 
 Problema Primal Problema Dual 
 n restrições e m variáveis 
 coeficientes da função objectivo 
 constantes 
Problema (max) Problema (min) 
Restrição (P) Variável (D) 
    0 
    0 
 =  não restrita 
 n variáveis e m restrições 
 constantes 
 coeficientes da função objectivo 
Problema (max) Problema (min) 
Variável (P) Restrição (D) 
  0   
  0   
 não restrita  = 
 
 
Capítulo 3. Dualidade e Análise de Sensibilidade 
 
 Apontamentos de Investigação Operacional 41 Alberto Mulenga 
 
 
Da representação matricial, pode-se concluir que os coeficientes do problema dual são 
formados pela matriz transposta dos coeficientes do problema primal. 
 
Primal  max Z = CX min W = BY  Dual 
 Suj à 





0X
BAX
 Suj à 





0Y
CYAt
 
 
Onde A é matriz dos coeficientes do problema primal e A
t
 é a matriz transposta de A, 
calculada trocando as linhas com as colunas de A. 
 
Exemplo 3.2. Formar o dual do problema. 
Min w = 4x1 + 8x2 
Sujeito à 











0
2215
1811
4073
21
21
21
ix
xx
xx
xx
 
 
Resolução 
O problema primal tem 3 restrições, portanto 3 variáveis duais sendo a terceira não 
restrita. 
 
Etapa 1. transformar a equação em duas inequações. 
 
Min w = 4x1 + 8x2 
 
Sujeito à 














0
2215
2215
1811
4073
21
21
21
21
ix
xx
xx
xx
xx
 
 
Etapa 2. Escrever o dual correspondente com y3 = y3
+
- y3
-
 
 
Max z = 40y1 + 18y2 + 22y3
+
 - 22y3
- 
Max z = 40y1 + 18y2 + 22y3 
 
Suj à 











0;0;0
81117
45513
33
3321
3321
yyy
yyyy
yyyy
i
 ou Suj à 








restrito nao ;0
8117
4513
3
321
321
yy
yyy
yyy
i
 
 
 
 
 
Capítulo 3. Dualidade e Análise de Sensibilidade 
 
 Apontamentos de Investigação Operacional 42 Alberto Mulenga 
 
 
3.1.2 INTERPRETAÇÃO ECONÓMICA DAS VARIÁVEIS DUAIS 
 
As variáveis duais podem receber uma interpretação económica, que leva ao cálculo da 
utilidade marginal (preço de sombra, valor marginal, etc.) dos recursos. Vejamos as 
relações das suas soluções através de um exemplo. 
 
Exemplo 3.3. Uma indústria dispõe de três recursos A, B e C, em quantidades limitadas, 
com os quais pretende produzir dois produtos: produto 1 e produto 2. A tabela a baixo dá 
a utilização unitária de cada recurso em cada um dos produtos e a disponibilidade de cada 
recurso. A indústria sabe que cada unidade produzida do produto 1 dá uma margem 
unitária de lucro de 5 u.m., e cada unidade produzida do produto 2 dá uma margem 
unitária de lucro de 6 u.m. O problema da programação da produção da empresa é 
determinar a quantidade a ser feita dos produtos 1 e 2, de forma a maximizar a margem 
total de lucro. 
 
Recurso Recurso gasto para fazer 1 unidade de Disponibilidade 
 Produto 1 Produto 2 
A 
B 
C 
1 
1 
7 
2 
1 
4 
14 
9 
56 
 
Resolução 
Problema 1: 
Maximizar z = 5x1 + 6x2 
Sujeito à 











0
5647
911
1421
21
21
21
ix
xx
xx
xx
 
 
Suponhamos que a indústria tenha a alternativa de vender os recursos A, B e C, em vez 
de empregá-los na produção dos dois produtos. 
 
O problema agora é encontrar o valor de cada unidade do recurso. É evidente que a venda 
dos recursos deve fornecer um ganho pelo menos igual ao obtido com a utilização deles 
na produção. 
 
Sejam 
y1 valor do recurso A por unidade; 
y2 valor do recurso B por unidade e 
y3 valor do recurso C por unidade 
 
O valor total do estoque dos recursos é: 14y1 + 9y2 + 56y3 
 
 
 
Capítulo 3. Dualidade e Análise de Sensibilidade 
 
 Apontamentos de Investigação Operacional 43 Alberto Mulenga 
 
 
 
Por outro lado, cada um dos produtos pode ser avaliado, levando em conta a utilização 
dos recursos por unidade fabricada. Assim, o produto 1 gasta 1 unidade do recurso A, 1 
unidade de B e 7 unidades de C, sua avaliação em termos do conteúdo de recurso é: 
1y1 + 1y2 + 7y3 
 
Para o produto 2, analogamente a avaliação é: 2y1 + 1y2 + 4y3 
 
É claroque essas avaliações dos produtos não podem ser inferiores as margens unitárias 
de lucro fornecidas por cada um. Assim podemos escrever: 
 
Produto1. 1y1+1y2+7y3  5 
Produto 2. 2y1+1y2+4y3  6 
 
Neste conjunto de inequações o administrador tem interesse em determinar o valor 
mínimo do estoque total, tendo em conta que as avaliações dos produtos sejam pelo 
menos iguais aos lucros unitários fornecidos. Em termos de programação linear, estamos 
a descrever o problema dual. 
 
Problema 2 
Minimizar W = 14y1+9y2+56y3 
Sujeito à 








0
6412
5711
321
321
iy
yyy
yyy
 
 
Conforme as definições anteriores, o problema 1 é primal e o problema 2 é o dual. 
 
Portanto, as variáveis duais podem ser interpretadas como avaliações unitárias dos 
recursos relativos as contribuições de cada um para a obtenção do lucro total. Isto 
significa que, resolvidos os problemas, as variáveis duais indicam as variações que 
ocorrem no valor da função objectivo do primal, para variações unitárias nos níveis dos 
recursos. 
 
Relações entre os valores óptimos do primal e do dual 
 
Resolução do problema primal 
Atenção: vamos designar de yi as variáveis de folga. 
 
Maximizar Z = 5x1 + 6x2 +0y1+0y2+0y3 
 
 
Capítulo 3. Dualidade e Análise de Sensibilidade 
 
 Apontamentos de Investigação Operacional 44 Alberto Mulenga 
 
 
Sujeito à 











0;0
5610047
901011
1400121
32121
32121
32121
ii yx
yyyxx
yyyxx
yyyxx
 
Tabela simplex inicial 
Base x1 x2 y1 y2 y3 bi 
y1 
y2 
y3 
 1 2 1 0 0 
 1 1 0 1 0 
 7 4 0 0 1 
14  (7) 
 9  (9) 
56  (14) 
Z -5 -6 0 0 0 0 
1
a
 iteração 
Base x1 x2 y1 y2 y3 bi 
x2 
y2 
y3 
1/2 1 1/2 0 0 
1/2 0 -1/2 1 0 
 5 0 -2 0 1 
7  l1’=1/2l1 
2  l2’=l2-l1’ 
28 l3’=l3-4l1’ 
z -2 0 3 0 0 42 l4’=l4+6l1’ 
2
a
 Iteração 
Base x1 x2 y1 y2 y3 bi 
X2 
x1 
y3 
 0 1 1 -1 0 
 1 0 -1 2 0 
 0 0 3 -10 1 
5  l1’=l1-1/2l2’ 
4  l2’=2l2’ 
8  l3’=l3-5l2’ 
Z 0 0 1 4 0 50 l4’=l4+2l2’ 
 
Solução primal: x1= 4; x2 = 5; y1 = 0; y2 = 0; y3 = 8 e Zmax = 50 
 
Resolução do problema dual. Designando por xi as variáveis de excesso e ai as variáveis 
artificiais, logo estamos numa escolha entre o método de grande M e o método de duas 
fases; vamos optar pelo método de duas fases. 
Minimizar W = 14y1+9y2+56y3+0x1+0x2+0a1+0a1 
Sujeito à 








0;0;0
61010412
50101711
2121321
2121321
iii axy
aaxxyyy
aaxxyyy
 
 
Tabela inicial simplex (1
a
 fase) 
base Y1 y2 y3 x1 x2 a1 a2 bi 
a1 
a2 
 1 1 7 -1 0 1 0 
 2 1 4 0 -1 0 1 
5  (0.71) 
6  (1.5) 
W -14 –9 -56 0 0 0 0 0 
Za -3 -2 -11 1 1 0 0 -11 
1
a
 Fase (iteração 1) 
base y1 y2 y3 x1 x2 a1 a2 bi 
 
Capítulo 3. Dualidade e Análise de Sensibilidade 
 
 Apontamentos de Investigação Operacional 45 Alberto Mulenga 
 
 
y3 
a2 
1/7 1/7 1 -1/7 0 1/7 0 
10/7 3/7 0 4/7 -1 -4/7 1 
5/7 l1’=1/7l1 
22/7 L2’=l2-4l1’ 
W -6 –1 0 -8 0 8 0 40 L3’=l3+56l1’ 
Za -10/7 -3/7 0 -4/7 1 11/7 0 -22/7l4’=l4+11l1’ 
1
a
 Fase (iteração 2) 
base y1 y2 y3 x1 x2 a1 a2 bi 
y3 
y1 
 0 1/10 1 -1/5 1/10 1/5 –1/10 
 1 3/10 0 2/5 -7/10 –2/5 7/10 
2/5 l1’=l1-1/7l2’ 
11/5 L2’=7/10l2’ 
W 0 4/5 0 –28/5 –21/5 28/5 21/5 266/5 L3’=l3+6l2’ 
Za 0 0 0 0 0 1 1 0 l4’=l4+10/7l2’ 
 
Za = 0; a1 = 0 e a2 = 0, logo devemos passar para a segunda fase. 
 
Tabela simplex inicial (2
a
 fase) 
base y1 y2 y3 x1 x2 bi 
y3 
y1 
 0 1/10 1 -1/5 1/10 
 1 3/10 0 2/5 -7/10 
2/5  (4) 
11/5  (22/3) 
W 0 4/5 0 –28/5 –21/5 266/5 
2
a
 fase (iteração 1) 
base y1 y2 y3 x1 x2 bi 
y2 
y1 
 0 1 10 -2 1 
 1 0 -3 1 -1 
4  l1’=10l1 
1  l2’=l2-3/10l1’ 
W 0 0 -8 -4 -5 50  l3’=l3-4/5l1’ 
 
Solução dual y1=1; y2 = 4; y3 = 0; x1 = 0; x2 = 0 com Wmin = 50 
 
Comparando as duas tabelas terminais e as soluções obtidas chega-se as conclusões ou 
relações: 
 
Relação 1. Para quaisquer duas soluções viáveis possíveis do primal e dual, tem-se 
 Z  W  exemplo z = 42 e w = 266/5. 
 
Relação 2. As soluções óptimas dos dois problemas guardam entre se a relação: 
Max Z = Min W  Zmax = Wmin = 50 
 
Relação 3. Os valores das variáveis duais podem ser obtidos da solução do problema 
primal, bastando tomar os coeficientes da última linha das variáveis básicas iniciais. Se o 
dual é de maximizar, lemos os valores tal como estão, caso contrário lemos com o sinal 
oposto, portanto: 
 
Saindo de max (P) para min (D) 
 Solução primal: x1 = 4; x2 = 5; y1 = 0; y2 = 0; y3 = 8; Zmax = 50 
 
Capítulo 3. Dualidade e Análise de Sensibilidade 
 
 Apontamentos de Investigação Operacional 46 Alberto Mulenga 
 
 
 Solução dual: y1 = 1; y2 = 4; y3 = 0; x1 = 0; x2 = 0; Wmin = 50 
 
 Saindo de min (P) para max (D) 
 Solução dual: y1 = 1; y2 = 4; y3 = 0; x1 = 0; x2 = 0; Wmin = 50 
 Solução primal x1 = 4; x2 = 5; y1 = 0; y2 = 0; y3 = 8; Zmax = 50