Dualiadade - Primal/Dual

Prévia do material em texto

X - D U A L I D A D E 
 
 
 
 
 
 • 1 - Introdução. Regras de transformação "Primal - Dual" 
 
Consideremos os dois problemas P1 e P2 de Programação Linear seguintes: 
 
P1 : 
 n 
 Maximizar F = Σ ck . Xk 
 k = 1 
sujeito a: 
 n 
 Σ aik . Xk ≤ bi i = 1, 2, ... , m 
 k = 1 
 
 Xk ≥ 0 k = 1, 2, ... , n 
 
 
P2 : 
 m 
 Minimizar G = Σ bi . Ui 
 i = 1 
sujeito a: 
 m 
 Σ aik . Ui ≥ ck k = 1, 2, ... , n 
 i = 1 
 
 Ui ≥ 0 i = 1, 2, ... , m 
 
 
ou, utilizando a notação matricial: 
 
 
P1 : 
 
 Maximizar F = C . X 
 
sujeito a: 
 A . X ≤ b 
 
 X ≥ 0n 
 
 
 P2 : 
 
 Minimizar G = bT . U 
 
 sujeito a: 
 AT . U ≥ CT 
 
 U ≥ 0m 
R
uy
 C
os
ta
, 2
00
6 
 100
 Na representação anterior, o vector das incógnitas de P1, X, é um vector coluna 
( n x 1 ), o vector das incógnitas de P2, U, é um vector coluna ( m x 1 ), C é um vector linha 
( 1 x n ), A é uma matriz ( m x n ) e b é um vector coluna ( m x 1 ). De notar que 0n é o vector 
nulo do tipo ( n x 1 ) e que 0m é o vector nulo do tipo ( m x 1 ). 
 
 
 P1 e P2 formam um par de problemas duais, isto é, P1 é o problema dual de P2 
e vice-versa. 
 
 
 Algumas Regras de Transformação "Primal-Dual" podem ser enunciadas: 
 
R1 : A cada restrição do problema primal corresponde uma variável do 
problema dual. 
 
 A cada variável do problema primal corresponde uma restrição do 
problema dual. 
 
 
R1 : 
 
restrição P ↔ variável D ; variável P ↔ restrição D 
 
 
 
 
R2 : A matriz dos coeficientes das restrições do problema dual é a 
transposta da matriz dos coeficientes das restrições do correspondente 
problema primal. 
 
 
R2 : 
 
A P = ATD ; A D = ATP 
 
 
 
 
R3 : Os termos independentes das restrições de um dos problemas 
(primal/dual) são os coeficientes da função objectivo no outro problema 
(dual/primal). 
 
 
 
R3 : 
 
Termos independentes P ↔ Coeficientes da f.o. D 
 
Termos independentes D ↔ Coeficientes da f.o. P 
 
 
 
 
R4 : A um problema primal de maximização com restrições do tipo ≤ e 
variáveis não negativas, corresponde um problema dual de minimização 
com restrições do tipo ≥ e variáveis não negativas. 
 
 
 
R4 : 
 
Problema Primal 
 
Max 
restrições ' ≤ ' 
variáveis ' ≥ 0 ' 
 
 
 
 
↔
 
Problema Dual 
 
Min 
restrições ' ≥ ' 
variáveis ' ≥ 0 ' 
 
 
 
 Para podermos aplicar as 'Regras de Transformação' apresentadas, resolvamos os 
seguintes exercícios: 
R
uy
 C
os
ta
, 2
00
6 
 101
Ex.1 : 
 
 
 
 
 Escreva o dual do problema de Programação Linear seguinte: 
 
 MAX F = 2 . X1 + 3 . X2 
 
sujeito a: 
 
 2 . X1 - 3 . X2 ≤ 4 
 - 1 . X1 + 4 . X2 ≤ 5 
 5 . X1 + 2 . X2 ≤ 9 
 6 . X1 - 2 . X2 ≤ 7 
 
 X1 , X2 ≥ 0 . 
 
 
 
ê 
 
Resolução : 
 
 
 
 MIN G = 4 . U1 + 5 . U2 + 9 . U3 + 7 . U4 
 
sujeito a: 
 
 2 . U1 - 1 . U2 + 5 . U3 + 6 . U4 ≥ 2 
 - 3 . U1 + 4 . U2 + 2 . U3 - 2 . U4 ≥ 3 
 
 U1 , U2 , U3 , U4 ≥ 0 . 
 
 
 Note-se que o problema primal apresentado tem m = 4 (número de equações) e 
n = 2 + 4 (número de incógnitas), pelo que a sua resolução pelo Algoritmo Simplex Revisto 
implicaria a manipulação (incluindo inversão) de matrizes B ( 4 x 4 ). O problema dual 
correspondente tem m = 2 (número de equações) e n = 4 + 2 (número de incógnitas), pelo 
que a sua resolução pelo Algoritmo Simplex Revisto implicaria a manipulação de matrizes 
B ( 2 x 2 ) ! Assim, a priori, é mais fácil resolver o problema dual, já que este corresponderá a 
um menor esforço de cálculo... Posteriormente retomaremos esta questão. 
 
 
 
 Ao observarmos as 'Regras de Transformação' apresentadas, em particular a regra 
 
 
 
