Programação Não Linear e Dinâmica no Planejamento e Programação da Operação Energética Copyright, 2005 © Notas de Aula - Prof. Secundino Soares COSE -

Pro

gra

ma

ção

Nã

o L

ine

ar

e D

inâ

mic

a n

o P

lan

eja

me

nto

e P

rog

ram

açã

o d

a O

pe

raçã

o E

nerg

étic

a

Slide-1Copyright, 2005 © Notas de Aula - Prof. Secundino Soares

COSE - 2006COSE - 2006

Faculdade de Engenharia Elétrica e de Computação Faculdade de Engenharia Elétrica e de Computação Universidade Estadual de Campinas - UNICAMPUniversidade Estadual de Campinas - UNICAMP

PROGRAMAÇÃO NÃO LINEARPROGRAMAÇÃO NÃO LINEAR

INTRODUÇÃOINTRODUÇÃO

• Modelos de otimizaçãoModelos de otimização

• Componentes e característicasComponentes e características

• Classificação dos ModelosClassificação dos Modelos

• Modelos Não-LinearesModelos Não-Lineares

• Alguns Modelos ClássicosAlguns Modelos Clássicos

• Escopo e Conteúdo do CursoEscopo e Conteúdo do Curso

Pro

gra

ma

ção

Nã

o L

ine

ar

e D

inâ

mic

a n

o P

lan

eja

me

nto

e P

rog

ram

açã

o d

a O

pe

raçã

o E

nerg

étic

a


COSE - 2006COSE - 2006

Programação Não LinearProgramação Não Linear

Definição 1.1 OtimizaçãoDefinição 1.1 Otimização– Ramo da matemática aplicada que se ocupa da determinação das Ramo da matemática aplicada que se ocupa da determinação das

melhores soluções para certos problemas matematicamente bem melhores soluções para certos problemas matematicamente bem definidosdefinidos

Envolve:Envolve:– Estudo de critérios de otimalidadeEstudo de critérios de otimalidade

– Desenvolvimento de métodos algorítmicos de soluçãoDesenvolvimento de métodos algorítmicos de solução

– Análise da estrutura destes métodosAnálise da estrutura destes métodos

– Experimentação numérica em problemas-teste ou em problemas reaisExperimentação numérica em problemas-teste ou em problemas reais

Aplicabilidade dos Métodos de OtimizaçãoAplicabilidade dos Métodos de Otimização– Qualquer área em que se processe informação numérica:Qualquer área em que se processe informação numérica:

– MatemáticaMatemática– EngenhariaEngenharia– EconomiaEconomia

Pro

gra

ma

ção

Nã

o L

ine

ar

e D

inâ

mic

a n

o P

lan

eja

me

nto

e P

rog

ram

açã

o d

a O

pe

raçã

o E

nerg

étic

a


COSE - 2006COSE - 2006


Existência:Existência:• Existe um problema de otimização sempre que, a partir da descrição do Existe um problema de otimização sempre que, a partir da descrição do

problema, é possível identificar, em geral, as seguintes componentes problema, é possível identificar, em geral, as seguintes componentes básicas:básicas:

Objetivos: Objetivos: aspectos essenciais do problema que estão sujeitos a otimizaçãoaspectos essenciais do problema que estão sujeitos a otimização

Variáveis de decisão:Variáveis de decisão: variáveis do problema sob as quais se exerce controle no sentido de variáveis do problema sob as quais se exerce controle no sentido de

otimizar objetivosotimizar objetivos

Restrições:Restrições: fatores que limitam ou restringem os valores que as variáveis de fatores que limitam ou restringem os valores que as variáveis de

decisão do problema podem assumirdecisão do problema podem assumir

Parâmetros:Parâmetros: dados ou recursos necessários ao problema de otimizaçãodados ou recursos necessários ao problema de otimização

Pro

gra

ma

ção

Nã

o L

ine

ar

e D

inâ

mic

a n

o P

lan

eja

me

