DAS-6651: Métodos de Otimização –
Teoria e Aplicações em Automação
DAS-6651
Eduardo Camponogara
1
0. Agenda
1.
2.
3.
4.
5.
2
Apresentação
Descrição e objetivos da disciplina
Plano da disciplina
Problema motivador: roteamento de pacotes
em redes de computadores
Problema motivador: gerenciamento da
produção em poços de petróleo
1. Apresentação
Eduardo Camponogara
Departamento de Automação e Sistemas
Sala DAS-338
Fone: 331-7688
E-mail: [email protected]
Página da disciplina:
http:www.das.ufsc.br/~camponog/Disciplinas/DAS-6651
3
2. Descrição e Objetivos



4
Visão abrangente do campo da otimização
Desenvolver a habilidade de modelar
problemas diversos, de natureza linear,
discreta e/ou não-linear
Estudo de cada sub-domínio, classes de
problemas e um algoritmo básico
2. Descrição e Objetivos
5
2. Descrição e Objetivos



6
Familiarizar os alunos com as diversas facetas
da otimização
Desenvolver a habilidade de traduzir
problemas não-estruturados em uma
linguagem formal
Entendimento elementar das classes de
problemas e algoritmos básicos
2. Como Atingir os Objetivos?

Listas de exercícios
–
7
De solução imediata, intermediários e mais
desafiadores

Experiência prática com experimentos
computacionais

Estudo de caso, dependendo do interesse de
cada aluno, com relatório final
3. Plano da Disciplina
8
1.
Apresentação
2.
Visão geral do domínio da otimização: modelagem
3.
Otimização irrestritra diferenciável: algoritmo de
descenso
4.
Otimização irrestritra diferenciável: algoritmo de
Newton e suas variações
3. Plano da Disciplina
9
5.
Otimização irrestrita não-diferenciável: algoritmo
genético e simulated annealing
6.
Aplicações de otimização irrestrita: treinamento de
redes neurais
7.
Programação linear: modelos, modelagem e
algoritmo básico
8.
Programação linear: dualidade, notação matricial e
teoria dos jogos
3. Plano da Disciplina
10
9.
Linguagens de modelagem Mosel e AMPL
10.
Fluxo em redes: problemas em grafos, algoritmos e
aplicações
11.
Programação inteira: formulação de problemas e
aplicações
12.
Programação inteira: condições de otimalidade e
relaxações
3. Plano da Disciplina
11
13.
Programação inteira: algoritmos exatos
14.
Apresentação de propostas de projetos
15.
Programação dinâmica: caso discreto e algoritmo
básico
16.
Programação dinâmica: caso contínuo
17.
Programação não-linear restrita: problemas
reduzidos e condições de otimalidade
3. Plano da Disciplina
12
18.
Programação não-linear restrita: método
Lagrangeano aumentado
19.
Programação não-linear restrita: algoritmo de região
de confiança
20.
Programação não-linear restrita: sequential quadratic
programming (SQP)
21.
Aplicações de programação não-linear restrita
3. Plano da Disciplina
22.
13
Apresentação de relatório final de projetos
3. Referências e Materiais

Notas de aula, capítulos de livros, slides e
assuntos expostos no quadro

Variedade grande de livros

Sítios com informações
http://www-neos.mcs.anl.gov

14
Software proprietário e de domínio público
4. Roteamento de Pacotes em
Redes de Computadores
• Grafo G=(V,E) com topologia da rede
Redes MPLS
• Capacidade uij de cada arco (i, j)
• Custo de transmissão/atraso cij
• Conjunto de requisições de serviço
(LSPs)
•sk – nó origem
•dk – nó destino
• lk – demanda de transmissão
15
Roteador
4. Roteamento de Pacotes em
Redes de Computadores
Minimize k=1,…,K (i,j)E cijxijk
Sujeito a:
k=0,…,K lkxijk  uij
e  d+(s_k) xek = 1
e  d-(d_k) xek = 1
ed+(i)xek - ed-(i)xek = 0
xek  {0, 1}
16
para cada (i,j)  E
para k = 1, …, K
para k = 1, …, K
para k, para todo i,
i  sk e i  dk
para k = 1, …, K e e E
4. Roteamento de Pacotes em
Redes de Computadores

Métodos de solução
–
–
–
17
Algoritmo Lagrangeano
Algoritmos exatos e programação inteira
Heurísticas
5. Gerenciamento da Produção em
Poços de Petróleo
18
5. Gerenciamento da Produção em
Poços de Petróleo
Maximize j=1npogojqjo - j=1npwgwjqjo - j=1npiqji
Sujeito a:
lj yj  qji ujyj
j = 1, …, n
qjo = ajo yj + aj1qji + aj2[qji]2 + aj3[qji]3 j = 1, …, n
yj  {0, 1}
j = 1, …, n
19
6. Fim
Obrigado pela presença!!!
20