R4 : 
 
Problema Primal 
 
Max 
restrições ' ≤ ' 
variáveis ' ≥ 0 ' 
 
 
 
 
↔
 
Problema Dual 
 
Min 
restrições ' ≥ ' 
variáveis ' ≥ 0 ' 
 
 
 
 
 
, 
 
pode surgir-nos uma interrogação: O que acontece se uma das restrições for uma 
desigualdade de 'sentido oposto' à regra " Max ; restrição ≤ / Min ; restrição ≥ " ? Para 
tentarmos responder a esta questão, poderemos considerar o seguinte exercício: 
R
uy
 C
os
ta
, 2
00
6 
 
 
 
 102
Ex.2 : 
 
 
 
 
 Escreva o dual do problema de Programação Linear seguinte: 
 
 MIN F = 4 . X1 + 2 . X2 + 1 . X3 
 
sujeito a: 
 
 2 . X1 + 1 . X2 + 3 . X3 ≥ 5 
 2 . X1 - 1 . X2 ≥ 6 
 - 1 . X1 + 3 . X2 + 4 . X3 ≤ 5 
 2 . X2 - 3 . X3 ≥ 4 
 
 X1 , X2 , X3 , X4 ≥ 0 . 
 
 
 
 
 
 
 
 
 
 
 
ê 
 
Resolução : 
 
 A terceira restrição pode ser re-escrita de modo a respeitar a regra 
" Min ; restrição ≥ " : 1 . X1 - 3 . X2 - 4 . X3 ≥ - 5 . Ter-se-ia, 
então, o seguinte problema dual: 
 
 
 MAX G = 5 . U1 + 6 . U2 - 5 . U3 + 4 . U4 
 
sujeito a: 
 
 2 . U1 + 2 . U2 + 1 . U3 ≤ 4 
 1 . U1 - 1 . U2 - 3 . U3 + 2 . U4 ≤ 2 
 3 . U1 - 4 . U3 - 3 . U4 ≤ 1 
 
 U1 , U2 , U3 , U4 ≥ 0 . 
 
 Para mantermos as regras anteriormente enunciadas, muito
especialmente, R2 e R3 deveríamos ter os simétricos dos coeficientes 
de U3 (relativamente ao problema dual apresentado), o que se 
consegue facilmente considerando U3 ≤ 0, ou seja, 
 
 
 MAX G = 5 . U1 + 6 . U2 + 5 . U3 + 4 . U4 
 
sujeito a: 
 
 2 . U1 + 2 . U2 - 1 . U3 ≤ 4 
 1 . U1 - 1 . U2 + 3 . U3 + 2 . U4 ≤ 2 
 3 . U1 + 4 . U3 - 3 . U4 ≤ 1 
 
 
 U1 , U2 , U4 ≥ 0 ; 
 
 
U3 ≤ 0 .
 
 R
uy
 C
os
ta
, 2
00
6 
 
 
Poderemos, assim, enunciar uma nova Regra de Transformação "Primal-Dual" : 
 
R5 : A uma restrição do problema primal de tipo 'oposto' à regra 
" Max / restrições ≤ ; Min / restrições ≥ " corresponderá no problema 
dual, uma variável não positiva, e vice-versa. 
 
 103
 
 
R5 : 
 
Problema Primal 
 
Max 
restrição ' ≥ ' 
 
 
 
↔
 
Problema Dual 
 
Min 
variável ' ≤ 0 ' 
 
 
Problema Primal 
 
Max 
variável ' ≤ 0 ' 
 
 
 
↔
 
Problema Dual 
 
Min 
restrição ' ≤ ' 
 
 
 Aproveitemos o problema dual do exercício nº 2 anterior e determinemos o 
correspondente problema dual: 
 
 
 MAX G = 5 . U1 + 6 . U2 + 5 . U3 + 4 . U4 
 
sujeito a: 
 
 2 . U1 + 2 . U2 - 1 . U3 ≤ 4 
 1 . U1 - 1 . U2 + 3 . U3 + 2 . U4 ≤ 2 
 3 . U1 + 4 . U3 - 3 . U4 ≤ 1 
 
 
 U1 , U2 , U4 ≥ 0 ; 
 
 
U3 ≤ 0 .
 
 
 
ê 
 
Resolução : 
 
 
 
 
 
 
 MIN F = 4 . X1 + 2 .X2 + 1 . X3 
 
sujeito a: 
 
 2 . X1 + 1 . X2 + 3 . X3 ≥ 5 
 2 . X1 - 1 . X2 ≥ 6 
 - 1 . X1 + 3 . X2 + 4 . X3 ≤ 5 
 2 . X2 - 3 . X3 ≥ 4 
 
 X1 , X2 , X3 , X4 ≥ 0 . 
 
 
F Não sei se notaram, mas o dual do 'problema dual' é igual ao 'problema primal' ! 
 
 
 Para aplicarmos as 'regras de transformação' apresentadas, resolvamos agora o 
exercício seguinte: 
R
uy
 C
os
ta
, 2
00
6 
I 
 
 
 104
Ex.3 Escreva o dual do problema de Programação Linear seguinte: 
 
 MAX G = 2 . X1 + 3 . X2 + 4 . X3 
 
