IA881 – Otimização Linear

Aula: Dualidade em Programação Linear

Ricardo C. L. F. Oliveira

Faculdade de Engenharia Elétrica e de Computação

Universidade Estadual de Campinas

1o Semestre 2023

R. C. L. F. Oliveira IA881 - Otimização Linear 1/40

Tópicos

1 Introdução do Problema Dual

2 Derivando o Problema Dual

3 Formas Canônicas e Generalizações

4 Propriedades da Teoria de Dualidade

5 Dualidade Forte e Teorema Fundamental da Dualidade

6 Folgas Complementares

R. C. L. F. Oliveira IA881 - Otimização Linear 2/40

 Introdução do Problema Dual

O Problema da Dieta
 Considere a formulação do problema da dieta visto na aula Introdução à
Programação Linear

min z = 25x1 + 35x2 + 50x3 + 33x4 + 35x5

s. a 3x1 + 4x2 + 5x3 + 3x4 + 6x5 ≥ 42
2x1 + 3x2 + 4x3 + 3x4 + 3x5 ≥ 24
xi ≥ 0, i = 1, . . ., 5

ou
cT x cT = 25 35 50  33 35
 
min  
s. a Ax ≥ b , 3 4 5 3 6 42
A= , b=
x≥0 2 3 4 3 3 24
em que xi , i = 1, . . . , 5 são alimentos que contêm uma certa quantidade de
proteı́nas e sais minerais. A dieta requer uma quantidade mı́nima de 42 e 24
unidades de proteı́nas e sais minerais, respectivamente. Os custos de cada
unidade de alimento aparecem na função objetivo, e a quantidade de proteı́nas e
sais minerais contida em cada alimento aparece nas restrições. Por exemplo, uma
unidade do alimento x1 contém 3 unidades de proteı́nas e 2 unidades de sais
minerais.

R. C. L. F. Oliveira IA881 - Otimização Linear 3/40

 Introdução do Problema Dual

Nova Perspectiva do Problema da Dieta

 Uma indústria farmacêutica deseja propor uma alternativa para a realização da

dieta, fornecendo pı́lulas que contêm as quantidades desejadas de proteı́nas e sais
minerais. Assim o consumidor interessado na dieta poderia abrir mão de comprar
os alimentos e realizar a dieta exclusivamente à base de pı́lulas. O problema que a
indústria farmacêutica enfrenta é encontrar valores adequados w1 e w2 para as
pı́lulas (unidades) de proteı́na e sais minerais, de modo a maximizar a receita ao
mesmo tempo que é competitiva com a dieta alternativa com base em alimentos.

Por exemplo, considere o alimento x1 e seus nutrientes. Para ser competitiva, a

indústria deve considerar que o custo da quantidade de proteı́nas e sais suprida
por x1 não pode superar o valor de mercado de uma unidade do alimento x1 , isto é,
3w1 + 2w2 ≤ 25. Caso contrário seria mais vantajoso (do ponto de vista econômico)
fazer a dieta por meio do alimento.

R. C. L. F. Oliveira IA881 - Otimização Linear 4/40

 Introdução do Problema Dual

Formulação Dual
Criando restrições similares para todos os alimentos, e considerando que o
consumidor irá comprar exatamente a quantidade de proteı́nas e sais que atende a
necessidade (42 e 24), o problema da indústria pode ser formulado
matematicamente como

max z = 42w1 + 24w2

s. a 3w1 + 2w2 ≤ 25
4w1 + 3w2 ≤ 35
5w1 + 4w2 ≤ 50
3w1 + 3w2 ≤ 33
6w1 + 3w2 ≤ 35
wi ≥ 0, i = 1, . . ., 2

ou
max wT b max wT b
s. a wT A ≤ cT ou s. a AT w ≤ c
w≥0 w≥0
Note que A, b e c são os mesmos definidos no problema original.

R. C. L. F. Oliveira IA881 - Otimização Linear 5/40

 Introdução do Problema Dual

Dualidade Via Multiplicadores de Lagrange I

A teoria de dualidade pode ser considerada como uma consequência natural do

método dos multiplicadores de Lagrange, frequentemente utilizado em cálculo
diferencial na minimização de funções sujeitas a restrições de igualdade. Por
exemplo, considere o problema

min x2 + y2
s. a x +y = 1

