Programação Linear/Inteira - Aula 4 · do problema é Ax = b - y. Thiago Queiroz (IMTec) Aula 4 Aula 4 3 / 29. Relaxação Lagrangeana Considere por i a penalização (ou o custo)

Unidade de Matemática e Tecnologia - RC/UFG

Programação Linear/Inteira - Aula 4

Prof. Thiago Alves de Queiroz

Aula 4

Thiago Queiroz (IMTec) Aula 4 Aula 4 1 / 29

Dualidade

Os parâmetros de entrada são dados de acordo com o problema:estoque disponível de produtos, capacidade das máquinas,demanda dos itens, etc.;Embora seja conveniente um decisor examinar como as possíveisvariações nos dados interferem na solução do problema;Por exemplo: Se o estoque de uma matéria-prima aumentasse,como o custo de produção se alteraria? (poderia gerar políticasde compras de matérias-primas);Essas observações correspondem a analisar o modelo sob outroponto de vista;Introduzem um novo modelo de otimização linear, chamadoproblema dual;O modelo original é chamado de problema primal.


Relaxação Lagrangeana

Considere um problema de otimização linear na forma padrão,chamado de problema primal:

Minimizar z = cTx

sujeito a :

{Ax = bx ≥ 0.

(1)

Em que A é uma matriz m × n e z = f(x);Se considerar que o vetor de recursos b é passível deperturbações, então a restrição b - Ax = 0 não precisa sersatisfeita exatamente;Pode-se analisar tal restrição como um vetor y = b - Ax;O vetor y é uma perturbação no vetor b de modo que a soluçãodo problema é Ax = b - y.



Considere por λi a penalização (ou o custo) unitário de perturbaro recurso i ;Então, λiyi é o custo adicional de perturbar o recurso i em yiunidades;Isto conduz a um novo problema, chamado problemalagrangeano, isto é, para cada λ = (λ1, λ2, . . . , λm), resolva:

Minimizar z + λ1y1 + λ2y2 + . . .+ λmymsujeito a :

{x ≥ 0. (2)

Em que y = b - Ax;Definição 10. A função objetivo do problema lagrangeano échamada função lagrangeana, sendo dada por:L(x , λ) = z + λ1y1 + λ2y2 + . . .+ λmym, com y = b - Ax.



Note que: L(x , λ) == cT x + λT y= cT x + λT (b − Ax)= (cT − λT A)x + λT b.Seja A = [a1,a2, . . . ,an], em que aj é a j-ésima coluna da matriz Ae c=(c1, c2, . . . , cn), então:(cT − λT A) = (c1 − λT a1, c2 − λT a2, . . . , cn − λT an);A função lagrangeana pode ser escrita como:L(x1, x2, . . . , xn, λ) =(c1 − λT a1)x1 + (c2 − λT a2)x2 + . . .+ (cn − λT an)xn + λT b;A função dual é definida por:g(λ) = minx≥0{L(x1, x2, . . . , xn, λ)}= minx≥0{(c1−λT a1)x1+(c2−λT a2)x2+. . .+(cn−λT an)xn+λ

T b}= minx1≥0{(c1 − λT a1)x1}+minx2≥0{(c2 − λT a2)x2}+ . . .+minxn≥0{(cn − λT an)xn}+ λT b


Problema Dual

A decomposição anterior da soma em n subproblemas menores éválidas, pois as variáveis x1, x2, . . . , xn são independentes entre si;Definindo R ⊇ S:R = {x ∈ Rn, tal que x ≥ 0},S = {x ∈ Rn, tal que Ax = b, x ≥ 0}.Segue, então, pela definição de função dual que:g(λ) = minx≥0{cT x + λT (b − Ax)}≤ min{Ax=b,x≥0}{cT x + λT (b − Ax)} (o termo b - Ax se anula)= min{cT x , sujeito a: Ax = b, x ≥ 0} (problema primal)≤ f(x), para todo x tal que Ax = b, x ≥ 0.Note que Minimizar{f (x), x ∈ R} ≤ Minimizar{f (x), x ∈ S}, emque R ⊇ S.


Problema Dual

Propriedade 5. Para todo λ ∈ Rm e para todo x tal que Ax = b, x≥ 0, então g(λ) ≤ f (x);Ou seja, a função dual g(λ) fornece um limitante inferior para afunção objetivo primal f(x), para todo x factível;Isto sugere procurar o λ que ofereça o maior dos limitantesinferiores;Definição 11. O maior limitante inferior para f(x), obtido pelafunção dual, define o problema dual lagrangeano, ou apenas,problema dual, dado por:

Maximizar g(λ)sujeito a :

{λ ∈ Rm.

(3)

As variáveis (λ1, λ2, . . . , λm) são chamadas variáveis duais;


Problema Dual

Se existe i tal que ci − λT ai < 0, então g(λ) = −∞, que é umlimitante inferior muito simples (e ruim);Para limitantes inferiores finitos, escolhe-se λ de modo queci − λT ai ≥ 0, i = 1,2, . . . ,n;Neste caso, minxi≥0(ci − λT ai) = 0, i = 1,2, . . . ,n, pois a soluçãodo problema lagrangeano é dada por:

I Se ci − λT ai > 0, então xi = 0 e (ci − λT ai)xi = 0;I Se ci − λT ai = 0, então xi ≥ 0 e (ci − λT ai)xi = 0.

Portanto, escolhe-se λ tal que ci − λT ai ≥ 0, i = 1,2, . . . ,n, entãog(λ) = λT b;As n desigualdades podem ser escritas como:λT a1 ≤ c1, λ

T a2 ≤ c2, . . . , λT an ≤ cn

⇔ (λT a1 λT a2 . . . λT an) ≤ (c1 c2 . . . cn)

⇔ λT A ≤ cT .


Problema Dual

Tomando-se a transposta de ambos os lados da últimadesigualdade, segue-se que:ATλ ≤ c (note que (AB)T = BT AT );Portanto, escolhem-se as variáveis duais tais que ATλ ≤ c,resultando na função dual g(λ) = λT b = bTλ;Logo, reescreve-se o problema dual para ficar mais justo, como:Propriedade 6. Considere o seguinte problema primal:

Minimizar z = cTx

sujeito a :

{Ax = bx ≥ 0.

(4)

então, o problema dual é dado pelo seguinte problema deotimização linear:

Maximizar g(λ) = bTλsujeito a :

{ATλ ≤ c. (5)


Problema DualDefinição 12. O conjunto de restrições ATλ ≤ c é chamado derestrições duais, e todo vetor λ que satisfaça as restrições duais échamado de solução dual factível.Propriedade 7. O dual do problema dual é o problema primal.Em linhas gerais, o problema dual é construído da seguinteforma, dado que o primal está na forma padrão:

I O problema dual é de Maximização;I O número de variáveis duais é igual ao número de restrições do

primal;I O número de restrições duais é igual ao número de variáveis x do

primal;I Os coeficientes da função objetivo dual são os coeficientes do

vetor de recursos b do primal;I A matriz de coeficientes das restrições duais é a transposta da

matriz (A) dos coeficientes do primal;I As restrições duais (sinal da desigualdade) depende do domínio

das variáveis no primal;I O vetor de recursos do dual é formado pelo vetor de custos c do

primal.Thiago Queiroz (IMTec) Aula 4 Aula 4 10 / 29

Problema Dual

Tabela: Regras para a construção do dual.

Primal (dual) Dual (primal)Minimização Maximização

Vetor de recursos b Vetor de custos cVetor de custos c Vetor de recursos b

Restrição Variável= Livre≤ ≤≥ ≥

Variável Restrição≥ ≤≤ ≥

Livre =


Exemplos Duais

Exemplo. Escreva o dual do seguinte problema:

Minimizar z = x1 + 2x2

sujeito a :

−2x1 + x2 ≤ 33x1 + 4x2 ≤ 5x1 − x2 ≤ 2x1 ≥ 0, x2 ≥ 0.

(6)

O problema dual resultante é (observe a tabela com as regras):

Maximizar g(λ) = 3λ1 + 5λ2 + 2λ3

sujeito a :

−2λ1 + 3λ2 + λ3 ≤ 1λ1 + 4λ2 − λ3 ≤ 2λ1 ≤ 0, λ2 ≤ 0, λ3 ≤ 0.

(7)


Exemplos Duais


Maximizar z = x1 + 2x2

sujeito a :

−2x1 + x2 ≤ 33x1 + 4x2 ≤ 5x1 − x2 ≤ 2x1 ≥ 0, x2 ≥ 0.

(8)


Minimizar g(λ) = 3λ1 + 5λ2 + 2λ3

sujeito a :

−2λ1 + 3λ2 + λ3 ≥ 1λ1 + 4λ2 − λ3 ≥ 2λ1 ≥ 0, λ2 ≥ 0, λ3 ≥ 0.

(9)


Exemplos Duais


Maximizar z = x1 + 2x2

sujeito a :

−2x1 + x2 + x3 ≥ 33x1 + 4x2 ≤ 5x1 ≥ 0, x2 ∈ R, x3 ≤ 0.

(10)


Minimizar g(λ) = 3λ1 + 5λ2

sujeito a :

−2λ1 + 3λ2 ≥ 1λ1 + 4λ2 = 2λ1 ≤ 0λ1 ≤ 0, λ2 ≥ 0.

(11)


Relações Primais-Duais

Os problemas primal e dual estão relacionados e, assim, épossível obter a solução de um a partir da solução do outro;Considere o conjunto de soluções factíveis do primal por:P = {x ∈ Rn, tal que Ax = b, x ≥ 0};Considere o conjunto de solução factíveis do dual por:D = {λ ∈ Rm , tal que ATλ ≤ c };Seque que a Propriedade 5 pode ser escrita como:g(λ) ≤ f (x), ∀λ ∈ D, ∀x ∈ P;Propriedade 8. Suponha que P 6= ∅ (existe solução primal). Oproblema primal não tem solução ótima se e somente se D = ∅.De outra forma, no caso de minimização do primal, f(x)→ −∞ see somente se não existir solução factível dual (D = ∅).Note que pela Propriedade 5, se existe λ ∈ D, então g(λ) é umlimitante inferior para f(x), impedindo que f(x)→ −∞;



Exemplo. Considere o seguinte par de problemas primal-dual:

(Primal) Maximizar z = x1 + x2

sujeito a :

−x1 + x2 ≤ 1x1 − 2x2 ≤ 1x1 ≥ 0, x2 ≥ 0.

(12)

(Dual) Minimizar g(λ) = λ1 + λ2

sujeito a :

−λ1 + λ2 ≥ 1λ1 − 2λ2 ≥ 1λ1 ≥ 0, λ2 ≥ 0.

(13)

A resolução gráfica mostra que o primal não tem solução ótima (asolução é ilimitada) e o dual é infactível, isto é, D = ∅. Veja nafigura seguinte.



Representação da região factível do par de problemas anteriores;

Figura: (a) Primal ilimitado, (b) Dual infactível.



Propriedade 9. Suponha que D 6= ∅ (existe solução dual). Oproblema dual não tem solução ótima se e somente se P = ∅. Istoé, g(λ)→∞ se e somente se não existir solução factível primal.Exemplo. Considere o problema:

(Primal) Minimizar z = −x1

sujeito a :

{0x1 = 1x1 ≥ 0.

(14)

(Dual) Maximizar g(λ) = λ1sujeito a :

{0λ1 ≤ −1. (15)

Ambos os problemas, primal e dual, são infactíveis;Das Propriedades 8 e 9 concluí-se que: se um dos problemas forinfactível, então o outro não tem solução ótima (é ilimitada ou éinfactível).



Propriedade 10. O problema primal tem solução ótima se esomente se o dual tiver solução ótima.Note que, se o problema primal tem solução ótima, então P 6= ∅,f(x) > −∞;Da Propriedade 8, segue que D 6= ∅, pois se D = ∅, então f(x)→ −∞, que é um absurdo já que f(x) > −∞;Assim, como P 6= ∅ e D 6= ∅, da Propriedade 9, segue queg(λ) <∞, ou seja, o problema dual não é infactível, nem ilimitado,de modo que há apenas a solução ótima como possibilidade;Propriedade 11. Sejam x∗ ∈ P e λ∗ ∈ D. Se f (x∗) = g(λ∗), entãox∗ é solução ótima primal e λ∗ é solução ótima dual.Note que, pela Propriedade 5, g(λ) ≤ f (x), para todo λ ∈ D epara todo x ∈ P, pois é impossível diminuir f(x) abaixo de f(x∗). Sefosse possível, então existiria x ∈ P tal que f(x) < f (x∗) = g(λ∗).



Analisando um pouco mais a condição de otimalidade daPropriedade 11. Sejam x ∈ P e λ ∈ D e suponha quef (x) = g(λ), isto é, cT x = λT b;Substituindo Ax = b, segue que cT x = λT Ax , o que resulta em:(cT − λT A)x = 0;Note que cT x = λT Ax ↔ cT x − λT Ax = 0;O vetor (cT − λT A) é o vetor das variáveis de folga do problemadual. Veja:

ATλ ≤ c ↔

aT

1 λ ≤ c1aT

2 λ ≤ c2...

aTn λ ≤ cn

↔

aT1 λ+ µ1 = c1

aT2 λ+ µ2 = c2

...aT

n λ+ µn = cn

, com

µ1 ≥ 0, µ2 ≥ 0, . . . , µn ≥ 0.



Como aTj λ = λT aj e

cT − λT A = (c1 − λT a1 c2 − λT a2 . . . cn − λT an),segue que:(cT − λT A)x = 0↔ (c1 − λT a1)x1 + (c2 − λT a2)x2 + . . .+ (cn − λT an)xn = 0↔ µ1x1 + µ2x2 + . . .+ µnxn = 0, em que µj = cj − λT aj ≥ 0.Como xj ≥ 0, j = 1,2, . . . ,n, cada uma das parcelas da somaacima é não-negativa, do que se conclui que todas são nulas,pois (cT − λT A)x = 0, ou seja:µ1x1 = 0, µ2x2 = 0, . . . , µnxn = 0Propriedade 12. (folgas complementares) As soluções x ∈ Rn eλ ∈ Rm são ótimas, primal e dual respectivamente, se e somentese:Ax = b, x ≥ 0 (x é factível primal)ATλ+ µ = c, λ ≥ 0 (λ é factível dual)µjxj = 0, j = 1,2, . . . ,n (folgas complementares).



A Propriedade 12 permite obter a solução ótima de um dosproblemas (primal ou dual) quando a solução ótima do outro éconhecida;Além disso, que a resolução de um problema de otimização linearpode ser obtida pela resolução de um sistema de equaçõesnão-lineares (as folgas complementares são não-lineares);Exemplo. Dado o problema abaixo (primal) e sua solução,obtenha a solução do dual. Verifique se são soluções ótimas.

(Primal) Minimizar z = x1 + x2 + x3

sujeito a :

45 x1 +

25 x2 = 108

35 x2 +

910 x3 = 120

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.

(16)

Cuja solução factível primal é: x1 = 35, x2 = 200, x3 = 0.



1. Escreva o problema dual associado ao primal, qual seja:

(Dual) Maximizar g(λ) = 108λ1 + 120λ2

sujeito a :

45λ1 + 0λ2 ≤ 125λ1 +

35λ2 ≤ 1

0λ1 +9

10λ2 ≤ 1λ1 ∈ R, λ2 ∈ R.

(17)

2. Adicione as variáveis de folga para deixar o problema dual naforma padrão, resultando em:

(Dual) Maximizar g(λ) = 108λ1 + 120λ2

sujeito a :

45λ1 + 0λ2 + µ1 = 125λ1 +

35λ2 + µ2 = 1

0λ1 +9

10λ2 + µ3 = 1λ1 ∈ R, λ2 ∈ R.

(18)

Em que: µ1, µ2, µ3 ≥ 0 são as variáveis de folga do dual.



3. Busque uma solução que atenda as folgas complementaresµ1x1 = 0, µ2x2 = 0 e µ3x3 = 0;Note que a solução do primal foi dada, ou seja,x1 = 35, x2 = 200, x3 = 0. Então, para atender as folgascomplementares, tem-se: µ1 = 0, µ2 = 0 e µ3 ≥ 0;Isto faz com que as restrições do dual associada as folgas nulassejam satisfeitas com igualdade:45λ1 + 0λ2 = 1, pois µ1 = 0,25λ1 +

35λ2 = 1, pois µ2 = 0;

Resolvendo o sistema de equações lineares acima, obtém-se:λ1 = 5

4 e λ2 = 56 ;



Resta verificar se tal solução dual satisfaz à terceira restrição dodual:9

10λ2 ≥ 1, é satisfeita pois λ2 = 56 .

Isto permite obter o valor de µ3, já que:9

10λ2 + µ3 = 1→ 910 ×

56 + µ3 = 1→ µ3 = 1

4 .4. Caso as soluções primais e duais sejam factíveis e satisfaçamas folgas complementares, conclui-se que elas são soluçõesótimas primal e dual, respectivamente.Veja que a solução do dual é: λ1 = 5

4 e λ2 = 56 , que juntamente

com a solução do primal: x1 = 35, x2 = 200, x3 = 0, satisfazem àsfolgas complementares, dado que µ1 = 0, µ2 = 0, µ3 = 1

4 ;Então, tais soluções são ótimas e o valor da função objetivo é:z = 35 + 200 = 235 = g(λ) = 108× 5

4 + 120× 56 = 235;



Substituindo µT = cT − λT A nas folgas complementares µT x = 0,obtém-se (cT − λT A)x = 0 ou cT x = λT Ax ;Note que Ax = b, para x factível fornece f (x) = cT x = λT b= g(λ);Propriedade 13. (dualidade forte) As soluções x∗ ∈ P e λ∗ ∈ Dsão ótimas, primal e dual respectivamente, se e somente sef (x∗) = g(λ∗).Propriedade 14. O vetor multiplicador simplex na solução ótimaprimal λT = cT

B B−1 é uma solução ótima dual.Note que o vetor multiplicador simplex é uma solução dual factívele os objetivos primal e dual:g(λ) = λT b = cT

B B−1b = cTB xB + cT

NxN = f (x);Ou seja, os objetivos são iguais;Lembre que uma solução básica primal é: xB = B−1b e xN = 0.



A condição de otimalidade do primal garante que o vetormultiplicador seja uma solução dual factível. Pela definiçãoλT = cT

B B−1, tem-se que:λT B = cT

B ↔ λT aj = ci para todo i básico;Isto é, as restrições duais associadas às variáveis básicas sãosatisfeitas com igualdade. Então, as folgas complementaresassociadas a tais restrições duais são nulas;Considerando as restrições de otimalidade satisfeitas, segue queos custos relativos:cj − λT aj ≥ 0 para todo j não-básico;Portanto, λT aj ≤ cj para todo j não-básico, ou seja, todas asrestrições duais associadas às variáveis não básicas (xN = 0)também são satisfeitas;Assim, todas as restrições duais são satisfeitas (as folgascomplementares também) de forma que λT = cT

B B−1 é umasolução factível dual. De fato, ela é ótima.



Exemplo. Seja o problema abaixo:

(Primal) Minimizar z = x1 + x2 + x3

sujeito a :

45 x1 +

25 x2 = 108

35 x2 +

910 x3 = 120

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.

(19)

Cuja solução ótima é: x1 = 35, x2 = 200, x3 = 0, a qual é básica:

xB =

(x1x2

)=(

108200

)e xN = (x3) = (0);

A inversa da matriz básica associada é: B−1 =

[54 −5

60 5

3

];



Para obter a solução ótima do dual, basta calcular o vetormultiplicador simplex, conforme garante a Propriedade 14, isto é:λT = cT

B B−1.Calculando o vetor multiplicado simplex:

λT = cTB B−1 = (1 1)

[54 −5

60 5

3

]= (5

456);

Portanto, a solução ótima do dual é: λ1 = 54 e λ2 = 5

6 .


Documents

Programação Linear/Inteira - Aula 4 · do problema é Ax = b - y. Thiago Queiroz (IMTec) Aula 4 Aula 4 3 / 29. Relaxação Lagrangeana Considere por i a penalização (ou o custo)