sujeito a: 
 
 3 . X1 - 2 . X2 ≤ 5 
 4 . X1 - 1 . X2 + 1 . X3 ≥ 6 
 2 . X1 + 3 . X2 - 1 . X3 ≤ 4 
 
 
 X1 , X2 ≥ 0 ; 
 
 
X3 ≤ 0 .
 
 
 
ê 
 
Resolução : 
 
 
 
 
 
 
 MIN F = 5 . U1 + 6 . U2 + 4 . U3 
 
sujeito a: 
 
 3 . U1 + 4 . U2 + 2 . U3 ≥ 2 
 - 2 . U1 - 1 . U2 + 3 . U3 ≥ 3 
 1 . U2 - 1 . U3 ≤ 4 
 
 
 U1 , U3 ≥ 0 ; 
 
 
U2 ≤ 0 .
 
 
 
 
 Já sabemos o que fazer se uma das restrições for uma desigualdade de 'sentido 
oposto' à regra " Max ; restrição ≤ / Min ; restrição ≥ " . Mas, o que fazer se se tiver uma 
restrição do tipo ' = ' ? Para tentarmos responder a esta questão, poderemos considerar o 
seguinte exercício: 
 
Ex.4 : 
 
 
 
 
 Escreva o dual do problema de Programação Linear seguinte: 
 
 MAX F = 2 . X1 + 3 . X2 
 
sujeito a: 
 
 - 1 . X1 + 4 . X2 ≤ 5 
 7 . X1 - 1 . X2 ≤ 8 
 2 . X1 - 2 . X2 = 3 
 3 . X1 + 5 . X2 ≤ 7 
 
 X1 , X2 , X3 , X4 ≥ 0 . 
 R
uy
 C
os
ta
, 2
00
6 
 105
 
 
 
ê 
 
Resolução : 
 
 A terceira restrição pode ser re-escrita do modo seguinte: 
 
 2 . X1 - 2 . X2 ≤ 3 ∧ 2 . X1 - 2 . X2 ≥ 3 , ou, equivalentemente: 
 
 2 . X1 - 2 . X2 ≤ 3 ∧ - 2 . X1 + 2 . X2 ≤ - 3 . 
 
 
 
 
 
 
 
 Ter-se-ia, então, o seguinte problema: 
 
 MAX F = 2 . X1 + 3 . X2 
 
sujeito a: 
 
 - 1 . X1 + 4 . X2 ≤ 5 
 7 . X1 - 1 . X2 ≤ 8 
 2 . X1 - 2 . X2 ≤ 3 
 - 2 . X1 + 2 . X2 ≤ - 3 
 3 . X1 + 5 . X2 ≤ 7 
 
 
 
 
 
ê 
 
 X1 , X2 ≥ 0 . 
 
 
 A este problema corresponde o seguinte dual: 
 
 MIN G = 5 . U1 + 8 . U2 + 3 . U3 - 3 . U4 + 7 . U5 
 
sujeito a: 
 
 - 1 . U1 + 7 . U2 + 2 . U3 - 2 . U4 + 3 . U5 ≥ 2 
 4 . U1 - 1 . U2 - 2 . U3 + 2 . U4 + 5 . U5 ≥ 3 
 
 U1 , U2 , U3 , U4 , U5 ≥ 0 . 
 
 
 Os coeficientes das variáveis não negativas U3 e U4 são simétricos, 
pelo que poderemos fazer a substituição V = U3 - U4 , com V ∈ ℜ: 
 
MIN G = 5 . U1 + 8 . U2 + 3 . V + 7 . U5 
 
sujeito a: 
 
 - 1 . U1 + 7 . U2 + 2 . V + 3 . U5 ≥ 2 
 4 . U1 - 1 . U2 - 2 . V + 5 . U5 ≥ 3 
 
 
 
ê 
 
 U1 , U2 , U5 ≥ 0 ; V ∈ ℜ. 
 
 
 Se designarmos V por U3 e U5 por U4, poderemos escrever o 
problema dual do problema dado na forma seguinte: 
 
R
uy
 C
os
ta
, 2
00
6 
 
 
 
 
 106
 
 MIN G = 5 . U1 + 8 . U2 + 3 . U3 + 7 . U4 
 
sujeito a: 
 
 - 1 . U1 + 7 . U2 + 2 . U3 + 3 . U4 ≥ 2 
 4 . U1 - 1 . U2 - 2 . U3 + 5 . U4 ≥ 3 
 
 
 U1 , U2 , U4 ≥ 0 ; 
 
U3 ∈ ℜ.
 
 
 
 
 
Poderemos, assim, enunciar uma nova Regra de Transformação "Primal-Dual" : 
 
R6 : A uma restrição do problema primal de tipo 'igualdade' corresponderá 
no problema dual, uma variável livre, e vice-versa. 
 
 
 
R6 : 
 
Problema Primal 
 
restrição ' = ' 
 
 
 
↔
 
Problema Dual 
 
variável ' ∈ ℜ ' 
 
 
 Exercitemos a utilização das 'regras de transformação' apresentadas, com o exercício 
seguinte: 
 
Ex.5 Escreva o dual do problema de Programação Linear seguinte: 
 
 MIN F = 2 . X1 + 3 . X2 + 4 . X3 + 2 . X4 
 