Uma maneira de resolver é por meio da introdução de um multiplicador de

Lagrange w, criando a chamada função Lagrangeana

L(x, y, p) = x 2 + y 2 + w(1 − x − y)

Minimizando a função Lagrangeana em função de x e y (∂ L/∂ x = 0, ∂ L/∂ y = 0),

tem-se a seguinte solução ótima x = y = w/2 (depende de w). Da restrição
x + y = 1, tem-se que w = 1, e a solução ótima do problema original é x = y = 1/2.

 Traduzindo, a técnica dos multiplicadores de Lagrange consiste em permitir que a

restrição x + y = 1 seja violada e associar a ela um multiplicador de Lagrange w,
que vai ponderar a quantidade violada, isto é 1 − x − y. Essa estratégia leva ao

R. C. L. F. Oliveira IA881 - Otimização Linear 6/40

 Introdução do Problema Dual

Dualidade Via Multiplicadores de Lagrange II

problema de minimização irrestrito de L(x, y, w). Quando w é escolhido de maneira

apropriada (w = 1, no exemplo), a solução ótima do problema restrito também é a
solução ótima do problema irrestrito. Em particular, para o valor especı́fico de w
determinado, a presença ou ausência da restrição (x + y = 1) não afeta o custo
ótimo.

Claramente, a técnica pode ser aplicada à programação linear: associa-se um

conjunto de variáveis wi a cada restrição e procuram-se valores de wi tais que a
presença ou ausência das restrições não afeta o custo ótimo. O fato interessante é
que a busca pelos valores apropriados de wi também pode ser feita por um
problema de programação linear (!), chamado de problema dual.

R. C. L. F. Oliveira IA881 - Otimização Linear 7/40

 Derivando o Problema Dual

Lagrangeana do Problema Primal

 Considere o PL na forma padrão
min cT x
s. a Ax = b (1)
x≥0
considerado daqui em diante como problema primal, e seja x⋆ uma solução ótima
(assumi-se que ela existe). Constrói-se o problema relaxado em que a restrição
Ax = b é colocada como uma penalização na função objetivo, isto é,
min cT x + wT (b − Ax)
(2)
s. a x≥0
sendo w um vetor de multiplicadores com a mesma dimensão de b. Considerando
g(w) como o valor ótimo do problema relaxado em função de w, tem-se
h i
g(w) = min cT x + wT (b − Ax) ≤ cT x⋆ + wT (b − Ax⋆ ) = cT x⋆
x≥0

Traduzindo, o valor g(w) é sempre menor ou igual ao custo ótimo primal cT x⋆ .

Assim, qualquer w leva a um limitante inferior g(w) para o custo ótimo cT x⋆ e o
problema irrestrito max g(w) pode ser interpretado como a busca pelo melhor
limitante inferior (mais próximo de cT x⋆ ), conhecido como problema dual.
R. C. L. F. Oliveira IA881 - Otimização Linear 8/40
 Derivando o Problema Dual

Forma do Problema Dual

O principal resultado na teoria de dualidade assegura que o custo ótimo do
problema dual é igual ao custo ótimo do problema primal. Ou seja, quando os
multiplicadores são escolhidos de maneira ótima no problema dual, violar a
restrição Ax = b não traz nenhuma vantagem (valor objetivo melhor).

 Utilizando a definição de g(w) , tem-se

h i
g(w) = min cT x + wT (b − Ax)
x≥0
= wT b + min(cT − wT A)x
x≥0

Note que
se cT − wT A ≥ 0

0,
min(cT − wT A)x =
x≥0 −∞, caso contrário
Portanto, ao tentar maximizar o valor de g(w) apenas é necessário considerar os
valores de w tais que g(w) 6= −∞. Assim, conclui-se que o problema dual é um PL
na forma
max wT b
s. a wT A ≤ cT
w irrestrito

R. C. L. F. Oliveira IA881 - Otimização Linear 9/40

 Derivando o Problema Dual

Problema Primal na Forma Canônica

 Se o problema primal estiver na forma canônica, ou seja, com a restrição Ax ≥ b,

é possı́vel introduzir variáveis de excesso Ax − xs = b, xs ≥ 0, e a restrição de
igualdade pode ser reescrita na forma
 
  x
A −I =b
xs

que leva às restrições duais

