Otimização (CI-1238 / Turma B)

Professor: Murilo V. G. da Silva - murilo@inf.ufpr.br

Início das aulas: 03/03/2026
Data da primeira prova: 14/04/2026
Data da segunda prova: 16/06/2026
Data da prova final: 30/06/2026

Avaliação: duas provas + dois trabalhos

Lista de exercícios: [aqui]

TRABALHO 1: [aqui] -- ENTREGA DIA 20/04/2026
TRABALHO 2: [aqui] -- ENTREGA DIA 15/06/2026

INTRODUÇÃO À OTIMIZAÇÃO
Leituras: [PAP98: sec 1.1 e 1.2] [KS99: sec. 1.1] [KT05: cap. 1]
Programa:
- Apresentação do curso e conceitos preliminares [slides 01] [slides 01 (compacto)]
- Problemas otimização [slides 02] [slides 02 (compacto)]
- Espaço de soluções de problemas [slides 03] [slides 03 (compacto)]

PROGRAMAÇÃO LINEAR - MODELAGEM
Leituras: [MAT07: sec 1.1, sec 2.1-4 e 2.7]
Cronograma:
- Introdução à Programação Linear; Modelagem por PL [slides 04] [slides 04 (compacto)]

PROGRAMAÇÃO LINEAR - ALGORITMO SIMPLEX
Leituras: [MAT07: sec. 4.1, 4.1, 4.4 e cap. 5]
Cronograma:
- Formas equacionais e soluções básicas [slides 05] [slides 05 (compacto)]
- Algoritmo Simplex [slides 06] [slides 06 (compacto)]
- Dualidade em Programação Linear [slides 07] [slides 07 (compacto)]
- Relaxamento em PLI's [slides 08] [slides 08 (compacto)]


09/04 - Revisão
14/04 - PROVA 1

ALGORITMOS DE ENUMERAÇÃO
Leituras: [KS99: cap 1-2]
Cronograma:
- Enumeração em Ordem Lexicográfica: [slides 09] [slides 09 (compacto)]
- Enumeração em Ordem de mudança mínima: [slides 10] [slides 10 (compacto)]

ALGORITMOS DE BACKTRACKING E BRANCH-AND-BOUND
Leituras: [KS99: cap 4]
Cronograma:
- Algoritmos de Backtracking (parte 1): [slides 11] [slides 11 (compacto)]
- Algoritmos de Backtracking (parte 2): [slides 12] [slides 12 (compacto)]
- Algoritmos de Branch-and-Bound [slides 13] [slides 13 (compacto)]

PROGRAMAÇÃO DINÂMICA
Leituras: [CLSR: cap. 15][DPV06: cap. 6]
Cronograma:
- Programação Dinâmica (parte 1): [slides 14] [slides 14 (compacto)]
- Programação Dinâmica (parte 2): [slides 15] [slides 15 (compacto)]

ALGORITMOS GULOSOS E APROXIMAÇÃO
Leituras: [DPV06: cap. 5]
Cronograma:
- Algoritmos Gulosos
- Algoritmos de Aproximação

11/06 -- Revisão
16/06 -- PROVA 2
30/06 -- PROVA FINAL

Bibliografia