sujeito a: 
 2 . X1 - 3 . X2 -5 . X3 ≤ 20 
 4 . X1 - 2 . X3 + 1 . X4 ≥ 15 
 3 . X2 + 1 . X3 - 1 . X4 = 7 
 
 
 X1 , X4 ≥ 0 ; 
 
 
X2 ≤ 0;
 
X3 ∈ ℜ.
 
 
 
ê 
 
Resolução : 
 
 
 
 MAX G = 20 . U1 + 15 . U2 + 7 . U3 
 
sujeito a: 
 2 . U1 + 4 . U2 ≤ 2 
 - 3 . U1 + 3 . U3 ≥ 3 
 - 5 . U1 - 2 . U2 + 1 . U3 = 4 
 1 . U2 - 1 . U3 ≤ 2 
 
 
U1 ≤ 0 , 
 
 U2 ≥ 0 ; 
 
 
U3 ∈ ℜ.
 
 
R
uy
 C
os
ta
, 2
00
6 
 
 Sintetizemos, agora as Relações "Primal - Dual" no quadro seguinte: 
 
 107
 
Relações ' Primal ↔ Dual ' 
 
 
Problema de 
Maximização 
 
 
Problema de 
Minimização 
 
i-ésima restrição 
i = 1, 2, ..., m. 
≤
=
≥
≥ 0 
∈ ℜ 
≤ 0 
 
i-ésima variável 
i = 1, 2, ..., m. 
 
k-ésima variável 
k = 1, 2, ..., m. 
≥ 0
∈ ℜ
≤ 0
≥ 
= 
≤ 
 
k-ésima restrição 
k = 1, 2, ..., m. 
matriz dos coeficientes das 
restrições 
A ( m x n ) 
 matriz dos coeficientes das 
restrições 
AT ( n x m ) 
coeficientes da função 
objectivo ck , C ( 1 x n ) 
k = 1, 2, ..., n. 
 termos independentes das 
restrições ck , CT ( 1 x n ) 
k = 1, 2, ..., n. 
termos independentes das 
restrições bi , b ( m x 1 ) 
i = 1, 2, ..., m. 
 coeficientes da função 
objectivo bi , bT ( 1 x m ) 
i = 1, 2, ..., n. 
 
Nota: Quadro adaptado de 'Programação Linear' ( vol. II ), Guerreiro et al, Mc Graw Hill 
 
 E aproveitemos as 'regras de transformação' apresentadas, para resolver o exercício 
seguinte: 
 
Ex.6 Escreva o dual do problema tipo de Programação Linear apresentado na 
sua 'forma standard': 
 
 
 n 
 Maximizar F = Σ ck . Xk 
 k = 1 
sujeito a: 
 n 
 Σ aik . Xk = bi i = 1, 2, ... , m 
 k = 1 
 
 Xk ≥ 0 k = 1, 2, ... , n 
 
 
 
ê 
 
Resolução : 
 
 m 
 Minimizar G = Σ bi . Ui 
 i = 1 
sujeito a: 
 m 
 Σ aik . Ui ≥ ck k = 1, 2, ... , n 
 i = 1 
 
 Ui ∈ ℜ i = 1, 2, ... , m 
 R
uy
 C
os
ta
, 2
00
6 
 
 
 108
 
 
 • 2 - Propriedades Fundamentais da Dualidade 
 
P1 : O dual do problema dual de um dado problema de Programação Linear é o 
próprio problema de Programação Linear. 
 
P2: Considerando o problema primal, um problema de Programação Linear 
cujo objectivo é maximizar a função objectivo F, pode garantir-se que o o 
valor da função objectivo F ( F = C .X ) não excede o valor da função 
objectivo G ( g = bT . U ) qualquer solução admissível do problema dual, ou 
seja, n m 
 F = Σ ck . Xk ≤ G = Σ bi . Ui , para ( Xk ), ( Ui ) soluções 
 k = 1 i = 1 
 admissíveis do problema primal e dual, respectivamente. 
 
 
P3 : Se X* = [ X1*, X2*, ... , Xn* ]T e U* = [ U1*, U2*, ... , UM* ]T são soluções 
admissíveis para os problemas primal e dual, respectivamente, tais que 
. n m 
 F* = Σ ck . Xk* = G* = Σ bi . Ui* , 
 k = 1i = 1 
então X* e U* são as soluções óptimas do problema primal e do problema 
dual, respectivamente. 
 
P4 : Para qualquer par de problemas primal-dual, a existência de solução 
óptima finita para um deles garante a existência de solução óptima finita para 
o outro, verificando-se F* = G*. 
 
 Esquematicamente, pode indicar-se: 
 
 ↓ Min G 
 F* = G* [em geral, F ≤ G ( ver P2 ), mas, 
 Max F ↑ no "óptimo finito", F* = G* ( P4 ).] 
 
 
 Recordemo-nos que 
 
 F* = C . X* = CB . XB* = CB . B-1 . b e que G* = bT . U* = U*T . b . 
 ↑ ↑ ↑ 
 ( relativamente à base óptima do problema primal ) 
 
 
 Assim, se F* = G * ( P4 ), U*T . b = CB . B-1 . b, ou seja, 
 
 
U*T = CB . B-1 
 ↑ ↑ 