wT A −I ≤ cT 0 ⇒ wT A ≤ cT , w ≥ 0
   

A partir dos resultados apresentados, é possı́vel estabelecer duas formas

(definições) importantes de dualidade (são equivalentes).

R. C. L. F. Oliveira IA881 - Otimização Linear 10/40

 Formas Canônicas e Generalizações

Forma Canônica de Dualidade

 Forma Canônica de Dualidade: Suponha que o problema primal é dado na
forma (canônica):
P : min cT x
s. a Ax ≥ b (3)
x≥0
então o problema dual é definido na forma

D: max wT b
s. a wT A ≤ cT (4)
w≥0
Note que existe exatamente uma variável dual para cada restrição do problema
primal e exatamente uma restrição dual para cada variável primal.
 Exemplo:

P : min z = 6x1 + 8x2 D : max z = 4w1 + 7w2

s. a 3x1 + x2 ≥ 4 s. a 3w1 + 5w2 ≤ 6
5x1 + 2x2 ≥ 7 w1 + 2w2 ≤ 8
xi ≥ 0, i = 1, . . ., 2 wi ≥ 0, i = 1, . . ., 2

R. C. L. F. Oliveira IA881 - Otimização Linear 11/40

 Formas Canônicas e Generalizações

Forma Padrão de Dualidade

 Forma Padrão de Dualidade: Outra definição equivalente de dualidade é dada
para um problema primal dado na seguinte forma (padrão):
P: min cT x
s. a Ax = b (5)
x≥0
então o problema dual é definido na forma
D: max wT b
s. a wT A ≤ cT (6)
w irrestrito
 Exemplo:

D : max z = 4w1 + 7w2

P : min z = 6x1 + 8x2 s. a 3w1 + 5w2 ≤ 6
s. a 3x1 + x2 − x3 =4 w1 + 2w2 ≤ 8
5x1 + 2x2 − x4 = 7 −w1 ≤0
xi ≥ 0, i = 1, . . . , 4 −w2 ≤ 0
w irrestrito
R. C. L. F. Oliveira IA881 - Otimização Linear 12/40
 Formas Canônicas e Generalizações

Dual do Dual
 Considere o problema dual em sua forma canônica
max wT b
s. a wT A ≤ cT
w≥0
Aplicando as transformações vistas nas primeiras aulas, é possı́vel reescrever esse
problema na forma
min −bT x̄
s. a (−AT )x̄ ≥ −c
x̄ ≥ 0
O problema dual desse último problema é dado por
max wT (−c) min cT w
s. a wT (−A)T ≤ (−bT ) ⇒ s. a Aw ≥ b
w≥0 x≥0
que apresenta a estrutura do problema primal.

Teorema 1
O dual do dual é o primal.

R. C. L. F. Oliveira IA881 - Otimização Linear 13/40

 Formas Canônicas e Generalizações

Formas Mistas de Dualidade e Generalizações I

 Utilizando as técnicas vistas na primeira aula, é possı́vel converter qualquer

problema de programação linear na forma padrão ou canônica. Por exemplo,
considere o problema

min z = c1 x1 + c2 x2 + c3 x3
s. a A11 x1 + A12 x2 + A13 x3 ≥ b1
A21 x1 + A22 x2 + A23 x3 ≤ b2
A31 x1 + A32 x2 + A33 x3 = b3
x1 ≥ 0, x2 ≤ 0, x3 irrestrito

R. C. L. F. Oliveira IA881 - Otimização Linear 14/40

 Formas Canônicas e Generalizações

Formas Mistas de Dualidade e Generalizações II

Para converter na forma canônica, multiplica-se a segunda desigualdade por -1,

divide-se a terceira restrição em duas desigualdades e as seguintes mudanças de
variáveis são realizadas x2 = −x2′ , x3 = x3′ − x3′′ , levando a

min z = c1 x1 − c2 x2′ + c3 x3′ − c3 x3′′

s. a A11 x1 − A12 x2′ + A13 x3′ − A13 x3′′ ≥ b1
−A21 x1 + A22 x2′ − A23 x3′ + A23 x3′′ ≥ −b2
A31 x1 − A32 x2′ + A33 x3′ − A33 x3′′ ≥ b3
−A31 x1 + A32 x2′ − A33 x3′ + A33 x3′′ ≥ −b3
x1 ≥ 0, x2 ≥ 0, x3′ ≥ 0, x3′′ ≥ 0

