OTIMIZACAO ESTOCASTICA - Bernardo PAGNONCELLI e Humberto - III-bienal-sbm-texto

8/18/2019 OTIMIZACAO ESTOCASTICA - Bernardo PAGNONCELLI e Humberto - III-bienal-sbm-texto

1/97

Uma Introdução à Otimização sob Incerteza

Humberto José Bortolossi

Departamento de Matemática Aplicada

Universidade FederalFluminense

Bernardo Kulnig Pagnoncelli

Departamento de Matemática

Pontif́ıcia Universidade Católicado Rio de Janeiro

III Bienal da Sociedade Brasileira de Matemática

Universidade Federal de Goiás

6 a 10 de novembro de 2006


2/97

Sumário

Prefácio iii

1 O Problema do Fazendeiro 1

1.1 Representando cenários . . . . . . . . . . . . . . . . . . . . . 4

1.2 EVPI e VSS . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2 O Problema do Jornaleiro 10

2.1 Resolução do Problema . . . . . . . . . . . . . . . . . . . . . 11

2.2 Um exemplo numérico . . . . . . . . . . . . . . . . . . . . . 13

2.3 Outras interpretações para o problema . . . . . . . . . . . . 15

3 Programação Linear com Coeficientes Aleatórios 17

3.1 O problema da mistura . . . . . . . . . . . . . . . . . . . . . 18

3.2 O problema da produção . . . . . . . . . . . . . . . . . . . . 27

4 Modelos de Recurso 32

4.1 Motivação: programação linear por metas . . . . . . . . . . 32

4.2 Modelos de recurso em otimização estocástica . . . . . . . . 36

4.3 Admissibilidade . . . . . . . . . . . . . . . . . . . . . . . . . 38

4.4 Propriedades das funções de recurso . . . . . . . . . . . . . . 40

4.5 Casos especiais: recurso completo e simples . . . . . . . . . . 41


3/97

4.6 Mı́nimos e esperanças . . . . . . . . . . . . . . . . . . . . . . 42

4.7 Cotas para o valor ótimo . . . . . . . . . . . . . . . . . . . . 42

4.8 O caso Ω finito . . . . . . . . . . . . . . . . . . . . . . . . . 45

5 O método L-shaped 47

5.1 A decomposição de Benders . . . . . . . . . . . . . . . . . . 47

5.2 O algoritmo de Benders . . . . . . . . . . . . . . . . . . . . 50

5.3 Um exemplo completo . . . . . . . . . . . . . . . . . . . . . 515.4 Decomposição de Benders em otimização estocástica: o mé-

todo L-shaped . . . . . . . . . . . . . . . . . . . . . . . . . . 53

6 Métodos Amostrais 56

6.1 Aproximação pela média amostral . . . . . . . . . . . . . . . 56

6.2 A decomposição estocástica . . . . . . . . . . . . . . . . . . 61

A Probabilidade 69

B Estat́ıstica 77

C Convexidade 81

D Programação Linear 86

Bibliografia 91


4/97

Prefácio

A maioria dos problemas da vida real trazem, em si, incertezas: elas sãoinerentes em virtualmente todos os sistemas relacionados com atuária, eco-nomia, meteorologia, demografia, ecologia, etc. Nos dias de hoje, problemasenvolvendo interações entre homem, natureza e tecnologia estão sujeitos a

mudanças rápidas, o que aumenta a incerteza. Cada nova revolução tec-nológica traz novos desafios para o conhecimento estabelecido até então.Mesmo no contexto determińıstico, existem sistemas que são tão complexos,que eles não permitem uma medida precisa de seus parâmetros.

A área de otimizaç˜ ao estoc´ astica (também conhecida como otimizaç˜ ao sobincerteza ) estuda modelos e métodos para abordar tais situações: elas incor-poram incertezas na modelagem através da inclusão de variáveis aleatóriascom distribuição de probabilidade conhecida. O objetivo é, então, encon-

trar soluções que sejam admisśıveis para todas as posśıveis realizações dasvariáveis aleatórias que são parte da modelagem.

A inclusão de variáveis aleatórias em um modelo de otimização cria muitasdificuldades: O que é uma solução admisśıvel? O que é uma solução ótima?Como resolver estes problemas? Apresentaremos neste texto algumas dasabordagens que procuram responder (dar um sentido) a estas perguntas.Nos concentraremos em uma classe muito importante de problemas de oti-mização estocástica: os chamados modelos de recurso em dois est´ agios . Emlinhas gerais, estes modelos permitem que se faça uma escolha inicial (ditade primeiro estágio) antes de se conhecer o valor dos parâmetros incertos.Após o conhecimento dos valores dos mesmos, o agente de decisão faz novasescolhas (ditas de segundo estágio) que visam corrigir posśıveis efeitos nega-tivos gerados pela decisão de primeiro estágio (por este motivo, as decisõesde segundo estágio também são chamadas de aç˜ oes corretivas ).

A solução obtida através da resolução de um problema de otimização

estocástica é balanceada para todos os posśıveis cen´ arios , ou seja, é a me-lhor solução que leva em contas todos os posśıveis valores que os parâmetrosaleatórios podem assumir. Não fixamos simplesmente cada cenário e resolve-


5/97

iv Prefácio

mos vários problemas de otimização: estamos incorporando todos os cenários

em um mesmo de problema e nos perguntando qual é a melhor decisão a setomar levando em conta todas as situações que podem ocorrer.

É um fato geral que muitas aplicações de otimização estocástica dão ori-gem a problemas de otimização determińıstica de grande porte, que sãointratáveis mesmo para os computadores mais modernos. Uma área de pes-quisa bastante ativa atualmente está voltada para o desenvolvimento de al-goritmos que aproximam as soluções de problemas de grande porte. Nestetexto apresentaremos dois deles, a aproximaç˜ ao pela média amostral e a

decomposiç˜ ao estoc´ astica .Do ponto de vista pedagógico, a área de otimização estocástica é muito

rica, por usar conceitos e resultados de programação linear, probabilidade eestat́ıstica.

Agradecimentos

Este texto é fruto de um ciclo de seminários realizados na Pontif́ıcia Uni-versidade Católica do Rio de Janeiro desde o segundo semestre de 2005, comoparte do programa de pós-graduação em atuária. Além de vários artigos daárea, os livros [03, 09, 10, 13, 14, 17] foram muito inspiradores!

Gostaŕıamos de agradecer a todos que participaram dos seminários: DerekHacon, Jessica Kubrusly, Marina Sequeiros Dias, Débora Freire Mondaini,Eduardo Teles da Silva, Niko A. Iliadis, Raphael M. Chabar e, em especial,ao professor Carlos Tomei, organizador dos seminários e co-autor de direitodeste texto!

Humberto José Bortolossi([email protected])

Departamento de Matemática Aplicada

Universidade Federal

Fluminense

Bernardo Kulnig Pagnoncelli([email protected])

Departamento de Matemática

Pontif́ıcia Universidade Católica

do Rio de Janeiro


6/97

Caṕıtulo 1

O Problema do Fazendeiro

Vamos começar nosso estudo de otimização estocástica pelo problema do fazendeiro [03]. João é um fazendeiro que possui de 500 hectares (ha) deterra dispońıveis para cultivo. Aliás, lembre-se que 500 ha equivalem a5 000 000 m2. Ele é especialista em três cultivos: trigo, milho e cana-de-açúcar. Durante o inverno, ele tem que decidir quanto de terra será dedicadaa cada uma das três culturas. A Figura 1.1 mostra duas possibilidades de

divisão.

milho cana-de-açúcar

trigo milho

cana-de-açúcar

trigo

Figura 1.1: Duas divisões posśıveis da terra.

Além do tamanho de sua propriedade, João possui outras restrições aserem consideradas. Ele também é proprietário de gado, que precisa seralimentado. Seu gado precisa de pelo menos 200 toneladas (T) de trigo e240 T de milho para a ração. Além do trigo e milho produzidos em suas

terras, ele pode comprar esses produtos de outros produtores, no mercadolocal. Seu excesso de produção pode ser vendido para atacadistas, porém opreço é bem menor devido a margem de lucro destes comerciantes.


7/97

2 III Bienal da Sociedade Brasileira de Matemática

A cana-de-açúcar é um cultivo exclusivamente para dar lucro: toda sua

produção é vendida para atacadistas a 36 reais por tonelada (R$/T). Noentanto, o governo impõe uma cota de produção de 6 000 T: qualquer quan-tidade produzida acima desse valor deve ser vendida por apenas 10R$/T.

Baseado em informações de anos anteriores, João sabe que o rendimentomédio de suas lavouras é 2.5, 3.0 e 20 toneladas por hectare (T/ha). Alémdisso, existe um custo de produção espećıfico de cada lavoura, que é dadoem R$/ha. Os dados completos do modelo estão representados na Tabela1.1 a seguir:

Trigo Milho Cana-de-açúcarRendimento (T/ha) 2.5 3.0 20

Custo de produção ($/ha) 150 230 260Preço de venda ($/T) 170 150 36(≤ 6 000 T)

10(> 6 000 T)Preço de compra ($/T) 238 210 –

Requerimento mı́nimo para o gado (T) 200 240 –Total de terra disponı́vel: 500 ha

Tabela 1.1: Dados para o problema do fazendeiro.

Para ajudar João a decidir sobre como dividir suas terras de forma amaximizar seus lucros, vamos formular um problema de otimização linearque descreve essa situação. Defina

x1 = hectares dedicados ao trigo,

x2 = hectares dedicados ao milho,

x3 = hectares dedicados a cana-de-açúcar,

w1 = toneladas de trigo vendidas,y1 = toneladas de trigo compradas,

w2 = toneladas de milho vendidas,

y2 = toneladas de milho compradas,

w3 = toneladas de cana-de-açúcar e

w4 = toneladas de cana-de-açúcar.

Queremos modelar essa situação como um problema de minimização aoinvés de um de maximização, por razões que ficaram claras um pouco maisà frente no texto. Logicamente, o valor da função objetivo deve ser interpre-


8/97

O Problema do Fazendeiro 3

tado com o sinal oposto. Dessa forma o problema fica

