Dualidade - Pesquisa Operacional

Prévia do material em texto

59
4- Dualidade em Programação Linear 
 
4.1- Introdução 
 
 Considere o problema clássico da dieta: (problema primal): Quer-se 
consumir quantidades de determinados alimentos de tal forma a satisfazer as 
necessidades mínimas de nutrientes exigidas a um custo mínimo dispendido, 
problema este ilustrado pelo quadro seguinte. 
 
 alimentos necessidades mín. de 
 nutrientes 
 a1 a2 a3 a4 a5 
 proteínas (g) 3 4 5 3 6 42 (4.1) 
sais minerais (g) 2 3 4 3 3 24 
 custo (R$) 25 35 50 33 36 
 
 Considerando-se: 
 aij : percentual do componente i presente no alimento j; 
 xj : quantidade do componente j presente na dieta a ser feita; 
 cj : preço por grama de cada ingrediente; 
 bi : quantidade mínima de cada ingrediente a ser consumida na dieta. 
 aj: coluna j da matriz do sistema; 
 
 Então, o Modelo Primal pode ser sistematizado da seguinte forma: 
 minimizar 25 x1 + 35 x2 + 50 x3 + 33 x4 + 36 x5 
 
 3 x1 + 4 x2 + 5 x3 + 3 x4 + 6 x5 ≥ 42 
 sujeito a : 2 x1 + 3 x2 + 4 x3 + 3 x4 + 3 x5 ≥ 24 
 x1 ; x2 ; x3 ; x4 ; x5 ≥ 0 
 
4.2- Formulação do modelo dual 
 
 Suponha que um vendedor de pílulas e sais minerais propõe substituir a 
dieta de alimentos expressa de acordo com o quadro (4.1), por uma dieta de 
pílulas, com as seguintes condições: 
1- a pílula de uma unidade (g) de proteína custará w1 ; 
2- “ “ “ “ “ “ “ sais minerais “ w2 ; 
3- os preços w1 e w2 serão fixados arbitrariamente; 
4- o vendedor garante que as pílulas terão preços iguais ou mais baratos que 
qualquer alimento; 
5- o vendedor pretende , é claro, maximizar sua renda de modo a satisfazer a 
necessidade da dieta; 
 
 60
 Para o problema posto, tem-se o modelo visto a seguir: 
 maximizar 42 w1 + 24 w2 
 
 3 w1 + 2 w2 ≤ 25 
 4 w1 + 3 w2 ≤ 35 
 sujeito a: 5 w1 + 4 w2 ≤ 50 (4.2) 
 3 w1 + 3 w2 ≤ 33 
 6 w1 + 3 w2 ≤ 36 
 w1 ; w2 ≥ 0 
 
 A cada modelo de Programação Linear, contendo coeficientes aij, bi e cj, 
corresponde um outro modelo, formado por esses mesmos coeficientes, porém 
dispostos de maneira diferente. Ao modelo original, visto em 4.1, dá-se o nome de 
“ Modelo Primal”, enquanto qua ao outro modelo visto em (4.2),denomina-se de 
“Modelo Dual”. Sobre estes dois modelos estão relacionadas propriedades que 
estabelecem que: 
a) se a função objetivo do primal é de minimização, então a função objetivo do 
dual é de maximização; 
b) os termos independentes das restrições do dual são coeficientes da função 
objetivo do primal; 
c) os coeficientes da função objetivo do dual são os termos independentes das 
restrições do primal; 
e) o número de variáveis do dual é igual ao número de restrições do primal; 
f) o número de restrições do dual é igual ao número de variáveis do primal; 
g) a matriz dos coeficientes do dual é a transposta da matriz dos coeficientes do 
primal; 
 
Definição 4.1: 
 Dado um Problema de Programação Linear 
(PP): min ctx ; c,x ∈ ℜn 
 s.a. Ax ≥ b; A∈ℜmxn, b∈ℜm 
 x ≥0 
O dual de (PP) é expresso por: 
(PD): max btw ; b,w ∈ ℜm 
 s.a. Atx ≤ b; At∈ℜnxm, c∈ℜn 
 w ≥0 
4.3- Propriedades 
 
 
 
Propriedade 4.3.1: 
 “O dual do dual é o primal”. 
 
