MAC 315 - MAC 5790 - MAP 5915 - Otimização Linear
Professor: Ernesto G. Birgin
egbirgin at ime.usp.br
Monitor: Diaulas S. Marcondes
diaulas 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 x: (16/08/21) Não haverá aula (recepção aos novos alunos da Pós-Graduação do IME).
- Aula 1: (18/08/21) O que é otimização linear? Modelagem de problemas. Referências: seções 1.1 e 1.2.
- Aula 2: (23/08/21) 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: (25/08/21) Poliedros e conjuntos convexos. Referência: seção 2.1.
- Aula 4: (30/08/21) Pontos extremos, vértices e soluções viáveis básicas. Referência: seção 2.2.
- Aula 5: (01/09/21) Poliedros no formato padrão. Referência: seção 2.3.
- Aula x: (06/09/21) Semana da pátria. Não haverá aula.
- Aula x: (08/09/21) Semana da pátria. Não haverá aula.
- Aula 6: (13/09/21) Degenerecência. Referência: seção 2.4.
- Aula 7: (15/09/21) Existência e otimalidade de pontos extremos. Referência: seções 2.5 e 2.6.
- Aula 8: (20/09/21) Aula de exercícios.
Tópico 3 (6 aulas + 1 aula dúvidas/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: (22/09/21) Condições de otimalidade. Referência: seção 3.1.
- Aula 10: (27/09/21) Desenvolvimento do método simplex. Referência: seção 3.2.
- Aula 11: (29/09/21) Aula de dúvidas e exercícios.
- Aula 12: (04/10/21) P1 (às 10 horas em sala a definir)
- Aula 13: (06/10/21) Revisão da correção da P1.
- Aula 14: (11/10/21) Semana de estudos individuais. Não haverá aula presencial.
- Aula 15: (13/10/21) Semana de estudos individuais. Não haverá aula presencial.
- Aula 16: (18/10/21) Implementação do método simplex. Referência: seção 3.3.
- Aula 17: (20/10/21) Implementação do método simplex (cont).
- Aula 18: (25/10/21) Regras anticiclagem. Referência: seção 3.4.
- Aula 19: (27/10/21) 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: (01/11/21) Motivação. Referência: seção 4.1.
- Aula 21: (03/11/21) O problema dual. Referência: seção 4.2.
- Aula 22: (08/11/21) O teorema de dualidade. Referência: seção 4.3. Variáveis duais ótimas como custos marginais. Referência: seção 4.4.
- Aula 23: (10/11/21) Problemas no formato padrão e o método simplex dual. Referência: seção 4.5.
Tópico 5 (2 aulas + 3 aulas de dúvidas/exercícios/revisão + P2 + Psub): Análise de sensibilidade (Capítulo 5 do BT)
- Aula xx: (15/11/21) Proclamação da República. Não haverá aula.
- Aula 24: (17/11/21) Análise de sensibilidade local. Referência: seção 5.1.
- Aula 25: (22/11/21) Análise de sensibilidade local (cont).
- Aula 26: (24/11/21) Aula de dúvidas e exercícios.
- Aula 27: (29/11/21) P2 (às 10 horas em sala a definir)
- Aula 28: (01/12/21) Revisão da correção da P2 e aula de dúvidas e exercícios.
- Aula 29: (06/12/21) Psub (às 10 horas em sala a definir)
- Aula 30: (08/12/21) Revisão da correção da Psub.