Dualidade
Alexandre Salles da Cunha
DCC-UFMG, Abril 2010
Alexandre Salles da Cunha Dualidade
Motivacao
(P) max z = 4x1 +x2 +5x3 +3x4
s.t.: x1 −x2 −x3 +3x4 ≤ 1
5x2 +x2 +3x3 +8x4 ≤ 55
−x1 +2x2 +3x3 −5x4 ≤ 3
xi ≥ 0
Para obtermos limites inferiores: qualquer solucao viavel, por exemplox = (2, 1, 1, 1
2).
Como obtemos limites superiores ?
Alexandre Salles da Cunha Dualidade
Obtendo limites superiores
max z∗ = 4x1 +x2 +5x3 +3x4
s.t.: x1 −x2 −x3 +3x4 ≤ 1
5x1 +x2 +3x3 +8x4 ≤ 55
−x1 +2x2 +3x3 −5x4 ≤ 3
xi ≥ 0
Multiplicando a segunda restricao por 53 e a primeira e terceira por 0 e
somando o resultado temos:
5
3(5x1 +x2 +3x3 +8x4) ≤
5
355
=25
3x1 +5
3x2 +5x3 +40
3x4 ≤
275
3
Alexandre Salles da Cunha Dualidade
Obtendo limites superiores
Considerando a nao negatividade das variaveis de decisao e comparando oscoeficientes na funcao objetivo com os coeficientes da restricao
25
3x1 +
5
3x2 + 5x3 +
40
3x4 ≤
275
3
x1 ≥ 0 e 253 ≥ 4,
x2 ≥ 0 e 53 ≥ 1,
x3 ≥ 0 e 5 ≥ 5,
x4 ≥ 0 e 403 ≥ 3,
temos que 4x1 + x2 + 5x3 + 3x4 ≤253 x1 + 5
3x2 + 5x3 + 403 x4 ≤
2753 .
Logo o objetivo de qualquer solucao viavel e limitado superiormente por2753 e, em particular, z∗ ≤ 275
3 .
Alexandre Salles da Cunha Dualidade
Qual o melhor limite superior que podemos obter ?
Mutiplicando cada linha i das restricoes por uma quantidade pi ≥ 0:
p1(x1 −x2 −x3 +3x4) ≤ 1p1
p2(5x1 +x2 +3x3 +8x4) ≤ 55p2
p3(−x1 +2x2 +3x3 −5x4) ≤ 3p3
Somando o resultado temos:
x1(p1 + 5p2 − p3) +
x2(−p1 + p2 + 2p3) +
x3(−p1 + 3p2 + 3p3) +
x4(+3p1 + 8p2 − 5p3) ≤ p1 + 55p2 + 3p3
Alexandre Salles da Cunha Dualidade
Qual o melhor limite que podemos obter ?
Se impusermos que os coeficientes em x1, . . . , x4 na restricao sejampelo menos tao grandes quanto os da funcao objetivo(4x1 + x2 + 5x3 + 3x4)
p1 + 5p2 − p3 ≥ 4
−p1 + p2 + 2p3 ≥ 1
−p1 + 3p2 + 3p3 ≥ 5
+3p1 + 8p2 − 5p3 ≥ 3
podemos dizer que w = p1 + 55p2 + 3p3 fornece um limite superiorpara o objetivo de qualquer solucao viavel, em particular para asolucao otima.
Alexandre Salles da Cunha Dualidade
Qual o melhor limite que podemos obter ?
Entao e natural desejarmos conhecer o menor dos limites inferiores,gerados por um vetor (p1, p2, p3) conveniente. Ou seja, e naturalformularmos o seguinte Programa Linear:
O Problema Dual associado a (P)
(D) min w = p1 + 55p2 + 3p3
p1 + 5p2 − p3 ≥ 4
−p1 + p2 + 2p3 ≥ 1
−p1 + 3p2 + 3p3 ≥ 5
+3p1 + 8p2 − 5p3 ≥ 3
p1, p2, p3 ≥ 0
Alexandre Salles da Cunha Dualidade
De uma forma geral
Problema Primal
max
n∑
j=1
cjxj
n∑
j=1
aijxj ≤ bi i = 1, . . . ,m
xj ≥ 0 j = 1, . . . , n
Problema Dual
minm
∑
i=1
bipi
m∑
i=1
aijpi ≥ cj j = 1, . . . , n
pi ≥ 0 i = 1, . . . , n
Cada uma das restricoes primais∑
aijxj ≤ bi associa-se a umavariavel dual pi e vice-versa.Cada uma das restricoes duais
∑
aijpi ≥ cj associa-se a uma variavelprimal xj e vice-versa.Os coeficientes de cada variavel de um programa (primal ou dual) nafuncao objetivo aparecem no outro programa, como termoindependente do sistema de restricoes.
Alexandre Salles da Cunha Dualidade
Um outro ponto de partida
min c ′x
s.t.: Ax = b
x ≥ 0
onde A ∈ Rm×n, b ∈ R
m, c ∈ Rn.
Problema Relaxado
O sistema de restricoes Ax = b e relaxado, e a sua violacao e penalizadana funcao objetivo:
min c ′x + p′(b − Ax)
s.t.: x ≥ 0
onde p ∈ Rm e um vetor da mesma dimensao de b.
Alexandre Salles da Cunha Dualidade
O problema relaxado
L(p) :
g(p) = min c ′x + p′(b − Ax)
s.t.: x ≥ 0
Observe que o conjunto de viabilidade do problema relaxado inclui oconjunto de viabilidade do problema original.
g(p) = minx≥0
[
cx + p′(b − Ax)]
≤ (pela otim. de g(p))
c ′x∗ + p′(b − Ax∗) = (pela viab. de x∗)
c ′x∗
Ou seja...
g(p) fornece um limite dual (neste caso inferior) para c ′x∗.
Alexandre Salles da Cunha Dualidade
O melhor limite que podemos obter
O Problema Dual Lagrangeano
max g(p)
s.t.: p ∈ Rm sem restricoes !
Os principais resultados teoricos:
ja mostramos que g(p) ≤ c ′x∗ (dualidade fraca)
vamos mostrar que maxg(p) = c ′x∗ (dualidade forte).
Quando os precos p sao aqueles que resolvem o Problema DualLagrangeano, p∗, violar ou nao as restricoes Ax = b e irrelevante.Isto e, basta resolvermos o problema minx≥0g(p∗) que obtemos umasolucao otima para o problema primal !
Alexandre Salles da Cunha Dualidade
Explorando esta ultima observacao
g(p) = minx≥0
[
c ′x + p′(b − Ax)]
= p′b + minx≥0
(
c ′ − p′A)x]
Logo: minx≥0 [(c ′ − p′A)x ] =
{
0, se c ′ − p′A ≥ 0−∞ c.c.
Entao para maximizarmos g(p) basta considerarmos os valores de ppara os quais g(p) nao e −∞.
Portanto, o Problema Dual Lagrangeano e equivalente a:
Dual de Programacao Linear
max p′b
s.t.: p′A ≤ c
Alexandre Salles da Cunha Dualidade
Variacoes
Primal
min c ′x
s.t.: Ax ≤ b
x ≥ 0
Funcao Lagrangeana, p ≥ 0
g(p) = c ′x + p′(b − Ax)
s.t.: x ≥ 0
g(p) = minx≥0
[
cx + p′(b − Ax)]
≤ (pela otim. de g(p))
c ′x∗ + p′(b − Ax∗) ≤ (pela viab. de x∗, p ≤ 0)
c ′x∗
Dual Lagrangeano
max g(p)
s.t.: p ≤ 0
Dual Lagrangeano
max p′b
s.t.: c ′ ≥ p′A
p ≤ 0Alexandre Salles da Cunha Dualidade
Estrutura geral do par primal-dual
primal
min c ′x
a′ix ≥ bi , i ∈ M1
a′ix ≤ bi , i ∈ M2
a′ix = bi , i ∈ M3
xj ≥ 0, j ∈ N1
xj ≤ 0, j ∈ N2
xj irrestrito, j ∈ N3
dual
max b′p
pi ≥ 0, i ∈ M1
pi ≤ 0, i ∈ M2
pi irrestrito , i ∈ M3
p′Aj ≤ cj , j ∈ N1
p′Aj ≥ cj , j ∈ N2
p′Aj = cj , j ∈ N3
Alexandre Salles da Cunha Dualidade
O dual do dual e o primal
Teorema
Se transformarmos o problema dual em um problema de minimizacao eescrevermos o seu dual, iremos obter um problema de otimizacaoequivalente ao problema primal.
Exemplo:
min x1 +2x2 +3x3
−x1 +3x2 = 5
2x1 −x2 +3x3 ≥ 6
x3 ≤ 4
x1 ≥ 0
x2 ≤ 0
x3 ≷ 0
max 5p1 +6p2 +4p3
−p1 +2p2 ≤ 1
3p1 −p2 ≥ 2
3p2 +p3 = 3
p1 ≷ 0
p2 ≥ 0
p3 ≤ 0
Alexandre Salles da Cunha Dualidade
Equivalencias entre pares primal-dual
Par primal-dual I
min c′x
Ax ≥ b
x ≷ 0
max p′b
p ≥ 0
p′A = c′
Par primal-dual II - introduzindo folgas
min c′x + 0s
Ax − Is = b
x ≷ 0
s ≥ 0
max p′b
p ≷ 0
p′A = c′
−p ≤ 0
Par primal-dual III - introduzindo variaveis nao negativas
min c′x+ − c′x−
Ax+ − Ax− ≥ b
x+ ≥ 0
x− ≥ 0
max p′b
p ≥ 0
p′A ≤ c′
−p′A ≤ −c′
Efeito no dual de restricoes redundantes no primal
min c ′x
Ax = b
x ≥ 0
max p′b
p′A ≤ c ′
Vamos assumir que am =∑m−1
i=1 γai para escalares γ1, . . . , γm−1.
Para qualquer x viavel: bm = a′x =∑m−1
i=1 γia′ix =
∑m−1i=1 γibi .
As restricoes duais∑m
i=1 pia′i ≤ c ′ podem ser reescritas como:
∑m−1i=1 (pi + γipm)a′i ≤ c ′.
Alem disto, temos que o custo dual∑m
i=1 pibi =∑m−1
i=1 (pi + γipm)bi .
Defina qi = pi + γipm e verifique dual anterior equivale a:
max
m−1∑
i=1
qibi
m−1∑
i=1
qia′
i ≤ c ′
Alexandre Salles da Cunha Dualidade
Em sıntese
Teorema1 Suponha que tenhamos transformado um programa linear Π1 em
outro programa linear Π2, por uma sequencia de transformacoes daseguinte forma:
1 Substitua uma variavel livre pela diferenca de duas variaveis naonegativas;
2 Substitua uma desigualdade por uma restricao de igualdade,introduzindo variaveis de folga (excesso) convenientes;
3 Se alguma das linhas da matriz A em na forma padrao viavel e umacombinacao linear das outras linhas, elimine a correspondente linha dosistema na forma padrao.
Entao os dois problemas Π1,Π2 sao equivalentes, isto e, ou os dois saoinviaveis ou possuem o mesmo custo otimo.
Alexandre Salles da Cunha Dualidade
Dualidade Fraca
Par primal-dual
(P) min c ′x
Ax = b
x ≥ 0
(D) max p′b
p′A ≤ c ′
Teorema
Se x e uma solucao viavel para o problema primal (P) e p e uma solucaoviavel para o dual (D) de (P), entao p′b ≤ c ′x.
Prova
Ax = b → p′Ax = p′b
p′A ≤ c ′ → p′Ax ≤ c ′x
p′b ≤ c ′x
Alexandre Salles da Cunha Dualidade
Corolarios
1 Se o custo primal otimo e −∞, entao o dual deve ser inviavel.
2 Se o custo dual otimo e ∞, entao o problema primal deve ser inviavel.
3 Se x e p sao solucoes viaveis para P e D, respetivamente e sep′b = c ′x , entao x , p resolvem P,D.
Alexandre Salles da Cunha Dualidade
Dualidade Forte
Teorema
Se o programa primal (P) possui uma solucao otima x∗, entao o seu dual(D) possui uma solucao p∗ tal que p′b = c ′x.
Prova
Caso 1 - Vamos considerar o primal na forma padrao e posto de Acompleto.
Assumindo que o metodo simplex tenha sido implementado com ocriterio de pivoteamento lexicografico, obtemos uma solucao otimaassociada a base B, isto e, x∗ = (x∗
B , x∗N) = (cBB−1, 0). Assuma que
N seja o conjunto dos ındices das variaveis nao basicas na solucaootima.
Defina p∗′ = c ′BB−1 e verifique que p∗ e dual viavel (o simplexterminou com condicoes de custo reduzido nao negativos).
uma vez que p∗′b = c ′BB−1b = (cB , cN)′(xB , 0)b, segue o resultado.
Alexandre Salles da Cunha Dualidade
Dualidade Forte
Prova
Caso 2 - posto de A incompleto e o problema nao escrito na formapadrao.
Reescreva o problema primal na forma padrao, elimine as linhasredundantes e redefina as variveis duais.
Alexandre Salles da Cunha Dualidade
Analogia mecanica da dualidade forte
Alexandre Salles da Cunha Dualidade
Analogia mecanica da dualidade forte
Vamos imaginar que uma bola seja introduzida em um poliedro (naovazio), definido pelas restricoes aix ≥ bi ,∀i .
O ponto de energia mınima da bola corresponde ao canto maisinferior possıvel do poliedro, dado por x∗. Ou seja, o ponto deequilıbrio x∗ corresponde a solucao do Programa Linear:
min c ′x
a′ix ≥ bi ∀i
onde c e um vetor na direcao oposta ao campo gravitacional.
As forcas normais as retricoes ativas em x∗ compoem a forca queequilibra a forca exercida pelo campo gravitacional. Isto e:c =
∑
i piai , onde pi sao pesos nao negativos.
Alexandre Salles da Cunha Dualidade
Analogia mecanica da dualidade forte
Em particular, p e uma solucao viavel para o Programa Dual
max p′b
p′A = c ′
p ≥ 0
Dado que as forcas so podem se exercidas pelas restricoes ativas emx∗, devemos ter pi = 0 quando a′ix
∗ > bi .
Consequentemente, temos pi (bi − a′ix∗) = 0, ∀i
Logo p′b =∑
i pibi =∑
i pia′ix
∗ = c ′x∗.
Entao p e uma solucao otima do dual.
Alexandre Salles da Cunha Dualidade
Possibilidades do par primal-dual
Otimo Finito Ilimitado Inviavel
Otimo finito Possıvel Impossıvel ImpossıvelIlimitado Impossıvel Impossıvel PossıvelInviavel Impossıvel Possıvel Possivel
Alexandre Salles da Cunha Dualidade
Caso Inviavel-Inviavel
Primal
min x1 + 2x2
x1 + x2 = 1
2x1 + 2x2 = 3
Dual
max 2p1 + 2x2
p1 + 2p2 = 1
p1 + 2p2 = 2
Alexandre Salles da Cunha Dualidade
Teorema das Folgas Complementares
Uma importante relacao entre os pares primal-dual e expresso na forma dacondicao de complementaridade-folga (ccf):
Teorema
Sejam x e p duas solucoes viaveis, respectivamente para os programasprimal e dual. Os vetores x e p sao otimos se e somente se:
pi (a′ix − bi) = 0 ∀i
(cj − p′Aj)xj = 0 ∀j
Alexandre Salles da Cunha Dualidade
Prova
Prova
(1) Se satisfaz x , p sao viaveis e satisfazem ccf, entao o par x , p e otimo.
∑
i
pi (a′ix − bi) = 0 →
∑
i
pia′ix =
∑
i
pibi
∑
j
xj(cj − p′Aj) = 0 →∑
j
cjxj = p′∑
j
Ajxj = p′b
Tendo em vista a Dualidade Fraca, p′b = c ′x, logo demonstra-se aotimalidade de x , p.
Alexandre Salles da Cunha Dualidade
Prova
Prova
(2) Se o par x , p e viavel e otimo, entao ccf sao satisfeitas.
Defina ui = pi (a′ix − bi) e vj = (cj − p′Aj)xj .
Observe que dado a viabilidade de x , p temos que ui ≥ 0,∀i evj ≥ 0,∀j .
Observe ainda que:
∑
i
ui +∑
j
vj =∑
i pia′x −
∑
i pibi +
∑
j cjxj − p′∑
j Ajxj =
c ′x − p′b = 0
Logo, como ui ≥ 0,∀i , vj ≥ 0,∀j temos que:∑
i ui +∑
j vj = 0→
{
ui = 0 ∀ivj = 0 ∀j
Alexandre Salles da Cunha Dualidade
Exemplo
min 13x1 + 10x2 + 6x3
5x1 + x2 + 3x3 = 8
3x1 + x2 = 3
x ≥ 0
max 8p1 + 3p2
5p1 + 3p2 ≤ 13
p1 + p2 ≤ 10
3p1 ≤ 6
As condicoes pi (bi − a′ix) = 0 sao automaticamente satisfeitas paraqualquer x viavel.
Vamos considerear a solucao otima x∗ = (1, 0, 1). Para a variavel naobasica x2, temos que x∗
2 (c2 − p′A2) = 0, uma vez que x∗2 = 0.
Resolvendo o sistema linear associado a p′B = c ′B :
5p1 + 3p2 = 133p1 = 6
cuja solucao e p1 = 2, p1 = 1 e custo dual e 19
Alexandre Salles da Cunha Dualidade
Representacao geometrica do dual
min c ′x
a′ix ≥ bi i = 1, . . . ,mmax p′b
m∑
i=1
piai = c
p ≥ 0Vamos assumir que:
I denota um subconjunto de {1, . . . ,m}, |I | = n, tal que os vetoresai : i ∈ I sao l.i..
Como o sistema aix = bi , i ∈ I admite solucao unica, denote x I estasolucao, que e basica para o primal.
Assuma que x I e nao degenerada, isto e a′ixI 6= bi , i 6∈ I .
Vamos assumir que p ∈ Rm seja um vetor de variaveis duais, nao
necessariamente otimo.
Alexandre Salles da Cunha Dualidade
Representacao geometrica do dual
Vamos estabelecer as condicoes requeridas para que o par x , p sejamotimos para os programas primal e dual, respectivamente:
1 a′ix ≥ bi ,∀i ∈ 1, . . . ,m (viabilidade primal)
2 pi = 0,∀i 6∈ I (complementaridade folga)
3
∑mi=1 piai = c (viabilidade dual)
4 p ≥ 0 (viabilidade dual)
Entao temos:
Diante das ccf, a condicao (3) ficam:∑
i∈I piai = c , que admitesolucao unica, uma vez que os vetores ai : i ∈ I sao li. Vamos denotarpor pI esta solucao.
Observe que os vetores ai : i ∈ I formam uma base para o dual (nrestricoes de igualdade satisfeitas e m − n restricoes de naonegatividade justas para i 6∈ I )
Para o vetor pI ser viaavel, e necessario que pI ≥ 0. Isto significa quec deve ser uma combinacao nao negativa das linhas ai : i ∈ I
Alexandre Salles da Cunha Dualidade
Representacao geometrica do dual, n = 2, m = 5, primal
nao denegerada
Representacao geometrica do dual, n = 2, m = 5, primal
denegerada
I = {1, 2}
I = {2, 3}
I = {1, 3}
Variaveis duais interpretadas como custos marginais
primal
min c ′x
Ax = b
x ≥ 0
Hipoteses:
linhas de A sao li.
existe solucao basica otima nao degenerada x∗
vamos assumir que B seja a base otima associada.
Vamos assumir tambem que p′ = cBB−1 seja o vetor dual otimoassociado a esta base.
Alexandre Salles da Cunha Dualidade
Variaveis duais interpretadas como custos marginais
O que acontece se perturbarmos por d o vetor b ?
Desde que a perturbacao seja pequena o suficiente paraB−1(b + d) ≥ 0, a base otima permanece a mesma.
Esta perturbacao suficientemente pequena para que a base otimapermaneca a mesma existe como consequencia da nao degeneracaoprimal.
A base permanece otima porque alem de permanecer viavel, nao hamodificacao na condicao de otimalidade primal (ou viabilidade dual).
Com a introducao da perturbacao, o custo dual passa de p′b parap′(b + d).
Logo uma mudanca de di de uma unidade no i−esimo termoindependente acarreta uma modificacao de custo de pi , na funcaoobjetivo dual e, consequentemetne no novo objetivo primal.
Assim sendo, as variaveis duais podem ser interpretadas como o customarginal por unidade de aumento de bi .
Alexandre Salles da Cunha Dualidade
Cada variavel possui um custo em termos dos precos duais
Vamos considerar a variavel (primal) j cujo custo e cj .
Podemos sintetizar o custo da variavel primal utilizada (basica) emtermos dos precos das variaveis duais (interpretados como precos porunidades de recursos dos insumos empregados).
Ou seja, se j e uma variavel basica utilizada, cj = p′Aj .
Toda variavel tem entao um custo em termos dos fatores de producao.
Alexandre Salles da Cunha Dualidade
Metodo Dual Simplex
Na demonstracao do Teorema da Dualidade Forte, definimos o vetordual p′ = c ′bB
−1 e observamos que a condicao de otimalidade primalc ′ − c ′BB−1A ≥ 0 equivale na verdade a condicao de viabilidade dualp′A ≤ c ′.
Podemos entao pensar no metodo Simplex como um algoritmo quemantem a viabilidade primal durante todo seu curso e quando sedepara com a viabilidade dual, comprova a otimalidade primal (e dualtambem !).
O Metodo Simplex e portanto um algoritmo primal.
Uma alternativa ao Simplex Primal e o Metodo Dual Simplex quegera solucoes basicas viaveis para o problema dual e caminha para aviabilidade dual - Metodo Dual Simplex.
Alexandre Salles da Cunha Dualidade
Metodo Dual Simplex
Quadro Simplex
min z = c ′BB−1xB + (c ′N − c ′BB−1N)xN
xB = B−1b − B−1NxN
Full Tableau Correspondente:
−cBB−1b c
B−1b B−1A
Ao longo de todo o algoritmo c ≥ 0, p = c ′BB−1 ≷ 0 (dual viavel)
Quando observarmos B−1b ≥ 0 temos viabilidade primal e portanto asolucao dual em maos e otima.
Alexandre Salles da Cunha Dualidade
Metodo Dual Simplex
Vamos assumir que B−1b 6≥ 0.
Entao obtenha l tal que xB(l) < 0 e considere a linha l do Tableau,chamada linha pivot. Esta linha tem as seguintes entradas:xB(l), v1, . . . , vn, onde vi e a l -esima entrada do vetor B−1Ai .
Para todo i : vi < 0 (caso tal ındice exista), calculamos a razao c i
|vi |.
Seja j o ındice da variavel para a qual a razao mınima e atingida, istoe, vj < 0 e
c j
|vj |= min{ c i
|vi |,∀i : vi < 0}. A entrada vj e chamada
elemento pivot.Realizamos uma mudanca de base: a coluna Aj entra na base e acoluna AB(l) sai da base. Esta operacao de pivoteamento ocorre damesma forma que no metodo Simplex Primal: somamos a todas aslinhas do Full Tableau (exceto a linha l) um multiplo da linha pivotde forma que todos os elementos da coluna j sejam zero, exceto oelemento vj que sera transformado em um 1.
Em particular, para zerar o custo reduzido da linha zero do tableau,multiplicamos a linha pivot por
c j
|vj |e somamos a linha zero.
Alexandre Salles da Cunha Dualidade
Alguns casos a considerar
1 Caso c j = 0 para algum ındice j ∈ N (nao basico) temos adegeneracao dual e o algoritmo termina dependendo das regras depivoteamento empregadas (lexicografica e de Bland).
2 Dado uma escolha de variavel B(l) para sair da base, caso nao existai : vi < 0, o custo dual otimo e ∞ e o problema primal e inviavel. Oalgoritmo entao termina.
Alexandre Salles da Cunha Dualidade
Exemplo
Quadro simplex, dual viavel
x1 x2 x3 x4 x5
- w = 0 2 6 10 0 0
x4 = 2 - 2 4 1 1 0x5 = -1 4 -2 -3 0 1
Operacao de pivoteamento:
Sai da base: x5 uma vez que (B−1b)2 < 0.
Candidatos a entrar na base: x2, x3.
Quem entra na base, x2, uma vez que determina o teste da razao.
Como efetuar o pivoteamento ?
Alexandre Salles da Cunha Dualidade
Exemplo - implementando o pivoteamento
Devemos ”re-inverter”a matriz, expressando as novas variaveis basicasem termos das novas nao basicas.
Devemos fazer operacoes linha elementares de forma a obter, nascolunas do tableau associadas a uma variavel basica, um vetor dezeros, exceto por uma entrada 1, que ocorre na linha associada aquelavariavel basica.
Da mesma forma, devemos fazer com que a nova linha zero reflita aescolha das variaveis nao basicas, isto e, devemos zerar a entrada docusto reduzido associado a variavel i .
Alexandre Salles da Cunha Dualidade
Quadro inicial
x1 x2 x3 x4 x5
- w = 0 2 6 10 0 0
x4 = 2 - 2 4 1 1 0x5 = -1 4 -2 -3 0 1
Operacoes linha elementares:
L0 ← L0 +c j
|vj |Ll .
para todo k = 1, . . . ,m, k 6= l , Lk ← Lk + mk,lLl , onde mk,l e omultiplicador associado.
Ao final, dividimos a linha l por vi .
Quadro resultante
x1 x2 x3 x4 x5
- w = -3 14 0 1 0 3
x4 = 0 6 0 -5 1 2x2 = 1
2 -2 1 32 0 -1
2
Alexandre Salles da Cunha Dualidade
Quando usar o Dual Simplex
Quando o dual tiver alguma estrutura desejavel (exemplo: problemade fluxo em redes que admite alguma especializacao do Simplex).
Quando uma base dual viavel for prontamente disponıvel.
Isto tipicamente ocorre em situacoes de re-otimizacao onde:◮ Algum elemento de b foi perturbado e a base otima do programa
anterior nao e mais primal viavel e sim dual viavel.
◮ Alguma restricao adicional foi inserida no problema primal. Observeque a introducao desta restricao nao afeta a viabilidade dual.
Alexandre Salles da Cunha Dualidade
Interpretacao geometrica do dual
Continuamos considerando que o problema primal esta na forma padrao eque as linhas de A sao li.
Dado que temos a base B formada pelas linhas AB(1), . . . ,AB(m),temos a solucao basica xB = B−1b.
Com a mesma base, podemos resolver o sistema linear p′B = c ′B .Uma vez que B admite inversa, este sistema tem solucao unicap′ = B−1c ′b.
Esta solucao dual p e tal que o numero de restricoes duais justas, taisque seus vetores de coeficientes sao l.i. e igual a dimensao do espacodual.
Por este motivo, a solucao p e uma solucao basica para o dual.
Alexandre Salles da Cunha Dualidade
Exemplo
min x1 + x2
x1 + 2x2 − x3 = 2
x1 − x4 = 1
x ≥ 0
max 2p1 + p2
p1 + p2 ≤ 1
2p1 ≤ 1
p ≥ 0
Alexandre Salles da Cunha Dualidade
ponto A
x1 x2 x3 x4
- w = 0 1 1 0 0
x3 = -2 -1 -2 1 0x4 = -1 -1 0 0 1
1o. pivot - B
x1 x2 x3 x4
- w = -1 1/2 0 1/2 0
x2 = 1 1/2 1 -1/2 0x4 = -1 -1 0 0 1
2o. pivot - ponto C
x1 x2 x3 x4
- w = -3/2 0 0 1/2 1/2
x2 = 1/2 0 1 -1/2 1/2x1 = 1 1 0 0 -1
Alexandre Salles da Cunha Dualidade
Dualidade e degeneracao
Vamos continuar assumindo que o problema primal encontra-se na formapadrao e que a matriz de coeficientes A possui posto m.
min c ′x
Ax = b
x ≥ 0
Qualquer matriz B que forme uma base leva a uma solucao dualbasica, dada por p′ = cBB−1.As restricoes do programa dual sao p′A ≥ c ′ que podem serdesmembradas em dois conjuntos de restricoes, envolvendo as colunasbasicas e nao basicas:
◮ p′B ≥ cB . Estas m restricoes sao naturalmente satisfeitas de formajusta dado que p′ = c ′
BB−1.◮ p′N ≥ cN . Na base otima, estas restricoes duais, que representam a
condicao de otimalidade associada a custos reduzidos, sao satisfeitas.Entretanto, algumas delas podem ser satisfeitas de forma justa.
Alexandre Salles da Cunha Dualidade
Dualidade e degeneracao
Degeneracao no dual
Sempre que houver uma variavel nao basica j : p′Aj = cj isto ec j = 0, temos degeneracao dual.
Note que o espaco de viabilidade dual esta imerso em Rm e portanto,
temos mais de m restricoes satisfeitas de forma justa no ponto dualdado por p′ = cBB−1.
Alexandre Salles da Cunha Dualidade
Multiplicidade de solucoes primais otimas
Solucoes primais otimas multiplas
Dado um conjunto de variaveis basicas otimas {B(1), . . . ,B(m)},para existirem multiplas solucoes primais otimas e necessario existirpelo menos duas solucoes basicas otimas.
Portanto, e necessario existir uma variavel nao basica j : c j = 0.
A condicao acima implica que o problema dual e degenerado.
Atencao: existir j nao basico tal que c j = 0 nao implica que:
existem multiplicas solucoes primais otimas
existem multiplas bases otimas (podemos ter varias bases associadasa mesma solucao basica, mas apenas uma das bases sendo viavel).
Alexandre Salles da Cunha Dualidade
Multiplicidade de solucoes basicas otimas
Para existirem multiplas solucoes basicas otimas, e necessarioexistirem duas bases otimas.
E necessario que c j = 0 para alguma variavel nao basica j , logo odual e degenerado (mais de m restricoes duais justas).
Se dispomos de duas bases otimas no primal, duas alternativas podemocorrer:
◮ O programa primal possui uma unica solucao basica otima e, nestecaso, esta solucao precisa ser degenerada (caso contrario nao existiriamduas bases otimas)
◮ O programa primal possui pelo menos duas solucoes basicas otimas (oprimal nao precisa ser degenerado, pode ser ou nao degenerado).
Alexandre Salles da Cunha Dualidade
Exemplo
min 3x1 + x2
x1 + x2 − x3 = 2
2x1 − x2 − x4 = 0
x ≥ 0
max 2p1
p1 + 2p2 ≤ 3
p1 − p2 ≤ 1
p ≥ 0Eliminando x3, x4 do primal temos:
Alexandre Salles da Cunha Dualidade
Modificacao no exemplo
O que aconteceria ser o objetivo do programa primal anterior fossealterado para min x1 + x2 ?
Alexandre Salles da Cunha Dualidade
Lema de Farkas
Certificado de inviabilidade
Suponhamos que temos em maos um sistema de restricoes lineares naforma padrao Ax = b, x ≥ 0.
O Lema de Farkas nos fornece um meio, empregando Teoria daDualidade, de apresentar um certificado de inviabilidade de umsistema linear na forma padrao, dado que outro sistema linearassociado possui uma solucao.
Alexandre Salles da Cunha Dualidade
Lema de Farkas
Vamos considerar o sistema na forma padrao Ax = b, x ≥ 0.
Vamos entao admitir que exista um vetor p tal que p′A ≥ 0′ e quep′b < 0.
Observe que diante disto temos p′Ax ≥ 0 e entao p′b ≥ 0.
Assim sendo, se o primeiro sistema linear admite solucao, o segundoprecisa ser inviavel.
Teorema
Lema de Farkas
Seja A uma matriz de dimensoes m × n e b ∈ Rm. Entao exatamente uma
das seguintes afirmativas e verificada:
1 Existe algum x ≥ 0 : Ax = b
2 Existe algum p : p′A ≥ 0′, p′b < 0.
Alexandre Salles da Cunha Dualidade
Lema de Farkas
Prova1 Ja provamos que se existe x ≥ 0 : Ax = b e p′A ≥ 0 entao a segunda
alternativa nao pode acontecer.
2 Vamos considerar nao exista x ≥ 0 : Ax = b e escrever o par primaldual:
max 0′x
Ax = b
x ≥ 0
min p′b
p′A ≥ 0
3 Como o primal e inviavel, seu dual ou e inviavel ou ilimitado.
4 O vetor p = 0 e uma solucao dual viavel. Entao o dual e ilimitado.
5 Assim sendo, existe p viavel (isto e, p : p′A ≥ 0 de forma que p′b < 0.
Alexandre Salles da Cunha Dualidade
Ilustracao geometrica do Lema de Farkas
Vamos considerar as colunas A1, . . . ,An de A. A existencia dex ≥ 0 : Ax = b implica que b =
∑
i Aixi , isto e b pode ser escrito comouma combinacao linear nao negativa das colunas de A.
Alexandre Salles da Cunha Dualidade
Ilustracao geometrica do Lema de Farkas
A inexistencia de x ≥ 0 : Ax = b sugere que deve existir um vetor p e umhiperplano associado {z : p′z = 0} que divide o espaco em duas regioes:em uma encontram-se as combinacoes nao negativas das colunas de A. Naoutra, encontra-se o vetor b. Entao temos p′b < 0 e p′Aj ≥ 0 paraqualquer coluna j .
Alexandre Salles da Cunha Dualidade
Ilustracao geometrica do Lema de Farkas
A ultima observacao leva ao seguinte resultado:
Corolario
Sejam A1, . . . ,An as colunas de A e b um vetor em Rm. Suponha que
qualquer vetor p que satisfaca p′Ai ≥ 0, i = 1, . . . , n tambem satisfacap′b ≥ 0. Entao b pode ser escrito como combinacao linear nao negativadas colunas de A.
Alexandre Salles da Cunha Dualidade
Theorems of the alternative
Teorema
Suponha que o sistema linear Ax ≤ b possua ao menos uma solucao e sejad um escalar qualquer. Entao, as seguintes afirmativas sao equivalentes:
1 Toda solucao viavel para o sistema linear Ax ≤ b satisfaz c ′x ≤ d .
2 Existe algum p ≥ 0 tal que p′A = c ′ e p′b ≤ d .
Alexandre Salles da Cunha Dualidade
Prova
Parte 1: Se hipotese + (1) entao (2).
max c ′x
Ax ≤ b
min p′b
p′A = c
p ≥ 0
Uma vez que existe x : Ax ≤ b satisfazendo c ′x ≤ d , o programaprimal e limitado superiormente.
Logo, seu dual e tambem limitado. Por dualidade forte, a solucaootima do dual tambem possui limitante superior por d .
Alexandre Salles da Cunha Dualidade
Prova
Parte 1: Se hipotese + (2) entao (1).
max c ′x
Ax ≤ b
min p′b
p′A = 0
p ≥ 0
Se algum p satisfaz p′A = c ′, p ≥ 0 e p′b ≤ d entao por dualidadefraca qualquer solucao do sistema linear Ax ≤ b precisa satisfazerc ′x ≤ d .
Alexandre Salles da Cunha Dualidade
Cones e raios extremos
Cones
Um conjunto C ⊂ Rn e um cone se λx ∈ C para todo x ∈ C , λ ≥ 0.
Observe que diante desta definicao 0 ∈ C (escolha qualquer x ∈ C eλ = 0.
Alexandre Salles da Cunha Dualidade
Cones
Um conjunto do tipo P = {x ∈ Rn : Ax ≥ 0} e chamado cone poliedral.
Teorema
Seja C ⊂ Rn um cone poliedral definido pelas restricoes
a′ix ≥ 0, i = 1, . . . ,m. Entao, as seguintes afirmativas sao equivalentes:
1 O vetor 0 e um ponto extremo de C
2 O cone C nao possui linha
3 Existem n vetores ai linearmente independentes dentre aqueles quedefinem C .
Alexandre Salles da Cunha Dualidade
Recession cone
Considere um poliedro nao vazio P = {x ∈ Rn : Ax ≥ b} e um ponto fixo
y ∈ P . O recession cone em y e dado pelo conjunto das direcoes d aolongo das quais podemos nos mover indefinidamente sem sair do conjuntoP .
O recession cone e definido como:
{d ∈ Rn : A(y + λd) ≥ b,∀λ ≥ 0}
Nao e difıcil perceber que o recession cone e dado por
{d ∈ Rn : Ad ≥ 0}
e portanto e um cone poliedral.
O resultado acima mostra que o recession cone e independente doponto que fixamos no poliedro P .
Para o caso onde ∅ 6= P = {x ∈ Rn : Ax = b, x ≥ 0}, o recession
cone e o conjunto dos vetores que resolve Ax = 0, x ≥ 0.
Alexandre Salles da Cunha Dualidade
Recession cone
Alexandre Salles da Cunha Dualidade
Raios extremos
Definicao1 Um elemento nao nulo x do cone poliedral C ⊂ R
n e chamado umraio extremo se existem n − 1 restricoes ativas em x .
2 Um raio extremo extremo do cone de recessao associado a umpoliedro P e tambem um raio extremo de P .
Observacoes:
Dois raios extremos sao equivalentes se um e um multiplo positivo dooutro.
A intersecao de n − 1 restricoes lineares li define uma linha. Assimsendo, a combinacao de n − 1 restricoes li pode produzir no maximodois raios extremos, com direcoes opostas.
Dado que o numero de combinacoes de n − 1 restricoes li e finito, onumero de raios extremos nao equivalentes e finito tambem.
Um conjunto de raios extremos e dito completo se contem umexemplar de cada conjunto de raios extremos equivalentes.
Alexandre Salles da Cunha Dualidade
Raios extremos - ilustracao para n = 2, 3
Alexandre Salles da Cunha Dualidade
Caracterizacao de Programas Lineares Ilimitados
Caso 1: a regiao de viabiliade e um cone:
Teorema
Considere o problema de minimizar c ′x sobre um cone{x ∈ R
n : a′ix ≥ 0, i = 1, . . . ,m}. O custo otimo e −∞ se e somente sec ′d < 0 para algum raio extremo d de C .
Caso 2: poliedro qualquer que contenha um ponto extremo:
Teorema
Considere o problema de minimizar c ′x sujeito ao conjunto de restricoeslineares P = {x ∈ R
n : a′ix ≥ bi , i = 1, . . . ,m}. Assuma que P possuapelo menos um ponto extremo.Entao o custo otimo e −∞ se e somente se c ′d < 0 para algum raioextremo d de P .
Alexandre Salles da Cunha Dualidade
Representacao de poliedros
Teorema
Seja P = {x ∈ Rn : Ax ≥ b} um poliedro nao vazio contendo pelo menos
um ponto extremo. Assuma entao que {x1, . . . , xk} denote o conjunto dospontos extremos de P e que {w1, . . . ,w r} um conjunto completo de raiosextremos de P .Seja entao
Q =
x ∈ Rn : x =
k∑
i=1
λixi +
r∑
j=1
θjwj , θj ≥ 0, λi ≥ 0,
k∑
i=1
λi = 1
.
Entao Q = P .
Alexandre Salles da Cunha Dualidade
Representacao de poliedros - exemplo
P = {x ∈ R2 : x1 − x2 ≥ −2; x1 + x2 ≥ 1; x ≥ 0}
Alexandre Salles da Cunha Dualidade