Demonstração: 
 61
 Seja o problema primal: 
(PP): min ctx ; c,x ∈ ℜn 
 s.a. Ax ≥ b; A∈ℜmxn, b∈ℜm 
 x ≥0 
 
Pela definição 4.1, o seu dual é: 
(PD): max btw ; b,w ∈ ℜm 
 s.a. Atx ≤ b; At∈ℜnxm, c∈ℜn 
 w ≥0 
Vamos determinar o dual de PD. Para isso, vamos transformá-lo num 
problema de minimização e vamos também mudar o tipo de desigualdade da 
restrição para poder utilizar a definição 4.1. Então, temos: 
(PD): -min -btw ; b,w ∈ ℜm 
 s.a. -Atw ≥- c; At∈ℜnxm, c∈ℜn 
 w ≥0 
Logo, o dual de PD é: 
(PD’): ): -max -ctu ; c,u ∈ ℜm 
 s.a. -Au ≤ -c; A∈ℜmxn, b∈ℜm 
 w ≥0 
 
que é equivalente a: 
(PD’’): min ctu ; c,u ∈ ℜn 
 s.a. Au ≥ b; A∈ℜmxn, b∈ℜm 
 u ≥0 
que é equivalente ao problema primal (PP). 
 
Propriedade 4.3.2: 
 “Se a restrição k do primal é de igualdade, então a variável wk do dual é 
irrestrita. 
 
Demonstração: 
 Seja o problema primal: 
(PP): min ctx ; c,x ∈ ℜn 
 s.a. Ax = b; A∈ℜmxn, b∈ℜm 
 x ≥0 
 
que pode ser transformado na forma: 
 
min ctx ; c,x ∈ ℜn 
 s.a. Ax ≥ b; A∈ℜmxn, b∈ℜm 
 Ax ≤ b 
 x ≥0 
ou 
min ctx ; c,x ∈ ℜn 
 62
 s.a. Ax ≥ b; A∈ℜmxn, b∈ℜm 
 -Ax ≥ -b 
 x ≥0 
Sejam, então, 
A = A , b = b e w = w1 ... 
 -A -b w2 
 
O dual, por definição, será: 
(PD): max b t w ; b , w ∈ ℜ2m 
 s.a. A tx ≥ c; A t∈ℜnx2m, c∈ℜn 
w ≥0, 
ou seja 
(PD): max (b b ) w1 
 w2 
‘ 
 s.a. A w1 
 -A w2 ≥ c 
 
 w1, w2 ≥ 0 
 
ou, ainda, 
PD): max btw1 - btw2 
 s.a. Atw1 – At w2 ≥ 0; At∈ℜnxm, c∈ℜn 
 w1, w2 ≥ 0 
ou 
(PD): max bt (w1 - w2 ) 
 s.a. At (w1 – w2 ) ≥ 0 
 w1, w2 ≥ 0 
Substituindo w1 – w2 por u, teremos que u = w1 – w2, u é livre de sinal, pois w1 ≥ 0 
e w2 ≥ 0 . 
 
Portanto, a forma final do problema dual de (PP), será: 
 
(PD): max btu ; b,u ∈ ℜm 
 s.a. Atu ≤ b; At∈ℜnxm, c∈ℜn 
 u é irrestrito. 
 
 Nas propriedades que seguem, as demonstrações são análogas àquela 
vista para a propriedade 4.3.2 e não serão vistas aqui. 
Propriedade 4.3.3: 
 “Se a restrição k do primal é do tipo maior ou igual, então a variável wk do 
dual é não positiva”. 
 
Propriedade 4.3.4: 
 63
 “Se a variável xp do primal é sem restrição de sinal, então a restrição p do 
dual é de igualdade”. 
 
Propriedade 4.3.5: 
 “Se a variável xp do primal é não-positiva, então a restrição p do dual é do 
tipo maior ou igual”. 
 
 
 O quadro visto a seguir estabelece a relação direta entre as propriedades 
relativas aos problemas Primal e Dual: 
 
Primal (Min.) →→→→ Dual (Max.) 
restrição k é ≤ wk ≤ 0 
restrição k é = wk é qualquer 
restrição k é ≥ wk ≥ 0 
xk ≥ restrição k é ≤ 
xk é qualquer restrição k é = 
xk ≤ restrição k é ≥ 
Dual (min.) ← Primal (max.) 
 
