Modulo 3 - Curso de Otimizacao Linear

Prévia do material em texto

1 
Pontifícia Universidade Católica do Rio de Janeiro (PUC-Rio) 
Departamento de Engenharia Elétrica (DEE) 
www.ele.puc-rio.br 
 
 
 
 
Curso de Otimização Linear 
aplicado ao Setor Elétrico 
 
Módulo 3 
Prof. Alexandre Street 
 
Setembro de 2010 
2 
Agenda 
 Módulo 1 – Modelagem de problemas de PL 
 Módulo 2 – Propriedades das soluções e o Método Simplex 
 Módulo 3 – Teoria de dualidade e análise de sensibilidade 
 Introduzir o conceito de problema primal e dual (exemplos e interpretações); 
 teorema da dualidade fraca, forte e complementariedade de folgas 
 análise de sensibilidade com relação aos recursos: custo marginal e viabilidade 
primal; 
 análise de sensibilidade com relação a outros parâmetros do problema; 
 aplicações práticas de dualidade em problemas do setor elétrico: custo de 
oportunidade da água (“valor da água”). 
 
 Módulo 4 – Decomposição de Benders e PDDE 
 
 
3 
 O que significa primal e dual? 
 Primal é o problema em foco e dual é um outro problema que tenha certas 
características com relação ao seu par primal. 
 A principal das características é que o problema dual fornece um limite superior 
(para o caso de maximização) para todas as soluções viáveis do problema primal, 
incluindo, portanto, a ótima. 
• Qual quer solução viável do problema dual fornece um valor de objetivo superior ao 
primal 
• O objetivo do problema dual é busca o menor limite (mais apertado), sendo assim um 
problema de minimização. 
Teoria de dualidade 
f.obj. de ambos os problemas 
Valores das soluções (f.obj.) do problema dual 
Valores das soluções (f.obj.) do problema primal 
zp
* 
zd
* 
GAP dual 
4 
 Como formular o problema dual do seguinte problema de PL? 
Teoria de dualidade 
𝑧𝑝
∗ = Max
𝐱≥𝟎
𝒄𝑻 ⋅ 𝒙
𝑠. 𝑎: 𝑨 ⋅ 𝒙 ≤ 𝒃
 
5 
 Suponha que desejamos encontrar um limite superior para o lucro máximo z*p 
(ótimo) que podemos obter no problema da produção: 
 
 
 
 
 
 Como a solução ótima deste problema atende a todas as suas restrições, ao 
multiplicarmos a restrição (1.1) por 3, obteremos a seguinte inequação, válida 
para todos os pontos viáveis: 
 
 
 Em uma rápida análise podemos perceber que como todos os coeficientes 
dessa desigualdade são maiores que os respectivos coeficientes da f.obj., esta 
nunca poderá valer mais que 12! 
Teoria de dualidade 
𝑧𝑝
∗ = Max
𝐱≥𝟎
4 ⋅ 𝑥𝐴 + 3 ⋅ 𝑥𝐵 (1)
𝑠. 𝑎: 2 ⋅ 𝑥𝐴 + 1 ⋅ 𝑥𝐵 ≤ 4 (1.1)
1 ⋅ 𝑥𝐴 + 2 ⋅ 𝑥𝐵 ≤ 4 (1.2)
 
6 ⋅ 𝑥𝐴 + 3 ⋅ 𝑥𝐵 ≤ 12 
6 
 Se fizermos uma combinação linear positiva das restrições (1.1) e (1.2) a desigualdade 
decorrente será válida para todos os pontos que atendem às restrições originais: 
 
 
 
 
 
 Se fizermos y1 = 5/3 e y2 = 2/3, por exemplo, obteremos um limite superior igual a 28/3 
= 9.3..., que sabemos ser o máximo do problema da produção! 
 
 Isso nos mostra que o limite superior obtido por essa escolha de multiplicadores resulta 
no menor limite possível! Limite ótimo! 
 
 IMPORTANTE: O GAP de dualidade em problemas de PL é sempre zero!!! 
 Nos respectivos pontos ótimos as f.objs. do primal e do dual são iguais!!! 
 Teorema da Dualidade Forte 
Teoria de dualidade 
𝑦1 ⋅ 2 ⋅ 𝑥𝐴 + 1 ⋅ 𝑥𝐵 ≤ 𝑦1 ⋅ 4
𝑦2 ⋅ 1 ⋅ 𝑥𝐴 + 2 ⋅ 𝑥𝐵 ≤ 𝑦2 ⋅ 4 +
 
 𝑦1 ⋅ 2 + 𝑦2 ⋅ 1 ⋅ 𝑥𝐴 + 𝑦1 ⋅ 1 + 𝑦2 ⋅ 2 ⋅ 𝑥𝐵 ≤ 𝑦1 ⋅ 4 + 𝑦2 ⋅ 4 
7 
 Como podemos gerar uma sistemática para encontrar os pesos yi de maneira 
que eles proporcionem o menor limite superior (mínimo)? 
 
 
 
 
 Precisamos impor que cada coeficiente da desigualdade encontrada seja 
superior ao respectivo coeficiente da função objetivo: 
 
 
 
 Com isso, o lado direito dessa nova desigualdade será sempre maior que 
qualquer valor que a função objetivo possa valer dentro do conjunto de pontos 
viáveis: 
 
 
 
 
Teoria de dualidade 
𝑦1 ⋅ 2 ⋅ 𝑥𝐴 + 1 ⋅ 𝑥𝐵 ≤ 𝑦1 ⋅ 4
𝑦2 ⋅ 1 ⋅ 𝑥𝐴 + 2 ⋅ 𝑥𝐵 ≤ 𝑦2 ⋅ 4 +
 
 𝑦1 ⋅ 2 + 𝑦2 ⋅ 1 ⋅ 𝑥𝐴 + 𝑦1 ⋅ 1 + 𝑦2 ⋅ 2 ⋅ 𝑥𝐵 ≤ 𝑦1 ⋅ 4 + 𝑦2 ⋅ 4 
𝑦1 ⋅ 2 + 𝑦2 ⋅ 1 ≥ 4
𝑦1 ⋅ 1 + 𝑦2 ⋅ 2 ≥ 3
 
4 ⋅ 𝑥𝐴 + 3 ⋅ 𝑥𝐵 ≤ 𝑦1 ⋅ 2 + 𝑦2 ⋅ 1 ⋅ 𝑥𝐴 + 𝑦1 ⋅ 1 + 𝑦2 ⋅ 2 ⋅ 𝑥𝐵 ≤ 𝑦1 ⋅ 4 + 𝑦2 ⋅ 4 
𝑧𝑝 = 4 ⋅ 𝑥𝐴 + 3 ⋅ 𝑥𝐵 
8 
 Assim, queremos minimizar o limite superior, mexendo nos multiplicadores y, 
sujeito a esses multiplicadores gerarem um limite superior: 
 
 
 
 
 
 No problema (2)-(2.2), a função objetivo representa o limite superior para o 
problema primal: 
 É a combinação linear do lado direito das restrições do primal 
 
 A restrição (2.1) garante que o coeficiente associado à variável xA será superior 