minimizar 150 x1 + 230 x2 + 260 x3+238 y1 − 170 w1 + 210 y2 − 150 w2 − 36 w3 − 10 w4

sujeito a x1 + x2 + x3 ≤ 500,2.5 x1 + y1 − w1 ≥ 200,

3 x2 + y2 − w2 ≥ 240,w3 + w4 ≤ 20 x3,

w3 ≤ 6 000,x1, x2, x3, y1, y2, w1, w2, w3, w4

≥0.

(1.1)

Esse é um problema de otimização linear e existem diversos programasdispońıveis na internet que resolvem esse problema rapidamente. No entanto,é necessário escrevê-lo em uma linguagem especial, chamada AMPL ([08]).Essa linguagem é própria para problemas de otimização e é muito simplesde aprender, pois seu código é muito semelhante a maneira como escrevemosum problema de otimização. Mais detalhes em http://www.ampl.com/. O

mais popular resolvedor de problemas de otimização é o CPLEX, que apesarde não ser gratuito possui uma versão para estudantes gratuita, dispońıvelem http://www.ampl.com/DOWNLOADS/cplex80.html. A solução do pro-blema está descrita na Tabela 1.2.

Trigo Milho Cana-de-açúcar

Área (ha) 120 80 300Total produzido 300 240 6 000

Total vendido 100 – 6 000Total comprado – – –Lucro total: R $118 600

Tabela 1.2: Solução do problema.

Pronto, o problema de João está resolvido: basta dividir as terras deacordo com a Tabela 1.2 para que ele maximize seus lucros. No entanto,João fica desconfiado com a solução. E se sua experîencia em relação aorendimento médio das culturas não for tão precisa quanto ele pensa? E se

o ano em questão tiver um clima particularmente desfavorável e sua lavourarender menos do que o esperado? Será que a mesma divisão de terras é amelhor posśıvel? Vamos estudar essas questões na próxima seção.


9/97


1.1 Representando cenários

Vamos supor que num ano particularmente favorável os rendimentos sejam 20% maiores que os rendimentos médios sugeridos por João. Alterandoesse dados e resolvendo o problema para esses rendimentos obtemos a soluçãodescrita na Tabela 1.3. Por outro lado podemos ter um ano desfavorável noqual os rendimentos fiquem 20% abaixo da média. Nesse caso a solução édada pela Tabela 1.4.


Área (ha) 183.33 66.67 250Total produzido 550 240 6 000

Total vendido 350 - 6 000Total comprado - - -Lucro total: R$ 167 600

Tabela 1.3: Solução ótima com rendimentos 20% acima da média.


Área (ha) 100 25 375Total produzido 200 60 6 000

Total vendido - - 6 000Total comprado - 180 -Lucro total: R$ 59 950

Tabela 1.4: Solução ótima com rendimentos 20% abaixo da média.

Esses resultados são alarmantes para as finanças de João: mudanças de20% nos rendimentos das culturas em relação ao rendimento médio fazemo seu lucro variar de R$ 59 950 a R$ 167 667! Pensando na cana-da-açúcar,João tem o seguinte dilema: se reservar uma área muito grande para essecultivo e os rendimentos foram acima da média, então ele terá que venderuma quantidade da produção a um preço desfavorável por causa da cota. Poroutro lado, se ele reservar um área muito pequena e os rendimentos foremabaixo da média, então ele vai perder a oportunidade de vender cana-de-açúcar a um preço favorável.

João conclui que não existe uma solução que seja ótima para todos oscasos. No entanto, ele se questiona se existe uma solução que seja satisfatóriapara todos os tipos de rendimentos posśıveis. A resposta para essa pergunta


10/97


virá com a primeira formulação de otimização estocástica, que estudaremos

a seguir.Vamos introduzir um pouco de nomenclatura: os cenários 20% acima da

média, na média e 20% abaixo da média serão indexados por s = 1, 2, 3respectivamente. As variáveis y e w terão o mesmo significado da for-mulação (1.1), mas serão indexadas por wis, i = 1, 2, 3, 4, s = 1, 2, 3 ey js, j = 1, 2, s = 1, 2, 3. Por exemplo, y23 representa a quantidade demilho vendida no caso de preços abaixo da média. Vamos assumir que oscenários são eqüiprováveis, ou seja, que cada um ocorre com probabilidade

1/3. Além disso, supondo que João quer maximizar seus ganhos a longoprazo, é razoável supor que ele procura uma solução que maximize seu lucroesperado. Nesse caso o problema fica

minimizar150 x1 + 230 x2 + 260 x3

−13

(170 w11 − 238 y11 + 150 w21 − 210 y21 + 36 w31 + 10 w41)

−13

(170 w12 − 238 y12 + 150 w22 − 210 y22 + 36 w32 + 10 w42)

−13

(170 w13 − 238 y13 + 150 w23 − 210 y23 + 36 w33 + 10 w43)

sujeito ax1 + x2 + x3 ≤ 500

3 x1 + y11 − w11 ≥ 200, 3.6 x2 + y21 − w21 ≥ 240,w31 + w41 ≤ 24 x3, w31 ≤ 6000,

2.5 x1 + y12 − w12 ≥ 200, 3 x2 + y22 − w22 ≥ 240,w32 + w42 ≤ 20 x3, w32 ≤ 6000,

2 x1 + y13 − w13 ≥ 200, 2.4 x2 + y23 − w23 ≥ 240,w33 + w43 ≤ 16 x3, w33 ≤ 6000

x1, x2, x3 ≥ 0,y11, y21, y12, y22, y13, y23 ≥ 0,

w11, w21, w31, w41, w12, w22, w32, w42, w13, w23, w33, w43 ≥ 0

(1.2)

Esta é a chamada forma extensa de um problema de otimização es-


11/97


tocástica. Essa denominação vem do fato que todas as variáveis que de-

pendem de cenários estão explicitamente descritas no modelo. As variáveisx são chamadas variáveis de primeiro est´ agio, pois seu valor tem que serdefinido antes de se conhecer o clima e, conseqüentemente, o rendimento dasculturas. As variáveis yis e wis são variáveis de segundo est´ agio. São variáveisque são escolhidas após o conhecimento do rendimento das lavouras. Elasservem para corrigir uma posśıvel situação de déficit nas necessidades ali-mentares do gado resultante da escolha x de primeiro estágio. O problemado fazendeiro é um exemplo de problema de recurso com dois est´ agios , queserá estudado em detalhe mais adiante no texto.

Note que o problema 1.2 é linear e pode ser resolvido da mesma formaque os anteriores. Exibimos na Tabela 1.5 a solução ótima, bem como asquantidades produzidas em cada cenário e os valores de compra e venda dasculturas.


Primeiro estágio Área (ha) 170 80 250s = 1 Rendimento (T) 510 288 6 000

(Acima) Venda (T) 310 48 6 000(preço favorável)

Compra(T) – – - -s = 2 Rendimento (T) 425 240 5 000

(Média) Venda (T) 225 – 5 000(preço favorável)

Compra(T) – – –s = 3 Rendimento (T) 340 192 4 000

(Abaixo) Venda (T) 140 – 4 000(preço favorável)

Compra(T) – 48 –

Lucro total: R$ 108 390

Tabela 1.5: Solução ótima do modelo estocástico.

A primeira linha da Tabela 1.5 nos dá a solução de primeiro estágio en-quanto que as outras descrevem a solução de segundo estágio para cadacenário. O aspecto mais interessante da solução estocástica é que ela deixaclaro ser imposśıvel escolher uma solução que seja ótima para todos os

cenários. No caso s = 3 por exemplo, onde os rendimentos são 20% abaixoda média, temos a compra de 48 toneladas de milho para suprir as necessida-des do gado. É claro que se soubéssemos que os rendimentos seriam abaixo


12/97


da média terı́amos reservado mais área para o plantio de milho para evitar

que este produto fosse comprado de outros comerciantes.Dessa forma, a solução de primeiro estágio (x1, x2, x3) = (170, 80, 250) do

problema (1.2) representa o melhor que se pode fazer diante dos diferentescenários que podem ocorrer. Na próxima seção vamos tentar mensurar oganho de João por considerar o problema estocástico bem como a quantidadede dinheiro perdida por não conhecer com exatidão o futuro.

1.2 EVPI e VSS

Imagine que João tenha uma bola de cristal e consiga prever o clima nofuturo. Sob essa hipótese, ele não precisa do modelo estocástico (1.2): sempreque ele antevê um rendimento 20% abaixo da média (respectivamente 20%acima da média) ele escolhe a solução dada na Tabela 1.4 (resp. Tabela 1.3).Se os rendimentos forem na média, ele se baseia na Tabela 1.2.

Se esperarmos um número grande de anos, então o rendimento médio de

João sob informação perfeita (WS) será

WS = R$ 59 950 + R$ 167 667 + R$ 118 600

3 = R$ 115 406. (1.3)

Note que estamos assumindo que os diferentes cenários ocorrem ao acasocom probabilidade 1/3 cada. Essa rendimento médio corresponde à situaçãosob informação perfeita, ou seja, à situação onde João sabe com precisão quecenário ocorrerá no futuro.

Infelizmente, nós e os meteorologistas sabemos que tal hipótese não érealista. Assim, ao longo de um peŕıodo de, digamos, 20 anos, o melhorque João tem a fazer é utilizar a solução estocástica dada pela Tabela 1.5,obtendo um lucro esperado de R$ 108 390. A diferença entre este valor e olucro no caso sob informação perfeita (equação (1.3)) é o valor esperado de informaç˜ ao perfeita , ou EVPI:

EVPI = R$ 115 406 − R$ 108 390 = R$ 7 016. (1.4)

Um outro conceito importante em otimização estocástica é o valor da soluç˜ ao estoc´ astica (VSS). O VSS mede o ganho em considerar o modelo es-tocástico ao invés de simplesmente basear a decisão nos rendimentos médios.


13/97


Pense que João é um fazendeiro teimoso: mesmo sabendo que posśıveis va-

riações de rendimento podem ocorrer, ele insiste em dividir sua terra deacordo com a situação de rendimentos médios dado pela Tabela 1.2. O lucroobtido com essa poĺıtica é chamado Soluç˜ ao do Valor Esperado, ou EEV.

