Tabela de Conteúdos

Otimização combinatória (2025/2)

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.

Informações gerais

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, 111 (43425).
Consultas: a combinar.

Resultados

Notícias

Materiais

Aulas

No. Data Tópicos Notas cáp. Exercícios Soluções Leitura
Heurísticas
1 11/08 Administrativa, Introdução, Busca local. 10.1,10.2 Q1 SQ1, D1
2 13/08 GRASP, Simulated annealing, Busca local iterada, VNS. 10.3-10.6 Q2 SQ2, D2
3 18/08 Busca Tabu, Algoritmos genéticos, meméticos. 11 Q3 SQ3, D3
Programação linear
20/08 Aula inaugural.
4 25/08 Introdução: Exemplos e solução gráfica. 1.1,1.3 Q4 SQ4 V1,MF1,2
5 27/08 Formulação e exemplos. 1.1 E1, Q5 S1, SQ5 V1,MF2
6 01/09 Forma matricial e normal, introdução método simplex. 1.2,2.1,2.2 Q6 SQ6 V2,V6,MF2,3
7 03/09 Laboratório de formulação (sala 103/43413). 1.1,B.2 L SL
8 08/09 Método simplex. Sistemas ilimitados. 2.3,2.4 Q7 SQ7 V2,MF3.{1,2}
9 10/09 Método simplex. Pivô tool, fase I. Soluções degeneradas. 2.5 Q8, E2 SQ8, S2 V2,MF3.3
10 15/09 Revisão e exercícios. E3, UL3 S3 V3,MF3.6
11 17/09 Dualidade: Introdução, teoremas de dualidade. 3.1-3.3 Q9 SQ9 V5,MF4
12 22/09 Prova 1 P1 SP1
13 24/09 Dualidade: Folgas complementares. Método simplex dual. 3.2 3.4 Q10 SQ10
14 29/09 Método simplex dual. Analise de sensibilidade. 3.5,3.6 Q11 SQ11 V6,V7.1
15 01/10 Analise de sensibilidade. 3.7 Q12, E4 SQ12, S4 V6,V7.1
Programação inteira
16 06/10 Introdução e aplicações. 5, 6.1 Q13 SQ13 V23,W1.{1-4},PS13.1
17 08/10 Formulação e exemplos. 6.1-6.3 Q14 SQ14 W1.{5-7},PS13.1
18 13/10 Formulação e demonstrações. B.2 E5 S5
19 15/10 Revisão e exercícios. E6, UL6 S6, D4
20/10 Semana Acadêmica
22/10 Semana Acadêmica
27/10 Dia do Servidor Público
29/10 Revisão e exercícios.
20 03/11 Prova 2 P2 SP2
21 05/11 Matrizes totalmente unimodulares. 7.1 Q15 SQ15 W3.{1,2},K5.4,PS13.2
22 10/11 Problemas com solução simples, desigualdades válidas. 7.2-3 Q16 SQ16 W3.{3,4},PS13.2,W8.{1-4}
23 12/11 Problemas com solução simples, desigualdades válidas. 7.4 Q17, E7 SQ17 W8.{5,6},PS14.1
24 17/11 Algoritmos de planos de corte. 7.5 Q18 SQ18 W7,G5.2.3
25 19/11 Algoritmos de Branch and bound. 7.5 Q19, E8 SQ19 W7,G5.2.3
26 24/11 Revisão e exercícios. E9, UL9 SE9
27 26/11 Prova 3 P3 SP3
28 01/12 Algoritmos de aproximação.
29 08/12 Apresentação de trabalhos.
30 10/12 Apresentação de trabalhos.
15/12 Prova de recuperação.
20/12 Término oficial das aulas.

V: Vanderbei, W: Wolsey, PS: Papadimitriou/Steiglitz MF: Maculan/Fampa

Material

Ferramentas

Bibliografia

Locations of visitors to this page