( relativamente à base óptima do problema primal ) 
 
 
 
 
.
 
 
 Assim, se um problema de Programação Linear admitir solução óptima finita, a 
partir da sua base óptima será possível determinar a solução óptima do correspondente 
problema dual. 
 
 
 De notar que o valor óptimo das variáveis duais intervém no cálculo dos coeficientes r 
(a partir dos quais se verifica a optimalidade das soluções de um problema de Programação 
R
uy
 C
os
ta
, 2
00
6 
 109
Linear). Com efeito, relativamente à solução óptima de um problema de Programação Linear 
pode escrever-se 
 
 r* = - CD + ( CB . B-1 ) . D ≥ 0, o que é equivalente a r* = - CD + ( U*T ) . D ≥ 0. 
 
 Particularmente interessante se torna a determinação da solução óptima do problema 
dual quando é possível escrever-se o problema primal na forma: 
 
 
 B D1 I b è I B-1. D1 B-1 B-1. b 
 - CB - CD1 0 0 0 - CD1 + CB . B-1. D1 CB . B-1 CB . B-1. b
 
 ↑ 
 U*T 
 
 Estando agora clara a relação entre o par de problemas primal-dual, poderemos 
retomar as considerações feitas no final da resolução do exercício nº1. 
 
 Então, referimos que o problema primal apresentado tinha m = 4 (número de 
equações) e n = 2 + 4 (número de incógnitas), pelo que a sua resolução pelo Algoritmo 
Simplex Revisto implicaria a manipulação (incluindo inversão) de matrizes B ( 4 x 4 ), enquanto 
que o problema dual correspondente tinha m = 2 (número de equações) e n = 4 + 2 
(número de incógnitas), pelo que a sua resolução pelo Algoritmo Simplex Revisto implicaria a 
manipulação de matrizes B ( 2 x 2 ) ! Concluímos, então, que, a priori, seria mais fácil 
resolver o problema dual, já que este corresponderia a um menor esforço de cálculo... 
 
 Poderemos generalizar o raciocínio apresentado e referir que, dado um problema de 
Programação Linear que se pretende resolver, deve verificar-se se a resolução do 
correspondente problema dual não será mais fácil. Em caso afirmativo, deverá determinar-se 
a solução óptima do problema dual e, a partir da correspondente base óptima, determinar a 
solução óptima do problema (primal) dado. 
 
 De recordar que quanto maior for o número de restrições de um problema de 
Programação Linear, maior será a ordem das correspondentes matrizes B e, 
consequentemente, maior será o volume de cálculo envolvido. 
 
 Assim, dado um problema de Programação Linear, se o número de restrições for muito 
superior ao número de incógnitas (não incluindo as variáveis de folga) deve resolver- -se o 
correspondente problema dual, já que as matrizes BPrimal ( m x m ) são de ordem muito 
superior que as matrizes BDual. 
 
 
 Para terminarmos a indicação das propriedades fundamentais da Dualidade, refiramos 
ainda mais duas propriedades: 
 
P5: Um problema de Programação Linear admite solução óptima finita se e só 
se existirem soluções admissíveis para esse problema e para o seu dual. 
 
P6: Se um problema de Programação Linear não admitir solução óptima finita, 
então o correspondente dual não tem soluções admissíveis. 
 
 Primal (Max F) → 
Dual (Min G)↓ 
 
 
Explo. 
Problema Possível 
 S ≠ ∅ 
 
 
Explo. 
Problema Impossível 
S = ∅ 
Problema Possível 
S ≠ ∅ 
1 F* = G* ambos problemas 
têm solução óptima finita 
3 G* → - ∝ o problema dual 
não tem solução óptima finita 
Problema Impossível 
S = ∅ 
2 F*→+ ∝ o problema primal 
não tem solução óptima finita
4 Nenhum dos problemas tem soluções admissíveis 
R
uy
 C
os
ta
, 2
00
6 
 Exemplos das situações referidas no Quadro anterior (resolva os problemas graficamente): 
 
 110
 
 
Explo. 
 
 Problema Primal 
 
 
Problema Dual 
 
1 
 
 Max F = 5 . X 
 sujeito a X + Y = 1 
 X, Y ≥ 0 
 
 
X* = 1 , Y * = 0 ; F* = 5 
 
 Min G = U 
 sujeito a U ≥ 5 
 U ≥ 0 
 U ∈ ℜ 
 
X* = 1 , Y * = 0 ; F* = 5 
 
 
2 
 
 Max F = X + Y 
 sujeito a X - Y = 2 
 X, Y ≥ 0 
 
F* → + ∝ 
 
 Min G = 2 . U 
 sujeito a U ≥ 1 
 - U ≥ 1 
 
Problema impossível ( S = ∅ ) 
 
 
3 
 
 Max F = - X 
 sujeito a - X = 4 
 X ≥ 0 
 
Problema impossível ( S = ∅ ) 
 
 Min G = 4 . U 
 sujeito a - U ≥ - 1 
 U ∈ ℜ 
 
G* → - ∝ 
 
 
4 
 
 Max F = X + Y 
 sujeito a -X +Y = 4 
 X -Y = 4 
 X, Y ≥ 0 
 
Problema impossível ( S = ∅ ) 
 
 
 Min G = 4 . U + 4 . V 
 sujeito a - U + V ≥ 1 
 U - V ≥ 1 
 
 