4.4- Teoremas Básicos da Dualidade 
 
 Os teoremas que serão vistos a seguir estarão baseados nos seguintes 
pares de problemas: 
 Problema Primal (PP) Problema dual (PD) 
 minimizar z = cTx maximizar d = wTb 
 sujeito a 
Ax b
x
=
≥
�
�
� 0
 ⇔ sujeito a ATw ≤ c; 
onde A ∈∈∈∈ ℜℜℜℜmxn; x, c ∈∈∈∈ ℜℜℜℜn; b, w ∈∈∈∈ ℜℜℜℜm, AT ∈∈∈∈ ℜℜℜℜnxm 
e obviamente poderão ser estendidos para qualquer outra definição de pares 
primal e dual diferentes destes. 
 
Teorema 4.4.1: 
 Nas hipóteses dos problemas primal e dual serem factíveis é válido que a 
função objetivodual é um limitante inferior para a função objetivo primal, ou seja, 
wTb ≤ cTx para x primal factível e w dual factível. 
 Prova: 
 Para uma solução primal factível x tem-se que o sistema de soluções está 
satisfeito, isto é, Ax = b , enquanto que AT w ≤ c , para w dual factível. Assim: 
 wTb = wT Ax ≤ cT x . Portanto wTb ≤ cTx e o resultado segue. 
 
 64
Assim, a função dual fornece um limitante inferior à função primal, que 
deseja-se minimizar. Isto sugere que deve-se escolher w ∈ℜm tal que forneça o 
maior limitante inferior para a função objetivo primal, por isso, é interessante 
tentar-se maximizar a função dual. 
 
Teorema 4.4.2: 
 Se B é a base relacionada à solução ótima de (PP) então o vetor 
multiplicador wT = cB
TB-1 é a solução ótima de (PD). 
 Prova: 
 Considerando-se a partição de A = [B,N] , foi visto que pode-se escrever: 
 
 
Bx Nx b
c x c x z
B N
B
T
B N
T
N
+ =
+ =
�
�
�
 � 
B Bx B Nx B b
c x c x z
B N
B
T
B N
T
N
− − −+ =
+ =
�
�
�
1 1 1
 � 
 
c B Bx c B Nx c B b I
c x c x z II
B
T
B B
T
N B
T
B
T
B N
T
N
− − −+ =
+ =
�
�
�
��
1 1 1 ( )
( )
 
 Subtraindo-se (I) de (II) : ( c B
T - wTB) xB + (c N
T - wTN) xN = z - w
Tb. 
 Se x é uma solução básica factível então: 
 xB = B
-1b; xN = 0; c B
T - wTB = 0 e existe alguma componente de custo relativo 
não básico (c N
T - wTN)i < 0 . Assim (xN)i é uma variável não básica candidata a 
entrar na base. 
 Se x é uma solução ótima para o problema (PP), então: 
xB = B
-1b; xN = 0; c B
T - wTB = 0 e (c N
T - wTN) ≥ 0 (hipótese). 
 Assim , de c B
T - wTB = 0 e (c N
T - wTN) ≥ 0 pode-se concluir que: 
 wT[B,N] ≤ [c B
T , c N
T ] � wTA ≤ cT � AT w ≤ c. 
 Portanto, wT = cB
TB-1 é uma solução básica factível Dual. Como B é a 
base ótima de (PP), não é mais possível haver troca de base, então wT = cB
TB-1 é 
a solução ótima de (PD), e a prova está completa. 
 
Teorema 4.4.3: ( Teorema fundamental da dualidade em P.L.) 
 Considere os pares de problemas (PP) e (PD). 
 Se um dos problemas tiver solução ótima, então o outro também terá 
solução ótima. Considerando-se x* ∈∈∈∈ ℜℜℜℜn, a solução ótima do problema primal (PP) 
e w* ∈∈∈∈ ℜℜℜℜm, a solução ótima do problema dual (PD), então a seguinte igualdade é 
válida: cTx* = (w*)Tb. 
 Prova: 
 A primeira parte do teorema está demonstrada no teorema 5.4.2. 
 Resta demonstrar que: cTx* = (w*)Tb. Mas cTx* = c B