ao coeficiente da função objetivo (do primal); 
 
 A restrição (2.2) garante o mesmo para o coeficiente associado à variável xB. 
 
 
 
 
Teoria de dualidade 
𝑧𝑝
∗ ≤ 𝑧𝑑
∗ = Min
𝐲≥𝟎
4 ⋅ 𝑦
1
+ 4 ⋅ 𝑦
2
(2)
𝑠. 𝑎: 2 ⋅ 𝑦1 + 1 ⋅ 𝑦2 ≥ 4 (2.1)
1 ⋅ 𝑦1 + 2 ⋅ 𝑦2 ≥ 3 (2.2)
 
9 
 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: 
 2xA + 1xB  4 
• 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 
 
 
Teoria de dualidade (interpretação) 
Produto A 
(103 unid.) 
Produto B 
(103 unid.) 
Qt em Estoque 
 
Insumo M 
(103 m2) 
2 1 4 
Insumo F 
(Ton.) 
1 2 4 
10 
 Exemplo: Problema da produção 
 
 
 
 
 Uma possível interpretação para o dual seria: 
 Por que preços de insumos (ferro e madeira) o dono desta empresa ficaria 
indiferente entre produzir, obtendo assim o lucro da produção, e parar a produção 
e vender todo o seu estoque de insumos? 
 
 
 
Teoria de dualidade (interpretação) 
𝑧𝑝
∗ = Max
𝐱≥𝟎
4 ⋅ 𝑥𝐴 + 3 ⋅ 𝑥𝐵 (1)
𝑠. 𝑎: 2 ⋅ 𝑥𝐴 + 1 ⋅ 𝑥𝐵 ≤ 4 (1.1)
1 ⋅ 𝑥𝐴 + 2 ⋅ 𝑥𝐵 ≤ 4 (1.2)
 
11 
 Exemplo: Problema da produção 
 
 
 
 
 Uma possível interpretação para o dual seria: 
 Por que preços de insumos (ferro e madeira) o dono desta empresa ficaria 
indiferente entre produzir, obtendo assim o lucro com a produção, e parar a 
produção e vender todo o seu estoque de insumos? 
 Certamente por preços yM (MMR$/10
3m2) e yF (MMR$/Ton.) em que o lucro dessa 
venda supere o lucro da empresa operada de forma ótima z*p: 
 
 
 Porém, para obtermos isso, precisamos de condições sobre os preços que garantam 
que: a venda dos insumos necessários para produzir cada produto supere o seu 
lucro! 
 
 
 
Teoria de dualidade (interpretação) 
𝑧𝑝
∗ = Max
𝐱≥𝟎
4 ⋅ 𝑥𝐴 + 3 ⋅ 𝑥𝐵 (1)
𝑠. 𝑎: 2 ⋅ 𝑥𝐴 + 1 ⋅ 𝑥𝐵 ≤ 4 (1.1)
1 ⋅ 𝑥𝐴 + 2 ⋅ 𝑥𝐵 ≤ 4 (1.2)
 
𝑧𝑝
∗ ≤ 𝑧 = 𝑦𝑀 ⋅ 4 + 𝑦𝐹 ⋅ 4 
12 
 Exemplo: Problema da produção 
 
 
 
 
 
1. Condição para parar de vender o produto A: 
 Vender 2 mil m3 de madeira ao preço yM e vender 1 Ton. de ferro a yF deve gerar 
uma receita superior a 4 MMR$ (lucro que cada lote do produto A gera). 
2. Condição para parar de vender o produto B: 
 Vender 1 mil m3 de madeira ao preço yM e vender 2 Ton. de ferro a yF deve gerar 
uma receita superior a 3 MMR$ (lucro que cada lote do produto B gera). 
 
 
 
 
Teoria de dualidade (interpretação) 
𝑧𝑝
∗ = Max
𝐱≥𝟎
4 ⋅ 𝑥𝐴 + 3 ⋅ 𝑥𝐵 (1)
𝑠. 𝑎: 2 ⋅ 𝑥𝐴 + 1 ⋅ 𝑥𝐵 ≤ 4 (1.1)
1 ⋅ 𝑥𝐴 + 2 ⋅ 𝑥𝐵 ≤ 4 (1.2)
 
𝑦𝑀 ⋅ 2 + 𝑦𝐹 ⋅ 1 ≥ 4
𝑦𝑀 ⋅ 1 + 𝑦𝐹 ⋅ 2 ≥ 3
 
13 
 Exemplo: Problema da produção 
 
 
 
 
 Assim, a resposta para a pergunta: 
 Por que preços de insumos (ferro e madeira) o dono desta empresa ficaria 
indiferente entre produzir, obtendo assim o lucro com a produção, e parar a 
produção e vender todo o seu estoque de insumos? 
 É dada pelo problema que encontra a menor receita de venda dos insumos pela 
qual ainda sim vale a pena parar de produzir: 
 
 
Teoria de dualidade (interpretação) 
𝑧𝑝
∗ = Max
𝐱≥𝟎
4 ⋅ 𝑥𝐴 + 3 ⋅ 𝑥𝐵 (1)
𝑠. 𝑎: 2 ⋅ 𝑥𝐴 + 1 ⋅ 𝑥𝐵 ≤ 4 (1.1)
1 ⋅ 𝑥𝐴+ 2 ⋅ 𝑥𝐵 ≤ 4 (1.2)
 
𝑧𝑝
∗ ≤ 𝑧𝑑
∗ = Min
𝐲≥𝟎
4 ⋅ 𝑦
𝑀
+ 4 ⋅ 𝑦
𝐹
(2)
𝑠. 𝑎: 2 ⋅ 𝑦𝑀 + 1 ⋅ 𝑦𝐹 ≥ 4 (2.1)
1 ⋅ 𝑦𝑀 + 2 ⋅ 𝑦𝐹 ≥ 3 (2.2)
 
14 
 Como funciona o processo de “dualização” de restrições (relaxação 
lagrangeana)? 
 
 
 O processo de “dualização” implica em relaxar alguma das restrições (ou todas) 
do problema primal e incorporar uma penalização na f.obj. sobre a viabilidade 
das soluções. 
Teoria de dualidade 
𝑧𝑝
∗ = Max
𝐱≥𝟎
𝒄𝑻 ⋅ 𝒙
𝑠. 𝑎: 𝑨 ⋅ 𝒙 ≤ 𝒃
 
𝑧𝑝
∗ ≤ 𝜃 𝒚 = Max
𝐱≥𝟎
𝒄𝑻 ⋅ 𝒙 + 𝒚𝑻 ⋅ 𝒃 − 𝑨 ⋅ 𝒙 
𝑠. 𝑎: 𝑨 ⋅ 𝒙 ≤ 𝒃
 ∀ 𝒚 ≥ 𝟎 
𝑧𝑝
∗ ≤ 𝜃 𝒚 ≤ 𝜙 𝒚 = Max
𝐱≥𝟎
𝒄𝑻 ⋅ 𝒙 + 𝒚𝑻 ⋅ 𝒃 − 𝑨 ⋅ 𝒙 ∀ 𝒚 ≥ 𝟎 
Interpretação: O dono da fábrica 
agora pode vender ou comprar a 
sobra ou déficit de insumos em “um 
mercado” (ilimitado) por preços y 
15 
 Como se comporta a função dual lagrangeana? 
 
 
 Dado um vetor y de multiplicadores de Lagrange, 
 
 
 O processo de relaxação lagrangeana busca um vetor y que minimize (y)! 