Problema impossível ( S = ∅ ) 
 
 
Nota: Exemplos retirados de 'Programação Linear' ( vol. II ), Guerreiro et al, Mc Graw Hill 
 
 
 
 
 
 • 3 - Teorema da Complementaridade 
 
 
 Considerando o par de problemas 'primal-dual' 
 
Problema 'primal': 
 
Max F = C . X 
 
sujeito a A . X ≤ b 
 X ≥ 0 
Problema 'dual': 
 
Min G = bT . U 
 
sujeito a AT . U ≥ CT 
 U ≥ 0 , 
R
uy
 C
os
ta
, 2
00
6 
 
poderemos enunciar o Terorema da Complementaridade: 
 
 
 
 
 111
 
 É condição necessária e suficiente para que X e U, soluções admissíveis dos problemas 
primal e dual, respectivamente, sejam soluções óptimas, que verifiquem as seguintes 
condições: 
 
 Xk* > 0 ⇒ U*T . ak = ck [ 1 ] 
 
 U*T . ak > ck ⇒ Xk* = 0 [ 2 ] 
 
 Ui* > 0 ⇒ ai . X* = bi [ 3 ] 
 
 ai . X* < bi ⇒ Ui* = 0 [ 4 ] 
 
para i = 1, 2, ..., m e k = 1, 2, ..., n e representando ak e ai , respectivamente, a 
k-ésima coluna e a i-ésima linha de A. 
 
 
 De acordo com o Teorema da Complementaridade, podemos concluir que, 
relativamente à solução óptima: 
 
 • se uma 'variável primal' é positiva, então a correspondente 'restrição dual' é activa 
[ 1 ] e que se uma 'restrição dual' é não activa, então a correspondente 'variável primal' é nula 
[ 2 ]. 
 
 • se uma 'variável dual' é positiva, então a correspondente 'restrição primal' é activa 
[ 3 ] e que se uma 'restrição primal' é não activa, então a correspondente 'variável dual' é nula 
[ 4 ]. 
 
 
 
 Poderemos sintetizar o Teorema da Complementaridade, nas afirmações seguintes: 
 
 
 
 Relativamente às soluções óptimas do par de problemas 'primal-dual' de Programação 
Linear, 
 
 • é nulo o produto da k-ésima 'variável primal' pela variável de folga correspondente à k-
ésima 'restrição dual': 
 
 m 
 xk* . [ ( Σ aik . ui* ) - ck] = 0 ⇔ xk* . um+k* = 0 
 i = 1 
 k = 1, 2, ..., n 
 
 
 • é nulo o produto da i-ésima 'variável dual' pela variável de folga correspondente à 
i-ésima 'restrição primal': 
 
 n 
 ui* . [ ( Σ aik . xk* ) - bi ] = 0 ⇔ ui* . xn+i* = 0 
 k = 1 
 i = 1, 2, ..., m 
 
 
 
 
 Consideremos o seguinte par de problemas 'primal-dual' de Programação Linear: 
R
uy
 C
os
ta
, 2
00
6 
 
 112
 Max F = 2 X1 + 3 X2 Min G = 5 U1 + 3 U2 + 4 U3 
 
sujeito a sujeito a 
 3 X1 + 4 X2 ≤ 5 3 U1 + 6 U2 + 2 U3 ≥ 2 
 6 X1 - 1 X2 ≤ 3 4 U1 - 1 U2 + 4 U3 ≥ 3 
 2 X1 + 4 X2 ≤ 4 
 U1 , U2 , U3 ≥ 0 
 X1 , X2 ≥ 0 
 
 
 
 O Teorema da Complementaridade permite afirmar que, relativamente ao óptimo: 
 
 X1* > 0 ⇒ 3 U1* + 6 U2* + 2 U3* = 2 
 X2* > 0 ⇒ 4 U1* - 1 U2* + 4 U3* = 3 
 
 3 U1* + 6 U2* + 2 U3* > 2 ⇒ X1* = 0 
 4 U1* - 1 U2* + 4 U3* > 3 ⇒ X2* = 0 
 
 
 U1* > 0 ⇒ 3 X1* + 4 X2* = 5 
 U2* > 0 ⇒ 6 X1* - 1 X2* = 3 
 U3* > 0 ⇒ 2 X1* + 4 X2* = 4 
 
 3 X1* + 4 X2* < 5 ⇒ U1* = 0 
 6 X1* - 1 X2* < 3 ⇒ U2* = 0 
 2 X1* + 4 X2* < 4 ⇒ U3* = 0 
 
 
 
 
 Resolva, recorrendo ao Método gráfico o problema 'primal' dado. 
 
 [ Nós aguardamos, pacatamente, que resolva mesmo o problema ! ] 
 
 Como pode observar, a 1ª restrição é dominada pelas duas outras. A 
solução óptima do problema ( X1* = 8/13 ; X2* = 9/13 , com F* = 43/13 ) 
corresponde à intersecção das rectas respeitantes à 2ª e 3ª restrições. 
 
 Assim, relativamente ao óptimo, podemos concluir que a 2ª e a 3ª 