T xB = c B
T B-1b = (w*)Tb.
 Como cTx ≥ cTx* = (w*)Tb ≥ wTb pelo teorema 5.4.1, então pode-se 
concluir que x* é a solução ótima de (PP) e w* é a solução ótima de (PD). 
 65
 
Observação: 
Viu-se que, se x é uma solução básica factível então: 
 xB = B
-1b; xN = 0; c B
T - wTB = 0 e se existe alguma componente de custo 
relativo não básico (c N
T - wTN)i < 0 , (xN)i era candidata a entrar na base. 
 Isto quer dizer que, existe alguma componente wi infactível pois a 
restrição (c N
T - wTN)i < 0 está sendo violada. 
 O método dual-Simplex a ser visto baseia-se nesta infactibilidade para 
efetuar troca de soluções, ou seja, parte da infactibilidade das componentes wi e 
vai efetuando trocas de base até acabar com todas estas infactibilidades. Quando 
isto ocorrer é porque xB = B
-1b; xN = 0; c B
T - wTB = 0 e (c N
T - wTN) ≥ 0 e os 
dois problemas (PP) e (PD) estarão resolvidos, com x sendo uma solução ótima 
para o problema (PP) w uma solução ótima para o problema (PD). 
 
Corolário 4.4.1: 
 Se um dos problemas tiver solução ótima finita o outro também terá. 
 
Teorema 4.4.4: 
 Se um dos problemas é ilimitado o outro é infactível. 
 
 Este teorema pode ser ilustrado com o seguinte exemplo: 
 ( PP ) 
 minimizar z = -3x1 + 2x2 
 sujeito a 
− + ≥ −
− ≥ −
≥
�
�
�
�
�
x x
x x
x x
1 2
1 2
1 2
2 4
3
0,
 
 Determinando-se (PD) e resolvendo-se (PP) e (PD) geometricamente, 
ilustra-se o resultado desejado. 
 
Teorema 4.4.5: 
 Se um dos problemas é infactível o outro é ilimitado ou infactível. 
 O exemplo a seguir ilustra esse resultado: 
 (PP) 
 minimizar z = -x1 - x2 
 sujeito a: 
− − ≥
− + ≥
≥
�
�
�
�
�
x x
x x
x x
1 2
1 2
1 2
1
1
0,
 
 Determinando-se (PD) e resolvendo-se (PP) e (PD) geometricamente, tem-
se o resultado esperado. 
 
4.4.1- Quadro resumo de Corolários e Teoremas Básicos da Dualidade 
 
 66
 Dual 
Primal 
Tem solução 
factível 
Não tem solução 
factível 
Tem solução 
factível 
 Mín z = Máx d Min z = - � 
Não tem solução 
factível 
max d = � Pode ocorrer 
 
4.5- Folgas Complementares 
 
 A resolução de um Problema de Programação Pinear pode ser 
obtida resolvendo-se o sistema conjunto: 
cTx - wTb = 0; 
Ax = b, x ≥ 0 ; 
AT w ≤ c ⇔ AT w + wF = 0, wF ≥ 0. 
 
 A primeira equação cTx - wTb = 0, pode ser escrita por: 
cTx - wT Ax = 0 ⇔ (cT - wT A) x = 0. 
 Esta equação relaciona as variáveis de folga do problema dual wF com as 
variáveis primais x, onde wF = c
T - wT A. 
 Para wF dual factível e x primal factível tem-se wF ≥ 0 e x ≥ 0. 
 Logo, (cT - wT A) x = 0 ⇔ (c i
T - wT ai) xi = 0 para i = 1,...,n; 
qual é equivalente à seguinte relação de complementariedade: 
(c i
T - wT ai) > 0 � xi = 0; 
(c i
T - wT ai) = 0 � xi > 0. 
 Assim, para x e w soluções ótimas de (PP) e (PD), respectivamente, se a 
i-ésima restrição do dual for inativa ((c i
T - wT ai) > 0 ) então a correspondente 
variável primal será nula ( caso contrário cTx ≤ wTb ). Se a i-ésima variável primal 
for positiva então a correspondente restrição dual será ativa ((c i
T - wT ai) = 0). 
 Esta propriedade é conhecida na literatura como “condições das folgas 
