MAC 315 - Programação Linear
Professor: Ernesto G. Birgin
egbirgin at ime.usp.br
Monitores: Diaulas S. Marcondes
diaulas at ime.usp.br
e Kennedy A. G. Araujo
kennedy94 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.
-
Programa do curso MAC315, MAC5790, MAP5915.
-
Critério de avaliação
-
Bibliografia básica recomendada
-
Datas importantes (provas e exercícios-programa)
-
Informações importantes sobre exercício-programas
-
Notas
- Exercícios-programa: EP1 e EP2. (A pedido, estes enunciados incluem mais detalhes sobre como devem ser as saídas: EP1 e EP2.
- Listas de exercícios:
- Nas listas abaixo:
- BT refere-se ao livro "Introduction to Linear Optimization" de D. Bertsimas e J. N. Tsitsiklis (editora Athenas Scientific, 1997).
- GL refere-se ao livro "Otimização Combinatória e Programação Linear -- Modelos e Algoritmos" de M. C. Goldbarg e H. P. L. Luna (editora Elsevier, 2005).
- L1: exercícios 1 da página 79 de [GL] e 1.12 de [BT]. Data de entrega sugerida: 24/ago/21 (data limite +7 dias)
- L2: Data de entrega sugerida: 31/ago/21 (data limite +7 dias)
- L3: exercícios 2.4 e 2.5 de [BT]. Data de entrega sugerida: 7/set/21 (data limite +7 dias)
- L4: Data de entrega sugerida: 14/set/21 (data limite +7 dias)
- L5: exercícios 2.9 e 2.10 de [BT]. Data de entrega sugerida: 21/set/21 (data limite +7 dias)
- L6: exercícios
2.11, 2.12 e 2.13 de [BT]. Data de entrega sugerida: 28/set/21 (data limite +7 dias)
- L7: exercícios 3.1, 3.2 e 3.3 de [BT]. Data de entrega sugerida: 04/out/21 (data limite +7 dias)
- L8: exercícios 3.4 e 3.5 de [BT]. Data de entrega sugerida: 11/out/21 (data limite +7 dias)
- L9: exercícios 3.7 e 3.12 de [BT]. Data de entrega sugerida: 18/out/21 (data limite +7 dias)
- L10: exercícios 3.17, 3.18 e 3.19 de [BT]. Data de entrega sugerida: 25/out/21 (data limite +7 dias)
- L11: exercícios 4.1 e 4.2 de [BT]. Data de entrega sugerida: 2/nov/21 (data limite +7 dias)
- L12: exercícios 4.3 e 4.4 de [BT]. Data de entrega sugerida: 9/nov/21 (data limite +7 dias)
- L13: exercícios 4.19 e 4.22 de [BT]. Data de entrega sugerida: 16/nov/21 (data limite +7 dias)
- L14: exercícios 5.1 e 5.5 de [BT]. Data de entrega sugerida: 23/nov/21 (data limite +7 dias)
Horário
LINK: Clique aqui para entrar na aula (nos horarios programados). IMPORTANTE: se tiver, esteja logado no seu email USP, para poder entrar sem a necessidade de autorização.
MATERIAL:
- As aulas da disciplina não serão expositivas e não serão gravadas. 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. No horario das aulas comentaremos brevemente o tópico do dia, tiraremos dúvidas e resolveremos exercícios.
PROGRAMAÇÃO (que definitivamente sofrerá alterações em função do andamento do curso):
- Tópico 0 (1 aula): Boas vindas
- Aula 1: (17/08/21) Encontro inicial.
- Tópico 1 (3 aulas): Introdução, modelagem e resolução gráfica (Capítulo 1 do BT)
- Aula 2: (19/08/21) O que é otimização linear? Modelagem de problemas. Referência: seções 1.1 e 1.2 do BT (Bertsimas e Tsitsiklis). Outras fontes: Aula 1 da playlist de programação linear do Prof. Pedro; V1-1 da playlist da Prof. Wen.
- Aula 3: (24/08/21) Modelando problemas lineares por partes convexos. Referência: seção 1.3 do BT.
- Aula 4: (26/08/21) Representação e resolução gráfica. Referência: seção 1.4 do BT. Outras fontes: Aula 3 da playlist de programação linear do Prof. Pedro; V2-01 até V2-09 da playlist da Prof. Wen.
- A este tópico estão associadas as listas de exercícios L1 e L2.
- Tópico 2 (5 aulas): Geometria de programação linear (Capítulo 2 do BT)
- Aula 5: (31/08/21) Poliedros e conjuntos convexos. Referência: seção 2.1 do BT.
Outras fontes: V3-31 até V3-33 da playlist da Prof. Wen.
- Aula 6: (02/09/21) Pontos extremos, vértices e soluções viáveis básicas. Referência: seção 2.2 do BT.
Outras fontes: V3-34 e V3-35 da playlist da Prof. Wen.
- Aula 7: (09/09/21) Poliedros no formato padrão. Referência: seção 2.3 do BT.
- Aula 8: (14/09/21) Degenerecência. Referência: seção 2.4 do BT.
- Aula 9: (16/09/21) Existência e otimalidade de pontos extremos. Referência: seções 2.5 e 2.6 do BT.
- A este tópico estão associadas as listas de exercícios L3, L4, L5 e L6.
- Tópico 3 (8 aulas): O método simplex (Capítulo 3 do BT)
- Aula 10: (21/09/21) Condições de otimalidade. Referência: seção 3.1 do BT. Outras fontes: V3-01 até V3-30 para o módulo todo.
- Aula 11: (23/09/21) Condições de otimalidade (cont) e inicio de desenvolvimento do método simplex. Referência: seção 3.2 do BT.
- Aula 12: (28/09/21) Desenvolvimento do método simplex (cont).
- Aula 13: (30/09/21) Implementação do método simplex. Referência: seção 3.3 do BT.
- Aula 14: (05/10/21) Implementação do método simplex (cont).
- Aula 15: (07/10/21) Aula adicional sobre tableau com resolução de exercícios.
- Aula 16: (14/10/21) Regras anticiclagem. Referência: seção 3.4 do BT.
- Aula 17: (19/10/21) Encontrando uma solução viável básica inicial. Referência: seção 3.5 do BT.
- A este tópico estão associadas as listas de exercícios L7, L8, L9 e L10.
- Tópico 4 (4 aulas): Teoria de dualidade (Capítulo 4 do BT)
- Aula 18: (21/10/21) Motivação. Referência: seção 4.1 do BT. Outras fontes: V4-01 até V4-12 para o módulo todo.
- Aula 19: (26/10/21) O problema dual. Referência: seção 4.2 do BT.
- Aula 20: (28/10/21) O teorema de dualidade. Referência: seção 4.3 do BT.
Variáveis duais ótimas como custos marginais. Referência: seção 4.4 do BT.
- Aula 21: (04/11/21) Problemas no formato padrão e o método simplex dual. Referência: seção 4.5 do BT.
- A este tópico estão associadas as listas de exercícios L11, 12 e L13.
- Tópico 5 (3 aulas): Análise de sensibilidade (Capítulo 5 do BT)
- Aula 22: (09/11/21) Análise de sensibilidade local. Outras fontes: V5-01 até V5-03 para o módulo todo.
- Aula 23: (11/11/21) Análise de sensibilidade local (cont).
- Aula 24: (16/11/21; 23/11/21 para a turma da tarde) Encontro final.
- A este tópico está associada a lista de exercícios L14.