R. C. L. F. Oliveira IA881 - Otimização Linear 15/40

 Formas Canônicas e Generalizações

Formas Mistas de Dualidade e Generalizações III

Utilizando as seguintes variáveis duais w1 , w2′ , w3′ e w3′′ , tem-se a seguinte

representação dual

max w1 b1 − w2′ b2 + w3′ b3 − w3′′ b3

s. a w1 A11 − w2′ A21 + w3′ A31 − w3′′ A31 ≤ c1
−w1 A12 + w2′ A22 − w3′ A32 + w3′′ A32 ≤ −c2
w1 A13 − w2′ A23 + w3′ A33 − w3′′ A33 ≤ c3
−w1 A13 + w2′ A23 − w3′ A33 + w3′′ A33 ≤ −c3
w1 ≥ 0, w2′ ≥ 0, w3′ ≥ 0, w3′′ ≥ 0

Finalmente, utilizando as mudanças de variáveis w2 = −w2′ e w3 = w3′ − w3′′ , tem-se

max w1 b 1 + w2 b 2 + w3 b 3
s. a w1 A11 + w2 A21 + w3 A31 ≤ c1
w1 A12 + w2 A22 + w3 A32 ≥ c2
w1 A13 + w2 A23 + w3 A33 = c3
w1 ≥ 0, w2 ≤ 0, w3 irrestrito

R. C. L. F. Oliveira IA881 - Otimização Linear 16/40

 Formas Canônicas e Generalizações

Formas Mistas de Dualidade e Generalizações IV

Observando esse último problema e o primal original, percebe-se que cada

transformação aplicada no problema primal leva a uma modificação no problema
dual. Esse procedimento pode ser sistematizado conforme mostra a Tabela 1.

Tabela 1: Relações entre primal e dual .

problema min problema max

restrições
variáveis

≥0 ←−
−→ ≤
≤0 ←−
−→ ≥
irrestrito ←−
−→ =
≥ ←−
−→ ≥0
restrições

variáveis
≤ ←−
−→ ≤0
= ←−
−→ irrestrito

R. C. L. F. Oliveira IA881 - Otimização Linear 17/40

 Formas Canônicas e Generalizações

Formas Mistas de Dualidade e Generalizações V

 Exemplo:

max z = 8x1 + 3x2 − 2x3

s. a x1 − 6x2 + x3 ≥ 2
5x1 + 7x2 − 2x3 = −4
x1 ≤ 0, x2 ≥ 0, x3 irrestrito

Aplicando os resultados da tabela, tem-se

min z = 2w1 − 4w2

s. a w1 + 5w2 ≤ 8
−6w1 + 7w2 ≥ 3
w1 − 2w2 = −2
w1 ≤ 0, w2 irrestrito

R. C. L. F. Oliveira IA881 - Otimização Linear 18/40

 Propriedades da Teoria de Dualidade

Dualidade Fraca

 Como visto no inı́cio da aula, o custo g(w) associado a qualquer solução dual
fornece um limitante inferior para o custo ótimo. O próximo resultado formaliza essa
propriedade.

Teorema 2

Se x é uma solução factı́vel para o problema primal e w é uma solução factı́vel para
o problema dual, então
wT b ≤ cT x

Para provar o resultado, considere x e w como soluções factı́veis primais e duais,

respectivamente, e defina

ui = wi (ai x − bi )
vj = (cj − wT aj )xj

em que ai indica a linha i da matriz A.

R. C. L. F. Oliveira IA881 - Otimização Linear 19/40

 Propriedades da Teoria de Dualidade

Dualidade Fraca - Continuação

Da Tabela 1, observa-se que o sinal de wi é o mesmo de ai x − bi . Similarmente, o

sinal de xj é o mesmo de cj − wT aj . Assim, factibilidades primal e dual implicam
que ui ≥ 0, ∀i e vj ≥ 0, ∀j. Note que

∑ ui = wT Ax − wT b
i

∑ uj = cT x − wT Ax
j

Somando as duas igualdades e observando a não negatividade de ui e vj , tem-se

0 ≤ ∑ ui + ∑ vj = cT x − wT b.
i j

Portanto,
wT b ≤ cT x