nto

e P

rog

ram

açã

o d

a O

pe

raçã

o E

nerg

étic

a


COSE - 2006COSE - 2006


Motivações:Motivações:– Utilização racional de recursos escassosUtilização racional de recursos escassos

– EspaçoEspaço– TempoTempo– EnergiaEnergia

– Exploração racional de recursos naturais renováveis/ não-renováveisExploração racional de recursos naturais renováveis/ não-renováveis• MineraçãoMineração• PescaPesca• Papel CelulosePapel Celulose• AgriculturaAgricultura

– Planejamento da atividade econômicaPlanejamento da atividade econômica• Melhoria de serviçosMelhoria de serviços• Melhoria da qualidade de vidaMelhoria da qualidade de vida• Aumento de produtividadeAumento de produtividade

Pro

gra

ma

ção

Nã

o L

ine

ar

e D

inâ

mic

a n

o P

lan

eja

me

nto

e P

rog

ram

açã

o d

a O

pe

raçã

o E

nerg

étic

a


COSE - 2006COSE - 2006


Auguns Fatores ComplicantesAuguns Fatores Complicantes• Presença de múltiplos objetivos, em geral conflitantesPresença de múltiplos objetivos, em geral conflitantes• Ambigüidade entre parâmetros e variáveis de decisãoAmbigüidade entre parâmetros e variáveis de decisão• Incertezas com relação a limites e restrições sobre variáveis e funçõesIncertezas com relação a limites e restrições sobre variáveis e funções• Elementos probabilísticos e variantes no tempoElementos probabilísticos e variantes no tempo• Conhecimento apenas qualitativo de certos aspectos do problemaConhecimento apenas qualitativo de certos aspectos do problema• Dimensão do problemaDimensão do problema

Complexidade X Viablilidade ComputacionalComplexidade X Viablilidade Computacional• Memória e capacidade de processamento dos computadores são limitadasMemória e capacidade de processamento dos computadores são limitadas• Restrições à formulação e ao modelo do problema são necessáriasRestrições à formulação e ao modelo do problema são necessárias

Pro

gra

ma

ção

Nã

o L

ine

ar

e D

inâ

mic

a n

o P

lan

eja

me

nto

e P

rog

ram

açã

o d

a O

pe

raçã

o E

nerg

étic

a


COSE - 2006COSE - 2006


Otimização Como AnáliseOtimização Como Análise– Apoio a tomada de decisões fornecendo ferramentas para a análise do Apoio a tomada de decisões fornecendo ferramentas para a análise do

problema sob diferentes cenáriosproblema sob diferentes cenários

Otimização Como SínteseOtimização Como Síntese– Em muitas situações, o modelo é uma representação fiel do problema a Em muitas situações, o modelo é uma representação fiel do problema a

ser resolvidoser resolvido

Exemplo 1.1Exemplo 1.1 - dentre os retângulos de mesmo perímetro p, encontre o que - dentre os retângulos de mesmo perímetro p, encontre o que produz a maior áreaproduz a maior área

1x

2x

21 22 xxp

Pro

gra

ma

ção

Nã

o L

ine

ar

e D

inâ

mic

a n

o P

lan

eja

me

nto

e P

rog

ram

açã

o d

a O

pe

raçã

o E

nerg

étic

a


COSE - 2006COSE - 2006

Modelo de OtimizaçãoModelo de Otimização

Curvas de nívelCurvas de nível

*1x

*2x

kxx 21

12 x

kx

1x

2x

164

2

2121