Logo, o segundo caso (que proporciona valor infinito) será sempre evitado! 
 A interpretação para esse comportamento é: 
 se o lucro unitário de produção (cT) for inferior à receita de venda de seus insumos 
no mercado ao preço y (yTA), então paramos a produção e vendemos todos os 
insumos no mercado, resultando em um lucro de yTb. 
 Caso contrário, ocorre a possibilidade de arbitragem, onde podemos comprar no 
mercado os insumos por preços que geram um custo inferior ao lucro de produção. 
Assim, compramos infinito e vendemos infinito, obtendo assim um resultado 
ilimitado. 
Teoria de dualidade 
𝑧𝑝
∗ ≤ 𝜙 𝒚 = Max
𝐱≥𝟎
𝒄𝑻 ⋅ 𝒙 + 𝒚𝑻 ⋅ 𝒃 − 𝑨 ⋅ 𝒙 ∀ 𝒚 ≥ 𝟎 
𝑧𝑝
∗ ≤ 𝜙 𝒚 = Max
𝐱≥𝟎
 𝒄𝑻 − 𝒚𝑻 ⋅ 𝑨 ⋅ 𝒙 + 𝒚𝑻 ⋅ 𝒃 = 
 𝒚𝑻 ⋅ 𝒃, 𝑠𝑒 𝒄𝑻 − 𝒚𝑻 ⋅ 𝑨 ≤ 𝟎 
+∞, 𝑐𝑎𝑠𝑜 𝑐𝑜𝑛𝑡𝑟á𝑟𝑖𝑜
 
16 
 O problema dual busca um vetor y que minimize (y)! Logo, o segundo caso 
será sempre evitado! 
 
 
 
 
 Assim, temos o seguinte par primal-dual: 
 
 
 
 
 
 
 
 
 
 
Teoria de dualidade 
𝑧𝑝
∗ ≤ Min
𝐲≥𝟎
 𝜙 𝒚 = Min
𝐲≥𝟎
 
 𝒚𝑻 ⋅ 𝒃, 𝑠𝑒 𝒄𝑻 − 𝒚𝑻 ⋅ 𝑨 ≤ 𝟎 
+∞, 𝑐𝑎𝑠𝑜 𝑐𝑜𝑛𝑡𝑟á𝑟𝑖𝑜
 = Min
𝐲≥𝟎
𝒚𝑻 ⋅ 𝒃
𝑠. 𝑎: 𝒚𝑻 ⋅ 𝑨 ≥ 𝒄𝑻 
 
𝑧𝑝
∗ = Max
𝐱≥𝟎
𝒄𝑻 ⋅ 𝒙
𝑠. 𝑎: 𝑨 ⋅ 𝒙 ≤ 𝒃
≤ 𝑧𝑑
∗ = Min
𝐲≥𝟎
𝒚𝑻 ⋅ 𝒃
𝑠. 𝑎: 𝒚𝑻 ⋅ 𝑨 ≥ 𝒄𝑻 
 
17 
Agenda 
 Módulo 1 – Modelagem de problemas de PL 
 Módulo 2 – Propriedades das soluções e o Método Simplex 
 Módulo 3 – Teoria de dualidade e análise de sensibilidade 
 Introduzir o conceito de problema primal e dual (exemplos e interpretações); 
 teorema da dualidade fraca, forte e complementaridade de folgas 
 análise de sensibilidade com relação aos recursos: custo marginal e viabilidade 
primal; 
 análise de sensibilidade com relação a outros parâmetros do problema; 
 aplicações práticas de dualidade em problemas do setor elétrico: custo de 
oportunidade da água (“valor da água”). 
 
 Módulo 4 – Decomposição de Benders e PDDE 
 
 
18 
Dualidade Fraca e Forte 
 O teorema da dualidade Fraca diz que (Primal de Maximização): 
 O valor mínimo do problema Dual (de minimização) é superior ao máximo do 
problema primal (maximização). 
• Isso torna-se óbvio depois de mostrado o processo de construção do dual da 
maneira que apresentamos aqui. Este foi concebido para sempre gerar um limite 
superior para o problema primal. 
 O teorema da dualidade Forte diz que (Primal de Maximização): 
 No ótimo o valor da função objetivo de qualquer par primal-dual decorrente 
de um PL é sempre o mesmo! 
 
 
 
f.obj. 
Valores das soluções (f.obj.) do problema dual 
Valores das soluções (f.obj.) do problema primal 
zp
*=zd
* 
 
GAP dual = 0 
𝑧𝑝
∗ = Max
𝐱≥𝟎
𝒄𝑻 ⋅ 𝒙
𝑠. 𝑎: 𝑨 ⋅ 𝒙 ≤ 𝒃
= 𝑧𝑑
∗ = Min
𝐲≥𝟎
𝒚𝑻 ⋅ 𝒃
𝑠. 𝑎: 𝒚𝑻 ⋅ 𝑨 ≥ 𝒄𝑻 
 
19 
 Exemplo: despacho centralizado vs competição perfeita 
 O despacho ótimo “centralizado” de um período, que visa atender uma 
demanda d (MWh) utilizando os recursos disponíveis (capacidades Gi) é dado 
pelo seguinte problema: 
 
 
 
 
 
 
 
 Para que este problema atinja o seu objetivo, é importante que os agentes 
informe os seus reais custo operativos e capacidades (ci, Gi). 
 
 
Dualidade Forte (Ex. de implicação prática) 
𝐶∗ = Min
𝐠≥𝟎
 𝑐𝑖 ⋅ 𝑔𝑖
𝑛
𝑖=1
 (3)
𝑠. 𝑎: 𝑔𝑖
𝑛
𝑖=1
≥ 𝑑 (3.1)
𝑔𝑖 ≤ 𝐺𝑖 ∀𝑖 = 1, … , 𝑛 (3.2)
 
20 
 Exemplo: despacho centralizado vs competição perfeita 
 
 É possível mostrar, sob certas condições (que serão identificadas), que: 
 Um mercado competitivo, 
• onde os agente são todos price-takers e visam maximizar os seus lucros com a venda de 
energia através de um leilão de preço uniforme, 
 proporciona o mesmo despacho (solução de geração) que o despacho de mínimo 
custo: 
 
 Começamos por dualizar a restrição de atendimento à demanda 
 Onde para todo   0 teremos a seguinte relação: 
 
 
 
 
 
 
 
 
 
Dualidade Forte (Ex. de implicação prática) 
𝐶∗ ≥ 𝐶𝑑
∗(𝜋) = Min
𝐠≥𝟎
 𝑐𝑖 ⋅ 𝑔𝑖
𝑛
𝑖=1
+ 𝜋 ⋅ 𝑑 − 𝑔𝑖
𝑛
𝑖=1
 (4)