R. C. L. F. Oliveira IA881 - Otimização Linear 20/40

 Propriedades da Teoria de Dualidade

Dualidade Fraca - Continuação

 Como ilustração, considere o exemplo

P : min z = 6x1 + 8x2 D : max z = 4w1 + 7w2

s. a 3x1 + x2 ≥ 4 s. a 3w1 + 5w2 ≤ 6
5x1 + 2x2 ≥ 7 w1 + 2w2 ≤ 8
xi ≥ 0, i = 1, . . ., 2 wi ≥ 0, i = 1, . . ., 2

As soluções factı́veis x0 = [7/5, 0]T e w0 = [2, 0]T . Então cT x0 = 42/5 = 8.4 e

wT0 b = 8. Assim, a solução ótima para ambos os problemas tem valor objetivo entre
8 e 8.4. Essa propriedade pode ser utilizada para terminar um problema de
programação linear por conta da proximidade do ótimo.

R. C. L. F. Oliveira IA881 - Otimização Linear 21/40

 Propriedades da Teoria de Dualidade

Outras Propriedades

 Outros resultados podem ser derivados a partir do teorema anterior.

Corolário 1
Se x0 e w0 são soluções factı́veis para os problemas primal e dual,
respectivamente, tal que cT x0 = wT0 b, então x0 e w0 são soluções ótimas para
seus respectivos problemas.

Corolário 2
Se um dos problemas tem um valor objetivo ilimitado, então o outro problema não
possui solução factı́vel.

R. C. L. F. Oliveira IA881 - Otimização Linear 22/40

 Dualidade Forte e Teorema Fundamental da Dualidade

Dualidade Forte

 Um outro resultado, conhecido como dualidade forte, é apresentado a seguir

Corolário 3

Se um problema possui uma solução ótima, então ambos os problemas possuem

soluções ótimas e os dois valores ótimos são iguais.

Para provar o resultado, considere um PL primal na forma padrão (matriz A com

rank completo) e a existência de uma solução ótima. Aplicando o método Simplex
nesse problema e evitando a ciclagem com as precauções necessárias, o método
vai terminar com uma solução ótima x e uma base ótima B. Seja xB = B−1 b o vetor
de variáveis básicas. O método termina pois o vetor de custos reduzidos é não
positivo, portanto
cTB B−1 A − cT ≤ 0
sendo que cB é o vetor com os custos das variáveis básicas.

R. C. L. F. Oliveira IA881 - Otimização Linear 23/40

 Dualidade Forte e Teorema Fundamental da Dualidade

Dualidade Forte - Continuação

Definindo w como wT = cTB B−1 , tem-se wT A ≤ cT , que mostra que w é uma

solução factı́vel para o problema dual

max wT b
s. a wT A ≤ cT

Além disso,
wT b = cTB B−1 b = cTB xB = cT x.
Pelo Corolário 3, w é uma solução ótima para o problema dual, com o mesmo valor
da solução ótima do primal.

R. C. L. F. Oliveira IA881 - Otimização Linear 24/40

 Dualidade Forte e Teorema Fundamental da Dualidade

Teorema Fundamental da Dualidade

 Finalmente, temos o resultado mais importante no contexto de dualidade em

programação linear, chamado de Teorema Fundamental da Dualidade:

Teorema 3
Com relação aos problemas de programação linear primal e dual, apenas uma das
alternativas apresentadas a seguir é verdadeira:
T
1 Ambos possuem soluções ótimas x⋆ e w⋆ com cT x⋆ = w⋆ b.
2 Se um problema tem um valor objetivo ótimo ilimitado, o outro deve ser
infactı́vel.
3 Ambos os problemas são infactı́veis.

O teorema anterior mostra que a dualidade não é completamente simétrica. Na

melhor das hipóteses, podemos afirmar que

P ótimo ⇔ D ótimo
P(D) ilimitado ⇒ D(P) infactı́vel
P(D) infactı́vel ⇔ D(P) ilimitado ou infactı́vel

R. C. L. F. Oliveira IA881 - Otimização Linear 25/40

 Folgas Complementares

Folgas Complementares I

 Uma importante relação entre as soluções ótimas primal e dual é fornecida pelas
condições das folgas complementares.

Teorema 4

Sejam x e w soluções factı́veis para os problemas primal e dual, respectivamente.