p)x,x(f

pxx

****

Solução

Solução Gráfica:Solução Gráfica:

1k 2k 3k

"Restrições"

Decisão" de Variáveis"

""Parâmetro..

.

"Àrea"

Objetivo" "Função

,

""Maximizar

0

0

22

2

1

21

2121

21

),(

x

x

pxxas

xxxx

xxfMax

pp/2/2

pp/2/2

Pro

gra

ma

ção

Nã

o L

ine

ar

e D

inâ

mic

a n

o P

lan

eja

me

nto

e P

rog

ram

açã

o d

a O

pe

raçã

o E

nerg

étic

a


COSE - 2006COSE - 2006


Solução Analítica:Solução Analítica:Como Como 2x2x11 + 2x + 2x22 = p = p, é possível reescrever o problema na forma:, é possível reescrever o problema na forma:

Do cálculo elementar, Do cálculo elementar, g(xg(x11)) atinge um máximo em quando atinge um máximo em quando

ee

Portanto, e

02

)( 1/1211

1 xx

pxg

xMax px

*11 xx

02

2)( *1*

111

1

px

xxxg

dx

d02)( *

1112

1

2

xx

xgdx

d

4*2

*1

pxx 16

),(2

*2

*1

pxxf

Solução Computacional:Solução Computacional:– alternativa quando as soluções gráfica ou analítica não são possíveis.alternativa quando as soluções gráfica ou analítica não são possíveis.

Pro

gra

ma

ção

Nã

o L

ine

ar

e D

inâ

mic

a n

o P

lan

eja

me

nto

e P

rog

ram

açã

o d

a O

pe

raçã

o E

nerg

étic

a


COSE - 2006COSE - 2006


Qualquer problema de otimização pode ser colocado na forma:Qualquer problema de otimização pode ser colocado na forma:

Onde Onde define a região de factibilidadedefine a região de factibilidade. .

No caso do exemplo 1.1No caso do exemplo 1.1

= { x = (x= { x = (x11, x, x22) : x) : x11 0, x 0, x22 0 e 2x 0 e 2x11 + 2x + 2x22 = p } = p }

A otimalidade de x* A otimalidade de x* pode ser expressa como: pode ser expressa como:

f (x*) f (x*) f (x), f (x), x x

– a)a) Condição Necessária de OtimalidadeCondição Necessária de Otimalidade

– b)b) Condição Suficiente de OtimalidadeCondição Suficiente de Otimalidade

0)(*

xxxf

dx

d

0)(*2

2

xx

xfdx

d

xxfMax

x)(

Pro

gra

ma

ção

Nã

o L

ine

ar

e D

inâ

mic

a n

o P

lan

eja

me

nto

e P

rog

ram

açã

o d

a O

pe

raçã

o E

nerg

étic

a


COSE - 2006COSE - 2006

Classificação dos Modelos de OtimizaçãoClassificação dos Modelos de Otimização

– a) Linear a) Linear xx Não LinearNão Linear– b) Mono - Objetivob) Mono - Objetivo xx Multi - ObjetivoMulti - Objetivo– c) Determinísticoc) Determinístico xx EstocásticoEstocástico– d) Diferenciáveld) Diferenciável xx Não - DiferenciávelNão - Diferenciável– e) Estáticoe) Estático xx DinâmicoDinâmico

Exemplo 1.2: Problema da DietaExemplo 1.2: Problema da DietaSelecionar alimentos e suas quantidades de modo a atender necessidades diárias mínimas de nutrientes a um custo mínimo..

• xx11, x, x2 2 , ... , x, ... , xnn : quantidades dos n alimentos

• b1 ,b2 , ... , bm : quantidades mínimas dos m nutrientes

• c1 ,c2 , ... , cn : custo/unidade dos n alimentos

• aij : concentração do nutriente i no alimento j

Pro

gra

ma

ção

Nã

o L

ine

ar

e D

inâ

mic

a n

o P

lan

eja

me

nto

e P

rog

ram

açã

o d

a O

pe

raçã

o E

nerg

étic

a


COSE - 2006COSE - 2006

Modelo de Otimização LinearModelo de Otimização Linear

Objetivo e restrições são funções lineares das variáveis de decisãoObjetivo e restrições são funções lineares das variáveis de decisão..

s.a:s.a:

Características:Características:– AditividadeAditividade

– ProporcionalidadeProporcionalidade

