Índice
-
- INF05010: Otimização combinatória
- INF05016/CMP 588: Algoritmos avançados
- CMP612: Algorithms
- CMP268: Técnicas de busca heurística
If one would take statistics about which mathematical problem is using up most of the computer time in the world, then … the answer would probably be linear programming. (László Lovász)
Bem-vindo à otimização combinatória.
Carga horária: 60 h (em 30 aulas de 2h)
Créditos: 4
Súmula: Modelagem matemática, programação linear e não-linear. Programação inteira e solução via métodos exatos. Algoritmos de aproximação e heurísticas.
Turma: A.
Horário/Sala: Seg/Qua 10.30, TBD (43425).
Consultas: a combinar.
No. | Data | Tópicos | Notas cáp. | Exercícios | Soluções | Leitura |
---|---|---|---|---|---|---|
Heurísticas | ||||||
1 | 18/03 | Administrativa, Introdução, Busca local. | 10.1,10.2 | Q1 | D1 | |
2 | 20/03 | GRASP, Simulated annealing, Busca local iterada, VNS. | 10.3-10.6 | Q2 | D2 | |
3 | 25/03 | Busca Tabu, Algoritmos genéticos, meméticos. | 11 | |||
Programação linear | ||||||
4 | 27/03 | Introdução: Exemplos e solução gráfica. | 1.1,1.3 | V1,MF1,2 | ||
5 | 01/04 | Formulação e exemplos. | 1.1 | V1,MF2 | ||
6 | 03/04 | Laboratório de formulação (sala 101/43413). | 1.1,B.2 | |||
7 | 08/04 | Forma matricial e normal, introdução método simplex. | 1.2,2.1,2.2 | V2,V6,MF2,3 | ||
8 | 10/04 | Método simplex. Sistemas ilimitados. | 2.3,2.4 | V2,MF3.{1,2} | ||
9 | 15/04 | Método simplex. Pivô tool, fase I. Soluções degeneradas. | 2.5 | V2,MF3.3 | ||
10 | 17/04 | Revisão e exercícios. | V3,MF3.6 | |||
11 | 22/04 | Prova 1 | ||||
12 | 24/04 | Dualidade: Introdução, teoremas de dualidade. | 3.1-3.3 | V5,MF4 | ||
13 | 29/04 | Dualidade: Folgas complementares. Método simplex dual. | 3.2 3.4 | |||
01/05 | Dia do Trabalho | |||||
14 | 06/05 | Método simplex dual. Analise de sensibilidade. | 3.5,3.6 | V6,V7.1 | ||
15 | 08/05 | Analise de sensibilidade. | 3.7 | V6,V7.1 | ||
Programação inteira | ||||||
16 | 13/05 | Introdução e aplicações. | 5, 6.1 | V23,W1.{1-4},PS13.1 | ||
17 | 15/05 | Formulação e exemplos. | 6.1-6.3 | W1.{5-7},PS13.1 | ||
18 | 20/05 | Formulação e demonstrações. | B.2 | |||
19 | 22/05 | Revisão e exercícios. | ||||
20 | 27/05 | Prova 2 | ||||
21 | 29/05 | Matrizes totalmente unimodulares. | 7.1 | W3.{1,2},K5.4,PS13.2 | ||
22 | 03/06 | Problemas com solução simples, desigualdades válidas. | 7.2-3 | W3.{3,4},PS13.2,W8.{1-4} | ||
23 | 05/06 | Algoritmos de planos de corte. | 7.4 | W8.{5,6},PS14.1 | ||
24 | 10/06 | Algoritmos de Branch and bound 1. | 7.5 | W7,G5.2.3 | ||
25 | 12/06 | Algoritmos de Branch and bound 2. | 7.5 | W7,G5.2.3 | ||
26 | 17/06 | Revisão e exercícios. | ||||
27 | 19/06 | Prova 3 | ||||
28 | 24/06 | Algoritmos de aproximação. | ||||
29 | 26/06 | Apresentação de trabalhos. | ||||
30 | 01/07 | Apresentação de trabalhos. | ||||
Provas de recuperação. | ||||||
20/07 | Término oficial das aulas. |
📢: Aula à distância.