restrições são activas (isto é, têm folga nulas). Pelo Teorema da 
Complementaridade, podemos, imediatamente, concluir que se a 1ª restrição 
é a única restrição não activa, então a correspondente variável dual, U1* é a 
única variável dual 'original' nula. 
 
 Mas, se o problema dual tem duas restrições (e três variáveis 'originais'), 
então as correspondentes matrizes B são do tipo ( 2 x 2 ). Ora se U1* é 
nula, então U2* e U3* serão obrigatoriamente não nulas, isto é pertencerão à 
base óptima do problema dual. 
 
 Como, neste caso, é mais fácil resolver analiticamente o problema dual do 
que o problema primal e já sabemos quais as variáveis que integram a 
respectiva base óptima ... 
 R
uy
 C
os
ta
, 2
00
6 
 113
F ... resolva o problema 'dual' utilizando a formulação matricial do Simplex. 
¸ [ Nós aguardamos, pacatamente, que resolva mesmo o problema ! ] 
 
 Deve ter obtido U2* = 1/13 ; U3* = 10/13 , com G* = 43/13 [ Claro que se tinha 
que obter F* = G * ! ]. 
 
 A partir do problema 'dual' pode obter a solução óptima do problema 
'primal' (calculando CB . B-1 relativamente à base óptima do problema 'dual') 
- deve obter X1* = 8/13 ; X2* = 9/13 , verificando os resultados obtidos 
anteriormente. 
 
 
 
 Relativamente à solução óptima, os valores assumidos pelas variáveis duais 
costumam ser designados por preços-sombra associados às restrições do problema primal. 
A uma 'restrição primal' não activa corresponde um preço-sombra nulo. Um preço-sombra não 
nulo corresponde a uma restrição activa. A designação de preço-sombra, prende-se com o 
facto de, em aplicações de carácter económico, o preço-sombra correspondente a uma dada 
'restrição primal' representar a quantia máxima que estaríamos dispostos a pagar para 
incrementar em uma unidade a disponibilidade do correspondente recurso (isto é, aumentar em 
uma unidade o termo independente da restrição). 
 
 Se se alterar os termos independentes do problema primal (que, em geral, exprimem 
disponibilidades de recursos) - e se se mantiver a mesma base - é possível calcular facilmente 
a variação produzida na função objectivo: 
 
 Com efeito, sabemos que F = CB . B-1 . b = UT . b , pelo que se se alterar b para 
b' = b + ∆b, ter-se-á: 
 
 F' = UT . b' = UT . ( b + ∆b ) = UT . b + UT . ∆b = F + UT . ∆b , 
 
ou seja, ∆F = F' - F = UT . ∆b, isto é, ∆F = UT . ∆b , ou seja os valores óptimos das variáveis 
duais constituem coeficientes de sensibilidade da função objectivo, em relação aos termos 
independentes das restrições. 
 
 Apliquemos algumas das noções apresentadas, a partir da análise do seguinte par de 
problemas 'primal-dual' de Programação Linear: 
 
 Min F = - X1 + 2 X2 Max G = 5 U1 + 3 U2 + 4 U3 
 
sujeito a sujeito a 
 1 X1 + 1 X2 ≤ 10 1 U1 + 1 U2 + 1 U3 ≤ - 1 
 1 X1 + 1 X2 ≥ 5 1 U1 + 1 U2 - 1 U3 ≤ 2 
 1 X1 - 1 X2 ≤ 0 
 U1 ≤ 0 ; U2 ≥ 0 ; U3 ≤ 0 
 X1 , X2 ≥ 0 
 
 
 
X2 
 
Ð 10 + 
Max P = 1 X1 - 2 X2 
sujeito a 
 
 1 X1 + 1 X2 + 1 X3 = 10 
 1 X1 + 1 X2 - 1 X4 = 5 
 1 X1 - 1 X2 + 1 X5 = 0 
 
 X1 , X2 , X3 , X4 , X5 ≥ 0 
 
Î
5
 
5/2
 F 
  
 5/2 5 10 1 X
R
uy
 C
os
ta
, 2
00
6 
 114
 
 Como se pode observar, pela resolução gráfica, a solução óptima do problema 'primal' 
é ( X1* = 5/2 ; X2* = 5/2 ), a que corresponde F* = 5/2. De notar que o vértice do espaço de 
soluções admissíveis correspondente à solução óptima é definido pela intersecção da 2ª e 3ª 
restrições, ou seja, a base óptima é ( X1 ; X2 ; X3 ), já que X3*é a variável de folga 
correspondente à primeira restrição. Por outro lado, se a 2ª e 3ª 'restrições primais' são 
activas, então, as correspondentes variáveis duais estarão na base correspondente à solução 
óptima do problema dual, isto é, essa base é ( U2 ; U3 ). 
 
F Utilizando a formulação matricial do Simplex, verifique que ( X1 ; X2 ; X3 ) é a base óptima do problema primal. 
 
 ... Deve ter obtido r = [ + 1/2 ; + 3/2 ], ( X1* = 5/2 ; X2* = 5/2 ) e P*= - 5/2 ⇔ F * = 5/2 
 
F A partir da base óptima do problema primal, determine a solução óptima do problema dual. 
 
 ... Deve ter obtido UT* = [ 0 ; + 1/2 ; - 3/2 ] , isto é, U1* = 0 ; U2* = + 1/2 ; U3* = - 3/2. 
 ... De notar que G* = 5/2 = F* ü 
 