Propriedades:Propriedades:– Solução por algoritmos extremamente eficientesSolução por algoritmos extremamente eficientes

– Convergência em um número finito de passosConvergência em um número finito de passos

nn2211 xc ... xc xc Minx

mnmn2m21m1

n2n2221 21

n1n212111

b x a ... x a xa

b x a ... x axa

b x a ... x a xa

2

1

0 x, ... , x,x n21

Pro

gra

ma

ção

Nã

o L

ine

ar

e D

inâ

mic

a n

o P

lan

eja

me

nto

e P

rog

ram

açã

o d

a O

pe

raçã

o E

nerg

étic

a


COSE - 2006COSE - 2006

Modelo de Otimização Linear Multi - ObjetivoModelo de Otimização Linear Multi - Objetivo

Vários objetivos são considerados simultâneamente.Vários objetivos são considerados simultâneamente.

• s1,s2 , ... , sn : concentração de colesteral/unidade dos n alimentos• h1 ,h2 , ... , hn : concentração de carbohidrato/unidade dos n alimentos

Características:Características:– conflito entre objetivosconflito entre objetivos– perda de otimalidadeperda de otimalidade– solução de compromissosolução de compromisso

nn2211

nn 22 11

nn2211

xh ... xh xh

xs ... xs xs

xc ... xc xc

Minx

mnmn2m21m1

n2n2221 21

n1n212111

b x a ... x a xa

b x a ... x axa

b x a ... x a xa

2

1

0 x, ... , x,x n 21

Pro

gra

ma

ção

Nã

o L

ine

ar

e D

inâ

mic

a n

o P

lan

eja

me

nto

e P

rog

ram

açã

o d

a O

pe

raçã

o E

nerg

étic

a


COSE - 2006COSE - 2006

Objetivos e/ou restrições são funções de variáveis aleatóriasObjetivos e/ou restrições são funções de variáveis aleatórias

valor esperado

Características:Características:– a solução também é caracterizada em termos estatísticosa solução também é caracterizada em termos estatísticos– em geral, busca-se modelos determinísticos equivalentesem geral, busca-se modelos determinísticos equivalentes

Modelo de Otimização EstocásticaModelo de Otimização Estocástica

nn2211 xc ... xc xc Minx

m

n

b xa ... xa xa

b xa ... xa xa

b xa ... xa xa

nmn2m21m1

2n2 222 121

1n1n212111

0 x, ... , x,x n21

c1,c2, ... ,Cn

aij , i = 1,2, ... , n

j = 1,2, ... , m

Variáveis aleatórias Variáveis aleatórias com distribuições de com distribuições de probabilidades probabilidades conhecidas.conhecidas.

Pro

gra

ma

ção

Nã

o L

ine

ar

e D

inâ

mic

a n

o P

lan

eja

me

nto

e P

rog

ram

açã

o d

a O

pe

raçã

o E

nerg

étic

a


COSE - 2006COSE - 2006

Objetivo e/ou restrições são funções não - diferenciáveis das Objetivo e/ou restrições são funções não - diferenciáveis das variáveis de decisãovariáveis de decisãoExemplo: o custo do alimento j pode ser descrito como:Exemplo: o custo do alimento j pode ser descrito como:

Características:• grandes dificuldades numéricas

• caso especial: se são lineares, então Programação

Linear por Partes