𝑠. 𝑎: 𝑔𝑖 ≤ 𝐺𝑖 ∀𝑖 = 1, … , 𝑛 (4.1)
 
21 
 Exemplo: despacho centralizado vs competição perfeita 
 
 Em seguida, rearranjamos os termos de maneira a colocar o gi em evidência: 
 
 
 
 
 
 
 
 
 
Dualidade Forte (Ex. de implicação prática) 
𝐶∗ ≥ 𝐶𝑑
∗(𝜋) = Min
𝐠≥𝟎
 𝑐𝑖 ⋅ 𝑔𝑖
𝑛
𝑖=1
+ 𝜋 ⋅ 𝑑 − 𝑔𝑖
𝑛
𝑖=1
 (4)
𝑠. 𝑎: 𝑔𝑖 ≤ 𝐺𝑖 ∀𝑖 = 1, … , 𝑛 (4.1)
 
𝐶∗ ≥ 𝐶𝑑
∗(𝜋) = Min
𝐠≥𝟎
𝜋 ⋅ 𝑑 − (𝜋 − 𝑐𝑖) ⋅ 𝑔𝑖
𝑛
𝑖=1
 (4)
𝑠. 𝑎: 𝑔𝑖 ≤ 𝐺𝑖 ∀𝑖 = 1, … , 𝑛 (4.1)
 
22 
 Exemplo: despacho centralizado vs competição perfeita 
 
 Como o primeiro termo não depende da decisão g, este pode ser colocado fora 
do “Min”: 
 
 
 
 
 
 
 
 
 
Dualidade Forte (Ex. de implicação prática) 
𝐶∗ ≥ 𝐶𝑑
∗ 𝜋 = 𝜋 ⋅ 𝑑 + Min
𝐠≥𝟎
− (𝜋 − 𝑐𝑖) ⋅ 𝑔𝑖
𝑛
𝑖=1
 (4)
𝑠. 𝑎: 𝑔𝑖 ≤ 𝐺𝑖 ∀𝑖 = 1, … , 𝑛 (4.1)
 
𝐶∗ ≥ 𝐶𝑑
∗(𝜋) = Min
𝐠≥𝟎
𝜋 ⋅ 𝑑 − (𝜋 − 𝑐𝑖) ⋅ 𝑔𝑖
𝑛
𝑖=1
 (4)
𝑠. 𝑎: 𝑔𝑖 ≤ 𝐺𝑖 ∀𝑖 = 1, … , 𝑛 (4.1)
 
23 
 Exemplo: despacho centralizado vs competição perfeita 
 
 Por fim, repare que o problema de minimização pode ser decomposto em n 
problemas, em que cada um pode ser substituído por um de maximização da 
seguinte forma: 
 
 
 
 
 
 
 
 
 
Dualidade Forte (Ex. de implicação prática) 
𝐶∗ ≥ 𝐶𝑑
∗ 𝜋 = 𝜋 ⋅ 𝑑 + Min
𝐠≥𝟎
− (𝜋 − 𝑐𝑖) ⋅ 𝑔𝑖
𝑛
𝑖=1
 (4)
𝑠. 𝑎: 𝑔𝑖 ≤ 𝐺𝑖 ∀𝑖 = 1, … , 𝑛 (4.1)
 
𝐶∗ ≥ 𝐶𝑑
∗ 𝜋 = 𝜋 ⋅ 𝑑 − Max
gi≥0
(𝜋 − 𝑐𝑖) ⋅ 𝑔𝑖 (4)
𝑠. 𝑎: 𝑔𝑖 ≤ 𝐺𝑖 (4.1)
𝑛
𝑖=1
 
24 
 Exemplo: despacho centralizado vs competição perfeita 
 
 O problema resultante é o problema em que cada agente gerador visa 
maximizar a sua renda vendendo energia a um preço  (R$/MWh) e a 
demanda (inelástica) paga o mesmo preço pela aquisição dessa energia. 
 
 Onde, 
Dualidade Forte (Ex. de implicação prática) 
𝐶∗ ≥ Max
π≥0
 𝜋 ⋅ 𝑑 − 𝐿𝑖
∗(𝜋)
𝑛
𝑖=1
 
𝐿𝑖
∗(𝜋) = Max
gi≥0
(𝜋 − 𝑐𝑖) ⋅ 𝑔𝑖 (4)
𝑠. 𝑎: 𝑔𝑖 ≤ 𝐺𝑖 (4.1)
 
Q 
p 
d 
 
gi=0 
gi=Gi 
25 
 Exemplo: despacho centralizado vs competição perfeita 
 Para constatarmos a igualdade obtida anteriormente, entre o bem estar social 
e o custo mínimo de operação, escrevemos diretamente o dual do problema de 
despacho a mínimo e mostramos que esse pode ser obtido por um mercado 
competitivo. 
 
 
 
 
 
 
 
 
 
𝐶∗ = Max
π≥0
𝛉≥𝟎
𝜋 ⋅ 𝑑 − 𝜃𝑖 ⋅ 𝐺𝑖
𝑛
𝑖=1
(5)
𝑠. 𝑎: 𝜋 − 𝜃𝑖 ≤ 𝑐𝑖 ∀𝑖 = 1, … , 𝑛 (5.1)
 
Dualidade Forte (Ex. de implicação prática) 
𝐶∗ = Max
π≥0
 𝜋 ⋅ 𝑑 − Min
θi≥0
𝜃𝑖 ⋅ 𝐺𝑖
𝑠. 𝑎: 𝜃𝑖 ≥ 𝜋 − 𝑐𝑖 
 
𝑛
𝑖=1
 Maxπ≥0
 𝜋 ⋅ 𝑑 − 𝐿𝑖
∗ 𝜋 
𝑛
𝑖=1
 
26 
Dualidade Forte (Ex. de implicação prática e teórica) 
 Talvez a mais importante, ou pelo menos mais conhecida e difundida em 
diversas áreas, devido à relação entre o problema primal e o dualseja a 
interpretação da variável dual como “preço sombra” ou custo marginal 
dos recursos: 
 Em problemas convexos, em que vale a dualidade forte, a variável dual pode 
ser interpretada como a derivada parcial do valor ótimo da função objetivo do 
primal, com relação ao lado direito da restrição associada a esta variável 
 que em ultima análise é o multiplicador de lagrange 
𝑧𝑝
∗ = 𝑧𝑑
∗ = 𝒚∗𝑻 ⋅ 𝒃 
𝜕𝑧𝑝
∗
𝜕𝒃
= 
𝜕𝑧𝑝
∗
𝜕𝑏1
, … ,
𝜕𝑧𝑝
∗
𝜕𝑏𝑚
 = 𝑦1
∗, … , 𝑦𝑚
∗ = 𝑦∗𝑇 
27 
Dualidade Forte e complementariedade de folgas 
 A complementariedade entre folgas e variáveis duais é uma propriedade 
que caracteriza a otimalidade de um par de soluções primal-dual 
 
 
 Interpretação: No ponto ótimo, a derivada da função objetivo com relação 
a um recurso (RHS de uma restrição = bi) só pode apresentar valor 
diferente de zero, se e somente se, esta restrição estiver ativa (atendida 
como igualdade), ou seja, si
* = 0. 
 
 Exemplo: Quanto varia o lucro ótimo do problema da produção, se 