complementares” , que são condições necessárias e suficientes que inter-
relacionam soluções factíveis e estabelecem um critério para atingir a otimalidade 
do PPL. Estas podem ser enunciadas no seguinte teorema. 
 
Teorema 4.5.1: ( Teorema das folgas complementares) 
 Considerando-se x* e w* soluções factíveis de (PP) e (PD) 
respectivamente, então, se x* e w* são soluções ótimas para (PP) e (PD) tem-se: 
• o valor ótimo da variável w*i do dual é igual ao coeficiente na linha dos custos 
relativos ótima, da variável de folga x*n+i do primal, isto é, w
*
i = r
*
n+i (i=1,...,m); 
• o valor da variável de folga w*m+j do dual é igual ao coeficiente de custo relativo 
ótimo, xj do primal, isto é, w
*
m+j = r
*
j (j=1,...,n). 
 
 67
 Este teorema tem o seu nome devido ao fato das variáveis de folga do dual 
e as variáveis de folga do primal estarem ligadas entre si. Porisso é que se diz 
que as soluções do primal e do dual são “complementares” entre si. 
 
Corolário 4.5.1: 
• (wF*)i = 0 quando x n i+
* > 0 (i = 1, 2,…, m) isto é, se na solução ótima do primal, a 
variável de folga xn+i* for básica, então a variável do dual (wF
*)i é não básica. 
• (wF*)m+j = 0 quando xj* > 0 (j = 1, 2,…,n), isto é, se na solução ótima do 
primal, a variável xj* for básica, então a variável de folga do dual (wF
* )m+i é não 
básica. 
 
 Na próxima seção será visto em detalhes o método Dual-Simplex. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
4.6- O Método Dual - Simplex 
 
 O método Dual-Simplex é aplicado na situação em que a solução inicial do 
primal é infactível, porém os elementos da função objetivo são todos não-
negativos. O método procura alcançar a factibilidade primal, transfornando as 
variáveis xj negativas em não negativas, mas preservando a factibilidade dual, ou 
seja, mantendo os coeficientes de custo relativo não negativos. 
 
4.6.1- Resumo do método 
 68
 
 Suponha que em uma iteração corrente o quadro do método apresente as 
seguintes características: 
 
a) Todos os elementos do vetor custo relativo são não-negativos, ou seja, 
(rN)j ≥ 0, j = 1, 2,…, n. Esta condiçãoé denominada de otimalidade primal ou 
solução dual factível. 
b) Exista pelo menos um elemento (xB)i < 0 , ou seja, a condição de não 
negatividade das variáveis primais não é atendida. Diz-se que a solução é primal 
infactível. 
 
 Antes de definir-se completamente os passos do método dual-simplex, 
ilustremo-lo com o seguinte exemplo. 
 
Exemplo 4.6.1: 
 Seja o problema de programação linear primal: 
 Min � = 3 w1 + 4 w2 + 9 w3 
 s.a w1 + w3 ≥ 5 
 w2 + 2 w3 ≥ 2 
 w1, w2, w3 ≥ 0 
 Problema dual: 
 Max z = 5 x1 + 2 x2 
 x1 ≤ 3 
 x2 ≤ 4 
 x1 + 2 x2 ≤ 9 
 x1 e x2 ≥ 0 
 Resolvendo o primal pelo método dual-simplex: 
Forma padrão: Min � = 3 w1 + 4 w2 + 9 w3 
 s.a w1 + w3 - w4 = 5 
 w2 + 2 w3 - w5 = 2 
 w1,…, w5 ≥ 0 
 Para iniciarmos o método devemos ter-se bi < 0 então multiplicando-se por (-1), 
as equações do sistema, tem-se:: 
 Min � = 3 w1 + 4 w2 + 9 w3 
 s.a - w1 - w3 + w4 = -5 
 - w2 - 2 w3 + w5 = -2 
 w1,…, w5 ≥ 0 
Quadro 1: 
 w1 w2 w3 w4 w5 
w1 -1 0 -1 1 0 -5 
w5 0 -1 -2 0 1 -2 
 3 4 9 0 0 0 
1) Variável que sai da base: 
 69
 b4 = ε= min { -5, -2} = -5 � w4 sai da base (a linha pivô é a linha 1). 