Como calculá-lo? É simples: fixe a distribuição de terras do caso de ren-dimentos médios, ou seja, calcule a solução do problema (1.1) nas variáveisyis e wis, tomando x1 = 120, x2 = 80 e x3 = 300 e os rendimentos iguaisa 3.0, 3.6 e 24 (para s = 1) e depois 2, 2.4 e 16 (para s = 3). As soluçõessão R $55 120 e R$ 148 000 respectivamente. Lembrando que a solução é

R$ 118 600 no caso de rendimentos médios e R$ 108 390 no caso estocástico,temos

EEV = R$ 55 120 + R$ 118 600 + R$ 148 000

3 = R$107 240,

VSS = R$108 390 − R$ 107 240 = R$ 1 150.

Os conceitos de EVPI e VSS são importantes pois eles quantificam o valorda informação e o ganho em se considerar a formulação estocástica. No

caso do EVPI, ele diz o quanto vale a pena pagar para se obter informaçãoperfeita. Já o VSS nos dá acesso ao quanto estamos ganhando em consideraro modelo estocástico ao invés de simplesmente supor que os rendimentos dasculturas são dados pelos rendimentos médios.

Exerćıcios

[01] No problema do fazendeiro, suponha que quando os rendimentos sãoaltos para um fazendeiro o mesmo ocorre para os fazendeiros vizinhos.Assim ,o aumento na demanda reduz os preços. Considere por exemploque os preços do milho e do trigo caem 10% quando os rendimentos sãoacima da média e sobem 10% quando são abaixo. Formule e resolva oproblema nesse caso, supondo que as alterações de preço são verificadaspara compra e para venda de milho e trigo e que a cana-de-açúcar nãosofre mudanças.

[02] Suponha agora que a propriedade do fazendeiro é dividida em quatrolotes, de tamanhos 185, 145, 105 e 65 hectares respectivamente. Por


14/97


razões de eficiência, o fazendeiro só pode cultivar um tipo de produto

por lote. Formule e resolva o problema do fazendeiro nesse caso.[03] Imagine que as compras e vendas de trigo e milho só podem ser feitas

em centenas de toneladas, ou seja, não é posśıvel comprar nem venderesses produtos em quantidades diferentes de múltiplos de 100. Formulee resolva o problema do fazendeiro sob essas restrições.


15/97

Caṕıtulo 2

O Problema do Jornaleiro

O segundo exemplo que vamos considerar é conhecido como problema do jornaleiro ou problema da árvore de natal. Este problema é um clássico naárea de otimização, possuindo vasta literatura a respeito. Uma interessanteaplicação do problema do jornaleiro é descrita em [01]. Nesse artigo, idéiasdo problema do jornaleiro são aplicadas à distribuição de revistas da empresaTime inc. e o processo desenvolvido pelos autores gerou uma economia de3.5 milhões de dólares por ano. Vamos descrever o problema seguindo aformulação proposta por [03].

O fazendeiro João tem um irmão na cidade chamado José, que é jornaleiro.Toda manhã ele vai ao editor do jornal e compra uma quantidade x de jornaisa um preço c por unidade. Essa quantidade x é limitada superiormente porum valor u, pois José tem um poder de compra finito. Ele vende seus jornais

a um preço q por unidade. José possui um acordo com o editor do jornal:qualquer jornal não vendido pode ser devolvido ao editor, que paga um preçor < c por ele.

O dilema de José diz respeito a demanda di´ aria por jornal, que é incerta.Se ele comprar um número muito grande de jornais corre o risco de nãovendê-los e perder dinheiro com isso. Por outro lado, se comprar poucosJosé pode não atender a demanda e deixar de faturar dinheiro. Vamos supor

que a demanda ξ é uma variável aleatória não-negativa com função densidadef e função distribuição F , que y é o número de jornais efetivamente vendidose que w é o número de posśıveis jornais devolvidos ao editor. A formulação


16/97

O Problema do Jornaleiro 11

do problema do jornaleiro é

min0≤x≤u {cx + Q(x)}

onde

Q(x) = Eξ [Q(x, ξ )]e

Q(x, ξ ) = min −qy(ξ ) − rw(ξ )sujeito a y(ξ ) ≤ ξ ,

y(ξ ) + w(ξ )≤

x,y(ξ ), w(ξ ) ≥ 0.

O śımbolo Eξ representa a esperança com respeito a ξ . Para uma quanti-dade x de jornais comprados, a função −Q(x, ξ ) denota o lucro obtido coma venda destes jornais para um valor fixo de demanda ξ . O valor −Q(x) é olucro esperado calculado sobre todos os valores ξ posśıveis.

Assim como no problema do fazendeiro, o problema do jornaleiro é estru-turado em dois estágios: no primeiro estágio José decide quantos jornais vai

comprar através da variável x. Após essa escolha, ele vai tentar vender esses jornais para uma demanda ξ . As variáveis de segundo estágio representamquanto ele conseguiu vender (y(ξ )) e quanto ele devolveu ao editor (w(ξ )).Observe que a dependência dessas variáveis em ξ deixa claro que elas sãode segundo estágio, pois seu valor só é determinado após o conhecimento dademanda ξ .

José procura a quantidade certa de jornais a comprar de forma a maxi-mizar seu lucro esperado sob incerteza de demanda. Note aqui a semelhança

com o problema do fazendeiro: se a demanda fosse conhecida José simples-mente comprava ξ jornais e obteria o lucro máximo. No entanto, como noproblema do fazendeiro, não é posśıvel escolher um valor x que maximizeseu lucro para todos os posśıveis valores de demanda ξ . O que José buscaentão é uma escolha que, em média , lhe dê o maior lucro.

2.1 Resolução do Problema

O primeiro passo para encontrar uma solução expĺıcita do problema do jornaleiro é resolver o problema de segundo estágio. Felizmente a solução


17/97


é imediata: se a demanda ξ for menor que o número de jornais comprados

então y∗(ξ ) = ξ . Se for maior então y∗(ξ ) = x. Para encontar w∗(ξ ) bastaobservar que retornos de jornais ao editor só ocorrem se a demanda ξ formenor que x. Conclui-se então que

y∗(ξ ) = min{ξ, x},w∗(ξ ) = max{x − ξ, 0}.

A resolução desse problema nos permite escrever Q(x) explicitamente:

Q(x) = Eξ [

−q min

{ξ, x

} −r max

{x

−ξ, 0

}] .

Vamos ver posteriormente que a função Q é convexa e derivável quandoa variável aleatória ξ for cont́ınua. Como estamos no intervalo [0, u] e afunção Q(x) é convexa, sabemos que se c + Q(0) > 0, então a derivada nãotroca de sinal no intervalo e a solução ótima é x = 0. De maneira análoga,se c + Q(u) < 0, então a solução ótima é x = u. Caso nenhuma dessascondições se verifique temos que encontrar o ponto cŕıtico de c + Q(x).

Usando a definição A.15 dada no apêndice A, temos que

Q(x) = x

−∞(−qt − r(x − t))f (t) dt +

∞x

−qxf (t) dt.

Manipulando a expressão e usando a equação (A.2) do apêndice A obtemosque

Q(x) = −(q − r) x

−∞tf (t)dt − rxF (x) − qx(1 − F (x)).

Usando integração por partes, podemos simplificar ainda mais a expressão:

Q(x) = −qx + (q − r) x−∞

F (t)dt. (2.1)

A partir desta expressão podemos concluir que

Q(x) = −q + (q − r)F (x). (2.2)Finalmente, a solução do problema é

x∗ = 0, se q −cq

−r < F (0),

x∗ = u, se q −cq −r > F (u),x∗ = F −1

q −cq −r

, caso contrário.

(2.3)


18/97


Qualquer modelagem razoável da demanda ξ admite que ela só assume va-

lores positivos. Nesse caso F (0) = 0 e, portanto, nunca temos x∗ = 0.O exemplo do jornaleiro é mais um exemplo de problema de recurso com

dois estágios. Novamente o agente decisório, nesse caso José, tem que fazeruma escolha sob incerteza. Ele não conhece a demanda no momento quecompra os jornais junto ao editor. Após a compra ele ajusta as variáveisde segundo estágio de acordo com o valor da demanda, agora conhecido.A solução do problema representa a poĺıtica de compras que rende o maiorlucro esperado para José.

2.2 Um exemplo numérico

Vamos apresentar um exemplo numérico do problema do jornaleiro. Su-ponha que o custo por jornal para o jornaleiro seja c = 10, que o preço devenda seja q = 25, que o preço de devolução ao editor seja de r = 5 por

jornal e que o poder de compra é u = 150. Além disso, considere que a

demanda ξ é dada por uma variável aleatória uniforme cont́ınua definidano intervalo [50, 150]. Na Tabela A.1 do apêndice A listamos a densidade,média e variância dessa variável aleatória.

Integrando-se a densidade de ξ , obtemos a função distribuição da de-manda:

F (x) =

x−50100 , se 50 ≤ x ≤ 150,

1, se x > 150,

0, caso contrário.

(2.4)

A inversa dessa função é F −1(y) = 100 y + 50 no intervalo [50, 150]. Usan-do (2.3), temos que a solução do problema é

x∗ = F −1(3/4) = 125,

com lucro esperado de 1312.5. Assim, José deve comprar 125 jornais por diapara maximizar seu lucro esperado.

Podemos também calcular o valor da solução estocástica (VSS) para esseproblema. Lembrando: temos que inicialmente calcular a solução ótima parao problema do jornaleiro para ξ = 100, ou seja, com demanda constante igual


19/97


a média de ξ , isto é, temos que resolver é

min0≤x≤150

{ cx − q min{100, x} − r max{x − 100, 0}} .

Ao invés de obter o máximo usando cálculo, podemos ver imediatementepela Figura 2.1 que a solução é x∗ = 100.

1000 150 x