F Utilizando a formulação matricial do Simplex, aplicada ao problema dual (na forma standard), verifique que ( U2 ; U'3 ) é a base óptima desse problema. 
 
 ... Não se esqueça de fazer U3 = - U'3 . Deverá obter U2* = + 1/2 ; U'3* = + 3/2. 
 
F Utilizando a formulação matricial do Simplex, aplicada à base óptima do problema dual, verifique a solução óptima do problema primal. 
 
 ... Deverá obter ( X1* = 5/2 ; X2* = 5/2 ). 
 
 Recordemo-nos que X1* = 5/2 ; X2* = 5/2, pelo que facilmente determinamos os 
valores correspondentes das variáveis de folga X3*, X4* e X5* : X3* = 10 - ( X1* + X2* ) = 5 e 
X4* = X5* = = 0 (de recordar que a 2ª e 3ª 'restrições primais' são activas, pelo que as 
correspondentes variáveis de folga são nulas). Por outro lado, U1* = 0 ; U2* = + 1/2 ; U3* = 
- 3/2, pelo que os valores das correspondentes variáveis de folga do problema dual serão U4* 
= - 1 - ( U1*+ U2* + U3* ) = 0 e U5* = 2 - ( 1 U1* + 1 U2* - 1 U3 ) = 0 (ou seja as duas 
'restrições duais' são activas). 
 
 Verifiquemos o cumprimento das condições estabelecidas pelo Teorema da 
Complementaridade: 
 
 X3* . U1* = 0 ⇔ 5 . 0 = 0 ü 
 X4* . U2* = 0 ⇔ 0 . 1/2 = 0 ü 
 X5* . U3* = 0 ⇔ 0 . (-3/2) = 0 ü 
 
 X1* . U4* = 0 ⇔ 5/2 . 0 = 0 ü 
 X2* . U5* = 0 ⇔ 5/2 . 0 = 0 ü 
 
 
 
 Aproveitemos para retomar a noção de preço-sombra. Comecemos com U2* = + 1/2. 
Tal indica-nos que, se se incrementar uma unidade ao termo independente da segunda 
'restriçãoprimal', a função objectivo F sofrerá um incremento de + 1/2 ( o que, por acaso, não 
nos interessaria muito, já que o objectivo do problema primal é Minimizar F ! ). De notar que o 
que se referiu só é válido na hipótese de se manter óptima a mesma base ! 
R
uy
 C
os
ta
, 2
00
6 
 
 115
F Considere o problema primal 'alterado' (na forma standard): 
Max P = 1 X1 - 2 X2 
sujeito a 
 
 1 X1 + 1 X2 + 1 X3 = 10 
 1 X1 + 1 X2 - 1 X4 = 5 + 1 
 1 X1 - 1 X2 + 1 X5 = 0 
 
 X1 , X2 , X3 , X4 , X5 ≥ 0 
 
Utilizando a formulação matricial do Simplex, verifique que ( X1 ; X2 ; X3 ) 
se mantém a base óptima do problema primal. 
 
 ... Deve ter obtido r = [ + 1/2 ; + 3/2 ], ( X1* = 3 ; X2* = 3 ) e P*= - 3 ⇔ F * = 3 = 5/2 + 1/2 
 ↑ ↑ 
 F*orig. U2* 
 
 
 Se considerermos, agora, U3* = - 3/2, tal indicar-nos-á que, a um incremento de uma 
unidade no termo independente da terceira 'restrição primal', a função objectivo F sofrerá um 
'incremento' de - 3/2 ( o que, por acaso, nos interessaria, já que o objectivo do problema primal 
é Minimizar F ! ). ( Continuamos a assumir que se mantem óptima a mesma base ! ) 
 
F Considere o problema primal 'alterado' (na forma standard): 
Max P = 1 X1 - 2 X2 
sujeito a 
 
 1 X1 + 1 X2 + 1 X3 = 10 
 1 X1 + 1 X2 - 1 X4 = 5 
 1 X1 - 1 X2 + 1 X5 = 0 + 1 
 
 X1 , X2 , X3 , X4 , X5 ≥ 0 
 
Utilizando a formulação matricial do Simplex, verifique que ( X1 ; X2 ; X3 ) 
se mantém a base óptima do problema primal. 
 
 ... Deve ter obtido r = [ + 1/2 ; + 3/2 ], ( X1* = 3 ; X2* = 2 ) e P*= - 1 ⇔ F * = 1 = 5/2 + (- 3/2) 
 ↑ ↑ 
 F*orig. U3* 
 
 
 
 
 
 Assim, a Dualidade tem, pelo menos, duas importantes aplicações: por um lado, 
relativamente a um per de problemas 'primal-dual' de Programação Linear, permite-nos 
resolver o problema 'mais simples' e obter a solução de ambos; por outro lado, os valores 
óptimos das variáveis duais de um problema de Programação Linear podem ser encarados 
como coeficientes de sensibilidade da função objectivo, face a eventuais variações dos termos 
independentes ('disponibilidades de recursos'), o que é muito importante, numa interpretação 
de 'caractér económico'. R
uy
 C
os
ta
, 2
00
6 
 116