2) Variável que entra na base: 
 Min = 
−
−
− −
−
�
�
�
�
�
�
3
1
4
0
9
1
0
1
0
0
, , , , =3 � w1 entra na base e o elemento pivô da 
eliminação gaussiana e a11 = -1. 
3) Pivoteamento em torno de a11: 
 
Quadro 2: 
 w1 w2 w3 w4 w5 
w1 1 0 1 -1 0 5 
w5 0 -1 -2 0 1 -2 
 0 4 6 3 0 -15 
1) Variável que sai na base: 
 w5 = -2 � sai da base (linha pivô 2). 
 
 
2) Variável que entra na base: 
 Min = 
����
����
����
����
����
���� −−−−
−−−−
−−−−
−−−−
−−−−
1
0
,
0
3
,
2
6
,
1
4
,
0
0
= 3 � w3 entra na base (elemento pivô: a23 = -2). 
3) Pivoteamento em torno de a22: 
Quadro 3: 
 w1 w2 w3 w4 w5 
w1 1 -1/2 0 -1 1/2 4 
w3 0 1/2 1 0 -1/2 1 
 0 1 0 3 3 -21 
 Portanto, como não há nenhum bi < 0, o quadro é ótimo, com w* = (4, 
0,1,0,0) e z* = 21. 
 Vamos resolver o Problema dual e comparar sua solução com o Problema 
primal. 
Forma padrão: Max z = 5 x1 + 2 x2 z - 5 x1 - 2 x2 = 0 
 x1 + x3 = 3 
 x2 + x4 = 4 
 x1 + 2 x2 + x5 = 9 
 x1, x2, x3, x4, x5 ≥ 0 
Quadro 1: 
 x1 x2 x3 x4 x5 b 
x3 1 0 1 0 0 3 
x4 0 1 0 1 0 4 
x5 1 2 0 0 1 9 
-z -5 -2 0 0 0 0 
1) Variável que entra na base: 
 x1 entra pois o seu coeficiente na função objetivo é mais negativo. 
2) Variável que sai da base: 
 70
ε = mínimo { 3/1, 4/0, 9/1} = 3. 
Portanto x3 sai da base. O elemento pivô é a11 = 1. 
3) Pivoteamento em torno de a11, obtendo o quadro 2: 
 
 x1 x2 x3 x4 x5 b 
x1 1 0 1 0 0 3 
x4 0 1 0 1 0 4 
x5 0 2 -1 0 1 6 
-z 0 -2 5 0 0 15 
 
1) Variável que entra na base: 
 x2 entra pois o seu coeficiente de custo relativo é negativo. 
2) Variável que sai da base: 
ε = mínimo { 3/0, 4/1, 6/2} = 3. 
Portanto x5 sai da base. O elemento pivô é a31 = 2. 
3) Pivoteamento em torno de a31, obtendo o quadro 3: 
 
 x1 x2 x3 x
4 
x5 b 
x1 1 0 1 0 0 3 
x4 0 0 1/2 1 -1/2 1 
x5 0 1 -1/2 0 1/2 3 
-z 0 0 4 0 1 21 
 
4.6.2- Definição dos passos do método Dual-Simplex 
 
 Considere D = { w ∈ℜm tal que ATw ≤ c }. 
 Considere também uma partição da matriz A = [B,N] e uma solução 
corrente w . 
 
 
 
 
Teorema 4.6.2.1: 
 w é um vértice de D se e somente se existirem m restrições ativas em w , 
com os gradientes linearmente independentes, isto é, com uma base B ∈ℜmxm , 
associada a estas m restrições ativas, isto é, w é dual factível. 
 
Definição 4.6.2.1: 
 Se alguma restrição dual associada a uma coluna não-básica for ativa, istp 
é, a Nj
T w = c Nj , dizemos que w é dual degenerada ou a partição A = [B,N] é dual 
degenerada. 
 71
 
Teorema 4.6.2.2: 
 Se o problema primal tiver solução ótima então existirá pelo menos um 
vértice ótimo. 
 
 As provas dos teoremas vistos são deixadas como exercício pois são 
análogas às demonstrações feitas para o problema primal. 
 
4.6.3- Direções duais factíveis 
 
 Suponha conhecida uma partição dual factível, isto é, ∃ B-1 tal que 