{1250

{1500

cx +Q (x ,100)

Figura 2.1: Gráfico de cx + Q(x, ξ ) para ξ = 100.

Uma maneira ainda mais fácil de ver é que se sabemos que a demanda é100, então devemos comprar x = 100 jornais para maximizar o lucro!

Ainda falta calcular o valor de EEV, que é o valor esperado da soluçãosupondo que o jornaleiro comprou 100 jornais. Para isso fazemos

EEV = Eξ [10 · 100 + Q(100, ξ )] = 100 · 10 − 25 · 100 + 20 100

50

ξ − 50100

dξ

= 1000 − 2500 + 20

75

2 − 25

= −1250,

que resulta num lucro de R$ 1 250. Logo, temos que

VSS = 1312.5 − 1250 = 62.5.

Por fim, vamos ao cálculo do EVPI. Recordando: para obter o EVPI,supomos que se conhece o futuro, ou seja, que se sabe o valor que demanda


20/97


ξ . O valor do EVPI é a esperança com relação a ξ de todas essas soluções.

No problema do fazendeiro, a incerteza estava associada a apenas três tiposde acontecimentos. Aqui a demanda ξ pode assumir uma quantidade nãoenumerável de valores. Portanto, teremos que fazer uso da integral paraobter o EVPI.

Dado um valor qualquer de demanda ξ , a solução ótima obviamente éx∗ = ξ . Assim, temos

WS = Eξ [cξ + −qξ ] = −15Eξ (ξ ) = −1500. (2.5)

Conseqüentemente, temos queEVPI = 1500 − 1312.5 = 187.5.

2.3 Outras interpretações para o problema

Primeiramente vamos usar o conceito de ganho marginal para derivar asolução do problema por uma outra trilha. A expressão ganho marginal em

economia se refere ao crescimento no lucro obtido quando se aumenta emuma unidade a quantidade vendida ou adquirida de um determinado bem.Vamos apresentar uma aplicação desse conceito ao problema do jornaleiroque nos permite chegar a resposta (2.3) do problema do jornaleiro de maneiraelementar.

Suponha que jornaleiro comprou k jornais. Qual é o lucro esperado navenda do k-ésimo jornal? A resposta é

lucro esperado = P(ξ < k)(r−

c) + P(ξ ≥

k)(q −

c), (2.6)

onde P(ξ < k) é probabilidade dele não vender o k-ésimo jornal e P(ξ ≥ k)é a probabilidade dele vender este k-ésimo jornal.

A situação ideal ocorre quando o lucro esperado com a venda do último jornal é zero: se fosse negativo a demanda seria menor que k (jornal “en-calhado”) e se fosse positivo a demanda seria maior que k (falta de jornal).Igualando-se a equação (2.6) a zero, temos

lucro esperado = 0

= P(ξ < k)(r − c) + P(ξ ≥ k)(q − c)= F (k)(r − c) + (1 − F (k))(q − c).


21/97


Desta maneira, F (k) = (q − c)/(q − r) e, portanto,

k = F −1q − cq − r

. (2.7)

Assim, o número de jornais a ser comprado para que em média todos sejamvendidos é k∗ = F −1( q −cq −r ), a mesma solução encontrada anteriormente.

Uma outra interpretação interessante do problema do jornaleiro, menci-onada em [02], surge quando nos perguntamos sobre a probabilidade de sevender todos os jornais para um dada escolha de x. Esse valor é igual a

P({vender tudo}) = P(ξ ≥ x) = 1 − F (x).Vamos ver qual é a probabilidade de se vender tudo se comprarmos x∗ jornais:

P({vender tudo}) = 1 − F (x∗) = 1 − q − cq − r =

c − rq − r .

É comum encontrar na literatura artigos que não permitem que um jornalnão vendido seja devolvido ao editor, ou seja, r = 0. Nesse caso, temos quea quantidade de jornal a ser comprada deve ser escolhida de maneira que aprobabilidade de se vender todos os jornais seja igual a razão custo unitárioc do jornal dividido pelo seu preço unitário q .


22/97

Caṕıtulo 3

Programação Linear com CoeficientesAleatórios

Neste caṕıtulo apresentaremos as abordagens clássicas usadas na mode-lagem e solução de problemas de programação linear onde um ou mais coe-ficientes são aleatórios (otimização estocástica linear).

Tradicionalmente, são propostos dois tipos de modelos clássicos para setratar problemas de otimização com coeficientes aleatórios: a abordagem “es-pere e veja” (em inglês, “wait and see”) e a abordagem “aqui e agora” (eminglês, “here and now”). Em “espere e veja”, o agente de decisão pode espe-rar por uma realização dos coeficientes aleatórios para tomar a sua decisão.Já em “aqui e agora”, o agente de decisão deve fazer suas escolhas antes ou sem o conhecimento das realizações dos coeficientes aleatórios. Neste

segundo caso, uma dificuldade adicional aparece: sem se conhecer os coefici-entes, as definições habituais de admissibilidade e otimalidade não se aplicame especificações adicionais são necessárias.

A teoria pressupõe que seja dada (conhecida) a distribuição conjunta doscoeficientes. Poder-se-ia argumentar que esta hipótese é restritiva, visto quedificilmente existem dados suficientes para a construção de uma estimativaconfiável. Como conseqüência, é o modelador do problema que acaba fa-

zendo a escolha da distribuição conjunta. Note, contudo, que este tipo dearbitrariedade não é diferente da que uma abordagem determinı́stica fariaao escolher uma realização particular dos coeficientes aleatórios.


23/97


3.1 O problema da mistura

Vamos começar com um exemplo onde a aleatoriedade se manifesta apenasem alguns dos coeficientes das restrições em desigualdades. Para isto, consi-dere a seguinte situação: um fazendeiro consultou um engenheiro agrônomoque recomendou 7 g de um nutriente A e 4 g de um nutriente B paracada 100 m2 de terra. O fazendeiro dispõe de dois tipos de adubo. Cada kg doprimeiro adubo possui ω1 g do nutriente A e ω2 g de um nutriente B. Cada kgdo segundo adubo, por sua vez, possui 1 g de cada nutriente. Os custos de

compra dos dois adubos são iguais: uma unidade monetária por kg. As quan-tidades ω1 e ω2 são incertas: o fabricante dos adubos garante que elas sãovariáveis aleatórias independentes, uniformemente distribúıdas e com supor-tes nos intervalos [1, 4] e [1/3, 1], respectivamente. O problema (da mistura)é então decidir o quanto comprar de cada adubo para atender a necessidadede nutrientes em 100 m2 de terra minimizando o custo de compra:

minimizar f (x1, x2) = x1 + x2sujeito a ω1 x1 + x2 ≥ 7,

ω2 x1 + x2 ≥ 4,x1 ≥ 0,x2 ≥ 0.

(3.1)

Note que o conjunto admisśıvel deste programa linear depende dos valoresdos coeficientes ω1 e ω2.

Abordagem “Espere e Veja”

Nesta abordagem, supõe-se que o agente de decisão possa fazer a esco-lha dos valores de x = (x1, x2) depois da realização de ω = (ω1, ω2). Destamaneira, o problema (3.1) pode ser considerado um programa linear pa-ramétrico1: as soluções ótimas e o valor ótimo são calculados em funçãode ω. Por exemplo:

(a) Para ω = (ω1, ω2) = (1, 1/3), o conjunto admisśıvel correspondente é oapresentado na Figura 3.1, a solução ótima é

1No endereço http://www.professores.uff.br/hjbortol/car/activities/problema-da-mistura-01.html vocêencontrará um applet JAVA interativo que desenha o conjunto admisśıvel e calcula a solução ótima doproblema (3.1) para diferentes valores de ω1 e ω2.


24/97

Programação Linear com Coeficientes Aleatórios 19

x∗(ω) = x∗(1, 1/3) = (x∗1(1, 1/3), x∗2(1, 1/3)) = (9/2, 5/2)

e o valor ótimo é v∗(1, 1/3) = x∗1(1, 1/3) + x∗2(1, 1/3) = 7.

7

4

79/2

5/2

0 12 x 1

x 2

Figura 3.1: Conjunto admisśıvel do problema da mistura para ω = (ω1, ω2) =(1, 1/3).

(b) Para ω = (ω1, ω2) = (5/2, 2/3), o conjunto admisśıvel correspondente éo apresentado na Figura 3.2, a solução ótima é

x∗(ω) = x∗(5/2, 2/3) = (x∗1(5/2, 2/3), x∗2(5/2, 2/3)) = (18/11, 32/11)

e o valor ótimo é v∗(5/2, 2/3) = x∗1(5/2, 2/3) + x∗2(5/2, 2/3) = 50/11 =

4.54.

(c) Para ω = (ω1, ω2) = (4, 1), o conjunto admisśıvel correspondente é oapresentado na Figura 3.3, a solução ótima é

x∗(ω) = x∗(4, 1) = (x∗1(4, 1), x∗2(4, 1)) = (1, 3)

e o valor ótimo é v∗(4, 1) = x∗1(4, 1) + x∗2(4, 1) = 4.


25/97


7

4

0 614/518/11 x 1

x 2

32/11

Figura 3.2: Conjunto admisśıvel do problema da mistura para ω = (ω1, ω2) =(5/2, 2/3).

7

4

0 47/41 x 1

x 2

3

Figura 3.3: Conjunto admisśıvel do problema da mistura para ω = (ω1, ω2) =(4, 1).


26/97


De fato, é posśıvel mostrar (exercı́cio) que a solução ótima do problema (3.1)

para (ω1, ω2) ∈ Ω = [1, 4] × [1/3, 1] é dada por

(x∗1(ω1, ω2), x∗2(ω1, ω2)) =

3

ω1 − ω2 , 4 ω1 − 7 ω2

ω1 − ω2

, se

7

ω1≤ 4

ω2,

7

ω1, 0

, caso contrário,

e que o valor ótimo associado é dado por

v∗(x∗1(ω1, ω2), x∗2(ω1, ω2)) =

3 + 4 ω1 − 7 ω2

ω1 − ω2 , se 7

ω1≤ 4

ω2,

7

ω1, caso contrário.

A partir destas expressões, o agente de decisão pode então calcular as dis-tribuições de x∗ = (x∗1(ω1, ω2), x

∗2(ω1, ω2)) e v

∗(x∗1(ω1, ω2), x∗2(ω1, ω2)) e suas

caracteŕısticas como média, variância, etc. (veja o exerćıcio [03]).

Abordagem “Aqui e Agora”

Nesta abordagem, o agente de decisão deve fazer a escolha de x = (x1, x2)sem conhecer os valores de ω = (ω1, ω2) (mas sabendo a função distribuiçãode ω). Sem se conhecer os coeficientes, as definições habituais de admissibili-dade e otimalidade não se aplicam e especificações adicionais de modelagem

são necessárias. Apresentaremos agora os tipos de especificações mais tradi-cionais.

1. Abolir incertezas

O agente de decisão simplesmente faz uma escolha apropriada para ω e,então, ele resolve o problema determinı́stico correspondente.

(a) Escolha “pessimista”: ω = (1, 1/3).Neste caso, o conjunto admisśıvel é o representado na Figura 3.1 e ovalor ótimo correspondente é v = 7.


27/97


(b) Escolha “neutra”:

ω = (5/2, 2/2) = E[(ω1, ω2)].

Neste caso, o conjunto admisśıvel é o representado na Figura 3.2 e ovalor ótimo correspondente é v = 50/11 = 4.54.

(c) Escolha “otimista”: ω = (4, 1).Neste caso, o conjunto admisśıvel é o representado na Figura 3.3 e ovalor ótimo correspondente é v = 4.

Vantagem da especificação: o problema reformulado é fácil de se resolver,pois ele é um programa linear determińıstico. Desvantagem: a solução

ótima x∗ = (x∗1, x∗2), quando implementada, pode não ser admissı́vel.

2. Incorporar riscos nas restriç˜ oes (chance constraints)

O agente de decisão descreve uma “medida de risco”, faz uma escolha do“ńıvel máximo de risco aceitável” e, então, ele incorpora estes elementos nasrestrições do programa linear. Aqui, o agente de decisão pode ainda esco-lher entre ńıveis de confiabilidade individuais ou um ńıvel de confiabilidade

conjunto.

(a) Nı́veis de confiabilidade individuais.

O agente de decisão escolhe dois ńıveis de confiabilidade individuaisα1, α2 ∈ [0, 1] e ele decreta que x = (x1, x2) ∈ [0, +∞) × [0, +∞) éadmisśıvel se, e somente se,

P (ω1 x1 + x2 ≥ 7) ≥ α1P (ω2 x1 + x2

≥4)

≥ α2

. (3.2)

Restrições deste tipo são denominadas restriç˜ oes probabilı́sticas indivi-duais (separadas) (em inglês, individual (separate) chance constraints ).Os riscos são definidos em termos da probabilidade de inadmissibilidade,isto é,

risco1 := P (ω1 x1 + x2 < 7)

risco2 := P (ω2 x1 + x2 < 4) . (3.3)

Podemos reescrever as condições (3.2) de forma mais expĺıcita usando as

funções distribuição2

F 1 e F 2 das variáveis ω1 e ω2. De fato, é posśıvel2No apêndice A você encontrará, entre outros conceitos de probabilidade, a definição de função distri-

buição de uma variável aleatória.


28/97


mostrar (exerćıcio) que se 0 ≤ α1


29/97


(b) Nı́vel de confiabilidade conjunto.

O agente de decisão escolhe um ńıvel de confiabilidade conjunto α ∈ [0, 1]e ele decreta que x = (x1, x2) ∈ [0, +∞) × [0, +∞) é admissı́vel se, esomente se,

P (ω1 x1 + x2 ≥ 7 e ω2 x1 + x2 ≥ 4) ≥ α. (3.8)Restrições deste tipo são denominadas restriç˜ oes probabilı́sticas conjun-tas (em inglês, joint chance constraints ). O risco é definido como aprobabilidade de inadmissibilidade do sistema de restrições do programa

linear, isto é, como o númerorisco := P (ω1 x1 + x2 < 7 ou ω2 x1 + x2 0,

1, se x1 = 0 e x2 ≥ 7,0, se x1 = 0 e 0 ≤ x2


30/97


Com esta abordagem e para este valor de α, o problema da mistura (3.1)

fica modelado assim:minimizar

f (x1, x2) = x1 + x2

sujeito a

x2 ≥ max

−2 x1 + 7,11 − 5 x1 +

9 − 18 x1 + 433 x212

, −5 x19

+ 4

,

x1 ≥ 0, x2 ≥ 0.(3.12)

Este problema de otimização não-linear assume o valor mı́nimo

v∗ = 220/43 = 5.1162790 . . .

no ponto ótimo x∗ = (x∗1, x∗2) = (54/43, 166/43) = (1.25 . . . , 3.86 . . .).

O conjunto admissı́vel4 de (3.12) é apresentado na Figura 3.4.

3. Aceitar inadmissibilidade, penalizando déficits esperados

A idéia aqui é acrescentar à função objetivo parcelas que penalizam inad-missibilidade. Vamos primeiro estabelecer algumas notações. Note que arestrição ω1 x1 + x2 ≥ 7 não é satisfeita se, e somente se, ω1 x1 + x2 − 7 < 0.Usando-se a (conveniente) notação

z − =

0, se z ≥ 0,−z, se z 0 (podemos entãopensar em (ω1 x1 + x2 − 7)− > 0 como uma “medida de inadmissibilidade”para a restrição ω1 x1+x2 ≥ 7). Analogamente, ω2 x1+x2 ≥ 4 não é satisfeitase, e somente se, (ω2 x1 + x2 − 4)− > 0. Escolhendo-se custos de penalidadeunitários q 1 > 0 e q 2 > 0, as expressões

q 1 Eω1

(ω1 x1 + x2 − 7)−

e q 2 Eω2

(ω2 x1 + x2 − 4)−

4No endereço http://www.professores.uff.br/hjbortol/car/activities/problema-da-mistura-03.html. vocêencontrará um applet JAVA interativo que desenha o conjunto admisśıvel e calcula a solução ótima doproblema da mistura usando restrições probabiĺısticas para diferentes valores dos ńıvel de confiabilidadeconjunto α.


31/97


7

4

0 127 x 1

x 2

9/5

17/5

Figura 3.4: Conjunto admisśıvel do problema da mistura usando restriçõesprobabiĺısticas para o ńıvel de confiabilidade conjunto α = 2/3.

representam então, respectivamente, os custos médios para inadmissibilidadenas restrições ω1 x1 + x2 ≥ 7 e ω2 x1 + x2 ≥ 4. Nesta abordagem, o agentede decisão substitui o problema da mistura (3.1) original pelo problema

minimizarg(x1, x2) = x1 + x2 + q 1 Eω1 [(ω1 x1 + x2 − 7)−] + q 2 Eω2 [(ω2 x1 + x2 − 4)−]

sujeito a x1 ≥

0, x2 ≥

0.

(3.13)

Várias questões surgem neste momento: como calcular as médias (espe-ranças) envolvidas e como resolver o problema de otimização? Como vere-mos, o cálculo das esperanças é elementar, mas não-trivial. Apesar de sernão-linear, a função objetivo de (3.13) possui propriedades desejáveis paraos algoritmos numéricos em otimização: ela é convexa e subdiferenciável. Seos coeficientes aleatórios têm distribuição cont́ınua (como no problema da

mistura), o cálculo da esperança é especialmente dif́ıcil. Nestes casos, umaprática comum é substituir a distribuição cont́ınua por uma aproximaçãodiscreta.


32/97


3.2 O problema da produção

Vamos estudar agora um programa linear onde a aleatoriedade apareceem uma restrição em igualdade. Mais precisamente, considere o problema(da produção):

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

x ≥ 0,(3.14)

onde c > 0 é o custo unitário de produção. Este problema de otimizaçãosimples modela o processo de minimização do custo de produção c x sob a res-trição de que a produção x atenda à demanda ω. Aqui, vamos supor que ω éuma variável aleatória cont́ınua não-negativa com média µ = E [ω], variânciaσ2 = E

(ω − E [ω])2 e função distribuição F (t) = P (ω ≤ t), com t ∈ R.

Abordagem “Espere e Veja”

Se o agente de decisão pode esperar pela realização da demanda ω antesde escolher o valor da produção x, então o problema é fácil se resolver:x∗(ω) = ω e v∗(ω) = c x∗(ω) = c ω.

Abordagem “Aqui e Agora”

1. Abolir incertezas

Nesta abordagem, o agente de decisão pode, por exemplo, substituir o valorde ω por ω = µ ou ω = µ + ∆, onde ∆ é um “estoque reserva” (por exemplo,∆ = σ ou ∆ = 2 σ). A probabilidade de que a demanda seja satisfeita (o nı́vel de serviço da produç˜ ao) é então dada por P (ω ≤ µ + ∆) = F (µ + ∆).2. Incorporar riscos nas restriç˜ oes (chance constraints)

Construir uma restrição probabiĺıstica P (x = ω) ≥ α baseada em uma res-trição em igualdade (x = ω) é inútil. De fato: se ω tem distribuição cont́ınua,

então P

(x = ω) = 0. Se ω tem um distribuição discreta finita, digamosP (ω = ωi) = pi (com pi ≥ 0 e p1 + · · · + pn = 1), então P (ω = x) = 0 paratodo x ∈ {ω1, . . . , ωn}.


33/97


Para valores adequados de α1 e α2, também é inútil construir restrições

probabilı́sticasP

(x ≥ ω) ≥ α1 e P (x ≤ ω) ≥ α2 combinadas, pois não existeprodução x que satisfaça as condiçõesP (x ≥ ω) ≥ α1P (x ≤ ω) ≥ α2 ⇐⇒

F (x) ≥ α1

1 − F (x) ≥ α2 ⇐⇒ α1 ≤ F (x) ≤ 1 − α2

se, por exemplo, α1 = α2 = 3/4, uma vez que a função distribuição F énão-decrescente.

Desta maneira, é preciso estabelecer prioridades. Podemos, por exemplo,

especificar um ńıvel de confiabilidade mı́nimo α ∈ (1/2, 1) e modelar o pro-blema (3.14) na forma

minx≥0

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

cx | x ≥ F −1(α)

cuja solução é, evidentemente, x∗ = F −1(α).

3. Aceitar inadmissibilidade, penalizando desvios esperados

Aqui devemos penalizar tanto déficits quanto superávits na produção: usan-

do-se as notações

z − =

0, se z ≥ 0,−z, se z


34/97


x∗ = F −1q − cq + h .

Note que esta solução tem a mesma forma da solução obtida via restriçõesprobabiĺısticas. De fato, se h = 0, a mesma solução é obtida se q/c =1/(1 − α):

α(nı́vel de confiabil idade)

q/c(custo de déficit/custo de produção)

0.990 100

0.975 400.950 20

0.900 10

0.800 5

0.500 2

Esta tabela é interessante: ela nos dá uma idéia de que valores escolher parao custo q em termos do ńıvel de confiabilidade α.

Exerćıcios

[01] Deduza as equações para a solução ótima (x∗1, x∗2) do problema da mis-

tura apresentadas na página 19.

[02] Mostre 4 ≤ v∗(x∗1(ω1, ω2), x∗2(ω1, ω2)) ≤ 7 para todo (ω1, ω2) no conjuntoΩ = [1, 4] × [1/3, 1], onde v∗ = v∗(x∗1(ω1, ω2), x∗2(ω1, ω2)) é o valor ótimodo problema da mistura.

[03] Mostre que a função distribuição F do valor ótimo v∗ do problema damistura é dada por

F (t) =

0, se 0 ≤ t ≤ 4,8 t3 − 18 t2 − 105 t + 196

4 t2(7 − t) , se 4 ≤ t ≤ 50/11,

49 t3

−307 t2 + 648 t

−1008

36 t2(t − 4) , se 50/11 ≤ t ≤ 7,1, se t ≥ 7.


35/97


Note que, com esta expressão para F em mãos, podemos então calcular

a função de densidade de v∗ (derivando-se F ):

f (t) =

0, se 0 < t


36/97


[07] Mostre que (3.16) pode ser reformulado como um modelo de recurso:

minx≥0

cx + E

min

y1≥0, y2≥0

qy1 + hy2x + y1 − y2 = ω .


37/97

Caṕıtulo 4

Modelos de Recurso

Neste caṕıtulo nos concentraremos na abordagem “aqui e agora” queaceita inadmissibilidade penalizando desvios médios. De fato, veremos queesta abordagem motiva uma classe importante de modelos em otimizaçãoestocástica: os modelos de recurso.

4.1 Motivação: programação linear por metas

Em problemas determińısticos, a técnica de programação linear por metas(em inglês, goal programming ) consiste em classificar (separar) as restriçõesdo problema em dois tipos: as restrições ŕıgidas (hard constraints ) que nãopodem ser violadas de maneira alguma e as restrições flexı́veis (soft cons-traints ) que podem ser violadas, mas n˜ ao a qualquer preço. Mais precisa-mente, considere o programa linear determinı́stico:

minx∈X

{cx | Ax = b e Tx ∼ h} , (4.1)

onde

• X = {x ∈ Rn | x ≤ x ≤ x} ou X = {x ∈ Rn | 0 ≤ x < +∞} (asdesigualdades entre vetores devem ser interpretadas componente a com-ponente),

• c ∈ Rn, A é uma matriz m × n, b ∈ Rm, T é uma matriz m × n, h ∈ Rm,• cx = ni=1 ci · xi e


38/97

Modelos de Recurso 33

• o śımbolo ∼ representa uma das relações =, ≥ e ≤ (componente a com-ponente).

Neste programa linear, consideraremos Ax = b como restrições ŕıgidas eTx ∼ h como restrições flex́ıveis. Como antes, a idéia é penalizar os des-vios de meta z = h − Tx das restrições flex́ıveis através de uma funç˜ ao de penalidade z → v(z) que é incorporada à função objetivo do problema deotimização original:

minx∈X

{cx + v(h

−Tx)

| Ax = b

}= min

x∈X

{cx + v(z)

| Ax = b e Tx + z = h

}.

(4.2)A função de penalidade fornece uma medida do quanto se deve pagar pelaviolação das metas (restrições) z ∼ 0 frente ao custo original cx. Existemvárias maneiras de se especificar a função de penalidade v, o que torna ométodo flex́ıvel. Vamos ver algumas delas agora.

1. Funç˜ ao de penalidade com custos individuais

Escrevendo-se

T =

t1

t2...

tm

, h =

h1

h2...

hm

e z =

z 1

z 2...

z m

,vemos que a notação vetorial Tx ∼ h (respectivamente, z ∼ 0) é umamaneira compacta e conveniente de se representar as m restrições escalares:

tix ∼ hi (respectivamente, z i ∼ 0) para i = 1, . . . , m. Aquiti = (T i1, T i2, . . . , T in)

representa a i-ésima linha da matriz T e o produto tix deve ser entendidocomo o produto escalar

n j=1 T ij x j.

Podemos então construir uma função de penalidade v que é caracterizada porcustos de penalidade individuais, que podem ser diferentes para superávitse déficits:

v(z) =m

i=1

vi(z i) =m

i=1

q iz +i + q iz −i vi(zi)

. (4.3)


39/97


A especificação dos custos de penalidade unitários q i e q i podem seguir as

seguintes diretivas:

• Se a restrição é do tipo tix = hi, isto é, z i = 0, penalizamos superávitse déficits escolhendo q i > 0 e q i > 0. Note que, neste caso, a função vi éconvexa como soma de funções convexas.

• Se a restrição é do tipo tix ≥ hi, isto é, z i ≤ 0, penalizamos superávitsescolhendo q i > 0 e premiamos déficits escolhendo q i ≤ 0. Para obterconvexidade, as escolhas de q i e q i devem ser tais que q i + q i ≥ 0. De fato:observe que

vi(z i) = q iz +i + q iz

−i =

+q iz i, se z i ≥ 0,−q iz i, se z i 0 e premiamos superávits escolhendo q i ≤ 0. Novamente,

para que a função vi seja convexa, é necessário que q i + q i ≥ 0.

2. Funç˜ ao de penalidade com custos individuais refinados

Considere o caso de restrições do tipo tix = hi, isto é, z i = 0. Como antes, afunção v é constrúıda usando-se custos de penalidade individuais mas, agora,


40/97


desvios muito grandes, digamos, fora de um intervalo [−li, +ui] contendo 0,receberão uma penalidade extra:

vi(z i) = q (1)i z

+i +

q

(2)i − q (1)i

(z i−ui)++q (1)i z −i +

q (2)

i − q (1)

i

(z i +li)

−. (4.4)

Note que esta função de penalidade também pode ser usada para se modelarrestrições do tipo z i ∈ [−li, +ui] bastando, para isto, tomar q (1)i = q

(1)i = 0.

3. Funç˜ ao de penalidade com custo conjunto

A seguinte função de penalidade pode ser usada se as restrições do programalinear são do tipo z i ≥ 0 e se o desvio máximo é mais importante do que asoma ponderada dos desvios individuais:

v(z) = v(z 1, z 2, . . . , z m) = q 0 max{z −1 , z −2 , . . . , z −m}. (4.5)Como o máximo de funções convexas resulta em uma função convexa, segue-se que v é uma função convexa de q 0 > 0.

4. Funç˜ ao de penalidade via aç˜ oes de recurso

Este quarto exemplo de função de penalidade é motivado pela idéia decorreções (y) para compensar desvios (z) gerados por decisões (x) tomadasa priori. Para construir a função de penalidade são necessários os seguintesingredientes:

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

Aqui q ∈ R p e W é uma matriz m × p. A matriz W é denominada matriz de recurso (ou matriz de tecnologia ) e o vetor q especifica os coeficientesdo custo da ação de recurso.

2. Um conjunto Y de variáveis de recurso.

Em geral, Y = {y ∈ R p | y ≤ y ≤ y} ou Y = {y ∈ R p | 0 ≤ y ≤ +∞} =R

p+.

A funç˜ ao de recurso v dá o custo mı́nimo das ações de recurso necessárias

para compensar o desvio z ∈R

m

nas restrições Tx ∼ h:v(z) = min

y∈Y{qy | Wy ∼ z} . (4.6)


41/97


De fato, todas as funções de penalidade (4.3), (4.4) e (4.5) apresentadas

anteriormente podem ser representadas deste modo, isto é, como uma funçãode penalidade via ações de recursos para estruturas de recurso (q, W) econjuntos de ações de recurso Y adequados:

• Se p = 2 m,q =

q, q

∈ Rm × Rm = R p, W = +Im×m −Im×m m×2 m eY = Rm+ ×Rm+ = R p+,

então a função de recuso v em (4.6) obtém a função de penalidade em (4.3).Aqui Im×m denota a matriz identidade de tamanho m × m.

• Se p = 4 m,q =

q(2), q(1), q(1), q(2)

∈ Rm × Rm ×Rm × Rm = R p,W =

+Im×m +Im×m −Im×m −Im×m

m×4 m e

Y =

{(y(2), y(1), y(1), y(2))

∈R

m+

×R

m+

×R

m+

×R

m+

| y(1)

≤u e y(1)

≤l

}então a função de recuso v em (4.6) obtém a função de penalidade em (4.4).

• Se p = 1, q = q 0 , W = −1 −1 · · · −1 T (de tamanho m × 1) eY = R+ então a função de recuso v em (4.6) obtém a função de penalidadeem (4.5).

4.2 Modelos de recurso em otimização estocástica

Nesta seção veremos como usar a idéia de função de penalidade via açõesde recurso para criar um modelo para a seguinte versão estocástica do pro-grama linear determinı́stico (4.1):

minx∈X

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

De fato, o uso de ações de recurso é muito adequado para uma modelagem

do tipo “aqui e agora” para o problema (4.7). Como o agente de decisãodeve fazer a escolha da variável x sem conhecer os valores de ω, podemospensar nas restrições estocásticas T(ω)x ∼ h(ω) como restrições flex́ıveis,


42/97


que serão ou não satisfeitas dependendo das realizações de ω. Os desvios

correspondentes são, então, penalizados via uma função de penalidade comações de recurso:

Estágio 1 Estágio 2

decisão em x → ocorre ω → ação corretiva y .

Aplicando então a estrutura de recurso, obtemos o assim denominado modelode recurso em dois est´ agios para o problema (4.7):

minx∈X

cx + E miny∈Y

{q(ω)y | W(ω)y ∼ h(ω) − T(ω)x} Ax = b .(4.8)

Podemos obter uma formulação mais compacta de (4.8) através da funç˜ aode penalidade via aç˜ oes de recurso (também denominada funç˜ ao de valor dosegundo est´ agio)

v(z,ω) = miny∈Y

{q(ω)y | W(ω)y ∼ z} (4.9)

e da funç˜ ao de custo de recurso mı́nimo esperado (também denominada funç˜ ao de valor esperado)

Q(x) = E [v(h(ω) − T(ω)x,ω)] . (4.10)De fato, com estas funções, não é dif́ıcil de se ver que o problema (4.8) éequivalente a

minx∈X

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

Observação 1. É muito importante notar que tanto no programa lineardo segundo estágio

miny∈Y

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

como no cálculo da função de valor do segundo estágio (4.9), o valor de ωestá fixo! Neste sentido, os programas lineares envolvidos são determińısticos(ω é considerado um parâmetro)!

Observação 2. Como os exerćıcios [05] e [07] do caṕıtulo 3 pedem paramostrar, os problemas (3.13) e (3.16) podem ser considerados como modelosde recurso.


43/97


Observação 3. No problema do fazendeiro, as variáveis de primeiro estágio

correspondem à distribui̧cão de terra em milho, trigo e cana-de-açúcar(x1, x2 e x3). Elas devem ser escolhidas por João antes de ele saber quaisserão os rendimentos destes cultivos. As variáveis de segundo estágio cor-respondem às vendas e às compras destes três cultivos no mercado local(w1, y1, w2, y2, w3 e w4). Elas devem ser tomadas como ações corretivas queorientam João a como vender e comprar de maneira ótima no mercado localdepois da colheita.

Observação 4. Sem perda de generalidade, podemos supor que T(ω),

h(ω), W(ω) e q(ω) dependem linearmente de ω = (ω1, . . . , ωr) ∈ Rr

:

T(ω) = T0 +r

k=1 ωk · Tk, h(ω) = h0 +r

k=1 ωk · hk,W(ω) = W0 +

rk=1 ωk · Wk e q(ω) = q0 +

rk=1 ωk · qk.

Aqui Tk, hk, Wk e qk são todos constantes (isto é, não-estocásticos), comdimensões m × n, m, m × p e p, respectivamente.

4.3 Admissibilidade

Nem todo programa linear tem solução (o conjunto admisśıvel pode servazio ou a função objetivo pode ser ilimitada neste conjunto) e nem todavariável aleatória tem média finita. Nesta seção apresentaremos alguns re-sultados sobre a admissibilidade e finitude do modelo de recurso em doisestágios (4.8). As demonstrações serão omitidas, pois elas usam ferramentasde programação linear e teoria da medida que fogem do escopo deste texto.

O leitor interessado pode consultar os livros [03, 13, 14].

Nas considerações que se seguem, vamos supor que a matriz de tecnolo-gia W é determińıstica, isto é, vamos supor que ela não depende de ω:

W(ω) = W = constante.

Quando isto acontece, dizemos que (q(ω), W(ω)) possui uma estrutura de recurso fixa . Seja então

ξ(ω) = (q(ω), h(ω), t1(ω), . . . , tm(ω)) ∈ R p+m+(m×n)o vetor aleatório formado por todas as componentes aleatórias do proble-


44/97


ma (4.8) e seja Ξ o suporte de ξ, isto é, o menor subconjunto fechado

de R

p+m+(m

×n)

satisfazendo a condição P

(ξ(ω) ∈ Ξ) = 1. Aqui ti(ω) denotaa i-ésima linha da matriz T(ω).Ao estudarmos questões de admissibilidade e finitude em (4.8), é natural

considerarmos:

1. O conjunto de decisões x que satisfazem as restrições (ŕıgidas) do primeiroestágio:

K 1 = {x ∈ Rn | Ax = b}.2. O conjunto de decisões x de primeiro estágio para as quais a função de

valor esperado é finita:

K 2 = {x ∈ Rn | Q(x) = E [v(h(ω) − T(ω)x,ω)] < +∞}.

Com estes conjuntos, o problema (4.8) se reescreve da seguinte maneira:

minimizar cx + Q(x)sujeito a x

∈K 1

∩K 2.

Note, contudo, que o cálculo do conjunto K 2 pode não ser uma tarefa fácil,por conta da esperança envolvida. Mais fáceis de se calcular são:

3. O conjunto de todas as decisões x de primeiro estágio para as quais oprograma linear do segundo estágio é admisśıvel para um valor de ξ ∈ Ξfixo1:

K 2(ξ) = {x ∈ Rn

| Q(x, ξ) = v(h(ω) − T(ω)x,ω) < +∞}.4. O conjunto de todas as decisões x de primeiro estágio para as quais o

programa linear do segundo estágio é admisśıvel para “muitos” valoresde ξ ∈ Ξ:

K P 2 = {x ∈ Rn | “∀ξ ∈ Ξ”, Q(x, ξ) < +∞} =

“ξ∈Ξ”K 2(ξ).

Aqui, “ξ ∈ Ξ” significa para todo ξ ∈ Ξ exceto possivelmente para valoresde ξ em um conjunto de probabilidade 0.1Note que v (h(ω) −T(ω)x,ω) pode ser escrito em termos de ξ ∈ Ξ, já que Ξ é o suporte do conjunto

(q(ω),h(ω), t1(ω), . . . , tm(ω)) ∈ R p+m+(m×n) | ω ∈Ω

.


45/97


O propósito do conjunto K P 2 é o de construir um mecanismo que permita

identificar se Q(x) < +∞ sem que, para isto, seja necessário calcular aesperança E [Q(x, ξ)]. Os próximos teoremas descrevem propriedades geomé-tricas de K P 2 e K 2 e estabelecem condições suficientes para que K 2 = K

P 2 .

Teorema 4.1 O conjunto K 2(ξ) é um politopo convexo e fechado paratodo ξ ∈ Ξ e, em particular, K P 2 é fechado e convexo. Se Ξ é finito,então K P 2 também é um politopo e K

P 2 = K 2.

Teorema 4.2 Suponha que W(ω) = W (recurso fixo) e que ξ tenhasegundos momentos finitos. Então:

(a) Se P (ω ∈ Ω | Q(x, ξ(ω)) < +∞) = 1, então Q(x) < +∞.(b) Vale a igualdade K P 2 = K 2 e, em particular, K 2 é fechado e con-

vexo.

(c) Se T(ω) = T = constante, então o conjunto K 2 é um politopo.(d) Se h(ω) e T(ω) são variáveis aleatórias independentes e se o su-

porte da distribuição de T(ω) é um politopo, então K 2 é um po-litopo.

4.4 Propriedades das funções de recurso

Nesta seção apresentaremos, sem demonstrações, as propriedades da fun-ção de segundo estágio Q(x, ξ) = v(h(ω) − T(ω)x,ω) e da função de valoresperado Q(x) = E [v(h(ω) − T(ω)x,ω)] = Eξ [Q(x, ξ)]. O leitor interes-sado pode consultar os livros [03, 13, 14].

Teorema 4.3 Se W(ω) = W (recurso fixo), então Q(x, ξ) é (a) con-vexa e linear por partes em (h(ω), T(ω)) (componentes do vetor

aleatório ξ), (b) côncava e linear por partes em q(ω) e (c) convexae linear por partes para todo x ∈ K = K 1 ∩ K 2.


46/97


Teorema 4.4 Se W(ω) = W (recurso fixo) e ξ tem segundos momen-

tos finitos, então (a) Q é uma função convexa, lipschitziana e finitaem K 2, (b) Q é linear por partes se Ξ é finito e (c) Q é diferenciávelem K 2 se a função distribuição de ξ é absolutamente contı́nua.

4.5 Casos especiais: recurso completo e simples

Dizemos que o modelo de recurso em dois estágios (4.8) tem recurso rela-tivamente completo se toda escolha de x que satisfaz as restrições (rı́gidas)do primeiro estágio também satisfaz as condições de admissibilidade e fini-tude do segundo estágio, isto é, dizemos que (4.8) tem recurso relativamente completo se K 1 ⊆ K 2. Embora a hipótese de recurso relativamente completoseja muito desejável e útil do ponto de vista computacional, pode ser dif́ıcilidentificar se um determinado problema tem ou não recurso relativamentecompleto, já que isto exigiria algum conhecimento dos conjuntos K 1 e K 2.

Existe, contudo, um tipo particular de recurso relativamente completo queé fácil de se identificar a partir da matriz de tecnologia W (determińıstica).Esta forma, denominada recurso completo, ocorre quando a matriz de tec-nologia W de (4.8) satisfaz a seguinte condição:

para todo z ∈ Rm, existe y ≥ 0 tal que Wy = z. (4.12)

Observe que se W satisfaz esta condição, então Q(x, ξ) < +∞ paraqualquer realização de ξ em Ξ. Wets e Witzgall propuseram, em [18], um

algoritmo para verificar se uma matriz W satisfaz ou não (4.12).

Uma outra situação especial é a de recurso simples . Ela ocorre quandoa matriz de tecnologia W é da forma

+I −I , y é dividido em (y, y) e

q(ω) = (q(ω), q(ω)). De fato, se (4.8) tem recurso simples, então vale oseguinte resultado (veja [03], página 92):

Teorema 4.5 Se o modelo de recurso em dois estágios (4.8) tem re-

curso simples e se ξ tem segundos momentos finitos, então Q é finitase, e somente se, q(ω) + q(ω) ≥ 0 com probabilidade 1.


47/97


4.6 Mı́nimos e esperanças

Nesta seção veremos uma reformulação de (4.8) que será útil tanto doponto de vista teórico como do ponto de vista computacional. Considere osdois problemas de otimização:

PL1

=

minx

∈X cx + E miny∈Y {q(ω)y | W(ω)y ∼ h(ω) − T(ω)x} Ax = b =

minx∈X

E

miny∈Y

{cx + q(ω)y | W(ω)y ∼ h(ω) − T(ω)x} Ax = b

e

PL0

=

minx∈X,y(·)∈Y E [cx + q(ω)y(ω)] Ax = bW(ω)y(ω) ∼ h(ω) − T(ω)x, ∀ω ∈ Ω ,onde Y é o conjunto das funções (mensuráveis) y : Ω → R p. Note queexistirão infinitas restrições em PL0 se Ω for um conjunto infinito.

Apesar de “min{·}” e “E [·]” não comutarem (veja o exerćıcio [05] destecaṕıtulo), sob certas condições (por exemplo, Ω finito), vale que

PL1 = PL0.

A demonstração deste fato usa teoria da medida, o que foge do escopo destetexto. Ao leitor interessado, indicamos o livro [17], páginas 16 a 21.

4.7 Cotas para o valor ótimo

Se o agente de decisão pode esperar pelas realizações de ξ para escolhero valor de x, ele então irá resolver cada um dos problemas de otimização

minx∈X f (x, ξ) = cx + miny∈Y {q(ω) | W(ω) = h(ω) − T(ω)x} Ax = b

(4.13)


48/97


um para cada realização posśıvel de ξ. Se

x(ξ) representa a solução deste

problema otimização (que, evidentemente, depende de ξ) então, em média,ele ganhará

WS = Eξ [f (x(ξ), ξ)] = Eξ minx∈X

{f (x, ξ) | Ax = b}

(4.14)

Este é o valor ótimo para a abordagem “espere e veja” (WS = wait and see ).Por outro lado, se o agente de decisão deve fazer a escolha de x antes dasrealizações de ξ, então ele ganhará

RP = minx∈X {Eξ [f (x, ξ)] | Ax = b} . (4.15)resolvendo um modelo de recurso em dois estágios (RP = recourse problem ).

Seja x∗ representa a solução ótima deste problema, então RP = Eξ [f (x∗, ξ)].O valor esperado de informaç˜ ao perfeita (EVPI = expected value of perfect information ) é, por definição, a diferença entre os valores ótimos para asabordagens “espere e veja” e “modelo de recurso”:

EVPI = RP − WS. (4.16)

No problema do fazendeiro, o valor ótimo para a abordagem “espere eveja” foi igual a WS = −R$ 115 406,00 (quando convertido para um pro-blema de minimização), enquanto que para a abordagem de “modelo de re-curso”, o valor ótimo foi igual a RP = −R$ 108 390,00. O valor esperado deinformação perfeita do fazendeiro foi, então, igual a RP−WS = R$ 7 016,00.Esta é a quantidade de dinheiro que o fazendeiro deveria pagar em cada anopara obter uma informaç˜ ao perfeita sobre o clima no pr´ oximo ano. Um bom meteorologista poderia cobrar este valor do fazendeiro para assessor´ a-lo em quest˜ oes clim´ aticas.

Pela definição de x(ξ), segue-se que f (x(ξ), ξ) ≤ f (x, ξ) para todo ξ ∈ Ξe para todo x ∈ X satisfazendo Ax = b. Em particular,

f (x(ξ), ξ) ≤ f (x∗, ξ)para todo ξ ∈ Ξ. Tomando-se a esperança dos dois lados, conclúımos que

WS = Eξ [f (x(ξ), ξ)] ≤ Eξ [f (x∗, ξ)] = RP.

Isto mostra que WS dá uma cota inferior para o valor ótimo de RP (que é oproblema (4.8)). Como corolário, obtemos também que EVPI ≥ 0.


49/97


Para usar a abordagem “espere e veja”, o agente de decis ão deve ser

capaz de (1) resolver cada um dos problemas (4.13) e (2) calcular a médiados valores ótimos correspondentes. Como o problema da mistura mostrou,estas tarefas podem ser muito trabalhosas! Uma alternativa tentadora é a desubstituir todas as variáveis aleatórias pelas suas médias e, então, resolver oproblema correspondente. Este problema é denominado problema do valor esperado ou problema do valor médio:

EV = minx∈X

f (x,

ξ) | Ax = b

(4.17)

onde ξ = Eξ [ξ] representa a média de ξ. Vamos denotar por x( ξ) a soluçãoótima de (4.17), denominada soluç˜ ao do valor esperado. Em prinćıpio, nãoexiste nenhum motivo para esperar que x( ξ) esteja, de alguma maneira,próxima da solução x∗ do modelo de recurso (4.15). O valor da soluç˜ aoestoc´ astica (VSS = value of stochastic solution ) (apresentado no problemado fazendeiro) é o conceito que justamente mede o quão bom (ou o quãoruim) é a decisão x =

x(

ξ) em termos de (4.15). Vamos primeiro definir

o resultado esperado no uso da soluç˜ ao do valor esperado (EEV = Expected

result of using the EV solution ):

EEV = Eξ

f x( ξ), ξ . (4.18)

EEV mede a eficácia da decisão x( ξ), permitindo-se que decisões do segundoestágio sejam escolhidas de maneira ótima como funções de x( ξ) e ξ. O valorda solução estocástica é, então, definida como

VSS = EEV

−RP. (4.19)

O valor de VSS d´ a o custo que se paga quando incertezas s˜ ao ignoradas no processo de decis˜ ao. No problema do fazendeiro, vimos que EEV =−R$ 107 240,00 e RP = −R$ 108 390,00, de modo que VSS = −R$ 1 150,00.

Pela definição de RP, segue-se que Eξ [f (x∗, ξ)] ≤ Eξ [f (x, ξ)] para qual-

quer x ∈ X satisfazendo Ax = b. Em particular,

RP = Eξ [f (x∗, ξ)] ≤ Eξ f ( x( ξ), ξ) = EEV.Isto mostra que EEV dá uma cota superior para o valor ótimo de RP (que

é o problema (4.8)). Como corolário, obtemos também que VSS ≥ 0.


50/97


4.8 O caso Ω finito

Se Ω é finito, digamos Ω = {ω1, . . . ,ωS } ⊆ Rr, o modelo de recurso (4.8),via a equivalência apresentada na seção 4.6, produz o seguinte programalinear (basta abrir a esperança em PL0!) denominada forma estendida de

minimizarx∈X

y1,y2,...,yS ∈Y

cx + p1q1y1 + p2q

2y2 + · · · + pS qS yS

sujeito a Ax = b,T1x + Wy1

∼ h1,

T1x + Wy2 ∼ h2,... . . .

... ...

TS x + WyS ∼ hS ,

(4.20)

onde ps = Pω = ωS

, qs = q(ωs), ys = y(ωs) Ts = T(ωs) e hs = h(ωs).

Aqui estamos supondo que o recurso é fixo (W(ω) = W).

A vantagem deste modelo é que ele é um programa linear. A única des-

vantagem é o seu tamanho: ele possui n + pS variáveis e m1 + mS restriçõesexpĺıcitas (isto é, não contando as posśıveis restrições na definição de X e Y).

Exerćıcios

[01] Mostre que para os valores de p, q, W e Y indicados em cada um dostrês casos na página 36, a função de recuso v em (4.6) obtém as funçõesde penalidade (4.3), (4.4) e (4.5) como casos especiais.

[02] Considere um exemplo de (4.8) onde Q(x, ξ ) = miny≥0 {y | ξy = 1 − x}.Mostre que se ξ tem distribuição triangular em [0, 1] (P(ξ ≤ u) = u2),então K P 2 = K 2.

[03] Mostre que a matriz W =

+I −I satisfaz a condição (4.12).[04] Mostre que a matriz W =

T −I

satisfaz a condição (4.12). Aqui

representa o vetor com todas as componentes iguais a 1.

[05] Considere f (x, ω) = (x − ω)2, onde x ∈ R e ω é uma varíavel aleatóriacom distribuição uniforme no intervalo [0, 1]. Mostre que, para esta


51/97


situação, “min{·}” e “E [·]” não comutam:

E

minx∈R

{f (x, ω)} = minx∈R

E [f (x, ω)]

.


52/97

Caṕıtulo 5

O método L-shaped

O L-shaped é possivelmente o método de resolução e aproximação deproblemas de otimização estocástica mais conhecido e tradicional. Ele seoriginou do método de decomposiç˜ ao de Benders , desenvolvido na década desessenta por J. F. Benders para resolver de maneira mais eficiente problemasde otimização com uma determinada estrutura. Na realidade, o L-shapedpode ser visto como uma aplicação do método de Benders em otimização

estocástica. Esse é o ponto de vista que será adotado nesse texto.

5.1 A decomposição de Benders

Considere o problema de otimização linear abaixo

VAL = minx,y

cT x + qT y

sujeito a Ax = b,Tx + Wy = h

x, y ≥ 0,(5.1)

onde c, q, x e y são vetores em Rn, h e b são vetores de Rm e A, T, W sãomatrizes m × n. O primeiro passo é eliminar a variável y da formulaçãodo problema, criando um subproblema parametrizado por x. Para isso, adecomposição de Benders reescreve o problema da seguinte forma:

VAL = minx

cT x +

Q(x)

sujeito a Ax = b,x ≥ 0,

(5.2)


53/97


onde Q(x) é o valor ótimo do subproblema

Q(x) = miny

qT y

sujeito a Wy = h − Tx,y ≥ 0.

(P)

Dualizando (P), temos o problema (D) definido a seguir:

Q(x) = maxp

pT (h − Tx)

sujeito a W

T

p ≤ q.(D)

Repare que a dualidade tirou a dependência do conjunto admisśıvel D de(D) em relação a x, ou seja, para qualquer escolha de x o conjunto admissı́velde (D) é o mesmo:

D = {p ∈ Rm | WT p ≤ q}.Vamos assumir que o conjunto D é não vazio e denotar seus pontos extremospor p1, . . . , pI e seus raios extremos por r1, . . . , rJ . O problema (D) dá

origem a duas situações distintas:

• Se Q(x) = +∞, então o simplex devolve o raio extremo r de D. Emparticular (r)T (h − Tx) > 0.

• Se Q(x) < +∞, então o simplex devolve um ponto extremo p de D.

Usando o teorema fundamental da programação linear (D.1), podemosreescrever o problema (D) como

Q(x) = minz

z

sujeito a (pi

Documents

OTIMIZACAO ESTOCASTICA - Bernardo PAGNONCELLI e Humberto - III-bienal-sbm-texto