variarmos marginalmente o a quantidade de madeira? 
 “A quantidade de madeira utilizada não pode ser maior que o estoque: 
 2xA + 1xB  4” 
 
𝑠𝑖
∗ ⋅ 𝑦𝑖
∗ = 0 ∀ 𝑖 = 1, … , 𝑚 
28 
Dualidade Forte e complementariedade de folgas 
 Exemplo: Quanto varia o lucro ótimo do problema da produção, se 
variarmos marginalmente a quantidade de madeira 
 “A quantidade de madeira utilizada não pode ser maior que o estoque: 
 2xA + 1xB  4”. 
 Recuperando o dicionário ótimo deste problema, vemos que s1
* = 0, pois é um 
variável não básica. Logo y1
*  0. 
 
 
 
xA 
xB 
4 
2 
(1.1) 
4 
2 
(1.2) 
4/3 
4/3 
cT 
𝛿 
𝑠1
∗ ⋅ 𝑦1
∗ = 0 
𝑧 =
28
3
−
5
3
⋅ 𝑠1 −
2
3
⋅ 𝑠2 
𝑥𝐴 =
4
3
−
2
3
⋅ 𝑠1 +
1
3
⋅ 𝑠2
𝑥𝐵 =
4
3
+
1
3
⋅ 𝑠1 −
2
3
⋅ 𝑠2
 
29 
Dualidade Forte e complementariedade de folgas 
 Exemplo: Quanto varia o lucro ótimo do problema da produção, se 
variarmos marginalmente a quantidade de madeira 
 “A quantidade de madeira utilizada não pode ser maior que o estoque: 
 2xA + 1xB  4”. 
 Somente porque a restrição deste recurso está ativa (s1
* = 0), pode existir um 
contribuição na função objetivo ao variarmos o recurso (y1
* = dz*/db1  0). 
 
 
 
𝑧 =
28
3
−
5
3
⋅ 𝑠1 −
2
3
⋅ 𝑠2 
𝑥𝐴 =
4
3
−
2
3
⋅ 𝑠1 +
1
3
⋅ 𝑠2
𝑥𝐵 =
4
3
+
1
3
⋅ 𝑠1 −
2
3
⋅ 𝑠2
 
𝑠1
∗ ⋅ 𝑦1
∗ = 0 
xA 
xB 
4 
2 
(1.1) 
4 
2 
(1.2) 
4/3 
4/3 
cT 
𝛿 
30 
Dualidade Forte e complementariedade de folgas 
 Exemplo: Quanto varia o lucro ótimo do problema da produção, se 
variarmos marginalmente a quantidade de madeira 
 No caso do problema com a restrição xA+xB  1, o fato de variarmos o lado 
direito desta restrição não contribui em nada para a f.obj. no ponto ótimo, 
pois s3
* = 5/3 > 0. Logo, y3 = 0!!! 
 
 
 
𝑠3
∗ ⋅ 𝑦3
∗ = 0 
xA 
xB 
4 
2 4 
2 
(a) (b) 
(d) 
(e) 
1 
1 
(f) 
(g) 
31 
Dualidade Forte e complementariedade de folgas 
 Como podemos obter os valores das variáveis duais no dicionário primal? 
 
 
 
 
𝑧 =
28
3
−
5
3
⋅ 𝑠1 −
2
3
⋅ 𝑠2 
𝑥𝐴 =
4
3
−
2
3
⋅ 𝑠1 +
1
3
⋅ 𝑠2
𝑥𝐵 =
4
3
+
1
3
⋅ 𝑠1 −
2
3
⋅ 𝑠2
 
𝑠1
∗ ⋅ 𝑦1
∗ = 0 
xA 
xB 
4 
2 
(1.1) 
4 
2 
(1.2) 
4/3 
4/3 
cT 
𝛿 
32 
Dualidade Forte e complementariedade de folgas 
 Como podemos obter os valores das variáveis duais no dicionário primal? 
 Nos custos reduzidos das folgas! Eles valem o negativo das variáveis duais. 
 Veja o porquê: 
 
 
 
 
 Como o GAP dual é zero (dualidade forte) e sabemos que xN = 0, 
 
 
 Ou seja, 
 
 
 
𝑧 = 𝒄𝑩
𝑻 ⋅ 𝑩−𝟏 ⋅ 𝒃 + 𝒄𝑵
𝑻 − 𝒄𝑩
𝑻 ⋅ 𝑩−𝟏 ⋅ 𝑵 ⋅ 𝒙𝑵 
𝒙𝑩 = 𝑩
−𝟏 ⋅ 𝒃 − 𝑩−𝟏 ⋅ 𝑵 ⋅ 𝒙𝑵 
𝑧𝑝
∗ = 𝑧𝑑
∗ = 𝒚∗𝑻 ⋅ 𝒃 = 𝒄𝑩
𝑻 ⋅ 𝑩−𝟏 ⋅ 𝒃 
𝒚∗𝑻 = 𝒄𝑩
𝑻 ⋅ 𝑩−𝟏 
33 
Dualidade Forte e complementariedade de folgas 
 Como podemos obter os valores das variáveis duais no dicionário primal? 
 Suponha que uma variável de folga termine no dicionário ótimo como não 
básica. 
 Como uma variável de folga não tem custo na função objetivo: cN=0 
 E a coluna da matriz A referente a ela é um vetor com apenas uma 
componente não nula e igual a um exatamente na linha correspondente à 
restrição desta folga, 
 Por exemplo, suponha a folga 1: 
 
 
 
 
𝑐 𝑠1 = 𝑐𝑠1 − 𝒄𝑩
𝑇 ⋅ 𝑩−1 ⋅ 𝑁𝑠1 
𝑐 𝑠1 = 0 − 𝒚
∗𝑻 ⋅ 
1
0
 = −𝑦1
∗ 
𝑧 =
28
3
−
5
3
⋅ 𝑠1 −
2
3
⋅ 𝑠2 
𝑥𝐴 =
4
3
−
2
3
⋅ 𝑠1 +
1
3
⋅ 𝑠2
𝑥𝐵 =
4
3
+
1
3
⋅ 𝑠1 −
2
3
⋅ 𝑠2
 
𝑦1
∗ =
5
3
 
34 
Dualidade Forte e complementariedade de folgas 
 Como a complementariedade implica em Dualidade Forte (GAP=0)? 
 
 
 
 Se as soluções primal e dual são ótimas, então são viáveis: 
 
 
 
 
 Ao multiplicarmos as duas igualdades acima, a primeira por y e a segunda 