( w )=c B
T B-1 e que esta seja uma partição não degenerada. 
 Se quiser-se determinar uma nova solução w = w + ε d com ε ≥ 0, então 
deve-se satisfazer: AT ( w + ε d) ≤ c ⇔ BT( w + ε d) ≤ cB. 
 Desde que , BT( w ) = cB � B
T d ≤ 0. 
 Isto é equivalente a, a Bi
T d ≤ 0 , para i = 1,...,m. 
 Note que, há duas possibilidades: 
i) a Bi
T d = 0 � a Bi
T ( w + ε d) = cB i ; (sempre estará satisfeita) 
ii) a Bi
T d ≤ 0 � a Bi
T ( w + ε d) ≤ cB i ; 
 Assim, a nova solução deixará de ser ativa apenas para as restrições em 
que ii) ocorra. 
 A estratégia dual-simplex consiste em definir a direção d de tal forma que 
apenas uma restrição deixe de ser ativa, para se obter a nova solução. Para isto, 
a direção é definida da seguinte maneira: 
BT dj = - ej; 
assim, a j-ésima restrição deixará de ser ativa na nova solução. 
 Para esta escolha tem-se que: dj = - (BT)j
-1 , onde (BT)j
-1 é a j-ésima linha 
de B-1. 
 
 
 
Teorema 4.6.3.1: 
 Para j =1,...,m; as direções dj são linearmente independentes e definem 
uma base para o conjunto de direções factíveis de D. 
 
4.6.4- Definição do tamanho do passo εεεε. 
 
 Como a solução é não degenerada, segue que ∃ε > 0 tal que: 
a Nj
T ( w + εd) ≤ cN j ; para i = 1,...,n-m 
e esta equação será sempre satisfeita desde que: 
 72
ε ≤
−c a w
a d
Nj Nj
T
Nj
T
 com aNj
T d > 0. 
 Assim, se escolher-se: 
ε =
−
=
−
>
c a w
a d
min
c a w
a d
a dNr Nr
T
Nr
T r
Nj Nj
T
Nj
T j Nj
T j{ / }0 ; 
a r-ésima restrição não básica torna-se ativa enquanto que uma das restrições 
básicas deixa de ser ativa. Por exemplo, se j = k, então a k-ésima restrição não 
básica torna-se inativa. 
 
4.6.5- Acréscimo da função objetivo dual. 
 
 Da forma que foi definida d tem-se que esta direção é uma direção de 
subida, isto é, de acréscimo da função o bjetivo dual. 
 Para a solução corrente tem-se : d = bT w . 
 Para a nova solução terá-se: d = bT ( w + ε dk ) = d + ε bT dk. 
 Note que, à solução básica primal associada à partição básica vale: 
xB = B-1b; 
e k-ésima componente de xB é: 
xBk = (B
-1)k b = - ( dk)Tb; 
 Então, 
d = d - ε xBk . 
 Assim, se xBk < 0, a função dual tem um acréscimo linear com a taxa -
xBk . 
 Desta forma, a infactibilidade da solução básica primal produz uma direção 
de subida para a função objetivo dual. 
 
4.6.6- Os passos do método Dual-Simplex. 
 
Passo 1: 
 Determine uma solução básica dual ( w )= c B
T B-1 e calcule a solução 
básica primal B xB = b. 
Passo 2: 
 Se xB ≥ 0, pare, pois não é mais possível obter acréscimos para a função 
objetivo dual. Caso contrário: 
 Seleção da variável a deixar a base: 
 Escolha uma das variáveis negativas, de preferência a mais negativa: 
(xB)k = min { (xB)i tal que (xB)i < 0}. 
 Assim, a variável básica corresponde à linha k sai da base e a linha k é a 
linha pivô. 
 
 73
Passo 3: 
 Determine dk tal que: BT dk = - ek; 
 
Passo 4: 
 Seleção da variável a entrar na base: 
 Determine r tal que: 
ε =
−
=
−
>
c a w
a d
min
c a w
a d
a dNr Nr
T
Nr
T r
Nj Nj
T
Nj
T j Nj
T j{ / }0 
 Se a Nj