Os vetores x e w são soluções ótimas para os respectivos problemas se, e
somente se:

wi (ai x − bi ) = 0, ∀i,
T
(cj − w aj )xj = 0, ∀j,

Na prova do Teorema 2, foi definido ui = wi (ai x − bi ) e vj = (cj − wT aj )xj e, para x e

w factı́veis, ui ≥ 0 e vj ≥ 0. Também foi mostrado que

cT x − wT b = ∑ ui + ∑ vj
i j

R. C. L. F. Oliveira IA881 - Otimização Linear 26/40

 Folgas Complementares

Folgas Complementares II

Pela dualidade forte, se x e w são ótimos, então cT x = wT b, o que implica em

ui = vj = 0, ∀i, j. Reciprocamente, se ui = vj = 0, ∀i, j, então cT x = wT b e pelo
Corolário 3, tem-se que x e w são ótimos.

 A primeira condição do Teorema 4 está automaticamente satisfeita para qualquer

solução factı́vel de um PL primal na forma padrão. Se houverem restrições do tipo
ai x ≥ bi , então a condição de folga complementar associada garante que a variável
dual correspondente wi é nula, a não ser que a restrição esteja ativa.

 O teorema das folgas complementares também permite a determinação de uma

solução dual ótima a partir de uma solução básica factı́vel ótima não degenerada
de um PL primal na forma padrão. Sejam xj as variáveis básicas dessa solução
primal. Então, da condição (cj − wT aj )xj = 0 tem-se que wT aj = cj para todo j. As
colunas básicas aj são LI (formam a base B) e o vetor w pode ser calculado
(unicamente) por meio de wT = cTB B−1 .

R. C. L. F. Oliveira IA881 - Otimização Linear 27/40

 Folgas Complementares

Exemplo

Exemplo
Considere o PL na forma padrão e seu dual

max z = 8w1 + 3w2

min z = 13x1 + 10x2 + 6x3
s. a 5w1 + 3w2 ≤ 13
s. a 5x1 + x2 + 3x3 = 8
w1 + w2 ≤ 10
3x1 + x2 =3
3w1 ≤ 6
xi ≥ 0, i = 1, . . . , 3
w irrestrito
Determine a solução ótima dual a partir da solução ótima primal não degenerada
x⋆ = [1, 0, 1]T .

Como x⋆ = [1, 0, 1]T é uma solução primal ótima não degenerada, utilizam-se as
folgas complementares para encontrar a solução ótima para o dual. A condição
wi (ai x⋆ − bi ) = 0 está automaticamente satisfeita para todo i pois o PL primal está
na forma padrão. A condição (cj − wT aj )xj⋆ = 0 está satisfeita para j = 2 pois
x2⋆ = 0. Entretanto, como x1⋆ > 0 e x3⋆ > 0, é necessário que 5w1 + 3w2 = 13 e
3w1 = 6, fornecendo w1 = 2 e w2 = 1. Note que essa é uma solução dual factı́vel
cujo custo vale 19, que é o mesmo custo de cT x⋆ (provando que x⋆ é de fato ótimo).
R. C. L. F. Oliveira IA881 - Otimização Linear 28/40
 Folgas Complementares

Exemplo

Exemplo
Considere o par primal dual

max z = 4w1 + 3w2

s. a w1 + 2w2 ≤ 2
min z = 2x1 + 3x2 + 5x3 + 2x4 + 3x5
w1 − 2w2 ≤ 3
s. a x1 + x2 + 2x3 + x4 + 3x5 ≥ 4
2w1 + 3w2 ≤ 5
2x1 − 2x2 + 3x3 + x4 + x5 ≥ 3
w1 + w2 ≤ 2
xi ≥ 0, i = 1, . . . , 5
3w1 + w2 ≤ 3
wi ≥ 0, i = 1, 2
Determine a solução ótima primal a partir de uma solução gráfica do problema dual.

A representação gráfica da região factı́vel do problema dual é mostrada na

Figura 1. O vetor gradiente é dado por b e o vértice ótimo é w ⋆ = [4/5, 3/5]T , com
valor objetivo ótimo dado por z ⋆ = 5.

R. C. L. F. Oliveira IA881 - Otimização Linear 29/40

 Folgas Complementares

1.2