por x, obtemos um termo em comum: 
 
 
 
 
𝐺𝐴𝑃 = 𝑧𝑑
∗ − 𝑧𝑝
∗ = 𝒚∗𝑻 ⋅ 𝒃 − 𝒄𝑻 ⋅ 𝒙∗ 
𝑨 ⋅ 𝒙∗ ≤ 𝒃, ou já com as folgas 𝑨 ⋅ 𝒙∗ + 𝒔∗ = 𝒃 
𝒚∗𝑻 ⋅ 𝑨 ≥ 𝒄𝑻, ou já com as folgas 𝒚∗𝑻 ⋅ 𝑨 − 𝒖∗𝑻 = 𝒄𝑻 
𝒚∗𝑻 ⋅ 𝑨 ⋅ 𝒙∗ 
35 
Dualidade Forte e complementariedade de folgas 
 Desta multiplicação encontramos as seguintes equações: 
 
 
 
 
 Igualando, encontramos que o GAP, diferença de funções objetivo do dual 
e primal, é igual á soma dos produtos das folga (primais e duais) pelas 
respectivas variáveis duais (do problema primal, 𝒚, e do problema dual, 
𝒙): 
 
 
 Se 
 
 
 Então o GAP = 0 
 𝒚∗𝑻 ⋅ 𝑨 ⋅ 𝒙∗ = 𝒚∗𝑻 ⋅ 𝒃 − 𝒚∗𝑻 ⋅ 𝒔∗ 
 𝒚∗𝑻 ⋅ 𝑨 ⋅ 𝒙∗ = 𝒄𝑻 ⋅ 𝒙∗ + 𝒖∗𝑻 ⋅ 𝒙∗ 
𝒚∗𝑻 ⋅ 𝒃 − 𝒄𝑻 ⋅ 𝒙∗ = 𝒚∗𝑻 ⋅ 𝒔∗ + 𝒖∗𝑻 ⋅ 𝒙∗ = 𝐺𝐴𝑃 
𝒚∗𝑻 ⋅ 𝒔∗ = 𝟎 
𝒖∗𝑻 ⋅ 𝒙∗ = 𝟎 
Complementaridade 
de Folgas 
36 
Agenda 
 Módulo 1 – Modelagem de problemas de PL 
 Módulo 2 – Propriedades das soluções e o Método Simplex 
 Módulo 3 – Teoria de dualidade e análise de sensibilidade 
 Introduzir o conceito de problema primal e dual (exemplos e interpretações); 
 teorema da dualidade fraca, forte e complementariedade de folgas 
 análise de sensibilidade com relação aos recursos: custo marginal e viabilidade 
primal; 
 análise de sensibilidade com relação a outros parâmetros do problema; 
 aplicações práticas de dualidade em problemas do setor elétrico: custo de 
oportunidade da água (“valor da água”). 
 
 Módulo 4 – Decomposição de Benders e PDDE 
 
 
37 
Análise de Sensibilidade 
 O objetivo da análise de sensibilidade consiste em estudar o 
comportamento do valor da função objetivo e da solução ótima ao 
variarmos os parâmetros do problema: matriz A, vetores c e b 
𝑧𝑝
∗ = Min
𝐱≥𝟎
𝒄𝑻 ⋅ 𝒙
𝑠. 𝑎: 𝑨 ⋅ 𝒙 ≤ 𝒃
 
38 
Análise de Sensibilidade: vetor de recursos 
 Com relação ao vetor b, duas constatações podem ser feitas com base na análise 
do dicionário ótimo: 
 
 
 
 
 O vetor b não tem efeito direto na otimalidade da base, pois não altera o custo 
reduzido; 
 Porém tem direto efeito na viabilidade da solução, pois uma variação pode acarretar em 
um xB < 0. 
 
 Logo, podemos perguntar quanto podemos variar o vetor b sem que este 
inviabiliza a atual solução ótima! 
 Esse range de recursos implica que: 
 apesar de a solução mudar ao variarmos b, a política de produção continuará baseada 
nos mesmos produtos! 
 a variação da de cada insumo terá o efeito na f.obj. decorrente de seu custo marginal 
(variável dual), pois a base não mudará. 
𝑧∗ = 𝒄𝑩
𝑻 ⋅ 𝑩−𝟏 ⋅ 𝒃 + 𝒄𝑵
𝑻 − 𝒄𝑩
𝑻 ⋅ 𝑩−𝟏 ⋅ 𝑵 ⋅ 𝒙𝑵 
𝒙𝑩 = 𝑩
−𝟏 ⋅ 𝒃 − 𝑩−𝟏 ⋅ 𝑵 ⋅ 𝒙𝑵 
39 
Análise de Sensibilidade: vetor de recursos 
 Para que  a base ótima continua viável? 
 
 
 
 
 Ou seja, para deltas que não tornem xB negativo (inviável). 
𝒙𝑩 = 𝑩
−𝟏 ⋅ (𝒃 + 𝚫) − 𝑩−𝟏 ⋅ 𝑵 ⋅ 𝒙𝑵 
𝑩−𝟏 ⋅ 𝒃 + 𝚫 ≥ 𝟎 
xA 
xB 
4 
2 
(1.1) 
4 
2 
(1.2) 
4/3 
4/3 𝛿1 
𝑩−𝟏 ⋅ 
4 + 𝛿1
4 + 𝛿2
 ≥ 𝟎 
𝑩−𝟏 ⋅ 
𝛿1
𝛿2
 ≥ −𝑩−𝟏 ⋅ 
4
4
 = 
−4/3 
−4/3
 
𝛿2 
40 
Análise de Sensibilidade: vetor de recursos 
 Exemplo: Quanto podemos variaro insumo 1 e continuarmos com a 
mesma base ótima? 
 
 
 
 
xA 
xB 
4 
2 
(1.1) 
4 
2 
(1.2) 
4/3 
4/3 
𝛿1 
𝑩−𝟏 ⋅ 
𝛿1
0
 ≥ −𝑩−𝟏 ⋅ 
4
4
 = 
−4/3 
−4/3
 
 
 
2
3
 −
1
3
−
1
3
 
2
3
 ⋅ 
𝛿1
0
 ≥ 
−4/3 
−4/3
 
𝛿1 ≥ −2 
𝛿1 ≤ 4 
41 
Análise de Sensibilidade: vetor de recursos 
 Exemplo: Qual o impacto na função objetivo? 
 Para variações dentro do intervalo anterior, a base não muda (faixa vermelha)! 
Logo: 
 
 
 
 
1 
z*(1) 
y1
* = 5/3 z* =28/3 
𝑧∗ 𝛿1 = 𝑦1
∗ ⋅ 𝑏1 + 𝛿1 + 𝑦2
∗ ⋅ 𝑏2 = 𝑧
∗ + 𝑦1
∗ ⋅ 𝛿1 
4 -2 
42 
Agenda 
 Módulo 1 – Modelagem de problemas de PL 
 Módulo 2 – Propriedades das soluções e o Método Simplex 
 Módulo 3 – Teoria de dualidade e análise de sensibilidade 
 Introduzir o conceito de problema primal e dual (exemplos e interpretações); 
 teorema da dualidade fraca, forte e complementariedade de folgas 
 análise de sensibilidade com relação aos recursos: custo marginal e viabilidade 
primal; 
 análise de sensibilidade com relação a outros parâmetros do problema; 
 aplicações práticas de dualidade em problemas do setor elétrico: custo de 
oportunidade da água (“valor da água”). 
 
 Módulo 4 – Decomposição de Benders e PDDE 
 
 
