Modulo 1 - Curso de Otimizacao Linear

Prévia do material em texto

Pontifícia Universidade Católica do Rio de Janeiro (PUC-Rio)
Departamento de Engenharia Elétrica (DEE)Departamento de Engenharia Elétrica (DEE)
www.ele.puc-rio.br
Curso de Otimização Linear
aplicado ao Setor Elétricoaplicado ao Setor Elétrico
Módulo 1Módulo 1
Prof. Alexandre Street
1
Setembro de 2010
AgendaAgenda
Módulo 1 – Modelagem de problemas de PL
Módulo 2 – Propriedades das soluções e o Método SimplexMódulo 2 – Propriedades das soluções e o Método Simplex
Módulo 3 – Teoria de dualidade e análise de sensibilidade
Módulo 4 – Decomposição de Benders e PDDE 
2
AgendaAgenda
Módulo 1 – Modelagem de problemas de PL:
historia da Programação Linear;historia da Programação Linear;
modelagem de problemas (foco no setor elétrico: exemplo de contratação de 
energia);
interpretação geométricainterpretação geométrica;
Exercícios com Excel
Módulo 2 – Propriedades das soluções e o Método Simplex
Módulo 3 – Teoria de dualidade e análise de sensibilidade
Módulo 4 – Decomposição de Benders e PDDE 
3
Breve História da PLBreve História da PL
Pré simplex
(1823 e 1911) Fourier e o matemático de la Vallée Poussin escreveram trabalhos muito similares à 
ano19471823 1911 1928/33/39
programação linear, mas não obtiveram o impacto que Dantzig teve pela ausência de interesse em se 
otimizar sistemas grandes: não existia computadores até então.
(1928 e 33) von Neumann e Leontief contribuíram com trabalhos independentes em teoria de jogos e 
d l d i d t i i (I t i d t i t t t d l d L ti fem modelagem da industria americana (Interindustry input-output model – que deu a Leontief o 
Nobel em 1976).
(1939) Kantorovich escreveu sua monografia sobre modelos semelhantes aos da PL, mas foi 
completamente ignorado até duas décadas depois por motivos ideológicos na União Soviéticacompletamente ignorado até duas décadas depois por motivos ideológicos na União Soviética.
(1947) Dantzig formulou o problema do planejamento e logística militar como um PL: buscando deixar 
de lado os procedimentos ad hoc de especialistas utilizados como regras para se selecionar uma 
solução dentro viável. 
(3 de outubro de 1947) Dantzig encontra von Neumann em Princeton para mostrar o simplex e pedir 
sua opinião. Ao invés disso, von Neumman o demosntra o desenvolvimento da teoria de dualidade 
utilizando o Lema de Farkas. 
4
No verão de 1947, Dantzig propôs o método simplex para resolver o problema de planejamento e 
obteve resultados melhores que os obtidos pelo algoritmo proposto por von Neumann.
Breve História da PLBreve História da PL
Logo após o simplexPré simplex
(1949) Zero Symposium of mathematical programming na universidade de Chicago
ano19471823 1911 1928/33/39 1949 1950/51/52 1954
(1949) Zero Symposium of mathematical programming na universidade de Chicago.
(1950) Wolfe, Dantzig e outros desenvolveram soluções para lidar com casos degenerados.
(1951) Karush, Kuhn e Tucker começaram a desenvolver a área de Programação não 
li t é d f di õ d ti lid d b i i i i dlinear, através das famosas condições de otimalidade que receberam as iniciais dos nomes 
desses 3 pesquisadores (KKT). Mais tarde, em 1960, a teoria de dualidade foi estendida para 
problemas não lineares.
(1952) Ch C M ll d l i i li ã i l(1952) Charnes, Cooper e Mellon desenvolvem a primeira aplicação comercial para o 
problema de mistura de tipos de petróleo para a fabricação de gasolina.
(1954) William Orchard-Hays da Rand Corporation escreveu o primeiro código comercial 
para resolver problemas genéricos de programação linear. Muitas das idéias teóricas para se 
compactar a inversa de uma matriz, se aproveitar das formas esparsas e garantir 
estabilidade numérica foram implementadas nesse código. Isso fez com que este código se 
t i i l l d PL d t dé d E difi f PL
5
tornasse o principal solver de PL durante décadas. E modificou a forma com que a PL era 
encarada.
Breve História da PLBreve História da PL
8 anos após o 
simplex
Logo após o simplexPré simplex
(1955) Dantzig e Wolfe começaram a desenvolver o princípio da decomposição por de
19471823 1911 1928/33/39 1949/50/51/52 1955 19621958 1984
(1955) Dantzig e Wolfe começaram a desenvolver o princípio da decomposição por de 
problemas com estruturas em bloco e acoplamento através de restrições “complicadas”. 
Publicaram o artigo Princípios da Decomposição em 1959.
(1955) Dantzig publicou o artigo “Linear Programming under Uncertainty” mas desde 1950(1955) Dantzig publicou o artigo Linear Programming under Uncertainty , mas desde 1950 
Cooper já havia pensado no problema de restrições probabilísticas (Chance Constraints).
(1958) Gomory propôs um algoritmo de planos de corte para resolver problemas de 
programação inteira que combinado com algoritmos de Branch and Bound se mostrou aprogramação inteira, que combinado com algoritmos de Branch and Bound se mostrou a 
técnica mais promissora, até os dias de hoje, para resolver problemas inteiros.
(1962) Benders criou a versão dual de decomposição de Dantzig e Wolfe, para problemas 
com estr t ra em blocos triang lar e acoplamento atra és de ariá eis “complicadas”com estrutura em blocos triangular e acoplamento através de variáveis “complicadas”. 
Proposto inicialmente para resolver problemas de programação inteira mista, rapidamente 
foi adaptado para a Programação Estocástica de grande porte por John Birge (1985) e Mario 
Veiga Pereira (1991)
6
Veiga Pereira (1991).
(1984) Karmarkar propôs o algoritmo de pontos interiores com complexidade polinomial.
AgendaAgenda
Módulo 1 – Modelagem de problemas de PL:
historia da Programação Linear;historia da Programação Linear;
modelagem de problemas (foco no setor elétrico: exemplo de contratação de 
energia);
interpretação geométrica;interpretação geométrica;
Exercícios com Excel
Módulo 2 – Propriedades das soluções e o Método Simplex
Módulo 3 – Teoria de dualidade e análise de sensibilidade
Módulo 4 – Decomposição de Benders e PDDE 
7
Modelagem Matemática (Formulação de um Problema)Modelagem Matemática (Formulação de um Problema)
O processo de modelagem é a parte mais importante para se resolver um 
problema de otimização:problema de otimização:
Em geral, um problema bem formulado não garante que este será facilmente 
resolvido, porém um problema mal formulado certamente será muito mais difícil de 
se resolverse resolver.
Existem muitas classificações para formulações matemáticas:
1. Restritos e irrestritos
2. Lineares e não lineares
3. Convexos e não convexos
4 Combinatoriais4. Combinatoriais
5. Etc...
8
Modelagem Matemática (Formulação de um Problema)Modelagem Matemática (Formulação de um Problema)
Em linhas gerais, existem 4 passos básicos para se modelar um problema:
1. Compreensão do problema
id tifi ã d t l t d j t t N t t l t ã• identificação das partes relevantes que se deseja tratar. Nesta parte, geralmente são
excluídas uma série de relações que não implicam em uma direta, ou substancial,
participação no objetivo do problema.
2 Identificação das variáveis de decisão: x = [x x ]T2. Identificação das variáveis de decisão: x = [x1,...,xn]T
• quais são as variáveis que se deseja obter com a resolução do problema, ou seja, o que se
deseja encontrar (otimizar) e os seus respectivos limites superiores e inferiores.
3 Identificar a função objetivo do problema: f(x)3. Identificar a função objetivo do problema: f(x)
• especificar uma função que, dado uma possível configuração das variáveis de decisão,
reproduza o valor que se deseja maximizar ou minimizar (otimizar): lucro, custo,
confiabilidade, chance de se obter algum resultado, distância de algum nível deconfiabilidade, chance de se obter algum resultado, distância de algum nível de
referência, etc...
4. Identificar as condições que as variáveis devem atender : gi(x) ≤ 0 para i=1,...,m
• para serem válidas (viáveis) de serem escolhidas, através de inequações ou equações.para serem válidas (viáveis) de serem escolhidas, através de inequações ou equações.
• É importante ressaltar que se uma possível solução não atender a algumadas restrições,
isso implica em descartar totalmente esta solução, independentemente do valor da sua
função objetivo. Logo, se existir alguma possibilidade de discussão sobre o trade-off
9
entre uma possível violação e o valor da função objetivo, isso deve ser incorporado no
modelo!
Modelagem Matemática (Formulação de um Problema)Modelagem Matemática (Formulação de um Problema)
Problemas de programação linear (PL):
Forma compacta matricial:
Maximizar≥ ⋅: ⋅ ≤ 
Revisar:
1. Multiplicação de matriz
2. Combinação linear, convexa e cônica
3. Gradiente e curvas de nível
Forma extensa:
. : ⋅ ≤ 3. Gradiente e curvas de nível
4. Conjunto convexo: poliedros e envoltórias
5. Função convexa e côncava: max e min
6. Conjunto de nível
7. Otimalidade de problemas convexos e de PL.Forma extensa:
Maximizar ⋅
p
a a =1: ⋅ ≤ ∀ = 1. : =1 ≤ ∀ = 1, … ,≥ 0 ∀ = 1, … ,
10
Modelagem Matemática (Formulação de um Problema)Modelagem Matemática (Formulação de um Problema)
Exemplo: Problema da produção
Um produtor de grande escala de Armários (produto “A”) e Berços (produto “B”)
tem que decidir quanto deve produzir de maneira otimizada, utilizando de Madeira
(insumo “M”) e Ferro (insumo “F”) apenas o que tem em estoque.( ) ( ) p q q
Sabe-se que a receita líquida com a venda de Armários e berços é respectivamente
igual a 4 MM$/mil-unid. e 3 MM$/mil-unid. vendidas.
A tabela a seguir mostra a quantidade de insumos total e a matriz insumo-produtoA tabela a seguir, mostra a quantidade de insumos total e a matriz insumo produto
(matriz tecnológica), que determina a quantidade de insumos necessária para se
produzir uma certa quantidade de cada produto:
Produto A 
(103 unid.)
Produto B 
(103 unid.)
Qt em Estoque
I MInsumo M
(103 m2) 2 1 4
Insumo F 1 2 4
11
(Ton.) 1 2 4
Modelagem Matemática (Formulação de um Problema)Modelagem Matemática (Formulação de um Problema)
Exemplo: Problema da produção
Variáveis de decisão: quantidade a produzir de cada produto xA e xB (mil unidades).
Função objetivo: f(xA, xB) = 4xA + 3xB
Restrições:
• A quantidade de madeira utilizada não pode ser maior que o estoque:A quantidade de madeira utilizada não pode ser maior que o estoque:
2xA + 1xB ≤ 4
• A quantidade de ferro utilizada não pode ser maior que o estoque:
1xA + 2xB ≤ 41xA + 2xB ≤ 4
• Não é permitido produzir negativo: xA ≥ 0, xB ≥ 0
Produto A 
(103 unid.)
Produto B 
(103 unid.)
Qt em Estoque
Insumo M
(103 m2) 2 1 4
Insumo F 1 2 4
12
(Ton.) 1 2 4
Modelagem Matemática (Formulação de um Problema)Modelagem Matemática (Formulação de um Problema)
Exemplo: Problema da produção
Variáveis de decisão: quantidade a produzir de cada produto xA e xB (mil unidades).
Função objetivo: f(xA, xB) = 4xA + 3xB
Restrições:Restrições:
• A quantidade de madeira utilizada não pode ser maior que o estoque:
2xA + 1xB ≤ 4
A tid d d f tili d ã d i t• A quantidade de ferro utilizada não pode ser maior que o estoque:
1xA + 2xB ≤ 4
• Não é permitido produzir negativo: xA ≥ 0, xB ≥ 0
Maximizar≥ 4 ⋅ + 3 ⋅ (1)≥. : 2 ⋅ + 1 ⋅ ≤ 4 (1.1)1 ⋅ + 2 ⋅ ≤ 4 (1.2)
13
Interpretação GráficaInterpretação Gráfica
Exemplo: Problema da produçãoMaximizar 4 + 3 (1)Maximizar≥ 4 ⋅ + 3 ⋅ (1). : 2 ⋅ + 1 ⋅ ≤ 4 (1.1)1 ⋅ + 2 ⋅ ≤ 4 (1.2)( )
xB(1.1)
Em (1.1), quando xA = 0, para atender na igualdade, xB = 4
4
( ), q A , p g , B
Em (1.1), quando xB = 0, para atender na igualdade, xA = 4
xA2
14
Interpretação GráficaInterpretação Gráfica
Exemplo: Problema da produçãoMaximizar 4 + 3 (1)Maximizar≥ 4 ⋅ + 3 ⋅ (1). : 2 ⋅ + 1 ⋅ ≤ 4 (1.1)1 ⋅ + 2 ⋅ ≤ 4 (1.2)
xB(1.1)
( )
4
v = [0,4]T – [2,0]T = [-2,4]T
xA2
15
Interpretação GráficaInterpretação Gráfica
Exemplo: Problema da produçãoMaximizar 4 + 3 (1)Maximizar≥ 4 ⋅ + 3 ⋅ (1). : 2 ⋅ + 1 ⋅ ≤ 4 (1.1)1 ⋅ + 2 ⋅ ≤ 4 (1.2)( )
xB(1.1) 2 1 −2 4 + 4 0
4v = [-2,4]
T 1 ⋅ = 2,1 ⋅ 4 = −4 + 4 = 0
a1 = [2,1]T
x2
16
xA2
Interpretação GráficaInterpretação Gráfica
Exemplo: Problema da produçãoMaximizar 4 + 3 (1)Maximizar≥ 4 ⋅ + 3 ⋅ (1). : 2 ⋅ + 1 ⋅ ≤ 4 (1.1)1 ⋅ + 2 ⋅ ≤ 4 (1.2)( )
xB(1.1) Definição: uma solução viável é um 
ponto que atendem a todas as restrições 
4
2
(1.2)
C j t d t iá i P lit
p q ç
simultaneamente.
2 Conjunto de pontos viáveis: Politopo
: Vértice ou ponto extremo do politopo
xA2 4
p p p
17
Interpretação GráficaInterpretação Gráfica
Exemplo: Problema da produçãoMaximizar 4 + 3 (1)Maximizar≥ 4 ⋅ + 3 ⋅ (1). : 2 ⋅ + 1 ⋅ ≤ 4 (1.1)1 ⋅ + 2 ⋅ ≤ 4 (1.2)
Definição: Curva de nível da função 
objetivo é o lugar em que todos os 
xB(1.1)
( )
j g q
pontos apresentam o mesmo valor de 
função objetivo (z – dado e constante)
4
2
(1.2)
[4,3]T
2
z3 = 25z0 = 0
z1 x aT⋅x = aT⋅y = aT⋅w = cte.
xA2 4 a y
18
w
Interpretação GráficaInterpretação Gráfica
Exemplo: Problema da produçãoMaximizar 4 + 3 (1)Maximizar≥ 4 ⋅ + 3 ⋅ (1). : 2 ⋅ + 1 ⋅ ≤ 4 (1.1)1 ⋅ + 2 ⋅ ≤ 4 (1.2)
Teorema: Se o conjunto viável não for 
vazio, um ou mais vértices serão pontos 
xB(1.1)
( )
, p
maximais (ótimos).4
2
(1.2)
Solução ótima do problema:2
4/3
Solução ótima do problema: 
produzir 1333 armários e berços!
xA2 44/3
* 16/3 + 12/3 28/3 9 333 MMR$
19
z = 16/3 + 12/3 = 28/3 = 9.333 MMR$
Interpretação GráficaInterpretação Gráfica
Exemplo: Problema da produçãoMaximizar 4 + 2 (1)Maximizar≥ 4 ⋅ + 2 ⋅ (1). : 2 ⋅ + 1 ⋅ ≤ 4 (1.1)1 ⋅ + 2 ⋅ ≤ 4 (1.2)
Definição: o problema tem solução 
degenerada quando o gradiente da 
xB(1.1)
( )
função objetivo for perpendicular a uma 
das faces ou facetas do politopo.
4
2
(1.2)
No caso degenerado o problema tem um2
4/3
No caso degenerado, o problema tem um 
conjunto não enumerável (“infinito”) de 
ótimos, mas certamente um conjunto 
finito de vértices estará contido nele!
xA2 44/3
finito de vértices estará contido nele!
20
z* = f(4/3,4/3) = 16/3 + 8/3 = 8 = f(2,0) 
Despacho Físico: O que é operar o sistema?Despacho Físico: O que é operar o sistema?
Operar o sistema é definir a cada etapa do tempo quais usinas serãoOperar o sistema é definir, a cada etapa do tempo, quais usinas serão 
acionadas para atender a demanda de energia elétrica
Entretanto os recursos disponíveis (ex: usinas) possuem capacidades Gi
diferentes e, sobretudo, custos de operação distintos ci
Critério: atender a demanda d ao menor custo operativo possível
21
Despacho Físico: Sistema Puramente TérmicoDespacho Físico: Sistema Puramente Térmico
Exemplo: 
Suponha dois geradores com custos variáveis de c1=100 e c2=150 R$/MWh
Capacidade Máxima G1=100 e G2=50 MW
Qual o despacho ótimo para uma determinada hora do dia com demanda 
d 120 MWh?d=120 MWh?
custo (R$/MWh)
150
50 MW
100 MW
100
Quantidade (MWh)120
100 MW
22
Despacho Físico: Sistema Puramente TérmicoDespacho Físico: Sistema Puramente Térmico
Exemplo: 
Suponha dois geradores com custos variáveis de c1=100 e c2=150 R$/MWh
Capacidade Máxima G1=100 e G2=50 MW
Qual o despacho ótimo para uma determinada hora do dia com demanda 
d 120 MWh?d=120 MWh?
custo (R$/MWh)
150
20
MW
100 MW
100
Quantidade (MWh)120
100 MW
23
Despacho Físico: Sistema Puramente TérmicoDespacho Físico: Sistema Puramente Térmico
Minimizar 100 ⋅ 1 + 150 ⋅ 2 (2)Exemplo: Interpretação gráfica do modelo de despacho ótimo:Minimizar≥ 100 1 + 150 2 (2). : 1 + 2 ≥ 120 (2.1)1 ≤ 100 (2.2)( )2 ≤ 50 (2.3)
g2
(2 1)
120
(2.1)
24
g1120
Despacho Físico: Sistema Puramente TérmicoDespacho Físico: Sistema Puramente Térmico
Minimizar 100 ⋅ 1 + 150 ⋅ 2 (2)Exemplo: Interpretação gráfica do modelo de despacho ótimo:Minimizar≥ 100 1 + 150 2 (2). : 1 + 2 ≥ 120 (2.1)1 ≤ 100 (2.2)( )2 ≤ 50 (2.3)
g2
(2 1)
(2.2)
120
(2.1)
(2.3)
Solução ótima:Solução ótima:
g* = [g1*,g2*]T = [100, 20]T
25
g1120100
Despacho Físico: Sistema Puramente TérmicoDespacho Físico: Sistema Puramente Térmico
Minimizar 100 ⋅ 1 + 150 ⋅ 2 (2)Exemplo: Interpretação gráfica do modelo de despacho ótimo:Minimizar≥ 100 1 + 150 2 (2). : 1 + 2 ≥ 120 (2.1)1 ≤ 100 (2.2)( )2 ≤ 50 (2.3)
g2
C i h di ã t á iCaminhar na direção contrária 
ao gradiente da função objetivo 
(-cT) minimiza o custo.
26
g1- cT = [-100,-150]Despacho Físico: Sistema Puramente TérmicoDespacho Físico: Sistema Puramente Térmico
Minimizar 100 ⋅ 1 + 150 ⋅ 2 (2)Exemplo: Interpretação gráfica do modelo de despacho ótimo:Minimizar≥ 100 1 + 150 2 (2). : −1 ⋅ 1 − 1 ⋅ 2 ≤ −120 (2.1)1 ⋅ 1 ≤ 100 (2.2)( )1 ⋅ 2 ≤ 50 (2.3)
g2 Condições de Otimalidade (KKT): ç ( )
1. O cone formado pelos gradientes das 
restrições ativas contém a direção 
do objetivo do nosso problema (-c). 
2. Ser um ponto viável.
3. complementariedade... (mais adiante)
T [ 1 1]
a2T= [1,0]
27
g1- cT
a1T= [-1,-1]
Despacho Físico: Sistema Puramente TérmicoDespacho Físico: Sistema Puramente Térmico
Minimizar 100 ⋅ 1 + 150 ⋅ 2 (2)Exemplo: Interpretação gráfica do modelo de despacho ótimo:Minimizar≥ 100 1 + 150 2 (2). : −1 ⋅ 1 − 1 ⋅ 2 ≤ −120 (2.1)1 ⋅ 1 ≤ 100 (2.2)( )1 ⋅ 2 ≤ 50 (2.3)
Condições de Otimalidade (KKT):ç ( )
podem ser associadas a condições de 
equilíbrio, onde um corpo pontual de 
massa finita é solto dentro do politopo.
28
Despacho Físico: Sistema Puramente TérmicoDespacho Físico: Sistema Puramente Térmico
∗( ) Mi (3)Qual o custo adicional do próximo MWh a ser?∗( ) = Min≥ ⋅=1 (3)≥ (3 1). : =1 ≥ (3.1)≤ ∀ = 1, … , (3.2)
custo (R$/MWh)
20
100
150
20
MW
100 MW
29
Quantidade (MWh)120
Despacho Físico: Sistema Puramente TérmicoDespacho Físico: Sistema Puramente Térmico
Qual o custo adicional do próximo MWh a ser atendido? 
∗( ) ∗( ) ∗( )
Δ ∗( ) = ∗( ) + 1 ∗( ) =
Δ ∗( ) = ∗( + 1) − ∗( ) 
Δ ( ) = ( ) + 2 ⋅ 1 − ( ) = 2
custo (R$/MWh)
150
1
MW
20
MW
100 MW
100
Quantidade (MWh)120
100 MW
121
30
Despacho Físico: Sistema Puramente TérmicoDespacho Físico: Sistema Puramente Térmico
Qual o custo marginal de atendimento à demanda? 
∗( )
∗( ) ∗( + Δ) − ∗( )(R$/MWh)150
∗( )
 ( ) = limΔ→0+ ( + Δ) ( )Δ100
custo (R$/MWh)
d (MWh)100
120
100
150 ∗( ) = ∗<1
MW
20
MW
100 MW
<−
31
Quantidade (MWh)120 121
Despacho Físico: Sistema Puramente TérmicoDespacho Físico: Sistema Puramente Térmico
Propriedades da função Custo Ótimo 
de Operação em função da demanda:
(R$/MWh)∗( ) (R$/MWh)
100
150
( )
 ∗( ) = Min≥ ⋅ 100≥ =1. : ≥
d (MWh)100
(R$)∗( )=1≤ ∀ = 1, … ,
1. é linear por partes;
2. tem primeira derivada descontínua;
( $)( )
c2=150
3. é crescente;
4. é convexa; 104
c1=100
32
100 d (MWh)
Despacho Físico: Sistema Puramente TérmicoDespacho Físico: Sistema Puramente Térmico
Se a demanda for maior que a soma das capacidades máximas, então o 
problema será inviável!
(2.1)
(2.2)
g2
120
Não existe região viável!
(2.3)50 ( )
33
g1120100
Despacho Físico: Sistema Puramente TérmicoDespacho Físico: Sistema Puramente Térmico
Se a demanda for maior que a soma das capacidades máximas, então o 
problema será inviável!
Na pratica o problema não é inviável, mas uma fração da demanda não será 
atendida: “corte de carga” ou déficit (diferente de racionamento).
(2.1)
(2.2)
A redução de demanda é realizada 
através de uma variável que relaxa a 
restrição o mínimo necessário para que o 
g2
120
ç p q
problema seja viável. Em troca, a função 
objetivo é penalizada por um custo de 
déficit.
(2.3)50
O custo de déficit deve ser maior que o 
custo de qualquer outra térmica.
A restrição deixa de ser hard e passa a 
ser soft.
34
g1120100
Despacho Físico: Sistema Puramente TérmicoDespacho Físico: Sistema Puramente Térmico
Se a demanda for maior que a soma das capacidades máximas, então o 
problema será inviável!
Na pratica o problema não é inviável, mas uma fração da demanda não será 
atendida: “corte de carga” ou déficit (diferente de racionamento).
(2.1)
(2.2) ∗( ) = Min ⋅ + ⋅
g2
120
( ) = Min≥≥0 ⋅=1 + ⋅+ ≥
(2.3)50
. : =1 + ≥≤ ∀ = 1, … ,
35
g1120100
Despacho Físico: Sistema Puramente TérmicoDespacho Físico: Sistema Puramente Térmico
C l ãConclusão:
Desacoplado no tempo: uma decisão operativa tomada hoje 
não afeta o custo operativo da próxima etapa;
As unidades têm um custo direto de operação: o custo 
operativo de uma unidade depende somente de seu próprio 
nível de geração e não da produção das outras unidades.nível de geração e não da produção das outras unidades.
36
Despacho Físico: Sistema HidroDespacho Físico: Sistema Hidro--TérmicoTérmico
Características do sistema Hídricos com reservatórios:
Usinas hidrelétrica podem estar em cascatas
a1tUsinas hidrelétrica podem estar em cascatas
Balanço hídrico
Volume do reservatório no final de t (vt) é 
1
2igual ao volume no final de t-1 (vt-1), mais 
a afluência lateral ao longo de t (at) e a 
montante, menos o turbinamento (ut) e 
2
a2t
s1t+u1t
t
vertimento (st) ao longo de t. s2t+u2t1 = −11 + 1 − 1 − 1 ∀ 
Limites de turbinamento e vertimento
2 = −12 + 2 + ( 1 + 1) − 2 − 2 ∀
Limites de defluência máxima e mínima
navegabilidade, recreação, alagamento, ...
37
≤ + ≤ ̅ ∀ , 
Despacho Físico: Sistema HidroDespacho Físico: Sistema Hidro--TérmicoTérmico
Função Objetivo:
Hidrelétricas possuem um custo praticamente
a1tHidrelétricas possuem um custo praticamente 
zero (desprezíveis se comparados às 
termelétricas, ~ 3 R$/MWh). 
L ã ã id d di t t f ã
1
2Logo não são consideradas diretamente na função 
objetivo.
Atendimento à demanda:
2
a2t
s1t+u1t
Geração termelétrica + a energia proveniente do 
volume turbinado de cada hidrelétrica + déficit.
s2t+u2t
O coeficiente de produção de uma usina pode ser 
1 + 2 + 1 ⋅ 1 + 2 ⋅ 2 + ≥ ∀ 
p ç p
simplificado por uma constante (em MWh/hm3), mas 
na prática depende também da altura de queda 
(mapeada no volume do reservatório)
( ) ⋅ 1 
38
(mapeada no volume do reservatório).
Despacho Físico: Sistema HidroDespacho Físico: Sistema Hidro--TérmicoTérmico
M(3)
UTE: Conjunto de Unidades Termelétricas
UHE: Conjunto de Unidades Hidrelétricas
1 2
M(i): Conjunto de hidrelétricas a montante de i
Ex: se i = 3, M(3)={1,2}; se i = 1, M(1)={∅} 3Minimizar≥, ≥≥0 ⋅∈ + ⋅∈ ≥0. : ∈ + ⋅∈ + ≥ ∀ ∈= −1 + + +∈ ( ) − − ∀ ∈ , ∈≤ ≤ ; ≤ ≤ ̅ ; ≤ ≤ ∀ ∈ ∈≤ ≤ ; ≤ ≤ ; ≤ ≤ ∀ ∈ , ∈⋅ ≤ ∀ ∈ , ∈≤ + ≤ ̅ ∀ ∈ , ∈
39
,≤ ≤ ̅ ∀ ∈ , ∈
Despacho Físico: Sistema HidroDespacho Físico: Sistema Hidro--TérmicoTérmico
Conclusão:
Acoplado no tempo: uma decisão operativa tomada hoje não 
pode ser analisada fora de um horizonte temporal, pois esta 
afeta o custo operativo da próxima etapa através dos 
volumes dos reservatórios
O volume de água armazenada hoje pode representar uma g j p p
economia no uso de combustíveis das termelétricas e de cortes 
de carga (déficits) em etapas posteriores.
O importante é minimizar o custo global ao longo do horizonte.O po ta te é a o custo g oba ao o go do o o te
As unidades hidrelétrica têm um custo indireto de 
oportunidade no uso da água: o custo de economizar o uso 
de combustível das termelétricas e de possíveis déficitsde combustível das termelétricas e de possíveis déficits 
futuros
40
Despacho Físico: Sistema HidroDespacho Físico: Sistema Hidro--TérmicoTérmico
Custo de oportunidade da água (1 hora):
Análise do problema de dois períodos e uma UHE: T = {1,2} e UHE={1}
Não existe restrição de defluência mínima, nem turbinamento mínimo
2∗( 1) = Min≥v2,u2,s2,r2≥0 1 ⋅ 21 + 2 ⋅ 22 + ⋅ 2 . : 21 + 22 + ⋅ 2 + 2 ≥ 22 + 2 + 2 = 1 + 2≤ ≤ ≤2 ≤ ; 2 ≤ ; 2 ≤⋅ 2 ≤ 1 ≤ 1 ≤ 1 ; 2 ≤ 2 ≤ 2≤ 2 ≤ ; ≤ 2 ≤
41
Despacho Físico: Sistema HidroDespacho Físico: Sistema Hidro--TérmicoTérmico
Custo de oportunidade da água (1 hora):
Suponha um rendimento de 1 MWh/hm3 para a turbina da hidrelétrica
Potência máxima da hidrelétrica igual a 200 MW
Uma afluência de 10 hm3
2∗( 1) = Min≥ 100 ⋅ 21 + 150 ⋅ 22 + 500 ⋅ 2
Demanda igual a 120 MWh 
2( 1) ≥v2,u2,s2,r2≥0 2 2 2. : 21 + 22 + 1 ⋅ 2 + 2 ≥ 120102 + 2 + 2 = 1 + 100 ≤ 2 ≤ 500 ; 0 ≤ 2 ≤ 100 ; 0 ≤ 2 ≤ 2001 ⋅ 2 ≤ 200 0 ≤ 21 ≤ 100 ; 0 ≤ 22 ≤ 50
42
Despacho Físico: Sistema HidroDespacho Físico: Sistema Hidro--TérmicoTérmico
Custo de oportunidade da água (1 hora):
O limite inferior para a função objetivo é zero (variáveis positivas)
Se podemos atender a demanda somente com energia da hidrelétrica, o 
custo será zero (gerar com hidro “custa zero”)
Suponha que v 110 hm3
2∗( 1)= Min 100 ⋅ 21 + 150 ⋅ 22 + 500 ⋅ 2
Suponha que v1 = 110 hm3
2( 1) ≥v2,u2,s2,r2≥0 2 2 2. : 21 + 22 + 1 ⋅ 2 + 2 ≥ 1202 + 2 + 2 = 1 + 100 ≤ 2 ≤ 500 ; 0 ≤ 2 ≤ 100 ; 0 ≤ 2 ≤ 2001 ⋅ 2 ≤ 2001 2 ≤ 200 0 ≤ 21 ≤ 100 ; 0 ≤ 22 ≤ 50
43
Despacho Físico: Sistema HidroDespacho Físico: Sistema Hidro--TérmicoTérmico
Custo de oportunidade da água (1 hora):
O limite inferior para a função objetivo é zero (variáveis positivas)
Se podemos atender a demanda somente com energia da hidrelétrica, o 
custo será zero (gerar com hidro custa zero)
Suponha que v 110 hm3
2∗( 1) = Min 100 ⋅ 210 + 150 ⋅ 220 + 500 ⋅ 20
Suponha que v1 = 110 hm3
2( 1) ≥v2,u2,s2,r2≥0 2 2 2. : 210 + 220 + 1 ⋅ 2120 + 20 ≥ 12020 + 2120 + 20 = 1200 ≤ 20 ≤ 500 ; 0 ≤ 20 ≤ 100 ; 0 ≤ 2120 ≤ 2001 ⋅ 2120 ≤ 2001 2120 ≤ 200 0 ≤ 210 ≤ 100 ; 0 ≤ 220 ≤ 50
44
Despacho Físico: Sistema HidroDespacho Físico: Sistema Hidro--TérmicoTérmico
Custo de oportunidade da água (1 hora):
Para cada valor inicial que o volume do reservatório pode assumir no 
segundo período (v1 ∈ [0,500] hm3), devemos “abater da demanda” a 
quantidade de geração hídrica máxima e realizar o despacho 
termelétrico remanescente.
2∗( 1) = Min≥v2,u2,s2,r2≥0 100 ⋅ 21 + 150 ⋅ 22 + 500 ⋅ 2 
(R$)2∗( 1) v2,u2,s2,r2≥0. : 21 + 22 + 2 ≥ 120 − min{200, 1 + 10} 2 + 2 + 2 = 1 + 100 ≤ 2 ≤ 500 ; 0 ≤ 2 ≤ 100 ; 0 ≤ 2 ≤ 200
104
c2=-150
2 2 21 ⋅ 2 ≤ 2000 ≤ 21 ≤ 100 ; 0 ≤ 22 ≤ 501.15x104
110
104
v1 (hm3)
c1=-100
10
45
Despacho Físico: Sistema HidroDespacho Físico: Sistema Hidro--TérmicoTérmico
Custo de oportunidade da água (1 hora):
O custo marginal de operação com relação ao volume inicial de um 
determinado período (no caso t=2), reflete o custo de oportunidade (em 
R$/MWh) da água no período anterior.
1 = 2∗( 1)1 
(R$)2∗( 1) (R$/MWh)− 2∗( 1)1
104
c2=-150
100
1501.15x104
110
104
v1 (hm3)
c1=-100
10 110
100
v1 (hm3)10
46
Energia Firme de um sistemaEnergia Firme de um sistema
A energia firme de um sistema hídrico corresponde a maior demanda que este 
sistema consegue atender de maneira “firme” (constante “segura” “garantida”)sistema consegue atender de maneira firme (constante, segura , garantida ).
A energia firme do sistema é superaditiva
Benefício não só da diversidade hidrológica 1 2
Como da regularização das cascatas
1
3
2
( ) ≥ ({ }) 
3
Maxd≥0
∈
d≥0, ≥. : ≤ ⋅∈ ∀ ∈∈= −1 + + +∈ ( ) − − ∀ ∈ , ∈≤ ≤ ≤ + ≤ ≤ ≤ ∀ ∈ ∈
47
≤ ≤ ; ≤ + ≤ ; ≤ ≤ ∀ ∈ , ∈
Energia Firme de um sistemaEnergia Firme de um sistema
A energia firme de um sistema hídrico corresponde a maior demanda que este 
sistema consegue atender de maneira “firme” (constante “segura” “garantida”)sistema consegue atender de maneira firme (constante, segura , garantida ).
A energia firme do sistema é superaditiva
Como repartir esse benefício sinérgico? 1 21
3
2( ) ≥ ({ }) 
3∈
Maxd≥0, ≥ mint∈T ⋅∈: − − + + + = ∀ ∈ ∈. : − −1 − +∈ ( ) + + = ∀ ∈ , ∈≤ ≤ ; ≤ ≤ ̅ ; ≤ ≤ ∀ ∈ , ∈
48
Energia Firme de um sistemaEnergia Firme de um sistema
1 3Usinas Vol INI Vol Max Vol Min Turb max Deflu min Rend Med
1 100 200 20 20 0 1
2 4
1 100 200 20 20 0 1
2 25 50 5 20 0 1
3 25 50 5 20 0 1
4 100 200 20 20 0 1
5 50 100 10 80 0 1
5
Total 300 600 60 160 0
18 0
20.0
Usina 1 Usina 2 Usina 3 Usina 4 Usina 5
1.2
1.4
m
éd
ia
 
8.0
10.0
12.0
14.0
16.0
18.0
m
3/
s
0.6
0.8
1.0
or
 p
ar
a 
o 
cic
lo
 d
a 
an
ua
l
0.0
2.0
4.0
6.0
8.0
1 2 3 4 5 6 7 8 9 10 11 12
0.0
0.2
0.4
1 7 13 19 25 31 37 43 49 55 61 67 73 79 85 91 97 03 09 15
m
ul
tip
lic
ad
o
49
1 2 3 4 5 6 7 8 9 10 11 12
meses
2 3 3 4 4 5 6 6 7 7 8 9 9 1 1 1
120 meses
Energia Firme Individual (cada usina separadamente)Energia Firme Individual (cada usina separadamente)
1 3
Usinas Vol INI Vol Max Vol Min Turb max Deflu min Rend Med
1 100 200 20 20 0 1
2 25 50 5 20 0 1
2 4
3 25 50 5 20 0 1
4 100 200 20 20 0 1
5 50 100 10 80 0 1
Total 300 600 60 160 0
5
0.016
0.018
0.02
200.0
250.0
Período Crítico Usina 1
Período Crítico Usina 2
Volume Usina 1
Volume Usina 2
0.012
0.014
0.0 6
150.0
00.0
E i Fi
0.006
0.008
0.01
100.0
m
3
Usinas
Energia Firme 
Individual
1 11.00
2 4.84
3 4.84
0
0.002
0.004
0 0
50.0
4 11.00
5 5.57
Total 37.23
50
00.0
1 5 9 13 17 21 25 29 33 37 41 45 49 53 57 61 65 69 73 77 81 85 89 93 97 10
1
10
5
10
9
11
3
11
7
meses (120 ao total)
Energia Firme do SistemaEnergia Firme do Sistema
1 3
Usinas Vol INI Vol Max Vol Min Turb max Deflu min Rend Med
1 100 200 20 20 0 1
2 25 50 5 20 0 1
3 25 50 5 20 0 1
2 4
3 25 50 5 20 0 1
4 100 200 20 20 0 1
5 50 100 10 80 0 1
Total 300 600 60 160 0
5
0 012
0.014
0.016
200.0
250.0
Período Crítico Sistema
Volume Usina 1
Volume Usina 2
Volume Usina 3
Volume Usina 4
Volume Usina 5
0 008
0.010
0.012
150.0
m
3 Energia Firme 
0.004
0.006
0.008
100.0
m
Usinas
Energia Firme 
Individual
Sistêmica 
(rateio)
1 11.00
2 4.84
3 4.84
0.000
0.002
0.0
50.0 4 11.00
5 5.57
Total 37.23 74.71
Diferença = 37.48
101%
51
1 5 9 13 17 21 25 29 33 37 41 45 49 53 57 61 65 69 73 77 81 85 89 93 97 10
1
10
5
10
9
11
3
11
7
meses (total 120)
101%
Energia Firme do Sistema: Código (Energia Firme do Sistema: Código (XpressXpress MOSEL)MOSEL)
!Minima Demanda em todos os periodos
forall(t in H) DemandaFirme(t):= 
d <= sum(i in UHE)rend(i)*u(t,i)d sum(i in UHE)rend(i) u(t,i)
!Balanco hidrico em t=1
forall(i in UHE, t in H | t=1) BalancoH(i,t):= 
v(t,i) = Vini(i) + a(t,i) + sum(j in UHE)(u(t,j)+s(t,j))*M(i,j) - s(t,i) - u(t,i)( , ) ( ) a( , ) su (j U )(u( ,j) s( ,j)) ( ,j) s( , ) u( , )
!Balanco hidrico em t>1
forall(i in UHE, t in H | t>1) BalancoH(i,t):= 
v(t,i) = v(t-1,i) + a(t,i) + sum(j in UHE)(u(t,j)+s(t,j))*M(i,j) - s(t,i) - u(t,i)( , ) ( , ) ( , ) (j )( ( ,j) ( ,j)) ( ,j) ( , ) ( , )
forall(i in UHE, t in H) DefluMin(i,t):= u(t,i) + s(t,i) >= Fmin(i)
forall(i in UHE, t in H) v(t,i) <= Vmax(i)
forall(i in UHE, t in H) v(t,i) >= Vmin(i)
forall(i in UHE, t in H) u(t,i) <= Umax(i)
maximize(d)
52
Contratação ótima sob incertezaContratação ótima sob incerteza
Uma empresa de geração de energia elétrica, proprietária de uma usina 
hidrelétrica de 100 MWmédios de Garantia Física (GF), analisa uma oferta de 
contratação para o mês seguinte no ACL;
O preço oferecido pelo consumidor foi de 120 R$/MWh para todo o lastro 
(GF) da hidrelétrica(GF) da hidrelétrica.
A decisão que o gerador deve tomar é: quanto pré-vender através desse 
contrato (Q = energia contratada).
Os riscos: a produção (G) e o preço de curto (π) prazo são incertos.
G 115 MW éd 20 R$/MWh
Q?
1 G1=115 MWméd. e π1 = 20 R$/MWh90%
Q?
2 G2=80 MWméd. e π2 = 600 R$/MWh
10%
53
Contratação ótima sob incertezaContratação ótima sob incerteza
A receita de um gerador contratado por quantidade é dada pela parcela fixa 
do contrato mais a diferença entre a geração e o montante contratado 
negociado no curto prazo, em cada cenário i=1, 2:= ⋅ + ( − ) ⋅
Podemos agrupar os termos que dependem da decisão de contratação:( ) +
No cenário i=1, termos a seguinte expressão de renda em R$/hora: 
= ( − ) ⋅ + ⋅
Já no cenário i 2 termos para cada hora do mês a seguinte renda:
1 = (120 − 20) ⋅ + 115 ⋅ 20 = 100 ⋅ + 2300 
Já no cenário i=2, termos para cada hora do mês, a seguinte renda:
2 = (120 − 600) ⋅ + 80 ⋅ 600 = −480 ⋅ + 48000 
54
Contratação ótima sob incertezaContratação ótima sob incerteza
Em média a renda será 90% a renda do cenário 1 + 10% a do cenário 2:0 90 90 + 20700.90 ⋅ 1 = 90 ⋅ + 2070
0 10 48 + 4800 ( ) = 42 ⋅ + 6870 +$0.10 ⋅ 2 = −48 ⋅ + 4800
48000 ℎ
12300 R
2300
12300
R2
R1
E(R)
55
Q (MWméd.)100
2
Contratação ótima sob incertezaContratação ótima sob incerteza
Como tomar decisões sob incerteza?
Se conhecemos a distribuição dos parâmetros que representam aSe conhecemos a distribuição dos parâmetros que representam a 
incerteza, uma primeira abordagem poderia ser a de maximizar o valor 
esperado da renda:MaximizarQ≥0 ( ). : ≤ 100 
56
Contratação ótima sob incertezaContratação ótima sob incerteza
Como tomar decisões sob incerteza?
Se conhecemos a distribuição dos parâmetrosque representam aSe conhecemos a distribuição dos parâmetros que representam a 
incerteza, uma primeira abordagem poderia ser a de maximizar o valor 
esperado da renda:MaximizarQ≥0 ( ). : ≤ 100 $ Q*=100
48000 ℎ
12300 R 90% de chance!!!
2300
12300
R2
R1
E(R)
90% de chance!!!
10% de chance!!!
57
Q (MWméd.)Q*=100
2
Contratação ótima sob incertezaContratação ótima sob incerteza
Como tomar decisões sob incerteza?
Se conhecemos a distribuição dos parâmetros que representam aSe conhecemos a distribuição dos parâmetros que representam a 
incerteza, uma primeira abordagem poderia ser a de maximizar o valor 
esperado da renda:MaximizarQ≥0 ( ). : ≤ 100 $ Q*=100
48000 ℎ
Jogue 4 vezes seguida uma moeda, 
a probabilidade de sair cara nas 
quatro jogadas é menor que
12300 R 90% de chance
quatro jogadas é menor que 
acontecer R2!
2300
12300 R1
E(R)
90% de chance
E se acontecer R2?
58
Q (MWméd.)Q*=100
2
Contratação ótima sob incertezaContratação ótima sob incerteza
Como tomar decisões sob incerteza?
O arrependimento vem de um resultado esperado (target) que não éO arrependimento vem de um resultado esperado (target) que não é 
atingido! Ou seja, é a diferença entre o que queremos para o que 
obtemos.
P d t d fi iPodemos pensar que temos despesas fixas a pagar que seriam 
perfeitamente honradas se obtivéssemos como receita o valor esperado 
da renda no spot, sem qualquer contrato: D = 6870 R$/hora
No caso anterior, o arrependimento foi A = D – R2= 6870. 
Podemos então limitar o arrependimento, por exemplo a zero (A ≤ 0) 
em todos os cenários: um arrependimento negativo é desejável (não meem todos os cenários: um arrependimento negativo é desejável (não me 
arrependo). Maximizar ( )MaximizarQ≥0 ( ). : ≤ 100≥ ∀ = 1,2
59
≥ ∀ 1,2
Contratação ótima sob incertezaContratação ótima sob incerteza
Como tomar decisões sob incerteza?
Maximizar a renda esperada sujeito a não se arrepender:Maximizar a renda esperada sujeito a não se arrepender:MaximizarQ≥0 42 ⋅ + 6870. : ≤ 100100 ⋅ + 2300 ≥ 6870−480 ⋅ + 48000 ≥ 6870$
48000 ℎ
12300 R
2300
12300
R2
R1
60
Q (MWméd.)
2
Q*=85.7
Contratação ótima sob incertezaContratação ótima sob incerteza
Como tomar decisões sob incerteza?
Maximizar a renda esperada sujeito a não se arrepender:Maximizar a renda esperada sujeito a não se arrepender:MaximizarQ≥0 42 ⋅: ≤ 100. : ≤ 100≥ 45.7≤ 85.7$
 
48000 ℎ
Em Q*=85.7, a variância 
12300 R
,
é menor que em Q=100. 
2300
12300
R2
R1
61
Q (MWméd.)Q*=85.7
2
Contratação ótima sob incertezaContratação ótima sob incerteza
Como tomar decisões sob incerteza?
Podemos pensar também em minimizar o maior arrependimento:Podemos pensar também em minimizar o maior arrependimento:MinimizarQ≥0 max1≤i≤2{ }
$ . : ≤ 1001 = − (100 ⋅ + 2300)2 = − (−480 ⋅ + 48000)48000 ℎ 2 ( 480 + 48000)
12300 R
2300
12300
R2
R1
62
Q (MWméd.)
2
Contratação ótima sob incertezaContratação ótima sob incerteza
Como tomar decisões sob incerteza?
Substituindo a expressão do arrependimento na f.obj., obtemos:Substituindo a expressão do arrependimento na f.obj., obtemos:MinimizarQ≥0 − min{100 ⋅ + 2300; −480 ⋅ + 48000}≤ 100$. : ≤ 100
48000 ℎ
12300 R
2300
12300
R2
R1
63
Q (MWméd.)
2
Contratação ótima sob incertezaContratação ótima sob incerteza
Como tomar decisões sob incerteza?
Neste caso, é equivalente a maximizar a pior renda:Neste caso, é equivalente a maximizar a pior renda:MaximizarQ≥0 min{100 ⋅ + 2300; −480 ⋅ + 48000}≤ 100$. : ≤ 100
48000 ℎ
12300 R
2300
12300
R2
R1
64
Q (MWméd.)
2
Contratação ótima sob incertezaContratação ótima sob incerteza
Como tomar decisões sob incerteza?
Neste caso, é equivalente a maximizar a pior renda:Neste caso, é equivalente a maximizar a pior renda:MaximizarQ≥0 min{100 ⋅ + 2300; −480 ⋅ + 48000}≤ 100$. : ≤ 100
48000 ℎ
Propriedades da f obj :
12300 R
Propriedades da f.obj.:
linear por partes
côncava
2300
12300
R2
R1
65
Q (MWméd.)
2
Contratação ótima sob incertezaContratação ótima sob incerteza
Como tomar decisões sob incerteza?
Para transfomar o problema de MaxMin em um PL:MaximizarQ≥0t
Para transfomar o problema de MaxMin em um PL:
. : ≤ 100≤ 100 ⋅ + 2300≤ 480 + 48000$ℎ ≤ −480 ⋅ + 4800048000 ℎ
Utilizamos uma variável auxiliar 
(t) tá b i d b
12300
(t) que está abaixo de ambas as 
curvas (R1 e R2).
O conjunto de pontos (t,Q) 
abai o da f obj representam o
Pontos (t,Q) viáveis2300
12300 abaixo da f.obj representam o 
hipografo da f.obj., que é um 
poliedro.
66
Q (MWméd.)
Contratação ótima sob incertezaContratação ótima sob incerteza
Como tomar decisões sob incerteza?
Para transfomar o problema de MaxMin em um PL:MaximizarQ≥0t
Para transfomar o problema de MaxMin em um PL:
. : ≤ 100−100 ⋅ + ≤ 2300480 + ≤ 48000$ℎ 480 ⋅ + ≤ 4800048000 ℎ
Utilizamos uma variável auxiliar 
(t) tá b i d b
12300
(t) que está abaixo de ambas as 
curvas (R1 e R2).
O conjunto de pontos (t,Q) 
abai o da f obj representam o
cT=[0,1]
Pontos (t,Q) viáveis2300
12300 abaixo da f.obj representam o 
hipografo da f.obj., que é um 
poliedro.
67
Q (MWméd.)Q*=78.8
Contratação ótima sob incertezaContratação ótima sob incerteza
Como tomar decisões sob incerteza?
Para transfomar o problema de MaxMin em um PL:MaximizarQ≥0t
Para transfomar o problema de MaxMin em um PL:
. : ≤ 100−100 ⋅ + ≤ 2300480 + ≤ 48000$ℎ 480 ⋅ + ≤ 4800048000 ℎ
12300
cT=[0,1]
2300
12300
Variância zero
68
Q (MWméd.)Q*=78.8
Contratação ótima sob incertezaContratação ótima sob incerteza
Conclusões:
Quando temos que tomar uma decisão sob incerteza, ou seja, em umQuando temos que tomar uma decisão sob incerteza, ou seja, em um 
contexto que envolva incerteza em um ou mais parâmetros do modelo, 
geralmente modelamos a distribuição de probabilidade conjunta desses 
parâmetros para incorporar a percepção do risco que corremos em cadaparâmetros para incorporar a percepção do risco que corremos em cada 
possível decisão;
Para otimizarmos a decisão, precisamos de uma medida que traduza 
uma preferência sobre as possíveis distribuições de probabilidade 
resultantes de cada decisão;
Utilizar o valor esperado (média) como preferência pode gerar decisões p ( ) p p g
muito arriscadas (cenários com uma grande variância).
Diversas metodologias podem ser utilizadas para incorporar e controlar 
o risco que se corre em cada decisãoo risco que se corre em cada decisão
Minimax arrependimento pode gerar decisões muito conservadoras
Outras medidas podem ser utilizadas: utilidade esperada medidas 
69
p p
de risco, etc...
Modelagem de funções côncavas e convexas por PLModelagem de funções côncavas e convexas por PL
Observação importante:
Podemos maximizar qualquer superfície côncava ou minimizar 
superfícies convexas utilizando PL:
Aplicações: 
1 Maximização de utilidade (côncava) e Lucro após IR (importante)1. Maximização de utilidade (côncava) e Lucro após IR (importante)
2. Minimização de custos de combustível quadráticos (convexa)
3. Restrição de risco Maximizar min { + }ç Maximizar≥t mini=1,…,n{ ⋅ + }. : ⋅ ≤( ) = mini=1,…,n{ ⋅ + }
Maximizar≥ t. : ≤ ⋅ + ∀ = 1, … , ⋅ ≤
70
x
AgendaAgenda
Módulo 1 – Modelagem de problemas de PL:
historia da Programação Linear;historia da Programação Linear;
modelagem de problemas (foco no setor elétrico: exemplo de contratação de 
energia);
interpretação geométricainterpretação geométrica;
Exercícios com Excel.
Módulo 2 – Propriedades das soluções e o Método Simplex:
soluções básicas viáveis e suas interpretações;
método simplex;método simplex;
exercícios (hands on).
Módulo 3 – Teoria de dualidade e análise de sensibilidade
Módulo 4 – Decomposição de Benders e PDDE 
71
Fluxo de potência DCFluxo de potência DC
Suponha a seguinte rede de transmissão:
Valore negativos representam um consumo (carga) e positivo produção (geração)
Valores em MWh
20.0 20.0
20.0 -120.00.0
N FIC NE
0.0
100.0
100 0
SE
0.0
100.0
0.0
S
72
Fluxo de potência DCFluxo de potência DC
Suponha a seguinte rede de transmissão:
Valores negativos representam um consumo (carga) e positivo produção (geração)T d lid 45 id d t i õ d fl d tê iTraçar a curva do slide 45, considerando restrições de fluxo de potência
∈ ( ) − ∈ ( ) = − ∀ = 1, … ,( ) ℎ∈ (−∞, ∞) ∀ ∈ ℎ
N->FIC FIC->NE SE->FIC SE->NE S->SE
Capacidade (MWh) 4000 100 0 1000 6000
Custo (R$/MWh) 0 0 0 0 0
Fluxo (MWh) 20 0 20 0 0 0 100 0 0 0
Linhas
Fluxo sainte 
líquido 
(MWh) Player
Déficit 
(MWh)
Geração 
Excedente 
(MWh)
Custo do 
Déficit 
(R$/MWh)
Balanço 
nodal 
(MWh)
Custo 
Geração 
(R$/MWh)Fluxo (MWh) 20.0 20.0 0.0 100.0 0.0
N 1 0 0 0 0 20.0 H1 20.0 0.0 0.0 0 500
FIC -1 1 -1 0 0 0.0 0.0 0.0 0.0 0 1000
NE 0 -1 0 -1 0 -120.0 C1 -120.0 0.0 0.0 0 500
SE 0 0 1 1 -1 100.0 T1 100.0 0.0 0.0 100 500
S 0 0 0 0 1 0.0 T2 0.0 0.0 0.0 150 500
Total = 0.0 0.0 0.0 0.0
Custo total = 0 R$ Custo de Geração (R$) = 10,000.0
(MWh) Player (MWh)(MWh) (R$/MWh)(MWh) (R$/MWh)
Var. Decisão Valores Unidades Hidrelétrica
Valores em MWh u2 20.0 hm3 v1 (hm3) = 10
s2 0.0 hm3 a (hm3) = 10
20.0 20.0 v2 0.0 hm3 rho (MWh/hm3) = 1
20.0 -120.0 g1 100.0 MWh P (MW) = 200
g2 0.0 MWh v2Max (hm3) = 500
N->FIC 20.0 MWh
0.0
N FIC NE
0.0 FIC->NE 20.0 MWh Estoque água = 20
100.0 SE->FIC 0.0 MWh Balanço hídrico = 20
SE->NE 100.0 MWh
S->SE 0.0 MWh
r2_N 0.0 MWh
r2_FIC 0.0 MWh
0.0 r2_NE 0.0 MWh
r2_SE 0.0 MWh
100.0
SE
73
r2_SE 0.0 MWh
0.0
S
Exercícios Regressão LinearExercícios Regressão Linear
Suponha o problema de regressão linear multivariada em que se deseja
encontrar os parâmtros do modelo (regressores) minimizando os erros
absolutos entre as observações e a predição do modelo:absolutos entre as observações e a predição do modelo:
a) Desenhe a função módulo de cada erro e mostre que esta é convexa;
b) Mostre como utilizar esse conceito para transformar o problema não linear 
abaixo em um problema de PL;
c) Mostre uma segunda formulação para esse problema com menos restrições que
a anterior;
d) Gere dados e compare a sensibilidade dos regressores obtidos por mínimos 
quadrados e pela soma mínima de valores absolutos, com relação à presença de 
outliers! Minimizar∈ℝ | |y ∈ℝ =1. : = − ⋅ − ∀ = 1, … , a1 x2 ei
74
=1x1