MAC 315 - MAC 5790 - MAP 5915 - Otimização Linear
Professor: Ernesto G. Birgin
egbirgin at ime.usp.br
Monitor PAE: Juan Sebastián Castaño Franco
jcastanof at ime.usp.br
O livro "Introduction to Linear Optimization" de D. Bertsimas e
J. N. Tsitsiklis (editora Athenas Scientific, 1997) contém todo o material do curso. Sugerimos fortemente que os alunos consultem este livro e façam os exercícios de cada capítulo. Veja a errata aqui.
Não deixe de ler nenhuma das páginas da disciplina, especialmente, a
referente ao critério de avaliação.
MATERIAL:
O conteúdo do curso está contido no livro do Bertsimas mencionado acima. Existe também uma série de videoaulas da Prof. Wen Shen da Penn State University que cobre a maioria dos tópicos da disciplina e uma série de videaulas do Prof. Pedro Munari da UFSCar que cobre alguns tópicos da disciplina.
PROGRAMAÇÃO (que definitivamente sofrerá alterações em função do andamento do curso):
Tópico 1 (2 aulas): Introdução, modelagem e resolução gráfica (Capítulo 1 do BT)
- Aula 1: (04/08/26) O que é otimização linear? Modelagem de problemas. Referências: seções 1.1 e 1.2.
- Aula 2: (06/08/26) Modelando problemas lineares por partes convexos. Representação e resolução gráfica. Referência: seções 1.3 e 1.4.
Tópico 2 (5 aulas + 1 aula de exercícios): Geometria de programação linear (Capítulo 2 do BT)
- Aula 3: (11/08/26) Poliedros e conjuntos convexos. Referência: seção 2.1.
- Aula 4: (13/08/26) Pontos extremos, vértices e soluções viáveis básicas. Referência: seção 2.2.
- Aula x: (18/08/26) Brazil-China Optimization Workshop 2026. Não haverá aula.
- Aula 5: (20/08/26) Poliedros no formato padrão. Referência: seção 2.3.
- Aula 6: (25/08/26) Degenerecência. Referência: seção 2.4.
- Aula 7: (27/08/26) Existência e otimalidade de pontos extremos. Referência: seções 2.5 e 2.6.
- Aula 8: (01/09/26) Aula de exercícios.
Tópico 3 (6 aulas + 1 aula de exercícios + P1 + 1 aula revisão da correção + 2 aulas de estudos individuais): O método simplex (Capítulo 3 do BT)
- Aula 9: (03/09/26) Condições de otimalidade. Referência: seção 3.1.
- Aula xx: (08/09/26) Semana da Pátria e 2nd Joint Meeting Brazil-Italy in Mathematics. Não haverá aula.
- Aula xx: (10/09/26) Semana da Pátria e 2nd Joint Meeting Brazil-Italy in Mathematics. Não haverá aula.
- Aula xx: (15/09/26) CNMAC2026. Não haverá aula.
- Aula 10: (17/09/26) Desenvolvimento do método simplex. Referência: seção 3.2.
- Aula 11: (22/09/26) Aula de exercícios
- Aula 12: (24/09/26) P1
- Aula 13: (29/09/26) Revisão da P1.
- Aula 14: (01/10/26) Implementação do método simplex. Referência: seção 3.3.
- Aula 15: (06/10/26) Implementação do método simplex (cont).
- Aula 16: (08/10/26) Regras anticiclagem. Referência: seção 3.4.
- Aula 17: (13/10/26) Semana de estudos individuais e Comissão de Avaliação do IMPA. Não haverá aula presencial.
- Aula 18: (15/10/26) Semana de estudos individuais. Não haverá aula presencial.
- Aula 19: (20/10/26) Encontrando uma solução viável básica inicial. Referência: seção 3.5.
Tópico 4 (4 aulas): Teoria de dualidade (Capítulo 4 do BT)
- Aula 20: (22/10/26) Motivação. Referência: seção 4.1. O problema dual. Referência: seção 4.2.
- Aula 21: (27/10/26) O teorema de dualidade. Referência: seção 4.3. Variáveis duais ótimas como custos marginais. Referência: seção 4.4.
- Aula 22: (29/10/26) Problemas no formato padrão e o método simplex dual. Referência: seção 4.5.
- Aula 23: (03/11/26) Análise de sensibilidade local. Referência: seção 5.1.
Tópico 5 (1 aula + 3 aulas de exercícios/revisão + P2 + Psub): Análise de sensibilidade (Capítulo 5 do BT)
- Aula 24: (05/11/26) Análise de sensibilidade local (continuação).
- Aula 25: (10/11/26) Aula de exercícios.
- Aula 26: (12/11/26) P2
- Aula 27: (17/11/26) Revisão da P2 e aula de exercícios.
- Aula 28: (19/11/26) Psub
- Aula 29: (24/11/26) Revisão da Psub.