43 
Análise de Sensibilidade: vetor de custos 
 O que muda se variarmos o cN no ótimo? 
 
 
 
 
 O custo de uma variável não básica só implica na otimalidade do problema; 
 O impacto fica restrito ao custo reduzido da variável não básica que tenha seu custo 
alterado; 
 Tanto o valor da função objetivo quanto a solução não se alteram! 
 
 Logo, para garantirmos que a base ótima não se altera em um problema de Max., 
𝑧∗ = 𝒄𝑩
𝑻 ⋅ 𝑩−𝟏 ⋅ 𝒃 + 𝒄𝑵
𝑻 − 𝒄𝑩
𝑻 ⋅ 𝑩−𝟏 ⋅ 𝑵 ⋅ 𝒙𝑵 
𝒙𝑩 = 𝑩
−𝟏 ⋅ 𝒃 − 𝑩−𝟏 ⋅ 𝑵 ⋅ 𝒙𝑵 
𝒄𝑵(𝒋)
𝑻 − 𝒄𝑩
𝑻 ⋅ 𝑩−𝟏 ⋅ 𝑵𝒋 ≤ 𝟎 
44 
Análise de Sensibilidade: vetor de custos 
 Contudo, ao variarmos cB impactamos em um conjunto muito maior de fatores: 
 
 
 
 
 O custo de uma variável básica implica na otimalidade do problema; 
 O impacto fica restrito ao custo reduzido, porém uma alteração em um custo de uma 
dada variável básica impacta no custo reduzido de todas as não básicas! 
 A função objetivo se altera! 
 
 Logo, para garantirmos que a base ótima não se altera em um problema de Max., 
precisamos reexaminar todos os custos reduzidos! 
𝑧∗ = 𝒄𝑩
𝑻 ⋅ 𝑩−𝟏 ⋅ 𝒃 + 𝒄𝑵
𝑻 − 𝒄𝑩
𝑻 ⋅ 𝑩−𝟏 ⋅ 𝑵 ⋅ 𝒙𝑵 
𝒙𝑩 = 𝑩
−𝟏 ⋅ 𝒃 − 𝑩−𝟏 ⋅ 𝑵 ⋅ 𝒙𝑵 
𝒄𝑵
𝑻 − 𝒄𝑩
𝑻 ⋅ 𝑩−𝟏 ⋅ 𝑵 ≤ 𝟎 
45 
Análise de Sensibilidade: inclusão de variáveis 
 A solução ótima mudaria se uma variável a mais fosse considerada? 
 Não se o seu custo reduzido for negativo na base ótima! 
 Logo, calculamos o custo reduzido desta nova variável e caso este seja negativo, ela 
seria não básica no ótimo (vale zero e não altera a solução) 
 
 
 
 Caso o custo reduzido seja positivo, pode-se aproveitar o dicionário anterior e 
prosseguir no simplex! 
𝑐𝑛𝑒𝑤
𝑇 − 𝒄𝑩
𝑻 ⋅ 𝑩−𝟏 ⋅ 𝑵𝒏𝒆𝒘 ≤ 𝟎 
46 
Agenda 
 Módulo 1 – Modelagem de problemas de PL 
 Módulo 2 – Propriedades das soluções e o Método Simplex 
 Módulo 3 – Teoria de dualidade e análise de sensibilidade 
 Introduzir o conceito de problema primal e dual (exemplos e interpretações); 
 teorema da dualidade fraca, forte e complementariedade de folgas 
 análise de sensibilidade com relação aos recursos: custo marginal e viabilidade 
primal; 
 análise de sensibilidade com relação a outros parâmetros do problema; 
 aplicações práticas de dualidade em problemas do setor elétrico: custo de 
oportunidade da água (“valor da água”). 
 
 Módulo 4 – Decomposição de Benders e PDDE 
 
 
47 
Despacho Físico: Sistema Hidro-Térmico 
 Características do sistema Hídricos com reservatórios: 
 Usinas hidrelétrica podem estar em cascatas 
 Balanço hídrico 
 Volume do reservatório no final de t (vt) é 
igual ao volume inicial de t (vt-1), mais a 
afluência lateral (at) e a montante, menos 
o turbinamento (ut) e vertimento (st). 
 
 
 
 Limites de turbinamento e vertimento 
 Limites de defluência máxima e mínima 
 navegabilidade, recreação, alagamento, ... 
 
 
 
 
 
1 
2 
a2t 
s1t+u
1
t 
a1t 
s2t+u
2
t 𝑣𝑡
1 = 𝑣𝑡−1
1 + 𝑎𝑡
1 − 𝑢𝑡
1 − 𝑠𝑡
1 ∀𝑡 
𝑣𝑡
2 = 𝑣𝑡−1
2 + 𝑎𝑡
2 + 𝑢𝑡
1 + 𝑠𝑡
1 − 𝑢𝑡
2 − 𝑠𝑡
2 ∀𝑡 
𝐴𝑖 ≤ 𝑢𝑡
𝑖 + 𝑠𝑡
𝑖 ≤ 𝐴 𝑖 ∀𝑡, 𝑖 
48 
Despacho Físico: Sistema Hidro-Térmico 
 Função Objetivo: 
 Hidrelétricas possuem um custo praticamente 
zero (desprezíveis se comparados às 
termelétricas, ~ 3 R$/MWh). 
 Logo não são consideradas diretamente na função 
objetivo. 
 Atendimento à demanda: 
 Geração termelétrica + a energia proveniente do 
volume turbinado de cada hidrelétrica + déficit. 
 
 
 O coeficiente de produção de uma usina pode ser 
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 
2 
a2t 
s1t+u
1
t 
a1t 
s2t+u
2
t 
𝑔𝑡
1 + 𝑔𝑡
2 + 𝜌1 ⋅ 𝑢𝑡
1 + 𝜌2 ⋅ 𝑢𝑡
2 + 𝑟𝑡 ≥ 𝑑𝑡 ∀ 𝑡 
𝜌𝑖(𝑣𝑡
𝑖) ⋅ 𝑢𝑡
1 
49 
M(3) 
Despacho Físico: Sistema Hidro-Térmico 
Minimizar
𝐠≥𝟎
𝐮,𝐬≥𝟎
r>0
 𝑐𝑖 ⋅ 𝑔𝑡
𝑖
𝑖∈𝑈𝑇𝐸
+ 𝑐𝑑 ⋅ 𝑟𝑡 
𝑡∈𝑇
𝑠. 𝑎: 𝑔𝑡
𝑖
𝑖∈𝑈𝑇𝐸
+ 𝜌𝑖 ⋅ 𝑢𝑡
𝑖
𝑖∈𝑈𝐻𝐸
+ 𝑟𝑡 ≥ 𝑑𝑡 ∀𝑡 ∈ 𝑇
𝑣𝑡
𝑖 = 𝑣𝑡−1
𝑖 + 𝑎𝑡
𝑖 + 𝑢𝑡
𝑗
+ 𝑠𝑡
𝑗
 