1  
1 4
w⋆ = 5 3
0.8

0.6
w2

0.4

0.2 b

-0.2 0 0.2 0.4 0.6 0.8 1 1.2

w1

Figura 1: Região factı́vel do problema dual.

R. C. L. F. Oliveira IA881 - Otimização Linear 30/40

 Folgas Complementares

Exemplo

Note que a segunda, terceira e quarta restrições duais no ponto w ⋆ fornecem

w1 − 2w2 ≤ 3 −0.4 ≤ 3
2w1 + 3w2 ≤ 5 ⇒ 3.4 ≤ 5
w1 + w2 ≤ 2 1.4 ≤ 2

indicando que as mesmas não estão ativas. Portanto, pelo teorema das folgas
complementares, x2⋆ = x3⋆ = x4⋆ = 0. Além disso, como w1⋆ ≥ 0 e w2⋆ ≥ 0, tem-se que
x1⋆ + 3x5⋆ = 4 e 2x1⋆ + x5⋆ = 3, o que fornece x1⋆ = x5⋆ = 1.

R. C. L. F. Oliveira IA881 - Otimização Linear 31/40

 Folgas Complementares

Revisitando o Problema da Dieta I

Considere o problema da dieta formulado do ponto de vista da indústria

farmacêutica, isto é

max z = 42x1 + 24x2

s. a 3x1 + 2x2 ≤ 25
4x1 + 3x2 ≤ 35
5x1 + 4x2 ≤ 50
3x1 + 3x2 ≤ 33
6x1 + 3x2 ≤ 35
xi ≥ 0, i = 1, . . ., 2

sendo tratado agora como o problema primal. A Figura 2 ilustra a região factı́vel do
problema, a direção do vetor gradiente c = [42 24]T e o ponto extremo ótimo x⋆ .

R. C. L. F. Oliveira IA881 - Otimização Linear 32/40

 Folgas Complementares

Revisitando o Problema da Dieta II

10
x⋆
8

6
x2
4

2
c
0

-2 0 2 4 6 8 10
x1

Figura 2: Região factı́vel do problema da dieta (ponto de vista da indústria

farmacêutica).

R. C. L. F. Oliveira IA881 - Otimização Linear 33/40

 Folgas Complementares

Revisitando o Problema da Dieta III

Mudando o sinal da função objetivo e introduzindo variáveis de folga, aplica-se o

método Simplex, que fornece (para as variáveis originais)
T
x⋆ = 2/3 z ⋆ = 276

31/3 ,

Substituindo x⋆ nas restrições, tem-se

22.66 ≤ 25, 33.66 ≤ 35, 44.66 ≤ 50, 33 ≤ 33, 35 ≤ 35

indicando que apenas duas restrições estão ativas. Pelo teorema da folgas
complementares, tem-se necessariamente que w1⋆ = w2⋆ = w3⋆ = 0 no problema
dual (formulação do ponto de vista do consumidor). O fato de w1⋆ = w2⋆ = w3⋆ = 0
pode ser interpretado pela indústria farmacêutica que as três primeiras restrições
não têm nenhuma influência na determinação dos valores ótimos para x1⋆ e x2⋆
(valor das pı́lulas de proteı́nas e sais minerais). Portanto, o custo ótimo z ⋆ pode se
manter mesmo diante de pequenas violações nas três primeiras restrições (por
exemplo, no valor dos alimentos). Em resumo, no cenário atual, apenas os valores
dos produtos quatro e cinco é que estão sendo determinantes na estipulação dos
preços das pı́lulas.

R. C. L. F. Oliveira IA881 - Otimização Linear 34/40

 Folgas Complementares

Revisitando o Problema da Dieta IV

Como x1⋆ > 0 e x2⋆ > 0, também do teorema das folgas complementares é
necessário que as restrições duais sejam atendidas na igualdade na solução ótima
dual, isto é,
3w1⋆ + 4w2⋆ + 5w3⋆ + 3w4⋆ + 6w5⋆ = 42
2w1⋆ + 3w2⋆ + 4w3⋆ + 3w4⋆ + 3w5⋆ = 24
o que fornece, w4⋆ = 2 e w5⋆ = 6.

R. C. L. F. Oliveira IA881 - Otimização Linear 35/40

 Folgas Complementares