T dk ≤ 0, par j = 1,...,n-m; então o problema dual é ilimitado e então 
o problema dual é infactível. Pare. Caso contrário vá para o passo seguinte. 
 
Passo 5: 
 Atualize a partição básica trocando-se a k-ésima coluna de B pela r-ésima 
coluna de N , efetuando pivoteamento em ark e volte ao passo 1. 
 
Observação: 
 Se o problema dual for de minimização, há duas formas de tratá-lo. A 
primeira é aquela que consiste na conversão do problema para maximização. A 
outra, consite em inverter o critério de escolha da variável a entrar na base4.7- Exercícios propostos 
 
4.7.1) Dado o PPL primal: 
minimizar z = x1 - x2 + x3 
 sujeito a 
x
x x x
x x x
1
1 2 3
1 2 3
9
2
0
≤
+ + ≤
≥
�
�
�
�
� , ,
; 
Pede-se: 
a) resolva o PPL primal pelo método simplex, identifique a solução dual; 
 74
b) determine o PPL dual, resolva-o pelo método dual-simplex e identifique a 
solução primal; 
c) Verifique que as soluções dos dois problemas satisfazem as condições do 
teorema das folgas complementares. 
 
4.7.2) Resolva o seguinte PPL primal : 
maximizar z = 5x1 + 6x2 
 sujeito a: 
x x
x x
x x
1 2
1 2
1 2
3 5
4 9 12
0
+ ≤
+ ≤
≥
�
�
�
�
� ,
; 
 Suponha que façamos a seguinte mudança na função objetivo: 
maximizar (5-3u)x1 + (6-4u)x2 ; u ≥ 0. Determine a solução ótima do modelo em 
função de u. 
 
4.7.3) Dado o PPL primal em função de f : 
maximizar z = 2 x1 + 3 x2 + 3x3 
 sujeito a 
x x x
x x x f
x x x f
1 2 3
1 2 3
1 2 3
2 2 12
2 4
0
+ + ≤
+ + ≤
≥
�
�
�
�
� , , ,
; 
Pede-se: 
 
a) determine o valor máximo de f para que a base ótima não se altere. 
b) Para valores de f maiores que aquele obtido em 2.1) resolva o problema pelo 
método dual-simplex até que não se consiga mais melhorar a função objetivo 
primal. 
 
4.7.4) Utilize o método dual-simplex para resolver o PPL abaixo em função de λ : 
maximizar z = 2x1 + 3x2 
 sujeito a: 
x x
x x
x x
1 2
1 2
1 2
2 13
5 2
0 2
+ ≤
+ ≤ +
≥ ≤
�
�
�
�
�
λ
λ, ;
; 
 
BIBLIOGRAFIA 
 
[1] SWOKOWSKI, Earl W. Cálculo com Geometria Analítica. Vol. 1 e 2, Editora 
McGraw – Hill, 1994. 
 
[2] CALLIOLI, Carlos A., DOMINGUES, Hygino H., COSTA, Roberto C. F. Álgebra 
Linear e Aplicações. Atual Editora, 1993. 
 
[3] MACULAN, Nelson (Filho), PEREIRA, Mário Veiga Ferraz, Programação 
Linear, Editora Atlas, 1980. 
 75
 
[4] LUENBERGER, David G., Linear and Nonlinear Programming, Second 
Edition, 1989. 
 
[5] BAZARAA, Mokhtar S., JARVIS, John J. Linear Programming and Network 
Flows, John Wiley & Sons, 1977. 
 
[6] PUCCINI, Abelardo de Lima, PIZZOLATO, Nelio Domingues, Programação 
Linear, Livros Técnicos e Científicos Editora S.A., 1987. 
 
[7] RAMALHETE, Manuel, GUERREIRO, Jorge, MAGALHÃES, Alípio, 
Programação Linear, Volume 1. McGraw - Hill, 1984. 
 
[8] YOSHIDA, Luzia Kazuko, Programação Linear. Métodos Quantitativos, 
Atual Editora, 1987. 
 
[9] BALBO, Antonio Roberto; BAPTISTA, Edméa Cássia. Tópicos de Otimização 
e Programação Matemática I – Curso de Especialização em Matemática 
Aplicada e Computacional. Depto de Matemática – Fac. de Ciências – UNESP de 
Bauru, 1996.