𝑗∈𝑀(𝑖)
− 𝑢𝑡
𝑖 − 𝑠𝑡
𝑖 ∀𝑖 ∈ 𝑈𝐻𝐸, 𝑡 ∈ 𝑇
𝑉𝑖 ≤ 𝑣𝑡
𝑖 ≤ 𝑉 𝑖 ; 𝑆𝑖 ≤ 𝑠𝑡
𝑖 ≤ 𝑆 𝑖 ; 𝑈𝑖 ≤ 𝑢𝑡
𝑖 ≤ 𝑈 𝑖 ∀𝑖 ∈ 𝑈𝐻𝐸, 𝑡 ∈ 𝑇
𝜌𝑖 ⋅ 𝑢𝑡
𝑖 ≤ 𝑃𝑖 ∀𝑖 ∈ 𝑈𝐻𝐸, 𝑡 ∈ 𝑇
𝐴𝑖 ≤ 𝑠𝑡
𝑖 + 𝑢𝑡
𝑖 ≤ 𝐴 𝑖 ∀𝑖 ∈ 𝑈𝐻𝐸, 𝑡 ∈ 𝑇
𝐺𝑖 ≤ 𝑔𝑡
𝑡 ≤ 𝐺 𝑖 ∀𝑖 ∈ 𝑈𝑇𝐸, 𝑡 ∈ 𝑇
 
 UTE: Conjunto de Unidades Termelétricas 
 UHE: Conjunto de Unidades Hidrelétricas 
 M(i): Conjunto de hidrelétricas a montante de i 
 Ex: se i = 3, M(3)={1,2}; se i = 1, M(1)={} 
 
1 
3 
2 
50 
 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 
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. 
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éficits 
futuros 
Despacho Físico: Sistema Hidro-Térmico 
51 
Despacho Físico: Sistema Hidro-Térmico 
𝐶2
∗ 𝑣1 = Min𝐠≥𝟎
v2,u2,s2,r2≥0
𝑐1 ⋅ 𝑔
2
1 + 𝑐2 ⋅ 𝑔
2
2 + 𝑐𝑑 ⋅ 𝑟2
𝑠. 𝑎: 𝑔
2
1 + 𝑔
2
2 + 𝜌 ⋅ 𝑢2 + 𝑟2 ≥ 𝑑2 
𝑣2 + 𝑢2 + 𝑠2 = 𝑣1 + 𝑎2
𝑣2 ≤ 𝑉 ; 𝑠2 ≤ 𝑆 ; 𝑢2 ≤ 𝑈 
𝜌 ⋅ 𝑢2 ≤ 𝑃 
𝐺1 ≤ 𝑔
2
1 ≤ 𝐺 
1
 ; 𝐺2 ≤ 𝑔
2
2 ≤ 𝐺 
2
 
 
 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 
 
52 
Despacho Físico: Sistema Hidro-Té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 5 hm3 
 Demanda igual a 120 MWh 
 
𝐶2
∗ 𝑣1 = Min𝐠≥𝟎
v2,u2,s2,r2≥0
100 ⋅ 𝑔
2
1 + 150 ⋅ 𝑔
2
2 + 500 ⋅ 𝑟2
𝑠. 𝑎: 𝑔
2
1 + 𝑔
2
2 + 1 ⋅ 𝑢2 + 𝑟2 ≥ 120 
𝑣2 + 𝑢2 + 𝑠2 = 𝑣1 + 5
0 ≤ 𝑣2 ≤ 500 ; 0 ≤ 𝑠2 ≤ 100 ; 0 ≤ 𝑢2 ≤ 200
1 ⋅ 𝑢2 ≤ 200 
0 ≤ 𝑔
2
1 ≤ 100 ; 0 ≤ 𝑔
2
2 ≤ 50 
 
53 
Despacho Físico: Sistema Hidro-Térmico 
𝐶2
∗ 𝑣1 = Min𝐠≥𝟎
v2,u2,s2,r2≥0
100 ⋅ 𝑔
2
1 + 150 ⋅ 𝑔
2
2 + 500 ⋅ 𝑟2
𝑠. 𝑎: 𝑔
2
1 + 𝑔
2
2 + 1 ⋅ 𝑢2 + 𝑟2 ≥ 120 
𝑣2 + 𝑢2 + 𝑠2 = 𝑣1 + 5
0 ≤ 𝑣2 ≤ 500 ; 0 ≤ 𝑠2 ≤ 100 ; 0 ≤ 𝑢2 ≤ 200
1 ⋅ 𝑢2 ≤ 200 
0 ≤ 𝑔
2
1 ≤ 100; 0 ≤ 𝑔
2
2 ≤ 50 
 
 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 v1 = 115 hm
3 
 
 
54 
Despacho Físico: Sistema Hidro-Térmico 
𝐶2
∗ 𝑣1 = Min𝐠≥𝟎
v2,u2,s2,r2≥0
100 ⋅ 𝑔
2
10 + 150 ⋅ 𝑔
2
20 + 500 ⋅ 𝑟20
𝑠. 𝑎: 𝑔
2
10 + 𝑔
2
20 + 1 ⋅ 𝑢2120 + 𝑟20 ≥ 120 
𝑣20 + 𝑢2120 + 𝑠20 = 120
0 ≤ 𝑣20 ≤ 500 ; 0 ≤ 𝑠20 ≤ 100 ; 0 ≤ 𝑢2120 ≤ 200
1 ⋅ 𝑢2120 ≤ 200 
0 ≤ 𝑔
2
10 ≤ 100 ; 0 ≤ 𝑔
2
20 ≤ 50 
 
 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 v1 = 115 hm
3 
 
 
55 
Despacho Físico: Sistema Hidro-Té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] hm
3), devemos “abater da demanda” a 
quantidade de geração hídrica máxima e realizar o despacho 
termelétrico remanescente. 
 
 
(R$) 
115 
10.000,0 
𝐶2
∗ 𝑣1 
c2=-150
 
v1 (hm
3) 
𝐶2
∗ 𝑣1 = Min𝐠≥𝟎
v2 ,u2 ,s2 ,r2≥0
100 ⋅ 𝑔2
1 + 150 ⋅ 𝑔2
2 + 500 ⋅ 𝑟2
𝑠. 𝑎: 𝑔2
1 + 𝑔2
2 + 𝑟2 ≥ 120 − min 200, 𝑣1 + 5 
𝑣2 + 𝑢2 + 𝑠2 = 𝑣1 + 5
0 ≤ 𝑣2 ≤ 500 ; 0 ≤ 𝑠2 ≤ 100 ; 0 ≤ 𝑢2 ≤ 200
1 ⋅ 𝑢2 ≤ 200 
0 ≤ 𝑔2
1 ≤ 100 ; 0 ≤ 𝑔2
2 ≤ 50 
 
c1=-100
 
15 
12.250,0 
Despacho hídro 
56 
Despacho Físico: Sistema Hidro-Té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. 
 
 
(R$/MWh) 
115 
100 
v1 (hm
3) 15 
150 
−
𝜕𝐶2
∗ 𝑣1 
𝜕𝑣1
 
𝑦𝑣1 =
𝜕𝐶2
∗ 𝑣1 
𝜕𝑣1
 
(R$) 
115 
10.000,0 
𝐶2
∗ 𝑣1 
c2=-150
 
v1 (hm
3) 
c1=-100
 
15 
12.250,0