Modelo de Otimização Não - DiferenciávelModelo de Otimização Não - Diferenciável

)(xf , )(xf ),(xf djj2j1 jjj

0 q1 q2 xj

cj(xj)

dj1jdj

2j1jj2

1jjj1

jj

qxq),(xf

qxq),(xf

qx0),(xf

)(xc

d

onde: d nº de pontos de não - diferenciabilidade

Pro

gra

ma

ção

Nã

o L

ine

ar

e D

inâ

mic

a n

o P

lan

eja

me

nto

e P

rog

ram

açã

o d

a O

pe

raçã

o E

nerg

étic

a


COSE - 2006COSE - 2006

Modelo de Otimização DinâmicaModelo de Otimização Dinâmica

O modelo é descrito por relações integro - diferenciais; as variáveis de O modelo é descrito por relações integro - diferenciais; as variáveis de decisão são funções do tempodecisão são funções do tempo..

Exemplo 1.3 - Pesca Racional em um lagoExemplo 1.3 - Pesca Racional em um lago

• y(t)y(t) : quantidade de peixes no instante t: quantidade de peixes no instante t• u(t)u(t) : intensidade da pesca no instante t : intensidade da pesca no instante t

• p, q, p, q, , , : constantes: constantes• TT : horizonte de otimização: horizonte de otimização

Características:Características:– Busca-se uma solução do tipo Busca-se uma solução do tipo

– Uma Uma técnica de soluçãotécnica de solução: Programação Dinâmica: Programação Dinâmica

0

T0

)0(),( - ) )(

- ) )(

.Yytu(t)yy(tty

dtu(t)qy(tu(t)ptu

Max

Tt0φ(y(t))u(t)peixe)dee(quantidaddeintensida

f

Pro

gra

ma

ção

Nã

o L

ine

ar

e D

inâ

mic

a n

o P

lan

eja

me

nto

e P

rog

ram

açã

o d

a O

pe

raçã

o E

nerg

étic

a


COSE - 2006COSE - 2006

ANÁLISE GERALANÁLISE GERAL

Diferentes modelos impõem diferentes condições de otimalidade e Diferentes modelos impõem diferentes condições de otimalidade e requerem métodos específicos de abordagem.requerem métodos específicos de abordagem.

Escopo do CursoEscopo do Curso– Curso se limita apenas a modelos de otimizaçãoCurso se limita apenas a modelos de otimização

• Não - LinearesNão - Lineares• Mono - ObjetivosMono - Objetivos• DeterminísticosDeterminísticos• DiferenciáveisDiferenciáveis• EstáticosEstáticos

Modelos de Otimização Não - LinearModelos de Otimização Não - Linear– Em função do tipo de não - linearidade, a otimização não - linear pode Em função do tipo de não - linearidade, a otimização não - linear pode

ser subdividida em:ser subdividida em: Quadrática Fracionária Geométrica Separável

Pro

gra

ma

ção

Nã

o L

ine

ar

e D

inâ

mic

a n

o P

lan

eja

me

nto

e P

rog

ram

açã

o d

a O

pe

raçã

o E

nerg

étic

a


COSE - 2006COSE - 2006

Modelo de Otimização QuadráticaModelo de Otimização Quadrática

– Considere o modelo estocástico do problema da dieta; os custos são variáveis aleatórias.

• Valor médio da função objetivo

• Variância da função objetivoVariância da função objetivo

– Alternativa

– Restrição de Custo:Restrição de Custo:

nn xcxcxc ...2211

jij,i xxv

n

1j

n

1i

jij

ji xxvx

Minn n

i

1 1

0...2211 cxcxcxc nn 0 x, ... , x,x n21

mnmn2m2m1

2n22221

1n1n21211

b x a ... x a xa

b x a ... x axa

b x a ... x a xa

1

2n1

1

Pro

gra

ma

ção

Nã

o L

ine

ar

e D

inâ

mic

a n

o P

lan

eja

me

nto

e P

rog

ram

açã

o d

a O

pe

raçã

o E

nerg

étic

a


COSE - 2006COSE - 2006

Seja p a probabilidade de que o custo da dieta seja menor ou igual a cº.

p = probp = probcc11xx11 + c + c11xx1 + ... + 1 + ... + ccnnxxnn c coo

Por hipótese, suponha que ci = i + w i, onde w é uma variável aleatória. Neste caso,

Problema:Problema:

Modelo de Otimização FracionáriaModelo de Otimização Fracionária

0

1

)( cxwprobp iii

n

j

n

iii

n

iii

x

xcwprobp

1

1

0

n

iii

n

iii

x

xcMax

x1

1

0

mnmn2m21m1

2n2n2221 21

1n1n212111

b x a ... x a xa

b x a ... x axa

b x a ... x a xa

0 x, ... , x,x n 21

Pro

gra

ma

ção

Nã

o L

ine

ar

e D

inâ

mic

a n

o P

lan

eja

me

nto

e P

rog

ram

açã

o d

a O

pe

raçã

o E

nerg

étic

a


COSE - 2006COSE - 2006

Problemas geométricos são freqüentes em projetos de engenharia.Problemas geométricos são freqüentes em projetos de engenharia.

Exemplo 1.4Exemplo 1.4 - Encontre o raio x - Encontre o raio x11 e a altura x e a altura x22 de um cilindro cujo volume não de um cilindro cujo volume não

seja inferior a v e que apresente custo de construção mínimo.seja inferior a v e que apresente custo de construção mínimo.

Onde:Onde: e e

c1 : custo/unid. área circular;

c2 : custo/unid. área lateral.

As funções do modelo de otimização geométrica são compostas por As funções do modelo de otimização geométrica são compostas por termos do tipo:termos do tipo:

Modelo de Otimização GeométricaModelo de Otimização Geométrica

2211

21 22 cxxcxMin

x

Vxx 221 021 xx

x2

x1

0aa1iij

n

1i

ijiii tk , xkt

Pro

gra

ma

ção

Nã

o L

ine

ar

e D

inâ

mic

a n

o P

lan

eja

me

nto

e P

rog

ram

açã

o d

a O

pe

raçã

o E

nerg

étic

a


COSE - 2006COSE - 2006

Outros ModelosOutros Modelos

Outros modelos de otimização cuja importância advém de características Outros modelos de otimização cuja importância advém de características estruturais.estruturais.

Modelo de Otimização Inteira / Mista– As variáveis de decisão (ou parte delas) só podem assumir valores

inteiros.

xi = 0,1,2,3, ....

Modelo de Otimização SeparávelModelo de Otimização Separável

n

1i

)(fMin ii xx

n1,2,3,...,i

m1,2,3,...,j

0x

0)(xg

i

n

1iiij

RRg

RRf

ij

i

:)(

:)(

Pro

gra

ma

ção

Nã

o L

ine

ar

e D

inâ

mic

a n

o P

lan

eja

me

nto

e P

rog

ram

açã

o d

a O

pe

raçã

o E

nerg

étic

a


COSE - 2006COSE - 2006

Escalas de Problemas de OtimizaçãoEscalas de Problemas de Otimização

– O porte do problema de otimização é função:O porte do problema de otimização é função:• da quantidade de memóriada quantidade de memória• do esforço computacionaldo esforço computacional

necessários para obter sua solução.necessários para obter sua solução.

– A análise do porte (grande, médio, pequeno) é complicada por alguns A análise do porte (grande, médio, pequeno) é complicada por alguns fatores:fatores:

• Diversidade de arquiteturasDiversidade de arquiteturas• Surgimento de novas tecnologiasSurgimento de novas tecnologias

• Processamento paraleloProcessamento paralelo• Programação concorrenteProgramação concorrente

– Desempenho de algoritmosDesempenho de algoritmos• Número de bytes alocadosNúmero de bytes alocados• Tempo de CPU (relativa)Tempo de CPU (relativa)• Número de operações elementares (absoluta)Número de operações elementares (absoluta)

Pro

gra

ma

ção

Nã

o L

ine

ar

e D

inâ

mic

a n

o P

lan

eja

me

nto

e P

rog

ram

açã

o d

a O

pe

raçã

o E

nerg

étic

a


COSE - 2006COSE - 2006

Otimização na FEEC / UNICAMPOtimização na FEEC / UNICAMP

TeoriaTeoria– Desenvolvimento de novos métodos / algoritmosDesenvolvimento de novos métodos / algoritmos

AplicaçõesAplicações– Quase sempre vinculados a convênios com organizações públicas.Quase sempre vinculados a convênios com organizações públicas.

• ANEEL, ONS, DUKE, CESP, AES, ELETROPAULO, CPFL ANEEL, ONS, DUKE, CESP, AES, ELETROPAULO, CPFL • TELEBRAS, RFFSA, TELESPTELEBRAS, RFFSA, TELESP

Algumas ÀreasAlgumas Àreas– Planejamento e controle da produçãoPlanejamento e controle da produção

– Planejamento e programação de sistemas eletro-energéticosPlanejamento e programação de sistemas eletro-energéticos

– Transportes (urbanos, ferroviários, ...)Transportes (urbanos, ferroviários, ...)

– Planejamento de redes de comunicaçãoPlanejamento de redes de comunicação

Pro

gra

ma

ção

Nã

o L

ine

ar

e D

inâ

mic

a n

o P

lan

eja

me

nto

e P

rog

ram

açã

o d

a O

pe

raçã

o E

nerg

étic

a


COSE - 2006COSE - 2006

Exemplo de AplicaçãoExemplo de Aplicação

PROBLEMAS DE LOCALIZAÇÃO E TRANSPORTEPROBLEMAS DE LOCALIZAÇÃO E TRANSPORTE

– N Fábricas

– M Mercados

Problema:Problema: Determine as localizações Determine as localizações ( x( xii, y, yi i ), ), i = 1,2, ... , Ni = 1,2, ... , N das fábricas e os volumes a das fábricas e os volumes a

transportar transportar wwij ij , , i =1,2, ... , N ; j = 1,2, ... , Mi =1,2, ... , N ; j = 1,2, ... , M de forma a minimizar a soma total de forma a minimizar a soma total

das distâncias percorridas.das distâncias percorridas.– ccii : capacidade da fábrica: capacidade da fábrica i i

– rrjj : demanda do mercado : demanda do mercado jj

– ddijij : distância entre a fábrica: distância entre a fábrica i i e o mercado e o mercado jj

– wwijij : volume destinado pela fábrica: volume destinado pela fábrica i i ao mercado ao mercado jj..

(a2,b2)

(a1,b1)

(a3,b3)

r1

r2

r3

(x1,y1)

(x2,y2)

F1

F2

c1

c2

M1

M2

M3

Pro

gra

ma

ção

Nã

o L

ine

ar

e D

inâ

mic

a n

o P

lan

eja

me

nto

e P

rog

ram

açã

o d

a O

pe

raçã

o E

nerg

étic

a


COSE - 2006COSE - 2006

Exemplo de AplicaçãoExemplo de Aplicação


No ModeloNo Modelo,,– as distâncias são ponderadas pelos volumesas distâncias são ponderadas pelos volumes– ddijij = f(x = f(xii,y,yii,a,ajj,b,bjj).). Por exemplo, Por exemplo,

: região do plano xy onde é possível localizar as fábricas

M

1i

N

1jij

i,i

ijijwyx

dwMin1,2,...,Ni

M

jiij ,

1cw

1,2,...,Mj

N

1ijij ,rw

Ω),y(x

,

ii

1,2, ... Mj, 1,2, ... Niij 0w

22 )by()ax(d jijiij

Pro

gra

ma

ção

Nã

o L

ine

ar

e D

inâ

mic

a n

o P

lan

eja

me

nto

e P

rog

ram

açã

o d

a O

pe

raçã

o E

nerg

étic

a


COSE - 2006COSE - 2006

Exemplo de aplicaçãoExemplo de aplicação

Problema:Problema:Determinar os níveis de geração térmica e hidráulica de forma a atender Determinar os níveis de geração térmica e hidráulica de forma a atender a demanda em cada período do horizonte de planejamento a um custo a demanda em cada período do horizonte de planejamento a um custo mínimo.mínimo.

Subsistema TérmicoSubsistema Térmico

ggijij: : geração da térmica i no período jgeração da térmica i no período j

ccii: custo de geração da: custo de geração da térmica itérmica i

GeraçãoGeraçãoTérmicaTérmica

GeraçãoGeraçãoHidráulicaHidráulica

Dj = Demanda

Tj

Hj + Tj= DjHj

gij

ci (gij)

0

Pro

gra

ma

ção

Nã

o L

ine

ar

e D

inâ

mic

a n

o P

lan

eja

me

nto

e P

rog

ram

açã

o d

a O

pe

raçã

o E

nerg

étic

a


COSE - 2006COSE - 2006


– A dinâmica do reservatório da usina i pode ser modelada com:

xi,j+1 = xij - uij + zij + yij

– Na equação dinâmica;

• zij : representa o volume total de água defluído no período j pelas usinas que estão imediatamente acima da usina i

• yij : representa o volume total de água afluente incremental (lateral) que chega à usina i no período j

Pro

gra

ma

ção

Nã

o L

ine

ar

e D

inâ

mic

a n

o P

lan

eja

me

nto

e P

rog

ram

açã

o d

a O

pe

raçã

o E

nerg

étic

a


COSE - 2006COSE - 2006


– Devido ao elevado custo da energia térmica, o problema é normalmente Devido ao elevado custo da energia térmica, o problema é normalmente formulado como:formulado como:

N

j

n

iiji

ij

kj

gcMingu

1 1

)(

j

n m

kkjij D

ig

1 1

kjkj( x( xkjkj, u, ukj kj ) = k) = kkkuukj kj kjkj(x(xkjkj))

xk,j+1 = xkj - ukj + zkj + ykj

kkjuuu k

kkjk xxx

iijiggg

i = 1,2, ... , n

j = 1,2, ... ,N

N:N: horizonte horizonten:n: nº de térmicas nº de térmicasm:m: nº de hidráulicas nº de hidráulicas

k = 1,2, ... , m

Pro

gra

ma

ção

Nã

o L

ine

ar

e D

inâ

mic

a n

o P

lan

eja

me

nto

e P

rog

ram

açã

o d

a O

pe

raçã

o E

nerg

étic

a


COSE - 2006COSE - 2006

Conclusão GeralConclusão Geral

A grande diversidade de modelos e aplicações de otimização não - linear A grande diversidade de modelos e aplicações de otimização não - linear torna necessária uma abordagem genérica do problematorna necessária uma abordagem genérica do problema

Neste curso, considera-se problemas de programação matemática na Neste curso, considera-se problemas de programação matemática na forma geral.forma geral.

O conjunto é normalmente reservado para descrever restrições mais simples. Por exemplo,

Min Min (x)(x) xx hi(x) = 0, i=1,2, ... , m

gj(x) 0, j=1,2, ... , n x onde:onde:

x Rn

(.):Rn R, ; hi(.):Rn R; gj(.):Rn R

0: xRx n

Pro

gra

ma

ção

Nã

o L

ine

ar

e D

inâ

mic

a n

o P

lan

eja

me

nto

e P

rog

ram

açã

o d

a O

pe

raçã

o E

nerg

étic

a


COSE - 2006COSE - 2006

Dois Aspectos CentraisDois Aspectos Centrais

– Primeiro:estabelecer condições necessárias e/ou suficientes para que dada solução x* seja considerada um mínimo do problema;

– Segundo: estudar o comportamento de algoritmos que obtém x* como o limite de uma seqüência de soluções xo, x1, ... , x* que converge satisfazendo as condições de otimalidade do problema.

– Estratégia• abordagem em grau crescente de complexidade

problemas irrestritos problemas com restrições de igualdade problemas com restrições de igualdade e desigualdade

– Antes dissoAntes disso;• fundamentos teóricos

Documents

Programação Não Linear e Dinâmica no Planejamento e Programação da Operação Energética Copyright, 2005 © Notas de Aula - Prof. Secundino Soares COSE -