Uma Introdução à Otimização sob Incerteza Aula 3 · 2014. 7. 28. · 3. Aceitar inadmissibilidade, penalizando desvios α (nível de conﬁabilidade) q/c (custo de déﬁcit/custo

Uma Introdução à Otimização sob IncertezaAula 3

Bernardo Kulnig Pagnoncelli1 e Humberto José Bortolossi2

1Departamento de MatemáticaPontifícia Universidade Católica do Rio de Janeiro

2Departamento de Matemática AplicadaUniversidade Federal Fluminense

III Bienal da SBMUniversidade Federal de Goiás

6 a 10 de novembro de 2006

B. K. Pagnoncelli, H. J. Bortolossi Uma Introdução à Otimização sob Incerteza 1

Quem fez o dever de casa?(Exercício [05] do Capítulo 3)

A solução está valendo um chocolate!


Quem fez o dever de casa?

minimizarx1 + x2 + q1 Eω1 [(ω1 x1 + x2 − 7)−] + q2 Eω2 [(ω2 x1 + x2 − 4)−]

sujeito a x1 ≥ 0, x2 ≥ 0,

é equivalente a

minimizar g(x1, x2) = x1 + x2 + Q(x1, x2)

sujeito a x1 ≥ 0, x2 ≥ 0,

onde

Q(x1, x2) = E[

miny1≥0, y2≥0

{q1y1 + q2y2

∣∣∣∣ ω1 x1 + x2 + y1 ≥ 7ω2 x1 + x2 + y2 ≥ 4

} ].


Otimização estocástica

Espere e Veja (Wait and See)

Aqui e Agora (Here and Now)

1. Eliminar incertezas.

2. Incorporar riscos nas restrições (chance constraints).

a. Níveis de confiabilidade individuais.

b. Nível de confiabilidade conjunto.

3. Aceitar inadmissibilidade penalizando déficits.


O problema da produção

Minimizar do custo de produção c x sob a restrição de que aprodução x atenda à demanda ω:

minimizar f (x) = c xsujeito a x = ω,

x ≥ 0,

A demanda ω é uma variável aleatória contínua não-negativa,com

1. Média: µ = E [ω].

2. Variância: σ2 = E[(ω − E [ω])2

].

3. Função distribuição: F (t) = P (ω ≤ t), com t ∈ R.



Minimizar do custo de produção c x sob a restrição de que aprodução x atenda à demanda ω:

minimizar f (x) = c xsujeito a x = ω,

x ≥ 0,

A demanda ω é uma variável aleatória contínua não-negativa,com

1. Média: µ = E [ω].

2. Variância: σ2 = E[(ω − E [ω])2

].

3. Função distribuição: F (t) = P (ω ≤ t), com t ∈ R.



Abordagem “espere e veja”Se o agente de decisão pode esperar pela realização dademanda ω antes de escolher o valor da produção x , então oproblema é fácil se resolver: x∗(ω) = ω e v∗(ω) = c x∗(ω) = c ω.

Abordagem “aqui e agora”

1. Abolir incertezasSubstituir ω por ω̂ = µ ou ω̂ = µ + ∆ (com ∆ = σ ou ∆ = 2 σ).

Probabilidade de que a demanda seja satisfeita (nível de serviço):

P (ω ≤ µ + ∆) = F (µ + ∆).



Abordagem “espere e veja”Se o agente de decisão pode esperar pela realização dademanda ω antes de escolher o valor da produção x , então oproblema é fácil se resolver: x∗(ω) = ω e v∗(ω) = c x∗(ω) = c ω.


1. Abolir incertezasSubstituir ω por ω̂ = µ ou ω̂ = µ + ∆ (com ∆ = σ ou ∆ = 2 σ).Probabilidade de que a demanda seja satisfeita (nível de serviço):

P (ω ≤ µ + ∆) = F (µ + ∆).




2. Incorporar riscos nas restriçõesConstruir uma restrição probabilística do tipo P (x = ω) ≥ αnão é conveniente.

Para valores adequados de α1 e α2, também não éconveniente construir restrições probabilísticas combinadas:

P (x ≥ ω) ≥ α1 e P (x ≤ ω) ≥ α2.

É preciso estabelecer prioridades: escolha α ∈ (1/2, 1) emodele o problema da mistura como

minx≥0

{cx | P (x ≥ ω) ≥ α} = minx≥0

{cx | x ≥ F−1(α)

}cuja solução é, evidentemente, x∗ = F−1(α).






P (x ≥ ω) ≥ α1 e P (x ≤ ω) ≥ α2.


minx≥0

{cx | P (x ≥ ω) ≥ α} = minx≥0

{cx | x ≥ F−1(α)







P (x ≥ ω) ≥ α1 e P (x ≤ ω) ≥ α2.


minx≥0

{cx | P (x ≥ ω) ≥ α} = minx≥0

{cx | x ≥ F−1(α)





3. Aceitar inadmissibilidade, penalizando desviosPenalizamos superávits e déficits:

Q(x) = E[h · (ω − x)− + q · (ω − x)+

],

onde

z− =

{0, se z ≥ 0,

−z, se z < 0,e z+ =

{z, se z ≥ 0,0, se z < 0,

O problema original fica então assim:

minimizar f (x) = c x + Q(x)

sujeito a x ≥ 0,




3. Aceitar inadmissibilidade, penalizando desviosComo

f ′(x) = c + Q′(x) = c − q + (q + h) F (x),

segue-se que a solução ótima é dada por

x∗ = F−1(

q − cq + h

).

Se h = 0, esta solução coincide com a solução obtida por chanceconstraints se

qc

=1

1− α.




3. Aceitar inadmissibilidade, penalizando desviosComo

f ′(x) = c + Q′(x) = c − q + (q + h) F (x),

segue-se que a solução ótima é dada por

x∗ = F−1(

q − cq + h

).

Se h = 0, esta solução coincide com a solução obtida por chanceconstraints se

qc

=1

1− α.




3. Aceitar inadmissibilidade, penalizando desvios

α(nível de confiabilidade)

q/c(custo de déficit/custo de produção)

0.990 1000.975 400.950 200.900 100.800 50.500 2

Esta tabela é interessante: ela nos dá uma idéia de que valoresescolher para o custo q em termos do nível de confiabilidade α.


Modelos de Recurso


Motivação: programação linear por metas

minx∈X

{cx | Ax = b e Tx ∼ h}

onde

X = {x ∈ Rn | x ≤ x ≤ x} ou X = {x ∈ Rn | 0 ≤ x < +∞},

c ∈ Rn, A é m̃ × n, b ∈ Rem, T é m × n, h ∈ Rm,

cx = c1 · x1 + c2 · x2 + · · ·+ cn · xn =∑n

i=1 ci · xi ,

o símbolo ∼ representa uma das relações =, ≥ e ≤(componente a componente).



minx∈X


Restrições rígidas : Ax = b.

Restrições flexíveis: Tx ∼ h.A idéia é penalizar os desvios de meta z = h − Tx dasrestrições flexíveis através de uma função de penalidade

z 7→ v(z)

que é incorporada à função objetivo do problema deotimização original:

minx∈X

{cx + v(h− Tx) | Ax = b}

=

minx∈X

{cx + v(z) | Ax = b e Tx + z = h} .



minx∈X


Restrições rígidas : Ax = b.Restrições flexíveis: Tx ∼ h.

A idéia é penalizar os desvios de meta z = h − Tx dasrestrições flexíveis através de uma função de penalidade

z 7→ v(z)


minx∈X

{cx + v(h− Tx) | Ax = b}

=

minx∈X

{cx + v(z) | Ax = b e Tx + z = h} .



minx∈X


Restrições rígidas : Ax = b.Restrições flexíveis: Tx ∼ h.A idéia é penalizar os desvios de meta z = h − Tx dasrestrições flexíveis através de uma função de penalidade

z 7→ v(z)


minx∈X

{cx + v(h− Tx) | Ax = b}=

minx∈X

{cx + v(z) | Ax = b e Tx + z = h} .


Como escolher a função de penalidade v?

Notação

T =

t1

t2

...

tm

, h =

h1

h2...

hm

e z =

z1

z2...

zm

.

Tx ∼ h ⇔ z = h− Tx ∼ 0

tix ∼ hi ⇔ zi = hi − tix ∼ 0 ∀i = 1, . . . , m

tix ≤ hi ⇔ zi = hi − tix ≥ 0



Notação

T =

t1

t2

...

tm

, h =

h1

h2...

hm

e z =

z1

z2...

zm

.

Tx ∼ h ⇔ z = h− Tx ∼ 0

tix ∼ hi ⇔ zi = hi − tix ∼ 0 ∀i = 1, . . . , m

tix ≤ hi ⇔ zi = hi − tix ≥ 0



Notação

T =

t1

t2

...

tm

, h =

h1

h2...

hm

e z =

z1

z2...

zm

.

Tx ∼ h ⇔ z = h− Tx ∼ 0

tix ∼ hi ⇔ zi = hi − tix ∼ 0 ∀i = 1, . . . , m

tix ≥ hi ⇔ zi = hi − tix ≤ 0



Notação

T =

t1

t2

...

tm

, h =

h1

h2...

hm

e z =

z1

z2...

zm

.

Tx ∼ h ⇔ z = h− Tx ∼ 0

tix ∼ hi ⇔ zi = hi − tix ∼ 0 ∀i = 1, . . . , m

tix = hi ⇔ zi = hi − tix = 0


Função de penalidade com custos individuais

v(z) =m∑

i=1

vi(zi) =m∑

i=1

(qiz

+i + q

iz−i

)︸︷︷︸

vi (zi )

.

Como escolher qi e qi?

Restrição do tipo tix = hi (isto é, zi = 0):

Penalizamos superávits escolhendo qi > 0 e penalizamosdéficits q

i> 0.

A função vi é convexa como soma de funções convexas.



v(z) =m∑

i=1

vi(zi) =m∑

i=1

(qiz

+i + q

iz−i

)︸︷︷︸

vi (zi )

.


Restrição do tipo tix = hi (isto é, zi = 0):

Penalizamos superávits escolhendo qi > 0 e penalizamosdéficits q

i> 0.

A função vi é convexa como soma de funções convexas.



v(z) =m∑

i=1

vi(zi) =m∑

i=1

(qiz

+i + q

iz−i

)︸︷︷︸

vi (zi )

.


Restrição do tipo tix ≥ hi (isto é, zi ≤ 0):

Penalizamos superávits escolhendo qi > 0 e premiamos déficitsescolhendo q

i< 0

A função vi é convexa se qi+ qi ≥ 0.



v(z) =m∑

i=1

vi(zi) =m∑

i=1

(qiz

+i + q

iz−i

)︸︷︷︸

vi (zi )

.


Restrição do tipo tix ≤ hi (isto é, zi ≥ 0):

Premiamos superávits escolhendo qi < 0 e penalizamos déficitsescolhendo q

i> 0

A função vi é convexa se qi+ qi ≥ 0.


Função de penalidade com custo conjunto

Supondo que todas as restrições são da forma zi ≥ 0:

v(z) = v(z1, z2, . . . , zm) = q0 max{z−1 , z−2 , . . . , z−m}.

A função v é convexa se q0 ≥ 0.


Função de penalidade via ações de recurso

Ingredientes necessários para construir a função de penalidade:

1. Uma estrutura de recurso (q, W).

Aqui q ∈ Rp (vetor de custos) e W é m × p (matriz de recurso).

2. Um conjunto Y de variáveis de recurso.

Y = {y ∈ Rp | y ≤ y ≤ y}ou

Y = {y ∈ Rp | 0 ≤ y ≤ +∞} = Rp+.

A função de recurso v é então definida por:

v(z) = miny∈Y

{qy | Wy ∼ z} .



Escolhendo-se uma estrutura de recurso adequado, é possívelrecuperar a função de penalidade com custos individuais e comcusto conjunto definidas anteriormente!



vi(zi) = qiz+i + q

iz−i .

q =(

qi , qi

)∈ R× R = R2, W =

[+1 −1

]1×2 ,

Y = R+ × R+ = R2+.

vi(zi) = miny∈Y

{qy | Wy = zi}

= miny≥0,y≥0

{[q q

] [yy

] ∣∣∣∣ [+1 −1

] [yy

]=

[zi

]}

= miny≥0,y≥0

{qy + qy | y − y = zi

}= qiz

+i + q

iz−i .



vi(zi) = qiz+i + q

iz−i .

q =(

qi , qi

)∈ R× R = R2, W =

[+1 −1

]1×2 ,

Y = R+ × R+ = R2+.

vi(zi) = miny∈Y

{qy | Wy = zi}

= miny≥0,y≥0

{[q q

] [yy

] ∣∣∣∣ [+1 −1

] [yy

]=

[zi

]}

= miny≥0,y≥0

{qy + qy | y − y = zi

}= qiz

+i + q

iz−i .



vi(zi) = qiz+i + q

iz−i .

q =(

qi , qi

)∈ R× R = R2, W =

[+1 −1

]1×2 ,

Y = R+ × R+ = R2+.

vi(zi) = miny∈Y

{qy | Wy = zi}

= miny≥0,y≥0

{[q q

] [yy

] ∣∣∣∣ [+1 −1

] [yy

]=

[zi

]}

= miny≥0,y≥0

{qy + qy | y − y = zi

}= qiz

+i + q

iz−i .



vi(zi) = qiz+i + q

iz−i .

q =(

qi , qi

)∈ R× R = R2, W =

[+1 −1

]1×2 ,

Y = R+ × R+ = R2+.

vi(zi) = miny∈Y

{qy | Wy = zi}

= miny≥0,y≥0

{[q q

] [yy

] ∣∣∣∣ [+1 −1

] [yy

]=

[zi

]}

= miny≥0,y≥0

{qy + qy | y − y = zi

}= qiz

+i + q

iz−i .



vi(zi) = qiz+i + q

iz−i .

q =(

qi , qi

)∈ R× R = R2, W =

[+1 −1

]1×2 ,

Y = R+ × R+ = R2+.

vi(zi) = miny∈Y

{qy | Wy = zi}

= miny≥0,y≥0

{[q q

] [yy

] ∣∣∣∣ [+1 −1

] [yy

]=

[zi

]}

= miny≥0,y≥0

{qy + qy | y − y = zi

}

= qiz+i + q

iz−i .



vi(zi) = qiz+i + q

iz−i .

q =(

qi , qi

)∈ R× R = R2, W =

[+1 −1

]1×2 ,

Y = R+ × R+ = R2+.

vi(zi) = miny∈Y

{qy | Wy = zi}

= miny≥0,y≥0

{[q q

] [yy

] ∣∣∣∣ [+1 −1

] [yy

]=

[zi

]}

= miny≥0,y≥0

{qy + qy | y − y = zi

}= qiz

+i + q

iz−i .




q =(

q0)∈ R, W =

−1...

−1

m×1

, Y = R+.

v(z) = miny∈Y

{qy | Wy ≤ z}

= miny≥0

[q0

] [y

] ∣∣∣∣∣∣∣ −1

...−1

[y

]≤

z1...

zm

= miny≥0

{qy | y ≥ −z1, . . . , y ≥ −zm}

= q0 max{z−1 , z−2 , . . . , z−m},




q =(

q0)∈ R, W =

−1...

−1

m×1

, Y = R+.

v(z) = miny∈Y

{qy | Wy ≤ z}

= miny≥0

[q0

] [y

] ∣∣∣∣∣∣∣ −1

...−1

[y

]≤

z1...

zm

= miny≥0

{qy | y ≥ −z1, . . . , y ≥ −zm}

= q0 max{z−1 , z−2 , . . . , z−m},




q =(

q0)∈ R, W =

−1...

−1

m×1

, Y = R+.

v(z) = miny∈Y

{qy | Wy ≤ z}

= miny≥0

[q0

] [y

] ∣∣∣∣∣∣∣ −1

...−1

[y

]≤

z1...

zm

= miny≥0

{qy | y ≥ −z1, . . . , y ≥ −zm}

= q0 max{z−1 , z−2 , . . . , z−m},




q =(

q0)∈ R, W =

−1...

−1

m×1

, Y = R+.

v(z) = miny∈Y

{qy | Wy ≤ z}

= miny≥0

[q0

] [y

] ∣∣∣∣∣∣∣ −1

...−1

[y

]≤

z1...

zm

= miny≥0

{qy | y ≥ −z1, . . . , y ≥ −zm}

= q0 max{z−1 , z−2 , . . . , z−m},




q =(

q0)∈ R, W =

−1...

−1

m×1

, Y = R+.

v(z) = miny∈Y

{qy | Wy ≤ z}

= miny≥0

[q0

] [y

] ∣∣∣∣∣∣∣ −1

...−1

[y

]≤

z1...

zm

= miny≥0

{qy | y ≥ −z1, . . . , y ≥ −zm}

= q0 max{z−1 , z−2 , . . . , z−m},




q =(

q0)∈ R, W =

−1...

−1

m×1

, Y = R+.

v(z) = miny∈Y

{qy | Wy ≤ z}

= miny≥0

[q0

] [y

] ∣∣∣∣∣∣∣ −1

...−1

[y

]≤

z1...

zm

= miny≥0

{qy | y ≥ −z1, . . . , y ≥ −zm}

= q0 max{z−1 , z−2 , . . . , z−m},


Modelos de recurso em otimização estocástica

minx∈X

{cx | Ax = b e T(ω)x ∼ h(ω)}

ESTÁGIO 1 ESTÁGIO 2

decisão em x → ocorre ω → ação corretiva y

minx∈X

{cx + E [v(z,ω)] | Ax = b}

onde

v(z,ω) = miny∈Y

{q(ω)y | W(ω)y ∼ h(ω)− T(ω)x} .



minx∈X

{cx | Ax = b e T(ω)x ∼ h(ω)}



minx∈X

{cx + E [v(z,ω)] | Ax = b}

onde

v(z,ω) = miny∈Y

{q(ω)y | W(ω)y ∼ h(ω)− T(ω)x} .



minx∈X

{cx | Ax = b e T(ω)x ∼ h(ω)}



minx∈X

{cx + E [v(z,ω)] | Ax = b}

onde

v(z,ω) = miny∈Y

{q(ω)y | W(ω)y ∼ h(ω)− T(ω)x} .



minx∈X

{cx +Q(x) | Ax = b}

onde

Q(x) = E [v(z,ω)] = E[miny∈Y

{q(ω)y | W(ω)y ∼ h(ω)− T(ω)x}]

︸︷︷︸LP de segundo estágio

.

Perguntas:O problema de segundo estágio sempre está bem definido?A esperança (uma integral!) sempre é finita?Q é uma função simpática?



minx∈X

{cx +Q(x) | Ax = b}

onde

Q(x) = E [v(z,ω)] = E[miny∈Y

{q(ω)y | W(ω)y ∼ h(ω)− T(ω)x}]

︸︷︷︸LP de segundo estágio

.

Perguntas:O problema de segundo estágio sempre está bem definido?A esperança (uma integral!) sempre é finita?Q é uma função simpática?



Perguntas:O problema de segundo estágio sempre está bem definido?

Resposta: Sim, se W é de recurso completo ou de recursosimples, isto é, se

∀z ∈ Rm,∃y≥0 | Wy = z (recurso completo)

ouW =

[+I −I

]. (recurso simples)

A esperança (uma integral!) sempre é finita?

Resposta: Sim, se ω tem segundos momentos finitos.

Q é uma função simpática?

Resposta: Sim! Q é convexa e diferenciável de ω temdistribuição contínua.



Perguntas:O problema de segundo estágio sempre está bem definido?Resposta: Sim, se W é de recurso completo ou de recursosimples, isto é, se


ouW =

[+I −I


A esperança (uma integral!) sempre é finita?

Resposta: Sim, se ω tem segundos momentos finitos.







ouW =

[+I −I


A esperança (uma integral!) sempre é finita?Resposta: Sim, se ω tem segundos momentos finitos.







ouW =

[+I −I


A esperança (uma integral!) sempre é finita?Resposta: Sim, se ω tem segundos momentos finitos.

Q é uma função simpática?Resposta: Sim! Q é convexa e diferenciável de ω temdistribuição contínua.


A forma extensa

minx∈X

{cx + E

[miny∈Y

{q(ω)y | W(ω)y = h(ω)− T(ω)x}] ∣∣∣∣ Ax = b

}

minimizarx∈X

y1,y2,...,yS∈Y

cx + p1q1y1 + p2q2y2 + · · ·+ pSqSyS

sujeito a Ax = b,

T1x + Wy1 ∼ h1,

T1x + Wy2 ∼ h2,...

. . ....

...TSx + WyS ∼ hS,

ps = P(ω = ωS)

, qs = q(ωs), ys = y(ωs), Ts = T(ωs), hs = h(ωs),W(ω) = W (recurso fixo).


A forma extensa

minx∈X

{cx + E

[miny∈Y

{q(ω)y | W(ω)y = h(ω)− T(ω)x}] ∣∣∣∣ Ax = b

}

minimizarx∈X

y1,y2,...,yS∈Y

cx + p1q1y1 + p2q2y2 + · · ·+ pSqSyS

sujeito a Ax = b,

T1x + Wy1 ∼ h1,

T1x + Wy2 ∼ h2,...

. . ....

...TSx + WyS ∼ hS,

ps = P(ω = ωS)

, qs = q(ωs), ys = y(ωs), Ts = T(ωs), hs = h(ωs),W(ω) = W (recurso fixo).


Documents

Uma Introdução à Otimização sob Incerteza Aula 3 · 2014. 7. 28. · 3. Aceitar inadmissibilidade, penalizando desvios α (nível de conﬁabilidade) q/c (custo de déﬁcit/custo