Uma Visão Geométrica do Par (x, w ) I

 Apresenta-se uma visão geométrica dos pares de vetores x e w sem a

necessidade de recorrer ao esboço gráfico da região factı́vel do dual. Considere o
problema primal na forma

min cT x min cT x
⇒
s. a Ax ≥ b s. a ai x ≥ bi , i = 1, . . . , m

com x ∈ Rn . Assume-se que os vetores (linha) ai geram o Rn . O problema dual é

dado por
max wT b
max wT b m
s. a wT A = cT ⇒ s. a ∑ wi ai = cT
w≥0 i=1
w≥0
Dado um conjunto de n linhas ai linearmente independentes, denotado por I, é
possı́vel construir uma solução (única) x̄ a partir de ai x = bi , i ∈ I, que é uma
solução básica para o problema primal. Assume-se que x̄ é uma solução não
degenerada (isto é, ai x 6= bi , i ∈
/ I).

R. C. L. F. Oliveira IA881 - Otimização Linear 36/40

 Folgas Complementares

Uma Visão Geométrica do Par (x, w ) II

Seja w ∈ Rm um vetor de variáveis duais (não necessariamente dual factı́vel). Para

que x̄ e w sejam soluções ótimas para seus respectivos problemas, é necessário
que

(a) ai x̄ ≥ bi , ∀i, (factibilidade primal)

(b) wi = 0, para todo i ∈
/ I, (folga complementar)
(c) ∑m i
i=1 wi a = c ,
T (factibilidade dual)
(d) w ≥ 0. (factibilidade dual)

Em função da condição (b), a condição (c) pode ser reduzida a

∑ wi a i = c T ,
i∈I

possuindo uma solução única (e básica) w̄ pois os vetores ai com i ∈ I são

linearmente independentes (formam uma base para o problema dual). Para que o
vetor w̄ seja dual factı́vel, ele precisa ser não negativo. Com a condição (b)
satisfeita, a factibilidade do vetor w̄ é equivalente ao vetor c ser uma combinação
não negativa dos vetores ai , i ∈ I, associados às restrições primais ativas, como
ilustra a Figura 3.

R. C. L. F. Oliveira IA881 - Otimização Linear 37/40

 Folgas Complementares

Uma Visão Geométrica do Par (x, w ) III

a3

A c a5

a4

a2

a1
D

Figura 3: Região factı́vel do problema primal e representação geométrica

das restrições duais.

R. C. L. F. Oliveira IA881 - Otimização Linear 38/40

 Folgas Complementares

Uma Visão Geométrica do Par (x, w ) IV

A figura mostra um caso particular com n = 2 variáveis e m = 5 restrições e

nenhum vetor ai é colinear. Para cada subconjunto I formado por dois elementos
de {1, 2, 3, 4, 5} existem soluções básicas primal x̄ e dual w̄. A seguir são
analisados os vértices A, B, C e D.
A I = {1, 2}, x̄ é primal infactı́vel e w̄ é dual infactı́vel pois c não pode ser
expresso como uma combinação não negativa dos vetores a1 e a2 .
B I = {1, 3}, x̄ é primal factı́vel e w̄ é dual infactı́vel.
C I = {1, 4}, x̄ é primal factı́vel e w̄ é dual factı́vel pois c pode ser expresso
como uma combinação não negativa dos vetores a1 e a4 .
D I = {1, 3}, x̄ é primal infactı́vel e w̄ é dual factı́vel.
 Seja x∗ uma solução básica primal degenerada. Nesse caso pode haver diversos
subconjuntos I tais que x̄ = x∗ . Utilizando diferentes subconjuntos I, é possı́vel
obter diversas soluções básicas duais w̄. Pode acontecer de algumas soluções w̄
serem factı́veis e outras não, como ilustra a Figura 4. Contudo, se w̄ é factı́vel
(todos os w̄i são não negativos) e se x∗ é primal factı́vel, então ambos são ótimos,
pois a condição das folgas complementares foi considerada.

R. C. L. F. Oliveira IA881 - Otimização Linear 39/40

 Folgas Complementares

Uma Visão Geométrica do Par (x, w ) V

a2

c a3

a1
x∗

Figura 4: Região factı́vel do problema primal e representação geométrica

das restrições duais.

R. C. L. F. Oliveira IA881 - Otimização Linear 40/40